命題邏輯PPT學(xué)習(xí)教案

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

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

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

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

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

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

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

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

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

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

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

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

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

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

15、：令：令 P：小張?jiān)趫D書館，：小張?jiān)趫D書館， Q：小張?jiān)谒蓿盒堅(jiān)谒奚嵘?命題表示為：命題表示為：習(xí)題習(xí)題： 他寫了他寫了 30 行或行或 50 行行字字解解：這里的：這里的“或或”可以有兩種不同的理解：可以有兩種不同的理解： (PQ)(PQ)一是，一是，“不可兼得的或不可兼得的或”，如上題寫成一復(fù)合命題；，如上題寫成一復(fù)合命題；二是，可作二是，可作“或許或許”，“大概大概”理解，就是一個(gè)原子理解，就是一個(gè)原子命題。命題。第19頁/共88頁21習(xí)題習(xí)題：1、2、3 趙常與錢深是好學(xué)生趙常與錢深是好學(xué)生解解：令：令 P：趙常是好學(xué)生，：趙常是好學(xué)生， Q：錢深是好學(xué)：錢深是好學(xué)生生 趙常與錢深是

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

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

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

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

20、各變元的一組真值指派真值指派習(xí)題習(xí)題：4作業(yè)例例： (PQ)(QS) 公式的各組真值指派就是其中公式的各組真值指派就是其中3個(gè)變元在真值表最個(gè)變元在真值表最左邊列出的左邊列出的8組值組值第26頁/共88頁28重言式重言式：若一個(gè)公式對于它的所有命題變元的任何一若一個(gè)公式對于它的所有命題變元的任何一 組真值指派，取值恒為真，則稱該公式為組真值指派，取值恒為真，則稱該公式為重言式重言式 或或永真公式永真公式，常用常用 “1” 表示表示習(xí)題習(xí)題：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習(xí)題習(xí)題：5、6作業(yè)矛盾式矛盾式：若一個(gè)公式對于它的所有命題變元的任何一：若一個(gè)公式對于它的所有命題變元的任何一 組真值指派，取值恒為假，則稱該公式為組真值指派，取值恒為假，則稱該公式為矛盾式矛盾式 或或永假公式永假公式，常用常用 “0” 表示表示可滿足公式可滿足公式：若一個(gè)公式至少有一組真值指派使公式若一個(gè)公式至少有一組真值指派使公式 的值為真，則稱該公式為的值為真，則稱該公式為可滿足公式可滿足公式例例： (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 命題公式的等值關(guān)系和蘊(yùn)涵關(guān)系命題公式的等值關(guān)系和蘊(yùn)涵關(guān)系 就像代數(shù)式之間有等式和不等式一樣，命題公式就像代數(shù)式之間有等式和不等式一樣，命題公式之間也常有一些關(guān)系，最基本的關(guān)系是等值關(guān)系和蘊(yùn)之間也常有一些關(guān)系，最基本的關(guān)系是等值關(guān)系和蘊(yùn)涵關(guān)系涵關(guān)系習(xí)題習(xí)題：4作業(yè) 等值關(guān)系實(shí)質(zhì)上是表示兩個(gè)公式之間的一種關(guān)等值關(guān)系實(shí)質(zhì)上是表示兩個(gè)公式之間的一種關(guān) 系，系， “ ” 是

23、一個(gè)表示關(guān)系的符號(hào)。是一個(gè)表示關(guān)系的符號(hào)。公式等值公式等值：設(shè)設(shè) A和和B是兩個(gè)命題公式，當(dāng)且僅當(dāng)是兩個(gè)命題公式，當(dāng)且僅當(dāng)A和和B 的真值表完全相同時(shí)，稱的真值表完全相同時(shí)，稱 A 和和 B 是是等值公式等值公式 記為記為 A B 注注： 公式等值的另一種定義是：公式等值的另一種定義是： 若若 AB 為重言式，則稱為重言式，則稱 A和和B是是等值公式等值公式第29頁/共88頁31基本等值關(guān)系：下面列出基本等值關(guān)系：下面列出 26 個(gè)重要的等值關(guān)系，它們可以像集個(gè)重要的等值關(guān)系，它們可以像集 合恒等式一樣用于推導(dǎo)其它等值關(guān)系合恒等式一樣用于推導(dǎo)其它等值關(guān)系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 交換交換律律 結(jié)合結(jié)合律律 分配分配律律 同一同一律律 零一零一律律 互否互否律律 雙重否定雙重否定律律 E7：P P P E7：P P P 等冪等冪律律 E9：P(PQ) P E9：P(PQ) P吸收吸收律律 E10：(PQ) PQE10：(PQ) PQ德摩根定律德摩根定律習(xí)題習(xí)題：第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 個(gè)等值關(guān)系中，前個(gè)等值關(guān)系中，前 19 個(gè)與集合恒等式的基本公式個(gè)與集合恒等式的基本公式 (參見書參見書 p16)非常相似非常相似 這里的這里的 “” 相當(dāng)于集合運(yùn)算符相當(dāng)于集合運(yùn)算符 “” 這里的這里的 “” 相當(dāng)于集合運(yùn)算符相當(dāng)于集合運(yùn)算符 “” 這里的這里的 “ ” 相當(dāng)于集合運(yùn)算符相當(dāng)于集合運(yùn)算符 “ ” 這這 26 個(gè)等值關(guān)系中，后個(gè)等值關(guān)系中，

26、后 7 個(gè)關(guān)系表明，所有命題公式個(gè)關(guān)系表明，所有命題公式 都能用都能用 “”、 “”、“ ” 表示表示 這這 26 個(gè)等值關(guān)系的證明都可以用真值表進(jìn)行，個(gè)等值關(guān)系的證明都可以用真值表進(jìn)行， 這是最基本的證明方法。這是最基本的證明方法。習(xí)題習(xí)題：第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 習(xí)題習(xí)題：例例 1：證明等值關(guān)系：證明等值關(guān)系： 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 習(xí)題習(xí)題：例例 2：證明等值關(guān)系：證明等值關(guān)系： P Q (P Q)( P Q) 從真值表可看出從真值表可看出 P Q (P Q)(P Q)第34頁/共88頁36 在代數(shù)中對公式進(jìn)行推導(dǎo)時(shí)，可以使用變量代換在代數(shù)中對公式進(jìn)行推導(dǎo)時(shí)，可以使用變量代換和公式代換。在這里，等值關(guān)系的推導(dǎo)中也有同樣的和公式代換。在這里，等值關(guān)系的推導(dǎo)中也有同樣的代換規(guī)則。代換規(guī)則。代換實(shí)例代換實(shí)例：設(shè)設(shè) A

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

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

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

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

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

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

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

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

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

37、9-4：設(shè)設(shè) A 、 B 為兩個(gè)命題公式，為兩個(gè)命題公式，AB 的的 充要條件是，充要條件是， AB 且且 BA 證證：設(shè)：設(shè) AB ，則，則 AB 是重言式，即是重言式，即 AB 1而而 A B (AB)(BA )(AB) (BA) 1，則，則 AB 1 且且 BA 1 按蘊(yùn)涵關(guān)系的定義，有按蘊(yùn)涵關(guān)系的定義，有 AB 且且 BA第45頁/共88頁47習(xí)題習(xí)題：定理定理 9-5：設(shè)：設(shè) 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蘊(yùn)涵關(guān)系：下面列出幾蘊(yùn)涵關(guān)系：下面列出幾 個(gè)重要的蘊(yùn)涵關(guān)系，它們可以個(gè)重要的蘊(yùn)涵關(guān)系，它們可以 按照定義直接證明按照定義直接證明習(xí)題習(xí)題：PQ P PQ Q P PQ Q PQP PQ Q PQ第47頁/共88頁49證明蘊(yùn)涵關(guān)系的方法證明蘊(yùn)涵關(guān)系的方法根據(jù)蘊(yùn)涵關(guān)系的定義證。把蘊(yùn)涵關(guān)系相應(yīng)的蘊(yùn)涵式根據(jù)蘊(yùn)涵關(guān)系的定義證。把蘊(yùn)涵關(guān)系相應(yīng)的蘊(yùn)涵式 PQ的等值式的等值式 PQ 變換成變換成 1 即可。即可。 列出蘊(yùn)涵關(guān)系左右公式的真值表，用真值表比較列出蘊(yùn)涵關(guān)系左右公式的真值表，用真值表比較習(xí)題習(xí)題：根據(jù)蘊(yùn)涵聯(lián)結(jié)

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

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

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

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

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

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

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

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

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

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

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

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

51、62頁/共88頁64例例 1：有前提：有前提 H1，H2，和結(jié)論，和結(jié)論 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 習(xí)題習(xí)題：(P Q )P) Q1 1 1 1 ( (PQ )Q )P1 0 1 1 第63頁/共88頁65例 1：有前提 H1，H2，和結(jié)論 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 ：如果今天出太陽，他就進(jìn)城 P ：今天出了太陽Q ：他進(jìn)城了 P Q ：如果狗有翅膀，則狗會(huì)飛上天 P ：狗有了翅膀Q ：狗飛上了天 P Q ：如果 n 是素?cái)?shù)，則 n 一定是整數(shù)Q ：n 是整數(shù)P ： n 是素?cái)?shù)習(xí)題習(xí)題：第64頁/共88頁66例 2：證明 C ：P 是前提 H1 ：P Q 和 H2 ：(P Q )的結(jié)論 C 是前提 H1 和 H2 的結(jié)論習(xí)題習(xí)題： ( ( 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 用直接證明法用直接證明法 ，我們設(shè)每一個(gè)前提的真值為真，我們設(shè)每一個(gè)前提的真值為真 ，能推導(dǎo)出，能推導(dǎo)出結(jié)論的真值也為真，則原推理正確，否則不正確。結(jié)論的真值也為真，則原推理正確，否則不正確。例 3：證明 P 是前提 (P Q )，QR ，R 的結(jié)論 P 是前提 (PQ )，QR ，R 的結(jié)論習(xí)題習(xí)題：證 設(shè) R為真 (前提3為真) 得 R 為假 將 R為假代入得：Q為真 繼得 Q 為假 設(shè) (PQ )

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

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

56、P 為真 (前提 2為真) 把 P 為假 代入 得 R 為假 于是 S R 為假 (得前提 3 為假)討論討論：此題用：此題用”直接證明直接證明”好，還是用好，還是用”反證法反證法”好好?第69頁/共88頁71在上述例子中，無論是直接證明還是反證法，都用到了各種推理規(guī)則，例如，全體引入規(guī)則，置換規(guī)則，代入規(guī)則等。而直接使用已知的蘊(yùn)涵關(guān)系式卻沒有。在上述例子中，無論是直接證明還是反證法，都用到了各種推理規(guī)則，例如，全體引入規(guī)則，置換規(guī)則，代入規(guī)則等。而直接使用已知的蘊(yùn)涵關(guān)系式卻沒有。習(xí)題習(xí)題：下面列出一些常用的蘊(yùn)涵關(guān)系式下面列出一些常用的蘊(yùn)涵關(guān)系式(推理定理推理定理)：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習(xí)題習(xí)題：如果證明過程的每一步所得到的結(jié)論都是根據(jù)推理規(guī)則得到的，如果證明過程的每一步所得到的結(jié)論都是根據(jù)推理規(guī)則得到的，則稱這樣的證明為則稱這樣的證明為“有效的有效的”，或曰，或曰“合理的合理的”下面舉例介紹利用推理定理進(jìn)行推理

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

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

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