离散数学析取范式与合取范式

1.4析取范式与合取范式简单析取式与简单合取式

析取范式与合取范式主析取范式与主合取范式1定义文字:命题变项及其否定的总称.简单析取式:有限个文字构成的析取式.如

p,

q,p

q,p

q

r,…简单合取式:有限个文字构成的合取式.如

p,

q,p

q,p

q

r,…1）一个简单析取式为重言式当且仅当它同时含有一个命题变项及它的否定；2）一个简单和取式为矛盾式当且仅当它同时含有一个命题变项及它的否定.由定义易知：2

由有限个简单合取式组成的析取式.

A1

A2

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

A1

A2

Ar,其中A1,A2,,Ar是简单析取式由定义易知：析取范式:1）在析取范式（合取范式）中没有联结词2）联结词只出现在原子命题前面.3）析取范式（合取范式）是合取式（析取式）的析取式（合取式）.3范式:析取范式与合取范式的总称.公式A的析取范式:与A等值的析取范式公式A的合取范式:与A等值的合取范式说明：单个文字既是简单析取式，又是简单合取式形如p

q

r,

p

q

r的公式既是析取范式，又是合取范式(为什么?)4

任何命题公式都存在着与之等值的析取范式与合取范式.求公式A的范式的步骤：

(1)消去A中的

,

（若存在）

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

(3)利用分配律

对

分配（析取范式）

对

分配（合取范式）公式的范式存在，但不惟一，这是它的局限性.定理（范式存在定理）5求公式的范式举例例1.15求下列公式的析取范式与合取范式:(1)A=(p

q)

r解(p

q)

r

(

p

q)

r

（消去

）

p

q

r

（结合律）这既是A的析取范式（由3个简单合取式组成的析取式），又是A的合取范式（由一个简单析取式组成的合取式）6(2)B=(p

q)

r解:(p

q)

r

(

p

q)

r

（消去第一个

）

(

p

q)

r

（消去第二个

）

(p

q)

r

（否定号内移——德摩根律）这一步已为析取范式（两个简单合取式构成）继续：(p

q)

r

(p

r)

(q

r)（

对

分配律）这一步得到合取范式（由两个简单析取式构成）7例1.16(1)求(

p

q)(p

r)的析取范式;解:(

p

q)(p

r)

(

p

q)

(

p

r)（消去

）

(

p

q)

(

p

r)（双重否定律）

(

p

p)

(q

p)

(

p

r)

(q

r)

（对分配）

(q

p)

(

p

r)

(q

r)（零律,同一律）8(2)求(p

q)

(p

r)

的合取范式。解:(p

q)

(p

r)

(

p

q)

(p

r)

（消去

）

(

p

q

p)

(

p

q

r)

（对分配）

p

q

r

（排中律,同一律）

9极小项定义在含有n个命题变项的简单合取式中，若每个命题变项均以文字的形式在其中出现且只出现一次，而且第i（1

i

n）个文字出现在左起第i位上，这样的简单合取式称为极小项.如：p

q，p

q

r10说明：n个命题变项产生2n个极小项，2n个极小项均互不等值.用mi表示第i个极小项，其中i是该极小项成真赋值的十进制表示,mi称为极小项的名称.11公式成真赋值极小项

p

q

p

qp

qp

q00011011由p,q两个命题变项形成的极小项:12

由p,q,r三个命题变项形成的极小项:公式成真赋值极小项

p

q

r

p

q

r

p

q

r

p

q

rp

q

rp

q

rp

q

rp

q

r000001010011100101110111m0m1m2m3m4m5m6m713主析取范式主析取范式:由极小项构成的析取范式.例如，n=3,命题变项为p,q,r时，(

p

q

r)

(

p

q

r)

m1

m3

是主析取范式

A的主析取范式:与A等值的主析取范式.

14定理

任何命题公式都存在着与之等值的主析取范式,并且是惟一的.用等值演算法求公式的主析取范式的步骤：(1)先求析取范式;(2)将不是极小项的简单合取式化成与之等值的若干个极小项的析取，需要利用同一律、排中律、分配律、等幂律……(3)极小项用名称mi表示，按角标从小到大顺序排序.15求公式的主析取范式例1.17求公式(p

q)

r的主析取范式.(p

q)

r

(p

q)

r,（析取范式）①其中(p

q)

(p

q)

(

r

r)

(p

q

r)

(p

q

r)

m6

m7,②16r

(

p

p)

(

q

q)

r

(

p

q

r)

(

p

q

r)

(p

q

r)

(p

q

r)

m1

m3

m5

m7③②,③代入①并排序，得

(p

q)

r

m1

m3

m5

m6

m7（主析取范式）17例1.18求下列公式的主析取范式.(

p

q)

(p

r)((p

q)

r)

p答案:(1)(

p

q)

(p

r)

m2

m3

m5

m7

(2)((p

q)

r)

p

m2

m4

m5

m6

m7

18例1.19由(p

q)

r的真值表求其主析取范式.pqrp

q(p

q)

r

0000010101110111001011101110011111100000主析取范式为：m3

m5

m719作业:

P3617(1)(3)，18(1)，19

201.证明：⑴p

(q

r)

(p

q)

r⑵(p

q)

(p

q)

p2.求主析取范式：⑴

(p

q)

r⑵(p

q)

(q

r)

(3)

(p

q)

q

r

(4)(p

q)

r课堂练习：∑(0,1,3,7)∑(1,3,5,7)∑(5)∑(1,3,4,5,7)21主范式的用途——与真值表相同(1)求公式的成真赋值和成假赋值

例如(p

q)

r

m1

m3

m5

m6

m7，其成真赋值为001,011,101,110,111，其余的赋值000,010,100为成假赋值.

22

设A含n个命题变项，则A为重言式

A的主析取范式含2n个极小项A为矛盾式

A的主析取范式为0A为非重言式的可满足式

A的主析取范式中至少含一个但不含全部极小项(2)判断公式的类型23例1.20用主析取范式判断下述两公式是否等值：⑴p

(q

r)与(p

q)

r⑵p

(q

r)与(p

q)

r解:p

(q

r)

m0

m1

m2

m3

m4

m5

m7

(p

q)

r

m0

m1

m2

m3

m4

m5

m7(p

q)

r

m1

m3

m4

m5

m7显见，⑴中两公式等值，而⑵的两公式不等值.(3)判断两个公式是否等值24(4)分析和解决一些实际问题例1.21某公司要从赵、钱、孙三名新毕业的大学生中选派一些人出国学习，选派必须满足以下条件：

(1)若赵去，则孙也可以去；

(2)若钱去，则孙不能去；

(3)若孙不去，则赵或钱可以去.试用主析取范式法分析该公司如何选派他们出国？25解此类问题的步骤为：①将简单命题符号化；②写出各复合命题；③写出由②中复合命题组成的合取式；④求③中所得公式的主析取范式。26解:①设p：派赵去，q：派钱去，r：派孙去.②(1)p

r(2)q

r(3)

r(p

q)③(1)~(3)构成的合取式为

A=(p

r)

(q

r)

(

r(p

q))27④A的演算:A

(

p

q

r)

(

p

q

r)

(p

q

r)

∑(1,2,5)结论：由④可知，A的成真赋值为001、010、101，因而方案有三个：孙去（赵、钱不去）；钱去（赵、孙不去）；赵、孙（钱不去）.28极大项定义在含有n个命题变项的简单析取式中，若每个命题变项均以文字的形式在其中出现且只出现一次，而且第i（1

i

n）个文字出现在左起第i位上，这样的简单析取式称为极大项.29说明：n个命题变项产生2n个极大项，2n个极大项均互不等值.用Mi表示第i个极大项，其中i是该极大项成假赋值的十进制表示,Mi称为极大项的名称.30公式成假赋值极大项

p

qp

q

p

qp

q00100111由p,q两个命题变项形成的极大项31

由p,q,r三个命题变项形成的极大项公式成假赋值名称p

q

r

p

q

r

p

q

r

p

q

r

p

q

r

p

q

r

p

q

r

p

q

r

000001010011100101110111M0M1M2M3M4M5M6M7

32极小项与极大项比较由p,q两个命题变项形成的极小项与极大项公式成真赋值名称公式成假赋值名称

p

q

p

qp

qp

q00011011m0m1m2m3

p

q

p

q

p

q

p

q

00011011M0M1M2M3

极小项极大项33

由p,q,r三个命题变项形成的极小项与极大项极小项极大项公式成真赋值名称公式成假赋值名称

p

q

r

p

q

r

p

q

r

p

q

rp

q

rp

q

rp

q

rp

q

r000001010011100101110111m0m1m2m3m4m5m6m7p

q

r

p

q

r

p

q

r

p

q

r

p

q

r

p

q

r

p

q

r

p

q

r

000001010011100101110111M0M1M2M3M4M5M6M7

34主合取范式:由极大项构成的合取范式.例如，n=3,命题变项为p,q,r时，(p

q

r)

(

p

q

r)

M1

M5

是主合取范式A的主合取范式:与A等值的主合取范式.由上述比较可知：极小项mi与极大项Mi的关系:

mi

Mi,

Mi

mi

35求主合取范式的方法：1.

等值演算法：(1)先求合取范式;(2)将不是极大项的简单析取式化成与之等值的若干个极大项的合取，需要利用零