離散數(shù)學(xué)(01)

1、1 “離散數(shù)學(xué)離散數(shù)學(xué)”是一門相對于是一門相對于“連續(xù)數(shù)學(xué)連續(xù)數(shù)學(xué)”而命名的數(shù)學(xué)分支，也叫而命名的數(shù)學(xué)分支，也叫“不連續(xù)的數(shù)不連續(xù)的數(shù)學(xué)學(xué)”“”“離散數(shù)學(xué)離散數(shù)學(xué)”主要研究一些不連續(xù)的數(shù)主要研究一些不連續(xù)的數(shù)學(xué)問題。學(xué)問題。 概率論與數(shù)理統(tǒng)計概率論與數(shù)理統(tǒng)計中的隨機(jī)變量就中的隨機(jī)變量就有離散型和連續(xù)型之區(qū)分；有離散型和連續(xù)型之區(qū)分； 離散數(shù)學(xué)離散數(shù)學(xué)是是現(xiàn)代數(shù)學(xué)現(xiàn)代數(shù)學(xué)的一個重要分支，上的一個重要分支，上世紀(jì)八十年代，計算機(jī)科學(xué)得到迅猛發(fā)展，世紀(jì)八十年代，計算機(jī)科學(xué)得到迅猛發(fā)展，2 迫切需要一門適合計算機(jī)科學(xué)的相關(guān)數(shù)學(xué)課迫切需要一門適合計算機(jī)科學(xué)的相關(guān)數(shù)學(xué)課程，離散數(shù)學(xué)由此建立，它是研究離散量

2、的程，離散數(shù)學(xué)由此建立，它是研究離散量的結(jié)構(gòu)及相互關(guān)系的學(xué)科。它充分描述了計算結(jié)構(gòu)及相互關(guān)系的學(xué)科。它充分描述了計算機(jī)科學(xué)離散性的特點，是計算機(jī)科學(xué)與技術(shù)機(jī)科學(xué)離散性的特點，是計算機(jī)科學(xué)與技術(shù)的理論基礎(chǔ)，所以又稱為計算機(jī)數(shù)學(xué)。是計的理論基礎(chǔ)，所以又稱為計算機(jī)數(shù)學(xué)。是計算機(jī)、軟件專業(yè)本科生必修的專業(yè)基礎(chǔ)課；算機(jī)、軟件專業(yè)本科生必修的專業(yè)基礎(chǔ)課；到碩士研究生段還將開設(shè)到碩士研究生段還將開設(shè)“組合數(shù)學(xué)組合數(shù)學(xué)”；到；到博士研究生段還將開設(shè)博士研究生段還將開設(shè)“計算數(shù)學(xué)計算數(shù)學(xué)”；3 “離散數(shù)學(xué)離散數(shù)學(xué)”一方面給后繼課，如一方面給后繼課，如“數(shù)據(jù)數(shù)據(jù)結(jié)構(gòu)結(jié)構(gòu)”、“編譯系統(tǒng)編譯系統(tǒng)”、“操作系統(tǒng)操作系統(tǒng)

3、”、“數(shù)據(jù)庫原理數(shù)據(jù)庫原理”等，提供必要的科學(xué)基礎(chǔ)；等，提供必要的科學(xué)基礎(chǔ)；另一方面，通過學(xué)習(xí)離散數(shù)學(xué)，培養(yǎng)和提高另一方面，通過學(xué)習(xí)離散數(shù)學(xué)，培養(yǎng)和提高了同學(xué)們的抽象思維和邏輯推理能力，為大了同學(xué)們的抽象思維和邏輯推理能力，為大家今后繼續(xù)學(xué)習(xí)和工作打下堅實的數(shù)學(xué)基礎(chǔ)。家今后繼續(xù)學(xué)習(xí)和工作打下堅實的數(shù)學(xué)基礎(chǔ)。 我們選用的這本教材是我們選用的這本教材是方世昌方世昌著著離散離散數(shù)學(xué)數(shù)學(xué)（第二版），西安電子科技大學(xué)（第二版），西安電子科技大學(xué)4 出版社出版。是高等學(xué)校工科電子類規(guī)劃教材出版社出版。是高等學(xué)校工科電子類規(guī)劃教材精選系列，本書是一本非常有特點的教材。精選系列，本書是一本非常有特點的教材。初

4、版出版十三年后，經(jīng)過全國眾多學(xué)校的應(yīng)初版出版十三年后，經(jīng)過全國眾多學(xué)校的應(yīng)用，于用，于1996年改進(jìn)后出第二版；本書力求把年改進(jìn)后出第二版；本書力求把握與計算機(jī)科學(xué)密切相關(guān)的問題，通過精選握與計算機(jī)科學(xué)密切相關(guān)的問題，通過精選的大量實例深入淺出地介紹了的大量實例深入淺出地介紹了數(shù)理邏輯、集數(shù)理邏輯、集合論、二元關(guān)系、函數(shù)、代數(shù)系統(tǒng)、格與布合論、二元關(guān)系、函數(shù)、代數(shù)系統(tǒng)、格與布爾代數(shù)爾代數(shù)* 、圖論、圖論等（我們省掉其中的等（我們省掉其中的“無限集無限集合合”一章）一章）5 與與計算機(jī)科學(xué)技術(shù)密切相關(guān)的課題，既著重于計算機(jī)科學(xué)技術(shù)密切相關(guān)的課題，既著重于各部分內(nèi)容之間的緊密聯(lián)系，又深入探討各部各

5、部分內(nèi)容之間的緊密聯(lián)系，又深入探討各部分內(nèi)容的概念、理論、算法和實際應(yīng)用。因而分內(nèi)容的概念、理論、算法和實際應(yīng)用。因而本書既有深度，又有廣度，相信學(xué)了本書，即本書既有深度，又有廣度，相信學(xué)了本書，即能培養(yǎng)思維能力，又能培養(yǎng)理論聯(lián)系實際的扎能培養(yǎng)思維能力，又能培養(yǎng)理論聯(lián)系實際的扎實功底實功底 。各章內(nèi)容大致如下：。各章內(nèi)容大致如下： 第一章第一章 數(shù)理邏輯數(shù)理邏輯 將形式邏輯符號化后進(jìn)行邏輯推理，來將形式邏輯符號化后進(jìn)行邏輯推理，來6證明命題的真值，對命題公式運算。證明命題的真值，對命題公式運算。 第二章第二章 集合集合 研究集合基本概念、集合之間的運算關(guān)研究集合基本概念、集合之間的運算關(guān)系以及

6、特殊集合。系以及特殊集合。 第三章第三章 二元關(guān)系二元關(guān)系 是研究是研究“關(guān)系關(guān)系”的運算、的運算、 復(fù)合、劃分，以復(fù)合、劃分，以及及“關(guān)系關(guān)系”上的閉包運算等問題。本章內(nèi)容上的閉包運算等問題。本章內(nèi)容占全書很大比例。占全書很大比例。7第四章第四章 函數(shù)函數(shù) 本章內(nèi)容我們已經(jīng)是第三次學(xué)習(xí)，重點放本章內(nèi)容我們已經(jīng)是第三次學(xué)習(xí)，重點放在函數(shù)的映射問題上。在函數(shù)的映射問題上。第六章第六章 代數(shù)代數(shù) 是研究是研究“代數(shù)系統(tǒng)代數(shù)系統(tǒng)”中元素與運算構(gòu)成群、中元素與運算構(gòu)成群、半群、環(huán)與域的有關(guān)問題。完全不同于中學(xué)、半群、環(huán)與域的有關(guān)問題。完全不同于中學(xué)、大一學(xué)習(xí)過的代數(shù)問題大一學(xué)習(xí)過的代數(shù)問題8第七章第七

7、章 格與布爾代數(shù)格與布爾代數(shù)*(在時間充足時學(xué)習(xí)在時間充足時學(xué)習(xí)) 是研究是研究“代數(shù)系統(tǒng)代數(shù)系統(tǒng)”中中“格格”以及以及“特殊特殊格格” 的有關(guān)問題。是對的有關(guān)問題。是對“代數(shù)系統(tǒng)代數(shù)系統(tǒng)”的進(jìn)一的進(jìn)一步研究。步研究。第八章第八章 圖論圖論 是研究平面圖形中是研究平面圖形中“結(jié)點結(jié)點”與與“連線連線”之之間的關(guān)系，路徑的優(yōu)化、網(wǎng)絡(luò)、匹配等問題，間的關(guān)系，路徑的優(yōu)化、網(wǎng)絡(luò)、匹配等問題，9 離散數(shù)學(xué)離散數(shù)學(xué)課每周上課兩次，課每周上課兩次，4學(xué)時，安學(xué)時，安排排15周，共周，共60學(xué)時。學(xué)時。 考核方式：期末筆試占考核方式：期末筆試占70%，平時作業(yè)占，平時作業(yè)占30%， 每人準(zhǔn)備兩個作業(yè)本（或者用

8、合頁紙），寫每人準(zhǔn)備兩個作業(yè)本（或者用合頁紙），寫清班級、學(xué)號、姓名。每星期交一次作業(yè)，由清班級、學(xué)號、姓名。每星期交一次作業(yè)，由班長統(tǒng)一收齊交到四樓班長統(tǒng)一收齊交到四樓“專業(yè)教研室專業(yè)教研室”。交新。交新作業(yè)時領(lǐng)回批改過的作業(yè)，按學(xué)校規(guī)定每次作作業(yè)時領(lǐng)回批改過的作業(yè)，按學(xué)校規(guī)定每次作業(yè)將登記，批改三分之一。業(yè)將登記，批改三分之一。10 第一章第一章 數(shù)理邏輯數(shù)理邏輯1.1 命命 題題 邏輯學(xué)分為：邏輯學(xué)分為：“形式邏輯形式邏輯”和和“數(shù)理邏輯數(shù)理邏輯”兩個部分，他們的最大區(qū)別在于，兩個部分，他們的最大區(qū)別在于， “形式邏輯形式邏輯”允許有二意性而允許有二意性而“數(shù)理邏輯數(shù)理邏輯”決不允許。決

9、不允許?！皵?shù)數(shù)理邏輯理邏輯” 就是將就是將 “形式邏輯形式邏輯”數(shù)學(xué)符號化；數(shù)學(xué)符號化； 例如：陳述句例如：陳述句“你吃飽了你吃飽了”在在“形式邏輯形式邏輯”中中可以理解為：可以理解為：11（1）你的確是吃的過飽了）你的確是吃的過飽了（2）你這個人的行為很無聊，如同吃飽飯撐的。）你這個人的行為很無聊，如同吃飽飯撐的。 這就是這就是“形式邏輯形式邏輯”的二意性。一個陳述句的二意性。一個陳述句可能有兩個意識?？赡苡袃蓚€意識。 命題是邏輯學(xué)中的基本單位；陳述語句是邏命題是邏輯學(xué)中的基本單位；陳述語句是邏輯學(xué)的形式語言，斷言是一個陳述語句。輯學(xué)的形式語言，斷言是一個陳述語句。12 1.1.1 命題命題

10、 在特定的范圍、時間、和空間內(nèi)具有唯在特定的范圍、時間、和空間內(nèi)具有唯一確定的真假性。這樣的陳述語句就是一確定的真假性。這樣的陳述語句就是命題命題； 一個命題是一個或真或假而不一個命題是一個或真或假而不能兩者都是的能兩者都是的斷言斷言。如果命題是真。如果命題是真, 我們說它的我們說它的真值真值為真，為真，如果命題是如果命題是假假, 我們說它的我們說它的真值真值是假。是假。13 例例 1 下述都是命題下述都是命題: (a) 今天下雪今天下雪; (c) 2 是偶數(shù)而是偶數(shù)而 3 是奇數(shù)是奇數(shù); (b) 3+3=6; (d) 陳勝起義那天陳勝起義那天, 杭州下雨杭州下雨;(e) 2008年人類將登上

11、火星。年人類將登上火星。 以上命題以上命題, (a)的真值取決于今天的天氣的真值取決于今天的天氣, (b)和和(c)是真是真, (d)已無法查明它的真值已無法查明它的真值, 但它但它是或真或假是或真或假, 將它歸屬于命題。將它歸屬于命題。 (e)目前尚未目前尚未確定其真假確定其真假, 但它是有真值的但它是有真值的, 應(yīng)歸屬于命題。應(yīng)歸屬于命題。14例例 2 下述都不是命題下述都不是命題:(a) x+y4。 (c) 真好啊真好啊! (b) x=3。 (d) 你去哪里你去哪里? (a)和和(b)是斷言，不是命題是斷言，不是命題, 因為它的真值因為它的真值取決于取決于x和和y的值。的值。 (c)和和

12、(d)都不都不是斷言是斷言, 所所以不是命題。以不是命題。自然語句中有自然語句中有陳述句陳述句、祈使句祈使句、疑問句疑問句、和、和感嘆句感嘆句等，其中能判斷對錯的只等，其中能判斷對錯的只有有陳述句陳述句。15例例 3 一個人說一個人說:“我正在說謊我正在說謊”。 他是在說謊還是在說真話呢他是在說謊還是在說真話呢? 如果他講真如果他講真話話, 那么他所說的是真那么他所說的是真, 也就是他在說謊。也就是他在說謊。 我我們得出結(jié)論如果他講真話們得出結(jié)論如果他講真話, 那么他是在說謊。那么他是在說謊。 另一方面另一方面, 如果他是說謊如果他是說謊, 那么他說的是假那么他說的是假; 因為他承認(rèn)他是說謊因

13、為他承認(rèn)他是說謊, 所以他實際上是在說真所以他實際上是在說真話話, 我們得出結(jié)論如果他是說謊我們得出結(jié)論如果他是說謊, 那么他是講那么他是講真話。真話。16 從以上分析從以上分析, 我們得出他必須既非說謊也我們得出他必須既非說謊也不是講真話。這樣不是講真話。這樣, 斷言斷言“我正在說謊我正在說謊”事實事實上不能指定它的上不能指定它的真假真假, 所以不是命題。所以不是命題。 這種這種斷言叫斷言叫悖論悖論。例：學(xué)生甲在教師乙處學(xué)習(xí)法律，約定一年學(xué)例：學(xué)生甲在教師乙處學(xué)習(xí)法律，約定一年學(xué)成甲支付學(xué)費成甲支付學(xué)費2000圓，同時規(guī)定在學(xué)生甲和圓，同時規(guī)定在學(xué)生甲和教師乙在同一場官司中，師生分別作為控辯

14、教師乙在同一場官司中，師生分別作為控辯雙方，若學(xué)生方獲勝為學(xué)成的標(biāo)準(zhǔn)；雙方，若學(xué)生方獲勝為學(xué)成的標(biāo)準(zhǔn)；17 學(xué)業(yè)結(jié)束后學(xué)生拒絕支付學(xué)費，他認(rèn)為：學(xué)業(yè)結(jié)束后學(xué)生拒絕支付學(xué)費，他認(rèn)為： 教師您可以通過打官司解決，如果教師教師您可以通過打官司解決，如果教師官司打輸了，我自然不支付學(xué)費，如果教師官司打輸了，我自然不支付學(xué)費，如果教師官司打嬴了，說明我還沒有學(xué)成，根據(jù)先前官司打嬴了，說明我還沒有學(xué)成，根據(jù)先前的約定，我仍然可以不支付學(xué)費。的約定，我仍然可以不支付學(xué)費。 這也是個悖論的例子，無論教師乙的怎樣這也是個悖論的例子，無論教師乙的怎樣努力，在簽合同時就被學(xué)生甲算計進(jìn)去了。努力，在簽合同時就被學(xué)生甲

15、算計進(jìn)去了。18 若一個命題已不能分解成更簡單的命題若一個命題已不能分解成更簡單的命題, 則這個命題叫則這個命題叫原子命題原子命題或或本原命題本原命題。 例例 1 中中(a) , (b) , (d) , (e)都是本原命題都是本原命題, 但但(c)不不是是, 因為它可寫成因為它可寫成“2 是偶數(shù)是偶數(shù)”和和“3 是奇數(shù)是奇數(shù)”兩個命題。兩個命題。 命題和本原命題常用大寫字母命題和本原命題常用大寫字母P , Q , R :表示。表示。 如用如用P表示表示“4 是質(zhì)數(shù)是質(zhì)數(shù)”, 則記為則記為 ： P: 4 是質(zhì)數(shù)。是質(zhì)數(shù)。 19第一章第一章 數(shù)理邏輯數(shù)理邏輯 1.2 命題聯(lián)結(jié)詞命題聯(lián)結(jié)詞 1.1.

16、2 命題聯(lián)結(jié)詞命題聯(lián)結(jié)詞 命題和原子命題?？赏ㄟ^一些聯(lián)結(jié)詞構(gòu)命題和原子命題常可通過一些聯(lián)結(jié)詞構(gòu)成新命題成新命題, 這種新命題叫這種新命題叫復(fù)合命題復(fù)合命題。例如。例如 ： P: 明天下雪明天下雪, Q: 明天下雨明天下雨是兩個命題是兩個命題, 利用聯(lián)結(jié)詞利用聯(lián)結(jié)詞“不不”, “并且并且”, “或或”等可分別構(gòu)成新命題等可分別構(gòu)成新命題:20 “明天不下雪明天不下雪”; “明天下雪并且明天下雨明天下雪并且明天下雨”; “明天下雪或者明天下雨明天下雪或者明天下雨”等。等。 即即 ：“非非P”; ;“P并且并且Q”; “P或或Q”等。等。21 在代數(shù)式在代數(shù)式x+3 中中, “x “, “3” 叫運

17、算對象叫運算對象,代代數(shù)中的運算對象分有數(shù)中的運算對象分有“變量變量(x)”和和“常量常量(3)”；命題演算同樣對原子命題有命題演算同樣對原子命題有“變元變元(P)”和和“常元常元(真、假真、假)”之分；之分； “+”叫運算符叫運算符, x+3 表示運算結(jié)果。在命表示運算結(jié)果。在命題演算中題演算中, 也用同樣術(shù)語。聯(lián)結(jié)詞就是命題演也用同樣術(shù)語。聯(lián)結(jié)詞就是命題演算中的運算符算中的運算符, 叫叫邏輯運算符邏輯運算符或叫或叫邏輯聯(lián)結(jié)詞邏輯聯(lián)結(jié)詞。 常用的有以下常用的有以下 5 個。個。22 1.否定詞否定詞 設(shè)設(shè)P表示命題表示命題, 那么那么“P不真不真”是另一命題是另一命題, 表示為表示為 P,

18、叫做叫做P的的否定否定, 讀做讀做“非非P”。 從排從排中律知中律知: 如果如果P是假是假, 則則 P是真是真, 反之亦然。反之亦然。 所以所以否定詞否定詞 可以如下表所示定義?？梢匀缦卤硭径x。歸納為：歸納為：非真非真即假即假，非假即真非假即真。P P假假真真真真假假P P011023 這張表叫這張表叫真值表真值表, 定義運算符的真值表定義運算符的真值表, 指指明如何用運算對象的真值明如何用運算對象的真值, 來決定一個應(yīng)用運來決定一個應(yīng)用運算符的命題的真值。算符的命題的真值。 真值表的左邊列出運算真值表的左邊列出運算對象的真值的所有可能組合對象的真值的所有可能組合, 結(jié)果命題的真值結(jié)果命題

19、的真值列在最右邊的一列。為了便于閱讀列在最右邊的一列。為了便于閱讀, 我們通常我們通常用符號用符號T(true)或或 1 代表代表真真, 符號符號F(false)或或 0 代表代表假假。 一般在一般在公式中采用公式中采用T T和和F F, 在在真值表真值表中采用中采用 1 1 和和 0 0。24 例例 4(a) P: 4 是質(zhì)數(shù)。是質(zhì)數(shù)。P: 4 不是質(zhì)數(shù)。不是質(zhì)數(shù)。 或或 4 是質(zhì)數(shù)是質(zhì)數(shù), 不是這樣。不是這樣。 (b) Q: 這些都是男同學(xué)。這些都是男同學(xué)。 Q: 這些不都是男同學(xué)。這些不都是男同學(xué)。 (翻譯成翻譯成“這些都不是男同學(xué)這些都不是男同學(xué)”是錯的。是錯的。 ) 原命題為原命題為

20、p，非命題，非命題p 一般的理解為：一般的理解為： 并非并非p；即在命題前加；即在命題前加“并非并非”二二字。字。25例如：例如： p：上海是一個處處都清潔的城市；：上海是一個處處都清潔的城市； p：并非上海是一個處處都清潔的城市；：并非上海是一個處處都清潔的城市；而不能寫成：上海是一個處處都不清潔的城市；而不能寫成：上海是一個處處都不清潔的城市；2.合取詞合取詞 如果如果P和和Q是命題是命題, 那么那么“P并且并且Q”也是一也是一命題命題, 記為記為PQ, 稱為稱為P和和Q的的合取合取, 讀做讀做“P與與Q”或或“P并且并且Q”。 運算符運算符定義如下表所示定義如下表所示: 從真值表可知從真

21、值表可知PQ是真當(dāng)且僅當(dāng)是真當(dāng)且僅當(dāng)P和和Q俱真。俱真。26歸納為：歸納為： p，q同真時同真時pq為真，其余為假為真，其余為假。 類似集合運算中的：類似集合運算中的： “交交 ，”P QP Q0 00 11 01 10001例例5 P: 王華的成績王華的成績很好很好, Q: 王華的品德王華的品德很好。很好。 PQ: 王華的成績王華的成績很好并且品德很好。很好并且品德很好。27 3. 析取詞析取詞 如果如果P和和Q是命題是命題, 則則“P或或Q”也是一命題也是一命題, 記記作作PQ, 稱為稱為P和和Q的的析取析取, 讀做讀做“P或或Q”。運。運算符算符定義如右表所示。從真值表可知定義如右表所示

22、。從真值表可知PQ為真為真, 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)P或或Q至少有一為真。至少有一為真。歸納為：歸納為： p，q同假時同假時 p q 為假，其余為真為假，其余為真。 看的出：合取與析取有對偶的關(guān)系。看的出：合取與析取有對偶的關(guān)系。28析取類似集合運算中的：析取類似集合運算中的： “并并 ，”P QP Q0 00 11 01 10111例例 6 (a) P: 今晚今晚我寫字我寫字, Q: 今晚今晚我看書。我看書。 PQ: 今晚今晚我寫字或看書我寫字或看書 29 (b) P: 今年是閏年今年是閏年; Q: 今年她生孩子。今年她生孩子。 PQ: 今年是閏年或者今年她生孩子。今年是閏年或者今年她生孩子。 邏

23、輯運算符可以將兩個無關(guān)的命題連接成邏輯運算符可以將兩個無關(guān)的命題連接成一新命題。一新命題。 “或或”字常見的含義有兩種字常見的含義有兩種: 一種是一種是“可兼或可兼或”, 如上例中的或如上例中的或, 它不排除今晚既它不排除今晚既看書又寫字這種情況。看書又寫字這種情況。 30 一種是一種是“排斥或排斥或”, 例如例如“人固有一死人固有一死, 或或重于泰山重于泰山, 或輕于鴻毛或輕于鴻毛”中的中的“或或”, 它表示非它表示非此即彼此即彼, 不可兼得。不可兼得。 運算符運算符表示可兼或表示可兼或, 排斥排斥或以后用另一符號表達(dá)?；蛞院笥昧硪环柋磉_(dá)。 聯(lián)結(jié)詞聯(lián)結(jié)詞是自然語言中的是自然語言中的“或或”

24、、“或者或者”的邏輯抽象，而在自然語言中，的邏輯抽象，而在自然語言中，“或或”是多義是多義的，可列表如下：的，可列表如下：31“可兼或可兼或”與與“排斥或排斥或” 的聯(lián)系與區(qū)別的聯(lián)系與區(qū)別 或的或的 含義含義 例如例如 說明說明聯(lián)聯(lián)結(jié)結(jié)詞詞可可兼兼或或可可兼兼容容今天晚會上我或者唱歌或者今天晚會上我或者唱歌或者跳舞，也可以邊唱邊跳。跳舞，也可以邊唱邊跳。二者至少有一個發(fā)二者至少有一個發(fā)生，不排斥二者都生，不排斥二者都發(fā)生的情況發(fā)生的情況排排斥斥或或 不不可可兼兼容容他下午他下午2：00上街或在教室上街或在教室聽課。聽課。非此即彼，不可兼非此即彼，不可兼的的 非聯(lián)非聯(lián) 結(jié)詞結(jié)詞去主樓需要去主樓需

25、要6分鐘或分鐘或8分鐘分鐘近似數(shù)近似數(shù)“6至至8分分鐘鐘”32 4. 蘊涵詞蘊涵詞(涵常簡寫作含涵常簡寫作含) 如果如果P和和Q是命題是命題, 那么那么“P蘊含蘊含Q”也是命題也是命題, 記為記為PQ, 稱為稱為蘊含式蘊含式, 讀做讀做“P蘊含蘊含Q”或或“如如果果P, 那么那么Q”，是典型的，是典型的“因果關(guān)系因果關(guān)系”。 運算對象運算對象P叫做叫做前提前提 , 假設(shè)假設(shè)或或前件前件, 而而Q叫做叫做結(jié)論結(jié)論或或后件后件。邏輯推理經(jīng)常用到這種。邏輯推理經(jīng)常用到這種“因果關(guān)因果關(guān)系系”；運算符定義如下表所示。命題；運算符定義如下表所示。命題PQ是假是假, 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)P是真而是真而Q是假。

26、是假。33 歸納為：歸納為：條件為真，結(jié)論為假時條件為真，結(jié)論為假時pq pq 為假，其余為真為假，其余為真。 我們經(jīng)常把我們經(jīng)常把“”（條件命題）簡稱為：（條件命題）簡稱為： 單條件命題單條件命題。以區(qū)別后面的雙條件命題。以區(qū)別后面的雙條件命題。P QP Q0 00 11 01 1110134例例 7 (a) P: 天不下雨天不下雨, Q: 草木枯黃。草木枯黃。 PQ: 如果天不下雨如果天不下雨, 那么草木枯黃。那么草木枯黃。 (b) R: G是正方形是正方形, S: G的四邊相等。的四邊相等。 RS: 如果如果G是正方形是正方形, 那么那么G的四邊相等。的四邊相等。 (c) W: 桔子是紫

27、色的桔子是紫色的, V: 大地是不平的大地是不平的WV: 如果桔子是紫色的如果桔子是紫色的, 那么大地是不那么大地是不平的。平的。35 在日常生活中用蘊含式來斷言前提和結(jié)論在日常生活中用蘊含式來斷言前提和結(jié)論之間的因果或?qū)嵸|(zhì)關(guān)系之間的因果或?qū)嵸|(zhì)關(guān)系, 如上例如上例(a)和和(b), 這樣的這樣的蘊含式叫蘊含式叫形式蘊含形式蘊含, 然而然而, 在命題演算中在命題演算中, 一個蘊一個蘊含式的前提和結(jié)論并不需要有因果和實質(zhì)聯(lián)系含式的前提和結(jié)論并不需要有因果和實質(zhì)聯(lián)系, 這樣的蘊含式叫這樣的蘊含式叫實質(zhì)蘊含實質(zhì)蘊含, 如上例如上例(c)中中, 桔子的桔子的顏色和大地的外形之間沒有因果和實質(zhì)關(guān)系存顏色和

28、大地的外形之間沒有因果和實質(zhì)關(guān)系存在在, 但蘊含式但蘊含式WV是真是真, 36 因為前提是假而結(jié)論是真因為前提是假而結(jié)論是真,這就是我們這就是我們常說的常說的”善意推斷善意推斷”。即：條件為假時，即：條件為假時，條件命題永真。條件命題永真。例如：如果太陽從西邊出來，那么每個星期例如：如果太陽從西邊出來，那么每個星期我們就休息我們就休息5天。天。 這個命題的條件是假的，無論后面的結(jié)這個命題的條件是假的，無論后面的結(jié)論是什么，整個條件命題是真的。論是什么，整個條件命題是真的。37 蘊含式蘊含式PQ可以用多種方式陳述可以用多種方式陳述:“若若P, 則則Q” “P是是Q的充分條件的充分條件” “Q是是

29、P的必要條件的必要條件” “Q每當(dāng)每當(dāng)P” ; “P僅當(dāng)僅當(dāng)Q”等。等。如上例如上例(b)中的中的RS可陳述為可陳述為“G是正方形的是正方形的必要條件是它必要條件是它的四邊相等的四邊相等”。38 給定原命題給定原命題PQ, 我們把：我們把： QP, 叫做命題叫做命題PQ的的逆命題逆命題 P Q, 叫做命題叫做命題PQ的的否命題否命題 Q P ， 叫做命題叫做命題PQ的的逆否命題逆否命題. 其中其中原命題原命題與與逆否命題逆否命題，逆命題逆命題與與否命題否命題是同是同真值的。真值的。39 例如：例如：P:如果天下雨，如果天下雨，Q:那么地上濕。那么地上濕。 P Q （真）（真）逆命題：如果地上濕

30、，那么天下雨。逆命題：如果地上濕，那么天下雨。否命題：如果天不下雨，那么地上不濕。否命題：如果天不下雨，那么地上不濕。 這樣就不一定為真，也可能是灑水車剛這樣就不一定為真，也可能是灑水車剛剛過去灑過水了。但逆否命題：剛過去灑過水了。但逆否命題： 如果地上不濕，那么天沒下雨。是真的；如果地上不濕，那么天沒下雨。是真的；40 5. 等值詞等值詞 如果如果P和和Q是命題是命題, 那么那么“P等值于等值于Q”也也是命題是命題, 記為記為P Q, 稱為稱為等值式等值式, 讀做讀做“P等值于等值于Q”。 運算符運算符 定義如下表所示。定義如下表所示。歸納為：歸納為： p、q同真、假時同真、假時 p q 為

31、真，其余為真，其余為假。為假。P QP Q0 00 11 01 1100141 把蘊含式和等值式的真值表加以比較把蘊含式和等值式的真值表加以比較, 易知如果易知如果P Q是真是真, 那么那么PQ和和QP俱真俱真; 反之如果反之如果PQ和和QP俱真俱真, 那么那么P Q是真。是真。由于這些理由由于這些理由, P Q也讀做也讀做“P是是Q的充要的充要條件條件”或或“P當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)Q”。 如如p和和q是命題，復(fù)合命題是命題，復(fù)合命題p當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)q有有時簡稱為時簡稱為雙條件命題雙條件命題，且表為，且表為p q。42 從以上從以上 5 個定義可看出個定義可看出, 聯(lián)結(jié)詞之意義由聯(lián)結(jié)詞之意義由其

32、真值表唯一確定其真值表唯一確定, 而不由命題的含義確定。而不由命題的含義確定。 使用以上使用以上 5 個聯(lián)結(jié)詞個聯(lián)結(jié)詞, 可將一些語句翻譯成可將一些語句翻譯成邏輯式。邏輯式。 翻譯時為了減少圓括號翻譯時為了減少圓括號(一般不用其一般不用其它括號它括號)的使用的使用, 我們作以下約定，運算符結(jié)合我們作以下約定，運算符結(jié)合力的強弱順序為力的強弱順序為 ; ， , , , （ 同于四則運算中的同于四則運算中的次序）次序） 43 凡符合此順序的凡符合此順序的, 括號均可省去。相同的括號均可省去。相同的運算符運算符, 按從左至右次序計算時按從左至右次序計算時, 括號可省去括號可省去最外層的圓括號可以省去

33、。最外層的圓括號可以省去。例如例如: ( (P Q)R)(RP)Q)可寫成可寫成 ： (P QR)RPQ 但有時為了看起來清楚醒目但有時為了看起來清楚醒目, 也可以保留也可以保留某些原可省去的括號。某些原可省去的括號。44 例例 8 (a) 設(shè)設(shè)P表示表示“他有理論知識他有理論知識”, Q表表示示“他有實踐經(jīng)驗他有實踐經(jīng)驗” 則則“他既有理論知識他既有理論知識又有實踐經(jīng)驗又有實踐經(jīng)驗”可譯為可譯為: PQ。(b) 設(shè)設(shè)P: 明天下雨明天下雨, Q: 明天下雪明天下雪, R: 我去學(xué)校。我去學(xué)校。 則：則： (i) “如果明天不是雨夾雪則我去學(xué)校如果明天不是雨夾雪則我去學(xué)?！笨蓪懣蓪懗沙?; (

34、PQ)R ;45(ii) “如果明天不下雨并且不下雪則我去學(xué)校如果明天不下雨并且不下雪則我去學(xué)?！笨蓪懗煽蓪懗?; P QR ; (iii) “如果明天下雨或下雪則我不去學(xué)校如果明天下雨或下雪則我不去學(xué)校”可寫可寫成成 ; PQ R ;iv) “明天明天, 我將雨雪無阻一定去學(xué)校我將雨雪無阻一定去學(xué)?！笨蓪懗煽蓪懗?; (PQR)(PQR)(PQR) (PQR)46 (v) “當(dāng)且僅當(dāng)明天不下雪并且不下雨時我當(dāng)且僅當(dāng)明天不下雪并且不下雨時我才去學(xué)校才去學(xué)?！笨蓪懗煽蓪懗?; P Q R ; (c) 用邏輯符表達(dá)用邏輯符表達(dá)“說小學(xué)生編不了程序說小學(xué)生編不了程序, 或說小學(xué)生用不了個人計算機(jī)或說

35、小學(xué)生用不了個人計算機(jī), 那是不對的那是不對的”。 設(shè)設(shè)P: 小學(xué)生會編程序小學(xué)生會編程序, Q: 小學(xué)生會用個人小學(xué)生會用個人計算機(jī)。計算機(jī)。 則上句可譯為：則上句可譯為： (P Q) 47 (d) 用邏輯符表達(dá)用邏輯符表達(dá)“若不是他生病或出差若不是他生病或出差了了, 我是不會同意我是不會同意 他不參加學(xué)習(xí)他不參加學(xué)習(xí)”。 設(shè)設(shè)P: 他生病了他生病了, Q: 他出差了他出差了, R: 我同意我同意他不參加學(xué)習(xí)他不參加學(xué)習(xí), 則上句可譯為則上句可譯為 (PQ) R 或或 PQ R即：我同意他不參加學(xué)習(xí)的充要條件的他生即：我同意他不參加學(xué)習(xí)的充要條件的他生病了或者出差了病了或者出差了48 翻譯時

36、要按邏輯關(guān)系翻譯翻譯時要按邏輯關(guān)系翻譯, 而不能憑字而不能憑字面翻。面翻。 例如例如, 設(shè)設(shè)P: 林芬做作業(yè)林芬做作業(yè), Q: 林芳做林芳做作業(yè)作業(yè), 則則“林芬和林芳同在做作業(yè)林芬和林芳同在做作業(yè)”可譯為可譯為PQ, 但但“林芬和林芳是姐妹林芬和林芳是姐妹”就不能翻就不能翻釋成兩個命題的合取釋成兩個命題的合取, 它是一個原子命題。它是一個原子命題。 1.1.3 命題變元和命題公式命題變元和命題公式 通常通常, 如果如果P代表真值未指定的任意命題代表真值未指定的任意命題, 49 我們就稱我們就稱P為為命題變元命題變元; 如果如果P代表一個真代表一個真 值已指定的命題值已指定的命題, 我們就稱我

37、們就稱P為為命題常元命題常元。 但由于在命題演算中并不關(guān)心具體命題但由于在命題演算中并不關(guān)心具體命題的涵義的涵義, 只關(guān)心其真假值。只關(guān)心其真假值。 因此因此, 我們可以我們可以形式地定義它們。形式地定義它們。 以以“真真” , “假假”為其變域的變元為其變域的變元, 稱為稱為命命題變元題變元; T(1)和和F(0)稱為稱為命題常元命題常元。原子公式原子公式50單個原子公式是命題公式。單個原子公式是命題公式。 這種定義叫這種定義叫, 也叫也叫。由。由這種定義產(chǎn)生的公式也叫這種定義產(chǎn)生的公式也叫51 一個命題公式（合式公式一個命題公式（合式公式 ）如同一個函）如同一個函數(shù)表達(dá)式，由命題變元和命題常元取代函數(shù)數(shù)表達(dá)式，由命題變元和命題常元取代函數(shù)式中的變量和常量，由五個命題聯(lián)結(jié)詞取代式中的變量和常量，由五個命題聯(lián)結(jié)詞取代函數(shù)式中的各種運算。函數(shù)式中的各種運算。 命題公式的真假值一般不能確定。當(dāng)命命題公式的真假值一般不能確定。當(dāng)命題公式中所有命題變元代以真值時，命題公題公式中所有命題變元代以真值時，命題公式就確定了