離散數(shù)學(xué)講義第二章命題邏輯.ppt

《離散數(shù)學(xué)講義第二章命題邏輯.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué)講義第二章命題邏輯.ppt（88頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

第二章命題邏輯數(shù)理邏輯是用數(shù)學(xué)方法研究思維規(guī)律的一門(mén)學(xué)科 所謂數(shù)學(xué)方法是指 用一套數(shù)學(xué)的符號(hào)系統(tǒng)來(lái)描述和處理思維的形式與規(guī)律 因此 數(shù)理邏輯又稱為符號(hào)邏輯 本章介紹數(shù)理邏輯中最基本的內(nèi)容命題邏輯 首先引入命題 命題公式等概念 然后 在此基礎(chǔ)上研究命題公式間的等值關(guān)系和蘊(yùn)含關(guān)系 并給出推理規(guī)則 進(jìn)行命題演繹 主要內(nèi)容如下 2 1命題的概念和表示2 2邏輯聯(lián)結(jié)詞2 3命題演算的合適公式2 4等價(jià)與蘊(yùn)含2 5對(duì)偶與范式2 6命題演算的推理理論 例1判斷下列語(yǔ)句是否是命題 1 空氣是人生存所必需的 2 請(qǐng)把門(mén)關(guān)上 3 南京是中國(guó)的首都 4 你吃飯了嗎 5 x 3 6 啊 真美呀 7 明年春節(jié)是個(gè)大晴天 解語(yǔ)句 1 3 5 7 是陳述句 1 3 7 是命題 用真值來(lái)描述命題是 真 還是 假 分別用 1 和 0 表示 命題用大寫(xiě)的拉丁字母A B C P Q 或者帶下標(biāo)的大寫(xiě)的字母來(lái)表示 例2判斷下列陳述句是否是命題 P 地球外的星球上也有人 Q 小王是我的好朋友 解P Q是命題 原子命題 由簡(jiǎn)單句形成的命題 復(fù)合命題 由一個(gè)或幾個(gè)原子命題通過(guò)聯(lián)結(jié)詞的聯(lián)接而構(gòu)成的命題 例3A 李明是三好學(xué)生 B 李明既是三好學(xué)生又是足球隊(duì)員C 明天天氣晴朗 D 張平或者正在釣魚(yú)或者正在睡覺(jué) E 如果明天天氣晴朗 那么我們舉行運(yùn)動(dòng)會(huì) 解A C是原子命題B D E是復(fù)合命題 2 2邏輯聯(lián)結(jié)詞 1 否定 定義2 2 1設(shè)P是一個(gè)命題 則P的否定是一個(gè)復(fù)合命題 稱為P的否命題 記作 P 讀作 非P 例4設(shè)P 上海是一個(gè)城市 Q 每個(gè)自然數(shù)都是偶數(shù) 則有 P 上海不是一個(gè)城市 Q 并非每個(gè)自然數(shù)都是偶數(shù) 命題P取值為真時(shí) 命題 P取值為假 命題P取值為假時(shí) 命題 P取值為真 2 合取 定義2 2 2設(shè)P和Q是兩個(gè)命題 則P和Q的合取是一個(gè)復(fù)合命題 記作 P Q 讀作 P且Q 例5設(shè)P 我們?nèi)タ措娪?Q 房間里有十張桌子 則P Q表示 我們?nèi)タ措娪安⑶曳块g里有十張桌子 當(dāng)且僅當(dāng)命題P和Q均取值為真時(shí) P Q才取值為真 3 析取 定義2 2 3設(shè)P和Q是兩個(gè)命題 則P和Q的析取是一個(gè)復(fù)合命題 記作 P Q 讀作 P或Q 例6設(shè)命題P 他可能是100米賽跑冠軍 Q 他可能是400米賽跑冠軍 則命題P Q表示 他可能是100米或400米賽跑的冠軍 當(dāng)且僅當(dāng)P和Q至少有一個(gè)取值為真時(shí) P Q取值為真 4 蘊(yùn)含 定義2 2 4設(shè)P和Q是兩個(gè)命題 則它們的條件命題是一個(gè)復(fù)合命題 記作 P Q 讀作 如果P 則Q 例9將命題 如果我得到這本小說(shuō) 那么我今夜就讀完它 符號(hào)化 解令P 我得到這本小說(shuō) Q 我今夜就讀完它 于是上述命題可表示為P Q 例8若P 雪是黑色的 Q 太陽(yáng)從西邊升起 R 太陽(yáng)從東邊升起 則P Q和P R所表示的命題都是真的 當(dāng)P為真 Q為假時(shí) P Q為假 否則P Q為真 5 等值 定義2 2 5設(shè)P和Q是兩個(gè)命題 則它們的等值命題是一個(gè)復(fù)合命題 稱為等值式復(fù)合命題 記作 P Q 讀作 P當(dāng)且僅當(dāng)Q 當(dāng)P和Q的真值相同時(shí) P Q取真 否則取假 例10非本倉(cāng)庫(kù)工作人員 一律不得入內(nèi) 解令P 某人是倉(cāng)庫(kù)工作人員 Q 某人可以進(jìn)入倉(cāng)庫(kù) 則上述命題可表示為P Q 例11黃山比喜馬拉雅山高 當(dāng)且僅當(dāng)3是素?cái)?shù)令P 黃山比喜馬拉雅山高 Q 3是素?cái)?shù)本例可符號(hào)化為P Q 從漢語(yǔ)的語(yǔ)義看 P與Q之間并無(wú)聯(lián)系 但就聯(lián)結(jié)詞 的定義來(lái)看 因?yàn)镻的真值為假 Q的真值為真 所以P Q的真值為假 對(duì)于上述五種聯(lián)結(jié)詞 應(yīng)注意到 復(fù)合命題的真值只取決于構(gòu)成它的各原子命題的真值 而與這些原子命題的內(nèi)容含義無(wú)關(guān) 命題符號(hào)化利用聯(lián)結(jié)詞可以把許多日常語(yǔ)句符號(hào)化 基本步驟如下 1 從語(yǔ)句中分析出各原子命題 將它們符號(hào)化 2 使用合適的命題聯(lián)結(jié)詞 把原子命題逐個(gè)聯(lián)結(jié)起來(lái) 組成復(fù)合命題的符號(hào)化表示 例12用符號(hào)形式表示下列命題 1 如果明天早上下雨或下雪 那么我不去學(xué)校 2 如果明天早上不下雨且不下雪 那么我去學(xué)校 3 如果明天早上不是雨夾雪 那么我去學(xué)校 4 只有當(dāng)明天早上不下雨且不下雪時(shí) 我才去學(xué)校 解令P 明天早上下雨 Q 明天早上下雪 R 我去學(xué)校 1 P Q R 2 P Q R 3 P Q R 4 R P Q 例13 將下列命題符號(hào)化 1 派小王或小李出差 2 我們不能既劃船又跑步 3 如果你來(lái)了 那么他唱不唱歌將看你是否伴奏而定 4 如果李明是體育愛(ài)好者 但不是文藝愛(ài)好者 那么李明不是文體愛(ài)好者 5 假如上午不下雨 我去看電影 否則就在家里看書(shū) 解 1 令P 派小王出差 Q 派小李出差 命題符號(hào)化為P Q 2 令P 我們劃船 Q 我們跑步 則命題可表示為 P Q 3 令P 你來(lái)了 Q 他唱歌 R 你伴奏 則命題可表示為P Q R 4 令P 李明是體育愛(ài)好者 Q 李明是文藝愛(ài)好者 則命題可表示為 P Q P Q 5 令P 上午下雨 Q 我去看電影 R 我在家讀書(shū) 則命題可表示為 P Q P R 練習(xí)2 21 判斷下列語(yǔ)句哪些是命題 若是命題 則指出其真值 1 只有小孩才愛(ài)哭 2 X 6 Y 3 銀是白的 4 起來(lái)吧 我的朋友 是假 不是 是真 不是 2 將下列命題符號(hào)化 1 我看見(jiàn)的既不是小張也不是老李 解令P 我看見(jiàn)的是小張 Q 我看見(jiàn)的是老李 則該命題可表示為 P Q 2 如果晚上做完了作業(yè)并且沒(méi)有其它的事 他就會(huì)看電視或聽(tīng)音樂(lè) 解令P 他晚上做完了作業(yè) Q 他晚上有其它的事 R 他看電視 S 他聽(tīng)音樂(lè) 則該命題可表示為 P Q R S 2 3命題演算的合適公式一 命題公式的概念1 命題常元一個(gè)表示確定命題的大寫(xiě)字母 2 命題變?cè)粋€(gè)沒(méi)有指定具體內(nèi)容的命題符號(hào) 一個(gè)命題變?cè)?dāng)沒(méi)有對(duì)其賦予內(nèi)容時(shí) 它的真值不能確定 一旦用一個(gè)具體的命題代入 它的真值就確定了 3 命題公式命題公式 或簡(jiǎn)稱公式 是由0 1和命題變?cè)约懊}聯(lián)結(jié)詞按一定的規(guī)則產(chǎn)生的符號(hào)串 定義2 3 1 命題公式的遞歸定義 1 0 1是命題公式 2 命題變?cè)敲}公式 3 如果A是命題公式 則 A是命題公式 4 如果A和B是命題公式 則 A B A B A B A B 也是命題公式 有限次地利用上述 1 4 而產(chǎn)生的符號(hào)串是命題公式 例1判斷下列符號(hào)串是否為命題公式 1 P Q PR 2 P Q Q R 解 1 不是命題公式 2 是命題公式 4 代入實(shí)例定義2 3 2設(shè)A和B是兩個(gè)命題公式 如果將A中的某些命題變?cè)妹}公式進(jìn)行代換便可得到B 并且此種代換滿足 1 被代換的是命題變?cè)?2 如果要代換某個(gè)命題變?cè)?則要將該命題變?cè)贏中的一切出現(xiàn)進(jìn)行代換 3 代換必須同時(shí)獨(dú)立地進(jìn)行則稱B是A的一個(gè)代入實(shí)例 例2設(shè)A P Q P 判斷下列命題公式是否是A的代入實(shí)例 B S R Q S R C S R Q P 解B是 C不是 二 真值指派命題公式代表一個(gè)命題 但只有當(dāng)公式中的每一個(gè)命題變?cè)加靡粋€(gè)確定的命題代入時(shí) 命題公式才有確定的真值 成為命題 定義2 3 3設(shè)A P1 P2 Pn 是一個(gè)命題公式 P1 P2 Pn是出現(xiàn)于其中的全部命題變?cè)?對(duì)P1 P2 Pn分別指定一個(gè)真值 稱為對(duì)P1 P2 Pn公式A的一組真值指派 列出命題公式A在P1 P2 Pn的所有2n種真值指派下對(duì)應(yīng)的真值 這樣的表稱為A的真值表 例3給出公式F P Q Q R P R 的真值表 解公式F的真值表如下 三 公式類(lèi)型定義2 3 5如果對(duì)于命題公式F所包含的命題變?cè)娜魏我唤M真值指派 F的真值恒為真 則稱公式F為重言式 或永真公式 常用 1 表示 相反地 若對(duì)于F所包含的命題變?cè)娜魏我唤M真值指派 F的真值恒為假 則稱公式F為矛盾式 或永假公式 常用 0 表示 如果至少有一組真值指派使公式F的真值為真 則稱F為可滿足公式 例4構(gòu)造下列命題公式的真值表 并判斷它們是何種類(lèi)型的公式 1 P Q P Q 2 Q P P Q 3 P Q Q R P R 由上可知 F1是重言式 F2是矛盾式 2 4等價(jià)與蘊(yùn)含 一 命題公式的等價(jià)關(guān)系定義2 4 1設(shè)A和B是兩個(gè)命題公式 P1 P2 Pn是所有出現(xiàn)于A和B中的命題變?cè)?如果對(duì)于P1 P2 Pn的任一組真值指派 A和B的真值都相同 則稱公式A和B等價(jià) 記為A B 稱A B為等價(jià)式 注意 1 符號(hào) 與 的區(qū)別與聯(lián)系 2 可以驗(yàn)證等價(jià)關(guān)系滿足 自反性 對(duì)任意公式A 有A A 對(duì)稱性 對(duì)任意公式A B 若A B 則B A 可傳遞性 對(duì)任意公式A B C 若A B B C 則A C 3 當(dāng)A是重言式時(shí) A 1 當(dāng)A是矛盾式時(shí) 則A 0 定理2 4 1A B當(dāng)且僅當(dāng)A B是永真公式 二 基本的等價(jià)式設(shè)P Q R是命題變?cè)?下表中列出了24個(gè)最基本的等價(jià)式 三 等價(jià)式的判別有兩種方法 真值表方法 命題演算方法1 真值表方法 例1用真值表方法證明E10 P Q P Q 解令 A P Q B P Q 構(gòu)造A B以及A B的真值表如下 由于公式A B所標(biāo)記的列全為1 因此A B 0 例2用真值表方法證明E11 P Q P Q 解令A(yù) P Q B P Q構(gòu)造A B以及A B的真值表如下 由于公式A B所標(biāo)記的列全為1 因此A B 例3用真值表方法判斷P Q P Q是否成立 解令A(yù) P Q B P Q構(gòu)造A B以及A B的真值表 由于公式A B所標(biāo)記的列不全為1 A B不是永真公式 因此A B不成立 1 代入規(guī)則重言式的代入實(shí)例仍是重言式 2 命題演算方法 例如F P Q Q P 是重言式 若用公式A B代換命題變?cè)狿得公式F1 A B Q Q A B F1仍是重言式 注意 因?yàn)锳 B當(dāng)且僅當(dāng)A B是重言式 所以 若對(duì)于等價(jià)式中的任一命題變?cè)霈F(xiàn)的每一處均用同一命題公式代入 則得到的仍是等價(jià)式 2 置換規(guī)則設(shè)C是命題公式A的一部分 即C是公式A中連續(xù)的幾個(gè)符號(hào) 且C本身也是一個(gè)命題公式 則稱C為公式A的子公式 例如設(shè)公式A P Q P Q R S 則 P Q P Q P Q R S 等均是A的子公式 但 P P 和 Q等均不是A的子公式 置換規(guī)則設(shè)C是公式A的子公式 C D 如果將公式A中的子公式C置換成公式D之后 得到的公式是B 則A B 3 等價(jià)演算等價(jià)演算是指利用已知的一些等價(jià)式 根據(jù)置換規(guī)則 代入規(guī)則以及等價(jià)關(guān)系的可傳遞性推導(dǎo)出另外一些等價(jià)式的過(guò)程 由代入規(guī)則知前述的基本等價(jià)式 不僅對(duì)任意的命題變?cè)狿 Q R是成立的 而且當(dāng)P Q R分別為命題公式時(shí) 這些等價(jià)式也成立 例2證明命題公式的等價(jià)關(guān)系 P Q R Q P R Q 證明 P Q R Q P Q R Q E11 P R QE3 分配律 P R QE10 德 摩根定律 P R QE11所以 P Q R Q P R Q 例3證明下列命題公式的等價(jià)關(guān)系 P Q P P Q P Q 證明 P Q P P Q P Q P P Q E2 結(jié)合律 P Q P Q E7 等冪律 P Q P Q E1 交換律 P Q P Q E2 結(jié)合律 P QE 1 E9 交換律 吸收律 例4判別下列公式的類(lèi)型 1 Q P P Q 2 P Q P 解 1 Q P P Q Q P P Q E11 E6 Q P P P Q E3 Q 1 P Q E5 Q P Q E4 Q P QE10 Q Q PE1 E2 0E5 E8 所以Q P P Q 是矛盾式 2 P Q P P Q PE11 PE9 于是該公式是可滿足式 三 命題公式的蘊(yùn)含關(guān)系定義2 4 2設(shè)A B是兩個(gè)公式 若公式A B是重言式 即A B 1 則稱公式A蘊(yùn)含公式B 記作A B 稱 A B 為蘊(yùn)含式 注意 1 符號(hào) 和 的區(qū)別和聯(lián)系 2 A B是偏序關(guān)系 即自反性 A A反對(duì)稱 若A B B A 則A B傳遞性 若A B B C 則A C 3 若A B和C是三個(gè)命題公式 且A B A C 則A B C 4 若A B和C是三個(gè)命題公式 且A C B C 則A B C 定理2 4 2A B當(dāng)且僅當(dāng)A B是永真公式 四 基本的蘊(yùn)含式 五 蘊(yùn)含式的判別判定 A B 是否成立的問(wèn)題可轉(zhuǎn)化為判定A B是否為重言式 有下述判定方法 1 真值表 2 等價(jià)演算 3 假定前件A為真 4 假定后件B為假 1 真值表方法 例4證明I14 P Q P R Q R R 證明令公式F P Q P R Q R R 其真值表如下 公式F對(duì)任意的一組真值指派取值均為1 故F是重言式 2 等價(jià)演算方法例5證明I11 P P Q Q 證明 P P Q Q P P Q QE11 P P Q E10 P Q P Q E2 1代入規(guī)則 E5因此P P Q Q 3 假定前件A真假定前件A為真 檢查在此情況下 其后件B是否也為真 例6證明I12 Q P Q P 證明令前件 Q P Q 為真 則 Q為真 且P Q為真 于是Q為假 因而P也為假 由此 P為真 故蘊(yùn)含式I12成立 4 假定后件B假假定后件B為假 檢查在此情況下 其前件A是否也為假 例7證明蘊(yùn)含式 P Q R S P R Q S 證明令后件 P R Q S 為假 則P R為真 Q S為假 于是P R均為真 而Q和S至少一個(gè)為假 由此可知P Q與R S中至少一個(gè)為假 因此 P Q R S 為假 故上述蘊(yùn)含式成立 練習(xí)2 41 判斷下列等值式是否成立 1 P Q R Q P R Q 2 P Q P Q P Q 解 1 P Q R Q P Q R Q E11 P R QE3 P R QE10 2 P Q P Q P Q Q P E6 E10 P Q Q P E11 P Q E14 P R QE11 2 判定蘊(yùn)含式P Q R P Q P R 是否成立 解假定后件 P Q P R 為假 則P Q為真 P R為假 由P R為假 得P為真 R為假 又P Q為真 故得Q為真 于是P為真 Q R為假 從而P Q R 為假 因此蘊(yùn)含式成立 2 5功能完備集 其他聯(lián)結(jié)詞 問(wèn)題 為了能構(gòu)造任何意義的命題公式 究竟需要定義多少邏輯聯(lián)結(jié)詞 A0 FA1 P QA2 P QA3 PA4 P QA5 QA6 P Q P Q A7 P Q 定義2 5 1設(shè)S是一個(gè)由一些邏輯聯(lián)結(jié)詞組成的集合 若對(duì)于任意給定的命題公式 總可以找到一個(gè)僅含有S中的邏輯聯(lián)結(jié)詞的命題公式與之等價(jià) 則稱S是一個(gè)聯(lián)結(jié)詞功能完備集 定義2 5 2設(shè)S是一個(gè)聯(lián)結(jié)詞功能完備集 若S中的任一聯(lián)結(jié)詞都不能用S中的其他聯(lián)結(jié)詞等價(jià)表達(dá) 則稱S是一個(gè)極小的聯(lián)結(jié)詞功能完備集 例 是極小的聯(lián)結(jié)詞功能完備集 2 6對(duì)偶與范式一 對(duì)偶 定義2 6 1設(shè)A是一個(gè)僅含有聯(lián)結(jié)詞 和 的命題公式 在A中用 代替 用 代替 用T代替F 用F代替T 所得的命題公式稱為A的對(duì)偶式 記為A 例如 P Q R和 P Q R互為對(duì)偶式 P Q R的對(duì)偶式是 P Q R 定理2 6 1設(shè)A是一個(gè)僅含有聯(lián)結(jié)詞 和 的命題公式 P1 P2 Pn是出現(xiàn)于其中的全部命題變?cè)?則 A P1 P2 Pn A P1 P2 Pn A P1 P2 Pn A P1 P2 Pn 定理2 6 2設(shè)A和B是兩個(gè)僅含有聯(lián)結(jié)詞 和 的命題公式 如果A B 則A B 二 范式1 析取范式和合取范式 定義2 6 2一個(gè)命題公式若具有P1 P2 Pn 的形式 n 1 其中Pi 是命題變?cè)狿i或其否定 Pi 則稱其為質(zhì)合取式 例如 P Q R S是由命題變?cè)狿 Q R S組成的一質(zhì)合取式 定義2 6 3一個(gè)命題公式若具有P1 P2 Pn n 1 的形式 其中P i是命題變?cè)狿i或是其否定 Pi 則稱其為質(zhì)析取式 例如 Q P R是由命題變?cè)狿 Q R組成的一質(zhì)析取式 定理2 6 3 1 一質(zhì)合取式為永假式的充分必要條件是 它同時(shí)包含某個(gè)命題變?cè)狿及其否定 P 2 一質(zhì)析取式為永真式的充分必要條件是 它同時(shí)包含某個(gè)命題變?cè)狿及其否定 P 證明 2 必要性 假設(shè)A P1 P2 Pn 為一質(zhì)析取式 且A為一永真式 反證法 假設(shè)A式中不同時(shí)包含任一命題變?cè)捌浞穸?則在A中 當(dāng)Pi 為Pi時(shí)指派Pi取0 當(dāng)Pi 為 Pi時(shí) 指派Pi取1 i 1 2 n 這樣的一組真值指派使A的真值取0 這與A為永真式矛盾 充分性 設(shè)A含命題變?cè)狿i和 Pi 而Pi Pi是永真式 由結(jié)合律和零一律 A的真值必為1 故A也是永真式 定義2 6 4質(zhì)合取式的析取稱為析取范式 即具有A1 A2 An n 1 的形式的公式 其中Ai是質(zhì)合取式 例如 F1 P P Q R P Q R 是一析取范式 定義2 6 5質(zhì)析取式的合取稱為合取范式 即具有A1 A2 An n 1 的形式的公式 其中Ai是質(zhì)析取式 例如 F2 P P Q R P Q R 是一合取范式 F3 P R Q P Q R P R 也是一合取范式 二 求公式的析取范式和合取范式 任何一個(gè)命題公式都可以變換為與它等值的析取范式或合取范式 按下列步驟進(jìn)行 1 利用E11 E12和E14消去公式中的運(yùn)算符 和 2 利用德 摩根定律將否定符號(hào) 向內(nèi)深入 使之只作用于命題變?cè)?3 利用雙重否定律E6將 P 置換成P 4 利用分配律 結(jié)合律將公式歸約為合取范式或析取范式 例1求F1 P Q R S的合取范式和析取范式 解F1 P Q R SE11 P Q R SE10 P Q R S 析取范式 E10 E6 又F1 P Q R S P S Q R E1 E2 P S Q P S R 合取范式 E3 另外由F1 P S Q P S R P P S R S P S R Q P S R E3 P S Q P Q S Q R 析取范式 E9 E13 例2求F2 P Q P Q 的析取范式 合取范式 解F2 P Q P Q P Q P Q E14 P Q P Q P Q P Q E11 E6 P Q P Q P Q P Q E2 E10 E10 P Q P Q 合取范式 E2 E9 P P Q Q P Q E3 P P P Q P Q Q Q 析取范式 E3 定理2 6 4 1 公式A為永真式的充分必要條件是 A的合取范式中每一質(zhì)析取式至少包含一對(duì)互為否定的析取項(xiàng) 三 利用范式判定公式類(lèi)型 證明 2 必要性 用反證法 假設(shè)A A1 A2 An中某個(gè)Ai不包含一對(duì)互為否定的合取項(xiàng) 2 公式A為永假式的充分必要條件是 A的析取范式中每一質(zhì)合取式至少包含一對(duì)互為否定的合取項(xiàng) 則由定理知 Ai不是矛盾式 于是存在一組真值指派使Ai取值為真 對(duì)同一組真值指派 A的取值也必為真 這與A是矛盾式不符 假設(shè)不成立 充分性 假設(shè)任一Ai 1 i n 中含有形如P P合取式 其中P為命題變?cè)?于是由定理知 每一Ai 1 i n 都為矛盾式 因此A1 A2 An必為矛盾式 即A為矛盾式 因此A的析取范式中每一質(zhì)合取式至少包含一對(duì)互為否定的合取項(xiàng) 例3判別公式A P P Q P 是否為重言式或矛盾式 解A P P Q P E11 P P Q P P 析取范式 E3 根據(jù)定理2 6 4 A不是矛盾式 又A P P Q P P P P Q P 合取范式 E3 由定理2 6 4知 A是重言式 例4利用范式判斷公式P P Q 的類(lèi)型 解P P Q P P Q P P Q E12 P Q P P Q E 10 P Q P 析取范式 E 9 由定理 該公式不是永假公式 P P P Q 合取范式 E1 E 3 由定理 該公式也不是永真公式 由上可知 該公式是一可滿足公式 又P P Q P Q P 四 主析取范式和主合取范式 一 極小項(xiàng) 極大項(xiàng)定義2 6 6設(shè)有命題變?cè)狿1 P2 Pn 形如的命題公式稱為是由命題變?cè)狿1 P2 Pn所產(chǎn)生的極小項(xiàng) 而形如的命題公式稱為是由命題變?cè)狿1 P2 Pn所產(chǎn)生的極大項(xiàng) 其中Pi 為Pi或?yàn)?Pi i 1 2 n 例如 P1 P2 P3 P1 P2 P3均是由P1 P2 P3所產(chǎn)生的極小項(xiàng) P1 P2 P3是由P1 P2 P3產(chǎn)生的一個(gè)極大項(xiàng) 常用mk 0 k 2n 1 表示極小項(xiàng) 其中k為二進(jìn)制t1t2 tn對(duì)應(yīng)的十進(jìn)制 且若Pi 為 Pi ti 0 否則Pi 為1 例如 三個(gè)命題變?cè)狿 Q R共形成八個(gè)極小項(xiàng)m0 P Q R m1 P Q R m2 P Q Rm3 P Q R m4 P Q R m5 P Q Rm6 P Q R m7 P Q R 常用Mk 0 k 2n 1 表示極大項(xiàng) 其中k為二進(jìn)制t1t2 tn對(duì)應(yīng)的十進(jìn)制 且若Pi 為 Pi ti 1 否則Pi 為0 M0 P Q R M1 P Q R M2 P Q RM3 P Q R M4 P Q R M5 P Q RM6 P Q R M7 P Q R 極小項(xiàng) 極小項(xiàng)的簡(jiǎn)記 極小項(xiàng)的性質(zhì) 1 每一個(gè)極小項(xiàng)mk在與其下標(biāo)相對(duì)應(yīng)的真值指派下真值為真 而在其余2n 1種真值指派下真值為假 2 任意兩個(gè)不同的極小項(xiàng)的合取式是一個(gè)永假式 3 全部2n個(gè)極小項(xiàng)的析取式是一個(gè)重言式 極大項(xiàng)的性質(zhì) 1 每一個(gè)極大項(xiàng)Mk在與其下標(biāo)相對(duì)應(yīng)的真值指派下真值為假 而在其余2n 1種真值指派下真值為真 2 任意兩個(gè)不同的極大項(xiàng)的析取式是一個(gè)永真式3 全部2n個(gè)極大項(xiàng)的合取式是一個(gè)矛盾式 定義2 6 7由不同極小項(xiàng)所組成的析取式 稱為主析取范式 定義7 18由不同極大項(xiàng)所組成的合取式 稱為主合取范式 例如 P1 P2 P3 P1 P2 P3 P1 P2 P3 是一個(gè)主析取范式 P1 P2 P3 P1 P2 P3 P1 P2 P3 P1 P2 P3 是一個(gè)主合取范式 五 求公式的主析取范式和主合取范式 一 真值表法 例 P Q P R P Q R P Q R P Q R P Q R m2 m3 m5 m7 P Q R P Q R P Q R P Q R M0 M1 M4 M6 定理2 6 5每一個(gè)不為永假的命題公式F P1 P2 Pn 必與一個(gè)由P1 P2 Pn所產(chǎn)生的主析取范式等價(jià) 永真公式的主析取范式包含所有2n個(gè)最小項(xiàng) 永假公式的主析取范式是一個(gè)空公式 用0表示 定理2 6 6每一個(gè)不為永真的公式F P1 P2 Pn 必與一個(gè)由P1 P2 Pn所產(chǎn)生的主合取范式等價(jià) 永假公式的主合取范式包含所有2n個(gè)最大項(xiàng) 永真公式的主合取范式是一空公式 用1表示 例4求公式F1 P P Q P 和公式F2 P Q P Q 的主析取范式 解F1 P P Q P E11 P P Q P P E3 P Q Q P Q P Q Q E7 E4 E5 P Q P Q P Q P Q P Q E3 P Q P Q P Q P Q E1 E7 二 公式演算法對(duì)任一給定的公式除了用求范式時(shí)的四個(gè)步驟外 還要利用同一律 等冪律 互否律 分配律等進(jìn)一步將質(zhì)合取式 質(zhì)析取式 變換為最小項(xiàng) 最大項(xiàng) 的形式 F2 P Q P Q P Q P Q E11 P P Q Q P Q E3 例5求公式F1 P Q P Q 和公式F2 P P Q P 的主合取范式 F1 P Q P Q E11 P Q P Q Q Q P P E 5 E4 P Q P Q P Q P Q P Q E 3 P Q P Q P Q P Q E 7 解F2 P P Q P E11 P P P Q P E3 1 1E5 E1 1 六 利用主范式判定公式類(lèi)型1 利用主析取范式判定 1 若公式F P1 P2 Pn 的主析取范式包含所有2n個(gè)最小項(xiàng) 則F是永真公式 2 若F的主析取范式是一空公式且為0 則F是永假公式 3 否則 F為可滿足的公式 2利用主合取范式判定 1 若公式F P1 P2 Pn 的主合取范式包含所有2n個(gè)最大項(xiàng) 則F是永假公式 2 若F的主合取范式是一空公式且為1 則F是永真公式 3 否則 F為可滿足公式 例6求公式F Q P Q P的主范式并判定公式的類(lèi)型 解 1 求F的主析取范式 F Q P Q P Q P Q P Q P P P Q P Q Q P Q P Q P Q P Q P Q P Q P Q P Q 由此可知F是可滿足公式 2 求F的主合取范式 F Q P Q P P Q 由前分析和舉例可知 僅需求出公式F的任一種主范式即可判定F的類(lèi)型 練習(xí)2 61 判斷公式F P Q P Q 是否為重言式或矛盾式 解F P Q P Q Q P E11 P Q P Q Q P E10 E6 E11 P Q P Q P Q Q P E3 P Q P Q P P Q Q Q P E3 P Q P Q Q P E5 E8 F的主析取范式既非空公式 又未包含22 4個(gè)項(xiàng) 故F不是重言式和矛盾式 只是可滿足式 2 7命題演算的推理理論 3 如果甲是冠軍 則乙或丙將得亞軍 如果乙得亞軍 則甲不能得冠軍 如果丁得亞軍 丙不能得亞軍 事實(shí)是甲已得冠軍 可知 不能得亞軍 例1 如果天不下雨 我就去看電影 我沒(méi)有去看電影 說(shuō)明 2 如果李敏出差到學(xué)校 若王軍不生病 則王軍一定去看望李敏 如果李敏出差到長(zhǎng)沙 那么李敏一定來(lái)學(xué)校 王軍沒(méi)有生病 所以 一 推理推理是由已知的命題得到新命題的思維過(guò)程 定義2 7 1設(shè)A和B是兩個(gè)命題公式 如果A B 即如果命題公式A B為重言式 則稱B是前提A的結(jié)論或從A推出結(jié)論B 一般地設(shè)H1 H2 Hn和C是一些命題公式 若蘊(yùn)含式H1 H2 Hn C 成立 則稱C是前提集合 H1 H2 Hn 的結(jié)論 或稱從前提H1 H2 Hn能推出結(jié)論C 有時(shí)也記作H1 H2 Hn C 1 真值表法對(duì)于命題公式中所有命題變?cè)拿恳唤M真值指派作出該公式的真值表 看是否為永真 例1考察結(jié)論C是否是下列前提H1 H2的結(jié)論 1 H1 P Q H2 P C Q 二 如何判斷由一個(gè)前提集合能否推出某個(gè)結(jié)論 2 H1 P Q H2 P C Q 2 真值演算方法例證明 分析根據(jù)題意 需證明 證明 3 形式證明 方法 1 基本述語(yǔ)形式證明 一個(gè)描述推理過(guò)程的命題序列 其中每個(gè)命題或者是已知的命題 或者是由某些前提所推得的結(jié)論 序列中最后一個(gè)命題就是所要求的結(jié)論 這樣的命題序列稱為形式證明 有效的證明 如果證明過(guò)程中的每一步所得到的結(jié)論都是根據(jù)推理規(guī)則得到的 則這樣的證明稱作是有效的 有效的結(jié)論 通過(guò)有效的證明而得到結(jié)論 稱作是有效的結(jié)論 合理的證明 一個(gè)證明是否有效與前提的真假?zèng)]有關(guān)系 如果所有的前提都是真的 那么通過(guò)有效的證明所得到的結(jié)論也是真的 這樣的證明稱作是合理的 合理的結(jié)論 一個(gè)結(jié)論是否有效與它自身的真假?zèng)]有關(guān)系 通過(guò)合理證明而得到的結(jié)論稱作合理的結(jié)論 2 推理規(guī)則前提引用規(guī)則 P規(guī)則 在證明的任何步驟上都可以引用前提 結(jié)論引用規(guī)則 T規(guī)則 在證明的任何步驟上所得到的結(jié)論都可以在其后的證明中引用 置換規(guī)則 在證明的任何步驟上 命題公式的子公式都可以用與它等價(jià)的其它命題公式置換 代入規(guī)則 在證明的任何步驟上 重言式中的任一命題變?cè)伎梢杂靡幻}公式代入 得到的仍是重言式 例2證明R P Q 是前提P Q Q R P S S的結(jié)論 所以P Q Q R P S S R P Q 例3證明R S是前提P Q S R P和Q的有效結(jié)論 練習(xí)用形式證明方法證明 1 P Q是前提 P Q R R S S的結(jié)論 因此 P Q R R S S P Q CP規(guī)則 利用永真蘊(yùn)含式 要證明P Q R 則等價(jià)于證明P Q R將例3等價(jià)地改為證明由前提推出結(jié)論S 例4符號(hào)化下面語(yǔ)句的推理過(guò)程 并指出推理是否正確 如果甲是冠軍 則乙或丙將得亞軍 如果乙得亞軍 則甲不能得冠軍 如果丁得亞軍 丙不能得亞軍 事實(shí)是甲已得冠軍 可知丁不能得亞軍 解設(shè)A 甲得冠軍 B 乙得亞軍 C 丙得亞軍 D 丁得亞軍 推理過(guò)程符號(hào)化為A B C B A D C A D 4 間接證明 或反證法 定義2 7 2如果對(duì)于出現(xiàn)在公式H1 H2 Hn中的命題變?cè)娜魏我唤M真值指派 公式H1 H2 Hn中至少有一個(gè)為假 即它們的合取式H1 H2 Hn是矛盾式 則稱公式H1 H2 Hn是不相容的 否則稱公式H1 H2 Hn是相容的 定理2 7 1若存在一個(gè)公式R 使得H1 H2 Hn R R則公式H1 H2 Hn是不相容的 證明設(shè)H1 H2 Hn R R 而R R是矛盾式 所以前件H1 Hn必永假 因此 H1 H2 Hn是不相容的 則意味著 H1 H2 Hn R R 是重言式 為了證明H1 H2 Hn C 利用定理2 7 1 將 C添加到這一組前提中 轉(zhuǎn)化為證明H1 H2 Hn C R R 于是得出H1 H2 Hn C是不相容的 即H1 H2 Hn C是永假公式 這意味著當(dāng)H1 H2 Hn為真時(shí) C必為假 因而C必為真 例5證明 R Q R S S Q P Q P 用反證法 將 P 作為附加前提 添加到前提集合中 然后推出矛盾 證明 因此 R Q R S S Q P Q P 習(xí)題2 71 判斷下列推理是否正確如果這里有球賽 則通行是困難的 如果他們按指定的時(shí)間到達(dá) 則通行是不困難的 他們按指定時(shí)間到達(dá)了 所以這里沒(méi)有球賽 解先將已知條件符號(hào)化 令P 這里有球賽 Q 通行是困難的 R 他們按指定的時(shí)間到達(dá)了 編號(hào)公式依據(jù) 1 R QP 因此上述推理正確 2 RP 3 QT 1 2 I 4 P QP 5 PT 3 4 I 則上述推理過(guò)程符號(hào)化為P Q R Q R P 2 張三說(shuō)李四在說(shuō)謊 李四說(shuō)王五在說(shuō)謊 王五說(shuō)張三 李四都在說(shuō)謊 問(wèn)張三 李四 王五三人 到底誰(shuí)說(shuō)真話 誰(shuí)說(shuō)假話 解先將簡(jiǎn)單命題符號(hào)化 令P 張三說(shuō)真話 Q 李四說(shuō)真話 R 王五說(shuō)真話 由題意知推理的前提為 P Q P Q Q R Q R R P Q R P Q 下面根據(jù)已知前提進(jìn)行形式推理 因此 由上述推理知張三說(shuō)假話 王五說(shuō)假話 只有李四說(shuō)真話