離散數(shù)學(xué)第2章,高等教育出版社,屈婉玲,耿素云,張立昂,課件,PPT.ppt

1 主要內(nèi)容等值式與基本的等值式等值演算與置換規(guī)則析取范式與合取范式 主析取范式與主合取范式聯(lián)結(jié)詞完備集可滿足性問題與消解法 第二章命題邏輯等值演算 2 2 1等值式 定義2 1若等價式A B是重言式 則稱A與B等值 記作A B 并稱A B是等值式幾點說明 定義中 A B 均為元語言符號A或B中可能有啞元出現(xiàn) 例如 p q p q r r r為左邊公式的啞元 用真值表可檢查兩個公式是否等值請驗證 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蘊涵等值式A B A B等價等值式A B A B B A 假言易位A B B A等價否定等值式A B A B歸謬論 A B A B A特別提示 必須牢記這16組等值式 這是繼續(xù)學(xué)習(xí)的基礎(chǔ) 7 等值演算與置換規(guī)則 1 等值演算 由已知的等值式推演出新的等值式的過程2 等值演算的基礎(chǔ) 1 等值關(guān)系的性質(zhì) 自反性 對稱性 傳遞性 2 基本的等值式 3 置換規(guī)則 見3 3 置換規(guī)則設(shè) A 是含公式A的命題公式 B 是用公式B置換 A 中所有的A后得到的命題公式若B A 則 B A 8 等值演算的應(yīng)用舉例 證明兩個公式等值例2證明p q r p q r證p q r p q r 蘊涵等值式 置換規(guī)則 p q r 結(jié)合律 置換規(guī)則 p q r 德摩根律 置換規(guī)則 p q r 蘊涵等值式 置換規(guī)則 今后在注明中省去置換規(guī)則注意 用等值演算不能直接證明兩個公式不等值 9 證明兩個公式不等值例3證明p q r 與 p q r不等值證方法一真值表法 見例1 2 方法二觀察法 觀察到000 010是左邊的成真賦值 是右邊的成假賦值方法三先用等值演算化簡公式 然后再觀察p q r p q r p q r p q r p q r更容易看出前面的兩個賦值分別是左邊的成真賦值和右邊的成假賦值 等值演算的應(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 蘊涵等值式 q p q 德摩根律 p q q 交換律 結(jié)合律 p 0 矛盾律 0 零律 矛盾式 11 判斷公式類型 2 p q q p p q q p 蘊涵等值式 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 文字 命題變項及其否定的總稱 2 簡單析取式 有限個文字構(gòu)成的析取式p q p q p q r 3 簡單合取式 有限個文字構(gòu)成的合取式p q p q p q r 4 析取范式 由有限個簡單合取式組成的析取式p p q p q p q p q r q r 5 合取范式 由有限個簡單析取式組成的合取式p p q p q p q p p q r 6 范式 析取范式與合取范式的總稱 13 范式概念 說明 單個文字既是簡單析取式 又是簡單合取式 14 范式的性質(zhì) 定理2 1 1 一個簡單析取式是重言式當(dāng)且僅當(dāng)它同時含有某個命題變項和它的否定式 2 一個簡單合取式是矛盾式當(dāng)且僅當(dāng)它同時含有某個命題變項和它的否定式 定理2 2 1 一個析取范式是矛盾式當(dāng)且僅當(dāng)它每個簡單合取式都是矛盾式 2 一個合取范式是重言式當(dāng)且僅當(dāng)它的每個簡單析取式都是重言式 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é)合律 18 2 p q r p q r 消去第一個 p q r 消去第二個 p q r 否定號內(nèi)移 德摩根律 析取范式 p r q r 對 分配律 合取范式 求公式的范式 19 極小項與極大項 定義2 4在含有n個命題變項的簡單合取式 簡單析取式 中 若每個命題變項均以文字的形式在其中出現(xiàn)且僅出現(xiàn)一次 而且第i個文字出現(xiàn)在左起第i位上 1 i n 稱這樣的簡單合取式 簡單析取式 為極小項 極大項 幾點說明 n個命題變項有2n個極小項和2n個極大項2n個極小項 極大項 均互不等值用mi表示第i個極小項 其中i是該極小項成真賦值的十進(jìn)制表示 用Mi表示第i個極大項 其中i是該極大項成假賦值的十進(jìn)制表示 mi Mi 稱為極小項 極大項 的名稱 20 實例 由兩個命題變項p q形成的極小項與極大項 21 實例 由三個命題變項p q r形成的極小項與極大項 mi與Mi的關(guān)系 mi Mi Mi mi 22 主析取范式與主合取范式 主析取范式 由極小項構(gòu)成的析取范式主合取范式 由極大項構(gòu)成的合取范式例如 n 3 命題變項為p q r時 p q r p q r m1 m3 主析取范式 p q r p q r M1 M7 主合取范式公式A的主析取 合取 范式 與A等值的主析取 合取 范式定理2 5 主范式的存在惟一定理 任何命題公式都存在與之等值的主析取范式和主合取范式 并且是惟一的 23 求公式主范式的步驟 求公式主析取范式的步驟 設(shè)公式A含命題變項p1 p2 pn 1 求A的析取范式A B1 B2 Bs 其中Bj是簡單合取式j(luò) 1 2 s 2 若某個Bj既不含pi 又不含 pi 則將Bj展開成Bj Bj pi pi Bj pi Bj pi 重復(fù)這個過程 直到所有簡單合取式都是長度為n的極小項為止 3 消去重復(fù)出現(xiàn)的極小項 即用mi代替mi mi 4 將極小項按下標(biāo)從小到大排列 24 求公式主范式的步驟 求公式的主合取范式的步驟 設(shè)公式A含命題變項p1 p2 pn 1 求A的合取范式A B1 B2 Bs 其中Bj是簡單析取式j(luò) 1 2 s 2 若某個Bj既不含pi 又不含 pi 則將Bj展開成Bj Bj pi pi Bj pi Bj pi 重復(fù)這個過程 直到所有簡單析取式都是長度為n的極大項為止 3 消去重復(fù)出現(xiàn)的極大項 即用Mi代替Mi Mi 4 將極大項按下標(biāo)從小到大排列 25 實例 例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 實例 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個命題變項 A的主析取范式有s個極小項 則A有s個成真賦值 它們是極小項下標(biāo)的二進(jìn)制表示 其余2n s個賦值都是成假賦值例如 p q r m1 m3 m5 m6 m7成真賦值為001 011 101 110 111 成假賦值為000 010 100 類似地 由主合取范式也立即求出成假賦值和成真賦值 28 2 判斷公式的類型設(shè)A含n個命題變項 A為重言式 A的主析取范式含全部2n個極小項 A的主合取范式不含任何極大項 記為1 A為矛盾式 A的主合析取范式含全部2n個極大項 A的主析取范式不含任何極小項 記為0 A為非重言式的可滿足式 A的主析取范式中至少含一個 但不是全部極小項 A的主合取范式中至少含一個 但不是全部極大項 主范式的應(yīng)用 29 例7用主析取范式判斷公式的類型 1 A p q q 2 B p p q 3 C p q r解 1 A p q q p q q 0矛盾式 2 B p p q 1 m0 m1 m2 m3重言式 3 C p q r p q r p q r p q r p q r p q r p q r p q r m0 m1 m3 m5 m7非重言式的可滿足式 主范式的應(yīng)用 30 3 判斷兩個公式是否等值例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 解實際問題例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個命題變項 且已知A m1 m3 m7 求A的主合取范式 解A的成真賦值是1 3 7的二進(jìn)制表示 成假賦值是在主析取范式中沒有出現(xiàn)的極小項的下角標(biāo)0 2 4 5 6的二進(jìn)制表示 它們恰好是A的主合取范式的極大項的下角標(biāo) 故A M0 M2 M4 M5 M6 用成真賦值和成假賦值確定主范式 由主合取范式確定主析取范式用真值表確定主范式 34 2 3聯(lián)結(jié)詞的完備集 定義2 6稱F 0 1 n 0 1 為n元真值函數(shù) 0 1 n 00 0 00 1 11 1 包含個長為n的0 1符號串 共有個n元真值函數(shù) 35 真值函數(shù) 2元真值函數(shù) 36 公式與真值函數(shù) 任何一個含n個命題變項的命題公式A都對應(yīng)惟一的一個n元真值函數(shù)F F恰好為A的真值表 等值的公式對應(yīng)的真值函數(shù)相同 例如 p q p q都對應(yīng) 37 聯(lián)結(jié)詞完備集 定義2 7設(shè)S是一個聯(lián)結(jié)詞集合 如果任何n n 1 元真值函數(shù)都可以由僅含S中的聯(lián)結(jié)詞構(gòu)成的公式表示 則稱S是聯(lián)結(jié)詞完備集若S是聯(lián)結(jié)詞完備集 則任何命題公式都可由S中的聯(lián)結(jié)詞表示定理2 6S 是聯(lián)結(jié)詞完備集證明由范式存在定理可證 38 聯(lián)結(jié)詞完備集 推論以下都是聯(lián)結(jié)詞完備集 1 S1 2 S2 3 S3 4 S4 5 S5 證明 1 2 在聯(lián)結(jié)詞完備集中加入新的聯(lián)結(jié)詞后仍為完備集 3 A B A B 4 A B A B 5 A B A B 不是聯(lián)結(jié)詞完備集 0不能用它表示它的子集 等都不是 39 復(fù)合聯(lián)結(jié)詞 定義2 8設(shè)p q為兩個命題 p q 稱作p與q的與非式 記作p q 即p q p q 稱為與非聯(lián)結(jié)詞 p q 稱作p與q的或非式 記作p q 即p q p q 稱為或非聯(lián)結(jié)詞定理2 7 與 為聯(lián)結(jié)詞完備集 證明 為完備集 p p p p p p pp q p q p q p p q q p q p q p q p q p q 得證 為聯(lián)結(jié)詞完備集 對 類似可證 40 2 4可滿足性問題與消解法 不含任何文字的簡單析取式稱作空簡單析取式 記作 規(guī)定 是不可滿足的 約定 簡單析取式不同時含某個命題變項和它的否定S 合取范式 C 簡單析取式 l 文字 賦值 帶下角標(biāo)或 文字l的補lc 若l p 則lc p 若l p 則lc p S S S是可滿足的當(dāng)且僅當(dāng)S 是可滿足的定義2 9設(shè)C1 l C1 C2 lc C2 C1 和C2 不含l和lc 稱C1 C2 為C1和C2 以l和lc為消解文字 的消解式或消解結(jié)果 記作Res C1 C2 例如 Res p q r p q s q r s 41 消解規(guī)則 定理2 8C1 C2 Res C1 C2 證記C Res C1 C2 C1 C2 其中l(wèi)和lc為消解文字 C1 l C1 C2 lc C2 且C1 和C2 不含l和lc 假設(shè)C1 C2是可滿足的 是它的滿足賦值 不妨設(shè) l 1 C2必含有文字l l lc且 l 1 C中含有l(wèi) 故 滿足C 反之 假設(shè)C是可滿足的 是它的滿足賦值 C必有l(wèi) 使得 l 1 不妨設(shè)C1 含l 于是 滿足C1 把擴(kuò)張到l 和lc 上 若l p 則令 p 0 若lc p 則令 p 1 恒有 lc 1 從而 滿足C2 得證C1 C2是可滿足的 注意 C1 C2與Res C1 C2 有相同的可滿足性 但不一定等值 42 消解序列與合取范式的否證 定義2 10設(shè)S是一個合取范式 C1 C2 Cn是一個簡單析取式序列 如果對每一個i 1 i n Ci是S的一個簡單析取式或者是Res Cj Ck 1 j k i 則稱此序列是由S導(dǎo)出Cn的消解序列 當(dāng)Cn 時 稱此序列是S的一個否證 定理2 9一個合取范式是不可滿足的當(dāng)且僅當(dāng)它有否證 例11用消解規(guī)則證明S p q p q s q s q是不可滿足的 證C1 p q C2 p q s C3 Res C1 C2 q s C4 q s C5 Res C3 C4 q C6 q C7 Res C5 C6 這是S的否證 43 消解算法 消解算法輸入 合式公式A輸出 當(dāng)A是可滿足時 回答 Yes 否則回答 No 1 求A的合取范式S2 令S0 S2 S1 S的所有簡單析取式3 ForC1 S0和C2 S14 IfC1 C2可以消解then5 計算C Res C1 C2 6 IfC then7 輸出 No 計算結(jié)束8 IfC S0且C S1then9 S2 S2 C 44 消解算法 10 ForC1 S1 C2 S1且C1 C211 IfC1 C2可以消解then12 計算C Res C1 C2 13 IfC then14 輸出 No 計算結(jié)束15 IfC S0且C S1then16 S2 S2 C 17 IfS2 then18 輸出 Yes 計算結(jié)束19 ElseS0 S0 S1 S1 S2 S2 goto3 45 消解算法例題 例12用消解算法判斷下述公式是否是可滿足的 p p q p q q r q r 解S p p q p q q r q r 循環(huán)1S0 S1 p p q p q q r q r S2 Res p q p q pRes p q q r p rRes p q q r p rRes q r q r qS2 p r p r q 循環(huán)2S0 p p q p q q r q r S1 p r p r q S2 Res p q q p 46 消解算法例題 Res q r p r p qRes q r p r p qRes p r p r pS2 輸出 Yes 47 第二章習(xí)題課 主要內(nèi)容等值式與等值演算基本等值式 16組 24個公式 主析取范式與主合取范式聯(lián)結(jié)詞完備集消解法 48 基本要求 深刻理解等值式的概念牢記基本等值式的名稱及它們的內(nèi)容熟練地應(yīng)用基本等值式及置換規(guī)則進(jìn)行等值演算理解文字 簡單析取式 簡單合取式 析取范式 合取范式的概念深刻理解極小項 極大項的概念 名稱及下角標(biāo)與成真 成假賦值的關(guān)系 并理解簡單析取式與極小項的關(guān)系熟練掌握求主范式的方法 等值演算 真值表等 會用主范式求公式的成真賦值 成假賦值 判斷公式的類型 判斷兩個公式是否等值會將公式等值地化成指定聯(lián)結(jié)詞完備集中的公式會用命題邏輯的概念及運算解決簡單的應(yīng)用問題掌握消解規(guī)則及其性質(zhì)會用消解算法判斷公式的可滿足性 49 練習(xí)1 概念 1 設(shè)A與B為含n個命題變項的公式 判斷下列命題是否為真 1 A B當(dāng)且僅當(dāng)A與B有相同的主析取范式 2 若A為重言式 則A的主合取范式為0 3 若A為矛盾式 則A的主析取范式為1 4 任何公式都能等值地化成 中的公式 5 任何公式都能等值地化成 中的公式 說明 2 重言式的主合取范式不含任何極大項 為1 3 矛盾式的主合析范式不含任何極小項 為0 4 不是完備集 如矛盾式不能寫成 中的公式 5 是完備集 真 假 假 假 真 50 練習(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 重言式 51 練習(xí)題2 續(xù) 解用等值演算法求公式的主范式 p q q p q q p q q 0主析取范式 M0 M1 M2 M3主合取范式 2 p q q 矛盾式 52 解用等值演算法求公式的主范式 p q p p q p p p q p q m0 m1主析取范式 M2 M3主合取范式 3 p q p 練習(xí)2 續(xù) 非重言式的可滿足式 53 練習(xí)3 求公式的主范式 3 已知命題公式A中含3個命題變項p q r 并知道它的成真賦值為001 010 111 求A的主析取范式和主合取范式 及A對應(yīng)的真值函數(shù) 解 A的主析取范式為m1 m2 m7 A的主合取范式為M0 M3 M4 M5 M6 54 練習(xí)4 聯(lián)結(jié)詞完備集 4 將A p q r改寫成下述各聯(lián)結(jié)詞集中的公式 1 2 3 4 5 6 解 1 p q r p q r 2 p q r p q r 3 p q r p q r p q r 55 練習(xí)4解答 4 p q r p q r p q r 5 p q r p q r p q r p q r p q r p q r 6 p q r p q r p q r p q r p p q q r r 說明 答案不惟一 56 練習(xí)5 應(yīng)用題 5 某公司要從趙 錢 孫 李 周五名新畢業(yè)的大學(xué)生中選派一些人出國學(xué)習(xí) 選派必須滿足以下條件 1 若趙去 錢也去 2 李 周兩人中至少有一人去 3 錢 孫兩人中去且僅去一人 4 孫 李兩人同去或同不去 5 若周去 則趙 錢也去 用等值演算法分析該公司如何選派他們出國 5