《離散數(shù)學(xué)》PPT課件(全).ppt

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

1、離散數(shù)學(xué)計(jì)算機(jī)科學(xué)系授課教師：王靜1引言1為什么學(xué)習(xí)離散數(shù)學(xué)？離散數(shù)學(xué)是現(xiàn)代數(shù)學(xué)的一個(gè)重要分支，是計(jì)算機(jī)科學(xué)與技術(shù)的理論基礎(chǔ)，所以又稱為計(jì)算機(jī)數(shù)學(xué)，是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的核心、骨干課程。離散數(shù)學(xué)是什么課？它以研究離散量的結(jié)構(gòu)和相互間的關(guān)系為主要目標(biāo)，其研究對(duì)象一般是有限個(gè)或可數(shù)個(gè)元素，因此它充分描述了計(jì)算機(jī)科學(xué)離散性的特點(diǎn)。離散數(shù)學(xué)的主要內(nèi)容是什么？內(nèi)容包含：數(shù)理邏輯、集合論、代數(shù)結(jié)構(gòu)與布爾代數(shù)、圖論等。離散數(shù)學(xué)是隨著計(jì)算機(jī)科學(xué)的發(fā)展而逐步建立的，它形成于七十年代初期，是一門新興的工具性學(xué)科。2

2、引言2學(xué)習(xí)該課程的目的：一方面，它給后繼課，如數(shù)據(jù)結(jié)構(gòu)、編譯系統(tǒng)、操作系統(tǒng)、數(shù)據(jù)庫原理、軟件工程與方法學(xué)、計(jì)算機(jī)網(wǎng)絡(luò)和人工智能等，提供必要的數(shù)學(xué)基礎(chǔ)；另一方面，通過學(xué)習(xí)離散數(shù)學(xué)，可以培養(yǎng)和提高自己的抽象思維和邏輯推理能力，為以后的軟、硬件學(xué)習(xí)和研究開發(fā)工作，打下堅(jiān)實(shí)的數(shù)學(xué)基礎(chǔ)。3引言3教學(xué)要求：通過該課程的學(xué)習(xí)，學(xué)生應(yīng)當(dāng)了解并掌握計(jì)算機(jī)科學(xué)中普遍采用的離散數(shù)學(xué)中的一些基本概念、基本思想、基本方法。自學(xué)要求：通過反復(fù)看書及做課后習(xí)題，來加深對(duì)該課程中的一些基本概念的理解，逐步提高自己的抽象思維和邏輯

3、推理能力。4第一章命題邏輯數(shù)理邏輯是研究推理（即研究人類思維的形式結(jié)構(gòu)和規(guī)律）的科學(xué)，起源于17世紀(jì)，它采用數(shù)學(xué)符號(hào)化的方法，因此也稱為符號(hào)邏輯。從廣義上講，數(shù)理邏輯包括四論、兩演算——即集合論、模型論、遞歸論、證明論和命題演算、謂詞演算，但現(xiàn)在提到數(shù)理邏輯，一般是指命題演算和謂詞演算。本書也只研究這兩個(gè)演算。5數(shù)理邏輯的創(chuàng)始人是Leibniz，為了實(shí)現(xiàn)把推理變?yōu)檠菟愕南敕ǎ褦?shù)學(xué)引入了形式邏輯。其后，又經(jīng)多人努力，逐漸使得數(shù)理邏輯成為一門專門的學(xué)科。上個(gè)世紀(jì)30年代以后，數(shù)理邏輯進(jìn)入一個(gè)嶄新的

4、發(fā)展階段，邏輯學(xué)不僅與數(shù)學(xué)結(jié)合，還與計(jì)算機(jī)科學(xué)等密切關(guān)聯(lián)。1931年Godel不完全性定理的提出，以及遞歸函數(shù)可計(jì)算性的引入，促使了1936年tUring機(jī)的產(chǎn)生，十年后，第一臺(tái)電子計(jì)算機(jī)問世。第一章命題邏輯6數(shù)理邏輯與計(jì)算機(jī)學(xué)、控制論、人工智能的相互滲透推動(dòng)了其自身的發(fā)展，模糊邏輯、概率邏輯、歸納邏輯、時(shí)態(tài)邏輯等都是目前比較熱門的研究領(lǐng)域。本篇我們只從語義出發(fā)，對(duì)數(shù)理邏輯中的命題演算與謂詞演算等作一簡單的、直接的、非形式化的介紹，將不涉及任何公理系統(tǒng)。第一章命題邏輯71.1命題符號(hào)化及聯(lián)結(jié)詞基本

5、概念命題：能夠判斷真假的陳述句。命題的真值：命題的判斷結(jié)果。真值只取兩個(gè)值：真、假。真命題：真值為真的命題。假命題：真值為假的命題。判斷命題的兩個(gè)步驟：1、是否為陳述句；2、是否有確定的、唯一的真值。8例1：判斷下列句子是否為命題。1、雪是白色的。2、2是偶數(shù)且3也是偶數(shù)。3、陳勝吳廣起義那天杭州下雨。4、大于2的偶數(shù)均可分解為兩個(gè)質(zhì)數(shù)的和（哥德巴赫猜想）。5、真舒服??！6、別的星球上有生物存在。7、您去學(xué)校嗎？8、x+y<09、我正在說謊。10、1+101=1101.1命題符號(hào)化及聯(lián)結(jié)詞91.1

6、命題符號(hào)化及聯(lián)結(jié)詞區(qū)別命題都是陳述句，但陳述句不都是命題。只有陳述句所表達(dá)的判斷結(jié)果是唯一確定的（正確的或錯(cuò)誤的），它才是命題。10命題及其真值的抽象化在本書中，用小寫英文字母p,q,r,…p1,p2,p3…等表示命題，用“1”、“0”分別表示真值的真、假。如：p：羅納爾多是球星。q：5是負(fù)數(shù)。p3：明天天氣晴。皆為符號(hào)化的命題，其真值依次為1、0、1或0。1.1命題符號(hào)化及聯(lián)結(jié)詞11命題的分類簡單/原子命題：由不能再分解為更簡單的陳述句的陳述句構(gòu)成。如上例中的命題。復(fù)合命題：由簡單命題通過聯(lián)結(jié)詞

7、聯(lián)結(jié)而成的陳述句。例2：1）3不是偶數(shù)。2）2是素?cái)?shù)和偶數(shù)。3）林芳學(xué)過英語或日語。1.1命題符號(hào)化及聯(lián)結(jié)詞121.1命題符號(hào)化及聯(lián)結(jié)詞命題常項(xiàng)或常元：真值是唯一確定的即：0，1命題變項(xiàng)或變?cè)赫嬷凳遣淮_定的即：p，q，r區(qū)別命題與命題變項(xiàng)含義是不同的，命題指具體的陳述句，是有確定的真值，而命題變項(xiàng)的真值不定，只當(dāng)將某個(gè)具體命題代入命題變項(xiàng)時(shí)，命題變項(xiàng)化為命題，方可確定其真值。131.1命題符號(hào)化及聯(lián)結(jié)詞命題與命題變項(xiàng)象程序語言中常量與變量的關(guān)系一樣。例：5是一個(gè)常量，是一個(gè)確定的數(shù)字，而x是一個(gè)

8、變量，賦給它一個(gè)什么值它就代表什么值，即x的值是不定的。例3：判斷下列句子是否為命題？1．張校長的頭發(fā)有一萬根。2．我所說的是假的。（是）（否）14常用聯(lián)結(jié)詞1.否定詞設(shè)p為命題，復(fù)合命題“非p”（或“p的否定”）稱為p的否定式，記作?p，符號(hào)?稱為否定聯(lián)結(jié)詞。運(yùn)算規(guī)則：p?p10011.1命題符號(hào)化及聯(lián)結(jié)詞152.合取詞設(shè)p,q為二命題，復(fù)合命題“p并且q”（或“p與q”）稱為p與q的合取式，記作p∧q，符號(hào)∧稱為合取聯(lián)結(jié)詞。運(yùn)算規(guī)則：pqp∧q0000101001111.1命題