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

1、 命題與聯(lián)結(jié)詞離散數(shù)學(xué)邏輯邏輯 研究人類思維的科學(xué)。公元前四世紀(jì)亞里斯多德工具論奠定了邏輯學(xué)的理論基礎(chǔ)。中國最早的一部邏輯專著墨經(jīng)也創(chuàng)造了一個(gè)比較完整的邏輯體系。離散數(shù)學(xué)數(shù)理邏輯數(shù)理邏輯是一門用數(shù)學(xué)方法來研究推理規(guī)律數(shù)理邏輯是一門用數(shù)學(xué)方法來研究推理規(guī)律的科學(xué)。的科學(xué)。所謂數(shù)學(xué)方法主要是指引進(jìn)一套符號體系的所謂數(shù)學(xué)方法主要是指引進(jìn)一套符號體系的方法，所以數(shù)理邏輯也稱做符號邏輯。方法，所以數(shù)理邏輯也稱做符號邏輯。（創(chuàng)始人：十七世紀(jì)，德國數(shù)學(xué)家萊布尼茲）離散數(shù)學(xué)形式符號體系形式符號體系 由于自然語言存在模棱兩可、含糊的特性，所以有必要引入由于自然語言存在模棱兩可、含糊的特性，所以有必要引入形式化語

2、言。形式化語言在數(shù)理邏輯中稱為目標(biāo)語言。形式化語言。形式化語言在數(shù)理邏輯中稱為目標(biāo)語言。 例如：今天晚上八點(diǎn)中央一臺播放連續(xù)劇或紀(jì)錄片。例如：今天晚上八點(diǎn)中央一臺播放連續(xù)劇或紀(jì)錄片。 我吃蘋果或雪梨。我吃蘋果或雪梨。 定義定義目標(biāo)語言：具有單一、明確的含義的語言。（基本元素目標(biāo)語言：具有單一、明確的含義的語言。（基本元素是命題）是命題） 定義定義形式符號體系：由目標(biāo)語言和一些規(guī)定的公式與符號構(gòu)形式符號體系：由目標(biāo)語言和一些規(guī)定的公式與符號構(gòu)成的體系成的體系離散數(shù)學(xué)為何學(xué)習(xí)數(shù)理邏輯為何學(xué)習(xí)數(shù)理邏輯 程序程序 = 算法算法 + 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 算法算法 = 邏輯邏輯 + 控制控制 離散數(shù)學(xué)數(shù)理邏

3、輯的主要內(nèi)容數(shù)理邏輯的主要內(nèi)容 數(shù)理邏輯內(nèi)容豐富，但其主要包括數(shù)理邏輯內(nèi)容豐富，但其主要包括“兩個(gè)演算兩個(gè)演算” 加加“四論四論”，即：，即： 邏輯演算。包括命題演算和謂詞演算邏輯演算。包括命題演算和謂詞演算 證明論。主要研究數(shù)學(xué)理論系統(tǒng)的相容性（即不矛盾、證明論。主要研究數(shù)學(xué)理論系統(tǒng)的相容性（即不矛盾、協(xié)調(diào)性）的證明。協(xié)調(diào)性）的證明。 遞歸論（能行性理論）。自從電子計(jì)算機(jī)發(fā)明后，迫切遞歸論（能行性理論）。自從電子計(jì)算機(jī)發(fā)明后，迫切需要在理論上弄清計(jì)算機(jī)能計(jì)算哪些函數(shù)。遞歸論研究需要在理論上弄清計(jì)算機(jī)能計(jì)算哪些函數(shù)。遞歸論研究能行可計(jì)算的理論，它為能行可計(jì)算的函數(shù)找出各種理能行可計(jì)算的理論，它

4、為能行可計(jì)算的函數(shù)找出各種理論上精確化的嚴(yán)密類比物。論上精確化的嚴(yán)密類比物。 模型論。主要是對各種數(shù)學(xué)理論系統(tǒng)建立模型，并研究模型論。主要是對各種數(shù)學(xué)理論系統(tǒng)建立模型，并研究各模型之間的關(guān)系以及模型與系統(tǒng)之間的關(guān)系。各模型之間的關(guān)系以及模型與系統(tǒng)之間的關(guān)系。 公理集合論。主要研究在消除已知集合論悖論的情況下，公理集合論。主要研究在消除已知集合論悖論的情況下，用公理方法把有關(guān)集合的理論充分發(fā)展下去。用公理方法把有關(guān)集合的理論充分發(fā)展下去?，F(xiàn)代數(shù)理邏輯離散數(shù)學(xué)命題邏輯研究的內(nèi)容命題邏輯研究的內(nèi)容 命題邏輯也稱為命題演算命題邏輯也稱為命題演算 研究以命題為基本單位構(gòu)成的前提和結(jié)論之間的可推導(dǎo)關(guān)系研究

5、以命題為基本單位構(gòu)成的前提和結(jié)論之間的可推導(dǎo)關(guān)系. (1) 什么是命題？什么是命題？ (2) 如何表示命題？如何表示命題？ (3) 如何由一些前提推導(dǎo)出一些結(jié)論如何由一些前提推導(dǎo)出一些結(jié)論?離散數(shù)學(xué)命題與聯(lián)結(jié)詞命題與聯(lián)結(jié)詞 命題命題 聯(lián)結(jié)詞聯(lián)結(jié)詞離散數(shù)學(xué)命題的概念命題的概念具有判斷內(nèi)容（非真即假）的陳述句稱為命題。具有判斷內(nèi)容（非真即假）的陳述句稱為命題。 能夠確定或分辨其真假的陳述句。能夠確定或分辨其真假的陳述句。命題有一個(gè)值，稱為真值，真值只有命題有一個(gè)值，稱為真值，真值只有“真真”和和“假假”兩種，分別用兩種，分別用“T”（或（或“1”）和）和“F”（或（或“0”）表）表示。示。命題中的

6、判斷正確，其真值為真，稱為真命題，命命題中的判斷正確，其真值為真，稱為真命題，命題中的判斷錯(cuò)誤，真值為假，稱為假命題。題中的判斷錯(cuò)誤，真值為假，稱為假命題。離散數(shù)學(xué)命題示例命題示例1 中華人民共和國的首都是北京。中華人民共和國的首都是北京。 我們在學(xué)習(xí)我們在學(xué)習(xí)離散數(shù)學(xué)離散數(shù)學(xué)的數(shù)理邏輯部分。的數(shù)理邏輯部分。 所有素?cái)?shù)都是奇數(shù)。所有素?cái)?shù)都是奇數(shù)。 雪是黑色的。雪是黑色的。離散數(shù)學(xué)命題示例命題示例2 某些感嘆句、祈使句、疑問句等沒有真假之分，所以不是某些感嘆句、祈使句、疑問句等沒有真假之分，所以不是命題。命題。 明天開會嗎？明天開會嗎？ 多美妙啊！多美妙啊！ 請進(jìn)來。請進(jìn)來。 全體立正。全體立正

7、。離散數(shù)學(xué)判斷語句是否為命題要注意的問題：判斷語句是否為命題要注意的問題： 目前無法確定真值，但從本質(zhì)而言，真值存在的語句是命題。目前無法確定真值，但從本質(zhì)而言，真值存在的語句是命題。例：例： (1) 別的星球上有生物。別的星球上有生物。 (2) 2046年世界杯在中國舉行。年世界杯在中國舉行。 真值因時(shí)因地而異的判斷性陳述句是命題。真值因時(shí)因地而異的判斷性陳述句是命題。例：例：(1) 現(xiàn)在是上午?，F(xiàn)在是上午。 (2) 今天下雨。今天下雨。 含有未確定內(nèi)容的代詞，不能判斷真假的語句不是命題。含有未確定內(nèi)容的代詞，不能判斷真假的語句不是命題。例：例： (1) 1+101=110。當(dāng)當(dāng)1和和101

8、是二進(jìn)制數(shù)，語句為真，為十進(jìn)制數(shù)，語句為假。是二進(jìn)制數(shù)，語句為真，為十進(jìn)制數(shù)，語句為假。 (2) x+y10。 悖論不是命題。悖論不是命題。 例：我正在說慌。例：我正在說慌。離散數(shù)學(xué) 命題的分類命題的分類根據(jù)命題的構(gòu)成形式，可以將命題分為：根據(jù)命題的構(gòu)成形式，可以將命題分為：定義定義原子命題原子命題：不包含任何聯(lián)結(jié)詞的：不包含任何聯(lián)結(jié)詞的命題命題。定義定義復(fù)合命題：復(fù)合命題：由由原子命題原子命題和聯(lián)結(jié)詞組成的命題和聯(lián)結(jié)詞組成的命題。連接詞一。連接詞一般譯為：般譯為：“或者或者”、“并且并且”、“不不”、“如果如果則則”、“僅僅當(dāng)當(dāng)”、“當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)”等。等。 例如：例如：“明天下雪明天下雪

9、”、“9是素?cái)?shù)是素?cái)?shù)”都是原子命題，都是原子命題， “2不是素?cái)?shù)不是素?cái)?shù)”是復(fù)合命題是復(fù)合命題 “明天下雪或明天下雨明天下雪或明天下雨”是復(fù)合命題。是復(fù)合命題。 “中國獲得中國獲得2008奧運(yùn)的主辦權(quán)并且加入了奧運(yùn)的主辦權(quán)并且加入了WTO”是復(fù)合命題。是復(fù)合命題。 “如果如果A和和B是對頂角，則角是對頂角，則角A等于角等于角B”是復(fù)合命題。是復(fù)合命題。離散數(shù)學(xué) 命題的表示命題的表示 定義定義命題標(biāo)識符：表示命題的符號，通常是大寫英文字母。命題標(biāo)識符：表示命題的符號，通常是大寫英文字母。 定義定義命題符號化：將表示命題的符號放在該命題的前面。命題符號化：將表示命題的符號放在該命題的前面。 例：例

10、：P P：北京是中國的首都。北京是中國的首都。 Q Q：北京承辦：北京承辦20082008年奧運(yùn)。年奧運(yùn)。 離散數(shù)學(xué)命題的表示（續(xù)）命題的表示（續(xù)） 定義定義 命題常量：表示命題常量：表示確定命題確定命題的命題標(biāo)識符。的命題標(biāo)識符。 定義定義 命題變元：可表示任意一個(gè)（原子或復(fù)合）命題的命題變元：可表示任意一個(gè)（原子或復(fù)合）命題的命命題標(biāo)識符題標(biāo)識符，就稱為命題變元。當(dāng)，就稱為命題變元。當(dāng)命題變元命題變元表示表示原子命題原子命題時(shí)，時(shí)，該變元稱為原子變元。該變元稱為原子變元。 當(dāng)命題變元當(dāng)命題變元P P用一個(gè)特定命題去取代時(shí)，用一個(gè)特定命題去取代時(shí)， 才能確定才能確定P P的真值，的真值，這時(shí)

11、也稱對這時(shí)也稱對P P進(jìn)行指派。進(jìn)行指派。 例：例： 若若P P是是命題變元，命題變元， P P：北京是中國的首都。（指派北京是中國的首都。（指派P P為命題北京是中國的為命題北京是中國的首都）首都）離散數(shù)學(xué)命題命題小結(jié)小結(jié) 判斷一句話是否是命題的步驟：判斷一句話是否是命題的步驟： 1 1）看它是否是）看它是否是陳述句陳述句，如果是疑問句、感嘆句和祈使句則不，如果是疑問句、感嘆句和祈使句則不是是命題命題； 2 2）看它是否是）看它是否是悖論悖論，悖論不是命題，如，悖論不是命題，如“我正在說謊我正在說謊”； 3 3）看它真值是否唯一，如果不唯一，則不是）看它真值是否唯一，如果不唯一，則不是命題命

12、題。離散數(shù)學(xué)命題與聯(lián)結(jié)詞命題與聯(lián)結(jié)詞 命題命題 聯(lián)結(jié)詞聯(lián)結(jié)詞離散數(shù)學(xué)命題聯(lián)結(jié)詞命題聯(lián)結(jié)詞1. 否定：否定： 2. 合?。汉先。?3. 析?。何鋈。?4. 排斥析?。号懦馕鋈。?5. 條件（蘊(yùn)含）：條件（蘊(yùn)含）： 6. 雙條件：雙條件：離散數(shù)學(xué)否定否定 設(shè)設(shè)P為命題，為命題，P的否定也是一個(gè)命題，記作的否定也是一個(gè)命題，記作 P 當(dāng)當(dāng)P為為T時(shí)，時(shí)， P為為F 當(dāng)當(dāng)P為為F時(shí)，時(shí)， P為為T P與與P的關(guān)系如右表的關(guān)系如右表 例：設(shè)例：設(shè)P：上海是個(gè)大城市。：上海是個(gè)大城市。 則則P：上海不是一個(gè)大城市。：上海不是一個(gè)大城市。 或：上海是個(gè)不大的城市?；颍荷虾Ｊ莻€(gè)不大的城市。PPFTTF離散數(shù)學(xué)

13、合取合取 設(shè)設(shè)P、Q是命題，是命題，P和和Q的合取也是個(gè)命題，記作的合取也是個(gè)命題，記作PQ 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)P、Q同時(shí)為同時(shí)為T時(shí)，時(shí)，PQ為為T 其他情況下，其他情況下，PQ的真值都是的真值都是F 讀作讀作“P并且（與）并且（與）Q”PQPQFFFFTFTFFTTT離散數(shù)學(xué)合取示例合取示例(1) P: 我富有。我富有。 Q: 我快樂。我快樂。 PQ：我富有并且快樂。：我富有并且快樂。(2) P: 我們?nèi)ナ程贸燥?。我們?nèi)ナ程贸燥垺?Q: 教室里有三塊黑板。教室里有三塊黑板。 PQ: 我們?nèi)ナ程贸燥埐⑶医淌依镉腥龎K黑板。我們?nèi)ナ程贸燥埐⑶医淌依镉腥龎K黑板。 注：復(fù)合命題中的原子命題之間無需有一

14、般邏輯意義上的關(guān)注：復(fù)合命題中的原子命題之間無需有一般邏輯意義上的關(guān)聯(lián)，如聯(lián)，如(2)。離散數(shù)學(xué) 析取析取 設(shè)設(shè)P、Q是命題，則是命題，則P和和Q的析取也是個(gè)命題，記作的析取也是個(gè)命題，記作PQ。 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)P、Q同時(shí)為同時(shí)為F時(shí)，時(shí)，PQ為為F 其他情況下，其他情況下， PQ的真值都是的真值都是T 讀作讀作“P或或Q” （與自然語言中的（與自然語言中的“或或”不完全相同，是不完全相同，是兼并或）兼并或） PQPQFFFFTTTFTTTT離散數(shù)學(xué)析取例子析取例子 例：例：(1) P：猴子吃香蕉。：猴子吃香蕉。 Q：猴子吃橘子。：猴子吃橘子。 猴子吃香蕉或者吃橘子猴子吃香蕉或者吃橘子 ？

15、PQ (2) P：他明天早上吃蛋糕。：他明天早上吃蛋糕。 Q：他明天早上喝牛奶。：他明天早上喝牛奶。 PQ？ 他明天早上吃蛋糕或者喝牛奶他明天早上吃蛋糕或者喝牛奶 。 (3) P: 我明天早上我明天早上9點(diǎn)在家看書。點(diǎn)在家看書。 Q: 我明天早上我明天早上9點(diǎn)出去打球。點(diǎn)出去打球。 我明天早上我明天早上9點(diǎn)在家看書或出去打球點(diǎn)在家看書或出去打球 PQ？ 離散數(shù)學(xué) 排斥析取排斥析取 設(shè)設(shè)P、Q是命題，是命題，P和和Q的排斥析取也是個(gè)命題，記作的排斥析取也是個(gè)命題，記作 PQ 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)P和和Q的真值不相同時(shí)，的真值不相同時(shí)， PQ為為T， 其他情況下其他情況下,PQ的真值都是的真值都是F

16、讀作讀作“P或或Q” （排斥或）（排斥或）PQPQFFFFTTTFTTTFPQPQFFFFTTTFTTTT離散數(shù)學(xué)排斥析取示例排斥析取示例 指出下列命題中的指出下列命題中的“或或”是析取還是排斥析取是析取還是排斥析取今晚我去看演出或在家里看電視現(xiàn)場轉(zhuǎn)播。今晚我去看演出或在家里看電視現(xiàn)場轉(zhuǎn)播。他是一百米冠軍或跳高冠軍。他是一百米冠軍或跳高冠軍。派小王或小趙出差去上海。派小王或小趙出差去上海。派小王或小趙中的一個(gè)出差去上海。派小王或小趙中的一個(gè)出差去上海。1. 2、3為析取，為析取，1、 4為排斥析取為排斥析取PQPQFFFFTTTFTTTFPQPQFFFFTTTFTTTT離散數(shù)學(xué)條件條件/蘊(yùn)含蘊(yùn)

17、含 設(shè)設(shè)P、Q是命題，是命題，P對于對于Q的條件命題記為的條件命題記為PQ，或稱為，或稱為P蘊(yùn)含蘊(yùn)含Q 。 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)P的真值為的真值為T，Q的真值為的真值為F時(shí)，時(shí)，PQ的真值為的真值為F， 其他情況，其他情況， PQ的真值為的真值為T。 讀作讀作“如果（若）如果（若）P，則，則Q”、“Q是是P的必要條件的必要條件” 、“僅當(dāng)僅當(dāng)Q為真時(shí)，為真時(shí)，P為真為真” 稱稱P為前件，為前件，Q為后件。為后件。PQPQFFTFTTTFFTTT離散數(shù)學(xué)條件示例條件示例 P：天不下雨：天不下雨 Q：我去看電影：我去看電影 如果天不下雨，那么我去看電影：如果天不下雨，那么我去看電影： PQ 。 P：我

18、不到學(xué)校去。：我不到學(xué)校去。 Q：我生病。：我生病。 PQ：如果我不到學(xué)校去，那么我生病。：如果我不到學(xué)校去，那么我生病。 P：我去踢足球。：我去踢足球。 Q：我有時(shí)間。：我有時(shí)間。 僅當(dāng)我有時(shí)間，我去踢足球。僅當(dāng)我有時(shí)間，我去踢足球。PQ?FFTFTTTFFTTT離散數(shù)學(xué)雙條件雙條件 P、Q是命題，是命題，P和和Q的雙條件命題記作：的雙條件命題記作：P Q 當(dāng)當(dāng)P和和Q的真值相同時(shí)，的真值相同時(shí)，P Q的真值為的真值為T， 否則否則PQ的真值為的真值為F 翻譯為：翻譯為：“P當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)Q” 或者或者“若若P則則Q，否則，則，否則，則 Q”PQP QFFTFTFTFFTTT離散數(shù)學(xué)雙條件

19、示例雙條件示例 P：整數(shù)：整數(shù)a能被能被2整除整除 Q：a是偶數(shù)。是偶數(shù)。 當(dāng)且僅當(dāng)整數(shù)當(dāng)且僅當(dāng)整數(shù)a能被能被2整除，整除，a才是偶數(shù)：才是偶數(shù)：P Q 。 P：天不下雨：天不下雨 Q：我去看足球：我去看足球 P Q：如果天不下雨，我就去看足球，否則，我就不去看足球。：如果天不下雨，我就去看足球，否則，我就不去看足球。 P：224 Q：雪是白的：雪是白的 224當(dāng)且僅當(dāng)雪是白的：當(dāng)且僅當(dāng)雪是白的： P Q 注：復(fù)合命題中的原子命題之間無需有一般邏輯意義上的關(guān)聯(lián)。如此例中注：復(fù)合命題中的原子命題之間無需有一般邏輯意義上的關(guān)聯(lián)。如此例中P和和Q并無并無因果關(guān)系，因果關(guān)系，P Q仍是命題，其真值根據(jù)

20、聯(lián)結(jié)詞定義以及仍是命題，其真值根據(jù)聯(lián)結(jié)詞定義以及P和和Q的真值來確定。的真值來確定。離散數(shù)學(xué)綜合示例綜合示例設(shè)設(shè)P表示命題表示命題“天下雪天下雪”。Q表示命題表示命題“我去看電影我去看電影”。R表示命題表示命題“我有時(shí)間我有時(shí)間”。試以符號形式表示下列命題：試以符號形式表示下列命題：PPQQ R(QR) P天不下雪。天不下雪。如果天不下雪，那么我去看電如果天不下雪，那么我去看電影。影。我去看電影，僅當(dāng)我有時(shí)間。我去看電影，僅當(dāng)我有時(shí)間。如果我去看電影且我有時(shí)間，如果我去看電影且我有時(shí)間，那么天不下雪。那么天不下雪。離散數(shù)學(xué)聯(lián)結(jié)詞聯(lián)結(jié)詞小結(jié)小結(jié) 1. 1. 復(fù)合命題復(fù)合命題的真值只取決于構(gòu)成它們

21、的的真值只取決于構(gòu)成它們的原子命題原子命題的真值和命的真值和命題聯(lián)結(jié)符的定義，而與它們的內(nèi)容、含義無關(guān)，與聯(lián)結(jié)詞所題聯(lián)結(jié)符的定義，而與它們的內(nèi)容、含義無關(guān)，與聯(lián)結(jié)詞所連接的兩個(gè)連接的兩個(gè)原子命題原子命題之間是否有關(guān)系無關(guān)。之間是否有關(guān)系無關(guān)。 2. 2. ， 和和具有可交換性，而具有可交換性，而 ，沒有。沒有。離散數(shù)學(xué)聯(lián)結(jié)詞聯(lián)結(jié)詞小結(jié)小結(jié) 1.“1.“只要只要( (若、當(dāng)若、當(dāng))A)A成立，則成立，則B B成立成立” ：A AB B 2.“2.“僅當(dāng)僅當(dāng)A A成立時(shí)成立時(shí),B,B成立成立”和和“只有只有A A成立時(shí)，成立時(shí)，B B成立成立”： B BA A 3. 3. “A A成立成立, ,否則否則B B成立成立”：