離散數(shù)學(xué)－邏輯和證明ppt課件

1、離散數(shù)學(xué)邏輯離散數(shù)學(xué)邏輯黃曉宇黃曉宇HuangSirchinaHuangSirchina能力要求n三大能力三大能力n邏輯推理能力邏輯推理能力n算法分析與設(shè)計能力算法分析與設(shè)計能力n表達(dá)與編程能力表達(dá)與編程能力內(nèi)容要求n邏輯與證明邏輯與證明n算法算法n計數(shù)方法計數(shù)方法n遞歸遞歸n樹樹n網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型本講內(nèi)容n命題命題n命題邏輯命題邏輯n邏輯聯(lián)接詞邏輯聯(lián)接詞n真值表真值表命題邏輯電路化簡rqp命題邏輯電路化簡二）XYZ000010100111與電路與電路或電路或電路XYZXYZXYZ000011101111命題邏輯電路化簡三）rqprqpPQRO0000001001000110100010111

2、1011111命題邏輯推理知：（知：（1 1如果今天是星期一，則要進(jìn)行英語或離散數(shù)學(xué)考如果今天是星期一，則要進(jìn)行英語或離散數(shù)學(xué)考試；（試；（2 2如果英語老師有會，則不考英語；（如果英語老師有會，則不考英語；（3 3今天是今天是星期一，英語老師有會。星期一，英語老師有會。（1 1）考英語或離散數(shù)學(xué)考英語或離散數(shù)學(xué)今天是星期一今天是星期一英語老師有會英語老師有會（2 2）不考英語不考英語考離散數(shù)學(xué)考離散數(shù)學(xué)小結(jié)n使用自然語言表述的存在問題使用自然語言表述的存在問題n能否有一種語言，具有：能否有一種語言，具有：n高度的抽象性高度的抽象性n強(qiáng)大的表達(dá)能力強(qiáng)大的表達(dá)能力n完善的公理集合完善的公理集合命

3、題邏輯n命題邏輯也稱命題演算或語句演算，命題邏輯也稱命題演算或語句演算，它研究由命題為基本單位構(gòu)成的前它研究由命題為基本單位構(gòu)成的前提和結(jié)論之間的可推導(dǎo)關(guān)系提和結(jié)論之間的可推導(dǎo)關(guān)系n組成：命題組成：命題n研究對象：推導(dǎo)關(guān)系研究對象：推導(dǎo)關(guān)系命題n命題命題(Proposition)(Proposition)，是指具有真假意義的，是指具有真假意義的單句或復(fù)句，命題通常都是陳述句單句或復(fù)句，命題通常都是陳述句n命題是能夠確定或能夠分辨其真假的陳命題是能夠確定或能夠分辨其真假的陳述句，且真或假二者必居其一，也只居述句，且真或假二者必居其一，也只居其一。簡言之，命題非真必假。其一。簡言之，命題非真必假。

4、n例例1 1：P1 (a)P1 (a)(e)(e)n例例2 2：在引例：在引例2 2中，有哪些命題？中，有哪些命題？命題二）n一個命題的真或假稱為命題的真值，一個命題的真或假稱為命題的真值，簡稱值，真用簡稱值，真用T(True)T(True)或或1 1表示；假用表示；假用F(False)F(False)或或0 0表示表示n由于命題只有真、假二個真值，所以由于命題只有真、假二個真值，所以命題邏輯也稱二值邏輯命題邏輯也稱二值邏輯命題三）n應(yīng)該注意，一個陳述句能否分辨真假，應(yīng)該注意，一個陳述句能否分辨真假，與是否知道它的真假，是兩件事與是否知道它的真假，是兩件事: :n大學(xué)城共有大學(xué)城共有30013

5、30013人人n我所說的是假的我所說的是假的n在數(shù)理邏輯中，不能去糾纏各種具體命在數(shù)理邏輯中，不能去糾纏各種具體命題的真假問題，而是將命題當(dāng)成數(shù)學(xué)概題的真假問題，而是將命題當(dāng)成數(shù)學(xué)概念來處理，看成一個抽象的形式化的概念來處理，看成一個抽象的形式化的概念，把命題定義成非真必假的陳述句。念，把命題定義成非真必假的陳述句。命題的表示n一個原子命題，一般用大寫字母或帶下一個原子命題，一般用大寫字母或帶下標(biāo)的大寫字母，如標(biāo)的大寫字母，如P, Q, R,P, Q, R,或或Pi, Qi, Pi, Qi, Ri ,Ri ,等表示，把表示原子命題的符號，等表示，把表示原子命題的符號，稱為命題標(biāo)識符，簡稱命題符

6、稱為命題標(biāo)識符，簡稱命題符nP:P:今天是星期一今天是星期一nQ:Q:英語老師有會英語老師有會n邏輯聯(lián)接詞n邏輯聯(lián)結(jié)詞或命題聯(lián)結(jié)詞的簡稱，它邏輯聯(lián)結(jié)詞或命題聯(lián)結(jié)詞的簡稱，它是自然語言中連詞的邏輯抽象是自然語言中連詞的邏輯抽象. . 有了聯(lián)有了聯(lián)結(jié)詞，便可以用它和原子命題構(gòu)成復(fù)結(jié)詞，便可以用它和原子命題構(gòu)成復(fù)合命題合命題n邏輯聯(lián)接詞種類：否認(rèn)、合取、析取、邏輯聯(lián)接詞種類：否認(rèn)、合取、析取、條件、等價條件、等價否認(rèn)(Negation)， PPTFFT合取(Conjunction)，PQP QT T TTFFFTFFFF析取(Disjunction)，PQP QT T TTFTFTTFFF判斷真假P

7、Q命題真假命題真假今天是星期一今天是星期一考英語考英語今天是星期一今天是星期一不考試不考試今天星期二今天星期二考離散數(shù)學(xué)考離散數(shù)學(xué)今天星期二今天星期二學(xué)生放假學(xué)生放假如果今天是星期一，則要進(jìn)行英語或離散數(shù)學(xué)考試如果今天是星期一，則要進(jìn)行英語或離散數(shù)學(xué)考試P：今天是星期一：今天是星期一Q：今天考了英語或離散數(shù)學(xué)：今天考了英語或離散數(shù)學(xué)TTTF判斷真假二）n句型解讀：如果P則QPQ）n若P成立，則僅當(dāng)Q成立時為Tn若P不成立，則為T緣由？）邏輯蘊(yùn)含(Implication)，命題PQ,讀作“P條件Q或“如果P,則Q”。PQP QT T TTFFFTTFFTPQ P Q邏輯等價(logically

8、equivalent)，PQ命題真假命題真假今天是星期五今天是星期五今天離數(shù)提問今天離數(shù)提問今天是星期五今天是星期五今天沒離數(shù)今天沒離數(shù)今天星期二今天星期二今天離數(shù)提問今天離數(shù)提問今天星期二今天星期二今天沒離數(shù)今天沒離數(shù)每星期只在周五上離散數(shù)學(xué)，每次離散數(shù)學(xué)都提問。每星期只在周五上離散數(shù)學(xué)，每次離散數(shù)學(xué)都提問。P：今天是星期五：今天是星期五Q：今天離散數(shù)學(xué)提了問題：今天離散數(shù)學(xué)提了問題TFTF邏輯等價二）n定義：定義：P12 P12 定義定義.10nDe MorganDe Morgan邏輯定律邏輯定律n (P1 P2 Pn) (P1 P2 Pn) P1 P2 P1 P2 Pn

9、 Pnn (P1 P2 Pn) (P1 P2 Pn) P1 P2 P1 P2 Pn Pnn例例1 1：今天沒有人逃課。：今天沒有人逃課。n例例2 2：今天有人逃課。：今天有人逃課。邏輯等價三）PQP QT T TTFFFTFFFT邏輯等價四）P Q？(PQ) (Q P) (PQ) (Q P) (P Q) ( Q P) 真值表n對于命題公式對于命題公式 A A中每個命題變元，任給一中每個命題變元，任給一個指派個指派S(P)S(P)得到一種真值的組合得到一種真值的組合S(P1)S(P1)，S(P2)S(P2)，S(Pn)S(Pn)，稱為，稱為A A的一個真值指派，的一個真值指派，記為記為S(A)S(A)。若。若S(A)S(A)為為T T，稱，稱S(A)S(A)為為A A的真指派。的真指派。n設(shè)設(shè)A A為一命題公式，對其中出現(xiàn)