【學(xué)習(xí)】第一次課(緒論與數(shù)理邏輯初步)

1、1/26/2022整理課件1離散數(shù)學(xué)離散數(shù)學(xué) Discrete Mathematics30課時，課時，15次課次課主講：喬洪志主講：喬洪志1/26/2022整理課件2離散數(shù)學(xué)離散數(shù)學(xué)是指計算機(jī)科學(xué)中所使用的各種離是指計算機(jī)科學(xué)中所使用的各種離散的數(shù)學(xué)結(jié)構(gòu)。散的數(shù)學(xué)結(jié)構(gòu)。結(jié)構(gòu)結(jié)構(gòu)是指系統(tǒng)中的各個組成部分有機(jī)地搭配是指系統(tǒng)中的各個組成部分有機(jī)地搭配和排列。和排列。任何任何事物事物都有自己的結(jié)構(gòu)。都有自己的結(jié)構(gòu)。每一門每一門學(xué)科學(xué)科也有自己的結(jié)構(gòu)。也有自己的結(jié)構(gòu)。1/26/2022整理課件31. 人體的結(jié)構(gòu) 人體由大腦、五官、四肢、心、肝、肺等器官所組成。人體由大腦、五官、四肢、心、肝、肺等器官所組

2、成。 基本元素是各種細(xì)胞?；驹厥歉鞣N細(xì)胞。2. 房屋的結(jié)構(gòu) 房屋由地基、墻、門、窗、地板、房頂?shù)冉ㄖ锼M成。房屋由地基、墻、門、窗、地板、房頂?shù)冉ㄖ锼M成。 基本材料是磚、瓦、鋼筋、水泥、石灰等。基本材料是磚、瓦、鋼筋、水泥、石灰等。3. 學(xué)校的結(jié)構(gòu) 學(xué)校由若干院、系、所、處、科室、班級等單位所組成。學(xué)校由若干院、系、所、處、科室、班級等單位所組成。 基本成員是教師、學(xué)生、管理人員、實驗人員等?；境蓡T是教師、學(xué)生、管理人員、實驗人員等。4. 計算機(jī)的結(jié)構(gòu) 計算機(jī)由主板、計算機(jī)由主板、CPU、內(nèi)存條、硬盤、軟驅(qū)、電源、機(jī)、內(nèi)存條、硬盤、軟驅(qū)、電源、機(jī)箱、顯示器、鍵盤、鼠標(biāo)等部件所組成。

3、箱、顯示器、鍵盤、鼠標(biāo)等部件所組成。 基本成員是各種超大規(guī)模集成電路芯片?；境蓡T是各種超大規(guī)模集成電路芯片。1/26/2022整理課件4化學(xué)的結(jié)構(gòu) 化學(xué)主要由無機(jī)化學(xué)和有機(jī)化學(xué)所組成。化學(xué)主要由無機(jī)化學(xué)和有機(jī)化學(xué)所組成。 基本成員是各種化學(xué)元素?；境蓡T是各種化學(xué)元素。物理的結(jié)構(gòu) 物理主要由力學(xué)、電學(xué)、光學(xué)、熱學(xué)所組成。物理主要由力學(xué)、電學(xué)、光學(xué)、熱學(xué)所組成。 基本成員是各種場?；境蓡T是各種場。數(shù)學(xué)的結(jié)構(gòu) 數(shù)學(xué)主要由連續(xù)數(shù)學(xué)和離散數(shù)學(xué)所組成。數(shù)學(xué)主要由連續(xù)數(shù)學(xué)和離散數(shù)學(xué)所組成。 基本成員是各種集合的元素?；境蓡T是各種集合的元素。1/26/2022整理課件51. 1. 離散數(shù)學(xué)是離散數(shù)學(xué)是

4、離散的數(shù)學(xué)結(jié)構(gòu)離散的數(shù)學(xué)結(jié)構(gòu)的縮寫。的縮寫。2. 2. 離散數(shù)學(xué)的研究對象是世間一切離散數(shù)學(xué)的研究對象是世間一切事物之間的關(guān)系。事物之間的關(guān)系。3. 3. 離散數(shù)學(xué)所采用的研究方法有集離散數(shù)學(xué)所采用的研究方法有集合、代數(shù)、圖、數(shù)理邏輯等。合、代數(shù)、圖、數(shù)理邏輯等。1/26/2022整理課件6離散數(shù)學(xué)的內(nèi)容：離散數(shù)學(xué)的內(nèi)容： 數(shù)理邏輯（數(shù)理邏輯（Mathematics Logic) 集合論集合論(Sets) 組合論（組合論（Combination) 圖論（圖論（Graph Theory) 代數(shù)結(jié)構(gòu)（代數(shù)結(jié)構(gòu)（Algbra Structure) 線性代數(shù)線性代數(shù)(Linear Algbra ) 概

5、率論（概率論（Propobility Theory) 1/26/2022整理課件7數(shù)理邏輯 計算機(jī)是數(shù)理邏輯和電子學(xué)相結(jié)合的產(chǎn)物計算機(jī)是數(shù)理邏輯和電子學(xué)相結(jié)合的產(chǎn)物集合論 集合：一種重要的數(shù)據(jù)結(jié)構(gòu)集合：一種重要的數(shù)據(jù)結(jié)構(gòu) 關(guān)系：關(guān)系數(shù)據(jù)庫的理論基礎(chǔ)關(guān)系：關(guān)系數(shù)據(jù)庫的理論基礎(chǔ) 函數(shù)：所有計算機(jī)語言中不可缺少的一部分函數(shù)：所有計算機(jī)語言中不可缺少的一部分圖論 數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、編譯原理、計算機(jī)網(wǎng)數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、編譯原理、計算機(jī)網(wǎng) 絡(luò)原理的基礎(chǔ)絡(luò)原理的基礎(chǔ)代數(shù)系統(tǒng) 計算機(jī)編碼和糾錯碼理論計算機(jī)編碼和糾錯碼理論 數(shù)字邏輯設(shè)計基礎(chǔ)數(shù)字邏輯設(shè)計基礎(chǔ) 計算機(jī)使用的各種運算計算機(jī)使用的各種運算1/26/

6、2022整理課件8 18世紀(jì)，東普魯士的哥尼斯堡（現(xiàn)今叫加里寧格勒，世紀(jì)，東普魯士的哥尼斯堡（現(xiàn)今叫加里寧格勒，在波羅的海南岸）是一座景致迷人的城市，普勒格爾河橫在波羅的海南岸）是一座景致迷人的城市，普勒格爾河橫貫其境，并在這兒形成兩條支流，把整座城市分割成貫其境，并在這兒形成兩條支流，把整座城市分割成4個區(qū)個區(qū)域：河的兩岸（域：河的兩岸（A和和B），河中的島（），河中的島（C）和兩條支流之間）和兩條支流之間的半島（的半島（D）。當(dāng)時有七座橋橫跨普勒格爾河及其支流，把）。當(dāng)時有七座橋橫跨普勒格爾河及其支流，把河岸、半島和河心島連接起來。有人在游覽時提出這樣的河岸、半島和河心島連接起來。有人在游

7、覽時提出這樣的問題：能否從某個地方出發(fā)，穿過所有的橋各一次后再回問題：能否從某個地方出發(fā)，穿過所有的橋各一次后再回到出發(fā)點到出發(fā)點. 1/26/2022整理課件9離散數(shù)學(xué)課程設(shè)置：離散數(shù)學(xué)課程設(shè)置： 計算機(jī)系核心課程計算機(jī)系核心課程 信息類專業(yè)必修課程信息類專業(yè)必修課程 其它類專業(yè)的重要選修課程其它類專業(yè)的重要選修課程1/26/2022整理課件10 離散數(shù)學(xué)的后繼課程：離散數(shù)學(xué)的后繼課程： 數(shù)據(jù)結(jié)構(gòu)、編譯技術(shù)、數(shù)據(jù)結(jié)構(gòu)、編譯技術(shù)、 算法分析與設(shè)計、人工智能、算法分析與設(shè)計、人工智能、 數(shù)據(jù)庫、數(shù)據(jù)庫、1/26/2022整理課件11 教材：教材： 離散數(shù)學(xué)離散數(shù)學(xué)（第二版）（第二版） 方世昌方世

8、昌 編著編著 西安電子科技大學(xué)出版社出版西安電子科技大學(xué)出版社出版 1/26/2022整理課件12 參考教材：參考教材： Discrete Mathematics and Its Application (Forth Edition: 1998) Author: Kenneth H. Reson Publisher: McGraw-Hill 機(jī)械工業(yè)出版社機(jī)械工業(yè)出版社1/26/2022整理課件13 數(shù)理邏輯（數(shù)理邏輯（Mathematics Logic) 集合論集合論(Sets) 圖論（圖論（Graph Theory)1/26/2022整理課件14離散數(shù)學(xué)課程的學(xué)習(xí)方法離散數(shù)學(xué)課程的學(xué)習(xí)方法

9、: 強(qiáng)調(diào)：邏輯性、抽象性；強(qiáng)調(diào)：邏輯性、抽象性； 注重：概念、方法與應(yīng)用注重：概念、方法與應(yīng)用1/26/2022整理課件15概念（正確）（正確） 必須掌握好離散數(shù)學(xué)中大量的概念必須掌握好離散數(shù)學(xué)中大量的概念判斷（準(zhǔn)確）（準(zhǔn)確） 根據(jù)概念對事物的屬性進(jìn)行判斷根據(jù)概念對事物的屬性進(jìn)行判斷推理（可靠）（可靠） 根據(jù)多個判斷推出一個新的判斷根據(jù)多個判斷推出一個新的判斷1/26/2022整理課件161.1.1 命題邏輯命題邏輯 Proposition Logic邏輯學(xué)：邏輯學(xué)： 研究推理的一門學(xué)科研究推理的一門學(xué)科數(shù)理邏輯：數(shù)理邏輯： 用數(shù)學(xué)方法研究推理的一門數(shù)學(xué)學(xué)科用數(shù)學(xué)方法研究推理的一門數(shù)學(xué)學(xué)科 -

10、 一套符號體系一套符號體系 + 一組規(guī)則一組規(guī)則1/26/2022整理課件17數(shù)理邏輯的內(nèi)容：數(shù)理邏輯的內(nèi)容： 古典數(shù)理邏輯：古典數(shù)理邏輯： 命題邏輯、謂詞邏輯命題邏輯、謂詞邏輯 現(xiàn)代數(shù)理邏輯：現(xiàn)代數(shù)理邏輯： 公理化集合論、遞歸論、模型論、證明論公理化集合論、遞歸論、模型論、證明論1/26/2022整理課件18命題命題 Proposition 一個有確定真或假意義的語句一個有確定真或假意義的語句.命題邏輯命題邏輯 Proposition Logic1/26/2022整理課件19 命題命題是一個非真即假（不可兼）的陳述句。是一個非真即假（不可兼）的陳述句。有兩層意思，首先命題是一個陳述句，而命有

11、兩層意思，首先命題是一個陳述句，而命令句、疑問句和感嘆句都不是命題。其次是令句、疑問句和感嘆句都不是命題。其次是說這個陳述句所表達(dá)的內(nèi)容可決定是真還是說這個陳述句所表達(dá)的內(nèi)容可決定是真還是假，而且不是真的就是假的，不能不真又不假，而且不是真的就是假的，不能不真又不假，也不能又真又假。假，也不能又真又假。 凡與事實相符的陳述句為真語句，而與凡與事實相符的陳述句為真語句，而與事實不符的陳述句為假語句。事實不符的陳述句為假語句。1/26/2022整理課件20 這就是說，一個命題具有兩種可能的取值這就是說，一個命題具有兩種可能的取值（又稱真值）為真或為假，又只能取其一。通常（又稱真值）為真或為假，又只

12、能取其一。通常用大寫字母用大寫字母T表示真值為真，用表示真值為真，用F表示真值為假，表示真值為假，有時也可分別用有時也可分別用1和和0表示它們。表示它們。 因為只有兩種取值，所以這樣的命題邏輯也因為只有兩種取值，所以這樣的命題邏輯也稱為二值邏輯。稱為二值邏輯。 我們把以這種非真必假的命題作為研究對象的我們把以這種非真必假的命題作為研究對象的邏輯稱為古典邏輯，但也有人反對關(guān)于命題的這種邏輯稱為古典邏輯，但也有人反對關(guān)于命題的這種觀點，認(rèn)為存在既不真也不假的命題，例如：直覺觀點，認(rèn)為存在既不真也不假的命題，例如：直覺主義邏輯、多值邏輯等。主義邏輯、多值邏輯等。1/26/2022整理課件21舉例：下

13、列句子不是命題。舉例：下列句子不是命題。 （1） 8大于大于12嗎？嗎？ （2） 請勿吸煙。請勿吸煙。 （3） X大于大于Y。 （4） 本頁這一行的這句話是假話。本頁這一行的這句話是假話。1/26/2022整理課件22（1）是一個疑問句，不是陳述句。）是一個疑問句，不是陳述句。（2）是一個祈使句。）是一個祈使句。（3）是一個不能確定其真假的句子，它可能為真，）是一個不能確定其真假的句子，它可能為真，也可能為假，從而不為命題。在判斷一個語句是否是也可能為假，從而不為命題。在判斷一個語句是否是命題時，從語法上就是看他是否是陳述句。但值得注命題時，從語法上就是看他是否是陳述句。但值得注意的是，這里所

14、說的陳述句不包括那些意的是，這里所說的陳述句不包括那些“自指謂自指謂”的的語句。語句。（4）這個語句，它的結(jié)論是對自身而言的，就是所）這個語句，它的結(jié)論是對自身而言的，就是所謂謂“自指謂自指謂”的。這種自指謂的語句往往會產(chǎn)生自相的。這種自指謂的語句往往會產(chǎn)生自相矛盾的結(jié)論，即悖論。矛盾的結(jié)論，即悖論。1/26/2022整理課件23 All the following statements are propositions. 1. Washington, D.C., is the capital of the United States of America. 2. Toronto is the

15、 capital of Canada. 3. 1+1=2. 4. 2+2=3. Propositions 1 and 3 are true, whereas 2 and 4 are false. 1/26/2022整理課件24 Consider the following sentences. 1. What time is it? 2. Read this carefully. 3. x+1 =2. 4. x+y = z. Sentences 1 and 2 are not propositions because they are not statements. Sentences 3 a

16、nd 4 are not propositions because they are neither true nor false, since the variables in these sentences have not been assigned values. Various ways to form propositions from sentences of this type will be discussed in Section 1.3. 1/26/2022整理課件25命題的語句形式命題的語句形式 陳述句陳述句非命題語句：非命題語句： 疑問句疑問句 命令句命令句 感態(tài)句感

17、態(tài)句 非命題陳述句：悖論語句非命題陳述句：悖論語句1/26/2022整理課件26命題的符號表示：命題的符號表示： 大小寫英文字母：大小寫英文字母：P、Q、R、 p 、q 、r、。、。命題真值（命題真值（Truth Values）的表示：）的表示： 真：真：T、1 假：假：F、0 1/26/2022整理課件27命題語句真值確定的幾點說明：命題語句真值確定的幾點說明： 1、時間性、時間性 2、區(qū)域性、區(qū)域性 3、標(biāo)準(zhǔn)性、標(biāo)準(zhǔn)性命題真值間的關(guān)系表示：命題真值間的關(guān)系表示： 真值表（真值表（Truth Table) 1/26/2022整理課件28Let p be a proposition. The

18、statement It is not the case that p. is another proposition, called the negation of p. The negation of p is denoted by p. The proposition p is read not p.p的否定的否定1/26/2022整理課件29 Find the negation of the proposition Today is Friday and express this in simple English.The negation is It is not the case

19、that today is Friday. This negation can be more simply expressed by Today is not Friday.1/26/2022整理課件301/26/2022整理課件31 Let p and q be propositions. The proposition p and q, denoted by pq, is the proposition that is true when both p and q are true and is false otherwise. The proposition pq is called

20、the conjunction of p and q. The truth table for pq is shown in Table 2.p和和q的合取的合取1/26/2022整理課件321/26/2022整理課件33 Find the conjunction of the propositions p and q where p is the proposition Today is Friday and q is the proposition It is raining today.Solution: The conjunction of these propositions, pq

21、, is the proposition Today is Friday and it is raining today. This proposition is true on rainy Fridays and is false on any day that is not a Friday and on Fridays when it does not rain.1/26/2022整理課件34 Let p and q be propositions.The proposition p or q, denoted by pq,is the proposition that is false

22、 when p and q are both false and true otherwise. The proposition pq is called the disjunction of p and q.The truth table for pq is shown in Table 3.p和q的析取1/26/2022整理課件351/26/2022整理課件36 What is the disjunction of the propositions p and q where p and q are the same propositions as in Example 4?Solutio

23、n: The disjunction of p and q, p q, is the proposition Today is Friday or it is raining today. This proposition is true on any day that is either a Friday or a rainy day (including rainy Fridays). It is only false on days that are not Fridays when it also does not rain.1/26/2022整理課件37 Let p and q be

24、 propositions.The implication p q is the proposition that is false when p is true and q is false and true otherwise. In this implication p is called the hypothesis (or antecedent or premise) and q is called the conclusion (or consequence).如果如果p,則則q單條件單條件, 蘊(yùn)涵蘊(yùn)涵P:前提前提Q:結(jié)論結(jié)論1/26/2022整理課件381/26/2022整理課件

25、39“PQ”真假值的這種取法也有人為因素，表現(xiàn)在：真假值的這種取法也有人為因素，表現(xiàn)在：（1） 根據(jù)根據(jù)PQ真假值取法的定義可以看出，若真假值取法的定義可以看出，若P為假，為假，不論不論Q是否為真，則是否為真，則PQ為真。為真。我們來看我們來看 命題：命題：如果月亮從西邊出來，則太陽也從西邊出來。如果月亮從西邊出來，則太陽也從西邊出來。由定義這是一個真命題，但這使人感到有點不自然，既由定義這是一個真命題，但這使人感到有點不自然，既然月亮不會從西邊出來，我們完全可以認(rèn)為這個命題毫無用然月亮不會從西邊出來，我們完全可以認(rèn)為這個命題毫無用處或毫無意義。但是，我們感興趣的主要是（數(shù)學(xué)）推理和處或毫無意

26、義。但是，我們感興趣的主要是（數(shù)學(xué)）推理和證明的方法，在這種情況下，命題證明的方法，在這種情況下，命題PQ真的意義在于我們能真的意義在于我們能從從P真推出真推出Q真，而沒有必要追求從真，而沒有必要追求從P假能推出什么來。假能推出什么來。例如，關(guān)于整數(shù)的如下命題：例如，關(guān)于整數(shù)的如下命題：對某個實數(shù)對某個實數(shù)n，如果，如果n 2，那么，那么n*2 4。這是個真命題，而無須考慮命題變項取什么值。這是個真命題，而無須考慮命題變項取什么值。1/26/2022整理課件40（2） 蘊(yùn)涵詞可以連接兩個以上意義毫不相干的命題，只要蘊(yùn)涵詞可以連接兩個以上意義毫不相干的命題，只要前件和后件滿足前件和后件滿足P ?

27、 Q為真的定義所規(guī)定的條件，我們便可說為真的定義所規(guī)定的條件，我們便可說“PQ為真為真”。PQ真假的這種規(guī)定也引起了爭論。真假的這種規(guī)定也引起了爭論。例如：例如：如果地球停止了轉(zhuǎn)動，則大熊貓產(chǎn)在中國。如果地球停止了轉(zhuǎn)動，則大熊貓產(chǎn)在中國。 但注意到，我們關(guān)心的是推理，關(guān)心能否從但注意到，我們關(guān)心的是推理，關(guān)心能否從P真推出真推出Q真，真，不關(guān)心各命題之間實際意義是否有聯(lián)系。不關(guān)心各命題之間實際意義是否有聯(lián)系。 1/26/2022整理課件41 Find the converse and the contrapositive of the implication If today is Thursday, then I have a test today.Solution: The converse is If I have a test today, then today is Thursday.And the contrapositive of this implication is If I do not have a test today, then today is not Thursday.1/26/2022整理課件42 Let p and q be propositions