《离散数学-22-3命题逻辑等值演算.ppt》由会员分享，可在线阅读，更多相关《离散数学-22-3命题逻辑等值演算.ppt（39页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、2.2命题逻辑等值演算命题逻辑等值演算2.2.1等值式与等值演算等值式与等值演算等值式与基本等值式等值式与基本等值式真值表法与等值演算法真值表法与等值演算法2.2.2联结词完备集联结词完备集真值函数真值函数联结词完备集联结词完备集与非联结词和或非联结词与非联结词和或非联结词1等值式等值式定义定义2.11若等价式若等价式AB是重言式是重言式,则称则称A与与B等值等值,记作记作AB,并称并称AB是是等值式等值式说明说明:(1)是是元语言符号元语言符号,不要混同于不要混同于和和=(2)A与与B等值当且仅当等值当且仅当A与与B在所有可能赋值下的真值都在所有可能赋值下的真值都相相同同,即即A与与B有相同
2、的真值表有相同的真值表(3)n个命题变项的真值表共有个命题变项的真值表共有个个,故每个命题公式都有故每个命题公式都有无穷多个等值的命题公式无穷多个等值的命题公式(4)可能有哑元出现可能有哑元出现.在在B中出现中出现,但不在但不在A中出现的命题中出现的命题变项称作变项称作A的的哑元哑元.同样同样,在在A中出现中出现,但不在但不在B中出现的命中出现的命题变项称作题变项称作B的哑元的哑元.哑元的值不影响命题公式的真值哑元的值不影响命题公式的真值.2真值表法真值表法例例1判断判断(p q)与与 p q是否等值是否等值解解结论结论:(p q)(p q)p q p q p q (p q)p q (p q)
3、(p q)001101110110100110011001110010013真值表法真值表法(续续)例例2判断下述判断下述3个公式之间的等值关系个公式之间的等值关系:p(qr),(pq)r,(p q)r解解p q r p(qr)(pq)r (p q)r000101001111010101011111100111101111110000111111p(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)分配律
4、分配律 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)A5基本等值式基本等值式(续续)零律零律 A 11,A 00同一律同一律 A 0A,A 1A排中律排中律 AA1矛盾律矛盾律 AA0蕴涵等值式蕴涵等值式 ABA B等价等值式等价等值式 AB(AB)(BA)假言易位假言易位ABBA等价否定等值式等价否定等值式ABAB归谬论归谬论(AB)(AB)A6等值演算等值演算等值演算等值演算:由已知的等值式推演出新的等值式的过程由已知的等值式推演出新的等值式的过程置换规则置换规则:若若AB,则则(B
5、)(A)例例3证明证明p(qr)(p q)r证证p(qr)p(q r)（蕴涵等值式）蕴涵等值式）(pq)r（结合律）结合律）(p q)r（德摩根律）德摩根律）(p q)r（蕴涵等值式）蕴涵等值式）7实例实例等值演算不能直接证明两个公式不等值等值演算不能直接证明两个公式不等值.证明两个公式不证明两个公式不等值的基本思想是找到一个赋值使一个成真等值的基本思想是找到一个赋值使一个成真,另一个成假另一个成假.例例4证明证明:p(qr)(pq)r方法一方法一真值表法（见例真值表法（见例2）方法二方法二观察法观察法.容易看出容易看出000使左边成真使左边成真,使右边成假使右边成假.方法三方法三先用等值演算
6、化简公式先用等值演算化简公式,再观察再观察.8实例实例例例5用等值演算法判断下列公式的类型用等值演算法判断下列公式的类型(1)q(pq)解解 q(pq)q(p q)（蕴涵等值式）蕴涵等值式）q(pq)（德摩根律）德摩根律）p(qq)（交换律，结合律）交换律，结合律）p 0（矛盾律）矛盾律）0（零律）（零律）该式为矛盾式该式为矛盾式.9实例实例(续续)(2)(pq)(qp)解解(pq)(qp)(p q)(qp)（蕴涵等值式）蕴涵等值式）(p q)(p q)（交换律）交换律）1该式为重言式该式为重言式.10实例实例(续续)(3)(p q)(pq)r)解解(p q)(pq)r)(p(qq)r（分配律
7、）分配律）p 1 r（排中律）排中律）p r（同一律）同一律）非重言式的可满足式非重言式的可满足式.如如101是它的成真赋值是它的成真赋值,000是它的是它的成假赋值成假赋值.总结总结:A为矛盾式当且仅当为矛盾式当且仅当A0;A为重言式当且仅当为重言式当且仅当A1说明说明:演算步骤不惟一演算步骤不惟一,应尽量使演算短些应尽量使演算短些11真值函数真值函数称称F:0,1n0,1为为n元元真值函数真值函数n元真值函数共有元真值函数共有 个个每一个命题公式对应于一个真值函数每一个命题公式对应于一个真值函数每一个真值函数对应无穷多个命题公式每一个真值函数对应无穷多个命题公式1元真值函数元真值函数p00
8、01110101122元真值函数元真值函数p q 0000000000010000111110001100111101010101 p q 001111111101000011111000110011110101010113联结词完备集联结词完备集定义定义设设S是一个联结词集合是一个联结词集合,如果任何如果任何n(n 1)元真值元真值函数都可以由仅含函数都可以由仅含S中的联结词构成的公式表示中的联结词构成的公式表示,则称则称S是是联结词完备集联结词完备集下述联结词集合都是完备集下述联结词集合都是完备集:(1)S1=,(2)S2=,(3)S3=,(4)S4=,(5)S5=,(6)S6=,AB(A
9、B)(BA)AB A BA B (A B)(AB)A B (AB)A B (A)B AB14复合联结词复合联结词与非式与非式:p q(p q),称作称作与非联结词与非联结词或非式或非式:p q(p q),称作称作或非联结词或非联结词p q为真当且仅当为真当且仅当p,q不同时为真不同时为真p q为真当且仅当为真当且仅当p,q不同时为假不同时为假,是联结词完备集是联结词完备集证证 p (p p)p p p q (p q)(p q)(p q)(p q)得证得证 是联结词完备集是联结词完备集.对于对于 可类似证明可类似证明.152.3范式范式2.3.1析取范式与合取范式析取范式与合取范式简单析取式与简
10、单合取式简单析取式与简单合取式析取范式与合取范式析取范式与合取范式2.3.2主析取范式与主合取范式主析取范式与主合取范式极小项与极大项极小项与极大项主析取范式与主合取范式主析取范式与主合取范式主范式的用途主范式的用途16简单析取式与简单合取式简单析取式与简单合取式文字文字:命题变项及其否定的统称命题变项及其否定的统称简单析取式简单析取式:有限个文字构成的析取式有限个文字构成的析取式如如p,q,pq,p q r,简单合取式简单合取式:有限个文字构成的合取式有限个文字构成的合取式如如p,q,pq,p q r,(1)一个简单析取式是重言式当且仅当它同时含一个简单析取式是重言式当且仅当它同时含某个命题
11、变项和它的否定某个命题变项和它的否定(2)一个简单合取式是矛盾式当且仅当它同时含某个命题一个简单合取式是矛盾式当且仅当它同时含某个命题变项和它的否定变项和它的否定17析取范式与合取范式析取范式与合取范式析取范式析取范式:由有限个简单合取式组成的析取式由有限个简单合取式组成的析取式A1 A2Ar,其中其中A1,A2,Ar是是简单合取式简单合取式合取范式合取范式:由有限个简单析取式组成的合取式由有限个简单析取式组成的合取式A1 A2Ar,其中其中A1,A2,Ar是是简单析取式简单析取式范式范式:析取范式与合取范式的统称析取范式与合取范式的统称(1)一个析取范式是矛盾式当且仅当它的每一个一个析取范式
12、是矛盾式当且仅当它的每一个简单合取式都是矛盾式简单合取式都是矛盾式(2)一个合取范式是重言式当且仅当它的每一个简单析取一个合取范式是重言式当且仅当它的每一个简单析取式都是重言式式都是重言式18范式存在定理范式存在定理定理定理任何命题公式都存在着与之等值的析取范式与合任何命题公式都存在着与之等值的析取范式与合取范式取范式.证证 求公求公式式A的范式的步骤：的范式的步骤：(1)消去消去A中的中的,ABA B AB(A B)(AB)(2)否定联结词否定联结词 的内移或消去的内移或消去 AA(A B)AB(A B)AB19范式存在定理范式存在定理(续续)(3)使用分配律使用分配律 A(B C)(A B
13、)(A C)求合取范式求合取范式A(B C)(A B)(A C)求析取范式求析取范式例例1 1求求(pq)r 的析取范式与合取范式的析取范式与合取范式解解 (pq)r(p q)r(pq)r析取范式析取范式(pr)(qr)合取范式合取范式注意注意:公式的析取范式与合取范式不惟一公式的析取范式与合取范式不惟一.20极小项与极大项极小项与极大项定义定义在含有在含有n个命题变项的简单合取式个命题变项的简单合取式(简单析取式简单析取式)中中,若每个命题变项均以文字的形式出现且仅出现一次，若每个命题变项均以文字的形式出现且仅出现一次，而而且且第第i(1 i n)个个文文字字(按按下下标标或或字字母母顺顺序
14、序排排列列)出出现现在在左左起第起第i位上位上,称这样的简单合取式称这样的简单合取式(简单析取式简单析取式)为为极小项极小项(极大项极大项)说明说明:(1)n个命题变项产生个命题变项产生2n个极小项和个极小项和2n个极大项个极大项(2)2n个极小项个极小项(极大项极大项)均互不等值均互不等值(3)用用mi表示第表示第i个极小项个极小项,其中其中i是该极小项成真赋值的是该极小项成真赋值的十十进制表示进制表示.用用Mi表示第表示第i个极大项个极大项,其中其中i是该极大项成假赋是该极大项成假赋值的十进制表示值的十进制表示,mi(Mi)称为极小项称为极小项(极大项极大项)的名称的名称.21极小项与极大
15、项极小项与极大项(续续)设设mi 与与Mi是由同一组命题变项形成的极小项和极是由同一组命题变项形成的极小项和极大项大项,则则 mi Mi,Mi mi极小项极小项极大项极大项公式公式成真赋值成真赋值名称名称公式公式成假赋值成假赋值名称名称 pq 00m0p q 00M0 p q 01m1pq 01 M1 pq 10m2 p q 10M2p q 11m3 pq 11M3 p,q形成的极小项与极大项形成的极小项与极大项22主析取范式与主合取范式主析取范式与主合取范式主析取范式主析取范式:由极小项构成的析取范式由极小项构成的析取范式主合取范式主合取范式:由极大项构成的合取范式由极大项构成的合取范式例如
16、，例如，n=3,命题变项为命题变项为p,q,r时，时，(pq r)(p q r)m1 m3是是主析取范式主析取范式(p qr)(p qr)M1 M5是是主合取范式主合取范式定理定理2.7任何命题公式都存在着与之等值的主析取范式和任何命题公式都存在着与之等值的主析取范式和主合取范式主合取范式,并且是惟一的并且是惟一的.23求主析取范式的步骤求主析取范式的步骤设公式设公式A含命题变项含命题变项p1,p2,pn(1)求求A的析取范式的析取范式A=B1 B2 Bs,其中其中Bj是简单合是简单合取取式式j=1,2,s(2)若某个若某个Bj既不含既不含pi,又不含又不含 pi,则将则将Bj展开成展开成 B
17、jBj(pi pi)(Bj pi)(Bj pi)重复这个过程重复这个过程,直到所有简单合取式都是长度为直到所有简单合取式都是长度为n的极小的极小项为止项为止(3)消去重复出现的极小项消去重复出现的极小项,即用即用mi代替代替mi mi(4)将极小项按下标从小到大排列将极小项按下标从小到大排列24求主合取范式的步骤求主合取范式的步骤设公式设公式A含命题变项含命题变项p1,p2,pn(1)求求A的合取范式的合取范式A=B1 B2 Bs,其中其中Bj是简单析是简单析取取式式j=1,2,s(2)若某个若某个Bj既不含既不含pi,又不含又不含 pi,则将则将Bj展开成展开成 BjBj(pi pi)(Bj
18、 pi)(Bj pi)重复这个过程重复这个过程,直到所有简单析取式都是长度为直到所有简单析取式都是长度为n的极大的极大项为止项为止(3)消去重复出现的极大项消去重复出现的极大项,即用即用Mi代替代替Mi Mi(4)将极大项按下标从小到大排列将极大项按下标从小到大排列25实例实例例例1(1(续续)求求(pq)r 的主析取范式与主合取范式的主析取范式与主合取范式解解(1)(1)(pq)r(pq)rpq(pq)1同一律同一律(pq)(r r)排中律排中律(pqr)(pq r)分配律分配律m4 m5 r(p p)(q q)r 同同一一律律,排排中中律律(pqr)(p qr)(pqr)(p q r)m0
19、 m2 m4 m6分配律分配律得得(pq)rm0 m2 m4 m5 m6可记作可记作(0,2,4,5,6)26实例实例(续续)(2)(pq)r(pr)(qr)prp 0r 同一律同一律p(qq)r 矛盾律矛盾律(p qr)(pqr)分配律分配律M1 M3 qr(pp)qr 同一律同一律,矛盾律矛盾律(pqr)(pqr)分配律分配律M3 M7得得(pq)rM1 M3 M7可记作可记作(1,3,7)27快速求法快速求法设公式含有设公式含有n个命题变项个命题变项,则则长度为长度为k的简单合取式可展开成的简单合取式可展开成2n-k个极小项的析取个极小项的析取例如例如公式含公式含p,q,rq(p qr)
20、(p q r)(p qr)(p q r)m2 m3 m6 m7长度为长度为k的简单析取式可展开成的简单析取式可展开成2n-k个极大项的合取个极大项的合取例如例如pr(p qr)(pqr)M1 M328实例实例例例2(1)求求A(p q)(pq r)r的主析取范式的主析取范式解解用快速求法用快速求法(1)p q(p qr)(p q r)m2 m3 pq rm1 r(pq r)(p q r)(pq r)(p q r)m1 m3 m5 m7得得Am1 m2 m3 m5 m7(1,2,3,5,7)29实例实例(续续)(2)求求B p(p qr)的主合取范式的主合取范式解解 p(p q r)(p qr)
21、(pq r)(pqr)M4 M5 M6 M7 p qrM1得得BM1 M4 M5 M6 M7(1,4,5,6,7)30主析取范式的用途主析取范式的用途(1)求公式的成真赋值和成假赋值求公式的成真赋值和成假赋值设公式设公式A含含n个命题变项个命题变项,A的主析取范式有的主析取范式有s个极小项个极小项,则则A有有s个成真赋值个成真赋值,它们是极小项下标的二进制表示它们是极小项下标的二进制表示,其余其余2n-s个赋值都是成假赋值个赋值都是成假赋值 例如例如(pq)rm0 m2 m4 m5 m6成真赋值成真赋值:000,010,100,101,110;成假赋值成假赋值:001,011,11131主析取
22、范式的用途主析取范式的用途(续续)(2)判断公式的类型判断公式的类型设设A含含n个命题变项，则个命题变项，则A为重言式当且仅当为重言式当且仅当A的主析取范式含的主析取范式含2n个极小项个极小项A为矛盾式当且仅当为矛盾式当且仅当A的主析取范式不含任何极小项的主析取范式不含任何极小项,记作记作0A为可满足式当且仅当为可满足式当且仅当A的主析取范式中至少含一个极小项的主析取范式中至少含一个极小项32实例实例例例3用主析取范式判断公式的类型用主析取范式判断公式的类型:(1)A(pq)q (2)Bp(p q)(3)C(p q)r解解(1)A(p q)q(pq)q 0矛盾式矛盾式(2)B p(p q)1m
23、0 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非重言式的可满足式非重言式的可满足式33主析取范式的用途主析取范式的用途(续续)(3)判断两个公式是否等值判断两个公式是否等值例例4用主析取范式判断下面用主析取范式判断下面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)34实例实例(续续)(2)(p q)r 与与p(q r)
24、解解(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)35实例实例例例5某单位要从某单位要从A,B,C三人中选派若干人出国考察三人中选派若干人出国考察,需满需满足下述条件足下述条件:(1)若若A去去,则则C必须去必须去;(2)若若B去去,则则C不能去不能去;(3)A和和B必须去一人且只能去一人必须去一人且只能去一人.问有几种可能的选派方案问有几种可能的选派方案?解解记记p:派派A去去,q:派派B去
25、去,r:派派C去去(1)pr,(2)qr,(3)(pq)(p q)求下式的成真赋值求下式的成真赋值 A=(pr)(qr)(pq)(p q)36实例实例(续续)求求A的主析取范式的主析取范式 A=(pr)(qr)(pq)(p q)(p r)(qr)(pq)(p q)(pq)(pr)(rq)(rr)(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去去37主合取范式主合取范式由主析取范式求主合取范式由主析取范式求主合取范式设设没有出现的极小项是没有出现的极小项是其中其中t=2n-s,于是于是38主合取范式主合取范式(续续)例例6求求A=(pq r)(p q r)(p q r)的主合取范的主合取范式式解解A m1 m3 m7M0 M2 M4 M5 M6矛盾式的主合取范式含全部矛盾式的主合取范式含全部2n个极大项个极大项重言式的主合取范式不含任何极大项重言式的主合取范式不含任何极大项,记作记作139