清华离散数学(第2版)课件

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

判断(pq)与

pq

是否等值解结论:(pq)(pq)

pqpqpq(pq)pq(pq)(pq)001101110110100110011001110010013真值表法例1判断(pq)与pq是否等值结真值表法(续)例2判断下述3个公式之间的等值关系:

p(qr),(pq)r,(pq)r解

pqrp(qr)(pq)r(pq)r000101001111010101011111100111101111110000111111p(qr)与(pq)r等值,但与(pq)r不等值4真值表法(续)例2判断下述3个公式之间的等值关系:p基本等值式双重否定律

AA幂等律

AAA,AAA交换律

ABBA,ABBA结合律(AB)CA(BC)(AB)CA(BC)分配律

A(BC)(AB)(AC)

A(BC)(AB)(AC)德摩根律

(AB)AB

(AB)AB吸收律

A(AB)A,A(AB)A5基本等值式双重否定律AA5基本等值式(续)零律

A11,A00同一律

A0A,

A1A排中律

AA1矛盾律

AA0蕴涵等值式

ABAB等价等值式

AB(AB)(BA)假言易位

ABBA等价否定等值式

ABAB归谬论(AB)(AB)A6基本等值式(续)零律等值演算等值演算:由已知的等值式推演出新的等值式的过程置换规则:若AB,则(B)(A)

例3

证明

p(qr)(pq)r证

p(qr)p(qr)（蕴涵等值式）(pq)r

（结合律）(pq)r

（德摩根律）(pq)r

（蕴涵等值式）7等值演算等值演算:由已知的等值式推演出新的等值式的过程7实例等值演算不能直接证明两个公式不等值.证明两个公式不等值的基本思想是找到一个赋值使一个成真,另一个成假.例4证明:p(qr)(pq)r方法一真值表法（见例2）方法二观察法.容易看出000使左边成真,使右边成假.方法三先用等值演算化简公式,再观察.8实例等值演算不能直接证明两个公式不等值.证明两个公式不8实例例5

用等值演算法判断下列公式的类型(1)q(pq)

解q(pq)

q(pq)（蕴涵等值式）

q(pq)（德摩根律）

p(qq)（交换律，结合律）

p0（矛盾律）

0（零律）该式为矛盾式.9实例例5用等值演算法判断下列公式的类型9实例(续)(2)(pq)(qp)解(pq)(qp)

(pq)(qp)（蕴涵等值式）

(pq)(pq)（交换律）

1该式为重言式.10实例(续)(2)(pq)(qp)10实例(续)(3)((pq)(pq))r)解((pq)(pq))r)

(p(qq))r

（分配律）

p1r

（排中律）

pr

（同一律）非重言式的可满足式.如101是它的成真赋值,000是它的成假赋值.总结:A为矛盾式当且仅当A0;A为重言式当且仅当A1说明:演算步骤不惟一,应尽量使演算短些11实例(续)(3)((pq)(pq))r)总结真值函数定义2.12称F:{0,1}n{0,1}为n元真值函数n元真值函数共有个每一个命题公式对应于一个真值函数每一个真值函数对应无穷多个命题公式1元真值函数

p

000111010112真值函数定义2.12称F:{0,1}n{0,1}为n元真2元真值函数

pq

0000000000010000111110001100111101010101pq

0011111111010000111110001100111101010101132元真值函数pq13联结词完备集定义2.13

设S是一个联结词集合,如果任何n(n1)元真值函数都可以由仅含S中的联结词构成的公式表示,则称S是联结词完备集定理2.1下述联结词集合都是完备集:(1)S1={,,,,}(2)S2={,,,}(3)S3={,,}(4)S4={,}(5)S5={,}(6)S6={,}AB(AB)(BA)ABABAB(AB)(AB)AB(AB)AB(A)B

AB14联结词完备集定义2.13设S是一个联结词集合,如果任何n复合联结词与非式:pq(pq),称作与非联结词或非式:pq(pq),称作或非联结词pq为真当且仅当p,q不同时为真pq为真当且仅当p,q不同时为假定理2.2{},{}是联结词完备集证p(pp)pppq(pq)(pq)(pq)(pq)得证{}是联结词完备集.对于{}可类似证明.15复合联结词与非式:pq(pq),称作与非联结2.3范式2.3.1析取范式与合取范式简单析取式与简单合取式析取范式与合取范式2.3.2主析取范式与主合取范式极小项与极大项主析取范式与主合取范式主范式的用途162.3范式2.3.1析取范式与合取范式16简单析取式与简单合取式文字:命题变项及其否定的统称简单析取式:有限个文字构成的析取式如p,q,pq,pqr,…简单合取式:有限个文字构成的合取式如p,q,pq,pqr,…定理2.3

(1)一个简单析取式是重言式当且仅当它同时含某个命题变项和它的否定(2)一个简单合取式是矛盾式当且仅当它同时含某个命题变项和它的否定17简单析取式与简单合取式文字:命题变项及其否定的统称17析取范式与合取范式析取范式:由有限个简单合取式组成的析取式

A1A2Ar,其中A1,A2,,Ar是简单合取式合取范式:由有限个简单析取式组成的合取式

A1A2Ar,其中A1,A2,,Ar是简单析取式范式:析取范式与合取范式的统称

定理2.4(1)一个析取范式是矛盾式当且仅当它的每一个简单合取式都是矛盾式(2)一个合取范式是重言式当且仅当它的每一个简单析取式都是重言式18析取范式与合取范式析取范式:由有限个简单合取式组成的析取式1范式存在定理定理2.5

任何命题公式都存在着与之等值的析取范式与合取范式.证求公式A的范式的步骤：(1)消去A中的,ABAB

AB(AB)(AB)(2)否定联结词的内移或消去AA(AB)AB

(AB)AB19范式存在定理定理2.5任何命题公式都存在着与之等值的析取范范式存在定理(续)(3)使用分配律A(BC)(AB)(AC)求合取范式

A(BC)(AB)(AC)求析取范式例1

求(pq)r的析取范式与合取范式解(pq)r

(pq)r

(pq)r

析取范式(pr)(qr)合取范式注意:公式的析取范式与合取范式不惟一.20范式存在定理(续)(3)使用分配律20极小项与极大项定义2.17

在含有n个命题变项的简单合取式(简单析取式)中,若每个命题变项均以文字的形式出现且仅出现一次，而且第i(1in)个文字(按下标或字母顺序排列)出现在左起第i位上,称这样的简单合取式(简单析取式)为极小项(极大项)说明:(1)

n个命题变项产生2n个极小项和2n个极大项(2)2n个极小项(极大项)均互不等值(3)用mi表示第i个极小项,其中i是该极小项成真赋值的十进制表示.用Mi表示第i个极大项,其中i是该极大项成假赋值的十进制表示,mi(Mi)称为极小项(极大项)的名称.

21极小项与极大项定义2.17在含有n个命题变项的简单合取式(极小项与极大项(续)定理2.6设mi与Mi是由同一组命题变项形成的极小项和极大项,则mi

Mi,Mi

mi极小项极大项公式成真赋值名称公式成假赋值名称pq00m0

pq00M0

pq01m1

pq01M1pq10m2

pq10M2

pq11m3

pq11M3p,q形成的极小项与极大项22极小项与极大项(续)定理2.6设mi与Mi是由同一组命题主析取范式与主合取范式主析取范式:由极小项构成的析取范式主合取范式:由极大项构成的合取范式例如，n=3,命题变项为p,q,r时，(pqr)(pqr)

m1m3

是主析取范式

(pqr)(pqr)

M1M5

是主合取范式定理2.7任何命题公式都存在着与之等值的主析取范式和主合取范式,并且是惟一的.23主析取范式与主合取范式主析取范式:由极小项构成的析取范式23求主析取范式的步骤设公式A含命题变项p1,p2,…,pn(1)求A的析取范式A=B1B2…Bs,其中Bj是简单合取式j=1,2,…,s

(2)若某个Bj既不含pi,又不含pi,则将Bj展开成

BjBj(pipi)(Bjpi)(Bjpi)重复这个过程,直到所有简单合取式都是长度为n的极小项为止(3)消去重复出现的极小项,即用mi代替mimi(4)将极小项按下标从小到大排列24求主析取范式的步骤设公式A含命题变项p1,p2,…,pn24求主合取范式的步骤设公式A含命题变项p1,p2,…,pn(1)求A的合取范式A=B1B2…Bs,其中Bj是简单析取式j=1,2,…,s

(2)若某个Bj既不含pi,又不含pi,则将Bj展开成

BjBj(pipi)(Bjpi)(Bjpi)重复这个过程,直到所有简单析取式都是长度为n的极大项为止(3)消去重复出现的极大项,即用Mi代替MiMi(4)将极大项按下标从小到大排列25求主合取范式的步骤设公式A含命题变项p1,p2,…,pn25实例例1(续)

求(pq)r的主析取范式与主合取范式解(1)(pq)r

(pq)r

pq

(pq)1同一律(pq)(rr)排中律

(pqr)(pqr)分配律

m4m5r(pp)(qq)r

同一律,排中律(pqr)(pqr)(pqr)(pqr)m0m2m4m6

分配律得(pq)r

m0m2m4m5m6可记作(0,2,4,5,6)26实例例1(续)求(pq)r的主析取范式与主合取范实例(续)(2)(pq)r

(pr)(qr)

pr

p0r

同一律p(qq)r矛盾律(pqr)(pqr)

分配律M1M3qr

(pp)qr

同一律,矛盾律(pqr)(pqr)分配律M3M7得

(pq)rM1M3M7可记作(1,3,7)27实例(续)(2)(pq)r(pr)(快速求法设公式含有n个命题变项,则长度为k的简单合取式可展开成2n-k个极小项的析取例如公式含p,q,r

q

(pqr)(pqr)(pqr)(pqr)m2m3m6m7长度为k的简单析取式可展开成2n-k个极大项的合取例如pr

(pqr)(pqr)

M1M328快速求法设公式含有n个命题变项,则28实例例2(1)求A(pq)(pqr)r的主析取范式解用快速求法(1)pq

(pqr)(pqr)m2m3pqrm1r(pqr)(pqr)(pqr)(pqr)m1m3m5m7得A

m1m2m3m5m7(1,2,3,5,7)29实例例2(1)求A(pq)(pqr实例(续)(2)求B

p(pqr)的主合取范式解p(pqr)(pqr)(pqr)(pqr)M4M5M6M7pqrM1得BM1M4M5M6M7(1,4,5,6,7)30实例(续)(2)求Bp(pqr)的主合取范主析取范式的用途(1)求公式的成真赋值和成假赋值设公式A含n个命题变项,A的主析取范式有s个极小项,则A有s个成真赋值,它们是极小项下标的二进制表示,其余2n-s个赋值都是成假赋值例如

(pq)r

m0m2m4m5m6

成真赋值:000,010,100,101,110;成假赋值:001,011,11131主析取范式的用途(1)求公式的成真赋值和成假赋值31主析取范式的用途(续)(2)判断公式的类型

设A含n个命题变项，则

A为重言式当且仅当A的主析取范式含2n个极小项A为矛盾式当且仅当

A的主析取范式不含任何极小项,记作0A为可满足式当且仅当A的主析取范式中至少含一个极小项32主析取范式的用途(续)(2)判断公式的类型32实例例3用主析取范式判断公式的类型:(1)A

(pq)q(2)B

p(pq)(3)C(pq)r解(1)A

(

pq)q(pq)q0矛盾式(2)B

p(pq)1m0m1m2m3

重言式(3)C(pq)r(pq)r(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)m0m1m3m5m7

非重言式的可满足式33实例例3用主析取范式判断公式的类型:33主析取范式的用途(续)(3)判断两个公式是否等值例4用主析取范式判断下面2组公式是否等值:(1)p与(pq)(pq)解pp(qq)(pq)(pq)m2m3(pq)(pq)(pq)(pq)

(pq)(pq)m2m3故p(pq)(pq)34主析取范式的用途(续)(3)判断两个公式是否等值34实例(续)(2)(pq)r与p(qr)解(pq)r

(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)m1m3m5m6m7p(qr)(pq)(pr)(pqr)(pqr)(pqr)(pqr)m5m6m7故(pq)r

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

((rq)(pq))((pq)(pq))((pr)(pq))((rq)(pq))(pqr)(pqr)成真赋值:101,010结论:方案1派A与C去,方案2派B去37实例(续)求A的主析取范式37主合取范式由主析取范式求主合取范式设没有出现的极小项是其中t=2n-s,于是38主合取范式由主析取范式求主合取范式没有出现的极小项是其中t=主合取范式(续)例6求A=(pqr)(pqr)(pqr)的主合取范式解A

m1m3m7

M0M2M4M5M6矛盾式的主合取范式含全部2n个极大项重言式的主合取范式不含任何极大项,记作139主合取范式(续)例6求A=(pqr)(pq2.2命题逻辑等值演算2.2.1等值式与等值演算等值式与基本等值式真值表法与等值演算法2.2.2联结词完备集真值函数联结词完备集与非联结词和或非联结词402.2命题逻辑等值演算2.2.1等值式与等值演算1等值式定义2.11若等价式AB是重言式,则称A与B等值,记作AB,并称AB是等值式说明:(1)是元语言符号,不要混同于和=(2)A与B等值当且仅当A与B在所有可能赋值下的真值都相同,即A与B有相同的真值表(3)n个命题变项的真值表共有个,故每个命题公式都有无穷多个等值的命题公式(4)可能有哑元出现.在B中出现,但不在A中出现的命题变项称作A的哑元.同样,在A中出现,但不在B中出现的命题变项称作B的哑元.哑元的值不影响命题公式的真值.41等值式定义2.11若等价式AB是重言式,则称A与B等值真值表法例1

判断(pq)与

pq

是否等值解结论:(pq)(pq)

pqpqpq(pq)pq(pq)(pq)0011011101101001100110011100100142真值表法例1判断(pq)与pq是否等值结真值表法(续)例2判断下述3个公式之间的等值关系:

p(qr),(pq)r,(pq)r解

pqrp(qr)(pq)r(pq)r000101001111010101011111100111101111110000111111p(qr)与(pq)r等值,但与(pq)r不等值43真值表法(续)例2判断下述3个公式之间的等值关系:p基本等值式双重否定律

AA幂等律

AAA,AAA交换律

ABBA,ABBA结合律(AB)CA(BC)(AB)CA(BC)分配律

A(BC)(AB)(AC)

A(BC)(AB)(AC)德摩根律

(AB)AB

(AB)AB吸收律

A(AB)A,A(AB)A44基本等值式双重否定律AA5基本等值式(续)零律

A11,A00同一律

A0A,

A1A排中律

AA1矛盾律

AA0蕴涵等值式

ABAB等价等值式

AB(AB)(BA)假言易位

ABBA等价否定等值式

ABAB归谬论(AB)(AB)A45基本等值式(续)零律等值演算等值演算:由已知的等值式推演出新的等值式的过程置换规则:若AB,则(B)(A)

例3

证明

p(qr)(pq)r证

p(qr)p(qr)（蕴涵等值式）(pq)r

（结合律）(pq)r

（德摩根律）(pq)r

（蕴涵等值式）46等值演算等值演算:由已知的等值式推演出新的等值式的过程7实例等值演算不能直接证明两个公式不等值.证明两个公式不等值的基本思想是找到一个赋值使一个成真,另一个成假.例4证明:p(qr)(pq)r方法一真值表法（见例2）方法二观察法.容易看出000使左边成真,使右边成假.方法三先用等值演算化简公式,再观察.47实例等值演算不能直接证明两个公式不等值.证明两个公式不8实例例5

用等值演算法判断下列公式的类型(1)q(pq)

解q(pq)

q(pq)（蕴涵等值式）

q(pq)（德摩根律）

p(qq)（交换律，结合律）

p0（矛盾律）

0（零律）该式为矛盾式.48实例例5用等值演算法判断下列公式的类型9实例(续)(2)(pq)(qp)解(pq)(qp)

(pq)(qp)（蕴涵等值式）

(pq)(pq)（交换律）

1该式为重言式.49实例(续)(2)(pq)(qp)10实例(续)(3)((pq)(pq))r)解((pq)(pq))r)

(p(qq))r

（分配律）

p1r

（排中律）

pr

（同一律）非重言式的可满足式.如101是它的成真赋值,000是它的成假赋值.总结:A为矛盾式当且仅当A0;A为重言式当且仅当A1说明:演算步骤不惟一,应尽量使演算短些50实例(续)(3)((pq)(pq))r)总结真值函数定义2.12称F:{0,1}n{0,1}为n元真值函数n元真值函数共有个每一个命题公式对应于一个真值函数每一个真值函数对应无穷多个命题公式1元真值函数

p

000111010151真值函数定义2.12称F:{0,1}n{0,1}为n元真2元真值函数

pq

0000000000010000111110001100111101010101pq

0011111111010000111110001100111101010101522元真值函数pq13联结词完备集定义2.13

设S是一个联结词集合,如果任何n(n1)元真值函数都可以由仅含S中的联结词构成的公式表示,则称S是联结词完备集定理2.1下述联结词集合都是完备集:(1)S1={,,,,}(2)S2={,,,}(3)S3={,,}(4)S4={,}(5)S5={,}(6)S6={,}AB(AB)(BA)ABABAB(AB)(AB)AB(AB)AB(A)B

AB53联结词完备集定义2.13设S是一个联结词集合,如果任何n复合联结词与非式:pq(pq),称作与非联结词或非式:pq(pq),称作或非联结词pq为真当且仅当p,q不同时为真pq为真当且仅当p,q不同时为假定理2.2{},{}是联结词完备集证p(pp)pppq(pq)(pq)(pq)(pq)得证{}是联结词完备集.对于{}可类似证明.54复合联结词与非式:pq(pq),称作与非联结2.3范式2.3.1析取范式与合取范式简单析取式与简单合取式析取范式与合取范式2.3.2主析取范式与主合取范式极小项与极大项主析取范式与主合取范式主范式的用途552.3范式2.3.1析取范式与合取范式16简单析取式与简单合取式文字:命题变项及其否定的统称简单析取式:有限个文字构成的析取式如p,q,pq,pqr,…简单合取式:有限个文字构成的合取式如p,q,pq,pqr,…定理2.3

(1)一个简单析取式是重言式当且仅当它同时含某个命题变项和它的否定(2)一个简单合取式是矛盾式当且仅当它同时含某个命题变项和它的否定56简单析取式与简单合取式文字:命题变项及其否定的统称17析取范式与合取范式析取范式:由有限个简单合取式组成的析取式

A1A2Ar,其中A1,A2,,Ar是简单合取式合取范式:由有限个简单析取式组成的合取式

A1A2Ar,其中A1,A2,,Ar是简单析取式范式:析取范式与合取范式的统称

定理2.4(1)一个析取范式是矛盾式当且仅当它的每一个简单合取式都是矛盾式(2)一个合取范式是重言式当且仅当它的每一个简单析取式都是重言式57析取范式与合取范式析取范式:由有限个简单合取式组成的析取式1范式存在定理定理2.5

任何命题公式都存在着与之等值的析取范式与合取范式.证求公式A的范式的步骤：(1)消去A中的,ABAB

AB(AB)(AB)(2)否定联结词的内移或消去AA(AB)AB

(AB)AB58范式存在定理定理2.5任何命题公式都存在着与之等值的析取范范式存在定理(续)(3)使用分配律A(BC)(AB)(AC)求合取范式

A(BC)(AB)(AC)求析取范式例1

求(pq)r的析取范式与合取范式解(pq)r

(pq)r

(pq)r

析取范式(pr)(qr)合取范式注意:公式的析取范式与合取范式不惟一.59范式存在定理(续)(3)使用分配律20极小项与极大项定义2.17

在含有n个命题变项的简单合取式(简单析取式)中,若每个命题变项均以文字的形式出现且仅出现一次，而且第i(1in)个文字(按下标或字母顺序排列)出现在左起第i位上,称这样的简单合取式(简单析取式)为极小项(极大项)说明:(1)

n个命题变项产生2n个极小项和2n个极大项(2)2n个极小项(极大项)均互不等值(3)用mi表示第i个极小项,其中i是该极小项成真赋值的十进制表示.用Mi表示第i个极大项,其中i是该极大项成假赋值的十进制表示,mi(Mi)称为极小项(极大项)的名称.

60极小项与极大项定义2.17在含有n个命题变项的简单合取式(极小项与极大项(续)定理2.6设mi与Mi是由同一组命题变项形成的极小项和极大项,则mi

Mi,Mi

mi极小项极大项公式成真赋值名称公式成假赋值名称pq00m0

pq00M0

pq01m1

pq01M1pq10m2

pq10M2

pq11m3

pq11M3p,q形成的极小项与极大项61极小项与极大项(续)定理2.6设mi与Mi是由同一组命题主析取范式与主合取范式主析取范式:由极小项构成的析取范式主合取范式:由极大项构成的合取范式例如，n=3,命题变项为p,q,r时，(pqr)(pqr)

m1m3

是主析取范式

(pqr)(pqr)

M1M5

是主合取范式定理2.7任何命题公式都存在着与之等值的主析取范式和主合取范式,并且是惟一的.62主析取范式与主合取范式主析取范式:由极小项构成的析取范式23求主析取范式的步骤设公式A含命题变项p1,p2,…,pn(1)求A的析取范式A=B1B2…Bs,其中Bj是简单合取式j=1,2,…,s

(2)若某个Bj既不含pi,又不含pi,则将Bj展开成

BjBj(pipi)(Bjpi)(Bjpi)重复这个过程,直到所有简单合取式都是长度为n的极小项为止(3)消去重复出现的极小项,即用mi代替mimi(4)将极小项按下标从小到大排列63求主析取范式的步骤设公式A含命题变项p1,p2,…,pn24求主合取范式的步骤设公式A含命题变项p1,p2,…,pn(1)求A的合取范式A=B1B2…Bs,其中Bj是简单析取式j=1,2,…,s

(2)若某个Bj既不含pi,又不含pi,则将Bj展开成

BjBj(pipi)(Bjpi)(Bjpi)重复这个过程,直到所有简单析取式都是长度为n的极大项为止(3)消去重复出现的极大项,即用Mi代替MiMi(4)将极大项按下标从小到大排列64求主合取范式的步骤设公式A含命题变项p1,p2,…,pn25实例例1(续)

求(pq)r的主析取范式与主合取范式解(1)(pq)r

(pq)r

pq

(pq)1同一律(pq)(rr)排中律

(pqr)(pqr)分配律

m4m5r(pp)(qq)r

同一律,排中律(pqr)(pqr)(pqr)(pqr)m0m2m4m6

分配律得(pq)r

m0m2m4m5m6可记作(0,2,4,5,6)65实例例1(续)求(pq)r的主析取范式与主合取范实例(续)(2)(pq)r

(pr)(qr)

pr

p0r

同一律p(qq)r矛盾律(pqr)(pqr)

分配律M1M3qr

(pp)qr

同一律,矛盾律(pqr)(pqr)分配律M3M7得

(pq)rM1M3M7可记作(1,3,7)66实例(续)(2)(pq)r(pr)(快速求法设公式含有n个命题变项,则长度为k的简单合取式可展开成2n-k个极小项的析取例如公式含p,q,r

q

(pqr)(pqr)(pqr)(pqr)m2m3m6m7长度为k的简单析取式可展开成2n-k个极大项的合取例如pr

(pqr)(pqr)

M1M367快速求法设公式含有n个命题变项,则28实例例2(1)求A(pq)(pqr)r的主析取范式解用快速求法(1)pq

(pqr)(pqr)m2m3pqrm1r(pqr)(pqr)(pqr)(pqr)m1m3m5m7得A

m1m2m3m5m7(1,2,3,5,7)68实例例2(1)求A(pq)(pqr实例(续)(2)求B

p(pqr)的主合取范式解p(pqr)(pqr)(pqr)(pqr)M4M5M6M7pqrM1得BM1M4M5M6M7(1,4,5,6,7)69实例(续)(2)求Bp(pqr)的主合取范主析取范式的用途(1)求公式的成真赋值和成假赋值设公式A含n个命题变项