離散數(shù)學：第1章 命題邏輯基本概念

離散數(shù)學教材及參考書教材：

離散數(shù)學：屈婉玲，耿素云，張立昂，高等教育出版社參考書：

離散數(shù)學（第4版）：RichardJohnsonBaugh，電子工業(yè)出版社

離散數(shù)學：左孝凌，李為鑑，劉永才，上?？茖W技術(shù)文獻出版社

離散數(shù)學及其應用（第6版）：KennethH.Rosen，機械工業(yè)出版社2計算機科學與工程學院緒論：課程安排講授內(nèi)容：數(shù)理邏輯（第一、二、三、四、五章）集合論（第六、七、八章）代數(shù)結(jié)構(gòu)（第九、十章）成績構(gòu)成：

平時（作業(yè)、考勤）＋期末（無半期考試）

隨機點名，三次沒到者無成績作業(yè)：

每周三交作業(yè)3計算機科學與工程學院緒論：什么是離散數(shù)學研究離散量的結(jié)構(gòu)及相互關(guān)系的數(shù)學科學離散結(jié)構(gòu)：集合、關(guān)系、圖等

離散量是指分散開來的、不存在中間值的量研究對象:有限或可數(shù)個元素自然數(shù)、整數(shù)，真假值，有限節(jié)點等計算機技術(shù)的支撐科學：計算機只能處理離散的或離散化了的數(shù)量關(guān)系4計算機科學與工程學院緒論：學習意義

E.W.Dijkstra（荷蘭計算機科學家，提出了程序設(shè)計中常用的GOTO語句的三大危害；解決有向圖中最短路徑問題的Dijkstra算法）：

我現(xiàn)在年紀大了，搞了這么多年軟件，錯誤不知犯了多少，現(xiàn)在覺悟了。我想，假如我早年在數(shù)理邏輯上好好下點功夫的話，我就不會犯這么多的錯誤，不少東西邏輯學家早就說了，可我不知道。要是我能年輕二十歲的話，就要回去學邏輯。

學科意義：計算機科學技術(shù)的基礎(chǔ)和工具5計算機科學與工程學院緒論：離散數(shù)學與計算機科學數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)離散結(jié)構(gòu)數(shù)據(jù)庫原理軟件工程操作系統(tǒng)編譯原理人工智能可計算性理論……6計算機科學與工程學院緒論：數(shù)理邏輯邏輯學分類辯證邏輯：是研究事物發(fā)展的客觀規(guī)律形式邏輯：是研究思維的概念、判斷和推理的問題數(shù)理邏輯（又稱符號邏輯）數(shù)學方法研究形式邏輯的一門科學，使用符號數(shù)理邏輯創(chuàng)始人——萊布尼茲(Leibniz,1646-1716,德)現(xiàn)代數(shù)理邏輯：公理化集合論、模型論、遞歸函數(shù)論、證明論最基本組成內(nèi)容：命題演算、謂詞演算應用：邏輯電路、自動控制、人工智能等7計算機科學與工程學院第一部分數(shù)理邏輯■主要內(nèi)容命題邏輯基本概念

命題邏輯等值演算命題邏輯推理理論一階邏輯基本概念一階邏輯等值演算與推理8計算機科學與工程學院第1章命題邏輯基本概念命題與聯(lián)結(jié)詞命題及其分類聯(lián)結(jié)詞與復合命題命題公式及其賦值1.1命題與聯(lián)接詞命題：具有唯一真值陳述句

唯一性：或真或假但不能兩者都是的命題所用符號：常用小寫26個英文字母例子十是整數(shù)2100年人類將在月球生活x=3現(xiàn)在是幾點？1+1=2我現(xiàn)在說假話悖論！10計算機科學與工程學院1.1命題與聯(lián)接詞判斷下列語句是否為命題明天下雨加拿大是一個國家x+y>4注：命題是陳述句，陳述句不一定是命題命題有唯一真值，但真值可能受范圍、時空、環(huán)境、判斷標準、認識程度限制，一時無法確定11計算機科學與工程學院1.1命題與聯(lián)接詞命題分類簡單命題：不能被分解成更簡單的陳述句復合命題：簡單陳述句+聯(lián)接詞例子今天沒有天晴王華的成績很好并且品德很好小李是學數(shù)學或者計算機科學如果天下雨，那么地下濕12計算機科學與工程學院1.1命題與聯(lián)接詞否定聯(lián)接詞符號?,讀作“非”，“否定”定義：命題p

p的否定式：復合命題“p的否定”（“非p”）符號：

p

(符號稱作否定聯(lián)結(jié)詞)

p為真當且僅當p為假例子今天沒有天晴

p

p

：今天天晴ppTFFT13計算機科學與工程學院1.1命題與聯(lián)接詞合取聯(lián)接詞符號,讀作“合取”定義：命題p，q

p與q的合取式：復合命題“p并且q”

符號：pq(符號稱作合取聯(lián)結(jié)詞)

pq為真當且僅當p和q同時為真例子王華的成績很好并且品德很好pqp：王華的成績很好q：王華的品德很好pqpqFFFFTFTFFTTT14計算機科學與工程學院1.1命題與聯(lián)接詞析取聯(lián)接詞符號,讀作“析取”定義：命題p，q

p與q的析取式：復合命題“p或q”

符號：pq(符號稱作析取聯(lián)結(jié)詞)

pq為假當且僅當p和q同時為假例子小李是學數(shù)學或者計算機科學pqp：小李是學數(shù)學q：小李是學計算機科學pqpqFFFFTTTFTTTT15計算機科學與工程學院1.1命題與聯(lián)接詞析取聯(lián)接詞（相容或）≠“排斥或”排斥或：符號定義：命題p，q符號：pq等價于(pq)(pq)

pq為假當且僅當p和q同時為假或同時為真例子：小李在教室看書或在圖書館上網(wǎng)

小李在看書或者聽音樂（析取）pqpqFFFFTTTFTTTF16計算機科學與工程學院1.1命題與聯(lián)接詞蘊含聯(lián)接詞符號,讀作“如果…則…”、“蘊含”定義：命題p，q

p與q的蘊涵式：復合命題“如果p，則q”符號：pq(符號稱作蘊含聯(lián)結(jié)詞)

pq為假當且僅當p為真，q為假例子

如果天下雨，那么地下濕

pqp：天下雨q：地下濕pqpqFFTFTTTFFTTT17計算機科學與工程學院1.1命題與聯(lián)接詞更多關(guān)于蘊含聯(lián)接詞…pq：q是p的必要條件其他：pq的敘述方式：“只要p，就q”，“因為p，所以q”等

p為假，pq永遠為真如果給我一個支點，我能把

地球撬起來

區(qū)別于自然語言的“如果p,則q”p和q有內(nèi)在聯(lián)系pqpqFFTFTTTFFTTT18計算機科學與工程學院1.1命題與聯(lián)接詞更多例子如果天晴，則雪是白的

pq如果不天晴，則雪不是白的

pq（對給定正整數(shù)a）只要a能被4整除，則a能被2整除

pq19計算機科學與工程學院1.1命題與聯(lián)接詞給定命題pq它的逆命題qp它的反命題

pq它的逆反命題

qp各種命題關(guān)系

pq

qp

qppq20計算機科學與工程學院1.1命題與聯(lián)接詞等價式符號,讀作“當且僅當”定義：命題p，qp與q的等價式：復合命題“p當且僅當q”符號：pq(符號稱作等價聯(lián)結(jié)詞)pq為真當且僅當p與q真值相同例子

當且僅當a=2，才有a2=4pqp：a=2q：a2=4pqpqFFTFTFTFFTTT21計算機科學與工程學院1.1命題與聯(lián)接詞聯(lián)接詞的定義總結(jié)pqppqpqpqpqFFTFFTTFTTFTTFTFFFTFFTTFTTTT22計算機科學與工程學院1.1命題與聯(lián)接詞聯(lián)接詞的優(yōu)先級

、、、、括號最優(yōu)先同一優(yōu)先級：從左到右例子：求于命題pqr含義相同的命題((p)q)r((pq))rp(qr)(pqr)23計算機科學與工程學院1.1命題與聯(lián)接詞例：p：北京比天津人口多q：2＋2＝4r：烏鴉是白色的求下列命題真值((?p∧q)∨(p∧?q))→r(q∨r)→(p→?r)(?p∨r)(p∧?r)

TTF24計算機科學與工程學院1.1命題與聯(lián)接詞例子：符號化下面命題小強雖然不聰明，但很用功小李學過英語或者法語小李正在教室看書或在圖書館上網(wǎng)金無足赤，人無完人得道多助，失道寡助pqpq(pq)(pq)pq(pq)(pq)25計算機科學與工程學院1.1命題與聯(lián)接詞問題1：區(qū)別

x+y>4

明天下雨26計算機科學與工程學院1.1命題與聯(lián)接詞問題2：得道多助，失道寡助(pq)(pq)27計算機科學與工程學院1.1命題與聯(lián)接詞課堂練習：p：2+3=5q：大熊貓產(chǎn)在中國r：太陽從西部升起求下列命題真值

(r(pq))(pr)FFFTTTFF28計算機科學與工程學院1.2命題公式及其賦值

命題常項：簡單命題

命題變項：表示命題的變量真值可以變化的陳述句命題變項不是命題命題變項用確定命題代入才能確定真值命題變項所用符號：常用小寫26個英文字母命題變量不同于代數(shù)式的變量x+y>4的x，y不是命題變量29計算機科學與工程學院1.2命題公式及其賦值合式公式（命題公式）的遞歸定義：單個命題常項或命題變項是合式公式（原子命題公式）

A為合式公式，則A是合式公式

A，B為合式公式，則(AB),(AB),

(AB),(AB)為合式公式4.有限次應用1-3形成的字符串為合式公式

子公式B：給定合式公式AB是A的一部分B是合式公式30計算機科學與工程學院1.2命題公式及其賦值符號說明大寫字母A，B表示合式公式公式簡寫法則：公式最外層括號可以省略（A）的括號可以省略根據(jù)運算符優(yōu)先級省略括號

省略括號不能影響公式解釋31計算機科學與工程學院1.2命題公式及其賦值合式公式的樹狀展開

(AB)((C)(DC))ABAB(C)(DC)(C)DCCDC32計算機科學與工程學院1.2命題公式及其賦值例子(AB)C(pq)(qr)(B)pqr33計算機科學與工程學院1.2命題公式及其賦值公式層次若公式A是單個的命題變元，則稱A為0層合式稱公式Ａ是n+1(n≥0)層公式是指下面情況之一A＝?B，B是n層公式A＝BΛC，其中B，C分別為i層和j層公式，且n＝max(i,j)A＝B∨C，其中B，C的層次及n同(b)A＝B

C，其中B，C的層次及n同(b)A＝B

?

C，其中B，C的層次及n同(b)若公式Ａ的層次為k，則稱A是k層公式層次≠聯(lián)接詞數(shù)34計算機科學與工程學院1.2命題公式及其賦值例子：p,q,r,s為命題變元((pq)r)s(pq)(qr)(pqr)s

(pqr)43535計算機科學與工程學院1.2命題公式及其賦值命題公式的真值命題變項的常量化：常項替換（解釋）例子：公式pqr真值為T的解釋p:3是奇數(shù)；q:7是奇數(shù)；r:3乘7是奇數(shù)真值為F的解釋p:3是奇數(shù)；q:7是奇數(shù)；r:3乘7是偶數(shù)賦值命題變項賦真命題命題變項的真值為T命題變項賦假命題命題變項的真值為F36計算機科學與工程學院1.2命題公式及其賦值命題變項賦值A(chǔ)中命題變項：p1,…pn對p1,…pn賦值v：v(pi)=i，i{T,F}對A的真值遞歸定義v(B)=Tiffv(B)=Fv(BC)=Tiffv(B)=v(C)=Tv(BC)=Fiffv(B)=v(C)=Fv(BC)=Fiffv(B)=T，v(C)=Fv(BC)=Tiffv(B)=v(C)賦值（解釋）簡寫：12…,nn個變項的公式，共有2n個不同賦值37計算機科學與工程學院1.2命題公式及其賦值命題變項賦值成真賦值：v(A)=T成假賦值：v(A)=F例子：公式(pq)rFFF(p=F,q=F,r=F)TFF?(pq)rFFF38計算機科學與工程學院1.2命題公式及其賦值

真值表：A所有賦值列成表真值表構(gòu)造：找出A中命題變項：p1,…pn列出2n個賦值（2進制加法形式）從高到低寫成公式各個層次各個賦值：計算各層的真值39計算機科學與工程學院1.2命題公式及其賦值pqpq(pq)p?((pq)p)FFFFTFTTFTTFTTFTTTTF例?((pq)p)40計算機科學與工程學院1.2命題公式及其賦值pqrqrp(qr)FFFFFFFTFFFTFFFFTTTTTFFFTTFTFTTTFFTTTTTT例p(qr)41計算機科學與工程學院1.2命題公式及其賦值p

q?p?qp

?

qpq?p?q公式FFTTTTTFTTFFFTTFFTFFTTTFFTTT例(p

?

q)

?(pq?p?q)42計算機科學與工程學院1.2命題公式及其賦值命題公式分類：A重言式(永真式)：v(A)=T，對任意v矛盾式(永假式)：v(A)=F，對任意v可滿足式：v(A)=T，對某個v關(guān)系重言式是可滿足式，反之不一定成立真值判斷法重言式：真值表最后一列全為T矛盾式：真值表最后一列全為F可滿足式：真值表最后一列至少一個T43計算機科學與工程學院1.2命題公式及其賦值真值表有限性：給定n個命題變項共有22n個真值表例題：下列哪些具有相同真值？pqqp(pq)(pq)p44計算機科學與工程學院1.2命題公式及其賦值p

qpqqp