离散数学-1-7对偶与范式.ppt

单击此处编辑母版标题样式,,单击此处编辑母版文本样式,,第二级,,第三级,,第四级,,第五级,,*,*,第一章 命题逻辑,,1-7 对偶与范式,,1,,尽管命题公式的最小联结词组可为,,¬,，∧,,，,,¬,，∨,,，,,↑,,，,,↓,，,但实际上一般出于方便的目的，命题公式常常包含,,¬,，∧， ∨,从第15页的表1-4.8的,命题定律中可以看出，,很多常用等价式是成对出现的，只要将其中的“∧”和“∨”分别换成“∨”和“∧”，就可以由一个得到另一个例如，将命题定律,(,P∨Q)∨R,P,∨(Q∨R),中的“∨”换成“∧”就得到了命题定律,(,P∧Q)∧R,P,∧(Q∧R),这些成对出现的等价式反映了,等价的对偶性,我们将这样的公式称作具有,对偶规律,本节将先介绍对偶式和对偶原理2,,一、对偶式与对偶原理,,定义1-7.1,在给定的命题公式,A,中，将,联结词∨、∧分别换成∧、∨ ，若有特殊变元,F,和,T,亦相互对代,，所得的公式称为公式,A,的对偶式，记为,A,*,设,A,*,是,A,的对偶式，将,A,*,中的∨，∧，,F,，,T,分别换成∧，∨，,T,，,F,，,就会得到,A,。

即,A,是,A,*,的对偶式,，,(,A,*)*,,A,所以说,A,*,和,A,互为对偶式,例题1 写出下列表达式的对偶式,,1.（,P∨Q）∧R,,2.,（,P ∧ Q）∨,T,,3.,,（,,P∨Q）∧（ P∨,,（Q ∧,S,））,,3,,一、对偶式与对偶原理,,例题2 求,P↑Q,和,P↓Q,的对偶式解,：,,P,↑,Q,,¬(,P,∧,Q,),,¬(,P,∧,Q,),的对偶式是,¬(,P,∨,Q,),,P,↓,Q,,,故,P,↑,Q,的对偶式是,P,↓,Q,；,同样的方法可以证明,P,↓,Q,的对偶式是,P,↑,Q,注意：,根据例题2，,对偶式概念可以推广为,：在仅含有联结词¬，∧，∨，↑，↓的命题公式中，将联结词∨，∧，↑，↓，,F,，,T,分别换成 ∧，∨，↓，↑，,T,，,F,，,就得到了它的对偶式4,,一、对偶式与对偶原理,,*关于对偶式有以下两个结论定理1-7.1,设,A,*,是,A,的对偶式，,P,1,，,P,2,，…，,P,n,是出现在,A,和,A,*,中的原子变元，则,,¬,A,(,P,1,，,P,2,，…，,P,n,),,A,*(¬,P,1,，¬,P,2,，…，¬,P,n,),,A,(¬,P,1,，¬,P,2,，…，¬,P,n,),,¬,A,*(,P,1,，,P,2,，…，,P,n,),,,,证明见,P30,：,由德摩根律层层置换，即可层层推出。

5,,一、对偶式与对偶原理,,例：,设命题公式,A,(,P,,,Q,,,R,),,(,P,∨,Q,),∧,R,，,试用此公式验证定理的有效性证明：,,⑴,验证 ¬,A,(,P,,,Q,,,R,),,A,*(¬,P,, ¬,Q,, ¬,R,),,A,(,P,,,Q,,,R,),,(,P,∨,Q,)∧,R,,¬,A,(,P,,,Q,,,R,),,¬((,P,∨,Q,)∧,R,),,(¬,P,∧¬,Q,)∨¬,R,,A,*(,P,,,Q,,,R,),,(,P,∧,Q,)∨,R,,A,*(¬,P,, ¬,Q,, ¬,R,),,( ¬,P,∧¬,Q,)∨¬,R,,所以，¬,A,(,P,,,Q,,,R,),,A,*(¬,P,,¬,Q,,¬,R,),,,⑵,验证,A,(¬,P,,,¬,Q,,,¬,R,),,¬,A,*(,P,,,Q,,,R,),,A,(¬,P,,,¬,Q,,,¬,R,),,(¬,P,∨¬,Q,)∧¬,R,,,¬((,P,∧,Q,)∨,R,),,¬,A,*(,P,,,Q,,,R,),6,,一、对偶式与对偶原理,,定理1-7.2,,设,P,1,，,P,2,，,…,，,P,n,是出现在公式,A,和,B,中的所有原子变元，如果,A,,B,，,则,A,*,,B,*,。

证明,：,,因为,A,,B,,,所以,A,(,P,1,，,P,2,，,…,，,P,n,)↔,B,(,P,1,，,P,2,，,…,，,P,n,),是重言式,,根据定理1-5.2(,P19)，,在上述重言式中用¬,P,i,置换,P,i,，,,i,＝1,,…,,,n,，,所得的公式仍为重言式，即,,,A,(¬,P,1,，¬,P,2,，,…,，¬,P,n,)↔,B,(¬,P,1,，¬,P,2,，,…,，¬,P,n,),是重言,,式所以,A,(¬,P,1,，¬,P,2,，,…,，¬,P,n,),,B,(¬,P,1,，¬,P,2,，,…,，¬,P,n,),,,由定理1-7.1¬,A,*(,P,1,，,P,2,，,…,，,P,n,),,¬,B,*(,P,1,，,P,2,，,…,，,P,n,),,,即 ¬,A,*,,¬,B,*,,,因此,A,*,,B,*,,*,定理1.7.2叫做,对偶原理,对偶原理是数理逻辑中最基本的规律之一7,,一、对偶式与对偶原理,,例题4,:,如果,A(P,Q,R),是,P↑(Q∧¬(R,↓,P))，,求它的对偶式,A*(P,Q,R)并求,A,及,A*,的等价，但仅包含联结词“,∧,”、“,∨,”及“,¬”,的公式。

解： 因,A(P,Q,R),是,P↑(Q∧¬(R,↓,P)),,所以,A*,是,P,↓,(Q∨¬(R ↑ P)),,,而,P↑(Q∧¬(R,↓,P)),,,¬(P∧(Q∧(R∨P)),,故,P,↓,(Q∨¬(R ↑ P)),,¬,(,P∨(Q∨(R∧P)),,使用真值表和对偶原理可以简化或推证一些命题公式8,,一、对偶式与对偶原理,,例,：,证明,重言式的对偶式是矛盾式，矛盾式的对偶式是重言式证明,：,设,A,是重言式，即,A,,T,，,因为,T,的对偶式是,F,，,由对偶原理知,A,*,,F,所以,A,*,是矛盾式；,,设,A,是矛盾式，即,A,,F,,，,而,F,的对偶式是,T,，所以,A,*,,T,所以,A,*,是重言式9,,二、析取范式与合取范式,,每种数字标准形都能提供很多信息，如代数式的因式分解可判断代数式的根情况逻辑公式在等值演算下也有标准形,--,范式，范式有两种：析取范式和合取范式同一命题公式可以有各种相互等价的表达形式，范式可以实现命题公式的规范化,,,10,,二、析取范式与合取范式,,定义（补充）,仅有有限个命题变元或其否定构成的合(析)取式称作,简单合(析)取式,。

如：,,,┐,P,Q,等为,一个文字,(,一个命题变元或它的否定称为文字,)构成的简单合取式，┐,P∧P，P∧┐Q,等为2个文字构成的简单合取，,P∧Q∧┐R,┐P∧P∧Q,等为3个文字构成的简单合取式,,P,,┐,Q,等为,一个文字,（,一个变元或变元的否定）的简单析趋式,，,P∨┐P，┐P∨Q,等为2个变元（或变元的否定）简单析取式，┐,P∨┐Q∨R,P∨┐Q∨R,等为3个文字构成的简单析取式11,,二、析取范式与合取范式,,定义1-7.2,,一个命题公式称为,合取范式,，当且仅当它具有形式：,,,A,1,∧,A,2,∧……∧,A,n,(n 1),,其中,A,1,，,A,2,，……，,A,n,都是,简单析取式,如: (,P∨┐Q∨R),∧,(,┐P∨Q),∧,┐Q,,定义1-7.2,,一个命题公式称为,析取范式,，当且仅当它具有形式：,,,A,1,∨,A,2,∨,……,∨,A,n,(n 1),,其中,A,1,，,A,2,，……，,A,n,都是,简单合取式,如:,┐P∨,(,P∧Q) ∨ (P∧┐Q∧R),12,,二、析取范式与合取范式,,任何命题公式都可以化成与其等价的析取范式或合取范式。

求析取范式和合取范式的步骤如下：,,⑴,,消去联结词,“,→,”,和,“,↔,”，化归成,∧、∨、 ┐,,,P,→,Q,,┐P ∨Q,,P,↔,Q,,(P,∧Q) ∨(┐P ∨ ┐Q),,,,(,P,→,Q) ∧(Q,→,P),(,┐P ∨Q) ∧(┐ Q ∨,,P),,,,,(2),利用双重否定律消去否定联结词,“,¬,”,或利用德摩根律将否定联结词,“,¬,”,移到各命题变元前,(¬,内移,),,,,⑶利用分配律、结合律将公式归约为合取范式或析取范式P,∧(Q,,∨R),?,13,,二、析取范式与合取范式,,例：,求命题公式,(,P,∨,Q)↔P,的合取范式和析取范式解：,,,⑴,求合取范式,,,(,P,∨,Q,)↔,P,,,((,P,∨,Q,)→,P,)∧(,P,→(,P,∨,Q,)) (,消去↔),,,(,¬,(,P,∨,Q,)∨,P,)∧(,¬,P,∨(,P,∨,Q,)) (,消去→),,,((,¬,P,∧,¬,Q,)∨,P,)∧(,¬,P,∨(,P,∨,Q,)) (,,内移),,,(,¬,P,∨,P,)∧(,¬,Q,∨,P,)∧(,¬,P,∨,P,∨,Q,) (,分配律，,合取范式,),,,,1∧(,¬,Q,∨,P,)∧(1∨,Q,),,,1∧(,¬,Q,∨,P,)∧1 (,零律，,合取范式,),,,(,¬,Q,∨,P,),(,同一律,，,合取范式,),,,*由此例可以看出，公式的合取范式并不惟一。

14,,二、析取范式与合取范式,,⑵求析取范式,,(,P,∨,Q,)↔,P,,,,((,P,∨,Q,),∧,P,),∨,(¬(,P,∨,Q,),∧,¬,P,) (,消去,↔),,,,((,P,∨,Q,),∧,P,),∨,((¬,P,∧,¬,Q,),∧,¬,P,) (,,内移,),,,P,∨,(¬,P,∧,¬,Q,∧,¬,P,) (,吸收律,，,析取范式,),,,P,∨,(¬,P,∧,¬,P,∧,¬,Q,) (,交换律,),,,P,∨,(¬,P,∧,¬,Q,) (,幂等律,，,析取范式,),,,,*由此例可以看出，命题公式的析取范式也不惟一15,,三、主析取范式,,上述范式不唯一，下面追求一种更严格的范式,--,主范式,，它是存在且唯一的定义1-7.4,,n,个命题变元的合取式,，,称作,布尔合取、小项或极小项,其中每个变元与它的否定不能同时存在,，但两者,必须出现且仅出现一次,如：,P，Q,的构成的极小项为：,,P∧Q，P∧¬Q，¬P∧Q，¬P∧¬Q,,,练习：写出三个命题变元,P、Q、R,构成的极小项。

16,,三、主析取范式,,由于每个命题变项在极小项中以原形或否定式形式出现且仅出现一次，因而,n,个命题变项,共可产生2,n,个不同的极小项其中没有两个极小项是相等价的，,每个极小项都有且仅有一个成真指派,以成真指派所对应的二进制数,，,就可将所对应,极小项记作,m,i,,（,其中,i,为相应的二进制符号串）,17,,三、主析取范式,,两个命题变元的真值表、极小项、成真赋值,和符号标记如下：,真值表,,,P,,,Q,,,P,∧,Q,,,P,∧¬,Q,,,¬,P,∧,Q,,,¬,P,∧¬,Q,,,0,,,0,,,0,,,0,,,0,,,1,,,0,,,1,,,0,,,0,,,1,,,0,,,1,,,0,,,0,,,1,,,0,,,0,,,1,,,1,,,1,,,0,,,0,,,0,,两个命题变元的极小项,,极小项,,成真赋值,,记作,,,¬,P,∧¬,Q,,,00,,,m,00,,,¬,P,∧,Q,,,01,,,m,01,,,P,∧¬,Q,,,10,,,m,10,,,P,∧,Q,,,11,,,m,11,,18,,三、主析取范式,,,,,,,,,,,*,可以看出，极小项与成真赋值的对应关系为：变元对应,1,，而变元的否定对应,0,。

三个命题变元的极小项,,极小项,,,成真赋值,,,记作,,,¬,P,∧¬,Q,∧¬,R,,,000,,,m,000,,,¬,P,∧¬,Q,∧,R,,,001,,,m,001,,,¬,P,∧,Q,∧¬,R,,,010,,,m,010,,,¬,P,∧,Q,∧,R,,,011,,,m,011,,,P,∧¬,Q,∧¬,R,,,100,,,m,100,,,P,∧¬,Q,∧,R,,,101,,,m,101,,,P,∧,Q,∧¬,R,,,110,,,m,110,,,P,∧,Q,∧,R,,,111,,,m,111,,19,,三、主析取范式,,极小项有如下几个性质：,,（1）每一个极小项当其真值指派与编码相同时，其真值为1，其它2,n,-1,指派情况下均为02）,任意两个不同极小项的合取式永假例如：,,,,m,001,∧,m,100,,(,¬,P,∧,¬,Q,∧,R,)∧(,P,∧,¬,Q,∧,¬,R,),,,¬,P,∧,¬,Q,∧,R,∧,P,∧,¬,Q,∧,¬,R,,0,,（3）全体小项的析取式永为真记为：,,,20,,三、主析取范式,,定义1-7.5,对于给定的命题公式，如果有一个它的等价公式，仅由,极小项的析取,所组成，称该公式为原公式的,主析取范式,。

定理1-7.3,在真值表中，一个公式的真值,为,T,的指派所对应的极小项的析取,，即为此公式的主析取范式定理1-7.3的证明,P34,21,,三、主析取范式,,由定理1-7.3可知通过真值表求给定公式的主析取范式的步骤如下：,,（1）构造命题公式的真值表2）找出公式的成真赋值对应的极小项3）这些极小项的析取就是此公式的主析取范式例,用真值表法，求,(,P,→,Q,),→,R,的主析取范式22,,三、主析取范式,,解：,1.(,P→Q)→R,的真值表如下：,,,,,,,,,,,2.公式的成真赋值对应的极小项为：,¬,P,∧¬,Q,∧,R,(,成真赋值为001)、,,¬,P,∧,Q,∧,R,(,成真赋值为011)、,,P,∧¬,Q,∧¬,R,(,成真赋值为100)、,,,P,∧¬,Q,∧,R,(,成真赋值为101),、,P,∧,Q,∧,R,(,成真赋值为111),,,P,,,Q,,,R,,,P,→,Q,,,(,P,→,Q,),→,R,,,0,,,0,,,0,,,1,,,0,,,0,,,0,,,1,,,1,,,1,,,0,,,1,,,0,,,1,,,0,,,0,,,1,,,1,,,1,,,1,,,1,,,0,,,0,,,0,,,1,,,1,,,0,,,1,,,0,,,1,,,1,,,1,,,0,,,1,,,0,,,1,,,1,,,1,,,1,,,1,,23,,三、主析取范式,,3. (,P→Q)→R,的主析取范式为： (,P,∧,Q,∧,R,)∨(,P,∧¬,Q,∧,R,)∨(,P,∧¬,Q,∧¬,R,) ∨(¬,P,∧,Q,∧,R,)∨(¬,P,∧¬,Q,∧,R,),,,m,111,∨,m,101,∨,m,100,∨,m,011,∨,m,001,,,,m,7,∨,m,5,∨,m,4,∨,m,3,∨,m,1,,*,真值表成真指派中对变元的指派为0，对应的极小项中出现该命题变元的否定，若指派1则对应变元本身。

24,,三、主析取范式,,除了用真值表方法外，也可利用,等值演算法,求得给定命题公式的主析取范式，即用基本等价公式推出例题8：,用等价演算法求,(,P,∧,Q,),∨,(¬,P,∧,R,),∨,(,Q,∧,R,),的主析取范式解：,(,P,∧,Q,)∨(,¬,P,∧,R,)∨(,Q,∧,R,),,,(,P,∧,Q,∧(,R,∨,¬,R,))∨(,¬,P,∧,R,∧(,Q,∨,¬,Q,))∨(,Q,∧,R,∧(,P,∨,¬,P,)),,,(,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,)∨(,¬,P,∧,¬,Q,∧,R,),,,m,111,∨,m,110,∨,m,011,∨,m,001,,,例：,P,→,(P,∨,Q),,,┐,P,∨,P,∨,Q,,,,┐,P,∧,(,┐,Q,∨,Q),∨,P,∧,(,┐,Q,∨,Q),∨,(,┐,P,∨,P),∧,Q,,,(,┐,P,∧┐,Q),∨,(,┐,P,∧,Q),∨,(P,∧┐,Q),∨,(P,∧,Q),∨,(,┐,P,∧,Q),∨,(P,∧,Q),,,(,┐,P,∧┐,Q),∨,(,┐,P,∧,Q),∨,(P,∧┐,Q),∨,(P,∧,Q),,,m,0,∨,m,1,∨,m,2,∨,m,3,（永真）,,25,,三、主析取范式,,用等值演算法求主析取范式的步骤如下,：,,①,化归为析取范式。

②,除去析取范式中所有永假的析取项③,在析取式中，将重复出现的合取项和相同变 元合并④,对合取项补入没有出现的命题变元，即添加∧,(,P,∨,¬,P,),，,再用分配律展开，最后合并相同的极小项26,,四、主合取范式,,与主析取范式类似的是主合取范式,,定义1-7.6,,n,个命题变元的析取式,，,称作,布尔析取、大项或极大项,其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次如：,P，Q,构成的极大项为：,,,P∨Q，P∨¬Q，¬P∨Q，¬P∨¬Q,,,练习：写出三个命题变元,P、Q、R,构成的极大项27,,四、主合取范式,,与极小项类似地，,n,个命题变项,共可产生2,n,个极大项,，每个极大项只有,一个成假赋值,，将其对应的,二进制符号串,i,做极大项的角标，记作,M,i,（,其中,i,为相应的二进制符号串）,28,,四、主合取范式,,两个命题变元的极大项、成假赋值,和符号标记如下：,,,两个命题变元的极大项,,极大项,,,成假赋值,,,名称,,,P,∨,Q,,,00,,,M,00,,,P,∨¬,Q,,,01,,,M,01,,,¬,P,∨,Q,,,10,,,M,10,,,¬,P,∨¬,Q,,,11,,,M,11,,29,,四、主合取范式,,三个命题变元的极大项、成假赋值,和符号标记如下,：,,,,,,,,,,,,*可以看出，极大项与成假赋值的对应关系为：变元对应,0,，而变元的否定对应,1,。

三个命题变元的极大项,,极大项,,,成假赋值,,,名称,,,P,∨,Q,∨,R,,,000,,,M,000,,,P,∨,Q,∨¬,R,,,001,,,M,001,,,P,∨¬,Q,∨,R,,,010,,,M,010,,,P,∨¬,Q,∨¬,R,,,011,,,M,011,,,¬,P,∨,Q,∨,R,,,100,,,M,100,,,¬,P,∨,Q,∨¬,R,,,101,,,M,101,,,¬,P,∨¬,Q,∨,R,,,110,,,M,110,,,¬,P,∨¬,Q,∨¬,R,,,111,,,M,111,,30,,四、主合取范式,,极大项有如下几个性质：,,（1）每一个极大项当其真值指派与编码相同时，其真值为0，其它2,n,-1,指派情况下均为12）,任意两个不同的极大项的析取式为永真式3）,全体极大项的合取式为永假式记为：,,,M,0,∧,M,1,∧,…,∧,,,0,,31,,四、主合取范式,,定义1-7.7,,对于给定的命题公式，如果有一个它的等价公式，,仅由极大项的合取,组成，则该等价式称为原公式的,主合取范式,定理1-7.4,在真值表中，一个公式的真值为,F,的指派所对应的极大项的合取，即为此公式的主合取范式。

32,,四、主合取范式,,由定理1-7.4可知通过真值表求给定公式的主析取范式的步骤如下：,,（1）构造命题公式的真值表2）找出公式的成假赋值对应的极大项3）这些极大项的合取就是此公式的主合取范式例,用真值表法，求,(,P,→,Q,),→,R,的主合取范式,,33,,四、主合取范式,,解：,1.(,P→Q)→R,的真值表如下：,,,,,,,,,,,2.公式的成假赋值对应的极大项为：,P,∨,Q,∨,R,(,成假赋值为,000) 、,,P,∨¬,Q,∨,R,(,成假赋值为,010)、,¬,P,∨¬,Q,∨,R,(,成假赋值为,110),,3.,主合取范式为：,(,P,∨,Q,∨,R,),∧,(,P,∨,¬,Q,∨,R,),∧,(¬,P,∨,¬,Q,∨,R,),,,M,000,∧,M,010,∧,M,110,,M,0,∧,M,2,∧,M,6,,,P,,,Q,,,R,,,P,→,Q,,,(,P,→,Q,),→,R,,,0,,,0,,,0,,,1,,,0,,,0,,,0,,,1,,,1,,,1,,,0,,,1,,,0,,,1,,,0,,,0,,,1,,,1,,,1,,,1,,,1,,,0,,,0,,,0,,,1,,,1,,,0,,,1,,,0,,,1,,,1,,,1,,,0,,,1,,,0,,,1,,,1,,,1,,,1,,,1,,34,,四、主合取范式,,与求主析取范式相似，除了用真值表方法外，也可利用,等值演算法,求得给定命题公式的主合取范式。

其演算步骤如下：,,①化归为合取范式②除去所有永真的合取项③在合取式中合并重复出现的析取项和相同的变元④对析取项补入没有出现的命题变元即,增加∨(,P∧¬P),，,然后，应用分配律展开公式，最后合并相同的极大项35,,五、主析取范式与主合取范式的关系,我们今后可用,∑,表示,极小项的析取,，,∑,i,j,k,,即表示,m,i,∨,m,j,∨,m,k,,可用,∏,表示大项的合取,，,∏,i,j,k,即表示,M,i,∧,M,j,∧,M,k,,例如：,,(,p,∧,q,∧,r,)∨(,p,∧¬,q,∧,r,)∨(,p,∧¬,q,∧¬,r,)∨(¬,p,∧,q,∧,r,)∨(¬,p,∧¬,q,∧,r,),,m,111,∨,m,101,∨,m,100,∨,m,011,∨,m,001,,∑,1，3，4，5，7,,(p∨q∨r)∧(p∨¬q∨r)∧(¬p∨¬q∨r),,,,M,000,∧,M,010,∧,M,110,,∏,0，2，6,,,36,,五、主析取范式与主合取范式的关系,可以证明如果命题公式,P,的主析取范式为,,∑,i,1,,,i,2,,…,i,k,，,,则,P,的主合取范式为：,,,∏0,1,2,…,i,1,-1,,i,1,+1,,…,i,k,-1,,,i,k,+1,,… ,,2,n,-1,,例：,,(,P,→Q)→Q,,∑1，3，4，5，7,,∏0，2，6,,,,,37,,内容小结,,对偶式与对偶原理,,析取范式与合取范式,,主析取范式,,主合取范式,,主析取范式与主合取范式的关系,38,,课后作业,,P39 （4）a,c,e,f (可用真值表法或等值演算法),39,,。