數(shù)理邏輯與集合論：1 命題邏輯的基本概念

1、 引言n 現(xiàn)代科學技術(shù)的各個領(lǐng)域，都提出了大量離散結(jié)構(gòu)的科學問題。例如：n計算機科學計算機科學n程序設(shè)計程序設(shè)計n計算機網(wǎng)絡(luò)計算機網(wǎng)絡(luò)n信息論與編碼信息論與編碼n通信理論通信理論n現(xiàn)代密碼學現(xiàn)代密碼學n數(shù)字信號處理數(shù)字信號處理n形式語言形式語言 等等 它們都與離散數(shù)學密切相關(guān)。引言n離散數(shù)學n是是現(xiàn)代數(shù)學現(xiàn)代數(shù)學的一個重要分支，是計算機科學中基的一個重要分支，是計算機科學中基礎(chǔ)理論的礎(chǔ)理論的核心課程核心課程。n主要目標主要目標 研究研究離散量離散量的結(jié)構(gòu)和相互之間關(guān)系。的結(jié)構(gòu)和相互之間關(guān)系。n研究對象研究對象 一般是一般是有限個有限個或或可數(shù)個可數(shù)個元素。元素。n研究內(nèi)容研究內(nèi)容n數(shù)理邏輯數(shù)理

2、邏輯n集合論集合論n代數(shù)學代數(shù)學n組合數(shù)學組合數(shù)學n圖論圖論n計算理論計算理論n復(fù)雜網(wǎng)絡(luò)復(fù)雜網(wǎng)絡(luò)n網(wǎng)格及網(wǎng)絡(luò)計算等網(wǎng)格及網(wǎng)絡(luò)計算等數(shù)理邏輯與集合論的主要內(nèi)容第一部分第一部分 數(shù)理邏輯數(shù)理邏輯第第1章章 命題邏輯的基本概念命題邏輯的基本概念第第2章章 命題邏輯的等值和推理演算命題邏輯的等值和推理演算第第4章章 謂詞邏輯的基本概念謂詞邏輯的基本概念第第5章章 謂詞邏輯的等值和推理演算謂詞邏輯的等值和推理演算第二部分第二部分 集合論集合論第第 9 章章 集合集合第第10章章 關(guān)系關(guān)系第第11章章 函數(shù)函數(shù)第第12章章 實數(shù)集合與集合的基數(shù)實數(shù)集合與集合的基數(shù)本課程的要求n授課總學時n32學時：授課周

3、數(shù)為學時：授課周數(shù)為16周，每周周，每周2學時；學時；n作業(yè)第第3 3、6 6、8 8、1010、1212、1414、1616周周交作業(yè)，只有當交作業(yè)，只有當作業(yè)收齊交到講臺上后才開始上課作業(yè)收齊交到講臺上后才開始上課；n成績評定n 平平 時時 成成 績：績：20%n期末考成績：期末考成績：80%第一部分 數(shù)理邏輯n 先看著名物理學家愛因斯坦出的一道題先看著名物理學家愛因斯坦出的一道題: n一個商人想招聘一位聰明的助手，有兩人前來應(yīng)聘，一個商人想招聘一位聰明的助手，有兩人前來應(yīng)聘，商人為了試試誰更聰明，就把兩人帶進一間漆黑的屋商人為了試試誰更聰明，就把兩人帶進一間漆黑的屋子里，子里，n他打開燈

4、后說他打開燈后說：“桌子上有五頂帽子，桌子上有五頂帽子，兩頂紅色兩頂紅色，三三頂黑色頂黑色，現(xiàn)在把燈關(guān)掉，并把帽子的位置弄亂，然后，現(xiàn)在把燈關(guān)掉，并把帽子的位置弄亂，然后我們每人摸一頂帽子戴在自己頭上，我再藏起余下的我們每人摸一頂帽子戴在自己頭上，我再藏起余下的兩頂帽子，開燈后，你們要盡快說出自己頭上戴的帽兩頂帽子，開燈后，你們要盡快說出自己頭上戴的帽子的顏色。子的顏色?！眓當開燈后，那兩個應(yīng)試者看到商人頭上戴的是一頂當開燈后，那兩個應(yīng)試者看到商人頭上戴的是一頂紅紅帽子帽子，其中一個人便喊道：，其中一個人便喊道：“我戴的是我戴的是黑帽子黑帽子?！眓 請問這個人說得對嗎？他是怎么推導出來的呢？請

5、問這個人說得對嗎？他是怎么推導出來的呢？ 第一部分 數(shù)理邏輯n 這需要經(jīng)歷如下過程：這需要經(jīng)歷如下過程：n 什么是前提？有哪些前提？什么是前提？有哪些前提？n 結(jié)論是什么？結(jié)論是什么？n 根據(jù)什么進行推理？根據(jù)什么進行推理？n 怎么進行推理？怎么進行推理？ n 數(shù)理邏輯將回答這些問題，它包括數(shù)理邏輯將回答這些問題，它包括n 命題邏輯命題邏輯n 一階邏輯一階邏輯n 數(shù)理邏輯（符號邏輯）數(shù)理邏輯（符號邏輯）n 是用數(shù)學方法來研究是用數(shù)學方法來研究推理推理的的形式結(jié)構(gòu)形式結(jié)構(gòu)和和推理規(guī)律推理規(guī)律的數(shù)學學科的數(shù)學學科n 它除了研究數(shù)學基礎(chǔ)課題個，還擴展到了現(xiàn)代科學技術(shù)中，如它除了研究數(shù)學基礎(chǔ)課題個，還

6、擴展到了現(xiàn)代科學技術(shù)中，如n 程序語言、自動機理論、邏輯網(wǎng)絡(luò)、機器翻譯與機器證明等程序語言、自動機理論、邏輯網(wǎng)絡(luò)、機器翻譯與機器證明等吳文俊(1919-)數(shù)學機械化n 1976年，吳文俊教授在中國古代數(shù)學的啟發(fā)下，創(chuàng)建了數(shù)學機械化方法n 從從幾何公理體系幾何公理體系出發(fā)，引進坐標，將任意幾何問題出發(fā)，引進坐標，將任意幾何問題代數(shù)化代數(shù)化，將證，將證明題的明題的假設(shè)假設(shè)與與結(jié)論結(jié)論分別表示成分別表示成多元多項式方程多元多項式方程，在計算機上編程，在計算機上編程運算，以判斷定理是否成立。運算，以判斷定理是否成立。n 至至2008年，運用吳文俊教授的方法，已證明出年，運用吳文俊教授的方法，已證明出6

7、00多條定理，許多條定理，許多定理的證明不超過幾秒鐘。甚至有一些定理證明相當繁雜，即多定理的證明不超過幾秒鐘。甚至有一些定理證明相當繁雜，即便交給杰出的數(shù)學家來證也是相當困難的。便交給杰出的數(shù)學家來證也是相當困難的。n “數(shù)學機械化數(shù)學機械化” 是是近代數(shù)學史上的第一個中國原創(chuàng)的領(lǐng)域近代數(shù)學史上的第一個中國原創(chuàng)的領(lǐng)域，被國，被國際上稱為際上稱為“”。n 它它終于實現(xiàn)了千百年來終于實現(xiàn)了千百年來幾何定理幾何定理機械化證明的夢想。機械化證明的夢想。n 它它給給2000多年的公理化演繹體系帶來了強烈沖擊。多年的公理化演繹體系帶來了強烈沖擊。n 2000年年吳文俊吳文俊院士獲院士獲首屆首屆國家最高科技

8、獎國家最高科技獎。第1章 命題邏輯的基本概念 1.1 命題命題1.2 命題聯(lián)結(jié)詞及真值表命題聯(lián)結(jié)詞及真值表1.3 合式公式合式公式1.4 重言式重言式1.5 命題形式化命題形式化1.1 命題n 命題的概念 n引例就是要對引例就是要對“我戴的是黑帽子我戴的是黑帽子”，進行判斷。，進行判斷。這樣的這樣的陳述句陳述句稱為命題。稱為命題。n命題 可判斷真假的陳述句。可判斷真假的陳述句。n如：如：2是素數(shù)。是素數(shù)。 雪是黑色的。雪是黑色的。n命題的真值 判斷的結(jié)果判斷的結(jié)果n真值的取值 真（真（1或或T）與假（）與假（0或或F）n真命題真命題: 真值為真的命題（判斷正確）真值為真的命題（判斷正確）n假命

9、題假命題: 真值為假的命題（判斷錯誤）真值為假的命題（判斷錯誤）n任何命題的真值都是任何命題的真值都是唯一唯一的。的。命題n 注意: n感嘆句、祈使句、疑問句都不是命題感嘆句、祈使句、疑問句都不是命題n如：如：你跑得真快！你跑得真快！ 全體起立。全體起立。 又上課了嗎？又上課了嗎？n陳述句中的陳述句中的判斷結(jié)果不惟一確定判斷結(jié)果不惟一確定以及以及( (疑似疑似) )悖論悖論也不也不是命題是命題n如：如：x + 5 3 我是說謊者。我是說謊者。 利用正三角形導出利用正三角形導出“2=12=1”的的“證明證明”n 判斷給定句子是否為命題的步驟n首先判定它是否為陳述句，首先判定它是否為陳述句，n其次

10、判斷它是否有唯一的真值其次判斷它是否有唯一的真值。 除地球外的星球有生物。除地球外的星球有生物。 太陽明天會出來。太陽明天會出來。命題變項 n約定：用大寫英文字母（如：約定：用大寫英文字母（如：P, Q, R, ）來形式）來形式化命題，如化命題，如n用用P表示表示“ 2是素數(shù)是素數(shù)”。n用用Q表示表示“2 + 5 = 7”。n當當P表示任一命題時，表示任一命題時，P稱為稱為命題變項（變元）命題變項（變元）n命題與命題變項的區(qū)別命題與命題變項的區(qū)別n命題命題指具體確定真值的陳述句指具體確定真值的陳述句相當于常量相當于常量n如：如：“ 2是素數(shù)是素數(shù)”。n命題變項命題變項的真值不確定，它不是命題，

11、當它用確定命題的真值不確定，它不是命題，當它用確定命題取代后，它才能確定真值。取代后，它才能確定真值。命題的分類 n簡單命題(原子命題)n不能分解為更簡單的句子的陳述句。不能分解為更簡單的句子的陳述句。n如如 “2 2是素數(shù)是素數(shù)”n復(fù)合命題復(fù)合命題n由幾個簡單命題與由幾個簡單命題與聯(lián)結(jié)詞聯(lián)結(jié)詞按一定規(guī)則復(fù)合而成按一定規(guī)則復(fù)合而成的命題的命題 。n如：如： 3不不是偶數(shù)。是偶數(shù)。 2是素數(shù)是素數(shù)和和偶數(shù)偶數(shù)。1.2 命題聯(lián)結(jié)詞及真值表1. 否定詞n 定義定義: 設(shè)設(shè) P 是一個命題是一個命題, 構(gòu)造一個新命題是原命構(gòu)造一個新命題是原命題的否定題的否定, 稱該命題是命題稱該命題是命題 P 的的取

12、否命題取否命題, 表示表示成成“ P ”.n規(guī)定規(guī)定: :n P 為真當且僅當為真當且僅當P為假為假例如例如: P : 今天下雨今天下雨. P : 今天今天不不下雨下雨.自然語言中用到的聯(lián)結(jié)詞自然語言中用到的聯(lián)結(jié)詞: 非非 , 不不 , 并非并非 P PF T T F 真值表真值表公式在所有賦值下的取值公式在所有賦值下的取值情況列成的表情況列成的表 聯(lián)結(jié)詞2. 合取詞 n 定義定義: 設(shè)命題設(shè)命題 P 和和 Q 是兩個命題是兩個命題,構(gòu)造一個新命題構(gòu)造一個新命題“ P 與與 Q ”,稱作命題稱作命題 P 和和 Q 的合取的合取,表示成表示成“P Q ”. n 規(guī)定規(guī)定n當且僅當當且僅當 P 和

13、和 Q 都為真時都為真時, P Q 為真為真.n 自然語言中用到的聯(lián)結(jié)詞自然語言中用到的聯(lián)結(jié)詞:n“和和”，“與與” , “, “并且并且”n“既既.又又.” .” “不僅不僅.而且而且.” n“雖然雖然.但是但是. P Q P Q F FF TT FT T FFFT 例: 將下列命題符號化 P:李平聰明. Q:李平用功.(1) 李平既聰明又用功. (2) 李平雖然聰明但不用功.(3) 李平不但聰明而且用功.(4) 李平不是不聰明而是不用功.P QP QP Q ( P) Q例例: P:今天下雨今天下雨. Q: 3+3=6今天下雨與今天下雨與3+3=6. 可表示為可表示為:P Q “ ” 可以連

14、接兩個完全沒有聯(lián)系的命題可以連接兩個完全沒有聯(lián)系的命題. .聯(lián)結(jié)詞3. 析取詞n 定義定義:設(shè)命題設(shè)命題 P 和和 Q 是兩個命題是兩個命題, 構(gòu)造一個新命題構(gòu)造一個新命題“ P 或或Q ”, 稱作命題稱作命題 P 和和 Q 的析取的析取, 表示成表示成“P Q”. n 規(guī)定規(guī)定nPQ為假當且僅當為假當且僅當 P 與與 Q 同時為假同時為假. n當且僅當當且僅當 P 和和 Q 中至少一個為真時中至少一個為真時, P Q 為真為真. P Q PQ F FF TT FT TFTTT聯(lián)結(jié)詞n 例如：n P: 燈泡有故障燈泡有故障. Q: 開關(guān)有故障開關(guān)有故障.n燈泡有故障或開關(guān)有故障燈泡有故障或開關(guān)

15、有故障. (可能同時發(fā)生可能同時發(fā)生)n應(yīng)表示為應(yīng)表示為 P Qn 注意注意: 析取詞析取詞表示的是表示的是“可兼或可兼或”.n 例如例如:n P: 小李正在家里看書小李正在家里看書. Q: 小李正在劇場看戲小李正在劇場看戲.n 小李正在家里看書或正在劇場看戲小李正在家里看書或正在劇場看戲. （不可能同時發(fā)生）（不可能同時發(fā)生）n 表示為：表示為： (P Q) ( P Q) =P Q P Q P Q F FF TT F T TFTT F P Q PQ F FF TT FT TFTTT4. 蘊涵詞n 定義定義: 設(shè)設(shè) P,Q為二命題，復(fù)合命題為二命題，復(fù)合命題 “如果如果P,則則Q” 稱作稱作P

16、與與Q的的蘊涵式蘊涵式，記作，記作 P Q，并稱，并稱nP是蘊涵式的是蘊涵式的前件前件，nQ為蘊涵式的為蘊涵式的后件后件， n稱作稱作蘊涵聯(lián)結(jié)詞蘊涵聯(lián)結(jié)詞，n P是是Q的的充分條件充分條件，Q是是P 的的必要條件必要條件。n 常見錯誤常見錯誤n不分不分充分與必要條件充分與必要條件n混淆混淆充分與必要條件充分與必要條件聯(lián)結(jié)詞n“如果如果 P，則，則 Q ” 的不同表述法很多的不同表述法很多n 若若 P，就就 Qn 只要只要 P，就就 Qn P 僅當僅當 Qn 只有只有 Q 才才 Pn 除非除非 Q, 才才 P n 除非除非 Q, 否則非否則非 P聯(lián)結(jié)詞 PQ P是是Q 的的充分條件充分條件 P是

17、是Q 的的必要條件必要條件。（1）只要不下雨，我就騎自行車上班。（2）只有不下雨，我才騎自行車上班。設(shè)：設(shè)：P：天下雨。：天下雨。Q：我騎自行車上班。：我騎自行車上班。(1) 等價為：除非我騎自行車上班，否則天下雨除非我騎自行車上班，否則天下雨。 P Q（2）等價為：除非不下雨，我才騎自行車上班除非不下雨，我才騎自行車上班。 Q P 注意：注意：P Q 中的中的 P 和和 Q 不一定有內(nèi)在聯(lián)系不一定有內(nèi)在聯(lián)系。 例: 將下列命題符號化 聯(lián)結(jié)詞n 規(guī)定規(guī)定nPQ為為假假當且僅當當且僅當P為真為真Q為假為假. n當當 P 為假時，為假時，PQ 為真為真n 說明說明n如：如：P:“天氣好天氣好” Q

18、:“我去接你我去接你”n則則P Q ：“若天氣好，則我去接你若天氣好，則我去接你”n當天氣好時，當天氣好時，n我去接了你，此時，我去接了你，此時， P Q 真真n我沒去接你，此時，我沒去接你，此時， P Q 假假n 當天氣不好時，當天氣不好時，n我無論去或不去接你均未食言，此時認定我無論去或不去接你均未食言，此時認定P Q 為真為真是適當?shù)氖沁m當?shù)?P Q P Q F FF TT FT TTTFT PQ= P Q聯(lián)結(jié)詞5. 雙條件詞n 定義：定義：設(shè)設(shè)P，Q為二命題，為二命題， “P當且僅當當且僅當Q”稱作稱作 P 與與 Q 的的等價式等價式，記作，記作PQ，n 規(guī)定規(guī)定nPQ 為為真真當且僅

19、當當且僅當 P 與與 Q 真值相同真值相同.n 說明說明:n PQ 的邏輯關(guān)系的邏輯關(guān)系: P 與與 Q 互為充分必要條件互為充分必要條件 P Q P Q F FF TT FT TTFFT P Q=(PQ) (Q P)聯(lián)結(jié)詞舉例 P：兩個三角形是全等的。 Q：兩個三角形的三條對應(yīng)邊相等。則等價命題：則等價命題： P Q：兩個三角形全等，當且僅當它們的三條對應(yīng)邊兩個三角形全等，當且僅當它們的三條對應(yīng)邊分別相等。分別相等。下列復(fù)合命題的真值為(1) 2 + 2 4 當且僅當當且僅當 3 + 3 6.(2) 2 + 2 4 當且僅當當且僅當 3 是偶數(shù)是偶數(shù).(3) 2 + 2 4 當且僅當當且僅當

20、 太陽從東方升起太陽從東方升起.110 聯(lián)結(jié)詞的優(yōu)先順序為：聯(lián)結(jié)詞的優(yōu)先順序為： , , , , 1.3 合式公式n 合式公式n它由它由命題命題、命題變項命題變項按照一定的邏輯順序用按照一定的邏輯順序用命題聯(lián)結(jié)命題聯(lián)結(jié)詞詞連接起來構(gòu)成連接起來構(gòu)成n 合式公式（公式）的遞歸定義：(1)簡單命題是合式公式簡單命題是合式公式(2)若若A是合式公式，則是合式公式，則 ( A)也是合式公式也是合式公式(3)若若A, B是合式公式，則是合式公式，則(A B), (A B), (AB), (AB)也是合式公式也是合式公式(4)當且僅當經(jīng)過當且僅當經(jīng)過有限次有限次地使用地使用(1)(3)所組成的符號串才所組成

21、的符號串才是合式公式是合式公式n 說明:n (P Q), P(Q R), (P Q ) R 是合式公式是合式公式nPQR, P Q ，( P R ) ( P) 不是合式公式不是合式公式n 例如：合式公式 A=（P Q） Rn若若 P: “2是素數(shù)是素數(shù)”， Q: “3是奇數(shù)是奇數(shù)”， R :“4能被能被2整除整除”n則則A為為真命題。真命題。n若若 P: “2是素數(shù)是素數(shù)”， Q: “3是奇數(shù)是奇數(shù)”， R :“3能被能被2整除整除”n則則A為假命題。為假命題。合式公式的真值n 一個含有命題變項的合式公式的真值是不確定的.n 只有對合式公式的每個只有對合式公式的每個命題變項命題變項用指定的用指定的命題命題代替后，代替后，合式公式才成為合式公式才成為命題命題，其值才唯一確定。，其值才唯一確定。公式的賦值 n 定義定義 n給公式給公式A中的命題變項中的命題變項 P1, P2, , Pn指定一組真值稱指定一組真值稱為對為對A的一個的一個賦值賦值或或解釋解釋n成真賦值成真賦值: 使公式為真的賦值使公式為真的賦值n成假賦值成假賦值: 使公式為假的賦值使公式為假的賦值n 說明：說明：n A中僅出現(xiàn)中僅出現(xiàn) P1, P2, , Pn，給，給A賦值賦值 1 2 n是指是指 P1= 1, P2= 2, , Pn= n ， i