第2章 命題邏輯的等值演算

1、楊建林第二章第二章 命題邏輯的等值演算命題邏輯的等值演算2.1 等值式等值式等值式l定義2.1 設(shè)A、B是兩個公式，若AB是重言式，則稱A與B是等值的，記以AB。l類似：x*x+2*x+1 (x+1) 2l例：證明p p q ql等值定理 公式A、B等值的充要條件是公式A與B在任意解釋I下，其真值相同。（證明略）等值式等值式l在定義中，要注意符號“”不是聯(lián)結(jié)詞符，他是A與B等值的一種記法。l千萬不能將與混為一談等值式等值式l等值的性質(zhì)自反性自反性 A A對稱性對稱性 若若A B，則則B A傳遞性傳遞性 若若A B，B C，則則A C基本等值公式基本等值公式1) 雙重否定律： AA 2) 等冪律

2、AA AAA A基本等值式基本等值式 3) 交換律 AB BAAB BAA B B A基本等值式基本等值式 4)結(jié)合律A(BC) (AB)CA(BC) (AB)C基本等值式基本等值式 5) 分配律A(BC) (AB)(AC)A(BC) (AB)(AC)A (B C) (A B) (A C) (A B) C基本等值式基本等值式 6)摩根律(AB) AB(AB) AB(A B) A B(A B) (A B) ( A B)基本等值式基本等值式 7) 吸收律 A(AB) A，A(AB) A；8) 零律：A0 0A1 1基本等值式基本等值式 9) 同一律：A0 AA1 A基本等值式基本等值式 10)排中

3、律A A 111)矛盾式A A 012)蘊(yùn)涵等值式AB AB基本等值式基本等值式 13)等價等值式A B (A B)(B A)14)假言易位A B B A 15)等價否定等值式A B A B 基本等值式基本等值式 16)歸謬論(A B) (A B) A 等值演算等值演算l 稱由已知的等值式推演出另外一些等值式的過程為等值演算置換規(guī)則l對公式A中的子公式，用與之等值的公式代換稱為置換l置換規(guī)則：公式A的子公式置換后，A化為公式B，則A Bl若公式A是重言式，置換后，A化為公式B，則B也是重言式代入規(guī)則l代入規(guī)則：公式中代入的只能是命題變元，而不能是復(fù)合命題公式中代入的只能是命題變元，而不能是復(fù)合

4、命題對公式中某命題變項(xiàng)施以代入，必須對該公式中出現(xiàn)對公式中某命題變項(xiàng)施以代入，必須對該公式中出現(xiàn)的所有同一命題變項(xiàng)代替同一公式的所有同一命題變項(xiàng)代替同一公式代入規(guī)則l（rs）代替p，記作lA是一個公式，對A使用代入規(guī)則得到公式B，若A是重言式，則B也是重言式l例：判斷（rs） （rs）為重言式l置換與代入不同srp等值演算舉例l例1 證明：(p(qr)(qr)(pr) rl例2 證明(pq)(p(q r)(pq) 1(pq)(p(q r)(pq)(pr) 1(pq)(pq) (pq)(pqrs) (rpqs) (r (p q) s命題公式和真值表的關(guān)系pqAB A001100111010001

5、11100命題公式和真值表的關(guān)系n從從1來列寫來列寫nA () () ()n()寫成合取式，表示一種寫成合取式，表示一種A值為真的情況。如值為真的情況。如p=0，q=0時為真，時為真， ()寫成寫成 p qn0值取值取 p形式形式/每個合取式只在唯一的一個解釋下為真每個合取式只在唯一的一個解釋下為真nA ( p q) ( p q) (p q)命題公式和真值表的關(guān)系n從從0來列寫來列寫nB () () n由由1列寫的方式進(jìn)行轉(zhuǎn)化：列寫的方式進(jìn)行轉(zhuǎn)化： B () ()nB () ()n()寫成析取式，表示一種寫成析取式，表示一種B值為假的情況。如值為假的情況。如p=1，q=0時為假時為假， ()

6、寫成寫成p q， ()寫成寫成 p qn1值取值取 p形式形式nA p q 可推知：可推知：( p q) ( p q) (p q) p q作業(yè)l 2.4. 用等值演算法證明下面等值式:p(pq)(pq)(pq)(pq)(pq)(pq)(pq)(pq)(pq)2.2 2.2 析取范式與合取范式析取范式與合取范式判定問題判定問題l能否給出一個可行方法，對任意的公式，判定其是否是永真公式。l因?yàn)橐粋€命題公式的解釋的數(shù)目是有窮的，所以命題邏輯的判定問題是可解的(可判定的，可計(jì)算的)，亦即，命題公式的永真、永假性是可判定的?；靖拍頻 原子l 文字l 簡單合取式、簡單析取式l 析取范式、合取范式l 極小

7、項(xiàng)、極大項(xiàng)l 主析取范式、主合取范式范式范式l定 義 2 . 2 原 子 或 原 子 的 否 定 稱 為 文 字 。 例如，p，p是文字。l有限個文字組成的析取式稱為一個簡單析取式，或者子句；l有限個文字組成的合取式稱為一個簡單合取式，或者短語。 l特別，一個文字既可稱為是一個簡單析取式，也可稱為是一個簡單合取式。l例如，p，pq，pq 是簡單析取式，p，pq，pq 是簡單合取式。 范式范式l定義2.3 有限個簡單合取式的析取式稱為析取范式；有限個簡單析取式的合取式稱為合取范式。l特別， 一個文字既可稱為是一個合取范式，也可稱為是一個析取范式。 一個簡單析取式、簡單合取式既可看做是合取范式，也

8、可看做是析取范式。l例如， p，pq，pq，(pq)(pq)是析取范式。 p，pq，pq，(pq)(pr)是合取范式。 范式范式l析取范式與合取范式具有下面性質(zhì)：一個析取范式是矛盾式當(dāng)且僅當(dāng)它的每個簡單合取式都是矛盾式一個合取范式是重言式當(dāng)且僅當(dāng)它的每個簡單析取式都是重言式定理定理l 定理2.1( 范式存在定理) 對于任意命題公式，都存在等值于它的析取范式和合取范式。 l證明：對于公式G，通過如下算法即可得出等值于G的范式：步1. 使用基本等值式，將G中的邏輯聯(lián)結(jié)詞，刪除。步2. 使用(H) H和摩根律，將G中所有的否定號都放在原子之前。 步3. 反復(fù)使用分配律，即可得到等值于G的范式。 例：

9、例： l(p(qr)s (p(qr)s p(qr)s p(qr)s .(析取范式) (ps)(qr) (psq)(psr) (合取范式) 主范式主范式l 定義2. 4 設(shè)p1,pn是n個不同原子，一個簡單合取式如果恰好包含所有這n個原子或其否定，且其排列順序與p1,pn的順序一致，則稱此簡單合取式為關(guān)于p1,pn的一個極小項(xiàng)。l 顯然，共有2n個不同的極小項(xiàng)。 l 例如:對原子對原子p，q，r而言，而言，pq r， pq r，p q r都是都是極小項(xiàng)，但是，極小項(xiàng)，但是，p， p q不是極小項(xiàng)，不是極小項(xiàng)，對原子對原子p，q而言而言, , p q是極小項(xiàng)。是極小項(xiàng)。 l 對于n個原子p1,pn

10、而言，其不同的解釋共有2n個l 對于p1,pn的任一個極小項(xiàng)m，2n個解釋中，有且只有一個解釋使m取1值l 例：對p，q，r而言，pqr是極小項(xiàng)，解釋p，q，r使該極小項(xiàng)取1值，其他解釋都使該極小項(xiàng)取0值。l 如果將真值1，0看做是數(shù)，則每一個解釋對應(yīng)一個n位二進(jìn)制數(shù)。l 假設(shè)使極小項(xiàng)m取1值的解釋對應(yīng)的二進(jìn)制數(shù)為i，今后將m記為mi。例例:l 對p，q，r而言，pqr是極小項(xiàng)l 解釋p，q，r使該極小項(xiàng)取1值，解釋p，q，r 對應(yīng)的二進(jìn)制數(shù)是2 (010)l 于是pqr記為m2極小項(xiàng) 解釋 記法 pqr 000m0 pqr 001m1 pqr 010m2 pqr 011m3 pqr 100m

11、4 pqr 101m5 pqr 110m6 pqr 111m7 對對p，q，r而言，而言，8個極小項(xiàng)與其對應(yīng)個極小項(xiàng)與其對應(yīng)的解釋如下：的解釋如下： 12210,.,nmmmml 一般地，對p1,pn而言，2n個極小項(xiàng)為主析取范式l 定義2.5 設(shè)命題公式G中所有不同原子為p1,pn，如果G的某個析取范式G中的每一個簡單合取式都是關(guān)于p1,pn的一個極小項(xiàng)，且所有簡單合取式按照從小到大的順序出現(xiàn)，則稱G為G的主析取范式。l 永假公式的主析取范式用0表示。定理定理1.31.3l 定理2.2（主析取范式存在唯一性定理）對于命題公式G，都存在等值于它的主析取范式，并且是唯一的。 l 證明：由定理2.

12、1知，存在析取范式G，使得G G。設(shè)G中所有不同原子為p1,pn，對于G中每一個簡單合取式Gi進(jìn)行檢查，如果Gi不是關(guān)于p1,pn的極小項(xiàng)，則Gi中必然缺少原子p j1,pjk。 l因?yàn)椋簁221iiijkjkj1j1iimmm)PP()PP(GG于是將G中非極小項(xiàng)Gi化成了一些極小項(xiàng)之析取。對G中其他非極小項(xiàng)也做如上處理，最后得等值于G的主析取范式G*。 例例l 求求 (rp) (q (p r)主析取范式。 l 解：(rp)(q(pr) (rp)(qp)(qr)(pr)(qp)(qr)(pr)(qq)(qp)(rr)( (qr)(pp)(pqr)(pqr)(pqr)(pqr) 求 (pq)(

13、pr)(qr)主析取范式 (pq)(pr)(qr)的主析取范式為：(pqr) (pqr) (pqr) (pqr) pq rG0 000001 10 10001111000101011011 111定理l設(shè)公式G，H是關(guān)于原子p1,pn的兩個主析取范式。 如果G，H不完全相同，則G，H不等值。l證明：因?yàn)镚，H不完全相同，所以或者G中有一個極小項(xiàng)不在H中； 或者反之。不妨設(shè)極小項(xiàng)mi 在G中而不在H中。 于是根據(jù)極小項(xiàng)的性質(zhì)，二進(jìn)制數(shù)i所對應(yīng)的關(guān)于p1,pn的解釋Ii使mi取1值，從而使公式G取1值。 Ii使所有不是mi的極小項(xiàng)取0值，從而使公式H取0值。 故G，H不等值。 定理l對于任意公式G

14、，存在唯一一個與G等值的主析取范式。 永真永假性的判定 l引理 簡單合取式是永假的當(dāng)且僅當(dāng)至少有一個原子及其否定(也稱互補(bǔ)對)同時在此簡單合取式中出現(xiàn)。 l證明：充分性，若有一個原子p及其否定p同時出現(xiàn)在簡單合取式中，則此簡單合取式有形式：pp顯然，不管是什么解釋I，pp在I下取0值，于是此簡單合取式在I下取0值，故此簡單合取式永假。永真永假性的判定 必要性，若簡單合取式永假，而任意原子及其否定均不同時在簡單合取式中出現(xiàn)。那么，取這樣的解釋I：指定帶有否定號的原子取0值，不帶否定號的原子取1值，顯然，此簡單合取式在這個解釋I下取1值，與此簡單合取式永假矛盾。 定理l命題公式G是永假的當(dāng)且僅當(dāng)在

15、等值于它的析取范式中，每個簡單合取式均至少包含一個原子及其否定。 l證明： 設(shè)G的析取范式如下：G1Gn其中Gi是簡單合取式，i=1，n。顯然，公式G永假的充要條件是每個Gi永假。 再根據(jù)引理，此定理結(jié)論顯然成立。 例例判斷公式 (pq)(qr)(rp)是否永假?解： (pq)(qr)(rp)(pq)(qr)(rp)(pq)(qq)(pr)(qr)(rp)(pqr)(qqr)(prr)(q rr)(pqp)(qqp)(prp) (qrp) 故公式(pq)(qr)(rp)不是永假的。 例判斷公式 (pq)pq是否永假?解： (pq)pq (pq)pq (ppq)(qpq)故公式(pq)pq是永假

16、的。 其它方法 l 把公式化成主析取范式，公式永假時，主析取范式?jīng)]有極小項(xiàng)； 公式永真時，主析取范式有全部極小項(xiàng)。l 一種判定算法對任給要判定的命題公式G，設(shè)其中有原子p1,p2,pn， 令p1取1值，求G的真值，或?yàn)?，或?yàn)?，或成為新公式G1且其中只有原子p2, pn， 再令p1取0值，求G真值， 如此繼續(xù)，到最終只含0或1為止， 若最終結(jié)果全為1，則公式G永真，若最終結(jié)果全為0，則公式G永假，若最終結(jié)果有1，有0，則是可滿足的。(二叉樹) 例例(p qr) (pq)(pr) p取取1值值 p取取0值值 (qr) qrrrq取取1值值 q取取0值值 r取取1值值 r取取0值值 1111主合

17、取范式主合取范式l定義 設(shè)p1,pn是n個不同原子，一個簡單析取式如果恰好包含所有這n個原子或其否定，且其排列順序與p1,pn的順序一致，則稱此簡單析取式為關(guān)于p1,pn的一個極大項(xiàng)。l顯然，共有2n個不同的極大項(xiàng)。 l例如，對原子p，q，r而言，pqr，pqr，pqr都是極大項(xiàng)，但是，p，pq不是極大項(xiàng)，而pq對原子p，q而言是極大項(xiàng)。 l顯然，對于n個原子p1,pn而言，其不同的解釋共有2n個，對于p1,pn的任一個極大項(xiàng)M，2n個解釋中，有且只有一個解釋使M取0值。l例如，對p，q，r而言，pqr是極大項(xiàng)，解釋p， q，r使該極大項(xiàng)取0 值，其他解釋都使該極大項(xiàng)取1值。例例:l對p，q，

18、r而言，pqr是極大項(xiàng)，解釋p, q,r 使該極大項(xiàng)取0值，解釋p, q,r對應(yīng)的二進(jìn)制數(shù)是5 (101) ，于是pqr記為M5。 對p，q，r而言，8個極大項(xiàng)與其對應(yīng)的解釋如下：極大項(xiàng) 為假解釋 記法 pqr 111M7 pqr 110M6 pqr 101M5 pqr 100M4 pqr 011M3 pqr 010M2 pqr 001M1 pqr 000M0 主合取范式l 假設(shè)使極大項(xiàng)M取0值的解釋對應(yīng)的二進(jìn)制數(shù)為i，今后將M記為Mi。l 將極大項(xiàng)中各命題變項(xiàng)看成為0，其否定看成為1, 按順序排列后的二進(jìn)制數(shù)為i,該極大項(xiàng)表示為Mi;（與清華版教材的說法不一致，自成體系）l 注意：M1不是p

19、qr，而是pqr 主合取范式l 定義1.16 設(shè)命題公式G中所有不同原子為p1,pn，如果G的某個合取范式G中的每一個簡單析取式，都是關(guān)于p1,pn的一個極大項(xiàng)，則稱G為G的主合取范式。l 僅由極大項(xiàng)組成的合取式稱為命題公式的主合取范式。l 例如，在某命題公式A中p,q,r為p,q,r 和 p,q,r時真值為0，則A的主合取范式可記作為：)7, 1()()(RQPRQPl一般地，對p1,pn而言，2n個極大項(xiàng)為l永真公式的主合取范式用1表示。 12210,.,nMMMM定理定理l對于命題公式G，都存在等值于它的主合取范式，且唯一。 求主合取范式的方法l等值演算法l利用公式的主析取范式求公式的主

20、合取范式l用真值表求公式的主合取范式求主合取范式的方法l 用等值演算法求給定公式A的主合取范式的步驟如下l (1)求A的合取范式A;l (2)若A中的某簡單析取式B中不含命題變項(xiàng)pi及其否定形式pi ，則將B做如下等值演算：B(B pi)(B pi)l (3)消去重復(fù)出現(xiàn)的命題變項(xiàng)，重言式的簡單析取式及重復(fù)出現(xiàn)的極大項(xiàng)；l (4)將極大項(xiàng)按角標(biāo)由小到大排列，并且可用抽象符號表示之。由主析取范式可直接求出主合取范式 例如，上面的例3 主析取范式已經(jīng)求得，為那么，它的主合取范式為：)7,6,5,3, 1()4,2,0()()()(RQPRQPRQPRQP)(有下列結(jié)論，請關(guān)注： l 任意兩個極小項(xiàng)

21、的合取式為永假式，l 全體極小項(xiàng)的析取式為永真式。l 任意兩個極大項(xiàng)的析取式為永真式，l 全體極大項(xiàng)的合取式為永假式。作業(yè)l 2.5. 求下列公式的主析取范式求下列公式的主析取范式, 并求成真賦值并求成真賦值:再根據(jù)主析再根據(jù)主析取范式直接寫出對應(yīng)的主合取范式取范式直接寫出對應(yīng)的主合取范式l (1)( pq) ( qp)l (2) (pq) qrl (3)(p (qr) (pqr)l 2.6. 求下列公式的主合取范式求下列公式的主合取范式, 并求成假賦值并求成假賦值:l (1) (q p) pl (2)(pq) ( pr)l (3)(p (pq) r2.3 聯(lián)結(jié)詞的完備集聯(lián)結(jié)詞的完備集命題聯(lián)結(jié)詞的個數(shù)l一元聯(lián)結(jié)詞的個數(shù)