趙洪鑾離散數(shù)學第一章13節(jié)

1、離散數(shù)學離散數(shù)學1第一篇第一篇 數(shù)理邏輯數(shù)理邏輯 邏輯學：邏輯學：研究思維形式及思維規(guī)律的科學研究思維形式及思維規(guī)律的科學 思維的形式結構思維的形式結構包括包括 概念概念 判斷判斷 推理推理先看下面一道推理題：先看下面一道推理題： 如果我學習，那么我的離散數(shù)學不會不及格。如果我學習，那么我的離散數(shù)學不會不及格。 如果我不熱衷于玩撲克，那么我將學習。如果我不熱衷于玩撲克，那么我將學習。 但我離散數(shù)學不及格。但我離散數(shù)學不及格。 因此我熱衷于玩撲克。因此我熱衷于玩撲克。離散數(shù)學離散數(shù)學2 請問這個人說得對嗎？他是怎么推導出來的呢？請問這個人說得對嗎？他是怎么推導出來的呢？ 要回答這樣的問題，實際上

2、就是看由一些諸如要回答這樣的問題，實際上就是看由一些諸如“離散數(shù)離散數(shù)學不及格學不及格”這樣的前提能否推出這樣的前提能否推出“熱衷于玩撲克熱衷于玩撲克”這樣的這樣的結論來。這又需要經(jīng)歷如下過程：結論來。這又需要經(jīng)歷如下過程： (1) 什么是前提？有哪些前提？什么是前提？有哪些前提？ (2) 結論是什么？結論是什么？ (3) 根據(jù)什么進行推理？根據(jù)什么進行推理？ (4) 怎么進行推理？怎么進行推理？ 離散數(shù)學離散數(shù)學3n數(shù)理邏輯數(shù)理邏輯 用數(shù)學的方法來研究推理的規(guī)律統(tǒng)稱數(shù)理邏輯。用數(shù)學的方法來研究推理的規(guī)律統(tǒng)稱數(shù)理邏輯。n為什么研究數(shù)理邏輯為什么研究數(shù)理邏輯 程序程序=算法算法+數(shù)據(jù)數(shù)據(jù) 算法算

3、法=邏輯邏輯+控制控制數(shù)理邏輯是數(shù)理邏輯是用數(shù)學方法即通過引入表意符號研究用數(shù)學方法即通過引入表意符號研究推理的學問推理的學問。因此，數(shù)理邏輯又名為符號邏輯。因此，數(shù)理邏輯又名為符號邏輯。離散數(shù)學離散數(shù)學4第一章第一章 命題邏輯命題邏輯n命題邏輯，也稱命題演算，記為命題邏輯，也稱命題演算，記為ls。研。研究由命題為基本單位構成的前提和結論究由命題為基本單位構成的前提和結論之間的可推導關系。之間的可推導關系。n它與謂詞邏輯構成數(shù)理邏輯的基礎，而它與謂詞邏輯構成數(shù)理邏輯的基礎，而命題邏輯又是謂詞邏輯的基礎。命題邏輯又是謂詞邏輯的基礎。離散數(shù)學離散數(shù)學5本次課內(nèi)容：本次課內(nèi)容：命題，邏輯聯(lián)結詞，命題

4、符號化命題，邏輯聯(lián)結詞，命題符號化 (1)掌握命題概念掌握命題概念 (2)掌握聯(lián)結詞含義及真值表掌握聯(lián)結詞含義及真值表 (3)掌握命題符號化方法掌握命題符號化方法 本次課重點：本次課重點：離散數(shù)學離散數(shù)學61-1 命題及其表示方法命題及其表示方法內(nèi)容：內(nèi)容：命題命題重點：重點：掌握命題概念掌握命題概念 離散數(shù)學離散數(shù)學7一一.基本概念基本概念 命題：命題：具有具有確定真值的陳述句。確定真值的陳述句。 or 真值客觀存在且唯一真值客觀存在且唯一 or 能區(qū)分真假能區(qū)分真假可以看出：可以看出： （1）一個命題，總是具有一個一個命題，總是具有一個“值值”，稱為真，稱為真值。值。命真命真真命題：真值為

5、真真命題：真值為真(t，1)的命題。的命題。 假命題：真值為假假命題：真值為假(f，0)的命題。的命題。離散數(shù)學離散數(shù)學8（2）判斷命題規(guī)則：）判斷命題規(guī)則：只有具有只有具有確定真值確定真值的的陳述句陳述句才是命題，感嘆句，疑才是命題，感嘆句，疑問句，祈使句等都不是命題。問句，祈使句等都不是命題。 真值必須真值必須唯一唯一，與是否知道其真值無關與是否知道其真值無關。 （3）判斷命題的兩個步驟）判斷命題的兩個步驟： 1、是否為陳述句；、是否為陳述句； 2、是否有確定的、唯一的真值。、是否有確定的、唯一的真值。離散數(shù)學離散數(shù)學9 1、100是自然數(shù)。是自然數(shù)。2、這周四是否開會？、這周四是否開會？

6、3、11011104、how do you do ?5、別的星球上有生物。、別的星球上有生物。 6、2010年國慶是晴天。年國慶是晴天。7、x+398、我正在說謊。、我正在說謊。9、全體立正！、全體立正！ 10、離散數(shù)學是我們的基礎必修課。、離散數(shù)學是我們的基礎必修課。 11、我學英語，或者我學日語。、我學英語，或者我學日語。 12、 只有天下大雨，他才乘車去上班。只有天下大雨，他才乘車去上班。例例：判斷下列句子是否為命題：判斷下列句子是否為命題是是不是不是不是不是不是不是是是是是離散數(shù)學離散數(shù)學10 （2）（）（4）（）（9）不是命題。（）不是命題。（3）在十進）在十進制中為假，二進制中為真

7、，不能確定其真值。制中為假，二進制中為真，不能確定其真值。不是命題。（不是命題。（7）根據(jù)）根據(jù)x的值而定，無唯一真值，的值而定，無唯一真值，不是命題。不是命題。 （5）（）（6）目前無法確定，但從事物的本）目前無法確定，但從事物的本質(zhì)而言，它本身是有真假可言的，即客觀存在質(zhì)而言，它本身是有真假可言的，即客觀存在且唯一，為命題。無法確定真值；且唯一，為命題。無法確定真值； （8）是悖論。）是悖論。 所以所以，（，（1）（）（5） （6） （10）（）（11）（12）是命題。）是命題。分析：分析：離散數(shù)學離散數(shù)學11 “悖論悖論”這個詞的意義比較豐富，它包括一切與人們直覺和這個詞的意義比較豐富，

8、它包括一切與人們直覺和日常經(jīng)驗相矛盾的數(shù)學結論。由真推出假，由假推出真。日常經(jīng)驗相矛盾的數(shù)學結論。由真推出假，由假推出真。 (1) 說謊者悖論說謊者悖論 我們陷入了著名的說謊者悖論之中。下面是它的簡單形式。我們陷入了著名的說謊者悖論之中。下面是它的簡單形式。 這句話是錯的這句話是錯的n上面這個句子對嗎上面這個句子對嗎?n如果是對的，這句話就是錯的！如果是對的，這句話就是錯的！n如果這句話是錯的，那這個句子就對了！如果這句話是錯的，那這個句子就對了！n像這樣矛盾的說法比你所能想到的還要普遍得多。像這樣矛盾的說法比你所能想到的還要普遍得多。附錄附錄(悖論悖論):離散數(shù)學離散數(shù)學12著名的理發(fā)師悖論

9、是伯特納德著名的理發(fā)師悖論是伯特納德羅素提出的。羅素提出的。 告示告示: 城里所有不自己刮臉的男人都由我給他們刮臉，我也城里所有不自己刮臉的男人都由我給他們刮臉，我也只給這些人刮臉。只給這些人刮臉。n誰給這位理發(fā)師刮臉呢？誰給這位理發(fā)師刮臉呢？n如果他自己刮臉，那他就屬于自己刮臉的那類人。但是，如果他自己刮臉，那他就屬于自己刮臉的那類人。但是，他的招牌說明他不給這類人刮臉，因此他不能自己來刮。他的招牌說明他不給這類人刮臉，因此他不能自己來刮。n如果另外一個人來給他刮臉，那他就是不自己刮臉的人。如果另外一個人來給他刮臉，那他就是不自己刮臉的人。但是，他的招牌說他要給所有這類人刮臉。因此其他任何但

10、是，他的招牌說他要給所有這類人刮臉。因此其他任何人也不能給他刮臉?？磥恚瑳]有任何人能給這位理發(fā)師刮人也不能給他刮臉?？磥恚瑳]有任何人能給這位理發(fā)師刮臉了！臉了！n伯特納德伯特納德羅素提出這個悖論，為的是把他發(fā)現(xiàn)的關于集羅素提出這個悖論，為的是把他發(fā)現(xiàn)的關于集合的一個著名悖論用故事通俗地表述出來。合的一個著名悖論用故事通俗地表述出來。(2)羅素悖論（理發(fā)師悖論）羅素悖論（理發(fā)師悖論） 離散數(shù)學離散數(shù)學13注意：注意：1.命題的真值是具有命題的真值是具有客觀性質(zhì)客觀性質(zhì)的，而不是的，而不是由人的主觀決定的。由人的主觀決定的。2. 在數(shù)理邏輯中，不要糾纏各種具體問題在數(shù)理邏輯中，不要糾纏各種具體問題

11、的真假問題，而把它看成抽象化的數(shù)學的真假問題，而把它看成抽象化的數(shù)學概念。概念。離散數(shù)學離散數(shù)學14簡單簡單/原子命題：由不能再分解為更簡單的原子命題：由不能再分解為更簡單的陳述句的陳述句構成。陳述句的陳述句構成。(1) (5) (10) 復合命題：由簡單命題通過復合命題：由簡單命題通過聯(lián)結詞聯(lián)結詞聯(lián)結而聯(lián)結而成的陳述句。成的陳述句。它由原子命題、命題聯(lián)結它由原子命題、命題聯(lián)結詞和圓括號組成。詞和圓括號組成。(11) (12)命題的分類命題的分類離散數(shù)學離散數(shù)學15 常用大寫字母、帶下標的大寫字母、數(shù)字常用大寫字母、帶下標的大寫字母、數(shù)字 表示表示命題，稱之為命題，稱之為命題標識符。命題標識符

12、。 例如：例如：p： 北京是中國的首都。北京是中國的首都。 2：北京是中國的首都。：北京是中國的首都。n命題常量：命題常量：表示一個確定的命題的命題標示符。表示一個確定的命題的命題標示符。n命題變元：命題變元：任意命題的位置標志。命題變元不是任意命題的位置標志。命題變元不是命題（表示任意命題，不能確定真值）命題（表示任意命題，不能確定真值）當命題變元當命題變元p用一個特定的命題取代時，用一個特定的命題取代時，p才能確定才能確定真值，也稱對真值，也稱對p進行指派。進行指派。二、二、命題命題的表示法的表示法離散數(shù)學離散數(shù)學16本節(jié)的主要內(nèi)容有本節(jié)的主要內(nèi)容有: :1.1.給出了命題的概念；給出了命

13、題的概念；2.2.命題的判斷結果稱為命題的真值；命題的判斷結果稱為命題的真值；3. 3. 原子命題原子命題, , 復合命題復合命題。離散數(shù)學離散數(shù)學171-2 聯(lián)結詞聯(lián)結詞 內(nèi)容：內(nèi)容： 否定否定聯(lián)結詞聯(lián)結詞 合取合取聯(lián)結詞聯(lián)結詞 析取析取聯(lián)結詞聯(lián)結詞 條件條件聯(lián)結詞聯(lián)結詞 雙條件雙條件聯(lián)結詞聯(lián)結詞離散數(shù)學離散數(shù)學18(1)否定聯(lián)結詞否定聯(lián)結詞定義定義1-2.1 設設p為命題，復合命題為命題，復合命題“非非p”（或（或“p的否的否定定”）稱為）稱為p的否定式，記作的否定式，記作 p，符號，符號稱為否定聯(lián)結稱為否定聯(lián)結詞。詞。運算規(guī)則：屬于單目運算符運算規(guī)則：屬于單目運算符(一元運算一元運算)例

14、例: p:上海是一個大城市。上海是一個大城市。 p: 上海并不是一個大城市。上海并不是一個大城市。 p：上海是一個不大的城市。：上海是一個不大的城市。 pp t f f t離散數(shù)學離散數(shù)學19(2) 合取聯(lián)結詞合取聯(lián)結詞 p qpq t t t t f f f t f f f f定義定義1-2.2 設設p,q為二命題，復合命題為二命題，復合命題“p并且并且q”或或“p與與q”，稱為，稱為p與與q的合取式，記作的合取式，記作p q ，符號，符號稱為合取聯(lián)結詞。稱為合取聯(lián)結詞。運算規(guī)則：屬于二元運算符運算規(guī)則：屬于二元運算符合取運算特點：只合取運算特點：只有參與運算的二命有參與運算的二命題全為真時

15、，運算題全為真時，運算結果才為真，否則結果才為真，否則為假。為假。離散數(shù)學離散數(shù)學20例例1 p ：今天下雨。：今天下雨。 q： 明天下雨。明天下雨。 上述命題的合取為：上述命題的合取為： pq：今天下雨而且明天下雨：今天下雨而且明天下雨 pq：今天與明天都下雨。：今天與明天都下雨。 pq：這兩天都下雨。：這兩天都下雨。例例2 p: 地球在運轉(zhuǎn)。地球在運轉(zhuǎn)。q：224 則則 pq：地球在運轉(zhuǎn)且：地球在運轉(zhuǎn)且224例題例題離散數(shù)學離散數(shù)學21注意：注意：（1）自然語言中的表示自然語言中的表示“并且并且”意思的聯(lián)結詞，如意思的聯(lián)結詞，如“既既又又”、“不但不但而且而且”、“雖然雖然但是但是”、“一

16、面一面一面一面”等都可以符號化為等都可以符號化為 。 （2） 合取的概念與自然語言中的合取的概念與自然語言中的“與與”意義類似，但并不意義類似，但并不完全相同。尤其例完全相同。尤其例2在自然語言中是沒有意義的，但在數(shù)在自然語言中是沒有意義的，但在數(shù)理邏輯中仍能成為一個新的命題。理邏輯中仍能成為一個新的命題。 （3）不要見到不要見到“與與”或或“和和”就使用聯(lián)結詞就使用聯(lián)結詞 ！ 例如：甲與乙是同學。例如：甲與乙是同學。 這里的這里的“與與”不是合取。不是合取。離散數(shù)學離散數(shù)學22（3）析取聯(lián)結詞）析取聯(lián)結詞定義定義1-2.3 設設p,q為二命題，復合命題為二命題，復合命題“p或或q” 稱為稱為

17、p與與q的析取式，記作的析取式，記作p q，符號，符號稱為稱為析取聯(lián)結詞。析取聯(lián)結詞。運算規(guī)則：屬于二元運算符運算規(guī)則：屬于二元運算符析取運算特點：析取運算特點：只有參與運算的只有參與運算的二命題全為假時，二命題全為假時，運算結果才為假，運算結果才為假，否則為真。否則為真。離散數(shù)學離散數(shù)學23 析取運算只能表示自然語言中的析取運算只能表示自然語言中的“相容相容或或”(亦稱亦稱“可兼或可兼或”，用它聯(lián)結的命題具有相，用它聯(lián)結的命題具有相容性容性)的意思的意思 不能表示自然語言里的不能表示自然語言里的“排斥或排斥或” 還有一些漢語中的還有一些漢語中的“或或”不是命題聯(lián)結詞。不是命題聯(lián)結詞。注意注意

18、: 離散數(shù)學離散數(shù)學24例如：火車例如：火車8：00或或9：00到站。到站。 （排斥或）（排斥或） 設設p：火車：火車8：00到站。到站。q：火車：火車9：00到站。到站。 則上述命題就不可簡單符號化為：則上述命題就不可簡單符號化為：p q 而應描述為而應描述為(p q) (pq) 或者或者 p q命題命題p q（p q） t t f t f t f t f t f t t f t f f f t f離散數(shù)學離散數(shù)學25（1）小王愛打球或愛跑步。）小王愛打球或愛跑步。 （可兼或）（可兼或） 設設p：小王愛打球。：小王愛打球。 q：小王愛跑步。：小王愛跑步。 則上述命題可符號化為：則上述命題可符

19、號化為：p q（2）今晚我在家看電視或去影院看電影）今晚我在家看電視或去影院看電影 （排斥或）（排斥或） (p q) (pq) （3）他昨天做了二十或三十道習題。）他昨天做了二十或三十道習題。 “或或” 只是表示的習題的近似數(shù)目。原子命題只是表示的習題的近似數(shù)目。原子命題例如：例如：離散數(shù)學離散數(shù)學26（4）條件聯(lián)結詞）條件聯(lián)結詞定義定義1-2.4 設設p,q為二命題，復合命題為二命題，復合命題“如果如果p，則，則q” 稱稱為為p與與q的蘊涵式，記作的蘊涵式，記作p q，即，即“如果如果p，則，則q”，“若若p則則q”。并稱。并稱p為前件，為前件，q為后件，符號為后件，符號稱為蘊涵稱為蘊涵聯(lián)結

20、詞。聯(lián)結詞。運算規(guī)則：屬于二元運算符運算規(guī)則：屬于二元運算符 p qpq t t t t f f f t t f f t只有當只有當p的的真值為真值為t，q的真值為的真值為f時，時， p q的真值為的真值為f。否則均為否則均為t。離散數(shù)學離散數(shù)學27例題：例題：例例1：如果某動物為哺乳動物，則它必胎生。如果某動物為哺乳動物，則它必胎生。例例2：如果我得到這本小說，那末我今夜就讀完如果我得到這本小說，那末我今夜就讀完它。它。例例3：如果雪是黑的，那么太陽從西方出。如果雪是黑的，那么太陽從西方出。離散數(shù)學離散數(shù)學28（1）自然語言中可用自然語言中可用p q蘊涵式表述命題格式有蘊涵式表述命題格式有“

21、只要只要p p，就就q”“q”“因為因為p p，所以，所以q”q”、“只有只有q才才p”、“p僅當僅當q”（p成立，成立，q就成立）、就成立）、“除非除非q才才p”、“除非除非q，否則非，否則非p”、“q是是p的必要條件的必要條件”等。等。（2）與自然語言的不同：前件與后件可以沒有任何內(nèi)在聯(lián)系?。┡c自然語言的不同：前件與后件可以沒有任何內(nèi)在聯(lián)系?。?）在數(shù)學或其他自然科學中，往往是）在數(shù)學或其他自然科學中，往往是p為真為真 q也為真的推理關系。但也為真的推理關系。但在數(shù)理邏輯中，作為一種規(guī)定，當在數(shù)理邏輯中，作為一種規(guī)定，當p為假時，無論為假時，無論q如何，如何， p q均均為真。（善意的推定

22、）為真。（善意的推定） 注意：注意：離散數(shù)學離散數(shù)學29（5）雙條件聯(lián)結詞）雙條件聯(lián)結詞 定義定義1.5 設設p,q為二命題，復合命題為二命題，復合命題“p當且僅當當且僅當q” 稱為稱為p與與q的等價式，記作的等價式，記作p q，符號，符號 稱為等價聯(lián)結詞。稱為等價聯(lián)結詞。運算規(guī)則：屬于二元運算符運算規(guī)則：屬于二元運算符 p qp q t t t t f f f t f f f t當當p和和q的真的真值相同時，值相同時，p q的真的真值為值為t；否則；否則為為f。離散數(shù)學離散數(shù)學30說明：說明：雙條件命題也可以不顧因果關系，只根據(jù)雙條件命題也可以不顧因果關系，只根據(jù)聯(lián)結詞的定義確定真值。聯(lián)結詞

23、的定義確定真值。例例1：兩個三角形全等，當且僅當它們的三組對兩個三角形全等，當且僅當它們的三組對應邊相等。應邊相等。 例例2：燕子飛回南方，當且僅當春天來了。燕子飛回南方，當且僅當春天來了。 例例3： 22=4當且僅當雪是白的。當且僅當雪是白的。離散數(shù)學離散數(shù)學31小結：小結：n以上以上5種最基本、最常用、最重要的聯(lián)結詞可種最基本、最常用、最重要的聯(lián)結詞可以組成一個集合以組成一個集合，成為，成為一個聯(lián)結詞集。由后四種組成的命題是復合命一個聯(lián)結詞集。由后四種組成的命題是復合命題，亦可被多次使用，如題，亦可被多次使用，如（p q） r；n復合命題的真值，取決于原子命題的真值，與復合命題的真值，取決

24、于原子命題的真值，與原子命題之間是否有關系無關，與復合命題本原子命題之間是否有關系無關，與復合命題本身內(nèi)容、含義無關；身內(nèi)容、含義無關；n、 具有對稱性，具有對稱性， 、沒有；沒有；n連接詞具有運算和操作性，從已知命題得到新連接詞具有運算和操作性，從已知命題得到新命題。命題。離散數(shù)學離散數(shù)學32 1-3 命題公式與翻譯命題公式與翻譯內(nèi)內(nèi) 容：容： 合式公式合式公式 命題翻譯命題翻譯重點難點：重點難點：命題翻譯命題翻譯離散數(shù)學離散數(shù)學33合式公式合式公式wff命題公式：命題公式：將命題變元用聯(lián)結詞和圓括號按一定將命題變元用聯(lián)結詞和圓括號按一定的邏輯關系聯(lián)結起來的有意義的符號串。的邏輯關系聯(lián)結起來的有意義的符號串。例如：例如： pq，p （qp）說明：說明：命題公式是沒有真假值的。僅當命題變元命題公式是沒有真假值的。僅當命題變元用確定命題代入時，才得到一個命題。命題的用確定命題代入時，才得到一個命題。命題的真值依賴于代換變元的那些命題真值。真值依賴于代換變元的那些命題真值。 離散數(shù)學離散數(shù)學34定義定義1-2-1 合式公式是由下列規(guī)則形成的字符串：合式公式是由下列規(guī)則形成的字符串： （1）單個命題變元本身是一個合式公式。）單個命題變元本身是一個合式公式。 （2）如果）如果a是合式公式，那么是合式公式，那么a是合式公式。是合式公式