離散數(shù)學（第3版）課件ch1(1) 命題邏輯1.1-1.4 賁

1

美國數(shù)學家柯朗在《數(shù)學是什么》一書中的說：“數(shù)學，作為人類智慧的一種表達形式，反映生動活潑的意念，深入細致的思考，以及完美和諧的愿望，它的基礎是邏輯和直覺，分析和推進，共性和個性?！?/p>

法國數(shù)學家龐加萊：“數(shù)學是給予不同的東西以相同的名稱的技術?！?“數(shù)學的貢獻在于對整個科學技術（尤其是高新科技）水平的推進與提高，對科技人才的培育和滋潤，對經(jīng)濟建設的繁榮，對全體人民的科學思維與文化素質的哺育，這四方面的作用是極為巨大的，也是其他學科所不能全面比擬的?！保ㄍ蹊骼ぃ?shù)學的意義張恭慶(北京大學數(shù)學科學學院教授、中國科學院院士、第三世界科學院院士）一、世界強國與數(shù)學強國

二、數(shù)學及其基本特征

三、數(shù)學與當代科學技術

（一）數(shù)學與科學革命和技術革命

（二）數(shù)學與自然科學

（三）數(shù)學與社會科學

（四）數(shù)學與數(shù)據(jù)科學

（五）數(shù)學與技術科學

四、數(shù)學與國防

五、數(shù)學與國民經(jīng)濟

六、數(shù)學與文化教育

561Algorithms,Numbers,andMachines2Sets,Sequences,andCounting3BooleanExpressions,Logic,andProof4SearchingandSorting5GraphsandTrees6Relations:Especiallyon(Integer)Sequences7SequencesandSeries8GeneratingSequencesandSubsets9DiscreteProbabilityandAverage-CaseComplexity10TuringMachines7一、學科專業(yè)整體介紹二、什么是離散數(shù)學三、離散數(shù)學的主要內容四、離散數(shù)學的發(fā)展史五、學習離散數(shù)學的作用和目的六、課程特點與教學要求課程介紹8計算機科學與技術一、學科專業(yè)整體介紹9二、什么是離散數(shù)學

離散數(shù)學是一門重要理論基礎課，它所研究的對象是離散的數(shù)學關系和離散的數(shù)學結構模型。通過例子理解“離散數(shù)學”（1）**是***；**不是***（2）帽子問題。甲乙丙3人，5頂帽子（3紅2白）（3）三叉路口問題。（4）家庭舞會。（5）火柴游戲。（6）九宮圖問題。10一副牌隨便你攔腰斬，斬了很多次之后，把前面的五張拿出來，分別發(fā)給5個人，然后魔術師心靈感應一下，就可以知道這五張牌是什么。魔術師請拿紅牌的人幫一個忙，往前走一步。例如，魔術師知道這五張牌的紅黑順序是“黑紅黑紅紅”，然后魔術師就可以心靈感應出這五張牌是（

）。請問這其中的奧秘是什么呢？11

金銀銅小像不在這只匣里小像在這只匣里小像不在金匣里

金銀銅小像放在某一匣中。這3個陳述中至多有一個為真。問小像在哪一匣中？小像不在銀匣里小像不在這只匣里小像在這只匣里小像放在某一匣中。這3個陳述中至少一真、至少一假。問小像在哪一匣中？12三、離散數(shù)學的主要內容數(shù)理邏輯集合論圖論代數(shù)結構教材：《離散數(shù)學（第3版）》，2021清華大學出版社，高等學校計算機教育規(guī)劃教材作者：賁可榮、袁景凌、謝茜《離散數(shù)學解題指導（第2版）》，2016清華大學出版社，作者：賁可榮、袁景凌、高志華13四、離散數(shù)學的發(fā)展史主要從四方面介紹。參考教材的附錄。14為學習各專業(yè)課程作必要的數(shù)學準備；培養(yǎng)學生的學習能力、邏輯推理能力、抽象思維能力，提高學生綜合素質。五、學習離散數(shù)學的作用和目的15面向不同培養(yǎng)目標的離散數(shù)學定位培養(yǎng)類型科學型工程型應用型培養(yǎng)要求基礎理論和核心技術研究；原始創(chuàng)新基本理論與原理的綜合應用（創(chuàng)新性應用）計算機應用人才人才定位學術研究IT企事業(yè)應用領域信息化人才培養(yǎng)人數(shù)少較多多離散數(shù)學的基礎熟練掌握形式描述、變換、推理和證明方法；熟練掌握離散系統(tǒng)的描述與分析方法；了解實際離散系統(tǒng)的建模熟悉形式描述、變換、推理和證明方法；熟練掌握離散系統(tǒng)的描述與分析方法；了解實際離散系統(tǒng)的建模簡要了解形式描述、變換、推理和證明方法；掌握離散系統(tǒng)描述與分析方法；熟悉常用的實際離散系統(tǒng)模型涉及其他專業(yè)課算法與數(shù)據(jù)結構、數(shù)據(jù)庫系統(tǒng)原理、操作系統(tǒng)、編譯原理、軟件工程、人工智能、數(shù)字邏輯、計算機網(wǎng)絡算法與數(shù)據(jù)結構、數(shù)據(jù)庫系統(tǒng)原理、操作系統(tǒng)、編譯原理、軟件工程、數(shù)字邏輯、計算機網(wǎng)絡數(shù)據(jù)結構與算法、數(shù)據(jù)庫與信息管理技術、計算機網(wǎng)絡與互聯(lián)網(wǎng)學時安排建議學時：72-108建議學時：72-90建議學時：51-7216課程特點：內容繁多定義定理多抽象思維性強教學要求：適當?shù)刈龉P記注意預習復習獨立完成作業(yè)六、課程特點與教學要求教學時數(shù)：171.1現(xiàn)代邏輯學的基本研究方法1.2命題及其表示法1.3命題公式與語句形式化1.4重言式1.5對偶與范式1.6其他聯(lián)結詞1.7命題演算的推理理論1.8命題演算中的歸結推理命題邏輯第1章181.1現(xiàn)代邏輯學

邏輯學的發(fā)展歷史現(xiàn)代邏輯學的主要內容邏輯與計算機科學的聯(lián)系19邏輯發(fā)展歷史——三個階段初始階段：1660年代—19世紀末，數(shù)學應用于邏輯。Aristotle：形式邏輯（主詞和謂詞邏輯）Leibniz(1646-1716)

：建立直觀而又精確的思維演算作為數(shù)理邏輯的創(chuàng)始人，建立一個“普遍的符號語言”“思維的演算”，成功地將命題形式表達為符號公式，構成了一個關于兩個概念相結合的演算。

GeorgeBoole(1815-1864)

:邏輯代數(shù)DeMorgan(1806-1871)

:關系邏輯過渡階段：成熟階段：20邏輯發(fā)展歷史——三個階段初始階段：過渡階段：19世紀末—1940前后，邏輯應用于數(shù)學。非歐幾何與公理化方法微積分與實數(shù)理論，Piano算術

GiuseppePePeano(1858-1932)

集合論與數(shù)學基礎(1900年世界數(shù)學家大會)悖論與第三次數(shù)學危機，Hilbert（1862～1943）計劃成熟階段21邏輯發(fā)展歷史——三個階段初始階段：過渡階段：成熟階段：1930s—1970年，成為數(shù)學的獨立分支。KurtG?del(1906-1978)1930年發(fā)表的完全性定理說明了，形式系統(tǒng)可以從一階邏輯演算得到足夠的基本邏輯工具。G?del于1931年的論文證明了公理化方法有局限性。G?del不完全性定理：對任何一個包含Peano算術的有窮形式化的公理系統(tǒng)而言，必定存在一個明確定義的命題，在該系統(tǒng)中既不能證明它是真的，也不能證明它是假的。22現(xiàn)代邏輯學求助數(shù)學——符號化現(xiàn)代邏輯學追隨數(shù)學——公理化現(xiàn)代邏輯學改造數(shù)學——形式化現(xiàn)代邏輯學的主要內容

現(xiàn)代邏輯學包括：命題邏輯、謂詞邏輯、模態(tài)邏輯、時序邏輯、動態(tài)邏輯、多值邏輯、模糊邏輯等。23邏輯與計算機科學的聯(lián)系數(shù)字電路：布爾邏輯。計算理論：可計算性，Turing機，形式語言，自動機，計算復雜性。程序語義與驗證技術。程序的自動生成與轉換。SQL:本質上等價于一階邏輯。Prolog語言：以邏輯演算為基礎。LISP語言：以λ演算為基礎。人工智能。信息安全?！?4（從知道問題看推理）老師手中握有一副牌（黑桃5、4、8、J；紅心A、Q、4；◆A、5；梅花K、Q、5、4），我想好一張牌，并將該牌的花色告訴學生甲，將該牌的點數(shù)告訴學生乙。甲說：我敢肯定你不知道這張牌。乙說：那么我現(xiàn)在知道了。甲說：那么我也知道了。請問這張牌是什么牌？251.1現(xiàn)代邏輯學的基本研究方法1.2命題及其表示法1.3命題公式與語句形式化1.4重言式1.5對偶與范式1.6其他聯(lián)結詞1.7命題演算的推理理論1.8命題演算中的歸結推理命題邏輯第1章261.2命題及其表示法思考題：相傳在古代有一個殘酷的國王，為了不準別人進入他的領地而制定了一個法規(guī)：“凡進入者若講真話則殺頭，若講假話則淹死”。并要求士兵嚴格執(zhí)行上述命令。一天，一個人進來說了一句話，導致士兵無法執(zhí)行命令。請問這個人說了什么？一、命題的定義27例1判斷下列句子是否為命題。

(1)3是素數(shù)。

(2)2是無理數(shù)。

(3)x大于y。

(4)土星上有冰。

(5)2100年元旦是晴天。

(6)我正在說假話。

(7)請不要吸煙！

(8)這朵花真美麗?。?/p>

(9)3大于5嗎？符號化——命題一般用英文字母表示。定義1命題是一個可以判斷真假的陳述句。

28二、復合命題（1）4是偶數(shù)且是2的倍數(shù)。（2）武漢不是個小城市。（3）小王或小李考試得第一。（4）如果你努力，則你能成功。（5）三角形是等邊三角形，當且僅當三邊相等。

上述命題都是通過諸如“或”，“且”、“如果……，則……”等連詞聯(lián)結而成，這樣命題，稱為復合命題。相對地，構成復合命題的命題稱為簡單命題。那么，命題聯(lián)結詞用什么符號表示呢？29三、命題聯(lián)結詞定義2否定聯(lián)結詞┐設p為命題，復合命題“非p”(或“p的否定”)稱為p的否定式,記作┐p，符號┐稱作否定聯(lián)結詞。并規(guī)定┐p為真當且僅當p為假。30定義3合取聯(lián)結詞∧設p,q為二個命題，復合命題“p并且q”(或“p與q”)稱為p與q的合取式，記作p∧q，∧稱作合取聯(lián)結詞。并規(guī)定p∧q為真當且僅當p與q同時為真。31定義4析取聯(lián)結詞∨設p，q為二個命題，復合命題“p或q”稱作p與q的析取式，記作p∨q，∨稱作析取聯(lián)結詞。并規(guī)定p∨q為假當且僅當p與q同時為假。32定義5蘊涵聯(lián)結詞→設p，q為二個命題，復合命題“如果p，則q”稱作p與q的蘊涵式，記作p→q，→稱作蘊涵聯(lián)結詞。并規(guī)定p→q為假當且僅當p為真q為假。注意：在自然語言中，“如果p，則q”中的前件p與后件q往往具有某種內在聯(lián)系。而在數(shù)理邏輯中，p與q可以無任何內在聯(lián)系。33定義6等價聯(lián)結詞

設p，q為二命題，復合命題“p當且僅當q”稱作p與q的等價式，記作p

q，

稱作等價聯(lián)結詞。p

q的邏輯關系表示q是p的充分必要條件。341.1現(xiàn)代邏輯學的基本研究方法1.2命題及其表示法1.3命題公式與語句形式化1.4重言式1.5對偶與范式1.6其他聯(lián)結詞1.7命題演算的推理理論1.8命題演算中的歸結推理命題邏輯第1章351.3命題公式與語句形式化

一個賦予特定內容的命題的真值是確定的，只有“T”和“F”兩種，即命題常項或稱為命題常元。一個沒有任何意義的沒有賦予具體內容的命題是一個命題變元。一、命題公式的定義下面我們正式定義命題變元：定義：以“真”“假”為其值域的變元稱為命題變元。36定義(命題公式)(1)單個命題變元或命題常元是合式公式，并稱為原子命題公式。(2)若A是合式公式，則(┐A)也是合式公式。(3)若A，B是合式公式，則(A∧B)，(A∨B)，(A→B)，(A

B)也是合式公式。(4)只有有限次地應用(1)～(3)形式的符號串才是合式公式。

合式公式就是形式上合法的公式。well-formedformula,wff37(1)

P,Q,R是合式公式;(2)

若A是合式公式，則(┐A)也是合式公式;(3)

若A，B是合式公式，則(A∧B)，(A∨B)，(A→B)，(A

B)也是；(4)

沒有了。證明：（1）P,Q,R是wff（2）(P∧Q),(Q∨R)是wff（3）┐(Q∨R)是wff（4）((P∧Q)→(┐(Q∨R)))是wff證明((P∧Q)→(┐(Q∨R)))是wff。38

可用命題公式表示復合命題，常將這個過程稱為語句形式化，或命題的符號化，或稱為命題的翻譯。

命題的翻譯可按如下步驟進行：①找出復合命題中的簡單命題。②用英文字母表示這些簡單命題。③使用命題聯(lián)結詞將這些英文字母連接起來。二、語句形式化39例試翻譯下列命題。(1)這部分內容無趣,習題也不難,而且這門課程也不使人喜歡。(2)如果這部分內容無趣,或者習題難,

那么這門課程就不使人喜歡。(3)這部分內容有趣,意味著習題難,反之亦然。解：設P表示“這部分內容有趣”,Q表示“這些習題難”,R表示“這門課使人喜歡”,40例

用A表示“明天早晨七點下雨”,B表示“明天早晨七點刮風”,C表示“我去學?！?

試用A，B，C表示下列復合命題：(1)如果明天早晨七點下雨但不刮風，則我去學校；(2)如果明天早晨七點不下雨并且也不刮風，則我去學校；(3)如果明天早晨七點下雨或不刮風，則我去學校；(4)明天我風雨無阻，一定去學校；(5)只有當明天早晨七點不下雨并且也不刮風時，我才去學校；(6)只有當明天早晨七點下雨或刮風都不發(fā)生時，我才去學校。41三、真值表的構建定義

設p1,p2,…,pn是出現(xiàn)在公式A中的全部命題符號，給p1,p2,…,pn各指定一個真值，稱為對A的一個賦值或解釋。定義

在命題公式A中，對A的每一個賦值，就確定了A的一個真值，把它們匯列成表，稱該表為命題公式A

的真值表。42定義

設A和B是兩個命題公式，若對A和B的所有賦值，A和B的真值都相同，則稱A和B是邏輯等價的，記為A

B。例構建下列命題公式的真值表。(1)(p∧┐q)∨(┐p∧q)(2)┐(p→q)→p(3)(p∧┐q)∧┐p(4)┐

(p

q)43第1章命題邏輯1.1現(xiàn)代邏輯學1.2命題及其表示法1.3命題公式與語句形式化1.4重言式1.5對偶與范式1.6其他聯(lián)結詞1.7命題演算的推理理論1.8命題演算中的歸結推理441.4重言式定義1.11

設A為任一命題公式。若A在它的各種指派下取值均為真,則稱A是重言式(tautology)

或永真式。(2)若A在它的各種指派下取值均為假,則稱A是矛盾式(falsity)或永假式。(3)若A不是矛盾式,則稱A是可滿足式。

45定義1.12

設A和B是兩個命題公式，如果A

B是重言式，即A與B對任何指派都有相同的真值，則稱A與B邏輯等價(等值)，記為AB。46以下給出16組重要的命題等價式，其中A,B,C為命題變元。

1.雙重否定律

A

A2.冪等律

A

A∨A,A

A∧A3.交換律

A∨B

B∨A，A∧B

B∧A4.結合律

(A∨B)∨C

A∨(B∨C)(A∧B)∧C

A∧(B∧C)475.分配律

A∨(B∧C)

(A∨B)∧(A∨C)（∨對∧的分配律）

A∧(B∨C)

(A∧B)∨(A∧C)（∧對∨的分配律）6.德摩根律

(A∨B)

A∧

B，

(A∧B)

A∨

B7.吸收律

A∨(A∧B)

A，A∧(A∨B)

A

8.零律

A∨T

T,A∧F

F

489.同一律

A∨F

A，A∧T

A

10.排中律

A∨

A

T

11.矛盾律

A∧

A

F

12.蘊涵表達式

A→B

A∨B4913.等價表達式

(A

B)

(A→B)∧(B→A)14.假言易位

A→BB→┐A15.等價否定等價式

A

B

A

┐B

16.歸謬論

(A→B)∧(A→

B)

A50例用等值演算的方法驗證下列等價關系（1）(P→Q)→R

(Q∧P)∨R（2）P→(Q→R)

(P∧Q)→R51例用等值演算的方法判斷下列公式類型（1）Q∨((P∨Q)∧P)（2）(P∨P)→((Q∧Q)∧R)命題等價式

1.雙重否定律

A

A2.冪等律A

A∨A,A

A∧A3.交換律A∨B

B∨A，A∧B

B∧A4.結合律

(A∨B)∨C

A∨(B∨C)，(A∧B)∧C

A∧(B∧C)5.分配律