清华离散数学(第2版)：2.2-3.ppt

《清华离散数学(第2版)：2.2-3.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、2.2命题逻辑等值演算2.2.1等值式与等值演算等值式与基本等值式真值表法与等值演算法2.2.2联结词完备集真值函数联结词完备集与非联结词和或非联结词1等值式定义2.11若等价式AB是重言式,则称A与B等值,记作AB,并称AB是等值式说明:(1)是元语言符号,不要混同于和=(2)A与B等值当且仅当A与B在所有可能赋值下的真值都相同,即A与B有相同的真值表(3)n个命题变项的真值表共有个,故每个命题公式都有无穷多个等值的命题公式(4)可能有哑元出现.在B中出现,但不在A中出现的命题变项称作A的哑元.同样,在A中出现,但不在B中出现的命题变项称作B的哑元.哑元的值不影响命

2、题公式的真值.2真值表法例1判断(pq)与pq是否等值解结论:(pq)(pq)pqpqpq(pq)pq(pq)(pq)001101110110100110011001110010013真值表法(续)例2判断下述3个公式之间的等值关系:p(qr),(pq)r,(pq)r解pqrp(qr)(pq)r(pq)r000101001111010101011111100111101111110000111111p(qr)与(pq)r等值,但与(pq)r不等值4基本等值式双重否定律AA幂等律AAA

3、,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)A5基本等值式(续)零律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)A6等值演算等值演算:

4、由已知的等值式推演出新的等值式的过程置换规则:若AB,则(B)(A)例3证明p(qr)(pq)r证p(qr)p(qr)（蕴涵等值式）(pq)r（结合律）(pq)r（德摩根律）(pq)r（蕴涵等值式）7实例等值演算不能直接证明两个公式不等值.证明两个公式不等值的基本思想是找到一个赋值使一个成真,另一个成假.例4证明:p(qr)(pq)r方法一真值表法（见例2）方法二观察法.容易看出000使左边成真,使右边成假.方法三先用等值演算化简公式,再观察.8实例例5用等值演算法判断下列公式的类型(1)q(pq)解q(

5、pq)q(pq)（蕴涵等值式）q(pq)（德摩根律）p(qq)（交换律，结合律）p0（矛盾律）0（零律）该式为矛盾式.9实例(续)(2)(pq)(qp)解(pq)(qp)(pq)(qp)（蕴涵等值式）(pq)(pq)（交换律）1该式为重言式.10实例(续)(3)((pq)(pq))r)解((pq)(pq))r)(p(qq))r（分配律）p1r（排中律）pr（同一律）非重言式的可满足式.如101是它的成真赋值,000是它的成假赋值.总结:A为矛盾式当且仅当A0

6、;A为重言式当且仅当A1说明:演算步骤不惟一,应尽量使演算短些11真值函数定义2.12称F:{0,1}n{0,1}为n元真值函数n元真值函数共有个每一个命题公式对应于一个真值函数每一个真值函数对应无穷多个命题公式1元真值函数p0001110101122元真值函数pq0000000000010000111110001100111101010101pq001111111101000011111000110011110101010113联结词完备集定义2.13设S是一个联结词集合,如果任何n(n1)元真值函数都可以由仅含S中的联结词构成的公式表示,则称S是联结词完备集定理2.1

7、下述联结词集合都是完备集:(1)S1={,,,,}(2)S2={,,,}(3)S3={,,}(4)S4={,}(5)S5={,}(6)S6={,}AB(AB)(BA)ABABAB(AB)(AB)AB(AB)AB(A)BAB14复合联结词与非式:pq(pq),称作与非联结词或非式:pq(pq),称作或非联结词pq为真当且仅当p,q不同时为真pq为真当且仅当p,q不同时为