第二章命題邏輯等值演算

1、第二章 命題邏輯等值演算2.1 2.1 等值式等值式定義定義2.1 A B為重言式為重言式等值等值A(chǔ) B從表中可知它是重言式，即(pq) (pq)p (qr) (pq)r(pq)r (pq)r等值演算等值演算1616組重要的等值式組重要的等值式: :1. 雙重否定律雙重否定律 A A 2. 冪等律冪等律 A AA , A AA 3. 交換律交換律 AB BA ， AB BA4. 結(jié)合律結(jié)合律 (AB)C A(BC) (AB)C A(BC)7. 吸收律吸收律 A(AB) A ， A(AB) A 8. 零律零律 A1 1 , A0 0 9. 同一律同一律 A0 A ， A1 A 10. 排中律排中

2、律 AA 1 11. 矛盾律矛盾律 AA 0 12. 蘊涵等值式蘊涵等值式 AB AB 13. 等價等值式等價等值式 (A B) (AB)(BA) 14. 假言易位假言易位 AB BA 15. 等價否定等值式等價否定等值式 A B A B 16. 歸謬論歸謬論 (AB)(AB) A 由于A,B,C可以代表任意的公式，稱這樣的等值式為等值式模式等值式模式，每個等值式模式都給出了無窮多個同類型的具體的等值式。例如，在蘊涵等值式中，取A=p，B=q時，得等值式 pq pq 當取A=pqr，B=pq時，得等值式 (pqr)(pq) (pqr)(pq) 這些具體的等值式都被稱為原來的等值式模式的代入實例

3、代入實例。 置換規(guī)則置換規(guī)則 設(shè)(A)是含公式A的命題公式，(B)是用公式B置換了(A)中所有的A后得到的命題公式，若BA，則(B) (A). 例如：(pq)r (pq)r （蘊含等值式、置換規(guī)則）AB (pq)r （蘊含等值式、置換規(guī)則）(pq)r （得摩根律、置換規(guī)則）(pr)(qr) （分配律、置換規(guī)則）公式之間的等值關(guān)系具有自反性 A A對稱性 若AB，則 B A傳遞性 若AB，B C ，則 A C所以上述演算中得到的公式彼此之間都是等值的。 在演算的每一步都用到了置換規(guī)則，因而在以下的演算中，置換規(guī)則均不標出。等值演算的用途： (1) 驗證等值式例例2.3 用等值演算法驗證等值式：

4、(pq)r (pr)(qr) 證證: 可以從左邊開始演算，也可以從右邊開始演算。 現(xiàn)在從右邊開始演算。 (pr)(qr) （ p r)(q r)(p q ) r (p q ) r (pq)r 一般情況下，不能用等值演算法直接驗證兩個公式不等值。例2.4 證明：(pq)r p(qr)證：證： 方法一：真值表法。 方法二：觀察法。易知，010是(pq)r的成假賦值，而010是p(qr)的成真賦值，所以原不等值式成立。方法三：設(shè)A=(pq)r, B=p(qr)A= (pq)r (pq)r (pq)r (pq)r B= p(qr) p(qr) pqr 容易觀察到，000，010是A的成假賦值，而它們是

5、B的成真賦值。(2) 將命題公式化簡及判斷公式類型例2.5 用等值演算法判斷下列公式的類型。永真式永真式 (pq) p q (pq) p q (p q) p) q( (p q) p) q( (p q) p) q(p p)(q p)q(1 (q p) q(q p) q(q q ) p1 p1矛盾式矛盾式(2) (p (p q) ) r (p p q ) r (p p q ) r 0 r 0 最后結(jié)果說明(3)中公式不是重言式，00，01都是成假賦值，并且也不是矛盾式，因為10，11都是成真賦值。(3) p (p q ) p)q) p (p q ) p) q) p (p p) (q p) ) q)

6、 p (0 (q p) ) q) p (q p q) p 1 p例2.6 在某次研討會的中間休息時間，3名與會者根據(jù)王教授的口音對他是哪個省市的人進行了判斷： 甲說王教授不是蘇州人，是上海人 乙說王教授不是上海人，是蘇州人 丙說王教授既不是上海人，也不是杭州人聽完以上3人的判斷后，王教授笑著說，你們3人中有一人說得全對，有一人說對了一半，另一人說得全不對。試用邏輯演算法分析王教授到底是哪里的人？解 設(shè)命題 p：王教授是蘇州人。 q：壬教授是上海人。 r：王教授是杭州人。p, q, r 中必有一個真命題，兩個假命題，要通過邏輯演算將真命題找出來。 設(shè)每種數(shù)字標準形都能提供很多信息，如代數(shù)式的因式

7、分解可判斷代數(shù)式的根情況。邏輯公式在等值演算下也有標準形-范式 （公式的規(guī)范化）2.2 析取范式與合取范式定義定義2.22.2 命題變項及其否定統(tǒng)稱作文字文字。僅由有限個文字構(gòu)成的析取式稱作簡單析取式簡單析取式。僅由有限個文字構(gòu)成的合取式稱作簡單合取式簡單合取式。如：p、p、pqr等是簡單析取式p、p、 pqr 等是簡單合取式 注注: :一個文字既是簡單析取式，又是簡單合取式。 為方便起見，有時用A1,A2,As表示s個簡單析取式或s個簡單合取式。 定理定理2.1 2.1 （1）一個簡單析取式是重言式重言式當且僅當它同時含某個 命題變項及它的否定式。 （2）一個簡單合取式是矛盾式矛盾式當且僅當

8、它同時含有某 個命題變項及它的否定式。證明：證明： 設(shè)Ai是含n個文字的簡單析取式，若Ai中既含有某個命題變項pj，又含有它的否定式pj，由交換律、排中律和零律可知，Ai為重言式。反之，若Ai為重言式，則它必同時含某個命題變項及它的否定式，否則，若將Ai中的不帶否定號的命題變項都取0，帶否定號的命題變項都取1，此賦值為Ai的成假賦值，這與Ai是重言式相矛盾。如：pp，ppr都是重言式 , pq，pqr都不是重言式。 定義定義2.32.3 （1）由有限個簡單合取式構(gòu)成的析取式稱為析取范式析取范式。 （2）由有限個簡單析取式構(gòu)成的合取式稱為合取范式合取范式。 （3）析取范式與合取范式統(tǒng)稱為范式范式

9、。 設(shè)Ai(i=1,2,s)為簡單合取式，A=A1A2As為析取范式。 設(shè)Ai(i=1,2,s)為簡單析取式，A=A1A2As為合取范式 如：A1=pq，A2=qr，A3=p則由A1,A2,A3構(gòu)造的析取范式為A=A1A2A3=(pq)(qr)p 同樣，取A1=pqr，A2=pq，A3=r，則由A1,A2,A3組成的合取范式為A=A1A2A3=(pqr)(pq)r 注意： pqr 既是一個簡單合取式構(gòu)成的析取范式，又是由三個簡單析取式構(gòu)成的合取范式。 同樣如 pqr范式有如下性質(zhì): 定理定理2.22.2 （1）一個析取范式是矛盾式矛盾式當且僅當它的每個簡單每個簡單合取式都是矛盾式合取式都是矛盾

10、式。 （2）一個合取范式是重言式重言式當且僅當它的每個簡單每個簡單析取式都是重言式析取式都是重言式。 定理定理2.32.3 （范式存在定理范式存在定理）任一命題公式都存在著與之等值的析取范式與合取范式。 證明證明 首先，我們觀察到在范式中不出現(xiàn)聯(lián)結(jié)詞與 。由蘊涵等值式與等價等值式可知 AB AB A B (AB)(AB) （第1步）因而在等值的條件下，可消去任何公式中的聯(lián)結(jié)詞和 其次，在范式中不出現(xiàn)如下形式的公式： A, (AB), (AB)對其利用雙重否定律和德摩根律，可得 A A， (AB) AB， (AB) AB （第2步）再次，在析取范式中不出現(xiàn)如下形式的公式： A(BC) 在合取范式

11、中不出現(xiàn)如下形式的公式： A(BC) 利用分配律，可得 A(BC) (AB)(AC) A(BC) (AB)(AC) （第3步）由第1、2、3步，可將任一公式化成與之等值的析取范式或合取范式。 據(jù)此定理，求范式可使用如下步驟： 1.消去聯(lián)結(jié)詞 ， 2.否定號的消去（利用雙重否定律）或內(nèi)移（利用德摩根律）。 3.利用分配律：利用對的分配律求析取范式，對的分配律求合取范式。 例例2.7 求公式 (pq) r 的析取范式與合取范式： 1）先求合取范式(pq) r (pq) r （消去） (pq)r)(r(pq) （消去 ） (pq)r)(rpq) （消去） (pq)r)(pqr) （否定號內(nèi)移） (p

12、r)(qr)(pqr) （對分配律）2）求析取范式 求析取范式與求合取范式的前兩步是相同的，只是在利用分配律時有所不同。因而可以用（1）中前四步的結(jié)果，接著進行對分配律演算。 (pq) r (pq)r)(pqr) (pqp)(pqq)(pqr) (rp)(rq)(rr) (pqr)(pr)(qr) 第二步和第三步結(jié)果都是析取范式，這正說明命題公式的析取范式是不唯一的。同樣，合取范式也是不唯一的。為了求出命題公式的唯一規(guī)范化的形式，再進一為了求出命題公式的唯一規(guī)范化的形式，再進一步的加以約束，得到主范式。步的加以約束，得到主范式。定義定義2.42.4 在含有n個命題變項的簡單合取式（簡單析取式）

13、中，若每個命題變項和它的否定式不同時出現(xiàn)，而二者之一必出現(xiàn)且僅出現(xiàn)一次，且第i個命題變項或它的否定式出現(xiàn)在從左算起的第i位上（若命題變項無角標，就按字典順序排列），稱這樣的簡單合取式（簡單析取式）為極小項極小項（極大項極大項）。 如： p q r , p q r極小項極小項是簡單合取式，反之呢？是簡單合取式，反之呢？n個命題變項共可產(chǎn)生2n個不同的極小項。(極大項)每個極小項都有且僅有一個成真賦值。若成真賦值所對應(yīng)的二進制數(shù)轉(zhuǎn)換為十進制數(shù)i，就將所對應(yīng)極小項記作mi.類似地，每個極大項只有一個成假賦值，將其對應(yīng)的十進制數(shù)i做極大項的角標，記作Mi。p,q形成的極小項與極大 項 p,q,r形成的

14、極小項與極大項觀察一下極大項與極小項的關(guān)系？定理定理2.4 設(shè)設(shè)mi與與Mi是命題變項是命題變項p1,p2,pn形形成的極小項和極大項，則成的極小項和極大項，則 mi Mi ，Mimi 定義定義2.5 2.5 設(shè)由設(shè)由n n個命題變項構(gòu)成的析取范式（合個命題變項構(gòu)成的析取范式（合取范式）中所有的簡單合取式（簡單析取式）都是取范式）中所有的簡單合取式（簡單析取式）都是極小項（極大項），則稱該析取范式（合取范式）極小項（極大項），則稱該析取范式（合取范式）為主析取范式為主析取范式（主合取范式主合取范式）。）。 定理定理2.5 任何命題公式都存在著與之等值的主析取任何命題公式都存在著與之等值的主析取

15、 范式和主合取范式，并且是唯一的。范式和主合取范式，并且是唯一的。 證證: : 這里只證主合取范式的存在性和唯一性。 首先證明存在性。 設(shè)A是任一含n個命題變項的公式。由范式存在定理可知，存在與A等值的合取范式A，即A A，若A的某個簡單析取式Ai中既不含命題變項pj，也不含它的否定式pj，則將Ai展成如下形式： Ai Ai0 Ai(pjpj) (Aipj)(Ajpj)繼續(xù)這一過程，直到所有的簡單析取式都含任意命題變項或它的否定式。若在演算過程中出現(xiàn)重復(fù)的命題變項以及極大項和重言式時，都應(yīng)“消去”：如用p代替pp，Mi代替MiMi，1代替重言式等。最后就將A化成與之等值的主合取范式A。 下面再

16、證明唯一性： 假設(shè)某一命題公式A存在兩個與之等值的主合取范式B和C，即AB且AC，則BC。由于B和C是不同的主合取范式，不妨設(shè)極大項Mi只出現(xiàn)在B中而不出現(xiàn)在C中。于是，角標i的二進制表示為B的成假賦值，而為C的成真賦值。這與 BC矛盾，因而B與C必相同。 為了醒目和便于記憶，求出某公式的主析取范式（主合取范式）后，將極小項（極大項）都用名稱寫出，并且按極小項（極大項）名稱的角標由小到大順序排列。 例例2.8 求例2.7中公式的主析取范式和主合取范式。 解解 （1）求主析取范式 :在例2.7中已給出的公式的析取范式，即（pq） r(pqr)(pr)(qr)注意，因為公式含三個命題變項，所以極小

17、項均由三個文字組成。 （pr）p（qq）r (pqr)(pqr) m1m3 qr (pp)qr (pqr）(pqr)m3m7于是 (pq) r m1m3m4m7 記作 (1，3，4，7）(2)再求主合取范式：由例2.7已求出公式的合取范式，即(pq） r (pr)(qr)(pqr)(pr) (p(qq)r)(pqr)(pqr)M0M2(qr) (pp)qr)(pqr)(pqr) M2M6 于是，(pq）r M0M2M5M6 記作（0，2，5，6）對應(yīng)一個確定的命題公式，它的成真成假賦值個數(shù)是確定的，根據(jù)定理4，一旦求出公式的所有極小項，就能寫出公式的所有極大項，即極小項沒有出現(xiàn)的下標，就是極大

18、項的下標。幾點說明：1、由公式的主析取范式求主合取范式。設(shè)公式A含n個命題變項， A的主析取范式含s(0s2n)個極小項即：Ami1 mi2 mi3 mis (0ij2n-1 ;j=1,2, ,s;)沒出現(xiàn)的極小項為 mj1,mj2 ,mj2n-s,它們的角標的二進制表示為A的成真賦值，因而A的主析取范式為 Amj1 mj2 mj3 mj2n-s由雙重否定定律：AA(mj1 mj2 mj3 mj2n-s) mj1 mj2 mj3 mj2n-s Mj1 Mj2 Mj3 Mj2n-s （定理4）同理，由主合取范式也可求出主析取范式。2重言式與矛盾式的主合取范式 重言式無成假賦值，因而主合取范式不含

19、任何極大項。將重言式的主合取范式記為1。而主析取范式含全部2n個極小項。矛盾式無成真賦值，因而主析取范式不含任何極小項。將矛盾式的主析取范式記為0。而主合取范式含全部2n個極大項。可滿足式，它的主析取范式中至少含一個極小項。3主析取范式有多少種不同的情況 ？這與真值表相同，可以看出，真值表與主析取范式（主合取范式）是描述命題公式標準形式的兩種不同的等價形式。由主析取范式（主合取范式）立刻能確定 A的真值表，反之亦然。n個命題變項2n個極小項 22n種主析取范式用途：判斷兩命題公式是否等值；判斷命題公式的類型；求命題公式的成真、成假賦值；應(yīng)用。例2.9 分析和解決實際問題。某科研所要從3名科研骨

20、干A，B，C中挑選12名出國進修。由于工作需要，選派時要滿足下面3個條件，問所里應(yīng)如何選派他們? ()若A去，則C同去; (2)若B去，則C不能去; (3)者C不去，則A或B可以去。2.3 聯(lián)結(jié)詞的完備集聯(lián)結(jié)詞的完備集 元函數(shù)就是有個自變量的函數(shù)。 元真值函數(shù)元真值函數(shù)就是自變量和函數(shù)值都是真值（即或）的函數(shù)。其中F的自變量為n個命題變項記作：F：0，1n 0，1定義域： 0，1n =000,001,111值域：0，1； 具體如下：元真值函數(shù)2元真值函數(shù) 2.3 聯(lián)結(jié)詞的完備集聯(lián)結(jié)詞的完備集 一般地，n元真值函數(shù)共有多少個呢？ 每個自變量有2個取值方式，n個自變量共有2n 個不同取值方式。對n

21、個自變量的每個取值方式，函數(shù)值有2個取值方式，即為0或1，故n元真值函數(shù)共22n個。 每個真值函數(shù)，都可以找到許多與之等值的命題公式。例如，3元真值函數(shù)共有256個 F13 (2)pq (pq) (pq) (pq)(pq)(pq) 。但每個真值函數(shù)與唯一的主析?。ê先。┓妒降戎?。反過來，每個主析取范式對應(yīng)無窮多個與之等值的公式，所以每個真值函數(shù)對應(yīng)無窮多個與之等值的命題公式。由定理2.5可知，每個命題公式對應(yīng)唯一的與之等值的真值函數(shù)。2.3 聯(lián)結(jié)詞的完備集聯(lián)結(jié)詞的完備集 定義定義2.7 設(shè)S是一個聯(lián)結(jié)詞集合，如果任何n(n1)元真值函數(shù)都可以由僅含S中的聯(lián)結(jié)詞構(gòu)成的公式表示，則稱S是聯(lián)結(jié)詞完備集聯(lián)結(jié)詞完備集。 定理定理2.6 S=,是聯(lián)結(jié)詞完備集。 2.3 聯(lián)結(jié)詞的完備集聯(lián)結(jié)詞的完備集 證證: 因為任何n(n1)元真值函數(shù)都與唯一的一個主析取范式等值，而在主析取范式中僅含聯(lián)結(jié)詞,，所以S=,是聯(lián)結(jié)詞完備集。 推論推論 以下聯(lián)結(jié)詞集都是完備集：(1) S1=, (2) S2=, (3) S3=, (4) S4=, (5) S5=, 證證: (1)，(2)的成立是顯然的。 (3) 由于S=,是聯(lián)結(jié)詞完備集，因而任何真值函數(shù)都可以由僅含S中的聯(lián)結(jié)詞的公式表示。同時對于任意公式A,B,AB(AB) (AB),因而任意真值函數(shù)都可以由僅含S3 = ,