离散数学命题逻辑.ppt

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,离散数学,第一部分,-,命题逻辑,1,课程性质,离散数学,（又称,计算机数学,）是现代数学的重要分支，是计算机专业核心基础课程之一。,2,课程目标,离散数学,是以研究离散量的,结构,和相互之间的,关系,为主要目标，其研究对象一般为：,有限或可数个,元素（例如：自然数、整数、真假值、有限个结点等），而,离散性,也是计算机科学的显著特点。,3,与其他课程的关系,离散数学,与计算机科学的其他课程,如：数据结构、操作系统、编译原理、算法分析、逻辑设计、系统结构、容错技术、人工智能等有密切的联系。它是这些课程的,先导和基础,课程。,4,离散数学,高等教育出版社,屈婉玲著,Discrete Mathematics and Its Applications 6th Edition,Kenneth H Rosen,教材与参考书,5,课程内容,本课程根据大纲的内容和相关独立性，,可分为,四大部分,第一部分,数理逻辑,包括命题逻辑,;,谓词逻辑,第二部分,集合论,包括集合与关系,;,函数,6,课程内容,第三部分,代数系统,包括代数结构,;,格,与,布尔代数,第四部分,图论,7,学习方法,课程特点：定义、定理多,本课内容,定义,定理,习题,为了学好这门课，要求：,（）弄懂定义、定理，弄懂例题，加深对定义、定理的理解；,（）在复习基础上，做好课外作业。同学之间可以讨论，但要弄懂弄通。,（,3,）做好课堂笔记。,（,4,）结合专业实践，做到融会贯通。,8,学习建议,平时考勤,20%,平时作业,20%,期末考试,60%,考核方式,课前预习,+,课上笔记,+,课下习题,+,经典文献阅读,9,第一篇 数理逻辑,数理逻辑是用,数学语言,表述的,推理形式有效性,的学问。,命题逻辑、谓词逻辑,数理逻辑使用特制的表意符号，亦称为,符号逻辑,。,逻辑研究对象,逻辑真值,真，表示为,T,或,1,假，表示为,F,或,0,正确的推理形式,正确前提,正确的推理形式,必然得出正确的结论,10,第一章 命题逻辑,1.1,命题与联接词,什么是命题？,命题的运算符是什么？,如何表示命题？,有多少种命题的运算符？,语句表达,陈述句,疑问句,祈使句,感叹句,雪是白的。,2,是奇数。,X+Y5,。,你是谁？,我正在说谎。,北京是中国的首都。,前进！,天空多漂亮,!,特点：有的语句可以判断真假。,自然语言、命题,语言是人们思维和交际的工具，也是一种表达观念的符号系统。,自然语言由各种句式组成，如陈述句、疑问句、感叹句、祈使句等等。,陈述句是陈述一个事实或者说话人的看法，它包括肯定句和否定句两种。一般来说，仅有陈述句能够确定句子的意义是真还是假。,命题表达为具有,确定真假意义,的,陈述句,。,命题示例,雪是白的。,2,是奇数。,X+Y5,。,你是谁？,我正在说谎。,北京是中国的首都。,每个不小于,6,的偶数都是两个奇素数之和（歌德巴赫猜想）,21,世纪有人住在月球上。,他很高。,一个自然数不是合数就是素数,命题，真,命题，假,不确定，非命题,疑问句，非命题,悖论，非命题,命题，真,命题，真，有唯一真假值。,命题，真，有唯一真假值。,无法确定，非命题,命题，假，,1,不是合数和素数,命题的抽象表示,自然语言具有,二义性 比如：郑州市长远规划,命题逻辑不关注语句的内容，也不关注语句为何是真或为假，而是仅仅关注语句能够为真或假。,命题的,抽象,用小写字母表示命题，取值为,0,1,。,命题,真值,陈述句的意义为真，称为,真命题,，真值为,1,或,T,。,陈述句的意义为假，称为,假命题,，真值为,0,或,F,。,命题逻辑的研究对象,命题。,数理逻辑从,形式结构,方面研究命题。,自然语言复杂语句构造,简单语句,+,联接词（连词、介词）,=,复杂语句,语句联接词,并且,或,否定,如果,则,。,当且仅当,既不,，也不,。,运算思维,简单命题与复合命题,简单命题,由简单陈述句表述的命题称为简单命题。,命题逻辑不再进一步分析简单命题的内部结构,p:,孔子是圣人,语句联接词,并且,或,否定,如果,则,。,当且仅当,既不,，也不,。,复合命题,用联接词可以将若干个简单句组合成复合句。,子命题,命题逻辑如何运算？,数计算启示,自然数,运算：,+,、*,整数,运算：,+,、,-,、*,有理数,运算：,+,、,-,、*、,/,命题逻辑,真,1,，假,0,运算：,？,逻辑联结词,定义,0,和,1,称为,0,元函数。设,n0,称为,0,1,n,到,0,1,的函数为,n,元函数，真值函数也称为,联结词,。,命题的操作符（联结词）,非,与,或,如果,则,。,当且仅当,异或,真值,表,真值形式可以用图表来说明。这种表称为,真值,图表。,0,元函数,0,，,1,1,元函数,2,元函数,、,、,、,逻辑联结词,命题,p,的否定记为,p,读作非,p,真值表,逻辑联接词,的含义,自然语言中，并非的含义,举例：,：每一种生物均是动物。,F,：,有一些,生物,不是,动物。,T,这里,不能讲成“每一种生物都不是动物”。,逻辑联结词,真值表,p,q,称为,p,和,q,的合取,读作,p,且,q,逻辑联接词,的含义,自然语言中，并且的含义,都真,(p:1),才真,(q:1),举例：,(1)p,：王华的成绩很好,q,：王华的品德很好。,则,pq,：王华的成绩很好并且品德很好。,(2)p,：我们去种树,q,：房间里有一台电视机,则,pq,：我们去种树与房间里有一台电视机。,(3)p,：今天下大雨,q,：,3+3=6,则,pq,：今天下大雨和,3+3=6,由例,(2)(3),可见，在日常生活中，合取词应用在二个有关系的命题之间。而在逻辑学中，合取词,可以用在二个毫不相干的命题之间。,逻辑联结词,22,逻辑联结词,真值表,p,q,称为,p,和,q,的析取，读作,p,或,q,逻辑联接词,的含义,自然语言中，或的含义,都假,(p:0),才假,(q:0),举例：今天晴天或者下雨,逻辑联结词,真值表,逻辑联接词,的含义,自然语言中，如果,则,.,的含义,真,(1),假,(0),才假,(0),p,q,称为,p,蕴涵,q,读作,p,则,q,p,称为前件,q,称为后件,举例：,(1)p,：我拿起一本书,q,：我一口气读完了这本书,pq,：如果我拿起一本书，则我一口气,读完了这本书。,(2)p,：,Alice,当选总统,q,：,Alice,减税,pq,：如果,Alice,当选总统，那么,Alice,将减税,(3)p,：今天打雷了,q,：,1+1=2,pq,：如果今天打雷，那么,1+1=2,逻辑联结词,25,逻辑联结词,真值表,p,q,称为,p,与,q,等值，读作,p,当且仅当,q,p,与,q,互蕴含。,p,q=(p,q),(q,p),逻辑联接词,的含义,自然语言中，当且仅当的含义,相同才,1,，不同则,0,逻辑联结词,举例,设,：,ABC,是等腰三角形,：,ABC,有两只角相等,：,ABC,是等腰三角形当且仅当,有两只角相等。,逻辑联结词,Alice,是男孩,或,女孩。（不可兼或）,比较,李明学习英语,或,学习法语。,(,可兼或,),真值表,p,q,称为,p,与,q,异或（不可兼或），读作,p,异或,q,。,p,q=(p,q),(q,p),不同才,1,，相同则,0,区分“可兼或”与“不可兼或”,“可兼或”即,p,或,q,为“,T”,时（,pq,）为“,T”,，是,析取,。,例如：,灯泡有故障或开关有故障。,今晚写字或看书。,今天下雨或打雷。,以上例句均为“可兼或”。,29,“,不可兼或”即,p,和,q,的真值不同时，,p,q,为,T,。,（异或用“,”表示）,不是析取,。,区分“可兼或”与“不可兼或”,例：,Alice,通过电视看杂技,或,到剧场看杂技。,Alice,乘火车去北京,或,乘飞机去北京。,以上两句均为“不可兼或”。,30,命题联结词在使用中的优先级,（）先括号内，后括号外,（）运算时联结词的优先次序为：,（由高到低）,（）联结词按从左到右的次序进行运算,（）最外层的括号一律均可省去,（,p,q,r,）可写成,p,q,r,31,命题联结词注意事项,（,1,）五个联结词的含义与日常生活中的联结词,的,含义大致相同,。,（,2,）“或”可分为可兼或（）和异或（,）,（不可兼或）,（,3,）“,”,为一元运算，其余四个均为二元运算。,（,4,）,“”,分为形式条件和实质条件命题，,当前件,为“”时，不论后件怎样，则单条件命,题的真值均为“”。,（,5,）命题联结词是,命题或命题之间,的联结词，而,不是名词之间、数字之间和动词之间的联,结词。,32,命题符号化,以上介绍了五种常用的联结词及其相应的复合命题形式。数理逻辑的特点是把,逻辑推理变成类似数学演算,的完全形式化了的逻辑演算，为此，首先要把推理所涉及到的各命题符号化。,步骤如下：,找出各,简单命题,，分别符号化。,找出各,联结词,，把简单命题逐个联结起来。,33,命题符号化,例,.,将下列命题符号化：,（,1,）李明是计算机系的学生，他住在,312,室或,313,室,（,2,）张三和李四是朋友。,（,3,）虽然交通堵塞，但是老王还是准时到达了车站。,（,4,）只有一个角是直角的三角形才是直角三角形。,（,5,）老王或小李中有一个去上海出差。,（,6,）除非今天下雨，否则我去踢球。,34,命题符号化,解：,（,1,）首先用字母表示简单命题。,p,：李明是计算机系的学生。,q,：李明住在,312,室。,r,：李明住在,313,室。,该命题符号化为：,p,（,q,r,）,（,2,）张三和李四是朋友。是一个简单句,该命题符号化为：,p,35,命题符号化,（,3,）首先用字母表示简单命题。,p,：交通堵塞。,q,：老王准时到达了车站。,该命题符号化为：,p,q,（,4,）首先用字母表示简单命题。,p,：三角形的一个角是直角。,q,：三角形是直角三角形。,该命题符号化为：,p q,36,命题符号化,（,5,）首先用字母表示简单命题。,p,：老王去上海出差。,q,：小李去上海出差。,该命题符号化为,p,q,也可符号化为：（,p,q,）（,pq,）或者,（,p,q,）（,pq,）,37,命题符号化,约定：,（）我们,只注意命题的真假值,，而不再去注意命题的汉语意义。,（）对命题联结词，我们,只注意真值表的定义,，而不注意它日常生活中的含义。,38,1.2,命题公式,命题公式,命题常元：,表示,确定的命题,T,，,F,。,命题变元：,以真假为其,变域,之变元，或,没有指定真值,的命题。常用大写英文字母,表示。,命题公式,：由命题变元、常元、联结词、括号，,以规定的格式联结起来的,字符串,。,39,命题公式构造法则,定义,命题公式,(wff),可按下述法则来生成：,）,单个的命题变元,是一个命题公式。,）若是命题公式，,也为命题公式。,）若、是命题公式，则（,）、,（）、（）、（）,均为命题公式。,）当且仅当有限次使用,（）（）（）,所得到的包含有命题变元和命题常元，联结词，括号的符号串才是命题公式。,40,命题公式的真值表,例如：,(,(PQ),，,(P(QR),，,(PQ),R),，,P,都是命题公式。而,(P),，,(P,),都不是命题公式,命题公式的真值表,:,命题变元用,特定的命题来取代,，这一过程称为对该命题变元进行,真值指派,。,命题公式可以看成是一个以真假值为定义域和真假值为值域的一个,函数,。写成,(x),41,命题公式的真值表,例如：公式,P,(Q R),定义三元函数,Y(P,，,Q,，,R),P,(Q R),定义,命题公式,A,在其所有可能的赋值下取得的值列成的表称为,A,的真值表,。,42,命题公式真值表构造方法,构造真值表的步骤如下：,1),找出给定命题公式中,所有的命题变元,，列,出所有可能的赋值。,2),按照从低到高顺序写出,命题公式的各层次,。,3),对应每个赋值，,计算命题公式各层次的值,，直到最后计算出整个命题公式的值。,43,命题公式真值表构造方法,例构造命题公式,（）,R,）的真值表,例,2,构造命题公式,P,(P,Q),的真值表,例,3,构造命题公式,(P,Q),Q,的真值表,个命题变元有组真值指派；个命题变元有,2,3,组真值指派，个则有个,2,n,个真值指派。,44,前者是依赖于两个命题变元的，后者应依赖于三个命题变元。,输出“No”,计算结束,今天下雨或打雷。,注意:推理正确不能保证结论一定正确,p,pq,pq,(pqp(pqr),If S2=then,该命题符号化为：p,得证为联结词完备集.,第一章 命题逻辑 1.,公式A的析取(合取)范式与A等值的析取(合取)范式,Res(qr,qr)=q,(pqr)(pqr)(pqr),第二部分 集合论,（3）“”为一元运算，其余四个均为二元运算。,逻辑联结词,命题公式的永真式、永假式和可满足式,定义,设公式中有,n,个不同的原子变元,p,1,p,n,(n,为正整数,),。该变元组的任意一组确定的值（,u,1,u,n,）称为关于,p,1,p,n,的一个,完全指派,，其中,u,i,或为，或为。如果对于中部分变元赋以确定值，其余变元没有赋以确定的值，则这样的一组值称为公式的关于该变元组的,部分指派,。,定义,使公式取真的指派称为,成真指派,。,45,命题公式的永真式、永假式和可满足式,定义,如果一个命题公式的所有完全指派均为成真指派，则该公式称为,永真式,。如果一个命题公式的所有完全指派均为成假指派，则该公式称为,永假式,。不是永假式的公式，则称此命题公式是,可满足式,。,讨论：,（）永真式的否定为永假式（,）；永假式的否定为永真式（,）。,（）二个永真式的析取、合取、蕴含、等价,均为永真式。,46,第二章 命题逻辑等值演算,2.1,等值式,有哪些基本的等值式？,如何进行等值演算？,析取范式与合取范式，主析取范式与主合取范式的求解,什么是联结词完备集？,2.1,等值式,定义,2.1,若等价式,A,B,是重言式，则称,A,与,B,等值,，记作,A,B,，并称,A,B,是,等值式,几点说明：,定义中，,A,B,均为元语言符号,A,或,B,中可能有哑元出现,.,例如,(,p,q,),(,p,q,),(,r,r,),r,为左边公式的哑元,.,用真值表可检查两个公式是否等值,请验证：,p,(,q,r,),(,p,q,),r,p,(,q,r,),不与,(,p,q,),r,等值,48,等值式例题,例,1,判断下列各组公式是否等值,:,(1),p,(,q,r,),与,(,p,q,),r,1,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,0 0 0,0 0 1,0 1 0,0 1 1,1 0 0,1 0 1,1 1 0,1 1 1,(,p,q,),r,p,(,q,r,),q,r,p q r,p,q,0,0,0,0,0,0,1,1,结论,:,p,(,q,r,),(,p,q,),r,49,等值式例题,(2),p,(,q,r,),与,(,p,q,),r,0,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,0 0 0,0 0 1,0 1 0,0 1 1,1 0 0,1 0 1,1 1 0,1 1 1,(,p,q,),r,p,(,q,r,),q,r,p q r,p,q,1,1,1,1,0,0,1,1,结论,:,p,(,q,r,),与,(,p,q,),r,不等值,50,基本等值式,双重否定律,A,A,幂等律,A,A,A,A,A,A,交换律,A,B,B,A,A,B,B,A,结合律,(,A,B,),C,A,(,B,C,),(,A,B,),C,A,(,B,C,),分配律,A,(,B,C,),(,A,B,),(,A,C,),A,(,B,C,),(,A,B,),(,A,C,),德摩根律,(,A,B,),A,B,(,A,B,),A,B,吸收律,A,(,A,B,),A,A,(,A,B,),A,51,基本等值式,零律,A,1,1,A,0,0,同一律,A,0,A,.,A,1,A,排中律,A,A,1,矛盾律,A,A,0,蕴涵等值式,A,B,A,B,等价等值式,A,B,(,A,B,),(,B,A,),假言易位,A,B,B,A,等价否定等值式,A,B,A,B,归谬论,(,A,B,),(,A,B,),A,特别提示：必须牢记这,16,组等值式，这是继续学习的基础,52,等值演算与置换规则,1.,等值演算,由已知的等值式推演出新的等值式的过程,2.,等值演算的基础：,(1),等值关系的性质：自反性、对称性、传递性,(2),基本的等值式,(3),置换规则（见,3,）,3.,置换规则,设,(,A,),是含公式,A,的命题公式，,(,B,),是用公式,B,置换,(,A,),中所有的,A,后得到的命题公式,若,B,A,，则,(,B,),(,A,),53,等值演算的应用举例,证明两个公式等值,例,2,证明,p,(,q,r,),(,p,q,),r,证,p,(,q,r,),p,(,q,r,),（蕴涵等值式，置换规则）,(,p,q,),r,（结合律，置换规则）,(,p,q,),r,（德摩根律，置换规则）,(,p,q,),r,（蕴涵等值式，置换规则）,今后在注明中省去置换规则,注意：用等值演算不能直接证明两个公式不等值,54,证明两个公式不等值,例,3,证明,p,(,q,r,),与,(,p,q,),r,不等值,等值演算的应用举例,证 方法一,:,真值表法,见例,1(2),方法二,:,观察法,.,观察到,000,010,是左边的成真赋值，是右边的成假赋值,方法三,:,先用等值演算化简公式，然后再观察,p,(q,r),pq,r,(p,q),r,(pq)r,(pq),r,更容易看出前面的两个赋值分别是,左边的成真赋,值和右边的成假赋值,55,判断公式类型,:,A,为,矛盾式,当且仅当,A,0,A,为,重言式,当且仅当,A,1,例,4,用等值演算法判断下列公式的类型,(1),q,(,p,q,),(2)(,p,q,),(,q,p,),(3)(,p,q,),(,p,q,),r,),等值演算的应用举例,解,(1),q,(,p,q,),q,(,p,q,),（蕴涵等值式）,q,(,p,q,),（德摩根律）,p,(,q,q,),（交换律，结合律）,p,0,（矛盾律）,0,（零律）,矛盾式,56,判断公式类型,(2)(p,q),(,q,p),(,p,q),(q,p),（蕴涵等值式）,(,p,q),(,p,q),（交换律）,1,重言式,(3)(p,q),(p,q),r),(p,(q,q),r,（分配律）,p,1,r,（排中律）,p,r,（同一律）,可满足式,，,101,和,111,是成真赋值，,000,和,010,等是成假赋值,.,57,2.2,析取范式与合取范式,基本概念,(1),文字,命题变项及其否定的总称,(2),简单析取式,有限个文字构成的析取式,p,q,p,q,p,q,r,(3),简单合取式,有限个文字构成的合取式,p,q,p,q,p,q,r,(4),析取范式,由有限个简单合取式组成的析取式,p,p,q,p,q,(,p,q,),(,p,q,r,)(,q,r,),(5),合取范式,由有限个简单析取式组成的合取式,p,p,q,p,q,(,p,q,p,(,p,q,r,),(6),范式,析取范式与合取范式的总称,58,范式的性质,定理,2.1,(1),一个简单析取式是重言式当且仅当它,同时含有某,个命题变项和它的否定式,.,(2),一个简单合取式是矛盾式当且仅当它,同时含有某,个命题变项和它的否定式,.,定理,2.2,(1),一个析取范式是矛盾式当且仅当它,每个简单合,取式都是矛盾式,.,(2),一个合取范式是重言式当且仅当它的,每个简单析,取式都是重言式,.,59,命题公式的范式,定理,2.3,（范式存在定理）,任何命题公式,都存在与之等值的,析取范式与合取范式,公式,A,的析取,(,合取,),范式,与,A,等值的,析取,(,合取,),范式,求,公式,A,的范式的步骤,：,(1),消去,A,中的,（若存在）,A,B,A,B,A,B,(,A,B,),(,A,B,),(2),否定联结词,的,内移或消去,A,A,(,A,B,),A,B,(,A,B,),A,B,60,命题公式的范式,(3),使用,分配律,A,(,B,C,),(,A,B,),(,A,C,),求合取范式,A,(,B,C,),(,A,B,),(,A,C,),求析取范式,公式范式的不足,不惟一,61,求公式的范式,例,5,求下列公式的析取范式与合取范式,(1)(,p,q,),r,(2)(,p,q,),r,解,(1)(,p,q,),r,(,p,q,),r,（消去,）,p,q,r,（结合律）,(2)(,p,q,),r,(,p,q,),r,（消去第一个,）,(,p,q,),r,（消去第二个,）,(,p,q,),r,（否定号内移,德摩根律,),析取范式,(,p,r,),(,q,r,),（,对,分配律）合取范式,62,极小项与极大项,63,实例,由,两个命题变项,p,q,形成的极小项与极大项,极小项,极大项,公式,成真赋值,名称,公式,成假赋值,名称,p,q,p,q,p,q,p,q,0 0,0 1,1 0,1 1,m,0,m,1,m,2,m,3,p,q,p,q,p,q,p,q,0 0,0 1,1 0,1 1,M,0,M,1,M,2,M,3,64,实例,极小项,极大项,公式,成真赋值,名称,公式,成假赋值,名称,p,q,r,p,q,r,p,q,r,p,q,r,p,q,r,p,q,r,p,q,r,p,q,r,0 0 0,0 0 1,0 1 0,0 1 1,1 0 0,1 0 1,1 1 0,1 1 1,m,0,m,1,m,2,m,3,m,4,m,5,m,6,m,7,p,q,r,p,q,r,p,q,r,p,q,r,p,q,r,p,q,r,p,q,r,p,q,r,0 0 0,0 0 1,0 1 0,0 1 1,1 0 0,1 0 1,1 1 0,1 1 1,M,0,M,1,M,2,M,3,M,4,M,5,M,6,M,7,由,三个命题变项,p,q,r,形成的极小项与极大项,.,m,i,与,M,i,的关系：,m,i,M,i,M,i,m,i,65,主析取范式与主合取范式,主析取范式,由极小项构成的析取范式,主合取范式,由极大项构成的合取范式,例如，,n,=3,命题变项为,p,q,r,时，,(,p,q,r,),(,p,q,r,),m,1,m,3,主析取范式,(,p,q,r,),(,p,q,r,),M,1,M,7,主合取范式,定理,2.5,(,主范式的存在惟一定理,),任何命题公式,都存在与之等值的,主析取范式和主合取范式,并且是,惟一,的,66,需要说明,求任何一个公式的主析取范式和主合取范式不仅要取决于,该公式,，而且取决于该公式所包含的,命题变元,。,如公式：,G,1,(P,Q)=(PQ)Q,，,G,2,(P,Q,R)=(PQ)Q,。,前者是依赖于两个命题变元的，后者应依赖于三个命题变元。,求主析取范式和主合取范式的方法,等值推演法,利用基本等价公式进行变换,主范式,真值表技术,对公式的真值结果进行分解，分解成等价的极小项的析取或者极大项的合取,求公式,A,的主析取范式的方法与步骤,方法一、等值演算法,(1)化归为,析取范式,。,(2),除去,析取范式中所有永假的析取项。,(3)将析取式中重复出现的合取项和相同的变元,合并,。,(4)对合取项,补入没有出现的命题变元,，即添加如(,pp),式，然后应用,分配律展开,公式。,方法二、真值表法,(1)写出,A,的真值表,。,(2)找出,A,的成真赋值,。,(3)求出,每个成真赋值对应的极小项,（用名称表示），按角标,从小到大顺序析取,。,(1)等值推演法求主析取范式,(,pq),r,(,pqr),(pr),(qr),pqr,m,4,pr,p（qq）r,(,pqr)(pqr),m,1,m,3,qr,(pp)qr,(,pqr)(pqr),m,3,m,7,(,pq),r,m1m3m4m7,实例,实例,p,q,r,p,q,(,p,q,),r,0,0,0,1,0,0,0,1,1,1,0,1,0,1,0,0,1,1,1,1,1,0,0,0,1,1,0,1,0,0,1,1,0,1,0,1,1,1,1,1,(2),真值表法求,(pq),r,的,主析取范式。,解 首先列出其真值表,71,实例,将公式的真值进行分解，,分解成一些子公式,，该子公式,仅有一组解释使其真值为真,，此时的每一个子公式都对应了一个极小项。,p,q,r,(,p,q,),r,p,q,r,p,q,r,p,q,r,p,q,r,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,1,0,0,0,0,0,0,0,1,1,1,0,1,0,0,1,0,0,1,0,0,1,0,1,0,1,0,0,0,0,0,1,1,0,0,0,0,0,0,1,1,1,1,0,0,0,1,将,极小项全部进行析取,后，可得到相应的主析取范式：,(pq),r=(pqr)(pqr)(pqr)(pqr,),72,求公式,A,的主合取范式的方法与步骤,方法一、等值演算法,(1)化归为,合取范式,。,(2),除去,合取范式中所有永真的合取项。,(3)将合取式中重复出现的析取项和相同的变元,合并,。,(4)对析取项,补入,没有出现的命题变元，即添加如(,pp),式，然后应用,分配律展开,公式。,方法二、真值表法,(1)写出,A,的真值表,。,(2)找出,A,的成假赋值,。,(3)求出,每个成假赋值对应的极大项,（用名称表示），按角标,从小到大顺序合取,。,(1)等值推演法求主合取范式,(,pq),r,(pr),(qr),(pqr),pqr,M,5,pr,p(qq)r,(,pqr)(pqr),M,0,M,2,qr,(pp)qr,(,pqr)(pqr),M,2,M,6,(,pq),r,M0M2M5M6,实例,实例,p,q,r,p,q,(,p,q,),r,0,0,0,1,0,0,0,1,1,1,0,1,0,1,0,0,1,1,1,1,1,0,0,0,1,1,0,1,0,0,1,1,0,1,0,1,1,1,1,1,(2),真值表法求,(pq),r,的,主合取范式。,解 首先列出其真值表,75,实例,将公式的真值进行分解，,分解成一些子公式,，该,子公式仅有一组解释使其真值为假,，此时的每一个子公式都对应了一个极大项,将,极大项全部进行析取,后，可得到相应的主合取范式：,(,P,Q,),R,=(,P,Q,R,)(,P,Q,R,)(,P,Q,R,)(,P,Q,R,),p,q,r,(,p,q,),r,p,q,r,p,q,r,p,q,r,p,q,r,0,0,0,0,0,1,1,1,0,0,1,1,1,1,1,1,0,1,0,0,1,0,1,1,0,1,1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,0,1,0,1,1,0,1,1,1,0,0,1,1,1,0,1,1,1,1,1,1,1,1,76,真值表技术,利用真值表技术求主析取范式和主合取范式的简要方法：,从真值表知，,选出,公式的真值结果为,真,的所有的行，在这样的每一行中，,找到其每一个成真解释所对应的极小项,，,将这些极小项的析取,即可得到相应的主析取范式。,从真值表知，,选出,公式的真值结果为,假,的所有的行，在这样的每一行中，,找到其每一个成假解释所对应的极大项,，,将这些极大项的合取,即可得到相应的主合取范式。,从真值表按所给的算法求出主范式的方法，称为,真值表技术,（,Technique of Truth Table,）。,77,Try 1 Try,设,G,=,(,p,q,),r,，求出它的主析取范式和主合取范式。（分别用等值推演和真值表法）,78,主范式的应用,1.,求公式的成真成假赋,值,设公式,A,含,n,个命题变项,A,的主析取范式有,s,个极小项,则,A,有,s,个成真赋值,它们是极小项下标的二进制表示,其余,2,n,-,s,个赋值都是,成假赋值,例如,(,p,q,),r,m,1,m,3,m,5,m,6,m,7,成真赋值为,001,011,101,110,111,，,成假赋值为,000,010,100.,类似地，由主合取范式也立即求出成假赋值和成真赋值,.,79,2.,判断公式的类型,设,A,含,n,个命题变项,.,A,为重言式,A,的主析取范式含全部,2,n,个极小项,A,的主合取范式不含任何极大项,记为,1.,A,为矛盾式,A,的主合析取范式含全部,2,n,个极大项,A,的主析取范式不含任何极小项,记为,0.,A,为非重言式的,可满足式,A,的主析取范式中,至少含一个,、,但不是全,部,极小项,A,的主合取范式中,至少含一个,、,但不是全,部,极大项,.,主范式的应用,80,把扩张到l(和lc)上:,p(qq)（交换律，结合律）,课程特点：定义、定理多,个命题变项和它的否定式.,10 设S是一个合取范式,C1,C2,Cn是一个简单析取式,（1）首先用字母表示简单命题。,）当且仅当有限次使用（）（）（）所得到的包含有命题变元和命题常元，联结词，括号的符号串才是命题公式。,（1）李明是计算机系的学生，他住在312室或 313室,从真值表知，选出公式的真值结果为假的所有的行，在这样的每一行中，找到其每一个成假解释所对应的极大项，将这些极大项的合取即可得到相应的主合取范式。,pq 置换,p q r,解 S=p(pq)(pq)(qr)(qr),rs 前提引入,q：李明住在312室。,(3)置换规则（见3）,例,7,用主析取范式判断公式的类型,:,(1),A,(,p,q,),q,(2),B,p,(,p,q,)(3),C,(,p,q,),r,解,(1),A,(,p,q,),q,(,p,q,),q,0,矛盾式,(2),B,p,(,p,q,)1,m,0,m,1,m,2,m,3,重言式,(3),C,(,p,q,),r,(,p,q,),r,(,p,q,r,)(,p,q,r,)(,p,q,r,),(,p,q,r,)(,p,q,r,)(,p,q,r,),m,0,m,1,m,3,m,5,m,7,非重言式的可满足式,主范式的应用,81,3.,判断两个公式是否等值,例,8,用主析取范式判以下每一组公式是否等值,p,(,q,r,),与,(,p,q,),r,p,(,q,r,),与,(,p,q,),r,解,p,(,q,r,)=,m,0,m,1,m,2,m,3,m,4,m,5,m,7,(,p,q,),r,=,m,0,m,1,m,2,m,3,m,4,m,5,m,7,(,p,q,),r,=,m,1,m,3,m,4,m,5,m,7,显见，中的两公式等值，而的不等值,.,主范式的应用,82,4.,解实际问题,例,9,某单位要从,A,B,C,三人中选派若干人出国考察,需满足下述条件,:,(1),若,A,去,则,C,必须去,;,(2),若,B,去,则,C,不能去,;,(3)A,和,B,必须去一人且只能去一人,.,问有几种可能的选派方案,?,解 记,p,:,派,A,去,q,:,派,B,去,r,:,派,C,去,(1),p,r,(2),q,r,(3)(,p,q,),(,p,q,),求下式的成真赋值,A,=(,p,r,),(,q,r,),(,p,q,),(,p,q,),主范式的应用,83,求,A,的主析取范式,A,=(,p,r,),(,q,r,),(,p,q,),(,p,q,),(,p,r,),(,q,r,),(,p,q,),(,p,q,),(,(,p,q,),(,p,r,),(,r,q,),(,r,r,),(,p,q,),(,p,q,),(,(,p,q,),(,p,q,),(,(,p,r,),(,p,q,),(,(,r,q,),(,p,q,),(,(,p,q,),(,p,q,),(,(,p,r,),(,p,q,),(,(,r,q,),(,p,q,),(,p,q,r,),(,p,q,r,),成真赋值,:101,010,结论,:,方案,1,派,A,与,C,去,方案,2,派,B,去,主范式的应用,84,2.3,联结词的完备集,定义,2.6,称,F,:0,1,n,0,1,为,n,元真值函数,.,0,1,n,=000,001,111,，包含 个长为,n,的,0,1,符号串,.,共有 个,n,元真值函数,.,1,元真值函数,p,0 0 0 1 1,1 0 1 0 1,85,真值函数,p q,0 0,0 1,1 0,1 1,0 0 0 0 0 0 0 0,0 0 0 0 1 1 1 1,0 0 1 1 0 0 1 1,0 1 0 1 0 1 0 1,p q,0 0,0 1,1 0,1 1,1 1 1 1 1 1 1 1,0 0 0 0 1 1 1 1,0 0 1 1 0 0 1 1,0 1 0 1 0 1 0 1,2,元真值函数,86,公式与真值函数,任何一个含,n,个命题变项的命题公式,A,都对应,惟一的一个,n,元,真值函数,F,F,恰好为,A,的真值表,.,等值的公式对应的真值函数相同,.,例如：,p,q,p,q,都对应,87,联结词完备集,定义,2.7,设,S,是一个联结词集合，如果,任何,n,(,n,1),元真值函数都可以由仅含,S,中的联结词构成的公式表示,，则称,S,是,联结词完备集,若,S,是联结词完备集,则任何命题公式都可由,S,中的联结词表示,定理,2.6,S,=,是联结词完备集,证明 由范式存在定理可证,88,联结词完备集,推论,以下都是联结词完备集,(1),S,1,=,(2),S,2,=,(3),S,3,=,(4),S,4,=,(5),S,5,=,证明,(1),(2),在联结词完备集中,加入新的联结词后仍为完备集,(3),A,B,(,A,B,),(4),A,B,(,A,B,),(5),A,B,A,B,不是联结词完备集,0,不能用它表示,它的子集,等都不是,89,证明 由范式存在定理可证,(2)真值表法求(pq)r的主析取范式。,q：房间里有一台电视机,例2构造命题公式P (PQ)的真值表,（）运算时联结词的优先次序为：,矛盾律 AA0,由简单陈述句表述的命题称为简单命题。,r：是无理数，s：4是素数,1 0 1 0 1,第三部分 代数系统,：每一种生物均是动物。,证:记C=Res(C1,C2)=C1C2,其中l和lc为消解文字,C1=lC1,C2=lcC2,且C1和C2不含l和lc.,异或 ,真值函数 F,F 恰好为A的真值表.,p q称为p与q等值，读作p当且仅当q,p与q互蕴含。,复合联结词,定义,2.8,设,p,q,为两个命题,(,p,q,),称作,p,与,q,的,与非式,记作,p,q,即,p,q,(,p,q,),称为,与非联结词,(p,q),称作,p,与,q,的,或非式,记作,p,q,即,p,q,(p,q),称为,或非联结词,定理,2.7,与,为联结词完备集,.,证明,为完备集,p,p,p,(,p,p,),p,p,p,q,(,p,q,),p,q,(,p,p,),(,q,q,),p,q,(,p,q,),(,p,q,),(,p,q,),(,p,q,),得证,为联结词完备集,.,对,类似可证,90,2.4,可满足性问题与消解法,不含任何文字的简单析取式称作,空简单析取式,记作,。规定是不可满足的,.,约定,:,简单析取式不同时含某个命题变项和它的否定,S,:,合取范式,C,:,简单析取式,l,:,文字,:,赋值,带下角标或,文字,l,的补,l,c,:,若,l=p,则,l,c,=,p,;,若,l,=,p,则,l,c,=,p,.,S,S,:,S,是可满足的当且仅当,S,是可满足的,定义,2.9,设,C,1,=,