第一章-命題邏輯的基本概念資料課件

離散數(shù)學(xué)計(jì)算機(jī)1501-04趙曦教材《離散數(shù)學(xué)》

屈婉玲、耿素云、張立昂，高等教育出版社，

2015年3月第二版2學(xué)科地位3計(jì)算機(jī)相關(guān)專業(yè)，需具備的專業(yè)能力：計(jì)算思維能力；算法設(shè)計(jì)與分析能力；程序設(shè)計(jì)與實(shí)現(xiàn)能力；計(jì)算機(jī)系統(tǒng)的認(rèn)知、分析、開(kāi)發(fā)和應(yīng)用能力，簡(jiǎn)稱系統(tǒng)能力。4被有效地自動(dòng)計(jì)算形式化“計(jì)算思維”圖1自動(dòng)計(jì)算、形式化與“計(jì)算思維”的關(guān)系5中學(xué)數(shù)學(xué)數(shù)學(xué)分析離散數(shù)學(xué)形式語(yǔ)言與自動(dòng)機(jī)理論具體、靜止變量、運(yùn)動(dòng)離散、抽象（基本運(yùn)算系統(tǒng)）形式、模型（計(jì)算系統(tǒng)）實(shí)數(shù)抽象集合孤立、單一的計(jì)算（實(shí)例計(jì)算）一般、形式化的計(jì)算（類計(jì)算、模型計(jì)算）運(yùn)算范圍特征圖2“計(jì)算思維”梯度訓(xùn)練系統(tǒng)《離散數(shù)學(xué)》是現(xiàn)代數(shù)學(xué)的一個(gè)重要分支，是構(gòu)筑于數(shù)學(xué)和計(jì)算機(jī)學(xué)科之間的橋梁，是計(jì)算機(jī)科學(xué)的理論基礎(chǔ)。作為核心基礎(chǔ)課程，該課程在計(jì)算機(jī)及相關(guān)專業(yè)課程體系中扮演著重要的角色，是構(gòu)筑于數(shù)學(xué)和計(jì)算機(jī)學(xué)科之間的橋梁，。它以研究離散量的結(jié)構(gòu)及相互關(guān)系為主要目標(biāo)，充分描述了計(jì)算機(jī)科學(xué)離散性的特點(diǎn)。6與后續(xù)課程的關(guān)系數(shù)理邏輯——在人工智能、程序理論和數(shù)據(jù)庫(kù)理論等的研究中有重要的應(yīng)用。集合論、圖論——為數(shù)據(jù)結(jié)構(gòu)和算法分析奠定了數(shù)學(xué)基礎(chǔ)，也為許多問(wèn)題從算法角度如何加以解決提供了繼續(xù)抽象和描述的一些重要方法。代數(shù)結(jié)構(gòu)——代數(shù)結(jié)構(gòu)中的代數(shù)方法被廣泛應(yīng)用，如可計(jì)算性與計(jì)算復(fù)雜性、形式語(yǔ)言與自動(dòng)機(jī)、密碼學(xué)、網(wǎng)絡(luò)與通信理論、程序理論和形式語(yǔ)義學(xué)等計(jì)算機(jī)分支學(xué)科。7第一部分?jǐn)?shù)理邏輯數(shù)理邏輯命題邏輯一階邏輯用數(shù)學(xué)方法研究推理的一門(mén)科學(xué)。要想把這種推理規(guī)則應(yīng)用到各個(gè)學(xué)科領(lǐng)域中去，就必須使用一種概括性較強(qiáng)，并且又是獨(dú)立于任何特定的論證或者所涉及的學(xué)科的語(yǔ)言。這種語(yǔ)言是一種符號(hào)化的形式語(yǔ)言，它沒(méi)有二義性。

第一至五章將介紹這套符號(hào)化形式體系的制定，以及它在數(shù)理邏輯中的應(yīng)用。數(shù)理邏輯的發(fā)展在17世紀(jì)，曾經(jīng)設(shè)想創(chuàng)造一種“通用的科學(xué)語(yǔ)言”，能夠像數(shù)學(xué)一樣利用公式對(duì)推理過(guò)程進(jìn)行計(jì)算，但沒(méi)有實(shí)現(xiàn)。是數(shù)理邏輯的先驅(qū)。1847年，《邏輯的數(shù)學(xué)分析》，建立了“布爾代數(shù)”，并創(chuàng)造了一套符號(hào)系統(tǒng)，初步奠定了數(shù)理邏輯的基礎(chǔ)。101879年，《概念語(yǔ)言》，建立第一個(gè)比較嚴(yán)格的邏輯演算系統(tǒng)。《數(shù)學(xué)原理》，當(dāng)時(shí)數(shù)理邏輯的成果總結(jié)，使得數(shù)理邏輯形成了專門(mén)的學(xué)科。111930年以前，數(shù)理邏輯的發(fā)展主要是針對(duì)純數(shù)學(xué)的。從20世紀(jì)40年代起，自動(dòng)化和計(jì)算技術(shù)的發(fā)展要求建立包含數(shù)百個(gè)甚至數(shù)千個(gè)繼電器的復(fù)雜系統(tǒng)，人們難以進(jìn)行分析和綜合。于是，當(dāng)時(shí)多個(gè)國(guó)家?guī)缀跬瑫r(shí)出現(xiàn)了關(guān)于繼電器接點(diǎn)線路結(jié)構(gòu)的符號(hào)方法及數(shù)理邏輯的命題演算在其中的應(yīng)用。1943年，數(shù)理邏輯又應(yīng)用于所有開(kāi)關(guān)線路的理論中。以后，又在計(jì)算機(jī)科學(xué)和控制論方面獲得應(yīng)用，成為基礎(chǔ)理論之一。12數(shù)理邏輯在計(jì)算機(jī)科學(xué)技術(shù)中的應(yīng)用數(shù)理邏輯是計(jì)算理論的基礎(chǔ)，而計(jì)算理論又是計(jì)算機(jī)科學(xué)的核心基礎(chǔ)，在編譯原理、復(fù)雜性分析中有廣泛的應(yīng)用；

另外，數(shù)理邏輯也是形式語(yǔ)言、程序設(shè)計(jì)方法、機(jī)器證明、人工智能等學(xué)科的基礎(chǔ)。

下面將介紹一些數(shù)理邏輯的典型應(yīng)用，供參考。1314命題邏輯的知識(shí)在日常生活和工程技術(shù)中都有著廣泛的應(yīng)用。電子計(jì)算機(jī)是數(shù)理邏輯和電子學(xué)相結(jié)合的產(chǎn)物。實(shí)際上，無(wú)論是作為計(jì)算機(jī)雛形的圖靈機(jī)，還是作為程序設(shè)計(jì)的語(yǔ)言等，無(wú)不涉及它的知識(shí)和理論。命題邏輯的知識(shí)邏輯結(jié)構(gòu)151.11.22.22.13.13.216第一章命題邏輯的基本概念§1.1命題與聯(lián)結(jié)詞§1.2命題公式及其賦值17§1.1命題與聯(lián)結(jié)詞一、命題與真值二、命題的分類三、命題與真值的符號(hào)化四、常用聯(lián)結(jié)詞及其符號(hào)五、基本復(fù)合命題六、復(fù)合命題返回一、命題與真值181.命題2.命題的真值3.真命題4.假命題判斷結(jié)果惟一的陳述句。判斷的結(jié)果。真值為真的命題。真值為假的命題。命題的注意事項(xiàng)非假即真的陳述句。一切沒(méi)有判斷內(nèi)容，不分真假的句子，都不是命題。陳述句能否分辨真假，和是否知道它的真假，是兩回事。命題不能是疑問(wèn)句或是祈使句等其他類型的句子。一個(gè)命題的真值只能是真或是假，不能兼而有之。例

判斷下列句子是否為命題：序號(hào)句子是否為命題原因(1)是無(wú)理數(shù).√真命題(2)2+5＝8.√假命題(3)x+5＞3.×真值不確定(4)你有鉛筆嗎？×疑問(wèn)句(5)這只兔子跑得真快呀！×感嘆句(6)請(qǐng)不要講話！×祈使句(7)我正在說(shuō)謊話.×悖論（7）這種由真能推出假、又由假能推出真，從而既不能為真、也不能為假的陳述句稱為悖論。悖論不是命題。21（8）、（9）的真值雖然現(xiàn)在還不知道，但它的真值是唯一的，因而是命題。（10）在二進(jìn)制中為真，在十進(jìn)制中為假，需根據(jù)上下文才能確定其真值，因而不是命題。序號(hào)句子是否為命題原因(8)明年10月1日是晴天.√真值唯一(9)地球外的星球上有人.√真值唯一(10)11＋1＝100.×真值不確定返回221.簡(jiǎn)單命題（原子命題）2.復(fù)合命題返回不能被分解成更簡(jiǎn)單命題。簡(jiǎn)單命題是最小的基本單位。由簡(jiǎn)單命題通過(guò)聯(lián)接詞聯(lián)接而成。二、命題的分類231.命題的符號(hào)化2.真值的符號(hào)化用p、q、r等表示命題。用數(shù)字1代表真，0代表假。返回例如，令

p：是有理數(shù)，則p的真值為0。q：2+5=7，則q的真值為1。

注意：書(shū)P4例1.2三、命題與真值的符號(hào)化241.否定（定義1.1）2.合取∧（定義1.2）3.析取∨（定義1.3）4.蘊(yùn)涵→（定義1.4）5.等價(jià)（定義1.5）規(guī)定

p∧q為真當(dāng)且僅當(dāng)p與q同時(shí)為真.規(guī)定p∨q為假當(dāng)且僅當(dāng)p與q同時(shí)為假.規(guī)定pq為假當(dāng)且僅當(dāng)p為真q為假.規(guī)定pq為真當(dāng)且僅當(dāng)p與q同時(shí)為真或同時(shí)為假.四、常用聯(lián)結(jié)詞及其符號(hào)規(guī)定

p為真當(dāng)且僅當(dāng)p為假.25設(shè)p為命題，復(fù)合命題“非p”（或“p的否定”）稱為p的否定式，記作p。符號(hào)稱作否定聯(lián)結(jié)詞。規(guī)定p

為真當(dāng)且僅當(dāng)p為假。1.否定式與否定聯(lián)結(jié)詞“”2.合取式與合取聯(lián)結(jié)詞“∧”26設(shè)p，q為兩個(gè)命題，復(fù)合命題“p并且q”(或“p與q”)稱為p與q的合取式，記作p∧q，∧稱作合取聯(lián)結(jié)詞。規(guī)定

p∧q為真當(dāng)且僅當(dāng)p與q同時(shí)為真。合取的注意事項(xiàng)描述合取式的靈活性與多樣性。

自然語(yǔ)言中的“既…，又…”，“不但…，而且…”，“雖然…，但是…”，“一面…，一面…”等都表示兩件事情同時(shí)成立，因而都可以符號(hào)化為∧。

分清簡(jiǎn)單命題與復(fù)合命題

不要見(jiàn)到“與”、“和”就使用聯(lián)結(jié)詞∧。例1.3將下列命題符號(hào)化：序號(hào)命題符號(hào)化命題種類(1)吳穎既用功又聰明.p∧q復(fù)合命題(2)吳穎不僅用功而且聰明.p∧q復(fù)合命題(3)吳穎雖然聰明，但不用功.q

∧p復(fù)合命題(4)張輝與王麗都是三好生.r∧s復(fù)合命題(5)張輝與王麗是同學(xué).t簡(jiǎn)單命題解：令p：吳穎用功.q：吳穎聰明.r:張輝是三好學(xué)生.s:王麗是三好學(xué)生.

t:張輝與王麗是同學(xué).3.析取式與析取聯(lián)結(jié)詞“∨”29設(shè)p，q為兩個(gè)命題，復(fù)合命題“p或q”稱作p與q的析取式，記作p∨q，∨稱作析取聯(lián)結(jié)詞。規(guī)定p∨q為假當(dāng)且僅當(dāng)p與q同時(shí)為假?！盎颉钡暮x30或的含義例表達(dá)的意思聯(lián)結(jié)詞排斥或人固有一死，或重于泰山或輕于鴻毛。非此即彼，不可兼得。相容或a·b=0即a=0或b=0或a=b=0二者至少有一個(gè)發(fā)生，不排除二者都發(fā)生的情況。非聯(lián)結(jié)詞表示近似數(shù)或去書(shū)店需走8分鐘或10分鐘。近似數(shù)“8至10分鐘”例1.4將下列命題符號(hào)化：序號(hào)命題符號(hào)化命題種類(1)張曉靜愛(ài)唱歌或愛(ài)聽(tīng)音樂(lè).p∨q相容或(2)張曉靜只能挑選202或203房間.(r∧s)∨(r∧s)排斥或(3)張曉靜是江西人或安徽人.(t∧u)∨(t∧u)或t∨u排斥或相容或p∨q與排斥或(p∧q)∨(p∧q)的區(qū)別在于，當(dāng)p與q同為真時(shí)，p∨q為真，(p∧q)∨(p∧q)為假。因而，當(dāng)命題p與q不能同為真時(shí)，兩者相同。.4.蘊(yùn)涵式與蘊(yùn)涵聯(lián)結(jié)詞“”32設(shè)p，q為兩個(gè)命題，復(fù)合命題“如果p，則q”稱作p與q的蘊(yùn)涵式，記作pq，并稱p是蘊(yùn)涵式的前件，q為蘊(yùn)涵式的后件。稱作蘊(yùn)涵聯(lián)結(jié)詞。規(guī)定pq為假當(dāng)且僅當(dāng)p為真q為假。pq的邏輯關(guān)系33p為q

的充分條件，q為p的必要條件。常出現(xiàn)的錯(cuò)誤：不分充分與必要條件?！叭绻鹥，則q

”的不同表述法：若p，就q

只要p，就q

因?yàn)閜，所以qp僅當(dāng)q

只有q

才p

除非q才p或除非q,否則非p

以上各種敘述方法表面看有所不同，但都表示q是p的必要條件，因而都應(yīng)符合化為pq。

例：設(shè)p:天冷，q:小王穿羽絨服，

將下列命題符號(hào)化：序號(hào)句子符號(hào)化(1)只要天冷，小王就穿羽絨服.(2)因?yàn)樘炖?，所以小王穿羽絨服.(3)若小王不穿羽絨服，則天不冷.(4)只有天冷，小王才穿羽絨服.(5)除非天冷，小王才穿羽絨服.(6)除非小王穿羽絨服，否則天不冷.(7)如果天不冷，則小王不穿羽絨服.(8)小王穿羽絨服僅當(dāng)天冷的時(shí)候.pqpqpqqp

qp

pqqp

qp

35注意：1.在自然語(yǔ)言中，前提是假的，不論結(jié)論真假，整個(gè)語(yǔ)句的意義無(wú)法判斷。在邏輯中，當(dāng)前件p為假時(shí)，pq為真，稱為善意推定。2.p與q不一定有內(nèi)在聯(lián)系。PQPQFFTFTTTFFTTT5.等價(jià)式與等價(jià)聯(lián)結(jié)詞”36設(shè)p，q為兩個(gè)命題，復(fù)合命題“p當(dāng)且僅當(dāng)q”稱作p與q的等價(jià)式，記作pq，稱作等價(jià)聯(lián)結(jié)詞。規(guī)定pq為真當(dāng)且僅當(dāng)p與q同時(shí)為真或同時(shí)為假。等價(jià)的注意事項(xiàng)

pq的邏輯關(guān)系：p與q互為充分必要條件。

pq為真當(dāng)且僅當(dāng)p與q同真或同假。

p

q與(pq)(qp)等值。p與q不一定有內(nèi)在聯(lián)系。聯(lián)結(jié)詞的總結(jié)38p

qp

p∧qp∨qp

qp

q0010011011011010001001101111返回391.否定式p

2.合取式p∧q3.析取式p∨q4.析取式(p∧q)∨(p∧q)5.蘊(yùn)涵式pq6.等價(jià)式pqp為真當(dāng)且僅當(dāng)p為假。p∧q為真當(dāng)且僅當(dāng)p與q同時(shí)為真。返回p∨q為假當(dāng)且僅當(dāng)p與q同時(shí)為假。為真當(dāng)且僅當(dāng)p與q的真值相異。pq為假當(dāng)且僅當(dāng)p為真，q為假。pq為真當(dāng)且僅當(dāng)p與q的真值相同。五、基本復(fù)合命題401.復(fù)合命題2.聯(lián)結(jié)詞的優(yōu)先順序返回基本復(fù)合命題以及多次使用常用聯(lián)結(jié)詞集S中的聯(lián)結(jié)詞復(fù)合而成的命題。聯(lián)結(jié)詞的優(yōu)先順序?yàn)椋?,,,;

如果出現(xiàn)的聯(lián)結(jié)詞同級(jí)，又無(wú)括號(hào)時(shí)，則按從左到右的順序運(yùn)算；若遇有括號(hào)時(shí)，應(yīng)該先進(jìn)行括號(hào)中的運(yùn)算。六、復(fù)合命題41§1.2命題公式及其賦值一、命題常項(xiàng)與命題變項(xiàng)二、合式公式及其層次三、公式的賦值與真值表四、公式的類型返回一、命題常項(xiàng)與命題變項(xiàng)421.命題常項(xiàng)2.命題變項(xiàng)簡(jiǎn)單命題，其真值是確定的，稱為命題常項(xiàng)。取值1或0的變量p，q，r…。真值不確定（取值1或0）的陳述句。用p，q，r……表示。43注意：1.命題變項(xiàng)不是命題。2.命題變項(xiàng)與命題常項(xiàng)的關(guān)系如同數(shù)學(xué)

中變量與常量的關(guān)系。

3.p，q，r…既可以表示命題常項(xiàng)，也

可以表示命題變項(xiàng)。通?？梢杂缮舷?/p>

文確定。返回二、合式公式及其層次

441.合式公式（定義1.6）2.公式的層次（定義1.7）將命題變項(xiàng)用聯(lián)結(jié)詞和圓括號(hào)按一定的邏輯關(guān)系聯(lián)結(jié)起來(lái)的符號(hào)串稱為合式公式。對(duì)合式公式進(jìn)行分層，可準(zhǔn)確地求出公式的真值。1.合式公式45遞歸定義如下：(1)單個(gè)命題常項(xiàng)或變項(xiàng)是合式公式；(2)若A是合式公式，則(A)是合式公式；(3)若A,B是合式公式，則(AB),(AB),(AB),(AB)是合式公式；(4)有限次地應(yīng)用(1)~(3)形成的符號(hào)串是合式

公式。46注意：①設(shè)A合式公式，B為A的一部分，若

B也是合式公式，則稱B為A的子公式。

②不影響運(yùn)算次序的括號(hào)可以省去。2.公式的層次

(1)若公式A是單個(gè)的命題變項(xiàng)，稱A為0層公式。(2)稱A是n+1(n≥0)層公式是指下面情況之一：

(a)A=B，B是n層公式；

(b)A=BC，其中B，C分別為i層和j層公式，且n=max(i,j)；

(c)A=BC，其中B，C的層次及n同(b)；

(d)A=BC，其中B，C的層次及n同(b)；

(e)A=BC，其中B，C的層次及n同(b)。(3)若公式A的層次為k，則稱A是k層公式。4748公式的層次舉例序號(hào)合式公式層次(1)

p0(2)

p1(3)pq

2(4)(pq)r

3(5)((pq)r)(rs)4返回三、命題的賦值與真值表491.公式的賦值（定義1.8）成真賦值（定義1.8）成假賦值（定義1.8）2.真值表（定義1.9）1.公式的賦值

設(shè)p1,p2,…,pn是出現(xiàn)在公式A中的全部命題變項(xiàng)，給p1,p2,…,pn各指定一個(gè)真值（0或1），稱為對(duì)A的一個(gè)賦值或解釋。50成真賦值:使公式A為真的賦值。成假賦值:使公式A為假的賦值。本書(shū)對(duì)公式賦值的記法51

賦值=12…n之間不加標(biāo)點(diǎn)符號(hào)，i=0或1。

1.若A中出現(xiàn)的命題變項(xiàng)為p1,p2,…,pn，A賦值12…n是指p1=1,p2=2,…,pn=n2.若A中出現(xiàn)的命題變項(xiàng)(按字母順序)為p,

q,r,…，A賦值123…是指p=1，q=2,r=3…注意：含n（n≥1）個(gè)命題變項(xiàng)的公式有2n個(gè)

賦值。例：求下列公式的成真賦值和成假賦值。521.(pqr)2.(p

q)(p

r)

2.真值表

將命題公式A在所有賦值下取值情況列成表，稱作A的真值表。構(gòu)造真值表的步驟如下：

(1)列出所有命題變項(xiàng)，列出所有可能賦值；

(2)按從低到高的順序?qū)懗龈鲗哟危?/p>

(3)對(duì)應(yīng)每個(gè)賦值，計(jì)算命題公式各層次的

真值，直到計(jì)算出命題公式的真值。

5354例：給出公式的真值表A=(qp)qp

pqqp

(qp)q

(qp)qp

00011011

1011

0001

1111B=(pq)q

pqppq