離散數(shù)學(xué)_命題邏輯.ppt

離散數(shù)學(xué)命題邏輯 Proposition 主講教師 吳旭 第一章命題邏輯數(shù)理邏輯是用數(shù)學(xué)方法研究思維規(guī)律的一門學(xué)科 所謂數(shù)學(xué)方法是指 用一套數(shù)學(xué)的符號系統(tǒng)來描述和處理思維的形式與規(guī)律 因此 數(shù)理邏輯又稱為符號邏輯 本章介紹數(shù)理邏輯中最基本的內(nèi)容命題邏輯 首先引入命題 命題公式等概念 然后 在此基礎(chǔ)上研究命題公式間的等值關(guān)系和蘊含關(guān)系 并給出推理規(guī)則 進行命題演繹 主要內(nèi)容如下 命題和命題聯(lián)結(jié)詞命題公式與翻譯命題公式的等值關(guān)系和蘊含關(guān)系對偶與范式命題演算的推理理論 例1判斷下列語句是否是命題 1 空氣是人生存所必需的 2 請把門關(guān)上 3 南京是中國的首都 4 你吃飯了嗎 5 x 3 6 啊 真美呀 7 明年春節(jié)是個大晴天 解語句 1 3 5 7 是陳述句 1 3 7 是命題 用真值來描述命題是 真 還是 假 分別用 1 和 0 表示 命題用大寫的拉丁字母A B C P Q 或者帶下標(biāo)的大寫的字母來表示 例2判斷下列陳述句是否是命題 P 地球外的星球上也有人 Q 小王是我的好朋友 解P Q是命題 二 命題聯(lián)結(jié)詞 原子命題 由簡單句形成的命題 復(fù)合命題 由一個或幾個原子命題通過聯(lián)結(jié)詞的聯(lián)接而構(gòu)成的命題 例3A 李明既是三好學(xué)生又是足球隊員 B 張平或者正在釣魚或者正在睡覺 C 如果明天天氣晴朗 那么我們舉行運動會 定義五種聯(lián)結(jié)詞 或稱命題的五種運算 1 否定 定義1 1設(shè)P是一個命題 利用 和P組成的復(fù)合命題稱為P的否命題 記作 P 讀作 非P 命題P取值為真時 命題 P取值為假 命題P取值為假時 命題 P取值為真 例4設(shè)P 上海是一個城市 Q 每個自然數(shù)都是偶數(shù) 則有 P 上海不是一個城市 Q 并非每個自然數(shù)都是偶數(shù) 2 合取 定義1 2設(shè)P和Q是兩個命題 由P Q利用 組成的復(fù)合命題 稱為合取式復(fù)合命題 記作 P Q 讀作 P且Q 當(dāng)且僅當(dāng)命題P和Q均取值為真時 P Q才取值為真 例5設(shè)P 我們?nèi)タ措娪?Q 房間里有十張桌子 則P Q表示 我們?nèi)タ措娪安⑶曳块g里有十張桌子 3 析取 定義1 3由命題P和Q利用 組成的復(fù)合命題 稱為析取式復(fù)合命題 記作 P Q 讀作 P或Q 當(dāng)且僅當(dāng)P和Q至少有一個取值為真時 P Q取值為真 例6將命題 他可能是100米或400米賽跑的冠軍 符號化 解令P 他可能是100米賽跑冠軍 Q 他可能是400米賽跑冠軍 則命題可表示為P Q 設(shè)P Q是兩個命題 P異或Q是一個復(fù)合命題 記作P Q 4 蘊含 定義1 4由命題P和Q利用 組成的復(fù)合命題 稱為蘊含式復(fù)合命題 記作 P Q 讀作 如果P 則Q 當(dāng)P為真 Q為假時 P Q為假 否則P Q為真 例8將命題 如果我得到這本小說 那么我今夜就讀完它 符號化 解令P 我得到這本小說 Q 我今夜就讀完它 于是上述命題可表示為P Q 例9若P 雪是黑色的 Q 太陽從西邊升起 R 太陽從東邊升起 則P Q和P R所表示的命題都是真的 5 等值 定義1 5由命題P和Q 利用 組成的復(fù)合命題 稱為等值式復(fù)合命題 記作 P Q 讀作 P當(dāng)且僅當(dāng)Q 當(dāng)P和Q的真值相同時 P Q取真 否則取假 例10非本倉庫工作人員 一律不得入內(nèi) 解令P 某人是倉庫工作人員 Q 某人可以進入倉庫 則上述命題可表示為P Q 例11黃山比喜馬拉雅山高 當(dāng)且僅當(dāng)3是素數(shù)令P 黃山比喜馬拉雅山高 Q 3是素數(shù)本例可符號化為P Q 從漢語的語義看 P與Q之間并無聯(lián)系 但就聯(lián)結(jié)詞 的定義來看 因為P的真值為假 Q的真值為真 所以P Q的真值為假 對于上述五種聯(lián)結(jié)詞 應(yīng)注意到 復(fù)合命題的真值只取決于構(gòu)成它的各原子命題的真值 而與這些原子命題的內(nèi)容含義無關(guān) 三 命題符號化利用聯(lián)結(jié)詞可以把許多日常語句符號化 基本步驟如下 1 從語句中分析出各原子命題 將它們符號化 2 使用合適的命題聯(lián)結(jié)詞 把原子命題逐個聯(lián)結(jié)起來 組成復(fù)合命題的符號化表示 例12用符號形式表示下列命題 1 如果明天早上下雨或下雪 那么我不去學(xué)校 2 如果明天早上不下雨且不下雪 那么我去學(xué)校 3 如果明天早上不是雨夾雪 那么我去學(xué)校 4 只有當(dāng)明天早上不下雨且不下雪時 我才去學(xué)校 解令P 明天早上下雨 Q 明天早上下雪 R 我去學(xué)校 2 P Q R 1 P Q R 4 R P Q 3 P Q R 例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 練習(xí)1 11 判斷下列語句哪些是命題 若是命題 則指出其真值 1 只有小孩才愛哭 2 X 6 Y 3 銀是白的 4 起來吧 我的朋友 是假 不是 是真 不是 2 將下列命題符號化 1 我看見的既不是小張也不是老李 解令P 我看見的是小張 Q 我看見的是老李 則該命題可表示為 P Q 2 如果晚上做完了作業(yè)并且沒有其它的事 他就會看電視或聽音樂 解令P 他晚上做完了作業(yè) Q 他晚上有其它的事 R 他看電視 S 他聽音樂 則該命題可表示為 P Q R S 命題公式一 命題公式的概念1 命題常元一個表示確定命題的大寫字母或T和F 2 命題變元一個沒有指定具體內(nèi)容的命題符號 一個命題變元當(dāng)沒有對其賦予內(nèi)容時 它的真值不能確定 一旦用一個具體的命題代入 它的真值就確定了 3 命題公式命題公式 或簡稱公式 是由0 F 1 T 和命題變元以及命題聯(lián)結(jié)詞按一定的規(guī)則產(chǎn)生的符號串 定義1 6 命題公式的遞歸定義 0 F 1 T 是命題公式 命題變元是命題公式 如果A是命題公式 則 A是命題公式 如果A和B是命題公式 則 A B A B A B A B 也是命題公式 有限次地利用上述 而產(chǎn)生的符號串是命題公式 例1下列符號串是否為命題公式 P Q PR P Q Q R 解 不是命題公式 是命題公式 二 真值指派命題公式代表一個命題 但只有當(dāng)公式中的每一個命題變元都用一個確定的命題代入時 命題公式才有確定的真值 成為命題 定義1 7設(shè)F為含有命題變元P1 P2 Pn的命題公式 對P1 P2 Pn分別指定一個真值 稱為對公式F的一組真值指派 公式與其命題變元之間的真值關(guān)系 可以用真值表的方法表示出來 例2給出公式F P Q Q R P R 的真值表 解公式F的真值表如下 三 公式類型定義1 8如果對于命題公式F所包含的命題變元的任何一組真值指派 F的真值恒為真 則稱公式F為重言式 或永真公式 常用 1 T 表示 相反地 若對于F所包含的命題變元的任何一組真值指派 F的真值恒為假 則稱公式F為矛盾式 或永假公式 常用 0 F 表示 如果至少有一組真值指派使公式F的真值為真 則稱F為可滿足公式 例3構(gòu)造下列命題公式的真值表 并判斷它們是何種類型的公式 P Q P Q Q P P Q P Q Q R P R 由上可知 F1是重言式 F2是矛盾式 3 的真值表自己做一下 它是可滿足公式 命題公式的等值關(guān)系和蘊含關(guān)系 一 命題公式的等值關(guān)系定義1 9設(shè)A和B是兩個命題公式 P1 P2 Pn是所有出現(xiàn)于A和B中的命題變元 如果對于P1 P2 Pn的任一組真值指派 A和B的真值都相同 則稱公式A和B等值 記為A B 稱A B為等值式 注意 1 符號 與 的區(qū)別與聯(lián)系 不是聯(lián)結(jié)詞 A B不表示一個公式 它表示兩個公式間的一種關(guān)系 即等值關(guān)系 是聯(lián)結(jié)詞 A B是一個公式 A B當(dāng)且僅當(dāng)A B是永真公式 2 可以驗證等值關(guān)系是等價關(guān)系 即自反性 對任意公式A 有A A 對稱性 對任意公式A B 若A B 則B A 可傳遞性 對任意公式A B C 若A B B C 則A C 3 當(dāng)A是重言式時 A 1 當(dāng)A是矛盾式時 則A 0 二 基本的等值式設(shè)P Q R是命題變元 下表中列出了24個最基本的等值式 三 等值式的判別有兩種方法 真值表方法 命題演算方法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ī)則代入規(guī)則對于重言式中的任一命題變元出現(xiàn)的每一處均用同一命題公式代入 得到的仍是重言式 2 等值演算方法 例如F P Q Q P 是重言式 若用公式A B代換命題變元P得公式F1 A B Q Q A B F1仍是重言式 注意 因為A B當(dāng)且僅當(dāng)A B是重言式 所以 若對于等值式中的任一命題變元出現(xiàn)的每一處均用同一命題公式代入 則得到的仍是等值式 2 置換規(guī)則定義1 10設(shè)C是命題公式A的一部分 即C是公式A中連續(xù)的幾個符號 且C本身也是一個命題公式 則稱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 等值演算等值演算是指利用已知的一些等值式 根據(jù)置換規(guī)則 代入規(guī)則以及等值關(guān)系的可傳遞性推導(dǎo)出另外一些等值式的過程 由代入規(guī)則知前述的基本等值式 不僅對任意的命題變元P Q R是成立的 而且當(dāng)P Q R分別為命題公式時 這些等值式也成立 例2證明命題公式的等值關(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證明下列命題公式的等值關(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判別下列公式的類型 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 于是該公式是可滿足式 三 命題公式的蘊含關(guān)系定義1 11設(shè)A B是兩個公式 若公式A B是重言式 即A B 1 則稱公式A蘊含公式B 記作A B 稱 A B 為蘊含式 注意 符號 和 的區(qū)別和聯(lián)系與符號 與 的區(qū)別和聯(lián)系類似 不是聯(lián)結(jié)詞 A B 不是公式 它表示公式A與B之間存在蘊含關(guān)系 是聯(lián)系詞 A B是一個公式 A B當(dāng)且僅當(dāng)A B是永真公式 A B是偏序關(guān)系 即自反性 A A 反對稱 若A B B A 則A B 傳遞性 若A B B C 則A C 反對稱性的證明 設(shè)A B且B A 由定義7 11A B 1且B A 1 于是A B A B B A E14 1 1 1因此A B 傳遞性的證明 設(shè)A B B C 則A B 1 B C 1 A B C A B C A B C A B C 1 C A 1 1 1 1 因此A C 于是A C A C A C B B 四 基本的蘊含式 五 蘊含式的判別判定 A B 是否成立的問題可轉(zhuǎn)化為判定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 QE10 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 為假 故上述蘊含式成立 練習(xí)1 31 判斷下列等值式是否成立 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 為假 因此蘊含式成立 范式一 析取范式和合取范式 定義1 12一個命題公式若它具有P1 P2 Pn 的形式 n 1 其中Pi 是命題變元Pi或其否定 Pi 則稱其為質(zhì)合取式 基本積 例如 P Q R S是由命題變元P Q R S組成的一質(zhì)合取式 基本積 定義1 13一個命題公式若具有P1 P2 Pn n 1 的形式 其中P i是命題變元Pi或是其否定 Pi 則稱其為質(zhì)析取式 基本和 例如 Q P R是由命題變元P Q R組成的一質(zhì)析取式 基本和 定理1 4 1 一質(zhì)合取式為永假式的充分必要條件是 它同時包含某個命題變元P及其否定 P 2 一質(zhì)析取式為永真式的充分必要條件是 它同時包含某個命題變元P及其否定 P 證明 2 必要性 假設(shè)A P1 P2 Pn 為一質(zhì)析取式 且A為一永真式 反證法 假設(shè)A式中不同時包含任一命題變元及其否定 則在A中 當(dāng)Pi 為Pi時指派Pi取0 當(dāng)Pi 為 Pi時 指派Pi取1 i 1 2 n 這樣的一組真值指派使A的真值取0 這與A為永真式矛盾 例如A P1 P2 P3 則 P1 P2 P3 0 1 0 的指派 使A的真值為0 充分性 設(shè)A含命題變元Pi和 Pi 而Pi Pi是永真式 由結(jié)合律和零一律 A的真值必為1 故A也是永真式 定義1 14質(zhì)合取式的析取稱為析取范式 即具有A1 A2 An n 1 的形式的公式 其中Ai是質(zhì)合取式 例如 F1 P P Q R P Q R 是一析取范式 定義1 15質(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 也是一合取范式 二 求公式的析取范式和合取范式 任何一個命題公式都可以變換為與它等值的析取范式或合取范式 按下列步驟進行 1 利用E11 E12和E14消去公式中的運算符 和 2 利用德 摩根定律將否定符號 向內(nèi)深入 使之只作用于命題變元 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 定理1 5 1 公式A為永真式的充分必要條件是 A的合取范式中每一質(zhì)析取式至少包含一對互為否定的析取項 三 利用范式判定公式類型 證明 2 必要性 用反證法 假設(shè)A A1 A2 An中某個Ai不包含一對互為否定的合取項 2 公式A為永假式的充分必要條件是 A的析取范式中每一質(zhì)合取式至少包含一對互為否定的合取項 則由定理7 4知 Ai不是矛盾式 于是存在一組真值指派使Ai取值為真 對同一組真值指派 A的取值也必為真 這與A是矛盾式不符 假設(shè)不成立 充分性 假設(shè)任一Ai 1 i n 中含有形如P P合取式 其中P為命題變元 于是由定理7 4知 每一Ai 1 i n 都為矛盾式 因此A1 A2 An必為矛盾式 即A為矛盾式 因此A的析取范式中每一質(zhì)合取式至少包含一對互為否定的合取項 例3判別公式A P P Q P 是否為重言式或矛盾式 解A P P Q P E11 P P Q P P 析取范式 E3 根據(jù)定理7 5 A不是矛盾式 又A P P Q P P P P Q P 合取范式 E3 由定理1 5知 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 由定理1 5 該公式不是永假公式 P P P Q 合取范式 E1 E 3 由定理7 5 該公式也不是永真公式 由上可知 該公式是一可滿足公式 又P P Q P Q P 四 主析取范式和主合取范式定義1 16設(shè)有命題變元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)生的一個最大項 定義1 17由不同最小項所組成的析取式 稱為主析取范式 定義1 18由不同最大項所組成的合取式 稱為主合取范式 例如 P1 P2 P3 P1 P2 P3 P1 P2 P3 是一個主析取范式 P1 P2 P3 P1 P2 P3 P1 P2 P3 P1 P2 P3 是一個主合取范式 例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 五 求公式的主析取范式和主合取范式對任一給定的公式除了用求范式時的四個步驟外 還要利用同一律 等冪律 互否律 分配律等進一步將質(zhì)合取式 質(zhì)析取式 變換為最小項 最大項 的形式 F2 P Q P Q P Q P Q E11 P P Q Q P Q E3 定理1 6每一個不為永假的命題公式F P1 P2 Pn 必與一個由P1 P2 Pn所產(chǎn)生的主析取范式等值 永真公式的主析取范式包含所有2n個最小項 永假公式的主析取范式是一個空公式 用0表示 例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 7每一個不為永真的公式F P1 P2 Pn 必與一個由P1 P2 Pn所產(chǎn)生的主合取范式等值 永假公式的主合取范式包含所有2n個最大項 永真公式的主合取范式是一空公式 用1表示 六 利用主范式判定公式類型1 利用主析取范式判定 1 若公式F P1 P2 Pn 的主析取范式包含所有2n個最小項 則F是永真公式 例如 例4中的F1 2 若F的主析取范式是一空公式且為0 則F是永假公式 例如 例4中的F2 3 否則 F為可滿足的公式 2利用主合取范式判定 1 若公式F P1 P2 Pn 的主合取范式包含所有2n個最大項 則F是永假公式 例如 例5中的F1 2 若F的主合取范式是一空公式且為1 則F是永真公式 例如 例5中的F2 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的類型 練習(xí)1 41 判斷公式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不是重言式和矛盾式 只是可滿足式 命題演算的推理理論一 推理推理是由已知的命題得到新命題的思維過程 定義1 19設(shè)A和B是兩個命題公式 如果A B 即如果命題公式A B為重言式 則稱B是前提A的結(jié)論或從A推出結(jié)論B 一般地設(shè)H1 H2 Hn和C是一些命題公式 若蘊含式H1 H2 Hn C 成立 則稱C是前提集合 H1 H2 Hn 的結(jié)論 或稱從前提H1 H2 Hn能推出結(jié)論C 有時也記作H1 H2 Hn C 1 真值表法對于命題公式中所有命題變元的每一組真值指派作出該公式的真值表 看是否為永真 例1考察結(jié)論C是否是下列前提H1 H2的結(jié)論 1 H1 P Q H2 P C Q 二 如何判斷由一個前提集合能否推出某個結(jié)論 2 H1 P Q H2 P C Q 在這里 我們不關(guān)心結(jié)論是真還是假 而主要關(guān)心由給定的前提是否能推出這個結(jié)論來 2 等值演算方法例證明 分析根據(jù)題意 需證明 證明 3 形式證明 方法 1 基本述語形式證明 一個描述推理過程的命題序列 其中每個命題或者是已知的命題 或者是由某些前提所推得的結(jié)論 序列中最后一個命題就是所要求的結(jié)論 這樣的命題序列稱為形式證明 有效的證明 如果證明過程中的每一步所得到的結(jié)論都是根據(jù)推理規(guī)則得到的 則這樣的證明稱作是有效的 有效的結(jié)論 通過有效的證明而得到結(jié)論 稱作是有效的結(jié)論 合理的證明 一個證明是否有效與前提的真假沒有關(guān)系 如果所有的前提都是真的 那么通過有效的證明所得到的結(jié)論也是真的 這樣的證明稱作是合理的 合理的結(jié)論 一個結(jié)論是否有效與它自身的真假沒有關(guān)系 通過合理證明而得到的結(jié)論稱作合理的結(jié)論 2 推理規(guī)則前提引用規(guī)則 在證明的任何步驟上都可以引用前提 結(jié)論引用規(guī)則 在證明的任何步驟上所得到的結(jié)論都可以在其后的證明中引用 置換規(guī)則 在證明的任何步驟上 命題公式的子公式都可以用與它等值的其它命題公式置換 代入規(guī)則 在證明的任何步驟上 重言式中的任一命題變元都可以用一命題公式代入 得到的仍是重言式 例2證明R P Q 是前提P Q Q R P S S的結(jié)論 所以