離散數學-1-7 對偶與范式

《離散數學-1-7 對偶與范式》由會員分享，可在線閱讀，更多相關《離散數學-1-7 對偶與范式（39頁珍藏版）》請在裝配圖網上搜索。

1、,單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,*,第一章 命題邏輯,1-7 對偶與范式,1,盡管命題公式的最小聯結詞組可為，但實際上一般出于方便的目的，命題公式常常包含，。,從第15頁的表1-4.8的命題定律中可以看出，很多常用等價式是成對出現的，只要將其中的“和“分別換成“和“，就可以由一個得到另一個。,例如，將命題定律(PQ)RP(QR)中的“換成“就得到了命題定律(PQ)RP(QR)。這些成對出現的等價式反映了等價的對偶性。我們將這樣的公式稱作具有對偶規(guī)律。,本節(jié)將先介紹對偶式和對偶原理。,2,一、對偶式與對偶原理,定義1-7.1 在給定的命題

2、公式A中，將聯結詞、分別換成、，假設有特殊變元F和T亦相互對代，所得的公式稱為公式A的對偶式，記為A*。,*設A*是A的對偶式，將A*中的，F，T分別換成，T，F，就會得到A。即A是A*的對偶式，(A*)*A。所以說A*和A互為對偶式。,例題1 寫出以下表達式的對偶式,1.PQR,2.P QT,3.PQ PQ S,3,一、對偶式與對偶原理,例題2 求,PQ,和,PQ,的對偶式。,解,：,P,Q,(,P,Q,),(,P,Q,),的對偶式是,(,P,Q,),P,Q,故,P,Q,的對偶式是,P,Q,；,同樣的方法可以證明,P,Q,的對偶式是,P,Q,。,注意：,根據例題2，,對偶式概念可以推廣為,：

3、在僅含有聯結詞，的命題公式中，將聯結詞，,F,，,T,分別換成，,T,，,F,，,就得到了它的對偶式。,4,一、對偶式與對偶原理,*關于對偶式有以下兩個結論。,定理1-7.1 設A*是A的對偶式，P1，P2，Pn是出現在A和A*中的原子變元，那么,A(P1，P2，Pn)A*(P1，P2，Pn),A(P1，P2，Pn)A*(P1，P2，Pn),證明見P30：由德摩根律層層置換，即可層層推出。,5,一、對偶式與對偶原理,例：,設命題公式,A,(,P,Q,R,),(,P,Q,),R,，,試用此公式驗證定理的有效性。,證明：,驗證,A,(,P,Q,R,),A,*(,P,Q,R,),A,(,P,Q,R,

4、),(,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 設P1，P2，Pn是出現在公式A和B中的所有原子變元，如果AB，那么A*B*。,證明：,因為 AB,所以 A(P1，P2，Pn)B(P1，P2，Pn)是重言式,根據定

5、理1-5.2(P19)，在上述重言式中用Pi置換 Pi，,i1,n，所得的公式仍為重言式，即,A(P1，P2，Pn)B(P1，P2，Pn)是重言,式。,所以 A(P1，P2，Pn)B(P1，P2，Pn),由定理1-7.1A*(P1，P2，Pn)B*(P1，P2，Pn),即 A*B*,因此 A*B*,*定理1.7.2叫做對偶原理。對偶原理是數理邏輯中最根本的規(guī)律之一。,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

6、),而 P(Q(R P)(P(Q(RP),故 P(Q(R P)(P(Q(RP),使用真值表和對偶原理可以簡化或推證一些命題公式。,8,一、對偶式與對偶原理,例,：,證明,重言式的對偶式是矛盾式，矛盾式的對偶式是重言式。,證明,：,設,A,是重言式，即,A,T,，,因為,T,的對偶式是,F,，,由對偶原理知,A,*,F,。,所以,A,*,是矛盾式；,設,A,是矛盾式，即,A,F,，,而,F,的對偶式是,T,，所以,A,*,T,。,所以,A,*,是重言式。,9,二、析取范式與合取范式,每種數字標準形都能提供很多信息，如代數式的因式分解可判斷代數式的根情況。邏輯公式在等值演算下也有標準形-范式，范式

7、有兩種：析取范式和合取范式。,同一命題公式可以有各種相互等價的表達形式，范式可以實現命題公式的標準化,10,二、析取范式與合取范式,定義補充僅有有限個命題變元或其否認構成的合(析)取式稱作簡單合(析)取式。,如：,P,Q等為一個文字(一個命題變元或它的否認稱為文字)構成的簡單合取式，PP，PQ等為2個文字構成的簡單合取，PQR,PPQ等為3個文字構成的簡單合取式,P,Q等為一個文字一個變元或變元的否認的簡單析趨式，PP，PQ等為2個變元或變元的否認簡單析取式，PQR,PQR等為3個文字構成的簡單析取式。,11,二、析取范式與合取范式,定義1-7.2,一個命題公式稱為,合取范式,，當且僅當它具有

8、形式：,A,1,A,2,A,n,(n 1),其中,A,1,，,A,2,，,A,n,都是,簡單析取式,。,如:(,PQR),(,PQ),Q,定義1-7.2,一個命題公式稱為,析取范式,，當且僅當它具有形式：,A,1,A,2,A,n,(n 1),其中,A,1,，,A,2,，,A,n,都是,簡單合取式,。,如:,P,(,PQ)(PQR),12,二、析取范式與合取范式,任何命題公式都可以化成與其等價的析取范式或合取范式。求析取范式和合取范式的步驟如下：,消去聯結詞“和“，化歸成、,P Q P Q,P Q(P Q)(P Q),(P Q)(Q P)(P Q)(Q P),(2)利用雙重否認律消去否認聯結詞“

9、或利用德摩根律將否認聯結詞“移到各命題變元前(內移),利用分配律、結合律將公式歸約為合取范式或析取范式。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,),(,同一律,，,

10、合取范式,),*由此例可以看出，公式的合取范式并不惟一。,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個命題變元的合取式，稱作布爾合取、小項或極小項。其中每個變元與它

11、的否認不能同時存在，但兩者必須出現且僅出現一次。,如：P，Q的構成的極小項為：,PQ，PQ，PQ，PQ,練習：寫出三個命題變元P、Q、R構成的極小項。,16,三、主析取范式,由于每個命題變項在極小項中以原形或否認式形式出現且僅出現一次，因而n個命題變項共可產生2n個不同的極小項。其中沒有兩個極小項是相等價的，每個極小項都有且僅有一個成真指派。以成真指派所對應的二進制數，就可將所對應極小項記作mi,其中i為相應的二進制符號串。,17,三、主析取范式,兩個命題變元的真值表、極小項、成真賦值,和符號標記如下：,真值表,P,Q,P,Q,P,Q,P,Q,P,Q,0,0,0,0,0,1,0,1,0,0,1

12、,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

13、,三、主析取范式,極小項有如下幾個性質：,1每一個極小項當其真值指派與編碼相同時，其真值為1，其它2n-1指派情況下均為0。,2任意兩個不同極小項的合取式永假。,例如：,m001m100(PQR)(PQR),PQRPQR0,3全體小項的析取式永為真。記為：,20,三、主析取范式,定義1-7.5,對于給定的命題公式，如果有一個它的等價公式，僅由,極小項的析取,所組成，稱該公式為原公式的,主析取范式,。,定理1-7.3,在真值表中，一個公式的真值,為,T,的指派所對應的極小項的析取,，即為此公式的主析取范式。,定理1-7.3的證明,P34,21,三、主析取范式,由定理1-7.3可知通過真值表求給定

14、公式的主析取范式的步驟如下：,1構造命題公式的真值表。,2找出公式的成真賦值對應的極小項。,3這些極小項的析取就是此公式的主析取范式。,例 用真值表法，求(PQ)R的主析取范式。,22,三、主析取范式,解：,1.(,PQ)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,

15、0,1,1,0,1,0,1,1,1,0,1,0,1,1,1,1,1,23,三、主析取范式,3.(PQ)R的主析取范式為：(PQR)(PQR)(PQR)(PQR)(PQR),m111m101m100m011m001,m7m5m4m3m1,*真值表成真指派中對變元的指派為0，對應的極小項中出現該命題變元的否認，假設指派1那么對應變元本身。,24,三、主析取范式,除了用真值表方法外，也可利用等值演算法求得給定命題公式的主析取范式，即用根本等價公式推出。,例題8：用等價演算法求(PQ)(PR)(QR)的主析取范式。,解：(PQ)(PR)(QR),(PQ(RR)(PR(QQ)(QR(PP),(PQR)(

16、PQR)(PQR)(PQR),(PQR)(PQR),(PQR)(PQR)(PQR)(PQR),m111m110m011m001,例：P(PQ)PPQ,P(QQ)P(QQ)(PP)Q,(PQ)(PQ)(PQ)(PQ)(PQ)(PQ),(PQ)(PQ)(PQ)(PQ),m0m1m2m3 永真,25,三、主析取范式,用等值演算法求主析取范式的步驟如下,：,化歸為析取范式。,除去析取范式中所有永假的析取項。,在析取式中，將重復出現的合取項和相同變 元合并。,對合取項補入沒有出現的命題變元，即添加,(,P,P,),，,再用分配律展開，最后合并相同的極小項。,26,四、主合取范式,與主析取范式類似的是主合取范式,定義1-7.6 n個命題變元的析取式，稱作布爾析取、大項或極大項。其中每個變元與它的否認不能同時存在，但兩者必須出現且僅出現一次。,如：P，Q構成的極大項為：,PQ，PQ，PQ，PQ,練習：寫出三個命題變元P、Q、R構成的極大項。,27,四、主合取范式,與極小項類似地，n個命題變項共可產生2n個極大項，每個極大項只有一個成假賦值，將其對應的二進制符號串i做極大項的角標，記作Mi 其中i為相