命題邏輯等值演算.ppt

1 1 3命題邏輯等值演算 p q是命題變項(xiàng) p q與 p q在4個(gè)賦值00 01 10 11下均有相同的真值 即 p q p q 的取值都為1 重言式 永真式 給定n個(gè)命題變項(xiàng) 按合式公式的規(guī)則可以形成無數(shù)個(gè)命題公式 n個(gè)命題變項(xiàng)共2n個(gè)賦值 每個(gè)賦值時(shí)命題公式的值為0或1 因此n個(gè)命題變項(xiàng)共生成22n個(gè)真值不同的命題公式 如n 2 共16個(gè)真值不同的命題公式 如何判斷那些命題公式具有相同的真值 2 等值式 定義若等價(jià)式A B是重言式 則稱A與B等值 記作A B 并稱A B是等值式說明 定義中 A B 均為元語言符號(hào) A或B中可能有啞元出現(xiàn) 例如 在 p q p q r r 中 r為左邊公式的啞元 用真值表可驗(yàn)證兩個(gè)公式是否等值請(qǐng)驗(yàn)證 p q r p q rp q r p q r 3 基本等值式 雙重否定律 A A等冪律 A A A A A A交換律 A B B A A B B A結(jié)合律 A B C A B C A B C A B C 分配律 A B C A B A C A B C A B A C 注意 A B C代表任意的命題公式 4 基本等值式 續(xù) 德 摩根律 A B A B A B A B吸收律 A A B A A A B A零律 A 1 1 A 0 0同一律 A 0 A A 1 A排中律 A A 1矛盾律 A A 0 注意 A B C代表任意的命題公式 5 基本等值式 續(xù) 蘊(yùn)涵等值式 A B A B等價(jià)等值式 A B A B B A 假言易位 A B B A等價(jià)否定等值式 A B A B歸謬論 A B A B A注意 A B C代表任意的命題公式牢記這些等值式是繼續(xù)學(xué)習(xí)的基礎(chǔ) 6 等值演算與置換規(guī)則 等值演算 由已知的等值式推演出新的等值式的過程置換規(guī)則 若A B 則 B A 等值演算的基礎(chǔ) 1 等值關(guān)系的性質(zhì) 自反 對(duì)稱 傳遞 2 基本的等值式 3 置換規(guī)則 7 應(yīng)用舉例 證明兩個(gè)公式等值 例1證明p q r p q r證p q r p q r 蘊(yùn)涵等值式 置換規(guī)則 p q r 結(jié)合律 置換規(guī)則 p q r 德摩根律 置換規(guī)則 p q r 蘊(yùn)涵等值式 置換規(guī)則 說明 也可以從右邊開始演算 請(qǐng)做一遍 因?yàn)槊恳徊蕉加弥脫Q規(guī)則 故可不寫出熟練后 基本等值式也可以不寫出 8 應(yīng)用舉例 證明兩個(gè)公式不等值 例2證明 p q r p q r用等值演算不能直接證明兩個(gè)公式不等值 證明兩個(gè)公式不等值的基本思想是找到一個(gè)賦值使一個(gè)成真 另一個(gè)成假 方法一真值表法 自己證 方法二觀察賦值法 容易看出000 010等是左邊的成真賦值 是右邊的成假賦值 方法三用等值演算先化簡兩個(gè)公式 再觀察 9 應(yīng)用舉例 判斷公式類型 例3用等值演算法判斷下列公式的類型 1 q p q 解q p q q p q 蘊(yùn)涵等值式 q p q 德摩根律 p q q 交換律 結(jié)合律 p 0 矛盾律 0 零律 由最后一步可知 該式為矛盾式 10 例3 續(xù) 2 p q q p 解 p q q p p q q p 蘊(yùn)涵等值式 p q p q 交換律 1由最后一步可知 該式為重言式 問 最后一步為什么等值于1 11 例3 續(xù) 3 p q p q r 解 p q p q r p q q r 分配律 p 1 r 排中律 p r 同一律 這不是矛盾式 也不是重言式 而是非重言式的可滿足式 如101是它的成真賦值 000是它的成假賦值 總結(jié) A為矛盾式當(dāng)且僅當(dāng)A 0A為重言式當(dāng)且僅當(dāng)A 1說明 演算步驟不惟一 應(yīng)盡量使演算短些 12 1 4聯(lián)結(jié)詞全功能集 復(fù)合聯(lián)結(jié)詞排斥或與非式或非式真值函數(shù)聯(lián)結(jié)詞全功能集 13 復(fù)合聯(lián)結(jié)詞 排斥或 異或 p q之中恰好有一個(gè)成立 p q p q p q 與非式 p與q的否定 p q p q 或非式 p或q的否定 p q p q 問題 多少個(gè)聯(lián)結(jié)詞最合適 14 真值函數(shù) 問題 含n個(gè)命題變項(xiàng)的所有公式共產(chǎn)生多少個(gè)互不相同的真值表 答案為個(gè) 為什么 定義稱定義域?yàn)?00 0 00 1 11 1 值域?yàn)?0 1 的函數(shù)是n元真值函數(shù) 定義域中的元素是長為n的0 1串 常用F 0 1 n 0 1 表示F是n元真值函數(shù) 共有個(gè)n元真值函數(shù) 例如F 0 1 2 0 1 且F 00 F 01 F 11 0 F 10 1 則F為一個(gè)確定的2元真值函數(shù) 15 命題公式與真值函數(shù) 對(duì)于任何一個(gè)含n個(gè)命題變項(xiàng)的命題公式A 都存在惟一的一個(gè)n元真值函數(shù)F為A的真值表 等值的公式對(duì)應(yīng)的真值函數(shù)相同 下表給出所有2元真值函數(shù)對(duì)應(yīng)的真值表 每一個(gè)含2個(gè)命題變項(xiàng)的公式的真值表都可以在下表中找到 例如 p q p q p q p q q 等都對(duì)應(yīng)表中的 16 2元真值函數(shù)對(duì)應(yīng)的真值表 17 聯(lián)結(jié)詞的全功能集 定義在一個(gè)聯(lián)結(jié)詞的集合中 如果一個(gè)聯(lián)結(jié)詞可由集合中的其他聯(lián)結(jié)詞定義 則稱此聯(lián)結(jié)詞為冗余的聯(lián)結(jié)詞 否則稱為獨(dú)立的聯(lián)結(jié)詞 例如 在聯(lián)結(jié)詞集 中 由于p q p q 所以 為冗余的聯(lián)結(jié)詞 類似地 也是冗余的聯(lián)結(jié)詞 又在 中 由于p q p q 所以 是冗余的聯(lián)結(jié)詞 但 無冗余的聯(lián)結(jié)詞 類似地 也是冗余的聯(lián)結(jié)詞 但 無冗余的聯(lián)結(jié)詞 18 聯(lián)結(jié)詞的全功能集 續(xù) 定義設(shè)S是一個(gè)聯(lián)結(jié)詞集合 如果任何n n 1 元真值函數(shù)都可以由僅含S中的聯(lián)結(jié)詞構(gòu)成的公式表示 則稱S是聯(lián)結(jié)詞全功能集 如果聯(lián)結(jié)詞全功能集不含冗余的聯(lián)結(jié)詞 則稱為極小功能集 說明 若S是聯(lián)結(jié)詞全功能集 則任何命題公式都可用S中的聯(lián)結(jié)詞表示 若S1 S2是兩個(gè)聯(lián)結(jié)詞集合 且S1 S2 若S1是全功能集 則S2也是全功能集 19 聯(lián)結(jié)詞的全功能集實(shí)例 1 S1 2 S2 3 S3 4 S4 5 S5 6 S6 7 S7 而 等則不是聯(lián)結(jié)詞全功能集 20 例如已知 是全功能集 證明 也是全功能集證 因?yàn)?是全功能集 任意一個(gè)真值函數(shù)可以用 聯(lián)結(jié)詞的命題公式表示 對(duì)于任意的命題公式 A B A B 因此任意一個(gè)真值函數(shù)可以用 聯(lián)結(jié)詞的命題公式表示 例 p p p p p p p p p pp p p p p p p p p p p p p p p p