命題邏輯等值演算

1、命題邏輯等值演算第1頁，共53頁，2022年，5月20日，8點46分，星期二兩公式什么時候代表了同一個命題呢？抽象地看，兩個公式在任何相同的賦值下有相同的真假時即代表了相同的命題。設公式A,B共同含有n個命題變項，可能對A或B有啞元，若A與B有相同的真值表，則說明在2n個賦值的每個賦值下，A與B的真值都相同。于是公式AB應為重言式。 2.1 等值式第2頁，共53頁，2022年，5月20日，8點46分，星期二1、等值的定義及說明定義2.1 設A,B是兩個命題公式，若A,B構成的等價式AB為重言式,則稱A與B是等值的,記作AB。 說明注意與的區(qū)別。A或B中可能有啞元出現(xiàn)。pq (pq)(rr)r為

2、左邊公式中的啞元。用真值表可以驗證兩個公式是否等值。第3頁，共53頁，2022年，5月20日，8點46分，星期二例2.1 判斷下面兩個公式是否等值(pq) 與 pq 解答說明在用真值表法判斷AB是否為重言式時，真值表的最后一列可以省略。等值第4頁，共53頁，2022年，5月20日，8點46分，星期二例題2.2 判斷下列各組公式是否等值(1)p(qr)與(pq)r (2)(pq)r與(pq)r 解答等值不等值第5頁，共53頁，2022年，5月20日，8點46分，星期二2、基本等值式1.雙重否定律A A2.冪等律A AA,A AA 3.交換律AB BA，AB BA4.結合律(AB)C A(BC)

3、(AB)C A(BC) 5.分配律A(BC) (AB)(AC) （對的分配律）A(BC) (AB)(AC)（對的分配律）6.德摩根律(AB) AB(AB) AB 7.吸收律A(AB) A，A(AB) A 第6頁，共53頁，2022年，5月20日，8點46分，星期二 8.零律A1 1,A0 0 9.同一律A0 A，A1 A 10.排中律AA 1 11.矛盾律AA 0 12.蘊涵等值式AB AB13.等價等值式AB (AB)(BA)14.假言易位AB BA15.等價否定等值式 AB AB16.歸謬論(AB)(AB) A 第7頁，共53頁，2022年，5月20日，8點46分，星期二3、對偶原理一個邏

4、輯等值式，如果只含有、0、1那么同時把和互換把0和1互換得到的還是等值式。第8頁，共53頁，2022年，5月20日，8點46分，星期二4、等值演算與置換規(guī)則各等值式都是用元語言符號書寫的，其中A,B,C可以代表任意的公式，稱這樣的等值式為等值式模式。每個等值式模式都給出了無窮多個同類型的具體的等值式。例如，在蘊涵等值式 ABAB 中，取A=p，B=q時，得等值式 pqpq 取A=pqr，B=pq時，得等值式(pqr)(pq) (pqr)(pq)這些具體的等值式都被稱為原來的等值式模式的代入實例。由已知的等值式推演出另外一些等值式的過程為等值演算。置換規(guī)則 設(A)是含公式A的命題公式，(B)是

5、用公式B置換了(A)中所有的A后得到的命題公式，若BA，則(B)(A)。第9頁，共53頁，2022年，5月20日，8點46分，星期二關于等值演算的說明等值演算的基礎等值關系的性質：自反性：AA。對稱性：若AB，則BA。傳遞性：若AB且BC，則AC。基本的等值式置換規(guī)則等值演算的應用證明兩個公式等值判斷公式類型解判定問題第10頁，共53頁，2022年，5月20日，8點46分，星期二等值演算的應用舉例證明兩個公式等值(pq)r (pr)(qr)(pq)r (pq)r（蘊含等值式、置換規(guī)則） (pq)r（蘊含等值式、置換規(guī)則） (pq)r（德摩根律、置換規(guī)則） (pr)(qr)（分配律、置換規(guī)則）說

6、明也可以從右邊開始演算因為每一步都用置換規(guī)則，故可不寫出熟練后，基本等值式也可以不寫出通常不用等值演算直接證明兩個公式不等值解答第11頁，共53頁，2022年，5月20日，8點46分，星期二例2.3 用等值演算法驗證等值式(pq)r (pr)(qr) (pr)(qr) (pr)(qr)(蘊含等值式) (pq)r(分配律) (pq)r(德摩根律) (pq)r(蘊含等值式) 解答第12頁，共53頁，2022年，5月20日，8點46分，星期二例題2.4 用等值演算判斷下列公式的類型：（1） (p(pq)r （2）p(pq)p)q) （3）(pq)pq(1) (p(pq)r (ppq)r (ppq)r

7、 0r0故原公式為矛盾式(2) p(pq)p)q) p(pq)p)q) p(pp)(qp)q) p(0(qp)q) p(qpq) p1 p故原公式為非重言式的可滿足式解：第13頁，共53頁，2022年，5月20日，8點46分，星期二(3) (pq)pq (pq)pq （蘊涵等值式） (pq)p)q （蘊涵等值式） (pq)p)q （德摩根律） (pq)p)q（德摩根律） (pp)(qp)q （分配律） (1(qp)q （排中律） (qq)p （同一律） 1p（排中律） 1 （零律）公式為重言式第14頁，共53頁，2022年，5月20日，8點46分，星期二定義1 命題變項及其否定統(tǒng)稱作文字。僅由

8、有限個文字構成的析取式稱作簡單析取式。僅由有限個文字構成的合取式稱作簡單合取式。簡單析取式舉例：p,qpp，pq pqr,pqr簡單合取式舉例：p,qpp，pqpqr,ppq2.2 析取范式和合取范式 1、簡單析取式與簡單合取式第15頁，共53頁，2022年，5月20日，8點46分，星期二一個文字既是簡單析取式，又是簡單合取式。為討論方便，有時用A1,A2,As表示s個簡單析取式或s個簡單合取式。定理1 (1)一個簡單析取式是重言式當且僅當它同時含有某個命題變項及它的否定式。 (2)一個簡單合取式是矛盾式當且僅當它同時含有某個命題變項及它的否定式。 第16頁，共53頁，2022年，5月20日，

9、8點46分，星期二定義2 (1)由有限個簡單合取式構成的析取式稱為析取范式。 (2)由有限個簡單析取式構成的合取式稱為合取范式。 (3)析取范式與合取范式統(tǒng)稱為范式。 2、析取范式與合取范式設Ai(i=1,2,s)為簡單合取式，則A=A1A2As為析取范式。例如，A1=pq，A2=qr，A3=p，則由A1,A2,A3構造的析取范式為A=A1A2A3=(pq)(qr)p 設Ai(i=1,2,s)為簡單析取式，則A=A1A2As為合取范式。例如，取A1=pqr，A2=pq，A3=r，則由A1,A2,A3組成的合取范式為A=A1A2A3=(pqr)(pq)r第17頁，共53頁，2022年，5月20日

10、，8點46分，星期二定理2 (1)一個析取范式是矛盾式當且僅當它的每個簡單合取式都是矛盾式。 (2)一個合取范式是重言式當且僅當它的每個簡單析取式都是重言式。 定理3 任一命題公式都存在著與之等值的析取范式與合取范式。 3、析取范式和合取范式的性質說明研究范式的目的在于，將給定公式化成與之等值的析取范式或合取范式，進而將公式化成與之等值的主析取范式或主合取范式。第18頁，共53頁，2022年，5月20日，8點46分，星期二4、求給定公式范式的步驟(1)消去聯(lián)結詞、(若存在)。AB ABAB (AB)(AB)(2)否定號的消去(利用雙重否定律)或內移(利用德摩根律)。A A(AB) AB(AB)

11、AB(3)利用分配律：利用對的分配律求析取范式， 對的分配律求合取范式。A(BC) (AB)(AC)A(BC) (AB)(AC)第19頁，共53頁，2022年，5月20日，8點46分，星期二例題1 求下面公式的析取范式與合取范式：(pq) r (1) 求合取范式 (pq) r (pq) r （消去） (pq)r)(r(pq) （消去） (pq)r)(rpq)（消去） (pq)r)(pqr) （否定號內移） (pr)(qr)(pqr)（對分配律）解答第20頁，共53頁，2022年，5月20日，8點46分，星期二(2) 求析取范式 (pq) r (pq)r)(pqr) (pqp)(pqq)(pqr

12、) (rp)(rq)(rr) (pqr)(pr)(qr) 說明由此例可知，命題公式的析取范式不唯一。同樣，合取范式也是不唯一的。第21頁，共53頁，2022年，5月20日，8點46分，星期二5、范式的規(guī)范化形式定義3 在含有n個命題變項的簡單合取式（簡單析取式）中，若每個命題變項和它的否定式不同時出現(xiàn)，而二者之一必出現(xiàn)且僅出現(xiàn)一次，且第i個命題變項或它的否定式出現(xiàn)在從左算起的第i位上（若命題變項無角標，就按字典順序排列），稱這樣的簡單合取式（簡單析取式）為極小項（極大項）。n個命題變項共可產(chǎn)生2n個不同的極小項。其中每個極小項都有且僅有一個成真賦值。若成真賦值所對應的二進制數(shù)轉換為十進制數(shù)i，

13、就將所對應極小項記作mi 。類似地，n個命題變項共可產(chǎn)生2n個極大項，每個極大項只有一個成假賦值，將其對應的十進制數(shù)i做極大項的角標，記作Mi。第22頁，共53頁，2022年，5月20日，8點46分，星期二表1 p,q形成的極小項與極大項 P QPQPQPQPQ0 00 11 01 1 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0P QPQPQPQPQ0 00 11 01 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0第23頁，共53頁，2022年，5月20日，8點46分，星期二表2 p,q,r形成的極小項與極大項 第24頁，共53頁，2022年，5月20

14、日，8點46分，星期二定理4 設mi與Mi是命題變項p1,p2,pn形成的極小項和極大項，則 mi Mi， Mi mi 定義4 設由n個命題變項構成的析取范式（合取范式）中所有的簡單合取式（簡單析取式）都是極小項（極大項），則稱該析取范式（合取范式）為主析取范式（主合取范式）. 定理5 任何命題公式都存在著與之等值的主析取范式和主合取范式，并且是唯一的。 第25頁，共53頁，2022年，5月20日，8點46分，星期二定理5的證明(1)證明存在性。設A是任一含n個命題變項的公式。由定理2.3可知，存在與A等值的析取范式A，即AA，若A的某個簡單合取式Ai中既不含命題變項pj，也不含它的否定式pj

15、，則將Ai展成如下形式：Ai Ai1 Ai(pjpj) (Aipj)(Ajpj) 繼續(xù)這個過程，直到所有的簡單合取式都含任意命題變項或它的否定式。 若在演算過程中出現(xiàn)重復的命題變項以及極小項和矛盾式時，都應“消去”：如用p代替pp，mi代替mimi，0代替矛盾式等。最后就將A化成與之等值的主析取范式A。 第26頁，共53頁，2022年，5月20日，8點46分，星期二(2)證明唯一性。假設某一命題公式A存在兩個與之等值的主析取范式B和C，即AB且AC，則BC。由于B和C是不同的主析取范式，不妨設極小項mi只出現(xiàn)在B中而不出現(xiàn)在C中。于是，角標i的二進制表示為B的成真賦值，而為C的成假賦值。這與B

16、C矛盾，因而B與C必相同。 第27頁，共53頁，2022年，5月20日，8點46分，星期二6、求公式A的主析取范式的方法與步驟方法一、等值演算法(1)化歸為析取范式。 (2)除去析取范式中所有永假的析取項。(3)將析取式中重復出現(xiàn)的合取項和相同的變元合并。(4)對合取項補入沒有出現(xiàn)的命題變元，即添加如(pp)式，然后應用分配律展開公式。方法二、真值表法(1)寫出A的真值表。(2)找出A的成真賦值。(3)求出每個成真賦值對應的極小項（用名稱表示），按角標從小到大順序析取。第28頁，共53頁，2022年，5月20日，8點46分，星期二方法一、等值演算法(1)化歸為合取范式。 (2)除去合取范式中所

17、有永真的合取項。(3)將合取式中重復出現(xiàn)的析取項和相同的變元合并。(4)對析取項補入沒有出現(xiàn)的命題變元，即添加如(pp)式，然后應用分配律展開公式。方法二、真值表法(1)寫出A的真值表。(2)找出A的成假賦值。(3)求出每個成假賦值對應的極大項（用名稱表示），按角標從小到大順序析取。7、求公式A的主合取范式的方法與步驟第29頁，共53頁，2022年，5月20日，8點46分，星期二(1)求主合取范式pq pq M2(2)求析取范式pq pq （p（qq） （(pp)q） (pq)(pq)(pq)(pq) (pq)(pq)(pq) m0m1m3 解答pqp q001011100111例2 求命題公

18、式 pq 的主析取范式和主合取范式。第30頁，共53頁，2022年，5月20日，8點46分，星期二例3 求 的主析取范式和主合取范式。解：(1) 列真值表 (2) 成真賦值有010，100，101，110，111 (3)成假賦值有000，001，011主析取范式為主合取范式為方法一、真值表法第31頁，共53頁，2022年，5月20日，8點46分，星期二方法二、等值演算法 主析取范式第32頁，共53頁，2022年，5月20日，8點46分，星期二方法二、等值演算法 主合取范式第33頁，共53頁，2022年，5月20日，8點46分，星期二已知一種主范式,求另一種主范式分析: 主析取范式中沒有出現(xiàn)的極

19、小項有主合取范式為第34頁，共53頁，2022年，5月20日，8點46分，星期二主析取范式的用途 求公式的成真賦值與成假賦值判斷公式的類型 判斷兩個命題公式是否等值 應用主析取范式分析和解決實際問題 第35頁，共53頁，2022年，5月20日，8點46分，星期二求公式的成真賦值與成假賦值若公式A中含n個命題變項，A的主析取范式含s(0s2n)個極小項，則A有s個成真賦值，它們是所含極小項角標的二進制表示，其余2n-s個賦值都是成假賦值。在例2.8中，(pq)r m1m3m4m7,各極小項均含三個文字，因而各極小項的角標均為長為3的二進制數(shù)，它們分別是001，011，100，111，這四個賦值為

20、該公式的成真賦值,其余的為成假賦值。在例2.9中，pq m0m1m3，這三個極小項均含兩個文字，它們的角標的二進制表示00，01，11為該公式的成真賦值，10是它的成假賦值。 第36頁，共53頁，2022年，5月20日，8點46分，星期二判斷公式的類型設公式A中含n個命題變項，容易看出：A為重言式當且僅當A的主析取范式含全部2n個極小項。A為矛盾式當且僅當A的主析取范式不含任何極小項。此時，記A的主析取范式為0。A為可滿足式當且僅當A的主析取范式至少含一個極小項。第37頁，共53頁，2022年，5月20日，8點46分，星期二判斷公式的類型例2.10 用公式的主析取范式判斷公式的類型：(1) (

21、pq)q (2) p(pq) (3) (pq)r解答(1)(pq)q （pq）q (pq)q 0 (2)p(pq) m0m1m2m3 (3)(pq)r m0m1m3m5m7 矛盾式重言式可滿足式第38頁，共53頁，2022年，5月20日，8點46分，星期二判斷兩個命題公式是否等值設公式A,B共含有n個命題變項，按n個命題變項求出A與B的主析取范式A與B。若AB,則AB；否則，A與B不等值。例2.11 判斷下面兩組公式是否等值：(1) p與(pq)(pq) (2)(pq)r與(q)r (1) p p(qq) (pq)(pq) m2m3 (pq)(pq) m2m3 兩公式等值。(2) (pq)r

22、m1m3m4m5m7 (q)r m0m1m2m3m4m5m7 兩公式不等值。解答第39頁，共53頁，2022年，5月20日，8點46分，星期二應用主析取范式分析和解決實際問題例2.12某科研所要從3名科研骨干A,B,C中挑選12名出國進修。由于工作原因，選派時要滿足以下條件：(1)若A去，則C同去。(2)若B去，則C不能去。(3)若C不去，則A或B可以去。問應如何選派他們去？ 分析：(1)將簡單命題符號化(2)寫出各復合命題(3)寫出由(2)中復合命題組成的合取式（前提）(4)將(3)中公式化成析取式（最好是主析取范式）(5)這樣每個小項就是一種可能產(chǎn)生的結果。去掉不符合題意的小項，即得結論。

23、 第40頁，共53頁，2022年，5月20日，8點46分，星期二應用主析取范式分析和解決實際問題設 p:派A去，q:派B去，r:派C去 由已知條件可得公式 (pr)(qr)(r(pq) 經(jīng)過演算可得 (pr)(qr)(r(pq) m1m2m5 由于 m1=pqr, m2=pqr, m5=pqr可知，選派方案有3種：(a)C去，而A,B都不去。(b)B去，而A,C都不去。(c)A,C去，而B不去。解答第41頁，共53頁，2022年，5月20日，8點46分，星期二由公式的主析取范式求主合取范式 設公式A含n個命題變項。A的主析取范式含s(0s2n)個極小項，即沒有出現(xiàn)的極小項設為它們的角標的二進制

24、表示為A的成真賦值，因而A的主析取范式為第42頁，共53頁，2022年，5月20日，8點46分，星期二例2.13 由公式的主析取范式，求主合取范式： (1) A m1m2 (A中含兩個命題變項p,q)(2) B m1m2m3 (B中含兩個命題變項p,q,r) 解答(1) A M0M3 (2) B M0M4M5M6M7 第43頁，共53頁，2022年，5月20日，8點46分，星期二重言式與矛盾式的主合取范式設n為公式中命題變項個數(shù)矛盾式無成真賦值，因而矛盾式的主合取范式含2n個極大項。重言式無成假賦值，因而主合取范式不含任何極大項。將重言式的主合取范式記為1?？蓾M足式的主合取范式中極大項的個數(shù)一

25、定小于2n。 第44頁，共53頁，2022年，5月20日，8點46分，星期二真值表與范式的關系 AB當且僅當A與B有相同的真值表，又當且僅當A與B有相同的主析取范式（主合取范式）。真值表與主析取范式（主合取范式）是描述命題公式標準形式的兩種不同的等價形式。 n個命題變項共可產(chǎn)生2n個極小項（極大項）可以產(chǎn)生的主析取范式（主合取范式）數(shù)目為：第45頁，共53頁，2022年，5月20日，8點46分，星期二本章主要內容等值式與等值演算。基本的等值式，其中含：雙重否定律、冪等律、交換律、結合律、分配律、德摩根律、吸收律、零律、同一律、排中律、矛盾律、蘊含等值式、等價等值式、假言易位、等價否定等值式、歸謬論。與主析取范式及主合取范式有關的概念：簡單合取式、簡單析取式、析取范式、合取范式、極小項、極大項、主析取范式、主合取范式。 第46頁，共53頁，2022年，5月20日，8點46分，星期二本章學習要求 深刻理解等值式的概念。牢記24個基本等值式，這是等值演算的基礎；能熟練地應用它們進行等值演算。 了解簡單析取式、簡單合取式、析取范式、合取范式的概念。 深刻理解極小項及極大項的定