第二章 命題邏輯等值演算

1、第二章第二章 命題邏輯等值演算命題邏輯等值演算本章的主要內(nèi)容：本章的主要內(nèi)容：v 等值式與重言蘊(yùn)涵式等值式與重言蘊(yùn)涵式v 公式的標(biāo)準(zhǔn)型公式的標(biāo)準(zhǔn)型-范式范式v 聯(lián)結(jié)詞完備集聯(lián)結(jié)詞完備集本章與其他各章的聯(lián)系本章與其他各章的聯(lián)系v是第一章的抽象與延伸是第一章的抽象與延伸v是后續(xù)各章的先行準(zhǔn)備是后續(xù)各章的先行準(zhǔn)備 2.12.1等值式和重言蘊(yùn)涵式和重言蘊(yùn)涵式一、等值式與基本的等值式1 1等值式等值式定義定義2.12.1 若等價(jià)式若等價(jià)式AB是重言式，則稱是重言式，則稱A與與B等值，等值，記作記作AB，并稱，并稱AB是等值式。是等值式。注意：注意：（1 1）符號(hào)）符號(hào)“”與與“”的區(qū)別與聯(lián)系。的區(qū)別與聯(lián)

2、系。 “”不是聯(lián)結(jié)詞，不是聯(lián)結(jié)詞，AB不表示一個(gè)公式，它不表示一個(gè)公式，它表示兩個(gè)公式間的一種關(guān)系，即等值關(guān)系。表示兩個(gè)公式間的一種關(guān)系，即等值關(guān)系。 “”是聯(lián)結(jié)詞，是聯(lián)結(jié)詞，AB是一個(gè)公式。是一個(gè)公式。 AB當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)AB是重言式。是重言式。（2）可以驗(yàn)證等值關(guān)系是等價(jià)關(guān)系。）可以驗(yàn)證等值關(guān)系是等價(jià)關(guān)系。（3）當(dāng)）當(dāng)A是重言式時(shí)，是重言式時(shí)，A1；當(dāng)；當(dāng)A是矛盾式時(shí)，是矛盾式時(shí)，則則A0?？蓚鬟f性：可傳遞性：對任意公式對任意公式A,B,C，若，若AB，BC，則則AC。 對稱性：對稱性：對任意公式對任意公式A,B，若，若AB，則，則BA。自反性：自反性：對任意公式對任意公式A，有，有AA

3、。2. 基本的等值式雙重否定律雙重否定律 AA冪等律冪等律 A AA, A AA交換律交換律 A BB A, A BB A結(jié)合律結(jié)合律 (A B) CA (B C), (A B) CA (B C)分配律分配律 A (B C) (A B) (A C), A (B C) (A B) (A C)德摩根律德摩根律 (A B)AB (A B)AB吸收律吸收律 A (A B)A, A (A B)A零律零律 A 11, A 00同一律同一律 A 0A. A 1A排中律排中律 AA1矛盾律矛盾律 AA0蘊(yùn)涵等值式蘊(yùn)涵等值式 ABA B等價(jià)等值式等價(jià)等值式 AB(AB) (BA)假言易位假言易位 ABBA等價(jià)否

4、定等值式等價(jià)否定等值式 ABAB歸謬論歸謬論 (AB) (AB) A注意：要牢記各個(gè)等值式，這是繼續(xù)學(xué)習(xí)的基礎(chǔ)注意：要牢記各個(gè)等值式，這是繼續(xù)學(xué)習(xí)的基礎(chǔ)3. 3. 等值式的判別等值式的判別例例 用真值表法證明用真值表法證明 ： (p q) pq解解 令：令：A= (p q)，B= pq，構(gòu)造，構(gòu)造A，B 以及以及A B的真值表如下：的真值表如下：由于公式由于公式AB所標(biāo)記的列全為所標(biāo)記的列全為1，因此，因此AB。 pqp q (p q) p q pqAB00011111011010011110010110100001(1)(1)真值表法真值表法例例 用真值表法證明：用真值表法證明：p pq q

5、p p q q解解 令令A(yù)=pq，B= p q 構(gòu)造構(gòu)造A，B以及以及AB的真值表如下：的真值表如下：由于公式由于公式AB所標(biāo)記的列全為所標(biāo)記的列全為1，因此，因此AB.pq p p qpqAB001111011111100001110111例例 用真值表法判斷用真值表法判斷pqpq是否成立是否成立.解解 令令A(yù)=pq，B= pq 構(gòu)造構(gòu)造A，B以及以及AB的真值表的真值表由于公式由于公式AB所標(biāo)記的列不全為所標(biāo)記的列不全為1，AB不不是重言式，因此是重言式，因此AB不成立。不成立。pq p q pqpqAB0011111011001001100101100111 代入規(guī)則代入規(guī)則 對于重言式

6、中的任一命題變元出對于重言式中的任一命題變元出現(xiàn)的現(xiàn)的每一處每一處均用均用同一命題公式同一命題公式代入，得到的仍代入，得到的仍是重言式。是重言式。(2)(2)等值演算法等值演算法例：例： ( p q )( q p )AB AB 置換規(guī)則置換規(guī)則 設(shè)設(shè) (A)是含公式是含公式A的命題公式，的命題公式， (B)是用公式是用公式B置換了置換了 (A)中的所有的中的所有的A后得到后得到的命題公式，若的命題公式，若BA，則，則 (B)(A)等值演算等值演算 等值演算是指利用已知的一些等等值演算是指利用已知的一些等值式，根據(jù)值式，根據(jù)置換規(guī)則置換規(guī)則、代入規(guī)則代入規(guī)則以及以及等值關(guān)系等值關(guān)系的可傳遞性的可

7、傳遞性推導(dǎo)出另外一些等值式的過程。推導(dǎo)出另外一些等值式的過程。 (A)(pq) r (B)( pq) rpqpq(pq) r( pq) r例如：例如：例：例：證明下列等值式：證明下列等值式： (p q ) ( p ( p q ) ) p q證明：證明： (p q) ( p ( p q) (p q) ( ( p p ) q ) (結(jié)合律結(jié)合律) (p q) ( p q) (冪等律冪等律) ( p q ) ( p q ) (交換律交換律) p (q (p q) (結(jié)合律結(jié)合律) p q (吸收律吸收律) 例：例：證明等值式：證明等值式：（pq）（rq）（pr）q證明證明：(pq）（rq）（ pq）

8、( rq) (蘊(yùn)涵等值式蘊(yùn)涵等值式 )（ p r）q (分配律分配律) (pr)q (德摩根律德摩根律) (pr) q (蘊(yùn)涵等值式蘊(yùn)涵等值式 )所以所以（pq）（rq）（pr）q例：例：將下面程序語言進(jìn)行化簡：將下面程序語言進(jìn)行化簡：if A then if B then X else Y if B then X else Y解：解：該程序流程圖如下：該程序流程圖如下： StartABBXYEndFTFTFT執(zhí)行執(zhí)行X的條件：的條件：(AB)( AB)B (A A)B 執(zhí)行執(zhí)行Y的條件：的條件：(A B)( A B)B(A A)BStartBXYEndTF化簡結(jié)果：化簡結(jié)果：if B the

9、n X else Y練習(xí)：練習(xí)：用等值演算法證明下列等值式：用等值演算法證明下列等值式：(1)q(pr) (pq) r(2) （pq）（p q）（ pq）解（1） (pq) r （2）（）（p q）（ pq） (（ pq）（ qp）) (（pq）（qp）) （pq）(pq)r ( p q) r q( pr) q(pr) 二、重言蘊(yùn)涵式與基本重言蘊(yùn)涵式二、重言蘊(yùn)涵式與基本重言蘊(yùn)涵式注意：注意：符號(hào)符號(hào)“”和和 “ “”的區(qū)別和聯(lián)系與的區(qū)別和聯(lián)系與符號(hào)符號(hào)“”與與“”的區(qū)別和聯(lián)系類似。的區(qū)別和聯(lián)系類似。 “”不是聯(lián)結(jié)詞，不是聯(lián)結(jié)詞，“AB”不是公式，它表示不是公式，它表示公式公式A與與B之間存在之

10、間存在蘊(yùn)涵關(guān)系。蘊(yùn)涵關(guān)系。 “”是聯(lián)結(jié)詞，是聯(lián)結(jié)詞，AB是一個(gè)公式。是一個(gè)公式。 AB當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)AB是重言式是重言式 。1.定義定義 設(shè)設(shè)A，B是兩個(gè)公式，若公式是兩個(gè)公式，若公式AB是重言是重言式，即式，即AB1，則稱公式，則稱公式A蘊(yùn)涵公式蘊(yùn)涵公式B，記作，記作AB。稱。稱“AB”為重言蘊(yùn)涵式。為重言蘊(yùn)涵式。 AB是偏序關(guān)系是偏序關(guān)系即即 自反性：自反性：AA 反對稱性：反對稱性：若若AB，BA，則，則AB 傳遞性：傳遞性：若若AB，BC，則，則 AC反對稱性的證明：反對稱性的證明：AB1且且BA1于是于是AB(AB) (BA) 1 1 1因此因此 AB設(shè)設(shè)AB且且BA， 傳遞性的證

11、明：傳遞性的證明：則則AB1，BC1 ( A B C) ( AB C) (AB) C) ( A (BC) (1 C) ( A 1) 1 1 1因此因此 AC.于是于是 AC A C ( A C) (BB) 設(shè)設(shè)AB，BC， 2.基本重言蘊(yùn)涵式基本重言蘊(yùn)涵式附加律附加律 A (A B) B (A B)化簡律化簡律 (A B) A (A B) B假言推理假言推理 (AB) A B 拒取式拒取式 (AB)B A析取三段論析取三段論 (A B)B A假言三段論假言三段論 (AB) (BC) (AC)等價(jià)三段論等價(jià)三段論 (AB) (BC) (AC)構(gòu)造性二難構(gòu)造性二難 (AB) (CD) (A C)

12、(B D) (AB) ( AB) (AA) B破壞性二難破壞性二難 (AB) (CD) ( BD) ( AC)3.3.重言蘊(yùn)涵式的判別重言蘊(yùn)涵式的判別 判定判定“A B”是否成立的問題可轉(zhuǎn)化為判定是否成立的問題可轉(zhuǎn)化為判定A B是否為重言式，有下述判定方法：是否為重言式，有下述判定方法：（1 1）真值表法；）真值表法； （2 2）等值演算法；）等值演算法；（3 3）假定前件）假定前件A A為真；（為真；（4 4）假定后件）假定后件B B為假。為假。(1) (1) 真值表法真值表法例例 證明證明 ：(（pq）（p r）（q r）) r證明證明 令令 F =（pq）（pr）（qr）r，公式公式F對

13、任意的一組賦值取值均為對任意的一組賦值取值均為1，故，故F是重言是重言式，所以上述重言蘊(yùn)涵式成立。式，所以上述重言蘊(yùn)涵式成立。p q rpq pr q r (pq) (pr）（ q r）F0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 10 00 01 11 11 11 11 11 11 11 11 11 10 01 10 01 11 11 10 01 11 11 10 01 10 00 00 01 10 01 10 01 11 11 11 11 11 11 11 11 1(2) (2) 等值演算法等值演算法例：例：證明證明 ：p（pq） q 證明：證明：（p（p

14、q） q （p（ pq） q （蘊(yùn)涵等值式）（蘊(yùn)涵等值式） （ p （ pq）q （德摩根律）（德摩根律） （ pq） （ pq）（交換律、結(jié)合律）（交換律、結(jié)合律） 1 （排中律）（排中律） 因此因此 p（pq） q (3)(3) 假定前件假定前件A A為真為真例：例：證明證明 : : q （pq） p證明：證明：令前件令前件 q（pq）為真，）為真，則則 q為真為真, 且且pq為真。為真。于是于是q為假，因而為假，因而p也為假。由此也為假。由此 p為真。為真。故重言蘊(yùn)涵式故重言蘊(yùn)涵式 q （pq） p成立。成立。 假定前件假定前件A為真為真,檢查在此情況下檢查在此情況下,其后件其后件B是否

15、也為真。是否也為真。 ABA B001011100111 1 1 1 (4) (4) 假定后件假定后件B B為假為假 假定后件假定后件B為假，檢查在此情況下，其前件為假，檢查在此情況下，其前件A是是否也為假否也為假. 0 0 1ABA B001011100111例：例： (pq) (rs) (p r) (q s)證明證明:令后件令后件(p r)(q s)為假，則為假，則p r為真，為真，q s為假為假,于是于是p、r均為真，而均為真，而q和和s至少一個(gè)為假。至少一個(gè)為假。 由此可知由此可知 pq與與rs中至少一個(gè)為假中至少一個(gè)為假, 因此因此(pq) (rs)為假為假.故上述重言蘊(yùn)涵式成立。故

16、上述重言蘊(yùn)涵式成立。練習(xí)：練習(xí)：判定判定p（qr） （pq）（pr）是否成立）是否成立.(1)(1)真值表法真值表法: : 令令F=p（qr） （pq）（pr）p q r pq pr qr p(qr) (pq)(pr) F0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1111100111111010111011101111111011111110111111111(2)等值演算法p(qr)(pq)(pr)( p ( q r) ( ( p q) ( p r)(p (qr) (pq) ( p r) (p qr) (pp r) ( qp r) (p qr) ( pq

17、r) (p qr) (p q r)1(3)(3)假定后件（假定后件（pq）（pr）為假）為假則則pq為真，為真，pr為假。為假。由由pr為假為假,得得p為真，為真，r為假。為假。又又pq為真，故得為真，故得q為真。為真。于是于是p為真，為真，qr為假。為假。從而從而 前件前件p（qr）為假。）為假。因此重言蘊(yùn)涵式成立。因此重言蘊(yùn)涵式成立。(4)(4)假定前件假定前件p(qr)為真為真經(jīng)過分析之后，經(jīng)過分析之后，p,q,r的取值分別如下表所示：的取值分別如下表所示：p q rpqpr(pq)(pr)（后件后件）0 0 01110 0 11110 1 01110 1 11111 0 00011 0

18、 10111 1 1111后件為真，從而重言蘊(yùn)涵式成立。后件為真，從而重言蘊(yùn)涵式成立。等值和重言蘊(yùn)涵的關(guān)系：等值和重言蘊(yùn)涵的關(guān)系：證明等值式證明等值式A AB B的方法：的方法：AB 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)A B且且 B A .1) 真值表法真值表法2) 等值演算法等值演算法3) 證明證明A B且且 B A練習(xí)：練習(xí)：不構(gòu)造真值表證明下式：不構(gòu)造真值表證明下式：(1)(ab)(bc)(ca)(ab)(bc)(ca)(2) (pq) qpq解：解： (1)(ab)(bc)(ca)(b(ac)(ca)(b(ca)(ac)(ca)(bc)(ba)(ac)(ab)(bc)(ca)(2)假定后件假定后件pq為

19、假，則為假，則p,q均為假，所以均為假，所以pq為為真，從而前件真，從而前件(pq) q為假，因此為假，因此(pq) qpq成立。成立。 由等值式可知，同一命題公式可以有各種相互由等值式可知，同一命題公式可以有各種相互等值的表達(dá)形式，為了把命題公式規(guī)范化，需等值的表達(dá)形式，為了把命題公式規(guī)范化，需要研究公式的范式問題。要研究公式的范式問題。 如果公式中的變元數(shù)目較大時(shí)，對于公式的判如果公式中的變元數(shù)目較大時(shí)，對于公式的判定問題，真值表將非常繁瑣。每增加一個(gè)變元，定問題，真值表將非常繁瑣。每增加一個(gè)變元，計(jì)算將增加一倍。研究公式的標(biāo)準(zhǔn)型問題變得計(jì)算將增加一倍。研究公式的標(biāo)準(zhǔn)型問題變得十分重要。十

20、分重要。 給定任意一個(gè)命題公式，我們希望尋找其某種給定任意一個(gè)命題公式，我們希望尋找其某種一般的標(biāo)準(zhǔn)的形式，即范式一般的標(biāo)準(zhǔn)的形式，即范式(normal form) 。2.22.2 公式的標(biāo)準(zhǔn)型公式的標(biāo)準(zhǔn)型-范式范式1.1.基本概念基本概念（1）文字）文字命題變項(xiàng)及其否定的總稱命題變項(xiàng)及其否定的總稱（2）簡單析取式）簡單析取式有限個(gè)文字構(gòu)成的析取式有限個(gè)文字構(gòu)成的析取式p, q, pq, p q r, （3）簡單合取式）簡單合取式有限個(gè)文字構(gòu)成的合取式有限個(gè)文字構(gòu)成的合取式p, q, pq, p q r, （4）析取范式）析取范式由有限個(gè)簡單合取式組成的析取由有限個(gè)簡單合取式組成的析取式式 A

21、1 A2Ar (r 1)（5）合取范式）合取范式由有限個(gè)簡單析取式組成的合取由有限個(gè)簡單析取式組成的合取式式 A1 A2Ar (r 1)（6）范式）范式析取范式與合取范式的總稱析取范式與合取范式的總稱一、析取范式與合取范式一、析取范式與合取范式說明：說明：（1）單個(gè)文字既是簡單析取式，又是簡）單個(gè)文字既是簡單析取式，又是簡單合取式單合取式（2）形如）形如pq r, p qr的公式既是的公式既是析取范式，又是合取范式析取范式，又是合取范式.2.2.主要性質(zhì)主要性質(zhì)定理定理2.12.1 （1）一個(gè)簡單析取式是重言式當(dāng)且僅當(dāng)它同時(shí)）一個(gè)簡單析取式是重言式當(dāng)且僅當(dāng)它同時(shí)含某個(gè)命題變項(xiàng)及它的否定式。含某

22、個(gè)命題變項(xiàng)及它的否定式。（2）一個(gè)簡單合取式是矛盾式當(dāng)且僅當(dāng)它同時(shí)）一個(gè)簡單合取式是矛盾式當(dāng)且僅當(dāng)它同時(shí)含某個(gè)命題變項(xiàng)及它的否定式。含某個(gè)命題變項(xiàng)及它的否定式。定理定理2.22.2 （1）一個(gè)析取范式是矛盾式當(dāng)且僅當(dāng)它的每個(gè)）一個(gè)析取范式是矛盾式當(dāng)且僅當(dāng)它的每個(gè)簡單合取式都是矛盾式。簡單合取式都是矛盾式。（2）一個(gè)合取范式是重言式當(dāng)且僅當(dāng)它的每個(gè)）一個(gè)合取范式是重言式當(dāng)且僅當(dāng)它的每個(gè)簡單析取式都是重言式。簡單析取式都是重言式。3 3定理定理2.3 (2.3 (范式存在定理范式存在定理) )任何命題公式都存在著與之等值的析取范任何命題公式都存在著與之等值的析取范式與合取范式式與合取范式. .求公

23、式求公式A A的范式的步驟：的范式的步驟：（1）消去）消去A中的中的, （若存在）（若存在）（2）否定聯(lián)結(jié)詞）否定聯(lián)結(jié)詞 的內(nèi)移或消去的內(nèi)移或消去（3）使用分配律）使用分配律 對對 分配（析取范式）分配（析取范式） 對對 分配（合取范式）分配（合取范式）例例: :求下列公式的析取范式、合取范式求下列公式的析取范式、合取范式（1） ( p (qr) ) s解：解：( p (qr) ) s ( p ( q r) ) s (p ( q r) s p ( q r) s p (q r) s 析取范式析取范式 （ p s) (q r) （ p s q ) ( p s r) 合取范式合取范式（2） (p q

24、) (p q)解：解： (p q) (p q) (p q) (p q) (p q) (p q) ( pq) (p q) (p q) ( pq) pq p q (pp) (pq) (qp) (qq) ( 0 0 ) 0 (pq) (qp) 0 (pq) (qp) 析取范式析取范式(p q) ( pq) 合取范式合取范式（1）一個(gè)命題公式的合取、析取范式不是唯一）一個(gè)命題公式的合取、析取范式不是唯一的。的。 例如：例如：p (q r) (p q) (p r) (p p) (p r) (q p) (q r) 仍然得到公式的不同等值形式。仍然得到公式的不同等值形式。（2）為了使任意一個(gè)公式，化成惟一的

25、等值）為了使任意一個(gè)公式，化成惟一的等值形式，引入主范式的概念。形式，引入主范式的概念。注意：注意：定義定義2.4 2.4 在含有在含有n個(gè)命題變項(xiàng)的簡單合取式（簡單析取個(gè)命題變項(xiàng)的簡單合取式（簡單析取式）中，若每個(gè)命題變項(xiàng)均以文字的形式在式）中，若每個(gè)命題變項(xiàng)均以文字的形式在其中出現(xiàn)且僅出現(xiàn)一次，而且第其中出現(xiàn)且僅出現(xiàn)一次，而且第i（1 i n）個(gè)文字出現(xiàn)在左起第個(gè)文字出現(xiàn)在左起第i位上，稱這樣的簡單合位上，稱這樣的簡單合取式（簡單析取式）為極小項(xiàng)（極大項(xiàng)）取式（簡單析取式）為極小項(xiàng)（極大項(xiàng)）.二、主析取范式與主合取范式二、主析取范式與主合取范式1.1.極小項(xiàng)與極大項(xiàng)極小項(xiàng)與極大項(xiàng)幾點(diǎn)說明：

26、幾點(diǎn)說明：(1) n個(gè)命題變項(xiàng)產(chǎn)生個(gè)命題變項(xiàng)產(chǎn)生2n個(gè)極小項(xiàng)和個(gè)極小項(xiàng)和2n個(gè)極大項(xiàng)個(gè)極大項(xiàng);(2) 2n個(gè)極小項(xiàng)（極大項(xiàng)）均互不等值個(gè)極小項(xiàng)（極大項(xiàng)）均互不等值;(3) 用用mi表示第表示第i個(gè)極小項(xiàng)，其中個(gè)極小項(xiàng)，其中i是該極小項(xiàng)成是該極小項(xiàng)成真賦值的十進(jìn)制表示真賦值的十進(jìn)制表示. Mi表示第表示第i個(gè)極大項(xiàng)，其個(gè)極大項(xiàng)，其中中i是該極大項(xiàng)成假賦值的十進(jìn)制表示是該極大項(xiàng)成假賦值的十進(jìn)制表示, mi（Mi）稱為極小項(xiàng)（極大項(xiàng)）的名稱稱為極小項(xiàng)（極大項(xiàng)）的名稱. 由p, q兩個(gè)命題變項(xiàng)形成的極小項(xiàng)與極大項(xiàng)由下表給出極小項(xiàng)極大項(xiàng)公式成真賦值名稱公式成假賦值名稱pqpqpqpq 0 0 0 1 1

27、 0 1 1 m0m1m2m3 pq pq pqpq 0 0 0 1 1 0 1 1M0M1M2M3由p, q, r三個(gè)命題變項(xiàng)形成的極小項(xiàng)與極大項(xiàng)由下表給出. mi與Mi的關(guān)系：mi Mi, Mi mi 極小項(xiàng)極大項(xiàng)公式成真賦值名稱公式成假賦值名稱p q rp q rp q rp q rp q rp q rp q rp q r0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1 m0m1m2m3m4m5m6m7 p q r p q r p q r p q r p q r p q r p q r p q r0 0 00 0 10 1 00 1 11 0 01 0 1

28、1 1 01 1 1M0M1M2M3M4M5M6M72 2主析取范式與主合取范式主析取范式與主合取范式（1 1）定義）定義2.52.5 主析取范式主析取范式由極小項(xiàng)構(gòu)成的析取范式由極小項(xiàng)構(gòu)成的析取范式主合取范式主合取范式由極大項(xiàng)構(gòu)成的合取范式由極大項(xiàng)構(gòu)成的合取范式例如，例如，n=3, 命題變項(xiàng)為命題變項(xiàng)為p, q, r時(shí)，時(shí)，( p q r) ( p q r) m1 m3 主析取范式主析取范式 ( p q r) (p q r) M7 M1 主合取范式主合取范式（2 2）主范式的存在惟一定理）主范式的存在惟一定理定理定理2.52.5 任何命題公式都存在著與之等值的主任何命題公式都存在著與之等值的

29、主析取范式和主合取范式析取范式和主合取范式,并且是惟一的。并且是惟一的。（3 3）主析取范式與主合取范式的求法）主析取范式與主合取范式的求法在真值表中，一個(gè)公式的真值為在真值表中，一個(gè)公式的真值為1（0）的賦值）的賦值所對應(yīng)的極?。ù螅╉?xiàng)的析（合）取，即為此所對應(yīng)的極?。ù螅╉?xiàng)的析（合）取，即為此公式的公式的主析（合）取范式。主析（合）取范式。pq rG0 000001 10 10001111000101011011 111 1 1 1 1 0 0 1 1 0 1 1 1 1 1 0 1（1）求主析取范式）求主析取范式(pq)r (p q) r （析取范式）（析取范式） (p q) (p q)

30、 ( r r)(p qr) (p q r)m6 m7 r ( p p) ( q q) r ( pq r) ( p q r) (pq r) (p q r) m1 m3 m5 m7 , 代入代入并排序，得并排序，得(pq)r m1 m3 m5 m6 m7 （主析取范式）（主析取范式）例例 求公式 A=(pq)r的主析取范式與主合取范式.（2）求）求A的主合取范式的主合取范式(pq)r (p r) (q r) （合取范式）（合取范式） p r p (qq) r (p q r) (pq r) M0 M2 q r (pp) q r (p q r) ( p q r)M0 M4 , 代入代入并排序，得并排序

31、，得(pq)r M0 M2 M4 （主合取范式）（主合取范式）3. 3. 范式的用途范式的用途（1）求公式的成真與成假賦值）求公式的成真與成假賦值 (pq)r m1 m3 m5 m6 m7， 其成真賦值為001, 011, 101, 110, 111，當(dāng)然成假賦值為000, 010, 100. 類似地，由主合取范式也立即求出成假或成真賦值. （2）判斷公式的類型）判斷公式的類型設(shè)設(shè)A含含n個(gè)命題變項(xiàng)個(gè)命題變項(xiàng). A為重言式為重言式 A的主析取范式含的主析取范式含2n個(gè)極小項(xiàng)個(gè)極小項(xiàng) A的主合取范式為的主合取范式為1.A為矛盾式為矛盾式 A的主析取范式為的主析取范式為0 A的主合析取范式含的主合

32、析取范式含2n個(gè)極大項(xiàng)個(gè)極大項(xiàng)A為非重言式的可滿足式為非重言式的可滿足式 A的主析取范式中至少含一個(gè)（但不是全部）極小項(xiàng)的主析取范式中至少含一個(gè)（但不是全部）極小項(xiàng) A的主合取范式中至少含一個(gè)（但不是全部）極大項(xiàng)的主合取范式中至少含一個(gè)（但不是全部）極大項(xiàng)（3）判斷兩個(gè)公式是否等值）判斷兩個(gè)公式是否等值例例 用主析取范式判斷兩個(gè)公式是否等值用主析取范式判斷兩個(gè)公式是否等值 p(qr) 與與 (p q)r p(qr) 與與 (pq)r解：解： p(qr) = m0 m1 m2 m3 m4 m5 m7 (p q)r = m0 m1 m2 m3 m4 m5 m7 (pq)r = m1 m3 m4 m

33、5 m7顯見，顯見，中的兩公式等值，而中的兩公式等值，而的不等值的不等值.（4）解實(shí)際問題）解實(shí)際問題例：某科研所要從例：某科研所要從3名科研骨干名科研骨干A,B,C中挑選中挑選12名出國進(jìn)修。由于工作需要，選派時(shí)要名出國進(jìn)修。由于工作需要，選派時(shí)要滿足以下條件：滿足以下條件：（1）若）若A去，則去，則C同去；同去；（2）若）若B去，則去，則C不能去；不能去；（3）若）若C不去，則不去，則A或或B可以去?？梢匀?。問所里應(yīng)如何選派他們？問所里應(yīng)如何選派他們？三、對偶三、對偶命題等價(jià)公式多數(shù)成對出現(xiàn)，是對偶性質(zhì)的體命題等價(jià)公式多數(shù)成對出現(xiàn)，是對偶性質(zhì)的體現(xiàn)?，F(xiàn)。例如：例如： p (p q)p；p

34、(p q)p利用對偶性質(zhì)，可以擴(kuò)大等價(jià)公式的個(gè)數(shù)，減利用對偶性質(zhì)，可以擴(kuò)大等價(jià)公式的個(gè)數(shù)，減少證明次數(shù)。少證明次數(shù)。1. 1. 定義定義 (p 0) (p 1) 3.3.由公式的主析取范式求主合取范式，反之亦然。由公式的主析取范式求主合取范式，反之亦然。例：例：由公式的主析取范式，求主合取范式：由公式的主析取范式，求主合取范式：（1）Am1 m2 (A中含兩個(gè)命題變項(xiàng)中含兩個(gè)命題變項(xiàng)p,q)（2）B m1 m2 m3 (B中含命題變項(xiàng)中含命題變項(xiàng)p,q,r)解：解：（1）AM0 M3 （2）B M0 M4 M5 M6 M72.3 2.3 聯(lián)結(jié)詞的完備集聯(lián)結(jié)詞的完備集一、真值函數(shù)一、真值函數(shù)1問題的提出問題的提出問：含問：含n個(gè)命題變項(xiàng)的所有公式共產(chǎn)生多少個(gè)命題變項(xiàng)的所有公式共產(chǎn)生多少個(gè)互不相同的真值表？個(gè)互不相同的真值表？n22答案為 個(gè)，為什么？2真值函數(shù)的定義稱定義域?yàn)榉Q定義域?yàn)?00, 001, , 111，值域?yàn)?，值域?yàn)?,1的函數(shù)為的函數(shù)為n元真值函數(shù)，定義域中的元素元真值函數(shù)，定義域中的元素為為2n個(gè)長為個(gè)長為n的的0,1組成的符號(hào)串組成的符號(hào)串. 常用常用F:0,1n0,1 表示表示F是是n元真值函數(shù)元真值函數(shù). 易知，全體易知，全體n元函數(shù)共有元函數(shù)共有 個(gè)個(gè). 設(shè)設(shè)F:0,1n0,1，且，且F(0