離散數(shù)學(xué)(第二章)

1、離散數(shù)學(xué)許雷（數(shù)學(xué)與信息科學(xué)學(xué)院）郵箱：）電話：180802219261.3 命題公式的等值式定義定義1: 給定兩個(gè)命題公式給定兩個(gè)命題公式A和和B，設(shè)，設(shè)P1 ,P2 ,Pn為出現(xiàn)于為出現(xiàn)于A和和B中的所有原子變元中的所有原子變元,若給若給P1 , P2 ,Pn任一組真值指派任一組真值指派, A和和B的真值的真值都相同都相同,則稱則稱A和和B是等價(jià)的或邏輯相等是等價(jià)的或邏輯相等.記作記作A B。1.3 命題公式的等值式注注: (1) “ ”不是邏輯聯(lián)結(jié)詞不是邏輯聯(lián)結(jié)詞.(2)命題公式之間的邏輯相等關(guān)系具有命題公式之間的邏輯相等關(guān)系具有： 自反性：自反性：A A ； 對稱性：若對稱性：若A B

2、，則，則B A； 傳遞性：若傳遞性：若A B且且B C，則，則A C。1.3 命題公式的等值式證明公式等價(jià)的方法：證明公式等價(jià)的方法：1. 真值表法真值表法 2. 等值演算法等值演算法1. 真值表法真值表法 例例1.1.111 1111 0110 1110 0 Q QPPP Q 1.3 命題公式的等值式例例2. 證明證明: PQ (PQ) (QP)PQ PQ QP PQ (PQ) (QP)0 00 00 01 11 10 01 11 11.3 命題公式的等值式例例2. 證明證明: PQ (PQ) (QP)PQ PQ QP PQ (PQ) (QP)0 00 01 11 11 11 10 01 1

3、0 00 01 10 01 10 00 01 10 00 01 11 11 11 11 11 11.3 命題公式的等值式例例3：判斷公式判斷公式 P(QR)、(PQ)R是否等價(jià)是否等價(jià)P Q RPQQRP(QR)(PQ)R00001001010100001101100011010111010111111.3 命題公式的等值式P Q RPQQRP(QR)(PQ)R00001110010111010001101101111000111101011111010001111111例例3：判斷公式判斷公式 P(QR)、(PQ)R是否等價(jià)是否等價(jià)1.3 命題公式的等值式2. 等值演算法等值演算法(Equi

4、valent Calculation) 等值演算中使用的一條重要規(guī)則：等值演算中使用的一條重要規(guī)則：置換規(guī)則置換規(guī)則定義定義2 (子公式子公式)：如果如果X是是wff A的一部分的一部分,且且X本身也是本身也是wff，則稱，則稱X是是A的子公式。例如的子公式。例如, P (P Q)為為Q (P (P Q)的子公式。的子公式。1.3 命題公式的等值式(置換定理置換定理Axiom of rePlacement) 設(shè)設(shè)X是是wff A的子的子wff，若，若XY，則若將，則若將A中的中的X用用Y來置換，所得公式來置換，所得公式B與與A等價(jià)，即等價(jià)，即AB。證：證：因?yàn)閷ψ冊娜我恢概梢驗(yàn)閷ψ冊娜我恢?/p>

5、派,X與與Y真值相同，真值相同，所以所以Y取代取代X后，公式后，公式B與公式與公式A對變元的任對變元的任一指派真值也相同一指派真值也相同,所以所以AB。1.3 命題公式的等值式注注: : 滿足滿足置換定理置換定理的條件的置換稱為等價(jià)置的條件的置換稱為等價(jià)置 換換(或等價(jià)代換或等價(jià)代換).定義定義2( (等值演算等值演算) )：根據(jù)已知的等價(jià)公式根據(jù)已知的等價(jià)公式, ,推演出另外一些等價(jià)公式的過程稱為推演出另外一些等價(jià)公式的過程稱為等值演等值演算算.1.3 命題公式的等值式v常用的等價(jià)式：常用的等價(jià)式： 1.雙重否定律雙重否定律： P P 2.結(jié)合律：結(jié)合律：(P Q) RP (Q R) (P

6、Q) RP (Q R) (PQ)RP(QR) 3.交換律交換律: P QQ P P Q Q P PQ QP 4. 分配律分配律: P (Q R )(P Q) (P R) P (Q R)(P Q) (P R)1.3 命題公式的等值式v常用的等價(jià)式：常用的等價(jià)式： 5.冪等律冪等律: : P P P P P P 6.吸收律吸收律: P (P Q) P P (P Q) P 7.德德.摩根律摩根律: (P Q)P Q (P Q)P Q 8.同一律同一律: P 0P P 1P 9.零律零律: P 11 P 001.3 命題公式的等值式v常用的等價(jià)式：常用的等價(jià)式： 10.否定律否定律： P P1 P P

7、0 11. 蘊(yùn)涵等值式蘊(yùn)涵等值式: : PQ P Q 12. 等價(jià)等值式等價(jià)等值式: PQ(PQ) (QP) 13. 假言易位假言易位: PQQ P 14. 等價(jià)否定等值式等價(jià)否定等值式: PQPQ 15. 歸謬論歸謬論: (PQ ) ( PQ)P 1.3 命題公式的等值式其中其中P, Q, R等代表任意命題公式等代表任意命題公式. 這樣上面的這樣上面的每一個(gè)公式都是一個(gè)模式每一個(gè)公式都是一個(gè)模式, 它可以代表無數(shù)多它可以代表無數(shù)多個(gè)同類型的命題公式個(gè)同類型的命題公式. 例如例如, P P1 中中, 用用(P Q)置換置換P,則得則得 (P Q) (P Q)1 ,用用P置換置換P,則得則得 (

8、P) (P)1 。1.3 命題公式的等值式例例1 1： 證明證明 Q(P (P Q)QP證證: Q(P (P Q) QP P(吸收律吸收律)例例2： 證明證明 (P Q) QP Q證：證：(P Q) Q(P Q) (Q Q)(P Q) T P Q1.3 命題公式的等值式例例3：證明：證明(PQ)(Q R) P Q R證：證：(PQ)(Q R) (P Q)(Q R) (P Q) (Q R) (P Q) (Q R) (P Q R) (Q Q R) P Q R 1.3 命題公式的等值式例例4：驗(yàn)證驗(yàn)證P(QR) (PQ)R證證: 右右(PQ)R PQR P(QR) P(QR) P(QR)練：練：1.

9、(PQ)(PR)P(QR) 2.(PQ)(PQ)(PQ)(PQ) 1.3 命題公式的等值式等值演算的應(yīng)用：等值演算的應(yīng)用： 1.驗(yàn)證等值式驗(yàn)證等值式 2.判定公式的類型（判定公式的類型（p23,例例2.5） 3.解決工作生活中的判斷問題解決工作生活中的判斷問題例例5：甲、已、丙甲、已、丙3人根據(jù)口音對王教授是哪人人根據(jù)口音對王教授是哪人進(jìn)行了判斷：進(jìn)行了判斷： 甲說：王教授不是蘇州人，是上海人甲說：王教授不是蘇州人，是上海人 已說：王教授不是上海人，是蘇州人已說：王教授不是上海人，是蘇州人 丙說：王教授既不是上海人，也不是杭州人丙說：王教授既不是上海人，也不是杭州人結(jié)果結(jié)果3人中有一人全對，一

10、人對一半，一人全錯(cuò)。人中有一人全對，一人對一半，一人全錯(cuò)。問王教授是哪人？問王教授是哪人？1.4 析取范式與合取范式定義定義1: (1)文字文字：命題變元及其否定統(tǒng)稱為文字：命題變元及其否定統(tǒng)稱為文字(如如P , P). (2)簡單析取式簡單析取式：僅有有限個(gè)文字組成的析取式。：僅有有限個(gè)文字組成的析取式。 如如:P，P Q，P P，Q P P，P Q R S.(3)簡單合取式簡單合取式：僅有有限個(gè)文字組成的合取式。：僅有有限個(gè)文字組成的合取式。 如如:P, Q , Q P，P P，Q P P, P Q R.注意：注意：單個(gè)文字既是簡單析取式又是簡單合取式單個(gè)文字既是簡單析取式又是簡單合取式從

11、定義不難看出從定義不難看出:定理定理1：（1）一個(gè)簡單析取式是）一個(gè)簡單析取式是重言式重言式當(dāng)且僅當(dāng)它同當(dāng)且僅當(dāng)它同時(shí)含有某個(gè)時(shí)含有某個(gè)命題變元及其否定式命題變元及其否定式。（2）一個(gè)簡單合取式是）一個(gè)簡單合取式是矛盾式矛盾式當(dāng)且僅當(dāng)它同當(dāng)且僅當(dāng)它同時(shí)含有某個(gè)時(shí)含有某個(gè)命題變元及其否定式命題變元及其否定式。1.4 析取范式與合取范式 定義定義2: (1)析取范式析取范式：一個(gè)命題公式稱為：一個(gè)命題公式稱為析取范式析取范式,當(dāng)且當(dāng)且僅當(dāng)它具有形式僅當(dāng)它具有形式: A1A2An (n大于等于1)其中其中Ai(i=1,2,3,n)為簡單合取式為簡單合取式.如：如：PQ ，(PQ)(PQR), QP.

12、 (2)合取范式合取范式：一個(gè)命題公式稱為：一個(gè)命題公式稱為合取范式合取范式,當(dāng)且當(dāng)且僅當(dāng)它具有形式僅當(dāng)它具有形式: A1A2An (n大于等于1)其中其中Ai(i=1,2,3,n)為簡單析取式為簡單析取式.如：如：P Q ，(PQ)(PQR), QP.1.4 析取范式與合取范式(3)范式范式：析取范式與合取范式統(tǒng)稱為：析取范式與合取范式統(tǒng)稱為范式范式。顯然顯然, 任何合任何合(析析)取范式的對偶式是析取范式的對偶式是析(合合)取范式取范式.析取范式與合取范式的性質(zhì)析取范式與合取范式的性質(zhì): :定理定理2 2：(1) (1) 一個(gè)析取范式是矛盾式一個(gè)析取范式是矛盾式, ,當(dāng)且僅當(dāng)它的每當(dāng)且僅當(dāng)

13、它的每 一個(gè)簡單合取式都是矛盾式一個(gè)簡單合取式都是矛盾式; ;(2)(2)一個(gè)合取范式是重言式一個(gè)合取范式是重言式, ,當(dāng)且僅當(dāng)它的每當(dāng)且僅當(dāng)它的每 一個(gè)簡單析取式都是重言式一個(gè)簡單析取式都是重言式. .1.4 析取范式與合取范式定理定理3 (范式存在定理范式存在定理)任一個(gè)命題公式都存在著與之等價(jià)的析取范式與任一個(gè)命題公式都存在著與之等價(jià)的析取范式與合取范式。合取范式。1.4 析取范式與合取范式求命題公式的范式的基本步驟求命題公式的范式的基本步驟：1.4 析取范式與合取范式（）利用等價(jià)公式：化去（）利用等價(jià)公式：化去“”、“”聯(lián)聯(lián)結(jié)詞，把命題公式變?yōu)榕c其等價(jià)的用結(jié)詞，把命題公式變?yōu)榕c其等價(jià)的

14、用，表達(dá)的公式。表達(dá)的公式。 例例: ， （）（） （）（）（）將（）將“”深入到原子命題變元之前，并使深入到原子命題變元之前，并使變元之前最多只有一個(gè)變元之前最多只有一個(gè)“”詞。詞。例：例：（） 1.4 析取范式與合取范式（）利用（）利用對對的分配，將公式化為析取的分配，將公式化為析取范式，求合取范式利用范式，求合取范式利用對對 的分配的分配 。（）除去永假項(xiàng)得最簡析取范式與合取范（）除去永假項(xiàng)得最簡析取范式與合取范式。式。例：求（例：求（ ） R R的合取范式的合取范式 解：原式解：原式 （ ） R R （消去（消去 ） 1.4 析取范式與合取范式 （ ） R R） （R R （ ） （消

15、去消去） （ ） R R ） （ R R （ ） （消去（消去 ） （ ） R R ） （ P P R R ）（否定內(nèi)移（否定內(nèi)移 ）（ R R ） （ R R ） （ P P R R ）（ 對或?qū)虻姆峙涞姆峙?）1.4 析取范式與合取范式例：求（例：求（ ） R R的析取范式的析取范式 解：原式解：原式 （ ） R R （消去（消去) （ ） R R ） （ P P R R ） （否定內(nèi)移（否定內(nèi)移 ） （ P P ） （ ） （ R R ） （R R P P） （R R ） （R R R R ） （ R R ） （ R R P P） （R R ）（ 對對的分配）的分配）1.4 析取范式與

16、合取范式注意注意：（1）單個(gè)命題變元既是簡單合取式，又是單個(gè)命題變元既是簡單合取式，又是簡單析取式；公式簡單析取式；公式PQR既可以看成是既可以看成是三個(gè)簡單析取式構(gòu)成的合取范式，也可以三個(gè)簡單析取式構(gòu)成的合取范式，也可以看成是析簡單合取式構(gòu)成的析取范式?？闯墒俏龊唵魏先∈綐?gòu)成的析取范式。（2）一個(gè)命題公式的析一個(gè)命題公式的析(合合)取范式不是唯一取范式不是唯一的。的。1.4 析取范式與合取范式 例例1：求：求(P Q)R)P的析取范式與合取范式的析取范式與合取范式 解解: 原式原式(PQ)R)P(PQ )R)P(PR )(QR)P (析取范式析取范式)P(PR )(QR)P(QR) (析取范

17、式析取范式)(PQ P )(RP ) (合取范式合取范式)(PQ)(RP ) (合取范式合取范式)1.4 析取范式與合取范式 例例2：求：求(P Q) R的析取范式與合取范式的析取范式與合取范式 解解: 原式原式(PQ) R)(R(PQ) )(PQ)R)(R (PQ) )(PQ)R)(RPQ )(P Q)R)(RPQ )(PR)(QR)(RPQ ) (合取范式合取范式)(PQ)(RPQ ) )(R (RPQ )(PQR)(RP)(RQ) (析取范式析取范式)1.4 析取范式與合取范式命題公式的主析命題公式的主析(合合)取范式取范式(由于一個(gè)命題公式的析由于一個(gè)命題公式的析(合合)取范式不是唯一

18、取范式不是唯一, 因而它們不能作為命題公式的規(guī)范形式因而它們不能作為命題公式的規(guī)范形式(標(biāo)準(zhǔn)形標(biāo)準(zhǔn)形式式), 為了使任意命題公式化為唯一的標(biāo)準(zhǔn)形式為了使任意命題公式化為唯一的標(biāo)準(zhǔn)形式, 下下面引入主范式的概念面引入主范式的概念.1.4 析取范式與合取范式1.命題公式的主析取范式命題公式的主析取范式定義定義3：在含有在含有n個(gè)命題變元的個(gè)命題變元的簡單合取簡單合取式中式中,若每個(gè)命題變元和它的否定不同時(shí)出現(xiàn)，而二者若每個(gè)命題變元和它的否定不同時(shí)出現(xiàn)，而二者之一必出現(xiàn)且僅出現(xiàn)一次，稱這樣的之一必出現(xiàn)且僅出現(xiàn)一次，稱這樣的簡單合取簡單合取式式為為小項(xiàng)小項(xiàng).例如例如,三個(gè)命題變元三個(gè)命題變元P,Q,R

19、,其小項(xiàng)共有其小項(xiàng)共有8個(gè)個(gè):1.4 析取范式與合取范式 小項(xiàng)小項(xiàng) 編碼編碼 真值指派真值指派 小項(xiàng)的真值小項(xiàng)的真值 P Q R m000/ m0 000 1 P Q R m001/m1 001 1 P Q R m010/m2 010 1 P Q R m011/m3 011 1 P Q R m100/m4 100 1 P Q R m101/m5 101 1 P Q R m110/m6 110 1 P Q R m111/m7 111 11.4 析取范式與合取范式考慮：考慮：n個(gè)命題變元可產(chǎn)生多少個(gè)小（個(gè)命題變元可產(chǎn)生多少個(gè)?。ù蟠螅╉?xiàng)？）項(xiàng)？ n個(gè)變元的小項(xiàng)個(gè)變元的小項(xiàng): m0 P1 P2 .

20、Pn m1 P1 P2 . Pn m2n-1P1 P2 . Pn1.4 析取范式與合取范式極小項(xiàng)的性質(zhì)極小項(xiàng)的性質(zhì):沒有兩個(gè)小項(xiàng)是等價(jià)的沒有兩個(gè)小項(xiàng)是等價(jià)的, 且每個(gè)極小項(xiàng)有且且每個(gè)極小項(xiàng)有且僅有一個(gè)成真賦值，若成真賦值所對應(yīng)的二僅有一個(gè)成真賦值，若成真賦值所對應(yīng)的二進(jìn)制數(shù)轉(zhuǎn)化為十進(jìn)制數(shù)為進(jìn)制數(shù)轉(zhuǎn)化為十進(jìn)制數(shù)為i，就將所對應(yīng)的，就將所對應(yīng)的極小項(xiàng)記作極小項(xiàng)記作mi。(2) 任意兩個(gè)不同的極小項(xiàng)的合取為矛盾式任意兩個(gè)不同的極小項(xiàng)的合取為矛盾式.(3) 全體極小項(xiàng)的析取為永真式全體極小項(xiàng)的析取為永真式.1.4 析取范式與合取范式定義定義4：設(shè)命題公式設(shè)命題公式A中含有中含有n個(gè)命題變元個(gè)命題變元,

21、 如果如果A的的析析取范式中，所有的取范式中，所有的簡單合取簡單合取式都是式都是極小項(xiàng)極小項(xiàng)，則稱該，則稱該析取析取范式范式為為A的主析取的主析取范式范式。定理定理4:任何命題公式都存在著與之等價(jià)的主任何命題公式都存在著與之等價(jià)的主析取范式，并且是唯一的。析取范式，并且是唯一的。求主析取范式的方法求主析取范式的方法：真值表；等值演算發(fā)：真值表；等值演算發(fā)1.4 析取范式與合取范式真值表法：真值表法：在真值表中，一個(gè)公式的真值為在真值表中，一個(gè)公式的真值為1的指派所對的指派所對應(yīng)的極小項(xiàng)的析取，即為公式的主析取范式應(yīng)的極小項(xiàng)的析取，即為公式的主析取范式例：求出例：求出、 （）、）、的主析取范式的

22、主析取范式1.4 析取范式與合取范式例：求出例：求出、 （）、）、的主析取范式的主析取范式100111011101101010101100（）1.4 析取范式與合取范式則可直接寫出各命題公式的主析取范式：則可直接寫出各命題公式的主析取范式：（ ）（ ）（）（）（）（）（）（）（）（）（）1.4 析取范式與合取范式（1）只要命題公式不是永假式，則一定可以根）只要命題公式不是永假式，則一定可以根據(jù)該命題公式的真值表直接寫出其主析取范式據(jù)該命題公式的真值表直接寫出其主析取范式，其方法是找出該公式為，其方法是找出該公式為1的行，對應(yīng)寫出極的行，對應(yīng)寫出極小項(xiàng)的析取式，且一定是唯一的。小項(xiàng)的析取式，且一

23、定是唯一的。（2）若命題公式是含有）若命題公式是含有n個(gè)變元的永真式，則個(gè)變元的永真式，則它的主析取范式一定含有它的主析取范式一定含有2n個(gè)極小項(xiàng)。個(gè)極小項(xiàng)。（3）若二個(gè)命題公式對應(yīng)的主析取范式相同，）若二個(gè)命題公式對應(yīng)的主析取范式相同，則此二個(gè)命題公式一定是等價(jià)的。則此二個(gè)命題公式一定是等價(jià)的。（4）命題公式的主析取范式中極小項(xiàng)的個(gè)數(shù)一）命題公式的主析取范式中極小項(xiàng)的個(gè)數(shù)一定等于對應(yīng)真值表中真值為定等于對應(yīng)真值表中真值為1的個(gè)數(shù)。的個(gè)數(shù)。1.4 析取范式與合取范式等值演算法等值演算法：下面介紹不用真值表，直接求命題公式主析取范下面介紹不用真值表，直接求命題公式主析取范式的方法，分四步：式的方

24、法，分四步：（）將命題公式化歸為與其等價(jià)的析取范式；（）將命題公式化歸為與其等價(jià)的析取范式； （）除去永假項(xiàng)，合并基本積中相同項(xiàng)例：（）除去永假項(xiàng)，合并基本積中相同項(xiàng)例：），變?yōu)樽詈單鋈》妒?。），變?yōu)樽詈單鋈》妒?。（）利用添變元的方法，將所有基本積變?yōu)闃O（）利用添變元的方法，將所有基本積變?yōu)闃O小項(xiàng)。小項(xiàng)。1.4 析取范式與合取范式例：二個(gè)變元、，利用例：二個(gè)變元、，利用“”對或?qū)颉啊钡牡姆峙涮眄?xiàng)分配添項(xiàng)（） （）（） （） （）（）（）合并相同的極小項(xiàng)變?yōu)橐豁?xiàng)。（）合并相同的極小項(xiàng)變?yōu)橐豁?xiàng)。例：求（例：求（）的主析取范式的主析取范式解：原式解：原式（）（） -（1）化為析取范式）化為析取范式

25、 1.4 析取范式與合取范式 （） -（2）消去永假項(xiàng)，變?yōu)樽詈單鋈》妒剑┫ビ兰夙?xiàng)，變?yōu)樽詈單鋈》妒剑ǎǎǎǎǎ?-（3）添項(xiàng)）添項(xiàng)（）（） -（4）合并相同最小項(xiàng)）合并相同最小項(xiàng)1.4 析取范式與合取范式例例1：求：求(P Q)R)P的主析取范式的主析取范式。 解解: 原式原式(PQ)R)PP(QR) (析取范式析取范式)(P(QQ)(RR)(PP) (QR)(PQR)(PQR)(PQR) (PQR)(PQR)(PQR)(PQR)(PQR)(PQR) (PQR)(PQR) (主析取范式主析取范式)m7m6m5m4m2m2m4m5m6m71.4 析取范式與合取范式例例2：求：求(PQ

26、)R的主析取范式的主析取范式。解解:(PQR)(RP)(RQ) (析取范式析取范式)(PQR)(R P)(QQ) (PP) (RQ ) (PQR)(PQR)(PQR) (PQR)(PQR ) (PQR)(PQR) (PQR) (PQR) (主析取范式主析取范式) m1 m3 m4 m7 1.4 析取范式與合取范式2.命題公式的主合取范式命題公式的主合取范式定義定義5：在含有在含有n個(gè)命題變元的個(gè)命題變元的簡單析取簡單析取式中式中,若每個(gè)命題變元和它的否定不同時(shí)出現(xiàn)，而二者若每個(gè)命題變元和它的否定不同時(shí)出現(xiàn)，而二者之一必出現(xiàn)且僅出現(xiàn)一次，稱這樣的之一必出現(xiàn)且僅出現(xiàn)一次，稱這樣的簡單析取簡單析取式

27、式為為極大項(xiàng)極大項(xiàng).例如例如,三個(gè)命題變元三個(gè)命題變元P,Q,R,其大項(xiàng)共有其大項(xiàng)共有8個(gè)個(gè):1.4 析取范式與合取范式 大項(xiàng)大項(xiàng) 編碼編碼 真值指派真值指派 大項(xiàng)的真值大項(xiàng)的真值 P Q R M000/M0 000 0 P Q R M001/M1 001 0 P Q R M010/M2 010 0P Q R M011/M3 011 0P Q R M100/M4 100 0P Q R M101/M5 101 0 P Q R M110/M6 110 0 P Q R M111/M7 111 01.4 析取范式與合取范式極大項(xiàng)的性質(zhì)極大項(xiàng)的性質(zhì):沒有兩個(gè)大項(xiàng)是等價(jià)的沒有兩個(gè)大項(xiàng)是等價(jià)的, 且每個(gè)極大

28、項(xiàng)有且僅且每個(gè)極大項(xiàng)有且僅有一個(gè)成假賦值，若成假賦值所對應(yīng)的二進(jìn)有一個(gè)成假賦值，若成假賦值所對應(yīng)的二進(jìn)制數(shù)轉(zhuǎn)化為十進(jìn)制數(shù)為制數(shù)轉(zhuǎn)化為十進(jìn)制數(shù)為i，就將所對應(yīng)的極大，就將所對應(yīng)的極大項(xiàng)記作項(xiàng)記作Mi。(2) 任意兩個(gè)不同的極大項(xiàng)的析取為永真式任意兩個(gè)不同的極大項(xiàng)的析取為永真式.(3) 全體極大項(xiàng)的合取為矛盾式全體極大項(xiàng)的合取為矛盾式.1.4 析取范式與合取范式定義定義6：設(shè)命題公式設(shè)命題公式A中含有中含有n個(gè)命題變元個(gè)命題變元, 如如果果A的的合取范式合取范式中，所有的中，所有的簡單析取簡單析取式都是式都是大大項(xiàng)項(xiàng)，則稱該，則稱該合取合取范式范式為為A的主合取范式的主合取范式。定理：定理：任何命

29、題公式都存在著與之等價(jià)的主任何命題公式都存在著與之等價(jià)的主合取范式，并且是唯一的。合取范式，并且是唯一的。1.4 析取范式與合取范式定理定理5:在命題公式在命題公式A的真值表中的真值表中,真值為真值為0的的指派對應(yīng)的大項(xiàng)的合取指派對應(yīng)的大項(xiàng)的合取, 即為即為A的主的主合取范合取范式式一個(gè)命題公式一個(gè)命題公式A的主合取范式的主合取范式, 還可以通過等還可以通過等值演算的方法求出值演算的方法求出, 其推演步驟其推演步驟:(1) 將將A化為合取范式化為合取范式 ;(2) 除去合取范式中所有永真的合取項(xiàng)除去合取范式中所有永真的合取項(xiàng);1.4 析取范式與合取范式(3) 將合取范式中重復(fù)出現(xiàn)的簡單析取式和

30、相同將合取范式中重復(fù)出現(xiàn)的簡單析取式和相同變元都消去變元都消去;(4)若合取范式中某簡單析取式若合取范式中某簡單析取式B中不含命題變中不含命題變元元Pi, 添加添加(Pi Pi), 然后應(yīng)用分配律展開然后應(yīng)用分配律展開. 即即 B B 0B (Pi Pi) (B Pi) (B Pi).注：注：1.1.命題公式的主析命題公式的主析( (合合) )取范式唯一。取范式唯一。 2.2.兩命題公式若有相同的主析兩命題公式若有相同的主析( (合合) )取范取范 式，則二命題公式等價(jià)式，則二命題公式等價(jià). .1.4 析取范式與合取范式例例3：求：求(P Q)R)P的主合取范式的主合取范式。 解解: 原式原式

31、(PQ)R)P (PQ)(RP ) (合取范式合取范式)(PQ)(RR )(RP )(QQ)(PQR)(PQR)(PQR) (PQR) (PQR)(PQR)(PQR) (主合取范式主合取范式)M0M1M31.4 析取范式與合取范式 例例4：求：求(PQ)R的主合取范式的主合取范式。 解解: 原式原式(PR)(QR)(RPQ) (合取范合取范式式)(PR)(QQ) (PP) (QR) (PQR ) (PQR)(PQR)(PQR) (PQR)(PQR ) (PQR)(PQR) (PQR)(PQR ) (主合取范式主合取范式)M0M2M5 M6 1.4 析取范式與合取范式3.3.主析取范式和主合取范

32、式關(guān)系主析取范式和主合取范式關(guān)系設(shè)設(shè)Z為命題公式為命題公式A的主析取范式中所有小項(xiàng)的足的主析取范式中所有小項(xiàng)的足標(biāo)集合，標(biāo)集合，R為命題公式為命題公式A的主合取范式中所的主合取范式中所有大項(xiàng)的足標(biāo)集合有大項(xiàng)的足標(biāo)集合,則則 R=0,1，2.2n-1-Z或或 Z=0,1，2.2n-1-R。故已知命題公式故已知命題公式A的主析取范式，可求得其主的主析取范式，可求得其主合取范式；反之亦然。合取范式；反之亦然。注意到小項(xiàng)與大項(xiàng)之間具有關(guān)系：注意到小項(xiàng)與大項(xiàng)之間具有關(guān)系：miMi，Mimi（例：（例：m5：P Q R M5：P Q R）1.4 析取范式與合取范式4.主析主析(合合)取范式的應(yīng)用取范式的應(yīng)

33、用(1)求公式的成真求公式的成真/成假賦值：成假賦值： 若公式若公式A中含有中含有n個(gè)命題變元，且個(gè)命題變元，且A的主析的主析取范式含取范式含s個(gè)極小項(xiàng)，則個(gè)極小項(xiàng)，則A有有s個(gè)成真賦值，個(gè)成真賦值，有有2n-s個(gè)成假賦值。（即主析取范式中的小個(gè)成假賦值。（即主析取范式中的小項(xiàng)對應(yīng)的編碼是公式項(xiàng)對應(yīng)的編碼是公式A的成真賦值；反之的成真賦值；反之主合取范式中的大項(xiàng)對應(yīng)的編碼是公式主合取范式中的大項(xiàng)對應(yīng)的編碼是公式A的成假賦值）的成假賦值）.1.4 析取范式與合取范式(2)判斷公式的類型判斷公式的類型： 設(shè)公式設(shè)公式A中含有中含有n個(gè)命題變元，則：個(gè)命題變元，則：（1） A為重言式為重言式 A的的

34、主析取范式主析取范式含全部含全部2n個(gè)極個(gè)極小項(xiàng)小項(xiàng)（2）A為矛盾式為矛盾式 A的的主析取范式主析取范式不含任何極小項(xiàng)，不含任何極小項(xiàng)， 記記A的主析取范式為的主析取范式為0（3） A為可滿足式為可滿足式 A的的主析取范式主析取范式至少含一個(gè)極小項(xiàng)至少含一個(gè)極小項(xiàng)（4） A為矛盾式為矛盾式 A的的主合取范式主合取范式含全部含全部2n個(gè)極大項(xiàng)個(gè)極大項(xiàng)（5） A為重言式為重言式 A的的主合取范式主合取范式不含任何極大項(xiàng)，不含任何極大項(xiàng)， 記記A的主合取范式為的主合取范式為1 （6） A為可滿足式為可滿足式 A的的主合取范式主合取范式中極大項(xiàng)的個(gè)數(shù)中極大項(xiàng)的個(gè)數(shù) 一定小于一定小于2n 1.4 析取范

35、式與合取范式(3)判斷兩個(gè)命題是否等價(jià)判斷兩個(gè)命題是否等價(jià)5.解決實(shí)際問題：解決實(shí)際問題：某科研所有三名青年高級工程師某科研所有三名青年高級工程師A，B，C。所里要選派他們中的所里要選派他們中的1到到2人出國進(jìn)修，由人出國進(jìn)修，由于所里工作的需要，選派時(shí)必須滿足以下于所里工作的需要，選派時(shí)必須滿足以下條件：條件：若若A去，則去，則C也去也去若若B去，則去，則C不能去不能去若若C不去，則不去，則A或或B去去問所里應(yīng)如何選派他們？問所里應(yīng)如何選派他們？1.4 析取范式與合取范式解解: 設(shè)設(shè) P:派派A去。去。Q :派派B去。去。R :派派C去。去。根據(jù)所要滿足的條件，得命題公式為：根據(jù)所要滿足的條

36、件，得命題公式為： (PR)(Q R)(R( PQ) )求此公式的主析取范式求此公式的主析取范式:原式原式(PQR)(PQR)(PQR) 因此有三種選派方案：去，而、都不去；去因此有三種選派方案：去，而、都不去；去，而、都不去；、都去，而不去，而、都不去；、都去，而不去.1.4 析取范式與合取范式小結(jié)小結(jié):本節(jié)主要介紹了范式、本節(jié)主要介紹了范式、 析析(合合)取范式、取范式、(主主)析析(合合)取范式。重點(diǎn)掌握取范式。重點(diǎn)掌握(主主)析析(合合)取范式的求取范式的求法。法。 作業(yè)作業(yè): 1. 習(xí)題習(xí)題2: 7、8、9、30 2. 預(yù)習(xí)預(yù)習(xí)2.31.5 聯(lián)結(jié)詞的完備集v定義定義: 0, 1上的上的n元函數(shù)元函數(shù) f: 0, 1n 0, 1 就稱為一個(gè)就稱為一個(gè)n元真值函數(shù)（布爾函數(shù)）元真值函數(shù)（布爾函數(shù)）v自變量有自變量有2n組不同的取值，真值函數(shù)取組不同的取值，真值函數(shù)取值只有兩種：值只有兩種：1 0 n共有共有 種不同的真值函數(shù)種不同的真值函數(shù)22n1.5 聯(lián)結(jié)詞的完備集問題：v常用五個(gè)聯(lián)常用五個(gè)聯(lián)結(jié)結(jié)詞詞， ， ， ，是否有冗余呢？是否有冗余呢？ABABAB( AB) (B A) 1.5 聯(lián)結(jié)詞的完備集聯(lián)結(jié)詞完備集聯(lián)結(jié)詞完備集 定義：定義：一個(gè)聯(lián)結(jié)詞集合，若對于任何一個(gè)一個(gè)聯(lián)結(jié)詞集合，若對于任何一個(gè)公式均可以用該集