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

《離散數(shù)學講義第二章命題邏輯.ppt》由會員分享，可在線閱讀，更多相關《離散數(shù)學講義第二章命題邏輯.ppt（88頁珍藏版）》請在裝配圖網(wǎng)上搜索。

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