[小學教育]ch01邏輯證明集合函數-資料下載頁

　　

【正文】 結論： A=P∧ ? P 問題： 該結論是否有效結論。 (該推理是否正確 )。 (P∨ ? P → ?Q) ∧ Q →P ∧ ? P Institute of Computer Software 王兵 證明： (P∨ Q) →R= ( P →R) ∧ (Q →R) Institute of Computer Software 王兵 真值表和等值推理能滿足所有推理嗎？ 1. 如果明天天晴，我們準備外出旅游。 P→Q 2．明天的確天晴。 P 結論：我們外出旅游。 Q Institute of Computer Software 王兵 蘊含推理 等值推理 真值表 ? ? Institute of Computer Software 王兵 蘊含式 如果 A→ B是一永真式 , 那么稱為永真蘊含式 , 記為 A B, 讀做 “ A永真蘊含 B”。 ?? ? → Institute of Computer Software 王兵 “ ?” 與 “ → ” 的不同 ? 1.“→” 僅是一般的 蘊涵聯結詞 ， G→H 的結果仍是一個公式，而“ ?”卻描述了兩個公式 G， H之間的一種邏輯蘊涵關系， G ? H的“結果”，是非命題公式； 2. 用計算機來判斷 G ? H是辦不到的。然而計算機卻可“計算”公式 G→H 是否為永真公式。 Institute of Computer Software 王兵 推理定律 Institute of Computer Software 王兵 2022/4/14 例子 ? 1)、前提： – 1. 如果明天天晴，我們準備外出旅游。 P→Q – 2．明天的確天晴。 P ? 結論：我們外出旅游。 Q ? 可描述為： P→Q ， P?Q (假言推理 ) Institute of Computer Software 王兵 ? 2)、前提： – 1. 如果一個人是單身漢，則他不幸福。 P→Q – 2. 如果一個人不幸福，則他死得早。 Q→R ? 結論：單身漢死得早。 P→R ? 可描述為： P→Q ， Q→R ?P→R (假言三段論 ) Institute of Computer Software 王兵 2022/4/14 例子 (續 1) ? 3)、某女子在某日晚歸家途中被殺害，據多方調查確證，兇手必為王某或陳某，但后又查證，作案之晚王某在工廠值夜班，沒有外出，根據上述案情可得前提： 或陳某 。 P∨Q ? ，則他在作案當晚必外出 P→R –。 ┐R ? 結論：陳某是兇手。 Q ? 則 可描述為 ： P→R,┐R ?┐P (否定后件式 ) – P∨Q ， ┐P ?Q (選言三段論 ) Institute of Computer Software 王兵 演繹法 ? 演繹法 是從前提 (假設 )出發，依據公認的推理規則和推理定律，推導出一個結論來。 Y N 觸發規則 新事實 事實 =結論？ 事實庫 規則匹配 公理庫 將事實加入到事實庫中 結束 引入事實 Institute of Computer Software 王兵 2022/4/14 引入推理規則 ? 在數理邏輯中，主要的推理規則有： ? ① P規則（稱為前提引用規則）： 在推導的過程中，可 隨時引入前提集合中的任意一個前提 ； ? ② 規則Ｔ（邏輯結果引用規則）： 在推導的過程中，可以 隨時引入公式 S，該公式 S是由其前的一個或多個公式推導出來的邏輯結果 。 ? ③ 規則ＣＰ（附加前提規則）： 如果能從給定的 前提集合 Г 與公式 P推導出 S，則能從此 前提集合 Г 推導出 P→S 。 Institute of Computer Software 王兵 考慮下述論證 : 。 如果這里有球賽 , 則通行是困難的 。 如果他們按時到達 , 則通行是不困難的 。 他們按時到達了 。 所以這里沒有球賽 。 Institute of Computer Software 王兵 設 P: 這里有球賽 , Q: 通行是困難的 , R: 他們按時到達。這論證能表達如下 : 1)R? ┐ Q 前提引入 2） R 前提引入 3) ┐ Q 假言推理 1,2 4） P?Q 前提引入 5) ┐P 取拒式 3,4 Institute of Computer Software 王兵 例 如果考試及格，那我高興。若我高興，那么我飯量增加。我的飯量沒增加，所以我考試沒有及格。試對上述論證構造證明 解：設 P：我考試及格 . Q：我高興。 R：我飯量 增加。則此論證可表為 (P→Q) ?(Q→R) ?┐R?┐P Institute of Computer Software 王兵 證 : 1 P→Q P 2 Q→R P 3 ┐R P 4 ┐Q T， 2， 3 I11 5 ┐P T， 1， 4 I11 Institute of Computer Software 王兵 構造下列的推理的證明： 前提： P∨ Q,P→ ? R,S→M, ?S→R, ? M 結論： Q。 證： ① ? M P ② S→M P ③ ? S ①② I拒取式 ④ ? S→R P ⑤ R ③ ④ I假言推理 ⑥ P→ ? R P ⑦ ? P ⑤ ⑥ I拒取式 ⑧ P∨ Q P ⑨ Q ⑦ ⑧ I析取三段式 Institute of Computer Software 王兵 例 證明 R∧ （ P∨Q ）是前提 P∨Q ，Q→ R， P→ S ， 172。S的結論。 所以 P∨ Q， Q→ R， P→ S， 172。 S ? R∧ （ P∨ Q) 編號 公 式 依 據 （ 1） （ 2） （ 3） （ 4） （ 5） （ 6） （ 7） （ 8） P→ S 172。S 172。P P∨ Q Q Q→ R R R∧ （ P∨ Q） 前提（前提引入規則） 前提（前提引入規則） （ 1），（ 2）；取拒 前提 （ 3），（ 4）；析取三段論 前提 （ 5），（ 6）；假言推理 （ 4），（ 7）；合取 Institute of Computer Software 王兵 例 ? 一個公安人員審查一件盜竊案，已知的事實如下： ? A或 B盜竊了 x； ? 若 A盜竊了 x，則作案時間不能發生在午夜前； ? 若 B證詞正確，則在午夜時屋里燈光未滅； ? 若 B證詞不正確，則作案時間發生在午夜前； ? 午夜時屋里燈光滅了。 B盜竊了 x。 證明 設 P： A盜竊了 x； Q： B盜竊了 x； R：作案時間發生在午夜前； S： B證詞正確； T：在午夜時屋里燈光滅了。 則上述命題可符號化為： P∨ Q， P→ ?R， S→ ?T， ?S→R ， T ? Q Institute of Computer Software 王兵 2022/4/14 證明（續） ? 證明 1 采用 直接證明 方法 ? （ 1） T Ｐ ? （ 2） S→ ?T Ｐ ? （ 3） ?S Ｔ，（ 1），（ 2）， I ? （ 4） ?S→R Ｐ ? （ 5） R Ｔ，（ 3），（ 4）， I ? （ 6） P→┐R P ? （ 7） ?P Ｔ，（ 5），（ 6）， I ? （ 8） P∨Q Ｐ ? （ 9） Q Ｔ，（ 7），（ 8）， I Institute of Computer Software 王兵 2022/4/14 ? 證明 令 P：馬會飛； Q：羊吃草； ? R：母雞是飛鳥； ? S：烤熟的鴨子還會跑。 符號化上述語句為：Г ={P∨Q→R,R→S,┐S},G=┐Q 。證明Г ?G。 如果馬會飛或羊吃草，則母雞就會是飛鳥；如果母雞是飛鳥，那么烤熟的鴨子還會跑；烤熟的鴨子不會跑。所以羊不吃草。 例 Institute of Computer Software 王兵 2022/4/14 證 明 （續） ⑴ ┐ S P ⑵ R→S P ⑶ ┐ R T,⑴ ,⑵ ,I ⑷ P∨Q→R P ⑸ ┐ (P∨Q) T,⑶ ,⑷ ,I ⑹ ┐ P∧┐Q T,⑸ ,E ⑺ ┐ Q T,⑹ ,I Institute of Computer Software 王兵 張三說李四在說謊，李四說王五在說謊，王五說張三、 李四都在說謊。問張三、李四、王五三人，到底誰說真話，誰說假話？ 解 先將簡單命題符號化。 令 P：張三說真話； Q：李四說真話； R：王五說真話， 由題意知推理的前提為： P→ 172。 Q， 172。P→ Q， Q→ 172。R， 172。 Q→ R， R→ （ 172。P∧ 172。 Q）， 172。 R→ （ P∨ Q）。 下面根據已知前提進行形式推理。 Institute of Computer Software 王兵 因此，由上述推理知張三說假話，王五說假話，只有李四說真話。 編 號 公 式 依 據 （ 1） P → 172。 Q 前 提 （ 2） 172。 Q→ R 前 提 （ 3） P→ R （ 1），（ 2）；假言三段 （ 4） R→ （ 172。P∧ 172。Q） 前 提 （ 5） P→ （ 172。P∧ 172。 Q） （ 3），（ 4）；假言三段 （ 6） 172。P∨ （ 172。P∧ 172。 Q） （ 5）； E11 （ 7） 172。P （ 6）； E9 （ 8） 172。P→ Q 前 提 （ 9） Q （ 7），（ 8）； I11 （ 10） Q→ 172。R 前 提 （ 11） 172。R （ 9），（ 10）； I11 （ 12） 172。P∧ Q∧ 172。R （ 7），（ 9），（ 11）； I9 Institute of Computer Software 王兵 172 帶量詞的推理規則 為了構造推理系統，還要給出 4條重要的推理規則 ,即 消去量詞 和 引入量詞 的規則： 四條重要的推理規則 ，簡記為 UI ，簡記為 EI ，簡記為 EG ，簡記為 UG Institute of Computer Software 王兵 173 帶量詞的推理規則 ? 全稱量詞消去規則 (?) – c是個體常元 , c∈ D ? 所有人會思考 ? 李明會思考 ?xA(x) ?A(c) Institute of Computer Software 王兵 174 帶量詞的推理規則 ? 全稱量詞引入規則 (?+)