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

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

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

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

離散數(shù)學(xué)：左孝凌，李為鑑，劉永才，上海科學(xué)技術(shù)文獻(xiàn)出版社

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

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

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

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

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

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

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

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

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

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

p的否定式：復(fù)合命題“p的否定”（“非p”）符號(hào)：

p

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

p為真當(dāng)且僅當(dāng)p為假例子今天沒有天晴

p

p

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

p與q的合取式：復(fù)合命題“p并且q”

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

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

p與q的析取式：復(fù)合命題“p或q”

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

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

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

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

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

pq為假當(dāng)且僅當(dāng)p為真，q為假例子

如果天下雨，那么地下濕

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

p為假，pq永遠(yuǎn)為真如果給我一個(gè)支點(diǎn)，我能把

地球撬起來

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

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

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

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

pq它的逆反命題

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

pq

qp

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

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

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

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

x+y>4

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

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

命題常項(xiàng)：簡(jiǎn)單命題

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

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

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

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

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

省略括號(hào)不能影響公式解釋31計(jì)算機(jī)科學(xué)與工程學(xué)院1.2命題公式及其賦值合式公式的樹狀展開

(AB)((C)(DC))ABAB(C)(DC)(C)DCCDC32計(jì)算機(jī)科學(xué)與工程學(xué)院1.2命題公式及其賦值例子(AB)C(pq)(qr)(B)pqr33計(jì)算機(jī)科學(xué)與工程學(xué)院1.2命題公式及其賦值公式層次若公式A是單個(gè)的命題變?cè)瑒t稱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計(jì)算機(jī)科學(xué)與工程學(xué)院1.2命題公式及其賦值例子：p,q,r,s為命題變?cè)?(pq)r)s(pq)(qr)(pqr)s

(pqr)43535計(jì)算機(jī)科學(xué)與工程學(xué)院1.2命題公式及其賦值命題公式的真值命題變項(xiàng)的常量化：常項(xiàng)替換（解釋）例子：公式pqr真值為T的解釋p:3是奇數(shù)；q:7是奇數(shù)；r:3乘7是奇數(shù)真值為F的解釋p:3是奇數(shù)；q:7是奇數(shù)；r:3乘7是偶數(shù)賦值命題變項(xiàng)賦真命題命題變項(xiàng)的真值為T命題變項(xiàng)賦假命題命題變項(xiàng)的真值為F36計(jì)算機(jī)科學(xué)與工程學(xué)院1.2命題公式及其賦值命題變項(xiàng)賦值A(chǔ)中命題變項(xiàng)：p1,…pn對(duì)p1,…pn賦值v：v(pi)=i，i{T,F}對(duì)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)賦值（解釋）簡(jiǎn)寫：12…,nn個(gè)變項(xiàng)的公式，共有2n個(gè)不同賦值37計(jì)算機(jī)科學(xué)與工程學(xué)院1.2命題公式及其賦值命題變項(xiàng)賦值成真賦值：v(A)=T成假賦值：v(A)=F例子：公式(pq)rFFF(p=F,q=F,r=F)TFF?(pq)rFFF38計(jì)算機(jī)科學(xué)與工程學(xué)院1.2命題公式及其賦值

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

q?p?qp

?

qpq?p?q公式FFTTTTTFTTFFFTTFFTFFTTTFFTTT例(p

?

q)

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

qpqqp