《命题逻辑等值演算10225.ppt》由会员分享，可在线阅读，更多相关《命题逻辑等值演算10225.ppt（20页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1.3命题逻辑等值演算命题逻辑等值演算 p,q是是命命题题变变项项，pq 与与 p q在在4个个赋赋值值00、01、10、11下下均均有有相相同同的的真真值值，即即（pq）（p q）的的取取值值都都为为1（重言式，永真式）。（重言式，永真式）。给给定定n个个命命题题变变项项，按按合合式式公公式式的的规规则则可可以以形形成成无无数数个个命命题题公式。公式。n个个命命题题变变项项共共2n个个赋赋值值，每每个个赋赋值值时时命命题题公公式式的的值值为为0或或1，因因此此n个个命命题题变变项项共共生生成成22n个个真真值值不不同同的的命命题题公公式式。如如n=2，共共16个真值不同的命题公式。个真值不同
2、的命题公式。如何判断那些命题公式具有相同的真值？如何判断那些命题公式具有相同的真值？1等值式等值式 定义定义若等价式若等价式AB是重言式，则称是重言式，则称A与与B等值等值，记作记作AB，并称并称AB是是等值式等值式说明：定义中，说明：定义中，A,B,均为元语言符号均为元语言符号,A或或B中中可能有哑元出现可能有哑元出现.例如，在例如，在(pq)(p q)(r r)中，中，r为左边为左边公式的哑元公式的哑元.用真值表可验证两个公式是否等值用真值表可验证两个公式是否等值请验证：请验证：p(qr)(p q)r p(qr)(pq)r2基本等值式基本等值式 双重否定律双重否定律:AA等幂律等幂律：A
3、AA,A AA交换律交换律:A BB A,A BB A结合律结合律:(A B)CA(B C)(A B)CA(B C)分配律分配律:A(B C)(A B)(A C)A(B C)(A B)(A C)注意：注意：A,B,C代表任意的命题公式代表任意的命题公式3基本等值式基本等值式(续续)德德摩根律摩根律 :(A B)AB(A B)AB吸收律吸收律:A(A B)A,A(A B)A零律零律:A 11,A 00同一律同一律:A 0A,A 1A排中律排中律:AA1矛盾律矛盾律:AA0注意：注意：A,B,C代表任意的命题公式代表任意的命题公式4基本等值式基本等值式(续续)蕴涵等值式蕴涵等值式:ABA B等价等
4、值式等价等值式:AB(AB)(BA)假言易位假言易位:ABBA等价否定等值式等价否定等值式:ABAB归谬论归谬论:(AB)(AB)A注意注意:A,B,C代表任意的命题公式代表任意的命题公式牢记这些等值式是继续学习的基础牢记这些等值式是继续学习的基础5等值演算与置换规则等值演算与置换规则 等值演算等值演算:由已知的等值式推演出新的等值式的过程由已知的等值式推演出新的等值式的过程置换规则置换规则：若：若AB,则则(B)(A)等值演算的基础：等值演算的基础：(1)等值关系的性质：自反、对称、传递等值关系的性质：自反、对称、传递(2)基本的等值式基本的等值式(3)置换规则置换规则6应用举例应用举例证明
5、两个公式等值证明两个公式等值 例例1证明证明p(qr)(p q)r证证p(qr)p(q r)（蕴涵等值式，置换规则）蕴涵等值式，置换规则）(pq)r（结合律，置换规则）结合律，置换规则）(p q)r（德摩根律，置换规则）德摩根律，置换规则）(p q)r（蕴涵等值式，置换规则）蕴涵等值式，置换规则）说明说明:也可以从右边开始演算（请做一遍）也可以从右边开始演算（请做一遍）因为每一步都用置换规则，故可不写出因为每一步都用置换规则，故可不写出 熟练后，基本等值式也可以不写出熟练后，基本等值式也可以不写出 7应用举例应用举例证明两个公式不等值证明两个公式不等值例例2证明证明:p(qr)(pq)r用等值
6、演算不能直接证明两个公式不等值用等值演算不能直接证明两个公式不等值,证明两证明两个公式不等值的基本思想是找到一个赋值使一个成个公式不等值的基本思想是找到一个赋值使一个成真真,另一个成假另一个成假.方法一方法一真值表法（自己证）真值表法（自己证）方法二方法二观察赋值法观察赋值法.容易看出容易看出000,010等是左边的等是左边的成真赋值，是右边的成假赋值成真赋值，是右边的成假赋值.方法三方法三用等值演算先化简两个公式，再观察用等值演算先化简两个公式，再观察.8应用举例应用举例判断公式类型判断公式类型 例例3 3用等值演算法判断下列公式的类型用等值演算法判断下列公式的类型(1)q(pq)解解 q(
7、pq)q(p q)（蕴涵等值式）蕴涵等值式）q(pq)（德摩根律）德摩根律）p(qq)（交换律，结合律）交换律，结合律）p 0（矛盾律）矛盾律）0（零律）（零律）由最后一步可知，该式为矛盾式由最后一步可知，该式为矛盾式.9例例3(续续)(2)(pq)(qp)解解(pq)(qp)(p q)(qp)（蕴涵等值式）蕴涵等值式）(p q)(p q)（交换律）交换律）1由最后一步可知，该式为重言式由最后一步可知，该式为重言式.问：最后一步为什么等值于问：最后一步为什么等值于1？10例例3(续续)(3)(p q)(pq)r)解解(p q)(pq)r)(p(qq)r（分配律）分配律）p 1 r（排中律）排中
8、律）p r（同一律）同一律）这不是矛盾式，也不是重言式，而是非重言式的可这不是矛盾式，也不是重言式，而是非重言式的可满足式满足式.如如101是它的成真赋值是它的成真赋值,000是它的成假赋值是它的成假赋值.总结：总结：A为矛盾式当且仅当为矛盾式当且仅当A0 A为重言式当且仅当为重言式当且仅当A1说明：演算步骤不惟一说明：演算步骤不惟一,应尽量使演算短些应尽量使演算短些111.4联结词全功能集联结词全功能集 复合联结词复合联结词 排斥或排斥或 与非式与非式 或非式或非式真值函数真值函数联结词全功能集联结词全功能集12复合联结词复合联结词 排斥或（异或）排斥或（异或）:“p、q之中恰好有一个成立之
9、中恰好有一个成立”p q(pq)(p q)与非式与非式:“p与与q的否定的否定”p q(p q)或非式或非式:“p或或q的否定的否定”p q(p q)问题：多少个联结词最合适？问题：多少个联结词最合适？13真值函数真值函数 问题：含问题：含n个命题变项的所有公式共产生多少个互个命题变项的所有公式共产生多少个互不相同的真值表？不相同的真值表？答案为答案为 个，为什么？个，为什么？定义定义称定义域为称定义域为000,001,111，值域，值域为为0,1的函数是的函数是n元真值函数元真值函数，定义域中的元素是，定义域中的元素是长为长为n的的0,1串串.常用常用F:0,1n0,1表示表示F是是n元真值
10、元真值函数函数.共有共有 个个n元真值函数元真值函数.例如例如 F:0,120,1，且且F(00)=F(01)=F(11)=0，F(10)=1，则则F为一个确定的为一个确定的2元真值函数元真值函数.14命题公式与真值函数命题公式与真值函数对于任何一个含对于任何一个含n个命题变项的命题公式个命题变项的命题公式A，都存在都存在惟一的一个惟一的一个n元真值函数元真值函数F为为A的真值表的真值表.等值的公式对应的真值函数相同等值的公式对应的真值函数相同.下表给出所有下表给出所有2元真值函数对应的真值表元真值函数对应的真值表,每一个含每一个含2 2个命题变项的公式的真值表都可以在下表中找到个命题变项的公
11、式的真值表都可以在下表中找到.例如：例如：pq,p q,(p q)(pq)q)等等都对应都对应表中的表中的152元真值函数对应的真值表元真值函数对应的真值表p q0001101100000000000011110011001101010101 p q0001101111111111000011110011001101010101 16联结词的全功能集联结词的全功能集 定义定义在一个联结词的集合中，如果一个联结词可在一个联结词的集合中，如果一个联结词可由集合中的其他联结词定义，则称此联结词为由集合中的其他联结词定义，则称此联结词为冗余冗余的联结词的联结词，否则称为，否则称为独立的联结词独立的联结
12、词.例如例如,在联结词集在联结词集,中，由于中，由于pqp q,所以，所以，为冗余的联结词为冗余的联结词;类似地，类似地，也是冗余的也是冗余的联结词联结词.又在又在,中，由于中，由于p q(pq)所以，所以，是冗余的联结词，但是冗余的联结词，但,无冗余的联结词无冗余的联结词.类似地，类似地，也是冗余的联结词，也是冗余的联结词，但但,无冗余的联结词无冗余的联结词.17联结词的全功能集联结词的全功能集(续续)定义定义设设S是一个联结词集合，如果任何是一个联结词集合，如果任何n(n 1)元元真值函数都可以由仅含真值函数都可以由仅含S中的联结词构成的公式表中的联结词构成的公式表示，则称示，则称S是是联
13、结词全功能集联结词全功能集.如果如果联结词全功能集联结词全功能集不含冗余的联结词，则称为不含冗余的联结词，则称为极小功能集极小功能集.说明：说明：若若S是联结词全功能集，则任何命题公式都可用是联结词全功能集，则任何命题公式都可用S中的联结词表示中的联结词表示.若若S1,S2是两个联结词集合，且是两个联结词集合，且S1 S2.若若S1是全是全功能集，则功能集，则S2也是全功能集也是全功能集.18联结词的全功能集实例联结词的全功能集实例(1)S1=,(2)S2=,(3)S3=,(4)S4=,(5)S5=,(6)S6=(7)S7=而而,等则不是联结词全功能集等则不是联结词全功能集.19例例如已知如已知,是全功能集，证明是全功能集，证明,也是全功能集也是全功能集证：证：因为因为,是全功能集，任意一个真值函数可以用是全功能集，任意一个真值函数可以用,联结词的命题公式表示。联结词的命题公式表示。对对于于任任意意的的命命题题公公式式，AB A B,因因此此任任意意一一个个真真值函数可以用值函数可以用,联结词的命题公式表示。联结词的命题公式表示。例例 p(p p)p p p(p p)p p p (p)(p p)(p p)(p p)p (p)(p p)(p p)(p p)20