ch2命題演算(4).ppt

1 主要內(nèi)容等值式與基本的等值式等值演算與置換規(guī)則析取范式與合取范式 主析取范式與主合取范式 第二章命題邏輯等值演算 2 2 1等值式 定義2 1若等價(jià)式A B是重言式 則稱A與B等值 記作A B 并稱A B是等值式幾點(diǎn)說明 定義中 A B 均為元語言符號(hào)A或B中可能有啞元出現(xiàn) 例如 p q p q r r r為左邊公式的啞元 用真值表可檢查兩個(gè)公式是否等值請(qǐng)驗(yàn)證 p q r p q rp q r 不與 p q r等值 3 等值式例題 例1判斷下列各組公式是否等值 1 p q r 與 p q r 結(jié)論 p q r p q r 4 等值式例題 2 p q r 與 p q r 結(jié)論 p q r 與 p q r不等值 5 基本等值式 雙重否定律 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 A B A B A B吸收律A A B A A A B A 6 基本等值式 零律A 1 1 A 0 0同一律A 0 A A 1 A排中律A A 1矛盾律A A 0蘊(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特別提示 必須牢記這16組等值式 這是繼續(xù)學(xué)習(xí)的基礎(chǔ) 7 等值演算與置換規(guī)則 1 等值演算 由已知的等值式推演出新的等值式的過程2 等值演算的基礎(chǔ) 1 等值關(guān)系的性質(zhì) 自反性 對(duì)稱性 傳遞性 2 基本的等值式 3 置換規(guī)則 見3 3 置換規(guī)則設(shè) A 是含公式A的命題公式 B 是用公式B置換 A 中所有的A后得到的命題公式若B A 則 B A 8 等值演算的應(yīng)用舉例 證明兩個(gè)公式等值例2證明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ī)則 今后在注明中省去置換規(guī)則注意 用等值演算不能直接證明兩個(gè)公式不等值 9 證明兩個(gè)公式不等值例3證明p q r 與 p q r不等值證方法一真值表法 見例1 2 方法二觀察法 觀察到000 010是左邊的成真賦值 是右邊的成假賦值方法三先用等值演算化簡(jiǎn)公式 然后再觀察p q r p q r p q r p q r p q r更容易看出前面的兩個(gè)賦值分別是左邊的成真賦值和右邊的成假賦值 等值演算的應(yīng)用舉例 10 判斷公式類型 A為矛盾式當(dāng)且僅當(dāng)A 0A為重言式當(dāng)且僅當(dāng)A 1例4用等值演算法判斷下列公式的類型 1 q p q 2 p q q p 3 p q p q r 等值演算的應(yīng)用舉例 解 1 q p q q p q 蘊(yùn)涵等值式 q p q 德摩根律 p q q 交換律 結(jié)合律 p 0 矛盾律 0 零律 矛盾式 11 判斷公式類型 2 p q q p p q q p 蘊(yùn)涵等值式 p q p q 交換律 1重言式 3 p q p q r p q q r 分配律 p 1 r 排中律 p r 同一律 可滿足式 101和111是成真賦值 000和010等是成假賦值 12 2 2析取范式與合取范式 基本概念 1 文字 命題變項(xiàng)及其否定的總稱 2 簡(jiǎn)單析取式 有限個(gè)文字構(gòu)成的析取式p q p q p q r 3 簡(jiǎn)單合取式 有限個(gè)文字構(gòu)成的合取式p q p q p q r 4 析取范式 由有限個(gè)簡(jiǎn)單合取式組成的析取式p p q p q p q p q r q r 5 合取范式 由有限個(gè)簡(jiǎn)單析取式組成的合取式p p q p q p q p p q r 6 范式 析取范式與合取范式的總稱 13 范式概念 說明 單個(gè)文字既是簡(jiǎn)單析取式 又是簡(jiǎn)單合取式形如p q r p q r的公式既是析取范式 又是合取范式 14 范式的性質(zhì) 定理2 1 1 一個(gè)簡(jiǎn)單析取式是重言式當(dāng)且僅當(dāng)它同時(shí)含有某個(gè)命題變項(xiàng)和它的否定式 2 一個(gè)簡(jiǎn)單合取式是矛盾式當(dāng)且僅當(dāng)它同時(shí)含有某個(gè)命題變項(xiàng)和它的否定式 定理2 2 1 一個(gè)析取范式是矛盾式當(dāng)且僅當(dāng)它每個(gè)簡(jiǎn)單合取式都是矛盾式 2 一個(gè)合取范式是重言式當(dāng)且僅當(dāng)它的每個(gè)簡(jiǎn)單析取式都是重言式 15 命題公式的范式 定理2 3 范式存在定理 任何命題公式都存在與之等值的析取范式與合取范式公式A的析取 合取 范式 與A等值的析取 合取 范式求公式A的范式的步驟 1 消去A中的 若存在 A B A BA B A B A B 2 否定聯(lián)結(jié)詞 的內(nèi)移或消去 A A A B A B A B A B 16 命題公式的范式 3 使用分配律A B C A B A C 求合取范式A B C A B A C 求析取范式公式范式的不足 不惟一 17 求公式的范式 例5求下列公式的析取范式與合取范式 1 p q r 2 p q r解 1 p q r p q r 消去 p q r 結(jié)合律 最后結(jié)果既是析取范式 由3個(gè)簡(jiǎn)單合取式組成的析取式 又是合取范式 由一個(gè)簡(jiǎn)單析取式組成的合取式 18 2 p q r p q r 消去第一個(gè) p q r 消去第二個(gè) p q r 否定號(hào)內(nèi)移 德摩根律 析取范式 p r q r 對(duì) 分配律 合取范式 求公式的范式 19 極小項(xiàng)與極大項(xiàng) 定義2 4在含有n個(gè)命題變項(xiàng)的簡(jiǎn)單合取式 簡(jiǎn)單析取式 中 若每個(gè)命題變項(xiàng)均以文字的形式在其中出現(xiàn)且僅出現(xiàn)一次 而且第i個(gè)文字出現(xiàn)在左起第i位上 1 i n 稱這樣的簡(jiǎn)單合取式 簡(jiǎn)單析取式 為極小項(xiàng) 極大項(xiàng) 幾點(diǎn)說明 n個(gè)命題變項(xiàng)有2n個(gè)極小項(xiàng)和2n個(gè)極大項(xiàng)2n個(gè)極小項(xiàng) 極大項(xiàng) 均互不等值用mi表示第i個(gè)極小項(xiàng) 其中i是該極小項(xiàng)成真賦值的十進(jìn)制表示 用Mi表示第i個(gè)極大項(xiàng) 其中i是該極大項(xiàng)成假賦值的十進(jìn)制表示 mi Mi 稱為極小項(xiàng) 極大項(xiàng) 的名稱 20 實(shí)例 由兩個(gè)命題變項(xiàng)p q形成的極小項(xiàng)與極大項(xiàng) 21 實(shí)例 由三個(gè)命題變項(xiàng)p q r形成的極小項(xiàng)與極大項(xiàng) mi與Mi的關(guān)系 mi Mi Mi mi 22 主析取范式與主合取范式 主析取范式 由極小項(xiàng)構(gòu)成的析取范式主合取范式 由極大項(xiàng)構(gòu)成的合取范式例如 n 3 命題變項(xiàng)為p q r時(shí) p q r p q r m1 m3 主析取范式 p q r p q r M1 M7 主合取范式公式A的主析取 合取 范式 與A等值的主析取 合取 范式定理2 5 主范式的存在惟一定理 任何命題公式都存在與之等值的主析取范式和主合取范式 并且是惟一的 23 求公式主范式的步驟 求公式主析取范式的步驟 設(shè)公式A含命題變項(xiàng)p1 p2 pn 1 求A的析取范式A B1 B2 Bs 其中Bj是簡(jiǎn)單合取式j(luò) 1 2 s 2 若某個(gè)Bj既不含pi 又不含 pi 則將Bj展開成Bj Bj pi pi Bj pi Bj pi 重復(fù)這個(gè)過程 直到所有簡(jiǎn)單合取式都是長(zhǎng)度為n的極小項(xiàng)為止 3 消去重復(fù)出現(xiàn)的極小項(xiàng) 即用mi代替mi mi 4 將極小項(xiàng)按下標(biāo)從小到大排列 24 求公式主范式的步驟 求公式的主合取范式的步驟 設(shè)公式A含命題變項(xiàng)p1 p2 pn 1 求A的合取范式A B1 B2 Bs 其中Bj是簡(jiǎn)單析取式j(luò) 1 2 s 2 若某個(gè)Bj既不含pi 又不含 pi 則將Bj展開成Bj Bj pi pi Bj pi Bj pi 重復(fù)這個(gè)過程 直到所有簡(jiǎn)單析取式都是長(zhǎng)度為n的極大項(xiàng)為止 3 消去重復(fù)出現(xiàn)的極大項(xiàng) 即用Mi代替Mi Mi 4 將極大項(xiàng)按下標(biāo)從小到大排列 25 實(shí)例 例6 1 求公式A p q r的主析取范式和主合取范式解 p q r p q r 析取范式 p q p q r r p q r p q r m6 m7 r p p q q r p q r p q r p q r p q r m1 m3 m5 m7 代入 并排序 得 p q r m1 m3 m5 m6 m7 主析取范式 26 實(shí)例 p q r p r q r 合取范式 p r p q q r p q r p q r M0 M2 q r p p q r p q r p q r M0 M4 代入 并排序 得 p q r M0 M2 M4 主合取范式 27 主范式的應(yīng)用 1 求公式的成真成假賦值設(shè)公式A含n個(gè)命題變項(xiàng) A的主析取范式有s個(gè)極小項(xiàng) 則A有s個(gè)成真賦值 它們是極小項(xiàng)下標(biāo)的二進(jìn)制表示 其余2n s個(gè)賦值都是成假賦值例如 p q r m1 m3 m5 m6 m7成真賦值為001 011 101 110 111 成假賦值為000 010 100 類似地 由主合取范式也立即求出成假賦值和成真賦值 28 2 判斷公式的類型設(shè)A含n個(gè)命題變項(xiàng) A為重言式 A的主析取范式含全部2n個(gè)極小項(xiàng) A的主合取范式不含任何極大項(xiàng) 記為1 A為矛盾式 A的主合析取范式含全部2n個(gè)極大項(xiàng) A的主析取范式不含任何極小項(xiàng) 記為0 A為非重言式的可滿足式 A的主析取范式中至少含一個(gè) 但不是全部極小項(xiàng) A的主合取范式中至少含一個(gè) 但不是全部極大項(xiàng) 主范式的應(yīng)用 29 例7用主析取范式判斷公式的類型 1 A p q q 2 B p p q 解 1 A p q q p q q 0矛盾式 2 B p p q 1 m0 m1 m2 m3重言式 主范式的應(yīng)用 30 3 判斷兩個(gè)公式是否等值例8用主析取范式判以下每一組公式是否等值 p q r 與 p q r p q r 與 p q r解p q r m0 m1 m2 m3 m4 m5 m7 p q r m0 m1 m2 m3 m4 m5 m7 p q r m1 m3 m4 m5 m7顯見 中的兩公式等值 而 的不等值 主范式的應(yīng)用 31 4 解實(shí)際問題例9某單位要從A B C三人中選派若干人出國考察 需滿足下述條件 1 若A去 則C必須去 2 若B去 則C不能去 3 A和B必須去一人且只能去一人 問有幾種可能的選派方案 解記p 派A去 q 派B去 r 派C去 1 p r 2 q r 3 p q p q 求下式的成真賦值A(chǔ) p r q r p q p q 主范式的應(yīng)用 32 求A的主析取范式A p r q r p q p q p r q r p q p q p q p r r q r r p q p q p q p q p r p q r q p q p q p q p r p q r q p q p q r p q r 成真賦值 101 010結(jié)論 方案1派A與C去 方案2派B去 主范式的應(yīng)用 33 由主析取范式確定主合取范式例10設(shè)A有3個(gè)命題變項(xiàng) 且已知A m1 m3 m7 求A的主合取范式 解A的成真賦值是1 3 7的二進(jìn)制表示 成假賦值是在主析取范式中沒有出現(xiàn)的極小項(xiàng)的下角標(biāo)0 2 4 5 6的二進(jìn)制表示 它們恰好是A的主合取范式的極大項(xiàng)的下角標(biāo) 故A M0 M2 M4 M5 M6 用成真賦值和成假賦值確定主范式 由主合取范式確定主析取范式用真值表確定主范式 34 第二章習(xí)題課 主要內(nèi)容等值式與等值演算基本等值式 16組 24個(gè)公式 主析取范式與主合取范式 35 基本要求 深刻理解等值式的概念牢記基本等值式的名稱及它們的內(nèi)容熟練地應(yīng)用基本等值式及置換規(guī)則進(jìn)行等值演算理解文字 簡(jiǎn)單析取式 簡(jiǎn)單合取式 析取范式 合取范式的概念深刻理解極小項(xiàng) 極大項(xiàng)的概念 名稱及下角標(biāo)與成真 成假賦值的關(guān)系 并理解簡(jiǎn)單析取式與極小項(xiàng)的關(guān)系熟練掌握求主范式的方法 等值演算 真值表等 會(huì)用主范式求公式的成真賦值 成假賦值 判斷公式的類型 判斷兩個(gè)公式是否等值會(huì)將公式等值地化成指定聯(lián)結(jié)詞完備集中的公式會(huì)用命題邏輯的概念及運(yùn)算解決簡(jiǎn)單的應(yīng)用問題掌握消解規(guī)則及其性質(zhì)會(huì)用消解算法判斷公式的可滿足性 36 練習(xí)1 概念 1 設(shè)A與B為含n個(gè)命題變項(xiàng)的公式 判斷下列命題是否為真 1 A B當(dāng)且僅當(dāng)A與B有相同的主析取范式 2 若A為重言式 則A的主合取范式為0 3 若A為矛盾式 則A的主析取范式為1 4 任何公式都能等值地化成 中的公式 5 任何公式都能等值地化成 中的公式 說明 2 重言式的主合取范式不含任何極大項(xiàng) 為1 3 矛盾式的主合析范式不含任何極小項(xiàng) 為0 4 不是完備集 如矛盾式不能寫成 中的公式 5 是完備集 真 假 假 假 真 37 練習(xí)2 判斷公式類型 解用等值演算法求主范式 p q q p p q q p p q q p p q p q p q p q m2 m1 m3 m0 m0 m1 m2 m3主析取范式 1主合取范式 2 判斷下列公式的類型 1 p q q p 重言式 38 練習(xí)題2 續(xù) 解用等值演算法求公式的主范式 p q q p q q p q q 0主析取范式 M0 M1 M2 M3主合取范式 2 p q q 矛盾式 39 解用等值演算法求公式的主范式 p q p p q p p p q p q m0 m1主析取范式 M2 M3主合取范式 3 p q p 練習(xí)2 續(xù) 非重言式的可滿足式 40 練習(xí)3 求公式的主范式 3 已知命題公式A中含3個(gè)命題變項(xiàng)p q r 并知道它的成真賦值為001 010 111 求A的