第3章 命题逻辑.ppt

1、离 散 数 学,2020年10月9日星期五,2020/10/9,数理逻辑（Mathematical Logic） 是研究演绎推理的一门学科，用数学的方法来研究推理的规律统称为数理逻辑。 公元前四世纪由希腊的亚里斯多德首创 他力图把思维形式和存在联系起来， 并按照客观实际来阐明逻辑的范畴。,第二篇 数理逻辑,2020/10/9,主要研究内容：推理 着重于推理过程是否正确 着重于语句之间的关系 主要研究方法：数学的方法 就是引进一套符号体系的方法，所以数理逻辑又叫符号逻辑（Symbolic Logic）。,第二篇 数理逻辑,2020/10/9,什么是数理逻辑 ？ 用数学的方法来研究推理的规律统称为

2、数理逻辑。 为什么要研究数理逻辑？ 程序算法数据 算法逻辑控制,总结,日常语言叫做自然语言。 自然语言丰富，但是也有模棱两可的特性。,小朱和小张在寝室聊天，小李破门而入，小朱感叹：“说曹操曹操到。”（经典问题） 1、请问是谁来了? A、小朱 B、小张 C、小李D、曹操 2、门破了没有？ A、破了 B、没破,一个风和日丽的早晨，Summer跑过来对小王说：“好激动啊，刚刚捡到了100块钱啊！”小王说：“天上掉馅饼的事，你都遇到了！”请问：天上在下着什么？ A、小雨 B、钱 C、没下 D、馅饼,需要引入一种形式化语言单一、明确 这种形式化语言在数理逻辑中叫做目标语言 目标语言和一些规定的公式与符号

3、构成了数理逻辑的形式符号体系。,2020/10/9,第二篇 数理逻辑,2020/10/9,第三章 命题逻辑,命题逻辑也称命题演算，或语句逻辑。 研究内容： （1）研究以命题为基本单位构成的前提和结论之间的可推导关系 （2）研究什么是命题？ （3）研究如何表示命题？ （4）研究如何由一组前提推导一些结论？,2020/10/9,第三章 命题逻辑,命题逻辑的特征： 在研究逻辑的形式时，我们把一个命题只分析到其中所含的命题成份为止，不再分析下去。不把一个简单命题再分析为非命题的集合，不把谓词和量词等非命题成份分析出来。,2020/10/9,第三章 命题逻辑,2020/10/9,3.1 本章学习要求,2

4、020/10/9,3.2.1 命题 定义3.2.1具有确切真值的陈述句称为命题, 该命题可以取一个“值”，称为真值。 真值只有“真”和“假”两种， 分别用“”(或“”)和“”(或“”)表示。,3.2 命题与命题联结词,2020/10/9,（1）太阳是圆的； （2）成都是一个旅游城市； （3）北京是中国的首都； （4）这个语句是假的； （5）1110； （6）+y； （7）我喜欢踢足球； （8）3能被2整除； （9）地球外的星球上也有人； （10）中国是世界上人口最多的国家； （11）今天是晴天；,例3.2.1,T,T,T/F,非命题,T/F,F,T/F,T,T/F,T,非命题,2020/10/

5、9,例3.2.1（续）,（12）把门关上； （13）滚出去！ （14）你要出去吗？ （15）今天天气真好啊！,非命题,非命题,非命题,非命题,注意： 一切没有判断内容的句子都不能作为命题，如命令句、感叹句、疑问句、祈使句、二义性的陈述句等。,2020/10/9,命题一定是陈述句，但并非一切陈述句都是命题。 命题的真值有时可明确给出，有时还需要依靠环境、条件、实际情况时间才能确定其真值。,结论：,在数理逻辑中像字母“x”、“y”、“z”等字母总是表示变量。,约定：,2020/10/9,下列语句是否是命题？并判断其真值结果？ （1）四川不是一个国家； （2）3既是素数又是奇数； （3）张谦是大学生

6、或是运动员； （4）如果周末天气晴朗，则我们将到郊外旅游； （5）2+2=4当且仅当雪是白的。,例3.2.2,T/F,T/F,T,T,T,2020/10/9,一般来说，命题可分两种类型： 原子命题(简单命题)：不能再分解为更为简单命题的命题。 复合命题：可以分解为更为简单命题的命题。而且这些简单命题之间是通过如“或者”、“并且”、“不”、“如果.则.”、“当且仅当”等这样的关联词和标点符号复合而构成一个复合命题。,命题的分类,2020/10/9,今天天气很冷。 今天天气很冷并且刮风。 今天天气很冷并且刮风，但室内暖和。,例3.2.3,通常用大写的带或不带下标的英文字母、.P、Q、R、. Ai、

7、Bi 、Ci、.Pi、Qi、Ri、.等表示命题,2020/10/9,3.2.2 命题联结词,设命题P,Q表示任意两个命题,则最常见的命题联结词有：,3.析取,P或者Q,P与Q的析取,PQ,PQ=1P=1或Q=1,2.合取,P并且Q,P与Q的合取,PQ,PQ=1P=1且Q=1,1.否定,非P,P的否定,P,P=1 P=0,4.蕴涵,若P,则Q,P蕴涵Q,PQ,PQ=0 P=1,Q=0,5.等价,P当且仅当Q,P等价于Q,PQ,PQ=1P=1,Q=1 或P=0,Q=0,例如：命题P：2是素数；Q：北京是中国的首都,1.否定联结词,设p为命题，则p的否定是一个复合命题，记作： p ，读作“非p”或“

8、p的否定”。定义为：若p真值为1，则 p为0；若p为0，则 p的真值为1。 联结词“”也可以看作逻辑运算，它是一元运算。 【例】否定下列命题。 p ：王强是一名大学生。 p ：王强不是一名大学生。,P:苏州处处清洁 P: 苏州不处处清洁 (注意,不是处处不清洁) S：苏州处处不清洁 (假设苏州有两个地方寒山寺 、沙家浜）,所以P一定不是S,Q:这些都是男同学,Q:这些不都是男同学,S：这些都不是男同学,S和Q、Q的关系？,2. 合取联结词,定义1.1.2设p和q均为命题，则p和q的合取是一个复合命题，记作pq ，读作“p与q”或“p合取q”。 定义为：当且仅当p和q均为1时，pq的真值才为1，

9、其他情况pq 的真值都为0。,p：2是素数。（真值？） q：2是偶数。（真值？） 则pq表示： 2是素数和偶数 由于p，q的真值均为1，所以pq的真值也为1。,合取的概念与自然语言中的“与”“和”“并且”的意义很相似，但是不完全相同 小王是大学生，小张是大学生。 两个命题的合取为小王和小张都是大学生 但是对于命题“小王与小张是好朋友”。这个就不是命题的合取，而是一个普通命题。,p：我去旅游 q：教室里面有电视 pq：我去旅游并且教室里面有电视 自然语言中，上述命题合取没有任何意义。 但是在数理逻辑中， pq仍然是一个命题。满足合取的真值定义,练习:将下列命题符号化,张三既用功又聪明 p：张三用

10、功 q：张三聪明 p q,张三不仅用功又聪明 p：张三用功 q：张三聪明 p q,张三虽然聪明，但不用功 p：张三用功 q：张三聪明 q p,张三与李四是同班同学 t：张三与李四是同班同学 简单陈述句，t是原子命题,3. 析取联结词,定义设p和q均为命题，则p和q的析取是一个复合命题，记作pq，读作“p或q”或者“p析取q”。定义为：当且仅当p和q真值均为0时， pq真值才为0。其他情况pq真值都为1 联结词“”也可以看成逻辑运算，它是二元逻辑运算,p：张山是大学生 q：张山是篮球运动员 pq的语义： 张山是大学生 或者张山是篮球运动员,“”与汉语中的“或”相似，但又不相同。 分析下列两个命题

11、中的“或”，有什么区别？ 今晚9点，中央一台播放“雍正王朝”或者转播足球比赛 (不可兼) 灯泡有故障或开关有故障。 (可兼, “”是可兼或) 汉语中的或有可兼或与不可兼或(排斥或)的区分。,今晚9点，中央一台播放“雍正王朝”或者转播足球比赛,p：今晚9点，中央一台播放“雍正王朝” q：今晚9点，中央一台转播足球比赛 (p q) ( p q) 此复合命题为真当且仅当p，q中一个为真一个为假,4. 排斥析取词,定义: 设定p，q，则“p排斥析取q”也是一种命题，记作p q。,5. 条件联结词,定义:设p和q均为命题，复合命题”如果p，则q”，称为p与q的蕴含式，记为：pq。读作“如果p，那么q”或

12、“若p，则q”。 p是蕴含式的前件，q为蕴含式的后件 真值定义为：当且仅当p为1，q为0时， pq才为0。 pq的逻辑关系为q是p的必要条件,使用，注意几点：,(1)q是p的必要条件有许多不同叙述方式： ”只要p就q”, ”因为p，所以q”, ”p仅当q”, ”只有q才p”, ”除非q才p”, ”除非q，否则非p”等等,(2)在自然语言中，如果p则q，前件p与后件q往往具有某种内在联系。但是在数理逻辑中，p与q可以无任何内在联系,(3)在数学或其他自然科学中，如果p则q，往往表达前件p为真，后见q也为真的推理关系。但是在数理逻辑中，作为一种规定，当p为假时，无论q是真是假， pq均为真。 自然

13、语言中，前件为假，结论不管真假，整个语句的意义往往无法确定。,例 p： 月亮下山 q： 3+3=6,则pq： 若月亮下山,则3+3=6 （并没有实质蕴含关系，仍承认）,qp： 叫做pq的逆命题,qp： 叫做pq的逆否命题,【例】 p：小王努力学习。q：小王学习成绩优秀。 pq表示？ 如果小王努力学习，那么他的学习成绩就优秀。,如果小明学日语，小华学英语，则小芳学德语。 p：小明学日语 q：小华学英语 x：小芳学德语. 则原式可表示为：(pq)x,5. 等价(双条件)联结词,定义：设p和q均为命题，其复合命题pq称为双条件命题，读作：“p双条件q”或者“p等价q”。定义为：当且仅当p和q的真值相

14、同时， pq真值为1。 联结词“”也可以理解成逻辑运算，它是二元逻辑运算 双条件联结词表示的是一个充分必要关系,【例】 设p：张华是三好学生。 q：张华德、智、体全优秀。 pq表示： 张华是三好学生当且仅当德、智、体全优秀,p：2+2=4 q：雪是白的 pq表示： 2+2=4当且仅当雪是白的,若两圆O1,O2的面积相等，则它们的半径相等，反之亦然。 p:两圆O1,O2的面积相等 q:两圆O1,O2的半径相等 pq,练习： 求下列复合命题的真值 (1) 2 + 2 4 当且仅当 3 + 3 6. (2) 2 + 2 4 当且仅当 3 是偶数. (3) 2 + 2 4 当且仅当 太阳从东方升起.

15、(4) 2 + 2 4 当且仅当 美国位于非洲.,1,0,1,0,符号化命题，并指出它们的真值,是有理数是不对的(p) 2是偶素数(p,q) 2或者4是素数(p,r) 如果2是素数，则3也是素数(p,s) 2是素数当且仅当3也是素数(p,s) p ：1 p q ：1 p r ：1 p s ：1 p s ：1,2020/10/9,总结,2020/10/9,说明,1、联结词是句子与句子之间的联结，而非单纯的名词、形容词、数词等地联结； 2、联结词是两个句子真值之间的联结，而非句子的具体含义的联结，两个句子之间可以无任何地内在联系；,2020/10/9,说明,3、联结词与自然语言之间的对应并非一一对

16、应；,2020/10/9,符号化下列命题 （1）四川不是人口最多的省份； （2）王超是一个德智体全面发展的好学生； （3）教室的灯不亮可能是灯管坏了或者是停电了； （4）如果周末天气晴朗，那么学院将组织我们到石像湖春游； （5）两个三角形全等当且仅当三角形的三条边全部相等。,例3.2.4,2020/10/9,例3.2.4 解,（1）设：四川是人口最多的省份。 则命题（1）可表示为。 （2）设：王超是一个思想品德好的学生； ：王超是一个学习成绩好的学生； R：王超是一个体育成绩好的学生。 则命题（2）可表示为R。 （3）设：教室的灯不亮可能是灯管坏了 ：教室的灯不亮可能是停电了 则命题（3）可表

17、示为。,2020/10/9,（4）设：周末天气晴朗； ：学院将组织我们到石像湖春游。 则命题（4）可表示为。 （5）设：两个三角形全等； ：三角形的三条边全部相等。 则命题（5）可表示为。,例3.2.4 解(续),2020/10/9,为了不使句子产生混淆，作如下约定，命题联结词之优先级如下：,否定合取析取蕴涵等价 同级的联结词，按其出现的先后次序(从左到右) 若运算要求与优先次序不一致时，可使用括号；同级符号相邻时，也可使用括号。括号中的运算为最优先级。,约 定,2020/10/9,设命题P：明天上午七点下雨；Q：明天上午七点下雪； R：我将去学校。 符号化下述语句： 如果明天上午七点不是雨夹

18、雪，则我将去学校 如果明天上午七点不下雨并且不下雪，则我将去学校 如果明天上午七点下雨或下雪，则我将不去学校 明天上午我将雨雪无阻一定去学校,可符号化为： (PQR)(PQR) (PQR)(PQR)。 或 (PQ)(PQ)(PQ) (PQ)R。,例3.2.5,可符号化为：(PQ)R。,可符号化为:(PQ)R。,可符号化为:(PQ)R。,2020/10/9,例3.2.6,设命题P：你陪伴我； Q：你代我叫车子； R：我将出去。 符号化下述语句： 除非你陪伴我或代我叫车子，否则我将不出去 如果你陪伴我并且代我叫辆车子，则我将出去 如果你不陪伴我或不代我叫辆车子，我将不出去,R(PQ) 或 (PQ)

19、R,(PQ)R,(PQ)R,2020/10/9,设P:雪是白色的;Q:2+2=4。将下列命题符号化： （1）因为雪是白色的，所以2+2=4； PQ （2）如果2+2=4，则雪是白色的； QP （3）只有雪是白色的，才有2+2=4； QP （4）只有2+2=4，雪才是白色的； PQ （5）只要雪不是白色的，就有2+2=4； PQ （6）除非雪是白色的，否则2+24； P Q或QP （7）雪是白色的当且仅当2+2=4； P Q,2020/10/9,3.2.4 命题联结词的应用,例 3.2.7 用复合命题表示如下图所示的开关电路：,图3.2.1 图3.2.2 图3.2.3,AB,AB,A,设：开关闭

20、合；：开关闭合。,2020/10/9,3.3 命题公式、解释与真值表,定义3.3.1 一个特定的命题是一个常值命题，它不是具有值“T”(“1”)，就是具有值“F”(“0”)。 而一个任意的没有赋予具体内容的原子命题是一个变量命题，常称它为命题变量(或命题变元)，该命题变量无具体的真值，它的变域是集合T，F(或0，1) 注意 (1)复合命题为命题变元的“函数”,其函数值仍为真或“假”值。 (2)真值函数或命题公式，没有确切真值。,真值函数,2020/10/9,3.3.1命题公式,定义3.3.2 (命题公式) 命题变元本身是一个公式； 如G是公式，则(G)也是公式； 如G，H是公式，则(GH)、(

21、GH)、(GH)、(GH)也是公式； 仅由有限步使用规则1-3后产生的结果。该公式常用符号G、H、等表示。,2020/10/9,符号串： (PQ)； (P(PQ) ) )； ( ( (PQ)(RQ) ) (PR) )。 都是命题公式。,例3.3.1,例3.3.2符号串： (PQ)Q)；(PQ； (PQ(R； PQ。 等都不是合法的命题公式。,2020/10/9,例3.3.3,试用符号形式写出下列命题： （1）虽然今天天气晴朗，老陈还是不来； （2）除非你陪伴我或代我叫车子，否则我将不出去； （3）停机的原因在于语法错误或者程序错误； （4）若a和b是偶数，则a+b是偶数； （5）我们要做到身体

22、好、学习好、工作好，为祖国四化建设而奋斗。,2020/10/9,例3.3.3试用符号形式写出下列命题,（1）虽然今天天气晴朗，老陈还是不来。P：今天天气晴朗,Q：老陈还是不来,则有： PQ； （2）除非你陪伴我或代我叫车子，否则我将不出去 P：你陪伴我； Q：你代我叫车子；R：我出去。则： RPQ或PQR； （3）停机的原因在于语法错误或者程序错误。P：停机的原因在于语法错误，Q：停机的原因在于程序错误，则有： P Q；,（4）若a和b是偶数，则a+b是偶数。P：a是偶数；Q：b是偶数，R：a+b是偶数，则有： PQR； （5）我们要做到身体好、学习好、工作好，为祖国四化建设而奋斗。P：我们要

23、做到身体好,Q：我们要做到学习好, R：我们要做到工作好，S：我们要为祖国四化建设而奋斗，则有： PQR S。,2020/10/9,公式(P(QR)(Q(SR)可表示如下：,(P(QR)(Q(SR),P(QR) Q(SR),P QR Q SR,Q R S R,S,例3.3.4,2020/10/9,3.3.2 公式的解释与真值表,定义3.3.3 设P1、P2、Pn是出现在公式G中的所有命题变元，指定P1、P2、Pn一组真值，则这组真值称为G的一个解释,常记为。 一般来说，若有个命题变元，则应有2n个不同的解释。 如果公式G在解释下是真的，则称满足G；如果G在解释下是假的，则称弄假G。 定义3.3

24、.4 将公式G在其所有可能解释下的真值情况列成的表，称为G的真值表。,2020/10/9,例3.3.5,求下面公式的真值表： (P(PQ)R)Q 其中，、是的所有命题变元。,2020/10/9,例3.3.5（续）,进一步化简为：,成真赋值， 成假赋值？,练习：,写出下列公式的真值表, 并求它们的成真赋值和成假赋值 (pq) r (qp) qp,(1) A = (pq) r,成真赋值:000,001,010,100,110; 成假赋值:011,101,111,(2) B(qp)qp,成真赋值:00,01,10,11; 无成假赋值,2020/10/9,例3.3.6,求下面这组公式的真值表： 1 (

25、)； 2()； 3 () (Q)。,2020/10/9,从这三个真值表可以看到一个非常有趣的事实：,公式G1对所有可能的解释具有“真”值 公式G3对所有可能的解释均具有“假”值 公式G2则具有“真”和“假”值,结论,2020/10/9,定义3.3.5,公式G称为永真公式(重言式)，如果在它的所有解释之下都为“真”。 公式G称为永假公式(矛盾式),如果在它的所有解释之下都为“假”。 公式G称为可满足的，如果它不是永假的。,2020/10/9,从上述定义可知三种特殊公式之间的关系：,永真式G的否定G是矛盾式；矛盾式G的否定G是永真式。 永真式一定是可满足式,可满足式不一定是永真式 可满足式的否定不

26、一定为不可满足式(即为矛盾式),结论,2020/10/9,例3.3.7,写出下列公式的真值表，并验证其公式是重言式、矛盾式、可满足公式。 （1）G1=()()； （2）G2=(Q)(Q)(Q)； （3）G3=(PQ)Q。,2020/10/9,例3.3.7 解,三个公式的真值表如下：,2020/10/9,若将其看成两个公式，分别令： ， 。 则是一个永真公式，即这两个公式对任何解释都必同为真假，此时，说和相等，记为。为此可定义：,分析公式（1）,定义3.3.6 设G、H是公式，如果在任意解释下，G与H的真值相同，则称公式G、H是等价的，记作GH。,() (),2020/10/9,公式G、H等价的

27、充分必要条件是公式GH是永真公式 证明:“”假定G，H等价，则G，H在其任意解释下或同为真或同为假，于是由“”的意义知，GH在其任何的解释下，其真值为“真”，即GH为永真公式。 “”假定公式GH是永真公式，是它的任意解释，在下，GH为真，因此，G、H或同为真，或同为假，由于的任意性，故有GH。,定理3.3.1,2020/10/9,首先，双条件词“”是一种逻辑联结词，公式GH是命题公式，其中“”是一种逻辑运算，GH的结果仍是一个命题公式。而逻辑等价“”则是描述了两个公式G与H之间的一种逻辑等价关系，GH表示“命题公式G等价于命题公式H”，GH 的结果不是命题公式。 其次，如果要求用计算机来判断命

28、题公式G、H是否逻辑等价，即GH那是办不到的，然而计算机却可“计算”公式GH是否是永真公式。,“” 与“”的区别,2020/10/9,“=”的性质,由于“=”不是一个联结词，而是一种关系，为此，这种关系具有如下三个性质： （1）自反性 G=G； （2）对称性 若G=H，则H=G； （3）传递性 若G=H，H=S，则G=S。 这三条性质体现了“=”的实质含义。,2020/10/9,3.3.4 命题公式的基本等价关系,例3.3.8 证明公式G1()与公式G2(PQ)(QP)之间是逻辑等价的。 解：根据定理3.3.1，只需判定公式 G3() (PQ)(QP)为永真公式。,2020/10/9,设G，H

29、，S是任何的公式，则：,基本等价公式,1) 1：GGG (幂等律) 2：GGG 2) 3：GHHG (交换律) 4：GHHG 3)*5：G(HS)(GH)S(结合律) 6: G(HS)(GH)S 4)*7：G(GH) G (吸收律) 8：G(GH) G,2020/10/9,5)*9：G(HS)(GH)(GS)(分配律） 10：G(HS)(GH)(GS) 6) 11：GG(同一律) 12：GG 7) 13：G(零律） 14：G 8) 15：GG1(排中律) 9) 16：GG0(矛盾律),基本等价公式（续）,2020/10/9,基本等价公式（续）,10) 17：(G)G (双重否定律) 11)*1

30、8：(GH)GH (De MoRGan定律) 19：(GH)GH。 12)*20: (GH)(GH)(HG)(等价) 13)*21：(GH)(GH) (蕴涵) 14) E22：G G。 (假言易位) 15) E23：G G。 (等价否定等式) 16) E24：(G ) (G)G (归谬论),补充*： A(AB)AB A(AB)AB,2020/10/9,这种图是将G，H理解为某总体论域上的子集合，而规定GH为两集合的公共部分（交集合），GH为两集合的全部（并集合），G为总体论域（如矩形域）中G的补集，将命题中的真值“1”理解为集合中的总体论域（全集），将命题中的真值“0”理解为集合中的空集，则有

31、：,命题与集合之间的关系,“” 对“”与“”对“”的对比,2020/10/9,设G(P1,P2,Pn)是一个命题公式，其中： P1、P2、Pn是命题变元，G1(P1,P2,Pn)、G2(P1,P2,Pn)、.、Gn(P1,P2,Pn)为任意的命题公式，分别用G1、G2、Gn取代G中的P1、P2、Pn后得到新的命题公式： G(G1,G2,Gn)G(P1,P2,Pn) 若G是永真公式（或永假公式），则G也是一个永真公式（或永假公式）。,定理3.3.2(代入定理),2020/10/9,例3.3.9,设(, )()，证明公式G是一个永真公式。另有两个任意公式： (, )()； (, )()。 进一步验

32、证代入定理的正确性。,解 建立公式G的真值表如右所示。可见为永真公式。,2020/10/9,例3.3.9（续）,将，代入到中分别取代G中的命题变元P、Q，所得到的公式为： (P, Q) = G(H, S) = (H(HS)S = ()()()() 建立新公式(P, Q)的真值表。,(, )() (, )()； (, )(),2020/10/9,定理3.3.3(替换定理),设G1是G的子公式(即 G1是公式G的一部分)，H1是任意的命题公式，在G中凡出现G1处都以H1替换后得到新的命题公式H，若G1H1，则GH。,利用24个基本等价公式及代入定理和替换定理，可完成公式的转化和等价判定。 有些教材

33、叫等值演算,利用等值演算证明p(qr) = (pq)r 证p(qr) = p(qr) （蕴涵等值式，置换规则） = (pq)r （结合律，置换规则） = (pq)r （德摩根律，置换规则） = (pq)r （蕴涵等值式，置换规则） 今后在注明中省去置换规则 注意：用等值演算不能直接证明两个公式不等值,2020/10/9,例3.3.10,利用基本的等价关系，完成如下工作： （1）判断公式的类型： 证明 () ()()()是一个永真公式。 （2）证明公式之间的等价关系： 证明() = () （3）化简公式： 证明(P(R)(R)(PR) = R,练习：用等值式判断公式类型(1),(pq) ( q

34、p) = (pq) (pq) （假言易位） =1 永真式,练习：用等值式判断公式类型(2),(pq) q = ( pq) q =p q q =0 永假式,练习：用等值式判断公式类型(3),(p q) q = (p q) q (得摩根律) = ( p q) q = q (吸收律) 可满足式,练习：用等值式判断公式类型(4),(pq)(qp) = (pq)(qp) （蕴涵等值式） = (pq)(pq) （交换律） = 1 重言式,2020/10/9,例3.3.12,将下面程序语言进行化简。 If A then if B then X else Y else if B then X else Y,解

35、：执行X的条件为： ()(),执行Y的条件为： ()(),3.3.6 命题公式的应用,2020/10/9,例3.3.12(续）,执行X的条件可化简为： ()() ( ) 执行Y的条件可化简为： ()() (),程序可简化为：If B then X else Y,2020/10/9,例3.3.14,一家航空公司，为了保证安全，用计算机复核飞行计划。每台计算机能给出飞行计划正确或有误的回答。由于计算机也有可能发生故障，因此采用三台计算机同时复核。由所给答案，再根据“少数服从多数”的原则作出判断，试将结果用命题公式表示，并加以简化，画出电路图。,2020/10/9,例3.3.14 解,设C1，C2，

36、C3分别表示三台计算机的答案。 S表示判断结果。,真值表,则根据真值表，利用联结词的定义，S可用C1，C2，C3所对应的命题公式表示出来，同时可画出该命题公式所对应的电路图。,2020/10/9,例3.3.14 解（续）,S= (C1C2C3)(C1C2C3) (C1C2C3)(C1C2C3) =(C1C1)C2C3)(C1(C2C2) C3)(C1C2(C3C3) =(C2C3)(C1C3)(C1C2),2020/10/9,3.5 公式的标准型范式,3.5.1 析取范式和合取范式 定义3.5.1 （1）命题变元或命题变元的否定称为文字 （2）有限个文字的析取称为析取式(也称为子句） （3）有

37、限个文字的合取称为合取式(也称为短语） （4）P与 P称为互补对。,2020/10/9,例子,（1）、是文字； （2）是子句； （3）是短语。,P是一个子句，这种说法正确么？,一个命题变元或者其否定既可以是简单的子句，也可以是简单的短语。,因此，不但是文字，也是子句、短语,2020/10/9,定义3.5.2,（1）有限个短语的析取式称为析取范式 （2）有限个子句的合取式称为合取范式,一个不含最外层括号的短语（子句）也可以是析取范式（合取范式）。,2020/10/9,例子,（1）、是析取范式、合取范式； （2）是子句、析取范式、合取范式， ( )仅是子句、合取范式； （3） 是短语、析取范式、合

38、取范式， ()仅是短语、析取范式； （4）()()是析取范式； （5）()()是合取范式； （6）句子()、()既不是析取范式也不是合取范式,2020/10/9,总结,（1）单个的文字是子句、短语、析取范式，合取范式 （2）单个的子句是析取范式； （3）单个的短语是合取范式； （4）若单个的子句（短语）无最外层括号，则是合取范式（析取范式）； （5）析取范式、合取范式仅含联结词集， （6） “”联结词仅出现在命题变元前。,2020/10/9,范式的求解方法,定理3.5.1 对于任意命题公式，都存在与其等价的析取范式和合取范式。,转换方法：,（1）利用等价公式中的等价式和蕴涵式将公式中的、用联结

39、词 、来取代，这可利用如下等价关系：,() = ()； () = ()() = ()()。,2020/10/9,范式的求解方法(续),（2）重复使用德摩根定律将否定号移到各个命题变元的前端，并消去多余的否定号，这可利用如下等价关系：() =； () = ； () = 。,（3）重复利用分配律，可将公式化成一些合取式的析取，或化成一些析取式的合取，这可利用如下等价关系：() = ()()； () = ()()。,2020/10/9,例3.5.1,求公式：()(R)的析取范式和合取范式,解 ()(R),= ()(R)(RP),= (R)( RP）,= ()(R) ()( RP),= (R)合取范式

40、 = R析取范式,2020/10/9,范式的不惟一性,考虑公式： ()()， 其与之等价的析取范式： ()； ()()； ()()； ()()。 这种不惟一的表达形式给研究问题带来了不便。,2020/10/9,3.5.2 主析取范式和主合取范式,1 极小项和极大项,定义 3.5.3 在含有n个命题变元P1、P2、P3、Pn的短语或子句中，若每个命题变元与其否定不同时存在，但二者之一恰好出现一次且仅一次，则称此短语或子句为关于P1、P2、P3、Pn的一个极小项或极大项。,对于n个命题变元，可构成2n个极小项和2n个极大项,2020/10/9,例子,（1）一个命题变元P， 对应的极小项有两项：P、

41、 P； 对应的极大项有两项：P、 P。 （2）两个命题变元P、Q， 对应的极小项有四项： PQ、 PQ、P Q、 P Q； 对应的极大项有四项： PQ、 PQ、P Q、 P Q。,2020/10/9,例子（续）,（3）三个命题变元P、Q、R， 对应的极小项有八项： 、 、 、； 对应的极大项有八项： 、 、 、。,2020/10/9,两个命题变元的所对应极小项真值表,注意：（1）没有等价的两个极小项； （2）使该极小项的真值为真的指派是唯一的,并且 使得其它极小项为假； （3）使极小项为真的那组指派为对应极小项的编码； （4）命题变元与1对应，命题变元的否定与0对应。,0、0为真 0 0 m0

42、0(m0) 0 1为真0 1 m01(m1) 1 0为真1 0 m10(m2) 1 1为真1 1 m11(m3),2020/10/9,两个命题变元的所对应极大项真值表,注意：（1）没有等价的两个极大项； （2）使该极大项的真值为假的指派是唯一的并且 使得其它极大项为真； （3）使极大项为假的那组指派为对应极大项的编码； （4）命题变元与0对应，命题变元的否定与1对应。,0、0为假 0 0 M00(M0) 0 1为假0 1 M01(M1) 1 0为假1 0 M10(M2) 1 1为假1 1 M11(M3),2020/10/9,三个命题变元的极小项和极大项,mimj=F,2020/10/9,极小项

43、和极大项的性质,任意两个极小项的合取必为假； 任意两个极大项的析取必为真； 极大项的否定是极小项； 极小项的否定是极大项； 所有极小项的析取为永真公式； 所有极大项的合取是永假公式。,Mi=mi,MiMj=T,Mi= mi,2020/10/9,2 主析取范式和主合取范式,定义3.5.4 （1）在给定的析取范式中，每一个短语都是极小项，则称该范式为主析取范式 （2）在给定的合取范式中，每一个子句都是极大项，则称该范式为主合取范式 （3）如果一个主析取范式不包含任何极小项，则称该主析取范式为“空”；如果一个主合取范式不包含任何极大项，则称主合取范式为“空”。,2020/10/9,定理3.5.2,任

44、何一个公式都有与之等价的主析取范式和主合取范式。,证明（1）利用定理3.5.1先求出该公式所对应的析取范式和合取范式；,（2）在析取范式的短语和合取范式的子句中重复出现的命题变元，将其化成只出现一次；,（3）去掉析取范式中的所有永假式（ PP ）， 去掉合取范式中所有永真式（ PP ）,2020/10/9,定理3.5.2 证明（续）,（4）若析取范式的某一个短语中缺少该命题公式中所规定的命题变元，则可用公式：()Q = Q将命题变元P补进去，并利用分配律展开，然后合并相同的短语，此时得到的短语将是标准的极小项 若合取范式的某一个子句中缺少该命题公式中所规定的命题变元，则可用公式：()Q = Q

45、 将命题变元P补进去，并利用分配律展开，然后合并相同的子句，此时得到的子句将是标准的极大项；,2020/10/9,证明（续）,（5）利用等幂律将相同的极小项和极大项合并，同时利用交换律进行顺序调整，由此可转换成标准的主析取范式和主合取范式。,2020/10/9,3 求主析取范式和主合取范式的方法,主范式,2020/10/9,例3.5.2,利用等价公式转换法求公式(PQ)(QR)的主析取范式和主合取范式 。,解 （1）求主析取范式 (PQ)(QR)= (PQ)(QR),=(PQ)(QR) 析取范式,= (PQ(RR)(PP)QR),= (PQR)(PQR)(PQR) (PQR) 主析取范式,20

46、20/10/9,例3.5.2（续）,（2）求主合取范式 (PQ)(QR)= (PQ)(QR) =(PQ)(PR)(QQ)(QR) = (PQ)(PR)(QR)合取范式,2020/10/9,例3.5.2（续）,=(PQ(RR)(P(QQ)R) (PP)QR) = (PQR)(PQR)(PQR) (PQR)(PQR) (PQR) = (PQR)(PQR) (PQR)(PQR) 主合取范式,2020/10/9,需要说明,求任何一个公式的主析取范式和主合取范式不仅要取决于该公式，而且取决于该公式所包含的命题变元。,如公式： G1 = (PQ)Q， G2(P, Q, R) = (PQ)Q。 前者是依赖于

47、两个命题变元的，后者应依赖于三个命题变元。,2020/10/9,如何用极小项来构成主析取范式？,m1必须包含在 主析取范式中,m0必须包含在 主析取范式中,m3必须包含在 主析取范式中,m2一定不能包含 在主析取范式中,主析取范式中必须且只能包含使得公式 真值为真的那些解释对应的极小项。,P-Q 与m0m1m3 一定等价,2020/10/9,如何用极大项来构成主合取范式？,M1必须包含在 主合取范式中,M2必须包含在 主合取范式中,M0一定不能包含 在主合取范式中,M3一定不能包含 在主合取范式中,主合取范式中必须且只能包含使得公式 真值为假的那些解释对应的极大项。,2020/10/9,真值表

48、技术,（1）列出公式对应的真值表，选出公式的真值结果为真的所有的行，在这样的每一行中，找到其每一个解释所对应的极小项，将这些极小项进行析取即可得到相应的主析取范式。,（2）列出公式对应的真值表，选出公式的真值结果为假的所有的行，在这样的每一行中，找到其每一个解释所对应的极大项，将这些极大项进行合取即可得到相应的主合取范式。,2020/10/9,例3.5.4,利用真值表技术求公式G = ()的主析取范式和主合取范式。,2020/10/9,例3.5.4（续）,（1）求主析取范式 找出真值表中其真值为真的行： 2. 0 0 1； 4. 0 1 1； 5. 1 0 0； 6. 1 0 1； 8. 1

49、1 1。 这些行所对应的极小项分别为： P， P，P， P，P。,2020/10/9,例3.5.4（续）,将这些极小项进行析取即为该公式G的主析取范式。 G = () = (P)(P) (P)(P)(P),2020/10/9,例3.5.4（续）,（2）求主合取范式 找出真值表中其真值为假的行： 10 0 0； 30 1 0； 71 1 0。 这些行所对应的极大项分别为： P、P 、 将这些极大项进行合取即为该公式G的主合取范式： G = () =(P)(P)(),2020/10/9,4 主析取范式和主合取范式之间的转换,（1）已知公式G的主析取范式，求公式G的主合取范式,（a）求G的主析取范式

50、，即G的主析取范式中没有出现过的极小项的析取，若,为的主析取范式。其中，mji(i=1,2,2n-k)是mi(i=0,2n-1)中去掉mli(i=,k)后剩下的极小项。,为的主析取范式，则,2020/10/9,主析取范式主合取范式,（b）G=(G)即是G的主合取范式。即，,为G 的主合取范式。,2020/10/9,主合取范式主析取范式,（1）已知公式G的主合取范式，求公式G的主析取范式,（a）求G的主合取范式，即G的主合取范式中没有出现过的极大项的合取，若,为的主合取范式。其中，Mji(i=1,2,2n-k)是Mi(i=0,2n-1)中去掉Mli(i=,k)后剩下的极大项。,为的主合取范式，则

51、,2020/10/9,主合取范式主析取范式,（2）已知公式G的主合取范式，求公式G的主析取范式 （a）求G的主合取范式，即G的主合取范式中没有出现过的极大项的合取，若 为的主合取范式，则 为的主合取范式。 其中，mji (i=1,2,2n-k)是Mi(i=0,2n-1)中去掉mli (i=,k)后剩下的极大项。,2020/10/9,主合取范式主析取范式,（b）G=(G)即是G的主析取范式。即，,为G 的主析取范式。,2020/10/9,例3.5.5,设=()()()，求其对应的主析取范式和主合取范式。,解 = ()()( ),=()() (),= ()()() ()()(),= ()()() ()()(),= m0m1m3m4m6m7 主析取范式,2020/10/9,例3.5.5（续）,= m2m5 = (m2m5) m2 m5= M2M5 =()() 主合取范式,补充：命题公式如何化为主析取范式 例1. 用真值表求出PQ的主析取范式 P Q PQ 0 0 1 0 1 1 1 0 0 1 1 1 所以PQ ( P Q) （ P Q ) （P Q） m0 m1 m3,补充： 例2 .用真值表求出PQ的主合取范式 P Q PQ 0 0 1 0 1 1 1 0 0 1