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

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

p,

q,p

q,p

q

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

p,

q,p

q,p

q

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

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

A1

A2

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

A1

A2

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

q

r,

p

q

r的公式既是析取范式，又是合取范式(为什么?)第三页3第四页，共40页。

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

(1)消去A中的

,

（若存在）

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

(3)利用分配律

对

分配（析取范式）

对

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

q)

r解(p

q)

r

(

p

q)

r

（消去

）

p

q

r

（结合律）这既是A的析取范式（由3个简单合取式组成的析取式），又是A的合取范式（由一个简单析取式组成的合取式）第五页5第六页，共40页。(2)B=(p

q)

r解:(p

q)

r

(

p

q)

r

（消去第一个

）

(

p

q)

r

（消去第二个

）

(p

q)

r

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

q)

r

(p

r)

(q

r)（

对

分配律）这一步得到合取范式（由两个简单析取式构成）第六页6第七页，共40页。例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)（零律,同一律）第七页7第八页，共40页。(2)求(p

q)

(p

r)

的合取范式。解:(p

q)

(p

r)

(

p

q)

(p

r)

（消去

）

(

p

q

p)

(

p

q

r)

（对分配）

p

q

r

（排中律,同一律）

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

i

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

q，p

q

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

p

q

p

qp

qp

q00011011由p,q两个命题变项形成的极小项:第十一页11第十二页，共40页。

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

p

q

r

p

q

r

p

q

r

p

q

rp

q

rp

q

rp

q

rp

q

r000001010011100101110111m0m1m2m3m4m5m6m7第十二页12第十三页，共40页。主析取范式主析取范式:由极小项构成的析取范式.例如，n=3,命题变项为p,q,r时，(

p

q

r)

(

p

q

r)

m1

m3

是主析取范式

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

第十三页13第十四页，共40页。定理

任何命题公式都存在着与之等值的主析取范式,并且是惟一的.用等值演算法求公式的主析取范式的步骤：(1)先求析取范式;(2)将不是极小项的简单合取式化成与之等值的若干个极小项的析取，需要利用同一律、排中律、分配律、等幂律……(3)极小项用名称mi表示，按角标从小到大顺序排序.第十四页14第十五页，共40页。求公式的主析取范式例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,②第十五页15第十六页，共40页。r

(

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（主析取范式）第十六页16第十七页，共40页。例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

第十七页17第十八页，共40页。例1.19由(p

q)

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

q(p

q)

r

0000010101110111001011101110011111100000主析取范式为：m3

m5

m7第十八页18第十九页，共40页。作业:

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

第十九页19第二十页，共40页。1.证明：⑴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)第二十页20第二十一页，共40页。主范式的用途——与真值表相同(1)求公式的成真赋值和成假赋值

例如(p

q)

r

m1

m3

m5

m6

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

第二十一页21第二十二页，共40页。

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

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

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

A的主析取范式中至少含一个但不含全部极小项(2)判断公式的类型第二十二页22第二十三页，共40页。例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)判断两个公式是否等值第二十三页23第二十四页，共40页。(4)分析和解决一些实际问题例1.21某公司要从赵、钱、孙三名新毕业的大学生中选派一些人出国学习，选派必须满足以下条件：

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

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

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

r(2)q

r(3)

r(p

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

A=(p

r)

(q

r)

(

r(p

q))第二十六页26第二十七页，共40页。④A的演算:A

(

p

q

r)

(

p

q

r)

(p

q

r)

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

i

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

p

qp

q

p

qp

q00100111由p,q两个命题变项形成的极大项第三十页30第三十一页，共40页。

由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

第三十一页31第三十二页，共40页。极小项与极大项比较由p,q两个命题变项形成的极小项与极大项公式成真赋值名称公式成假赋值名称

p

q

p

qp

qp

q00011011m0m1m2m3

p

q

p

q

p

q

p

q

00011011M0M1M2M3

极小项极大项第三十二页32第三十三页，共40页。

由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

第三十三页33第三十四页，共40页。主合取范式:由极大项构成的合取范式.例如，n=3,命题变项为p,q,r时，(p

q

r)

(

p

q

r)

M1

M5

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

mi

Mi,

Mi

mi

第三十四页34第三十五页，共40页。求主合取范式的方法：1.

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