离散数学223命题逻辑等值演算课件.ppt

1、2.2 命题逻辑等值演算命题逻辑等值演算 2.2.1 等值式与等值演算等值式与等值演算 等值式与基本等值式等值式与基本等值式 真值表法与等值演算法真值表法与等值演算法 2.2.2 联结词完备集联结词完备集 真值函数真值函数 联结词完备集联结词完备集 与非联结词和或非联结词与非联结词和或非联结词等值式等值式定义定义2.11 若等价式若等价式AB是重言式是重言式,则称则称A与与B等值等值,记作记作AB,并称并称AB是是等值式等值式说明说明:(1)是是元语言符号元语言符号,不要混同于不要混同于和和=(2)A与与B等值当且仅当等值当且仅当A与与B在所有可能赋值下的真值都相在所有可能赋值下的真值都相同同

2、,即即A与与B有相同的真值表有相同的真值表(3)n个命题变项的真值表共有个命题变项的真值表共有 个个,故每个命题公式都有故每个命题公式都有无穷多个等值的命题公式无穷多个等值的命题公式(4)可能有哑元出现可能有哑元出现.在在B中出现中出现,但不在但不在A中出现的命题变中出现的命题变项称作项称作A的的哑元哑元.同样同样,在在A中出现中出现,但不在但不在B中出现的命题变中出现的命题变项称作项称作B的哑元的哑元.哑元的值不影响命题公式的真值哑元的值不影响命题公式的真值.n22真值表法真值表法例例1 判断判断 (p q)与与 p q 是否等值是否等值解解结论结论:(p q)(p q)p q p q p

3、q (p q)p q (p q)(p q)0 0 1 1 0 1 1 1 0 1 1 0 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 0 1 0 0 1真值表法真值表法(续续)例例2 判断下述判断下述3个公式之间的等值关系个公式之间的等值关系:p(qr),(pq)r,(p q)r解解 p q r p(qr)(pq)r (p q)r 0 0 0 1 0 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 p(qr)与与(p q)r等值等值,但与但与(pq)r不等

4、值不等值基本等值式基本等值式双重否定律双重否定律 AA幂等律幂等律 A 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)AB (A B)AB吸收律吸收律 A(A B)A,A(A B)A基本等值式基本等值式(续续)零律零律 A 11,A 00 同一律同一律 A 0A,A 1A排中律排中律 AA1矛盾律矛盾律 AA0蕴涵等值式蕴涵等值式 ABA B等价等值式等价等值式 AB(AB)(BA)假言易位假言易位 ABBA等价否定等值

5、式等价否定等值式 ABAB归谬论归谬论 (AB)(AB)A等值演算等值演算等值演算等值演算:由已知的等值式推演出新的等值式的过程由已知的等值式推演出新的等值式的过程置换规则置换规则:若若AB,则则(B)(A)例例3 证明证明 p(qr)(p q)r证证 p(qr)p(q r)（蕴涵等值式）蕴涵等值式）(pq)r （结合律）结合律）(p q)r （德摩根律）德摩根律）(p q)r （蕴涵等值式）蕴涵等值式）实例实例等值演算不能直接证明两个公式不等值等值演算不能直接证明两个公式不等值.证明两个公式不证明两个公式不等值的基本思想是找到一个赋值使一个成真等值的基本思想是找到一个赋值使一个成真,另一个成

6、假另一个成假.例例4 证明证明:p(qr)(pq)r方法一方法一 真值表法（见例真值表法（见例2）方法二方法二 观察法观察法.容易看出容易看出000使左边成真使左边成真,使右边成假使右边成假.方法三方法三 先用等值演算化简公式先用等值演算化简公式,再观察再观察.实例实例例例5 用等值演算法判断下列公式的类型用等值演算法判断下列公式的类型(1)q(pq)解解 q(pq)q(p q)（蕴涵等值式）蕴涵等值式）q(pq)（德摩根律）德摩根律）p(qq)（交换律，结合律）交换律，结合律）p 0 （矛盾律）矛盾律）0 （零律）（零律）该式为矛盾式该式为矛盾式.实例实例(续续)(2)(pq)(qp)解解

7、(pq)(qp)(p q)(qp)（蕴涵等值式）蕴涵等值式）(p q)(p q)（交换律）交换律）1该式为重言式该式为重言式.实例实例(续续)(3)(p q)(pq)r)解解 (p q)(pq)r)(p(qq)r （分配律）分配律）p 1 r （排中律）排中律）p r （同一律）同一律）非重言式的可满足式非重言式的可满足式.如如101是它的成真赋值是它的成真赋值,000是它的是它的成假赋值成假赋值.总结总结:A为矛盾式当且仅当为矛盾式当且仅当A0;A为重言式当且仅当为重言式当且仅当A1说明说明:演算步骤不惟一演算步骤不惟一,应尽量使演算短些应尽量使演算短些真值函数真值函数定义定义2.12 称称

8、F:0,1n0,1为为n元元真值函数真值函数n元真值函数共有元真值函数共有 个个每一个命题公式对应于一个真值函数每一个命题公式对应于一个真值函数每一个真值函数对应无穷多个命题公式每一个真值函数对应无穷多个命题公式n221元真值函数元真值函数 p 0 0 0 1 1 1 0 1 0 1)1(3)1(2)1(1)1(0FFFF2元真值函数元真值函数 p q 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1 p q 0 0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 1 1 1

9、1 1 0 0 0 1 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1)2(7)2(6)2(5)2(4)2(3)2(2)2(1)2(0FFFFFFFF)2(15)2(14)2(13)2(12)2(11)2(10)2(9)2(8FFFFFFFF联结词完备集联结词完备集定义定义2.13 设设S是一个联结词集合是一个联结词集合,如果任何如果任何n(n 1)元真值元真值函数都可以由仅含函数都可以由仅含S中的联结词构成的公式表示中的联结词构成的公式表示,则称则称S是是联结词完备集联结词完备集定理定理2.1 下述联结词集合都是完备集下述联结词集合都是完备集:(1)S1=,(2)S2=,(3)S

10、3=,(4)S4=,(5)S5=,(6)S6=,AB (AB)(BA)AB A BA B (A B)(AB)A B (AB)A B (A)B AB复合联结词复合联结词与非式与非式:p q(p q),称作称作与非联结词与非联结词或非式或非式:p q(p q),称作称作或非联结词或非联结词p q为真当且仅当为真当且仅当p,q不同时为真不同时为真p q为真当且仅当为真当且仅当p,q不同时为假不同时为假定理定理2.2 ,是联结词完备集是联结词完备集证证 p (p p)p p p q (p q)(p q)(p q)(p q)得证得证 是联结词完备集是联结词完备集.对于对于 可类似证明可类似证明.2.3

11、范式范式 2.3.1 析取范式与合取范式析取范式与合取范式 简单析取式与简单合取式简单析取式与简单合取式 析取范式与合取范式析取范式与合取范式 2.3.2 主析取范式与主合取范式主析取范式与主合取范式 极小项与极大项极小项与极大项 主析取范式与主合取范式主析取范式与主合取范式 主范式的用途主范式的用途简单析取式与简单合取式简单析取式与简单合取式文字文字:命题变项及其否定的统称命题变项及其否定的统称简单析取式简单析取式:有限个文字构成的析取式有限个文字构成的析取式如如 p,q,pq,p q r,简单合取式简单合取式:有限个文字构成的合取式有限个文字构成的合取式如如 p,q,pq,p q r,定理

12、定理2.3(1)一个简单析取式是重言式当且仅当它同时含一个简单析取式是重言式当且仅当它同时含某个命题变项和它的否定某个命题变项和它的否定(2)一个简单合取式是矛盾式当且仅当它同时含某个命题一个简单合取式是矛盾式当且仅当它同时含某个命题变项和它的否定变项和它的否定析取范式与合取范式析取范式与合取范式析取范式析取范式:由有限个简单合取式组成的析取式由有限个简单合取式组成的析取式 A1 A2Ar,其中其中A1,A2,Ar是是简单合取式简单合取式合取范式合取范式:由有限个简单析取式组成的合取式由有限个简单析取式组成的合取式 A1 A2Ar,其中其中A1,A2,Ar是是简单析取式简单析取式范式范式:析取

13、范式与合取范式的统称析取范式与合取范式的统称 定理定理2.4(1)一个析取范式是矛盾式当且仅当它的每一个一个析取范式是矛盾式当且仅当它的每一个简单合取式都是矛盾式简单合取式都是矛盾式(2)一个合取范式是重言式当且仅当它的每一个简单析取一个合取范式是重言式当且仅当它的每一个简单析取式都是重言式式都是重言式范式存在定理范式存在定理定理定理2.5 任何命题公式都存在着与之等值的析取范式与合任何命题公式都存在着与之等值的析取范式与合取范式取范式.证证 求公求公式式A的范式的步骤：的范式的步骤：(1)消去消去A中的中的,ABA B AB(A B)(AB)(2)否定联结词否定联结词 的内移或消去的内移或消

14、去 A A (A B)AB (A B)AB范式存在定理范式存在定理(续续)(3)使用分配律使用分配律 A(B C)(A B)(A C)求合取范式求合取范式 A(B C)(A B)(A C)求析取范式求析取范式例例1 1 求求(pq)r 的析取范式与合取范式的析取范式与合取范式解解 (pq)r (p q)r (pq)r 析取范式析取范式 (pr)(qr)合取范式合取范式注意注意:公式的析取范式与合取范式不惟一公式的析取范式与合取范式不惟一.极小项与极大项极小项与极大项定义定义2.17 在含有在含有n个命题变项的简单合取式个命题变项的简单合取式(简单析取式简单析取式)中中,若每个命题变项均以文字的

15、形式出现且仅出现一次，若每个命题变项均以文字的形式出现且仅出现一次，而且第而且第i(1 i n)个文字个文字(按下标或字母顺序排列按下标或字母顺序排列)出现在左出现在左起第起第i位上位上,称这样的简单合取式称这样的简单合取式(简单析取式简单析取式)为为极小项极小项(极大项极大项)说明说明:(1)n个命题变项产生个命题变项产生2n个极小项和个极小项和2n个极大项个极大项(2)2n个极小项个极小项(极大项极大项)均互不等值均互不等值(3)用用mi表示第表示第i个极小项个极小项,其中其中i是该极小项成真赋值的十是该极小项成真赋值的十进制表示进制表示.用用Mi表示第表示第i个极大项个极大项,其中其中i

16、是该极大项成假赋是该极大项成假赋值的十进制表示值的十进制表示,mi(Mi)称为极小项称为极小项(极大项极大项)的名称的名称.极小项与极大项极小项与极大项(续续)定理定理2.6 设设mi 与与Mi是由同一组命题变项形成的极小项和极是由同一组命题变项形成的极小项和极大项大项,则则 mi Mi,Mi mi 极小项极小项 极大项极大项 公式公式 成真赋值成真赋值 名称名称 公式公式 成假赋值成假赋值 名称名称 pq 0 0 m0 p q 0 0 M0 p q 0 1 m1 pq 0 1 M1 pq 1 0 m2 p q 1 0 M2 p q 1 1 m3 pq 1 1 M3 p,q形成的极小项与极大项

17、形成的极小项与极大项主析取范式与主合取范式主析取范式与主合取范式主析取范式主析取范式:由极小项构成的析取范式由极小项构成的析取范式主合取范式主合取范式:由极大项构成的合取范式由极大项构成的合取范式例如，例如，n=3,命题变项为命题变项为p,q,r时，时，(pq r)(p q r)m1 m3 是是主析取范式主析取范式 (p qr)(p qr)M1 M5 是是主合取范式主合取范式定理定理2.7 任何命题公式都存在着与之等值的主析取范式和任何命题公式都存在着与之等值的主析取范式和主合取范式主合取范式,并且是惟一的并且是惟一的.求主析取范式的步骤求主析取范式的步骤设公式设公式A含命题变项含命题变项p1

18、,p2,pn(1)求求A的析取范式的析取范式A=B1 B2 Bs,其中其中Bj是简单合取是简单合取式式 j=1,2,s (2)若某个若某个Bj既不含既不含pi,又不含又不含 pi,则将则将Bj展开成展开成 Bj Bj(pi pi)(Bj pi)(Bj pi)重复这个过程重复这个过程,直到所有简单合取式都是长度为直到所有简单合取式都是长度为n的极小的极小项为止项为止(3)消去重复出现的极小项消去重复出现的极小项,即用即用mi代替代替mi mi(4)将极小项按下标从小到大排列将极小项按下标从小到大排列求主合取范式的步骤求主合取范式的步骤设公式设公式A含命题变项含命题变项p1,p2,pn(1)求求A

19、的合取范式的合取范式A=B1 B2 Bs,其中其中Bj是简单析取是简单析取式式 j=1,2,s (2)若某个若某个Bj既不含既不含pi,又不含又不含 pi,则将则将Bj展开成展开成 Bj Bj(pi pi)(Bj pi)(Bj pi)重复这个过程重复这个过程,直到所有简单析取式都是长度为直到所有简单析取式都是长度为n的极大的极大项为止项为止(3)消去重复出现的极大项消去重复出现的极大项,即用即用Mi代替代替Mi Mi(4)将极大项按下标从小到大排列将极大项按下标从小到大排列实例实例例例1(1(续续)求求(pq)r 的主析取范式与主合取范式的主析取范式与主合取范式解解(1)(1)(pq)r (p

20、q)r pq (pq)1 同一律同一律 (pq)(r r)排中律排中律 (pqr)(pq r)分配律分配律 m4 m5 r (p p)(q q)r 同一律同一律,排中律排中律 (pqr)(p qr)(pqr)(p qr)m0 m2 m4 m6 分配律分配律得得 (pq)r m0 m2 m4 m5 m6可记作可记作 (0,2,4,5,6)实例实例(续续)(2)(pq)r (pr)(qr)pr p 0r 同一律同一律 p(qq)r 矛盾律矛盾律 (p qr)(pqr)分配律分配律 M1 M3 qr (pp)qr 同一律同一律,矛盾律矛盾律 (pqr)(pqr)分配律分配律 M3 M7得得 (pq)

21、r M1 M3 M7可记作可记作 (1,3,7)快速求法快速求法设公式含有设公式含有n个命题变项个命题变项,则则长度为长度为k的简单合取式可展开成的简单合取式可展开成2n-k个极小项的析取个极小项的析取例如例如 公式含公式含p,q,r q (p qr)(p q r)(p qr)(p q r)m2 m3 m6 m7长度为长度为k的简单析取式可展开成的简单析取式可展开成2n-k个极大项的合取个极大项的合取例如例如 pr (p qr)(pqr)M1 M3实例实例例例2(1)求求 A (p q)(pq r)r的主析取范式的主析取范式解解 用快速求法用快速求法(1)p q (p qr)(p q r)m2

22、 m3 pq r m1 r(pq r)(p q r)(pq r)(p q r)m1 m3 m5 m7得得 A m1 m2 m3 m5 m7 (1,2,3,5,7)实例实例(续续)(2)求求 B p(p qr)的主合取范式的主合取范式解解 p (p q r)(p qr)(pq r)(pqr)M4 M5 M6 M7 p qr M1得得 B M1 M4 M5 M6 M7 (1,4,5,6,7)主析取范式的用途主析取范式的用途(1)求公式的成真赋值和成假赋值求公式的成真赋值和成假赋值设公式设公式A含含n个命题变项个命题变项,A的主析取范式有的主析取范式有s个极小项个极小项,则则A有有s个成真赋值个成真

23、赋值,它们是极小项下标的二进制表示它们是极小项下标的二进制表示,其余其余2n-s个赋值都是成假赋值个赋值都是成假赋值 例如例如 (pq)r m0 m2 m4 m5 m6 成真赋值成真赋值:000,010,100,101,110;成假赋值成假赋值:001,011,111主析取范式的用途主析取范式的用途(续续)(2)判断公式的类型判断公式的类型 设设A含含n个命题变项，则个命题变项，则 A为重言式当且仅当为重言式当且仅当A的主析取范式含的主析取范式含2n个极小项个极小项A为矛盾式当且仅当为矛盾式当且仅当 A的主析取范式不含任何极小项的主析取范式不含任何极小项,记作记作0 A为可满足式当且仅当为可满

24、足式当且仅当A的主析取范式中至少含一个极小项的主析取范式中至少含一个极小项实例实例例例3 用主析取范式判断公式的类型用主析取范式判断公式的类型:(1)A (pq)q (2)B p(p q)(3)C(p q)r解解(1)A (p q)q (pq)q 0 矛盾式矛盾式(2)B p(p q)1 m0 m1 m2 m3 重言式重言式(3)C (p q)r (pq)r (pq r)(pqr)(pq r)(p q r)(pq r)(p q r)m0 m1 m3 m5 m7 非重言式的可满足式非重言式的可满足式主析取范式的用途主析取范式的用途(续续)(3)判断两个公式是否等值判断两个公式是否等值例例4 用主

25、析取范式判断下面用主析取范式判断下面2组公式是否等值组公式是否等值:(1)p与与(p q)(p q)解解 p p(q q)(pq)(p q)m2 m3 (p q)(p q)(p q)(p q)(pq)(p q)m2 m3故故 p (p q)(p q)实例实例(续续)(2)(p q)r 与与 p(q r)解解(p q)r (p qr)(p q r)(pq r)(p q r)(pq r)(p q r)m1 m3 m5 m6 m7 p(q r)(p q)(p r)(p qr)(p q r)(pq r)(p q r)m5 m6 m7故故 (p q)r p(q r)实例实例例例5 某单位要从某单位要从A

26、,B,C三人中选派若干人出国考察三人中选派若干人出国考察,需满需满足下述条件足下述条件:(1)若若A去去,则则C必须去必须去;(2)若若B去去,则则C不能去不能去;(3)A和和B必须去一人且只能去一人必须去一人且只能去一人.问有几种可能的选派方案问有几种可能的选派方案?解解 记记p:派派A去去,q:派派B去去,r:派派C去去(1)pr,(2)qr,(3)(pq)(p q)求下式的成真赋值求下式的成真赋值 A=(pr)(qr)(pq)(p q)实例实例(续续)求求A的主析取范式的主析取范式 A=(pr)(qr)(pq)(p q)(p r)(qr)(pq)(p q)(pq)(pr)(rq)(rr)

27、(pq)(p q)(pq)(pq)(pr)(pq)(rq)(pq)(pq)(p q)(pr)(p q)(rq)(p q)(pq r)(p qr)成真赋值成真赋值:101,010结论结论:方案方案1 派派A与与C去去,方案方案2 派派B去去主合取范式主合取范式由主析取范式求主合取范式由主析取范式求主合取范式设设没有出现的极小项是没有出现的极小项是siiimmmA21,21tjjjmmm其中其中t=2n-s,tjjjmmmA21tttjjjjjjjjjMMMmmmmmmA212121)(于是于是主合取范式主合取范式(续续)例例6 求求A=(pq r)(p q r)(p q r)的主合取范式的主合取范式解解 A m1 m3 m7 M0 M2 M4 M5 M6矛盾式的主合取范式含全部矛盾式的主合取范式含全部2n个极大项个极大项重言式的主合取范式不含任何极大项重言式的主合取范式不含任何极大项,记作记作1