离散结构其他课件-总复习第一章

11.5对偶与范式

对偶式与对偶原理

析取范式与合取范式

主析取范式与主合取范式

2对偶式和对偶原理定义

在仅含有联结词,∧,∨的命题公式A中，将∨换成∧,∧换成∨，若A中含有0或1，就将0换成1，1换成0，所得命题公式称为A的对偶式，记为A*.从定义不难看出，(A*)*还原成A定理

设A和A*互为对偶式，p1,p2,…,pn是出现在A和A*中的全部命题变项，将A和A*写成n元函数形式，则(1)A(p1,p2,…,pn)

A*(

p1,

p2,…,

pn)(2)A(

p1,

p2,…,

pn)

A*(p1,p2,…,pn)定理（对偶原理）设A，B为两个命题公式，若AB，则A*

B*.3析取范式与合取范式

文字:命题变项及其否定的总称简单析取式:有限个文字构成的析取式如p,q,pq,pqr,…简单合取式:有限个文字构成的合取式如p,q,pq,pqr,…析取范式:由有限个简单合取式组成的析取式

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

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

A1A2Ar,其中A1,A2,,Ar是简单合取式例如:(pq)(pqr)合取范式:由有限个简单析取式组成的合取式

A1A2Ar

,其中A1,A2,,Ar是简单析取式例如:(pq)(pqr)5析取范式与合取范式(续)范式:析取范式与合取范式的总称

公式A的析取范式:与A等值的析取范式公式A的合取范式:与A等值的合取范式说明：

单个文字既是简单析取式，又是简单合取式pqr,pqr既是析取范式，又是合取范式(为什么?)

6命题公式的范式

定理

任何命题公式都存在着与之等值的析取范式与合取范式.求公式A的范式的步骤：(1)消去A中的,（若存在）(2)否定联结词的内移或消去(3)使用分配律

对分配（析取范式）

对分配（合取范式）公式的范式存在，但不惟一7范式存在定理定理任何命题公式都存在着与之等值的析取范式与合取范式.证求公式A的范式的步骤：(1)消去A中的,ABAB

AB(AB)(BA)

(AB)(AB)8范式存在定理(2)否定联结词的内移或消去 (AB)AB

(AB)ABAA(3)使用分配律A(BC)(AB)(AC)求合取范式

A(BC)(AB)(AC)求析取范式9极小项与极大项

定义

在含有n个命题变项的简单合取式(简单析取式)中，若每个命题变项均以文字的形式在其中出现且仅出现一次，而且第i（1in）个文字出现在左起第i位上，称这样的简单合取式（简单析取式）为极小项（极大项）.说明：n个命题变项产生2n个极小项和2n个极大项2n个极小项（极大项）均互不等值用mi表示第i个极小项，其中i是该极小项成真赋值的十进制表示.用Mi表示第i个极大项，其中i是该极大项成假赋值的十进制表示,mi(Mi)称为极小项(极大项)的名称.

mi与Mi的关系:

mi

Mi,Mi

mi

10极小项与极大项(续)由p,q两个命题变项形成的极小项与极大项

公式

成真赋值名称

公式

成假赋值名称

p

qp

qp

qp

q00011011m0m1m2m3

p

q

p

q

p

q

p

q

00011011

M0M1M2M3

极小项

极大项

11

由p,q,r三个命题变项形成的极小项与极大项

极小项

极大项

公式

成真赋值名称

公式

成假赋值名称

pq

rpq

rpq

rpq

rpq

rpq

rpq

rpq

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

12主析取范式与主合取范式

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

m1m3

是主析取范式

(pqr)(pqr)

M1M5

是主合取范式

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

13主析取范式与主合取范式(续)定理

任何命题公式都存在着与之等值的主析取范式和主合取范式,并且是惟一的.

用等值演算法求公式的主范式的步骤：(1)先求析取范式（合取范式）(2)将不是极小项（极大项）的简单合取式（简单析取式）化成与之等值的若干个极小项的析取（极大项的合取），需要利用同一律（零律）、排中律（矛盾律）、分配律、幂等律等.

(3)极小项（极大项）用名称mi（Mi）表示，并按角标从小到大顺序排序.

14求主析取范式的步骤设公式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)将极小项按下标从小到大排列15求主合取范式的步骤设公式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)将极大项按下标从小到大排列16快速求法设公式含有n个命题变项,则长度为k的简单析取式可展开成2nk个极大项的合取例如pr

(pqr)(pqr)

M1M3长度为k的简单合取式可展开成2nk个极小项的析取例如公式含p,q,r

q

(pqr)(pqr)(pqr)(pqr)M5M4M1M017实例例2(1)求A(pq)(pqr)r的主析取范式解用快速求法18实例例2(1)求A(pq)(pqr)r的主析取范式解用快速求法pq

(pqr)(pqr)m2m3pqrm1r(pqr)(pqr)(pqr)(pqr)m1m3m5m7得Am1m2m3m5m7(1,2,3,5,7)19主合取范式由主析取范式求主合取范式设没有出现的极小项是其中t=2ns,于是20主合取范式(续)例6求A=(pqr)(pqr)(pqr)的主合取范式解A

m1m3m7(1,3,7)(0,2,4,5,6)M0M2M4M5M6矛盾式的主合取范式含全部2n个极大项重言式的主合取范式不含任何极大项,记作121主范式的用途——与真值表相同

(1)求公式的成真赋值和成假赋值

例如(pq)r

m1m3m5

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

类似地，由主合取范式也可立即求出成假赋值和成真赋值.22主范式的用途(续)(2)判断公式的类型

设A含n个命题变项，则