命題邏輯PPT學習教案

1、會計學1命題邏輯命題邏輯2數(shù)理邏輯是計算機應用和理論研究的理論基礎。本章數(shù)理邏輯是計算機應用和理論研究的理論基礎。本章介紹介紹命題邏輯命題邏輯邏輯是研究思維的形式結構及其規(guī)律的科學邏輯是研究思維的形式結構及其規(guī)律的科學邏邏輯輯數(shù)理邏輯數(shù)理邏輯辨證邏輯辨證邏輯命題邏輯命題邏輯謂詞邏輯謂詞邏輯( (用數(shù)學方法用數(shù)學方法) )符號邏輯符號邏輯傳統(tǒng)邏輯傳統(tǒng)邏輯兩種邏輯的區(qū)別只是在于它們工具語言的不同。兩種邏輯的區(qū)別只是在于它們工具語言的不同。第1頁/共88頁3習題習題： 1作業(yè)9.1 9.1 命題和命題聯(lián)結詞命題和命題聯(lián)結詞自然語言中的句子，只有陳述句能分辨真假。自然語言中的句子，只有陳述句能分辨真假

2、。定義定義：把每個能分辨真假的陳述句稱為：把每個能分辨真假的陳述句稱為命題命題 ，命題的命題的 結果稱為結果稱為真值真值 。 如果一個命題是真的，則稱它的真值為如果一個命題是真的，則稱它的真值為真真， 用用“1 1”表示；如果一個命題是假的，則稱它的真表示；如果一個命題是假的，則稱它的真 值為值為假假，用用“0 0”表示表示第2頁/共88頁4習題習題： 1作業(yè)例例： 今天下雪今天下雪 光緒皇帝死的那一天，是大晴天光緒皇帝死的那一天，是大晴天 任何一個大于任何一個大于 2 2 的偶數(shù)都可以表示成兩個素數(shù)的偶數(shù)都可以表示成兩個素數(shù) 之和之和 上帝保佑！上帝保佑！規(guī)定規(guī)定：在數(shù)理邏輯中，命題用大寫字

3、母或帶下標的大：在數(shù)理邏輯中，命題用大寫字母或帶下標的大 寫字母表示。寫字母表示。 天藍藍，海藍藍天藍藍，海藍藍 x xy y5 5第3頁/共88頁5習題習題：原子命題原子命題：若一個命題已不能分解成更簡單的命題，若一個命題已不能分解成更簡單的命題， 則稱該命題為則稱該命題為原子命題原子命題 或或 原始命題原始命題命題聯(lián)結詞命題聯(lián)結詞：若干原子命題通過以下五種聯(lián)結詞可以若干原子命題通過以下五種聯(lián)結詞可以 構成新的命題，稱這五種聯(lián)結詞為構成新的命題，稱這五種聯(lián)結詞為命題聯(lián)結詞命題聯(lián)結詞復合命題復合命題：若干原子命題通過命題聯(lián)結詞構成的新的若干原子命題通過命題聯(lián)結詞構成的新的 命題稱為命題稱為復合

4、命題復合命題五種聯(lián)結詞是五種聯(lián)結詞是 “否定否定”、“合取合取 ”、“析取析取 ”、“蘊涵蘊涵”、“等值等值 ”第4頁/共88頁6習題習題： 否定否定 “ ”把對一個命題把對一個命題 P 的否定的命題稱為的否定的命題稱為否命題否命題，記為記為 “ P ”，讀成，讀成“非非 P ”。真值表：真值表：PP 0 1 1 0 “ ” 在自然語言中相當于在自然語言中相當于 “非非”、“不不”、“沒有沒有”、 “不成立不成立”等詞等詞例：例：P：“今天上午打雷了今天上午打雷了”，它的否定句可以是：，它的否定句可以是： P：今天上午沒有打雷；：今天上午沒有打雷； P：今天上午打雷這件事不成立：今天上午打雷這

5、件事不成立定義定義：當且僅當當且僅當 P 為假時，為假時， P 為真。為真。第5頁/共88頁7習題習題：注注：數(shù)理邏輯中的：數(shù)理邏輯中的“ ”，是對一個命題的嚴格否定。，是對一個命題的嚴格否定。 自然語言中的否定詞往往有較大的差別，使用自然語言中的否定詞往往有較大的差別，使用 時要注意。時要注意。 “ ”聯(lián)結詞在集合運算中相當于聯(lián)結詞在集合運算中相當于“補補”運算符運算符 “ ”例例如：如： P：這些都是男同學；：這些都是男同學； 則則 P 應是：應是：“這些不都是男同學這些不都是男同學”； 不能是：不能是：“這些都不是男同學這些都不是男同學”第6頁/共88頁8 合取合取 “ ”合取是關于兩個

6、命題的聯(lián)結詞，記為合取是關于兩個命題的聯(lián)結詞，記為“”。 合取合取“”在自然語言中相當于在自然語言中相當于“并且并且”、“和和”、“以及以及”、 “既既又又”、“不僅不僅而且而且”、 “雖然雖然但是但是”等等 真值表：真值表：P PQ 0 0 0 0 1 0 Q0 1 0 1 1 1 習題習題： 定義定義：當且僅當命題當且僅當命題 P 和和 Q 均為真時，均為真時， PQ 才為真才為真第7頁/共88頁9例例： P：張新成績很好，：張新成績很好，Q：張新性格很好。：張新性格很好。 PQ： PQ：李珊與劉菲到五樓去了。：李珊與劉菲到五樓去了。 P：桌子是黃色的，：桌子是黃色的，Q：火星上有生命。：

7、火星上有生命。 PQ：習題習題：張新不僅成績很好而且性格很好張新不僅成績很好而且性格很好 P： Q： 李珊到五樓去了李珊到五樓去了 劉菲到五樓去了。劉菲到五樓去了。 桌子是黃色的并且火星上有生命桌子是黃色的并且火星上有生命 李珊與劉菲是同鄉(xiāng)李珊與劉菲是同鄉(xiāng)第8頁/共88頁103. 析取析取 “ ”析取是關于兩個命題的聯(lián)結詞，記為析取是關于兩個命題的聯(lián)結詞，記為“”。 析取析取 “” 在自然語言中相當于在自然語言中相當于“或者或者” 真值表：真值表：P PQ 0 0 0 1 1 1 Q0 1 0 1 1 1 習題習題： 定義：當且僅當命題定義：當且僅當命題 P 和和 Q 至少有一個取值為真時，至

8、少有一個取值為真時， P Q 便取值為真。便取值為真。第9頁/共88頁11習題習題： 1例例： P：這餐飯吃魚，：這餐飯吃魚， Q：這餐飯吃白菜。：這餐飯吃白菜。 P Q： P Q：今晚我寫字或看書。：今晚我寫字或看書。 P： Q：這餐飯吃魚或吃白菜這餐飯吃魚或吃白菜今晚我寫字今晚我寫字 今晚我看書今晚我看書 張曜在圖書館或在宿舍里。張曜在圖書館或在宿舍里。 設設 P：張曜在圖書館：張曜在圖書館 Q：張曜在宿舍里。：張曜在宿舍里。則復合命題應為：則復合命題應為：(PQ)(PQ)第10頁/共88頁12注注：集合運算中的：集合運算中的“”是是“ ”的特例的特例 自然語言中的自然語言中的“或者或者”

9、的含義有兩種，一種是的含義有兩種，一種是 “可兼或可兼或”，一種是，一種是“不可兼或不可兼或”。 而數(shù)理邏輯中定義的析取而數(shù)理邏輯中定義的析取“”的含義是的含義是 “可兼或可兼或”的意思：命題的意思：命題 P 成立，或者命成立，或者命題題 Q成立，或者命題成立，或者命題 P 和和 Q 都成立。都成立。不能表示不能表示“不可兼或不可兼或”的意思的意思 “不可兼或不可兼或”在命題邏輯中表示在命題邏輯中表示成成 (PQ)(PQ)習題習題： 意為：意為：“要么要么要么要么”第11頁/共88頁13 蘊涵蘊涵 “ ” 蘊涵蘊涵 “”在自然語言中相當于在自然語言中相當于 “如果如果必須必須”、“如果如果那么

10、那么”、“必須必須以便以便”、“Q 對于對于 P 是必要的是必要的 ”、 “P 對于對于 Q 是充分的是充分的 ” PQ 定義定義 中的中的 P 稱為蘊涵式的稱為蘊涵式的前件前件，Q 稱為蘊涵式稱為蘊涵式的的后件后件 。習題習題：蘊涵的真值表：蘊涵的真值表：P PQ 0 0 1 1 1 0 Q0 1 0 1 1 1 第12頁/共88頁14例例： 如果你走路時看書，那么你一定會成為近視眼如果你走路時看書，那么你一定會成為近視眼 PQ： “如果我放了假，我就到桂林去”；習題習題：解：設：解：設：P：你走路；：你走路；Q：你看書；：你看書； R：你會成為近視眼：你會成為近視眼 則復合命題為：則復合命

11、題為：(PQ)R解：解：P：我放了假，：我放了假， Q：我到桂林去：我到桂林去第13頁/共88頁15注注： 蘊涵的真假值表的特點是，只有當后件為蘊涵的真假值表的特點是，只有當后件為“假假”， 前件為前件為“真真”時，蘊涵式的值才為時，蘊涵式的值才為“假假”，其他，其他情況情況 蘊涵式的值均為蘊涵式的值均為“真真” 蘊涵實質上就是通常的“必要條件”的一種抽象討論討論：蘊涵的真假值表中不大好理解的是，當后件為：蘊涵的真假值表中不大好理解的是，當后件為 “真真”時，無論前件為真為假，時，無論前件為真為假， 蘊涵式的值都為蘊涵式的值都為“真真” 其實，這樣的定義方式也反映了客觀實際，它其實，這樣的定義

12、方式也反映了客觀實際，它并并不違背我們的邏輯思維常識。不違背我們的邏輯思維常識。看看前面的看看前面的例例習題習題：第14頁/共88頁16等值等值 “” 等值等值“”在自然語言中相當于在自然語言中相當于“當且僅當當且僅當”、“相當于相當于”、“和和一樣一樣”、“等價于等價于 ”、 “P 是是 Q 的充要條件的充要條件 ”習題習題：P PQ 0 0 1 0 1 0 Q0 1 0 1 1 1 等值的真值表：等值的真值表：第15頁/共88頁17例例： 除非他以書面或口頭的方式正式通知我，否則除非他以書面或口頭的方式正式通知我，否則 我不參加明天的會議。我不參加明天的會議。 PQ： “僅當你去我將留下僅

13、當你去我將留下”； P： Q：習題習題：解解：設：設 P：他書面通知我；：他書面通知我；Q：他口頭通知我；：他口頭通知我； R：我參加明天的會議：我參加明天的會議則復合命題表示為：則復合命題表示為： (PQ)R我留下我留下 你去你去第16頁/共88頁18如何把一個句子符號化如何把一個句子符號化步驟步驟：分析出句子中的原子命題，將它符號化；：分析出句子中的原子命題，將它符號化； 使用合適的聯(lián)結詞把原子命題聯(lián)結起來，組成使用合適的聯(lián)結詞把原子命題聯(lián)結起來，組成 復合命題的符號化表示。復合命題的符號化表示。注意注意：自然語言中的聯(lián)結詞與命題聯(lián)結詞的含義不是：自然語言中的聯(lián)結詞與命題聯(lián)結詞的含義不是

14、完全對應的，需要具體分析。完全對應的，需要具體分析。習題習題：1、2、3第17頁/共88頁19例例： 小李雖聰明，但不用功小李雖聰明，但不用功解解：令：令 P：小李聰明，：小李聰明， Q：小李用功：小李用功 若不是他生病或出差了，我是不會同意他不若不是他生病或出差了，我是不會同意他不 參加學習。參加學習。解解:令令 P：他生病了，：他生病了， Q：他出差了，：他出差了， R：我同意他不參加學習：我同意他不參加學習習題習題：1、2、3命題表示為：命題表示為：PQ命題表示為：命題表示為：(PQ)R 或者或者 (PQ)R第18頁/共88頁20 小張現(xiàn)在在圖書館或在宿舍里小張現(xiàn)在在圖書館或在宿舍里解解

15、：令：令 P：小張在圖書館，：小張在圖書館， Q：小張在宿：小張在宿舍舍 命題表示為：命題表示為：習題習題： 他寫了他寫了 30 行或行或 50 行行字字解解：這里的：這里的“或或”可以有兩種不同的理解：可以有兩種不同的理解： (PQ)(PQ)一是，一是，“不可兼得的或不可兼得的或”，如上題寫成一復合命題；，如上題寫成一復合命題；二是，可作二是，可作“或許或許”，“大概大概”理解，就是一個原子理解，就是一個原子命題。命題。第19頁/共88頁21習題習題：1、2、3 趙常與錢深是好學生趙常與錢深是好學生解解：令：令 P：趙常是好學生，：趙常是好學生， Q：錢深是好學：錢深是好學生生 趙常與錢深是

16、好朋友趙常與錢深是好朋友解解：這是一個原子命題。：這是一個原子命題。命題表示為：命題表示為： PQ第20頁/共88頁22判斷下列語句哪些是命題判斷下列語句哪些是命題 我正在說謊。我正在說謊。 3x 3x5858 圓的面積等于半徑的立方乘以圓的面積等于半徑的立方乘以 。 2 2 或是質數(shù)或是合數(shù)?；蚴琴|數(shù)或是合數(shù)。 你學過了法語，真好！你學過了法語，真好！ 公元前公元前 194 194 年發(fā)生過十天日食。年發(fā)生過十天日食。 如果你下午不開會就到我這里來，好嗎？如果你下午不開會就到我這里來，好嗎？第21頁/共88頁23命題符號化練習命題符號化練習 2 23 35 5 當且僅當當且僅當 是無理數(shù)是無

17、理數(shù)2 如果你來了，那么他唱不唱歌將看你是否伴奏而定如果你來了，那么他唱不唱歌將看你是否伴奏而定 生命不息戰(zhàn)斗不止生命不息戰(zhàn)斗不止 張穎是張穎是 18 18 歲，或是歲，或是 19 19 歲歲 李珊學過德語或法語李珊學過德語或法語 趙玲與陳實在討論問題趙玲與陳實在討論問題 莫伸手，伸手必被捉。莫伸手，伸手必被捉。 小代和小李是倆夫妻，他們都很貪婪小代和小李是倆夫妻，他們都很貪婪第22頁/共88頁249.2 命題公式命題公式命題常元命題常元：若一個表示命題的符號具有確定的真值若一個表示命題的符號具有確定的真值 (1 或或 0)，則稱它為，則稱它為命題常元命題常元習題習題：4命題變元命題變元：一個

18、任意的，真值不確定的命題我們稱一個任意的，真值不確定的命題我們稱 它為它為命題變元命題變元 ，仍用大寫字母表示，仍用大寫字母表示一、一、幾個概念幾個概念第23頁/共88頁25 0、1是命題公是命題公式式習題習題：4定義定義 9-6 ：關于：關于命題公式命題公式(或簡稱或簡稱公式公式)的定義的定義 命題變元是命題公式命題變元是命題公式 如果如果 A 是命題公式，則是命題公式，則 P 是命題公是命題公式式 如果如果 A 和和 B 是命題公式，則是命題公式，則(AB)、(AB)、 (AB)、(AB) 也是命題公式也是命題公式 只有有限次地利用上述只有有限次地利用上述 、 產生的產生的 符號串才是命題

19、公式符號串才是命題公式第24頁/共88頁26例例：看看下面的符號串哪些是公式：看看下面的符號串哪些是公式：(AB)(PQ) )習題習題：4作業(yè)(AB)P Q注注：命題公式不一定是命題，若公式中有命題變元時：命題公式不一定是命題，若公式中有命題變元時， 只有每一個命題變元都被賦以確定的真值時，公只有每一個命題變元都被賦以確定的真值時，公 式的真值才被確定，成為一個命題式的真值才被確定，成為一個命題( (AB)R) (PQ)BQ 10P QP第25頁/共88頁27真值指派真值指派：為一個公式的所有變元取一組確定的真值，為一個公式的所有變元取一組確定的真值， 稱為該公式關于各變元的一組稱為該公式關于

20、各變元的一組真值指派真值指派習題習題：4作業(yè)例例： (PQ)(QS) 公式的各組真值指派就是其中公式的各組真值指派就是其中3個變元在真值表最個變元在真值表最左邊列出的左邊列出的8組值組值第26頁/共88頁28重言式重言式：若一個公式對于它的所有命題變元的任何一若一個公式對于它的所有命題變元的任何一 組真值指派，取值恒為真，則稱該公式為組真值指派，取值恒為真，則稱該公式為重言式重言式 或或永真公式永真公式，常用常用 “1” 表示表示習題習題：5、6作業(yè)二、公式的類型二、公式的類型例例：命題公式：命題公式 F1(PQ) ( PQ) 的真值表如下：的真值表如下：P0 0 1 Q0 1 0 1 1 P

21、Q 1 1 0 1 P1 1 0 0 PQ1 1 0 1 (PQ)(PQ) 1 1 1 1 第27頁/共88頁29習題習題：5、6作業(yè)矛盾式矛盾式：若一個公式對于它的所有命題變元的任何一：若一個公式對于它的所有命題變元的任何一 組真值指派，取值恒為假，則稱該公式為組真值指派，取值恒為假，則稱該公式為矛盾式矛盾式 或或永假公式永假公式，常用常用 “0” 表示表示可滿足公式可滿足公式：若一個公式至少有一組真值指派使公式若一個公式至少有一組真值指派使公式 的值為真，則稱該公式為的值為真，則稱該公式為可滿足公式可滿足公式例例： (PQ)(QS) P0 0 0 Q0 0 1 0 1 PQ QQS (PQ

22、)(QS)S0 1 0 1 1 0 1 1 0 0 1 0 1 1 1 1 1 1 0 1 1 0 0 0 0 1 1 1 0 1 0 1 0 1 0 1 1 0 1 1 0 1 0 0 0 1 0 1 第28頁/共88頁309.3 命題公式的等值關系和蘊涵關系命題公式的等值關系和蘊涵關系 就像代數(shù)式之間有等式和不等式一樣，命題公式就像代數(shù)式之間有等式和不等式一樣，命題公式之間也常有一些關系，最基本的關系是等值關系和蘊之間也常有一些關系，最基本的關系是等值關系和蘊涵關系涵關系習題習題：4作業(yè) 等值關系實質上是表示兩個公式之間的一種關等值關系實質上是表示兩個公式之間的一種關 系，系， “ ” 是

23、一個表示關系的符號。是一個表示關系的符號。公式等值公式等值：設設 A和和B是兩個命題公式，當且僅當是兩個命題公式，當且僅當A和和B 的真值表完全相同時，稱的真值表完全相同時，稱 A 和和 B 是是等值公式等值公式 記為記為 A B 注注： 公式等值的另一種定義是：公式等值的另一種定義是： 若若 AB 為重言式，則稱為重言式，則稱 A和和B是是等值公式等值公式第29頁/共88頁31基本等值關系：下面列出基本等值關系：下面列出 26 個重要的等值關系，它們可以像集個重要的等值關系，它們可以像集 合恒等式一樣用于推導其它等值關系合恒等式一樣用于推導其它等值關系E1：PQ QP E1： PQ QP E

24、2：(PQ)R P(QR) E2：(PQ)R P(QR)E3： P(QR)(PQ)(PR)E3：P(QR )(PQ)(PR ) E4：P1 P E1：P0 PE5：P P 1 E5：PP 0 E6 、E6：(P) P E8：P 0 0 E8：P 1 1 交換交換律律 結合結合律律 分配分配律律 同一同一律律 零一零一律律 互否互否律律 雙重否定雙重否定律律 E7：P P P E7：P P P 等冪等冪律律 E9：P(PQ) P E9：P(PQ) P吸收吸收律律 E10：(PQ) PQE10：(PQ) PQ德摩根定律德摩根定律習題習題：第30頁/共88頁32 E11： P Q P Q E12：

25、P Q (P Q)( P Q) E13： P (Q R)(P Q) R E14： P Q (P Q)(Q P) E16： P Q Q P E17： (P Q) P Q E15： (P Q) P Q第31頁/共88頁33說明說明： 這這 26 個等值關系中，前個等值關系中，前 19 個與集合恒等式的基本公式個與集合恒等式的基本公式 (參見書參見書 p16)非常相似非常相似 這里的這里的 “” 相當于集合運算符相當于集合運算符 “” 這里的這里的 “” 相當于集合運算符相當于集合運算符 “” 這里的這里的 “ ” 相當于集合運算符相當于集合運算符 “ ” 這這 26 個等值關系中，后個等值關系中，

26、后 7 個關系表明，所有命題公式個關系表明，所有命題公式 都能用都能用 “”、 “”、“ ” 表示表示 這這 26 個等值關系的證明都可以用真值表進行，個等值關系的證明都可以用真值表進行， 這是最基本的證明方法。這是最基本的證明方法。習題習題：第32頁/共88頁34解解：列真值表：列真值表PP Q 0 0 1 1 1 0 Q0 1 0 1 1 1 PP Q 0 0 1 1 1 0 Q0 1 0 1 1 1 P1 1 0 0 習題習題：例例 1：證明等值關系：證明等值關系： P Q P Q 從真值表可看出從真值表可看出 P Q P Q 成立成立 第33頁/共88頁35解解：列真值表：列真值表PP

27、 Q 0 0 1 0 1 0 Q0 1 0 1 1 1 P P Q 0 0 0 0 1 0 Q0 1 0 1 1 1 P1 1 0 0 Q1 0 1 0 P Q 1 0 0 0 (P Q)(P Q)1 0 0 1 習題習題：例例 2：證明等值關系：證明等值關系： P Q (P Q)( P Q) 從真值表可看出從真值表可看出 P Q (P Q)(P Q)第34頁/共88頁36 在代數(shù)中對公式進行推導時，可以使用變量代換在代數(shù)中對公式進行推導時，可以使用變量代換和公式代換。在這里，等值關系的推導中也有同樣的和公式代換。在這里，等值關系的推導中也有同樣的代換規(guī)則。代換規(guī)則。代換實例代換實例：設設 A

28、 是一個命題公式，是一個命題公式，P1，P2，Pn 是是 其中出現(xiàn)的所有命題變元。其中出現(xiàn)的所有命題變元。 用某些表達式代換 A 中的某些命題變元； 若用表達式 Qi 代換 Pi 則必須用 Qi 代換 A 中所有的 Pi 。 那么，由此得到的新命題公式那么，由此得到的新命題公式 B 叫做表達式叫做表達式 A 的一個的一個代換實例代換實例習題習題：5作業(yè)第35頁/共88頁37例例 1：對于表達式：對于表達式 A=P(RP)中，用中，用 QS 代換其中的代換其中的 P， 得到表達式得到表達式 B =(QS)(R (QS) 則表達式則表達式 B 就是就是 A 的一個代換實例的一個代換實例注注：用表達

29、式：用表達式 QS 代換表達式代換表達式 A 中的中的 P 時，必須把時，必須把 A 中的所有中的所有 P 都代換掉，不能漏掉一個。都代換掉，不能漏掉一個。例例 2：對于表達式：對于表達式 A = PQ ，先用，先用 QS 代換其中的代換其中的 P，得到表，得到表 達式達式 B1 =(QS)Q ；再用；再用 R 代換其中的代換其中的 Q，得到表達式，得到表達式 B2 =(RS) R ，則，則 B2 就不是就不是 A 的代換實例的代換實例注注：若用多個表達式對多個變元進行代換，則代換必須同時進行：若用多個表達式對多個變元進行代換，則代換必須同時進行習題習題：5作業(yè)第36頁/共88頁38定理定理

30、9-2： (代入規(guī)則代入規(guī)則) 重言式的任一代換實例仍然是重言重言式的任一代換實例仍然是重言式式解釋解釋：這個定理的意義在于，前面的：這個定理的意義在于，前面的 26 個等值關系中的變元個等值關系中的變元 P、Q、R 不僅可以是任何命題變元，而且它們被換成命不僅可以是任何命題變元，而且它們被換成命 題公式時，這些等值關系也是成立的。題公式時，這些等值關系也是成立的。 這相當于代數(shù)式中的任何一個變量可以全部換成另一個這相當于代數(shù)式中的任何一個變量可以全部換成另一個 變量，也可換成另一個表達式變量，也可換成另一個表達式習題習題：7作業(yè)例例：分配：分配律律 E3：P(QR)(PQ )(PR ) 用表

31、達式用表達式 XY 代換其中的變量代換其中的變量 Q 得：得： P(XY )R )(P(XY )(P R ) 例第37頁/共88頁39(PQ )、RP 、Q(RP) 都是都是 A 的子表達式的子表達式子公式子公式：如果如果 C 是表達式是表達式 A 的一個符號子串，而的一個符號子串，而 C 本身也本身也 是一個表達式，則稱是一個表達式，則稱 C 為為 A 的的子公式子公式(子表達式子表達式)例例 1：表達式：表達式 A =(PQ )(Q(RP )中，中，(PQ)、(RP)、Q 都不是都不是 A 的子表達式的子表達式習題習題：7作業(yè) 例第38頁/共88頁40定理定理 9-3： (置換規(guī)則置換規(guī)則

32、 ) 表達式表達式 A 的任何一個子表達式的任何一個子表達式 C ，可以用，可以用 C 的等值表達式的等值表達式 D 置換，所得的新的表達式仍與原表達式置換，所得的新的表達式仍與原表達式 A 等值等值解釋解釋： 定理定理9-3 就像代數(shù)中的表達式一樣，可以把其中的任何一個子就像代數(shù)中的表達式一樣，可以把其中的任何一個子 表達式換成另一個與它等值的表達式，保持原表達式值不變。表達式換成另一個與它等值的表達式，保持原表達式值不變。 在命題公式中，也可把其中的任何一個子表達式換成另一個在命題公式中，也可把其中的任何一個子表達式換成另一個 等值的表達式。等值的表達式。 有了代入規(guī)則和置換規(guī)則，我們就可

33、以像代數(shù)中的恒等變換有了代入規(guī)則和置換規(guī)則，我們就可以像代數(shù)中的恒等變換 一樣，利用已知的等值關系式推導出其它一些更復雜的等值一樣，利用已知的等值關系式推導出其它一些更復雜的等值 關系式。關系式。習題習題：7作業(yè)第39頁/共88頁41習題習題：7作業(yè) 原等值原等值關系關系式成立式成立例例 1 證明：證明： (P(Q S )(P(Q S ) Q S 證證： (P(QS )(P(QS ) (PP)(QS) (分配律分配律) 1(QS ) (互否律互否律) QS (零一律零一律)第40頁/共88頁42習題習題：7作業(yè)證證：一般，把：一般，把“蘊涵蘊涵”轉換為轉換為“非非”、“且且”、“或或” 原等值

34、原等值關系式關系式成立成立(公式公式 E11)例例 3 證明：證明：P (Q R)(PQ)R左邊為 P(QR ) P(QR ) P(QR ) PQR(PQ )R (PQ )R (摩根定律摩根定律)(PQ )R第41頁/共88頁43習題習題：7作業(yè) 原等值原等值關系關系式成立式成立例例 4 證明：證明：PQ (PQ)(QP)證證： 右邊為右邊為 (PQ)(QP)(PQ)(QP) (P(QP)(Q(QP)(PQ)(PP)(QQ)(QP)(PQ)(QP)左邊為左邊為 PQ (PQ)(QP)第42頁/共88頁44習題習題：7作業(yè)例例 5 證明：證明：Q(PQ )P )是一個重言式是一個重言式 原式是一

35、個重言式原式是一個重言式證證： Q(PQ )P ) Q(PP )(QP ) Q(0(QP ) Q(QP ) QQP 1第43頁/共88頁45 集合中的被包含關系與這里的蘊涵關系完全相似，可以對集合中的被包含關系與這里的蘊涵關系完全相似，可以對 照著理解和記憶照著理解和記憶 “ ”是命題聯(lián)結詞，是命題聯(lián)結詞， AB 是一個公式，表示一個命題是一個公式，表示一個命題 蘊涵關系是一個偏序關系，滿足自反性、反對稱性、可蘊涵關系是一個偏序關系，滿足自反性、反對稱性、可 傳遞性傳遞性(為以下定理為以下定理4、定理、定理5支持支持)：習題習題：公式蘊涵公式蘊涵 ：設設 A 和和 B 是兩個命題公式，若表達式

36、是兩個命題公式，若表達式 AB 是重言式，是重言式， 即即 ( AB ) 1，則稱公式，則稱公式 A 蘊涵蘊涵 B ，記為記為 AB注注： 注意注意“ ”和和“ ”是兩個完全不同的符號。是兩個完全不同的符號。 “ ”不是聯(lián)結詞，而只是一個表示關系的符號，不是聯(lián)結詞，而只是一個表示關系的符號， AB 不是公式，不代不是公式，不代 表任何命題表任何命題對任意公式對任意公式 A ，有，有 AA對任意公式對任意公式 A、B ，若，若 AB ，BA ，則必有，則必有 A B 對任意公式對任意公式 A、B、C ，若，若 AB ，BC ，則，則 AC第44頁/共88頁46反之亦然反之亦然習題習題：定理定理

37、9-4：設設 A 、 B 為兩個命題公式，為兩個命題公式，AB 的的 充要條件是，充要條件是， AB 且且 BA 證證：設：設 AB ，則，則 AB 是重言式，即是重言式，即 AB 1而而 A B (AB)(BA )(AB) (BA) 1，則，則 AB 1 且且 BA 1 按蘊涵關系的定義，有按蘊涵關系的定義，有 AB 且且 BA第45頁/共88頁47習題習題：定理定理 9-5：設：設 A、B、C 是公式，是公式，若若 AB ，BC ， 則則 AC證證：由：由 AB 和和BC 得得 AB 和和 BC 都是重言式都是重言式而 AB AB，BC BC AB 1，BC 1 AC (AC)0(AC)(

38、BB)(ACB)(ACB)即 AC 1 AC成立(A1)(1C)111第46頁/共88頁48蘊涵關系：下面列出幾蘊涵關系：下面列出幾 個重要的蘊涵關系，它們可以個重要的蘊涵關系，它們可以 按照定義直接證明按照定義直接證明習題習題：PQ P PQ Q P PQ Q PQP PQ Q PQ第47頁/共88頁49證明蘊涵關系的方法證明蘊涵關系的方法根據(jù)蘊涵關系的定義證。把蘊涵關系相應的蘊涵式根據(jù)蘊涵關系的定義證。把蘊涵關系相應的蘊涵式 PQ的等值式的等值式 PQ 變換成變換成 1 即可。即可。 列出蘊涵關系左右公式的真值表，用真值表比較列出蘊涵關系左右公式的真值表，用真值表比較習題習題：根據(jù)蘊涵聯(lián)結

39、詞的定義證。蘊涵關系相應的蘊涵式根據(jù)蘊涵聯(lián)結詞的定義證。蘊涵關系相應的蘊涵式 PQ的前件的前件 P 為真時，證明后件為真時，證明后件 Q 必為真，則必為真，則 PQ 1，于是就有了，于是就有了 PQ ，否則該蘊涵關系不成立，否則該蘊涵關系不成立 根據(jù)蘊涵聯(lián)結詞的定義證。蘊涵關系相應的蘊涵式根據(jù)蘊涵聯(lián)結詞的定義證。蘊涵關系相應的蘊涵式 PQ的后件的后件 Q 為假時，證明前件為假時，證明前件 P 必為假，則必為假，則 PQ 1，于是就有了，于是就有了 PQ，否則該蘊涵關系不，否則該蘊涵關系不 成立成立第48頁/共88頁50 原蘊涵關系成立習題習題：例 1 證明： (PQ)(QR) PR證： 設 X

40、 (PQ)(QR)(PR) (取蘊涵關系的蘊涵式) (PQ)(QR)(PR) X (PQ)(QR)(PR) (取蘊涵式的等值式)(PQ)(QR)PR (德摩根定律)(PQ)P(QR)R (交換律) QPQR(QQ)PR 1PR (互否律)1第49頁/共88頁51 則必有 P 為真，且 (PQ )為真 (根據(jù)合取的真值表) 原蘊涵關系成立 (蘊涵關系的定義) 由 P 為真，得 P 為假，證 ： 假設前件 P(P Q )為真， 由 P 為假，再由 PQ 為真，得后件 Q 必為真 (析取的真值表) ( P( PQ ) ) Q 是個重言式 (蘊涵的真值表)習題習題：例 2 證明： P(PQ) Q 第5

41、0頁/共88頁52若 P 為真，則 P 為假，則 P (PQ)為假 (合取的真值表)前件 P (P Q)必然為假若 P 為假，由 Q 為假，則得 PQ 為假，仍有 P(PQ)為假 原蘊涵關系成立 (蘊涵關系的定義)證 ： 假設后件 Q 為假， (P (P Q) Q 是個重言式 (蘊涵的真值表)例 2 證明： P (P Q) Q習題習題：第51頁/共88頁53 原蘊涵關系成立 (蘊涵關系的定義)習題習題：例 3 證明： Q (P Q ) P 證 ：設 X (Q (P Q ) P (取蘊涵關系的蘊涵式) X (Q (P Q ) P (取蘊涵式的等值式) (Q P )(Q Q )P (分配律) (Q

42、 P ) 0 )P (互否律) (Q P )P (同一律) 1 QPP Q1 (德摩根定律)第52頁/共88頁54證 ：假設前件 Q (P Q)為真， 則必有 Q 為真，且(P Q )為真 (根據(jù)合取的真值表) 原蘊涵關系成立 (蘊涵關系的定義) 由 Q 為真，得 Q 為假由 Q 為假，再由 P Q 為真，又得 P 必為假 (根據(jù)蘊涵的真值表) 后件 P 必為真 (Q (P Q ) P 是個重言式 (根據(jù)蘊涵的真值表)習題習題：例 3 證明： Q (P Q) P 第53頁/共88頁55 若 Q 為假，則 Q (P Q ) 為假 (根據(jù)合取的真值表) 前件 Q (P Q) 總是為假 若 Q 為真

43、，則 Q 為假 原蘊涵關系成立 (蘊涵關系的定義)證 ：假設后件 P 為假，則 P 為真 由 Q 為假，加上 P 為真，則得 P Q 為假 (根據(jù)蘊涵的真值表) (Q(P Q ) P 是個重言式 (根據(jù)蘊涵的真值表) 仍有 Q (P Q )為假習題習題：第54頁/共88頁56習題習題：例 4 設 A、B、C 是公式，若 A B 且 A C ，證明：A (B C ) A (B C)成立 (蘊涵關系的定義)證 ：設 X A (B C) (取蘊涵關系的蘊涵式) X A(B C) (取蘊涵式的等值式) (AB)(AC) (A B)(A C) (蘊涵的定義) 代入 (A B)(A C) 得 1 A (B

44、 C) 1 由 A B 且 A C 得 A B 1 且 A C 1 第55頁/共88頁57 B 是重言式習題習題：例 5 設 A、B 是公式，若 A B 且 A 是重言式，則 B 一定也是重言式 證 ： A B 1 A B (蘊涵關系的定義) AB A 是重言式 A 0 上式為： 1 0 B B第56頁/共88頁58對偶對偶：在公式在公式 A 中，若把所有聯(lián)結詞中，若把所有聯(lián)結詞 代換成代換成 ，把，把 代換代換 成成 ，把，把 0 代換成代換成 1，把，把1 代換成代換成 0 ，則所得的公式稱為，則所得的公式稱為 A 的的對偶對偶 ，記作，記作 AD 公式中的所有聯(lián)結詞公式中的所有聯(lián)結詞 和

45、和 都可以置換成都可以置換成 、，所以，所以，在公式推導中總是把公式變成只包含在公式推導中總是把公式變成只包含 、 這三種聯(lián)結詞的這三種聯(lián)結詞的形式。形式。 定理定理 8：設設 A 、 AD 是兩個互為對偶的公式，是兩個互為對偶的公式，P1，P2，Pn 是是 其命題變元，則其命題變元，則習題習題： A(P1，P2，Pn) AD (P1，P2，Pn)第57頁/共88頁59習題習題： 定理定理 9(對偶原理對偶原理)： 設設 A(P1，P2，Pn)和和 B(P1，P2，Pn)是兩個是兩個 公式，若公式，若 A B ，則，則 AD BD 第58頁/共88頁609.5 命題演算的推理理論命題演算的推理

46、理論 邏輯推理就是由已知命題得到新命題的思維過程邏輯推理就是由已知命題得到新命題的思維過程推理前提(命題)結論(命題)一般地，前提可以是若干個命題的“且”習題習題：定義定義 ：設 A、B 是兩個命題公式，若 A B(即 A B 是重言式)， 則稱 B 是前提前提 A 的結論結論，或 從從 A 推出結論推出結論 B。 設 H1，H2，Hn 和 C 是一些命題公式， 若 H1H2Hn C 則稱 從前提從前提 H1，H2，Hn 推出結論推出結論 C ， 也可記為 H1，H2，Hn C 并稱 H1，H2，Hn為 C 的前提集合前提集合注：從一組前提是否可以推出某個結論的實質就是證明下述 蘊涵關系是否成

47、立 H1H2Hn C第59頁/共88頁61分析分析：前面已經(jīng)講了證明蘊涵關系處理的四種方法：前面已經(jīng)講了證明蘊涵關系處理的四種方法： 列出蘊涵關系的蘊涵式，通過等值變換把該蘊涵列出蘊涵關系的蘊涵式，通過等值變換把該蘊涵 式變換成式變換成 1 即可。即可。 設蘊涵式的前件為真，證明后件必為真設蘊涵式的前件為真，證明后件必為真 設蘊涵式的后件為假，證明前件必為假設蘊涵式的后件為假，證明前件必為假 列出蘊涵關系左右公式的真值表，用真值表比較列出蘊涵關系左右公式的真值表，用真值表比較這四種方法都可以用于證明前提由多個命題變元這四種方法都可以用于證明前提由多個命題變元組成的蘊涵關系。組成的蘊涵關系。習題

48、習題：第60頁/共88頁62習題習題： 第第 3 種方法在前提由多個命題變元組成時，要設種方法在前提由多個命題變元組成時，要設所有前提為真，由此推出結論為真，即可。這就是一所有前提為真，由此推出結論為真，即可。這就是一般的般的“直接證明法直接證明法”。 顯然，前兩種方法受蘊涵關系的規(guī)模的限制，在顯然，前兩種方法受蘊涵關系的規(guī)模的限制，在前提和結論都是比較復雜的命題公式或者包含的命題前提和結論都是比較復雜的命題公式或者包含的命題變元很多時，這兩種方法就很困難了。變元很多時，這兩種方法就很困難了。 第第 4 種方法在前提由多個命題變元組成時，要設種方法在前提由多個命題變元組成時，要設結論為假，由此

49、推出前提中有一個為假，即可。這就結論為假，由此推出前提中有一個為假，即可。這就是我們很熟悉的是我們很熟悉的“反證法反證法”，也叫也叫“間接證明法間接證明法”。第61頁/共88頁63形式證明形式證明：一個描述推理過程的命題序列，其中每個命題或者是一個描述推理過程的命題序列，其中每個命題或者是 已知命題，或者是由某些前提推得的結論，序列中最后一個已知命題，或者是由某些前提推得的結論，序列中最后一個 命題就是所要求的結論，這樣的命題序列稱為命題就是所要求的結論，這樣的命題序列稱為形式證明形式證明。推理規(guī)則推理規(guī)則： 前提引入規(guī)則前提引入規(guī)則：在證明的任何步驟上都可以引入前提在證明的任何步驟上都可以引

50、入前提 結論引用規(guī)則結論引用規(guī)則：在證明的任何步驟上所得到的結論都可在證明的任何步驟上所得到的結論都可 以在其后的證明中引用以在其后的證明中引用 置換規(guī)則置換規(guī)則：在證明的任何步驟，命題公式的子公式都可在證明的任何步驟，命題公式的子公式都可 以用與它等值的其它命題公式置換以用與它等值的其它命題公式置換 代入規(guī)則代入規(guī)則：在證明的任何步驟，重言式的任一命題變元在證明的任何步驟，重言式的任一命題變元 都可用一命題公式代入，得到的仍是重言式。都可用一命題公式代入，得到的仍是重言式。習題習題：構造一個邏輯結構嚴謹?shù)男问阶C明，需要以下推理規(guī)則的支持構造一個邏輯結構嚴謹?shù)男问阶C明，需要以下推理規(guī)則的支持第

51、62頁/共88頁64例例 1：有前提：有前提 H1，H2，和結論，和結論 C ，判斷推理能否成立：，判斷推理能否成立： H1 ：P Q ， H2 ： P ， C ： Q H1 ：P Q ， H2 ： Q ， C ： P 列真值表如下：列真值表如下：P(PQ)P0 0 0 0 1 0 Q0 1 0 1 1 1 P1 1 0 1 Q(P Q )Q0 1 0 1 習題習題：(P Q )P) Q1 1 1 1 ( (PQ )Q )P1 0 1 1 第63頁/共88頁65例 1：有前提 H1，H2，和結論 C ，判斷推理能否成立： H1 ：P Q ， H2 ： P ， C ： Q H1 ：P Q ， H

52、2 ： Q ， C ： P 顯然，第 小題中，從 H1，H2 能夠推出 C ； 第 小題中，不能從 H1，H2 推出 C 把具體命題代入上例中的命題變元 P，Q，則更容易理解 P Q ：如果今天出太陽，他就進城 P ：今天出了太陽Q ：他進城了 P Q ：如果狗有翅膀，則狗會飛上天 P ：狗有了翅膀Q ：狗飛上了天 P Q ：如果 n 是素數(shù)，則 n 一定是整數(shù)Q ：n 是整數(shù)P ： n 是素數(shù)習題習題：第64頁/共88頁66例 2：證明 C ：P 是前提 H1 ：P Q 和 H2 ：(P Q )的結論 C 是前提 H1 和 H2 的結論習題習題： ( ( P Q ) ( P Q ) ) P

53、( ( PQ )( PQ ) ) P ( P ( Q Q ) ) P (P 0) P P P P P 1證 (H1 H2 ) C ( ( P Q ) (P Q ) ) P第65頁/共88頁67 用直接證明法用直接證明法 ，我們設每一個前提的真值為真，我們設每一個前提的真值為真 ，能推導出，能推導出結論的真值也為真，則原推理正確，否則不正確。結論的真值也為真，則原推理正確，否則不正確。例 3：證明 P 是前提 (P Q )，QR ，R 的結論 P 是前提 (PQ )，QR ，R 的結論習題習題：證 設 R為真 (前提3為真) 得 R 為假 將 R為假代入得：Q為真 繼得 Q 為假 設 (PQ )

54、為真 (前提1為真) 得 PQ 為真 將 Q 為假代入得： P為真 (結論為真)設 QR 為真 (前提2為真)第66頁/共88頁68例 4：證明 (PQ)R，RS ，S P Q討論：這一題用反證法如何?習題習題：證：設 S 為真 (前提3為真)得 S 為假 設 RS為真 (前提2為真)將 S為假代入得：R為真 繼得R為假設 (PQ ) R為真 (前提1為真)將 R 為假代入得：PQ為假 P Q 為真 即 P Q為真 (結論為真) (PQ) R ，RS ，S P Q 成立第67頁/共88頁69例例：證明：證明 (PQ)R，RS ，S PQ習題習題：此題的結論是一個蘊含式，這種情況下可以將該蘊含式

55、的前件此題的結論是一個蘊含式，這種情況下可以將該蘊含式的前件也作為題目的前提，稱之為也作為題目的前提，稱之為“附加前提附加前提”；該蘊含式的后件作為題目的結論，使原題成為下面等價的形式：該蘊含式的后件作為題目的結論，使原題成為下面等價的形式：證明證明 (PQ)R，RS，S，P Q 第68頁/共88頁70例例 5：證明：證明 PQ 是是 S Q，R P ，SR 的結論的結論 PQ 是 S Q ， R P ， SR 的結論習題習題：證 設 PQ為假 (設結論為假) 則有： P 為假 且 Q 為假 若 S Q為真 (前提 1為真) 即： SQ 為真 代入 Q 為假 得 S 為真 S 為假 再設 R

56、P 為真 (前提 2為真) 把 P 為假 代入 得 R 為假 于是 S R 為假 (得前提 3 為假)討論討論：此題用：此題用”直接證明直接證明”好，還是用好，還是用”反證法反證法”好好?第69頁/共88頁71在上述例子中，無論是直接證明還是反證法，都用到了各種推理規(guī)則，例如，全體引入規(guī)則，置換規(guī)則，代入規(guī)則等。而直接使用已知的蘊涵關系式卻沒有。在上述例子中，無論是直接證明還是反證法，都用到了各種推理規(guī)則，例如，全體引入規(guī)則，置換規(guī)則，代入規(guī)則等。而直接使用已知的蘊涵關系式卻沒有。習題習題：下面列出一些常用的蘊涵關系式下面列出一些常用的蘊涵關系式(推理定理推理定理)：I3： P PQ I4：

57、Q PQI5： P PQ I6： Q PQI7： (PQ ) P I8： (PQ ) QI9： P，Q PQ I10： P，PQ QI11： P，PQ Q I12： Q，PQ P I13： PQ，QR PR I14：PQ ，PR，QR R I15： PQ (PR) (QR ) I16：PQ (PR) (QR ) I1： PQ P I2： PQ Q第70頁/共88頁72習題習題：如果證明過程的每一步所得到的結論都是根據(jù)推理規(guī)則得到的，如果證明過程的每一步所得到的結論都是根據(jù)推理規(guī)則得到的，則稱這樣的證明為則稱這樣的證明為“有效的有效的”，或曰，或曰“合理的合理的”下面舉例介紹利用推理定理進行推理

58、的一種方法下面舉例介紹利用推理定理進行推理的一種方法推理表推理表通過有效的證明得到的結論，我們稱為是通過有效的證明得到的結論，我們稱為是“有效的結論有效的結論”或或“合理的結論合理的結論”第71頁/共88頁73例 7：證明 PQ ，RQ ，RS P 習題習題：證明：RS前提 3RQ前提 2P Q前提 1編號公式依據(jù) P,I12I12：Q，PQP R,I1I1：PQ P Q,I10I10： P，PQ Q第72頁/共88頁74例例 8：證明：證明 PQ 是是 SQ 、R P、SR 的結論的結論證明：設結論 P Q 為假，即 ( PQ ) 為真， 亦即 (P Q ) 為真Q， I7 SQ前提 1RP

59、前提 2編號公式依據(jù)說明說明：此例是反證法的一個實例：由結論為假，以及若干前：此例是反證法的一個實例：由結論為假，以及若干前 提為真，推得某一前提為假提為真，推得某一前提為假R，I12SR，I9(SR)，摩根定理即前提 3 為假(PQ )結論即結論為假 P ， I7I7： (PQ ) P S ，I12 I12：Q, PQ P習題習題：第73頁/共88頁75它表示：兩個前提中，若一個是蘊涵式命題，另一個是其前件，則該蘊涵式的后件也是真命題。它表示：兩個前提中，若一個是蘊涵式命題，另一個是其前件，則該蘊涵式的后件也是真命題。特別在被推理的蘊涵關系式中，結論是一個蘊涵式特別在被推理的蘊涵關系式中，結

60、論是一個蘊涵式P Q 時，可以把結論中的前件時，可以把結論中的前件P 作為附加前提加到前提集合中，最后證得結論的后件為真即可。作為附加前提加到前提集合中，最后證得結論的后件為真即可。因此，因此，I11 又被稱為又被稱為“假言推理假言推理”和和“分離規(guī)則分離規(guī)則”。這個公式用得很多。這個公式用得很多。在前述的在前述的16 個推理定理中，值得特別提出的是個推理定理中，值得特別提出的是 I11 ：P，PQ Q 。習題習題：第74頁/共88頁76 (PQ)R前提 1PQ , 摩根定理編號公式依據(jù) S 前提 3P假設(附加前提)Q, , I10R S前提 2R, , I10I10： P，PQ Q例 9