07879離散數(shù)學-屈婉玲(數(shù)理邏輯)1.3-4

1、1.3 命題邏輯等值演算 等值式基本等值式等值演算置換規(guī)則1等值式 定義 若等價式AB是重言式，則稱A與B等值，記作AB，并稱AB是等值式說明：定義中，A,B,均為元語言符號, A或B中可能有啞元出現(xiàn).例如，在 (pq) (pq) (rr)中，r為左邊公式的啞元. 用真值表可驗證兩個公式是否等值請驗證：p(qr) (pq) r p(qr) (pq) r 2基本等值式 雙重否定律 : AA等冪律： AAA, AAA交換律: ABBA, ABBA結(jié)合律: (AB)CA(BC) (AB)CA(BC)分配律: A(BC)(AB)(AC) A(BC) (AB)(AC)3基本等值式(續(xù))德摩根律 : (A

2、B)AB (AB)AB吸收律: A(AB)A, A(AB)A零律: A11, A00 同一律: A0A, A1A排中律: AA1矛盾律: AA04基本等值式(續(xù))蘊涵等值式: ABAB等價等值式: AB(AB)(BA)假言易位: ABBA等價否定等值式: ABAB歸謬論: (AB)(AB) A注意:A,B,C代表任意的命題公式牢記這些等值式是繼續(xù)學習的基礎(chǔ)5等值演算與置換規(guī)則 等值演算: 由已知的等值式推演出新的等值式的過程置換規(guī)則：若AB, 則(B)(A) 等值演算的基礎(chǔ)： (1) 等值關(guān)系的性質(zhì)：自反、對稱、傳遞 (2) 基本的等值式 (3) 置換規(guī)則 6應(yīng)用舉例證明兩個公式等值 例1 證

3、明 p(qr) (pq)r證 p(qr) p(qr) （蘊涵等值式，置換規(guī)則） (pq)r （結(jié)合律，置換規(guī)則） (pq)r （德摩根律，置換規(guī)則） (pq) r （蘊涵等值式，置換規(guī)則）說明:也可以從右邊開始演算（請做一遍） 因為每一步都用置換規(guī)則，故可不寫出 熟練后，基本等值式也可以不寫出 7應(yīng)用舉例證明兩個公式不等值例2 證明: p(qr) (pq) r 用等值演算不能直接證明兩個公式不等值,證明兩個公式不等值的基本思想是找到一個賦值使一個成真,另一個成假. 方法一 真值表法（自己證） 方法二 觀察賦值法. 容易看出000, 010等是左邊的成真賦值，是右邊的成假賦值. 方法三 用等值演

4、算先化簡兩個公式，再觀察.8應(yīng)用舉例判斷公式類型 例3 用等值演算法判斷下列公式的類型(1) q(pq) 解 q(pq) q(pq) （蘊涵等值式） q(pq) （德摩根律） p(qq) （交換律，結(jié)合律） p0 （矛盾律） 0 （零律）由最后一步可知，該式為矛盾式. 9例3 (續(xù))(2) (pq)(qp) 解 (pq)(qp) (pq)(qp) （蘊涵等值式） (pq)(pq) （交換律） 1由最后一步可知，該式為重言式.問：最后一步為什么等值于1？ 10例3 (續(xù))(3) (pq)(pq)r) 解 (pq)(pq)r) (p(qq)r （分配律） p1r （排中律） pr （同一律）這不是

5、矛盾式，也不是重言式，而是非重言式的可滿足式.如101是它的成真賦值,000是它的成假賦值.總結(jié)：A為矛盾式當且僅當A0 A為重言式當且僅當A1說明：演算步驟不惟一,應(yīng)盡量使演算短些111.4 聯(lián)結(jié)詞全功能集 復合聯(lián)結(jié)詞 排斥或 與非式 或非式真值函數(shù)聯(lián)結(jié)詞全功能集12復合聯(lián)結(jié)詞 排斥或: pq(pq)(pq)與非式: pq(pq)或非式: pq(pq) 13真值函數(shù) 問題：含n個命題變項的所有公式共產(chǎn)生多少個互不相同的真值表？ 答案為 個，為什么？定義 稱定義域為000, 001, , 111，值域為0,1的函數(shù)是n元真值函數(shù)，定義域中的元素是長為n的0,1串. 常用F:0,1n0,1 表示

6、F是n元真值函數(shù). 共有 個n元真值函數(shù). 例如 F:0,120,1，且F(00)=F(01)=F(11)=0，F(xiàn)(01)=1，則F為一個確定的2元真值函數(shù).14命題公式與真值函數(shù) 對于任何一個含n個命題變項的命題公式A，都存在惟一的一個n元真值函數(shù)F為A的真值表.等值的公式對應(yīng)的真值函數(shù)相同.下表給出所有2元真值函數(shù)對應(yīng)的真值表, 每一個含2個命題變項的公式的真值表都可以在下表中找到. 例如：pq, pq, (pq)(pq)q) 等都對應(yīng)表中的152元真值函數(shù)對應(yīng)的真值表16聯(lián)結(jié)詞的全功能集 定義 在一個聯(lián)結(jié)詞的集合中，如果一個聯(lián)結(jié)詞可由集合中的其他聯(lián)結(jié)詞定義，則稱此聯(lián)結(jié)詞為冗余的聯(lián)結(jié)詞，否則稱為獨立的聯(lián)結(jié)詞.例如,在聯(lián)結(jié)詞集, , , , 中，由于 pqpq,所以，為冗余的聯(lián)結(jié)詞; 類似地，也是冗余的聯(lián)結(jié)詞. 又在, , 中，由于 pq(pq)，所以，是冗余的聯(lián)結(jié)詞. 類似地，也是冗余的聯(lián)結(jié)詞. 17聯(lián)結(jié)詞的全功能集(續(xù))定義 設(shè)S是一個聯(lián)結(jié)詞集合，如果任何n(n1) 元真值函數(shù)都可以由僅含S中的聯(lián)結(jié)詞構(gòu)成的公式表示，則稱S是聯(lián)結(jié)詞全功能集.說明： 若S是聯(lián)結(jié)詞全功能集，則任何命題公式都可用S中的聯(lián)結(jié)詞表示. 若S1, S2是兩個聯(lián)結(jié)詞集合，且S1 S2. 若S1是全功能集，則S2也是全