北大離散數(shù)學(xué)ppt課件.ppt

《北大離散數(shù)學(xué)ppt課件.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、離散數(shù)學(xué)主講教師:鄒復(fù)民離散數(shù)學(xué)是現(xiàn)代數(shù)學(xué)的一個重要分支。是計算機科學(xué)中基礎(chǔ)理論的核心課程，為計算機科學(xué)提供了有力的理論基礎(chǔ)和工具。離散數(shù)學(xué)的基本思想、概念和方法廣泛地滲透到計算機科學(xué)與技術(shù)發(fā)展的各個領(lǐng)域，而且其基本理論和研究成果更是全面而系統(tǒng)地影響和推動著其發(fā)展。離散數(shù)學(xué)的內(nèi)容十分豐富，最重要，最核心的是：數(shù)理邏輯、集合論、代數(shù)系統(tǒng)和圖論。本課程主要講授以上四個方面的內(nèi)容。數(shù)理邏輯簡介數(shù)理邏輯是用數(shù)學(xué)方法來研究推理的形式結(jié)構(gòu)和推理規(guī)律的數(shù)學(xué)學(xué)科，它與數(shù)學(xué)的其它分支、計算機科學(xué)、人工智能、語言學(xué)等學(xué)科均有密切的聯(lián)系。命題邏輯

2、和一階謂詞邏輯是數(shù)理邏輯中最成熟的部分，在計算機科學(xué)中應(yīng)用最為廣泛，其中命題邏輯是數(shù)理邏輯的最基礎(chǔ)部分，謂詞邏輯是在它的基礎(chǔ)上發(fā)展起來的。本課程在第一，二兩章中介紹數(shù)理邏輯的內(nèi)容。第一章命題邏輯第一節(jié)命題符號化及聯(lián)結(jié)詞內(nèi)容：命題，邏輯聯(lián)結(jié)詞，命題符號化(1)掌握命題概念(2)掌握聯(lián)結(jié)詞含義及真值表(3)掌握命題符號化方法重點：一、命題的概念命題：能判斷真假的陳述句。例1、判斷下列句子中哪些是命題。(1)北京是中國的首都。(2)雪是黑色的。(4)請把門關(guān)上！(6)地球外的星球上也有人。(3)。(5)是有理數(shù)。例1、判斷下列句

3、子中哪些是命題。(7)明天有課嗎？(8)本語句是假的。(9)小明和小林都是三好生。(10)小明和小林是好朋友。判斷一個語句是否為命題，首先看是否為陳述句，再看其真值是否唯一。表示。命題常項，命題變項均用二、邏輯聯(lián)結(jié)詞。這五種常用的聯(lián)結(jié)詞有真值表1、“非”稱為的否定式，記作例如：：11是素數(shù)；：11不是素數(shù)取值1，取值0。真值表2、“并且”稱為的合取式，記作。在例1.(9)中，：小明是三好生，：小林是三好生則小明和小林是三好生表示為。(1)李平既聰明又用功。(2)李平雖然聰明，但不用功。(3)李平不但聰明，而且用功。(4)李平

4、不是不聰明，而是不用功。例2、設(shè)：李平聰明，：李平用功。真值表3、“或者”稱的析取式，記作。例如，：小明學(xué)過英語，：小明學(xué)過日語，則小明學(xué)過英語或日語可表示為真值表：4、“如果那么”稱的蘊涵式，記作其中為前件，為后件。例3、一位父親對兒子說：“如果我去書店，就一定給你買本《兒童畫報》?！眴枺菏裁辞闆r下父親食言？解：可能情況有四種：(1)父親去了書店，給兒子買了《兒童畫報》。(2)父親去了書店，卻沒給兒子買《兒童畫報》。(3)父親沒去書店，卻給兒子買了《兒童畫報》。(4)父親沒去書店，也沒給兒子買《兒童畫報》。(1)如果天不下

5、雨，我就騎車上班。(2)只要天不下雨，我就騎車上班。(3)只有天不下雨，我才騎車上班。(4)除非天下雨，否則我就騎車上班。(5)如果天下雨，我就不騎車上班。(或)例4、：天下雨，：我騎車上班。真值表：5、“當(dāng)且僅當(dāng)”稱的等價式，記作。是的充要條件，也是的充要條件。例5、：，：3是奇數(shù)(1)當(dāng)且僅當(dāng)3是奇數(shù)。(2)當(dāng)且僅當(dāng)3不是奇數(shù)。(3)當(dāng)且僅當(dāng)3是奇數(shù)。(4)當(dāng)且僅當(dāng)3不是奇數(shù)。6、邏輯聯(lián)結(jié)詞與自然語言中聯(lián)結(jié)詞的關(guān)系。否定——不是，沒有，非，不。合取——并且，同時，和，既…又…，不但…而且…，雖然…但是…。析取——或者，或

6、許，可能。蘊涵——若…則…，假如…那么…，既然…那就…，倘若…就…。等價——當(dāng)且僅當(dāng)，充分必要，相同，一樣。7、運算順序邏輯聯(lián)結(jié)詞也稱邏輯運算符，規(guī)定優(yōu)先級的順，若有括號時，先進(jìn)行括號序為內(nèi)運算。例如：三、命題符號化。步驟：(1)找出各簡單命題，分別符號化。(2)找出各聯(lián)結(jié)詞，把簡單命題逐個聯(lián)結(jié)起來。例6、將下列命題符號化。(1)小王是游泳冠軍或百米賽跑冠軍。(2)小王現(xiàn)在在宿舍或在圖書館。：小王是游泳冠軍，：小王是百米賽跑冠軍。設(shè)原語句化為。：小王在宿舍，：小王在圖書館。設(shè)原語句化為。例6、將下列命題符號化。(3)選小王或

7、小李中的一人當(dāng)班長。(4)如果我上街，我就去書店看看，除非我很累。：選小王當(dāng)班長，：選小李當(dāng)班長。設(shè)原語句化為。：我上街，：我很累。：我去書店看看，設(shè)原語句化為)。(或(5)小麗是計算機系的學(xué)生，她生于1982或1983年，她是三好生。：小麗是計算機系的學(xué)生，：小麗生于1982年，：小麗生于1983年，：小麗是三好生。設(shè)原語句化為。第二節(jié)命題公式及分類內(nèi)容：命題公式，重言式，矛盾式，可滿足公式。重點：(1)掌握命題公式的定義及公式的真值表。(2)掌握重言式和矛盾式的定義及使用真值表進(jìn)行判斷。一、命題公式通俗地說，命題公式是由

8、命題常項，命題變項，聯(lián)結(jié)詞，括號等組成的字符串。規(guī)定：公式中最外層的括號，及的括號可省略。例1、判斷以下字符串中哪些是命題公式。(1)(2)(3)(4)(5)(6)解：(1)、(2)、(6)是公式，(3)、(4)、(5)不是。2、命題公式的層次。5例2、為___層公式。若的最高層次為，則稱