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

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

3、序=算法算法+數據數據 算法算法=邏輯邏輯+控制控制數理邏輯是數理邏輯是用數學方法即通過引入表意符號研究用數學方法即通過引入表意符號研究推理的學問推理的學問。因此，數理邏輯又名為符號邏輯。因此，數理邏輯又名為符號邏輯。離散數學離散數學編輯ppt4第一章第一章 命題邏輯命題邏輯n命題邏輯，也稱命題演算，記為命題邏輯，也稱命題演算，記為Ls。研。研究由命題為基本單位構成的前提和結論究由命題為基本單位構成的前提和結論之間的可推導關系。之間的可推導關系。n它與謂詞邏輯構成數理邏輯的基礎，而它與謂詞邏輯構成數理邏輯的基礎，而命題邏輯又是謂詞邏輯的基礎。命題邏輯又是謂詞邏輯的基礎。離散數學離散數學編輯pp

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

5、題，總是具有一個“值值”，稱為真，稱為真值。值。命真命真真命題：真值為真真命題：真值為真(T，1)的命題。的命題。 假命題：真值為假假命題：真值為假(F，0)的命題。的命題。離散數學離散數學編輯ppt8（2）判斷命題規則：）判斷命題規則：只有具有只有具有確定真值確定真值的的陳述句陳述句才是命題，感嘆句，疑才是命題，感嘆句，疑問句，祈使句等都不是命題。問句，祈使句等都不是命題。 真值必須真值必須唯一唯一，與是否知道其真值無關與是否知道其真值無關。 （3）判斷命題的兩個步驟）判斷命題的兩個步驟： 1、是否為陳述句；、是否為陳述句； 2、是否有確定的、唯一的真值。、是否有確定的、唯一的真值。離散數學

6、離散數學編輯ppt9 1、100是自然數。是自然數。2、這周四是否開會？、這周四是否開會？3、11011104、How do you do ?5、別的星球上有生物。、別的星球上有生物。 6、2010年國慶是晴天。年國慶是晴天。7、x+398、我正在說謊。、我正在說謊。9、全體立正！、全體立正！ 10、離散數學是我們的基礎必修課。、離散數學是我們的基礎必修課。 11、我學英語，或者我學日語。、我學英語，或者我學日語。 12、 只有天下大雨，他才乘車去上班。只有天下大雨，他才乘車去上班。例例：判斷下列句子是否為命題：判斷下列句子是否為命題是是不是不是不是不是不是不是是是是是離散數學離散數學編輯pp

7、t10 （2）（）（4）（）（9）不是命題。（）不是命題。（3）在十進制）在十進制中為假，二進制中為真，不能確定其真值。不中為假，二進制中為真，不能確定其真值。不是命題。（是命題。（7）根據）根據x的值而定，無唯一真值，的值而定，無唯一真值，不是命題。不是命題。 （5）（）（6）目前無法確定，但從事物的本）目前無法確定，但從事物的本質而言，它本身是有真假可言的，即客觀存在質而言，它本身是有真假可言的，即客觀存在且唯一，為命題。無法確定真值；且唯一，為命題。無法確定真值； （8）是悖論。）是悖論。 所以所以，（，（1）（）（5） （6） （10）（）（11）（12）是命題。）是命題。分析：分析：

8、離散數學離散數學編輯ppt11 “悖論悖論”這個詞的意義比較豐富，它包括一切與人們直覺這個詞的意義比較豐富，它包括一切與人們直覺和日常經驗相矛盾的數學結論。由真推出假，由假推出真。和日常經驗相矛盾的數學結論。由真推出假，由假推出真。 (1) 說謊者悖論說謊者悖論 我們陷入了著名的說謊者悖論之中。下面是它的簡單形式。我們陷入了著名的說謊者悖論之中。下面是它的簡單形式。 這句話是錯的這句話是錯的n上面這個句子對嗎上面這個句子對嗎?n如果是對的，這句話就是錯的！如果是對的，這句話就是錯的！n如果這句話是錯的，那這個句子就對了！如果這句話是錯的，那這個句子就對了！n像這樣矛盾的說法比你所能想到的還要普

9、遍得多。像這樣矛盾的說法比你所能想到的還要普遍得多。附錄附錄(悖論悖論):離散數學離散數學編輯ppt12著名的理發師悖論是伯特納德著名的理發師悖論是伯特納德羅素提出的。羅素提出的。 告示告示: 城里所有不自己刮臉的男人都由我給他們刮臉，我也城里所有不自己刮臉的男人都由我給他們刮臉，我也只給這些人刮臉。只給這些人刮臉。n誰給這位理發師刮臉呢？誰給這位理發師刮臉呢？n如果他自己刮臉，那他就屬于自己刮臉的那類人。但是，如果他自己刮臉，那他就屬于自己刮臉的那類人。但是，他的招牌說明他不給這類人刮臉，因此他不能自己來刮。他的招牌說明他不給這類人刮臉，因此他不能自己來刮。n如果另外一個人來給他刮臉，那他就

10、是不自己刮臉的人。如果另外一個人來給他刮臉，那他就是不自己刮臉的人。但是，他的招牌說他要給所有這類人刮臉。因此其他任何但是，他的招牌說他要給所有這類人刮臉。因此其他任何人也不能給他刮臉。看來，沒有任何人能給這位理發師刮人也不能給他刮臉。看來，沒有任何人能給這位理發師刮臉了！臉了！n伯特納德伯特納德羅素提出這個悖論，為的是把他發現的關于集羅素提出這個悖論，為的是把他發現的關于集合的一個著名悖論用故事通俗地表述出來。合的一個著名悖論用故事通俗地表述出來。(2)羅素悖論（理發師悖論）羅素悖論（理發師悖論） 離散數學離散數學編輯ppt13注意：注意：1.命題的真值是具有命題的真值是具有客觀性質客觀性質

11、的，而不是的，而不是由人的主觀決定的。由人的主觀決定的。2. 在數理邏輯中，不要糾纏各種具體問題在數理邏輯中，不要糾纏各種具體問題的真假問題，而把它看成抽象化的數學的真假問題，而把它看成抽象化的數學概念。概念。離散數學離散數學編輯ppt14簡單簡單/原子命題：由不能再分解為更簡單的原子命題：由不能再分解為更簡單的陳述句的陳述句構成。陳述句的陳述句構成。(1) (5) (10) 復合命題：由簡單命題通過復合命題：由簡單命題通過聯結詞聯結詞聯結而聯結而成的陳述句。成的陳述句。它由原子命題、命題聯結它由原子命題、命題聯結詞和圓括號組成。詞和圓括號組成。(11) (12)命題的分類命題的分類離散數學離

12、散數學編輯ppt15 常用大寫字母、帶下標的大寫字母、數字常用大寫字母、帶下標的大寫字母、數字 表示命表示命題，稱之為題，稱之為命題標識符。命題標識符。 例如：例如：P： 北京是中國的首都。北京是中國的首都。 2：北京是中國的首都。：北京是中國的首都。n命題常量：命題常量：表示一個確定的命題的命題標示符。表示一個確定的命題的命題標示符。n命題變元：命題變元：任意命題的位置標志。命題變元不是任意命題的位置標志。命題變元不是命題（表示任意命題，不能確定真值）命題（表示任意命題，不能確定真值）當命題變元當命題變元P用一個特定的命題取代時，用一個特定的命題取代時，P才能確定才能確定真值，也稱對真值，也

13、稱對P進行指派。進行指派。二、二、命題命題的表示法的表示法離散數學離散數學編輯ppt16本節的主要內容有本節的主要內容有: :1.1.給出了命題的概念；給出了命題的概念；2.2.命題的判斷結果稱為命題的真值；命題的判斷結果稱為命題的真值；3. 3. 原子命題原子命題, , 復合命題。復合命題。離散數學離散數學編輯ppt171-2 聯結詞聯結詞 內容：內容： 否定否定聯結詞聯結詞 合取合取聯結詞聯結詞 析取析取聯結詞聯結詞 條件條件聯結詞聯結詞 雙條件雙條件聯結詞聯結詞離散數學離散數學編輯ppt18(1)否定聯結詞否定聯結詞定義定義 設設P為命題，復合命題為命題，復合命題“非非P”（或（或“P的

14、否定的否定”）稱）稱為為P的否定式，記作的否定式，記作 P，符號，符號稱為否定聯結詞。稱為否定聯結詞。運算規則：屬于單目運算符運算規則：屬于單目運算符(一元運算一元運算)例例: P:上海是一個大城市。上海是一個大城市。 P: 上海并不是一個大城市。上海并不是一個大城市。 P：上海是一個不大的城市。：上海是一個不大的城市。 PP T F F T離散數學離散數學編輯ppt19(2) 合取聯結詞合取聯結詞 P QPQ T T T T F F F T F F F F定義定義 設設P,Q為二命題，復合命題為二命題，復合命題“P并且并且Q”或或“P與與Q”，稱為稱為P與與Q的合取式，記作的合取式，記作P

15、Q ，符號，符號稱為合取聯結詞。稱為合取聯結詞。運算規則：屬于二元運算符運算規則：屬于二元運算符合取運算特點：只合取運算特點：只有參與運算的二命有參與運算的二命題全為真時，運算題全為真時，運算結果才為真，否則結果才為真，否則為假。為假。離散數學離散數學編輯ppt20例例1 P ：今天下雨。：今天下雨。 Q： 明天下雨。明天下雨。 上述命題的合取為：上述命題的合取為： PQ：今天下雨而且明天下雨：今天下雨而且明天下雨 PQ：今天與明天都下雨。：今天與明天都下雨。 PQ：這兩天都下雨。：這兩天都下雨。例例2 P: 地球在運轉。地球在運轉。Q：224 則則 PQ：地球在運轉且：地球在運轉且224例題

16、例題離散數學離散數學編輯ppt21注意：注意：（1）自然語言中的表示自然語言中的表示“并且并且”意思的聯結詞，如意思的聯結詞，如“既既又又”、“不但不但而且而且”、“雖然雖然但是但是”、“一面一面一面一面”等都可以符號化為等都可以符號化為 。 （2） 合取的概念與自然語言中的合取的概念與自然語言中的“與與”意義類似，但并不意義類似，但并不完全相同。尤其例完全相同。尤其例2在自然語言中是沒有意義的，但在數在自然語言中是沒有意義的，但在數理邏輯中仍能成為一個新的命題。理邏輯中仍能成為一個新的命題。 （3）不要見到不要見到“與與”或或“和和”就使用聯結詞就使用聯結詞 ！ 例如：甲與乙是同學。例如：甲

17、與乙是同學。 這里的這里的“與與”不是合取。不是合取。離散數學離散數學編輯ppt22（3）析取聯結詞）析取聯結詞定義定義 設設P,Q為二命題，復合命題為二命題，復合命題“P或或Q” 稱為稱為P與與Q的析取式，記作的析取式，記作P Q，符號，符號稱為析取稱為析取聯結詞。聯結詞。運算規則：屬于二元運算符運算規則：屬于二元運算符析取運算特點：析取運算特點：只有參與運算的只有參與運算的二命題全為假時，二命題全為假時，運算結果才為假，運算結果才為假，否則為真。否則為真。離散數學離散數學編輯ppt23 析取運算只能表示自然語言中的析取運算只能表示自然語言中的“相容相容或或”(亦稱亦稱“可兼或可兼或”，用它

18、聯結的命題具有相，用它聯結的命題具有相容性容性)的意思的意思 不能表示自然語言里的不能表示自然語言里的“排斥或排斥或” 還有一些漢語中的還有一些漢語中的“或或”不是命題聯結詞。不是命題聯結詞。注意注意: 離散數學離散數學編輯ppt24例如：火車例如：火車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

19、F F T F離散數學離散數學編輯ppt25（1）小王愛打球或愛跑步。）小王愛打球或愛跑步。 （可兼或）（可兼或） 設設P：小王愛打球。：小王愛打球。 Q：小王愛跑步。：小王愛跑步。 則上述命題可符號化為：則上述命題可符號化為：P Q（2）今晚我在家看電視或去影院看電影）今晚我在家看電視或去影院看電影 （排斥或）（排斥或） (P Q) (PQ) （3）他昨天做了二十或三十道習題。）他昨天做了二十或三十道習題。 “或或” 只是表示的習題的近似數目。原子命題只是表示的習題的近似數目。原子命題例如：例如：離散數學離散數學編輯ppt26（4）條件聯結詞）條件聯結詞定義定義 設設P,Q為二命題，復合命題

20、為二命題，復合命題“如果如果P，則，則Q” 稱為稱為P與與Q的蘊涵式，記作的蘊涵式，記作P Q，即，即“如果如果P，則，則Q”，“若若P則則Q”。并稱。并稱P為前件，為前件，Q為后件，符號為后件，符號稱為蘊涵聯結詞。稱為蘊涵聯結詞。運算規則：屬于二元運算符運算規則：屬于二元運算符 P QPQ T T T T F F F T T F F T只有當只有當P的的真值為真值為T，Q的真值為的真值為F時，時， P Q的真值為的真值為F。否則均為否則均為T。離散數學離散數學編輯ppt27例題：例題：例例1：如果某動物為哺乳動物，則它必胎生。如果某動物為哺乳動物，則它必胎生。例例2：如果我得到這本小說，那末

21、我今夜就讀完如果我得到這本小說，那末我今夜就讀完它。它。例例3：如果雪是黑的，那么太陽從西方出。如果雪是黑的，那么太陽從西方出。離散數學離散數學編輯ppt28（1）自然語言中可用自然語言中可用P Q蘊涵式表述命題格式有蘊涵式表述命題格式有“只要只要P P，就就Q”“Q”“因為因為P P，所以，所以Q”Q”、“只有只有Q才才P”、“P僅當僅當Q”（P成立，成立，Q就成立）、就成立）、“除非除非Q才才P”、“除非除非Q，否則非，否則非P”、“Q是是P的必要條件的必要條件”等。等。（2）與自然語言的不同：前件與后件可以沒有任何內在聯系！）與自然語言的不同：前件與后件可以沒有任何內在聯系！（3）在數學

22、或其他自然科學中，往往是）在數學或其他自然科學中，往往是P為真為真 Q也為真的推理關系。但也為真的推理關系。但在數理邏輯中，作為一種規定，當在數理邏輯中，作為一種規定，當P為假時，無論為假時，無論Q如何，如何， P Q均均為真。（善意的推定）為真。（善意的推定） 注意：注意：離散數學離散數學編輯ppt29（5）雙條件聯結詞）雙條件聯結詞 定義定義 設設P,Q為二命題，復合命題為二命題，復合命題“P當且僅當當且僅當Q” 稱為稱為P與與Q的等價式，記作的等價式，記作P Q，符號，符號 稱為等價聯結詞。稱為等價聯結詞。運算規則：屬于二元運算符運算規則：屬于二元運算符 P QP Q T T T T F

23、 F F T F F F T當當P和和Q的真的真值相同時，值相同時，P Q的真的真值為值為T；否則；否則為為F。離散數學離散數學編輯ppt30說明：說明：雙條件命題也可以不顧因果關系，只根據雙條件命題也可以不顧因果關系，只根據聯結詞的定義確定真值。聯結詞的定義確定真值。例例1：兩個三角形全等，當且僅當它們的三組對兩個三角形全等，當且僅當它們的三組對應邊相等。應邊相等。 例例2：燕子飛回南方，當且僅當春天來了。燕子飛回南方，當且僅當春天來了。 例例3： 22=4當且僅當雪是白的。當且僅當雪是白的。離散數學離散數學編輯ppt31小結：小結：n以上以上5種最基本、最常用、最重要的聯結詞可以種最基本、

24、最常用、最重要的聯結詞可以組成一個集合組成一個集合，成為一，成為一個聯結詞集。由后四種組成的命題是復合命題，個聯結詞集。由后四種組成的命題是復合命題，亦可被多次使用，如亦可被多次使用，如（P Q） R；n復合命題的真值，取決于原子命題的真值，與復合命題的真值，取決于原子命題的真值，與原子命題之間是否有關系無關，與復合命題本原子命題之間是否有關系無關，與復合命題本身內容、含義無關；身內容、含義無關；n、 具有對稱性，具有對稱性， 、沒有；沒有；n連接詞具有運算和操作性，從已知命題得到新連接詞具有運算和操作性，從已知命題得到新命題。命題。離散數學離散數學編輯ppt32 1-3 命題公式與翻譯命題公

25、式與翻譯內內 容：容： 合式公式合式公式 命題翻譯命題翻譯重點難點：重點難點：命題翻譯命題翻譯離散數學離散數學編輯ppt33合式公式合式公式wff命題公式：命題公式：將命題變元用聯結詞和圓括號按一定將命題變元用聯結詞和圓括號按一定的邏輯關系聯結起來的有意義的符號串。的邏輯關系聯結起來的有意義的符號串。例如：例如： PQ，P （QP）說明：說明：命題公式是沒有真假值的。僅當命題變元命題公式是沒有真假值的。僅當命題變元用確定命題代入時，才得到一個命題。命題的用確定命題代入時，才得到一個命題。命題的真值依賴于代換變元的那些命題真值。真值依賴于代換變元的那些命題真值。 離散數學離散數學編輯ppt34定義定義1-2-1 合式公式是由下列規則形成的字符串：合式公式是由下列規則形成的字符串： （1）單個命題變元本身是一個合式公式。）單個命題變元本身是一個合式公式。 （2）如果）如果A是合式公式，那么是合式公式，那么A是合式公式。是合式公式。 （3）如果）如果A和和