工學(xué)至誠學(xué)院ch01命題邏輯基本概念

離散數(shù)學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院王一蕾yilei@2023/9/1計算機科學(xué)與技術(shù)系2第一部分?jǐn)?shù)理邏輯從廣義上講，數(shù)理邏輯包括四論、兩演算——即集合論、模型論、遞歸論、證明論和命題演算、謂詞演算，但現(xiàn)在提到數(shù)理邏輯，一般是指命題演算和謂詞演算。本篇我們只從語義出發(fā)，對數(shù)理邏輯中的命題演算與謂詞演算等作一簡單的、直接的、非形式化的介紹，將不涉及任何公理系統(tǒng)。第一章命題邏輯基本概念2023/9/1計算機科學(xué)與技術(shù)系4本章說明本章的主要內(nèi)容命題、聯(lián)結(jié)詞、復(fù)合命題命題公式、賦值、命題公式的分類本章與后續(xù)各章的關(guān)系本章是后續(xù)各章的準(zhǔn)備或前提2023/9/1計算機科學(xué)與技術(shù)系5第一章命題邏輯基本概念1.1命題與聯(lián)結(jié)詞基本概念命題：能夠判斷真假的陳述句。命題的真值：命題的判斷結(jié)果。真值只取兩個值：真、假。真命題：真值為真的命題。假命題：真值為假的命題。判斷命題的兩個步驟：

1、是否為陳述句；

2、是否有確定的、唯一的真值。2023/9/1計算機科學(xué)與技術(shù)系6第一章命題邏輯基本概念例：判斷下列句子是否為命題。1、100是自然數(shù)。2、太陽從西方升起。3、Howdoyoudo?4、今年國慶節(jié)下小雨。5、x+3>96、我正在說謊。7、請不要說謊！8、如果周末不下雨，那么我們將去郊游。9、這朵花真美麗??！2023/9/1計算機科學(xué)與技術(shù)系7第一章命題邏輯基本概念命題及其真值的抽象化在本書中，用小寫英文字母p,q,r,…p1,p2,p3…等表示命題，用“1”、“0”分別表示真值的真、假。如是：

p：羅納爾多是球星。

q：5是負(fù)數(shù)。

p3：明天天氣晴。皆為符號化的命題，其真值依次為1、0、1或0。2023/9/1計算機科學(xué)與技術(shù)系8第一章命題邏輯基本概念命題的分類簡單/原子命題：由不能再分解為更簡單的陳述句的陳述句構(gòu)成。如上例中的命題（除8外）復(fù)合命題：由簡單命題通過聯(lián)結(jié)詞聯(lián)結(jié)而成的陳述句。 如上例中的命題8，參見課本例1.22023/9/1計算機科學(xué)與技術(shù)系9第一章命題邏輯基本概念常用聯(lián)結(jié)詞定義1.1設(shè)p為命題，復(fù)合命題“非p”（或“p的否定”）稱為p的否定式，記作

p，符號

稱為否定聯(lián)結(jié)詞。運算規(guī)則：屬于單目運算符真值列舉2023/9/1計算機科學(xué)與技術(shù)系10第一章命題邏輯基本概念定義1.2設(shè)p,q為二命題，復(fù)合命題“p并且q”（或“p與q”）稱為p與q的合取式，記作p∧q，符號∧稱為合取聯(lián)結(jié)詞。運算規(guī)則：屬于雙目運算符真值列舉2023/9/1計算機科學(xué)與技術(shù)系11第一章命題邏輯基本概念合取運算特點：只有參與運算的二命題全為真時，運算結(jié)果才為真，否則為假。自然語言中的表示“并且”意思的聯(lián)結(jié)詞，如“既…又…”、“不但…而且…”、“雖然…但是…”、“一面…一面…”等都可以符號化為∧。注意：不要見到“與”或“和”就使用聯(lián)結(jié)詞∧！例題參見例1.32023/9/1計算機科學(xué)與技術(shù)系12例1.3

將下列命題符號化吳穎既用功又聰明。吳穎不僅用功而且聰明。吳穎雖然聰明，但不用功。張輝與王麗都是三好學(xué)生。張輝與王麗是同學(xué)。p:吳穎用功。q:吳穎聰明。r:張輝是三好學(xué)生。s:王麗是三好學(xué)生。t:張輝與王麗是同學(xué)。

(1)p∧q(2)p∧q(3)q∧┐p(4)r∧s(5)t解題要點：正確理解命題含義。找出原子命題并符號化。選擇恰當(dāng)?shù)穆?lián)結(jié)詞。

2023/9/1計算機科學(xué)與技術(shù)系13合取舉例p：我們?nèi)タ措娪啊?/p>

q：房間里有十張桌子。

p∧q：我們?nèi)タ措娪安⑶曳块g里有十張桌子。在數(shù)理邏輯中，關(guān)心的只是復(fù)合命題與構(gòu)成復(fù)合命題的各原子命題之間的真值關(guān)系，即抽象的邏輯關(guān)系，并不關(guān)心各語句的具體內(nèi)容。說明2023/9/1計算機科學(xué)與技術(shù)系14第一章命題邏輯基本概念定義1.3設(shè)p,q為二命題，復(fù)合命題“p或q”稱為p與q的析取式，記作p∨q，符號∨稱為析取聯(lián)結(jié)詞。運算規(guī)則：屬于雙目運算符真值列舉2023/9/1計算機科學(xué)與技術(shù)系15第一章命題邏輯基本概念析取運算特點：只有參與運算的二命題全為假時，運算結(jié)果才為假，否則為真。這里的析取運算只能表示自然語言中的“相容或”的意思，不能表示自然語言里的“排斥或”。例如：（1）小王愛打球或愛跑步。

設(shè)p：小王愛打球。q：小王愛跑步。則上述命題可符號化為：p∨q（2）火車8：00或9：00到站。

設(shè)p：火車8：00到站。q：火車9：00到站。則上述命題就不可簡單符號化為：p∨q

而應(yīng)描述為(p∧

q)∨(

p∧q)2023/9/1計算機科學(xué)與技術(shù)系16第一章命題邏輯基本概念定義1.4設(shè)p,q為二命題，復(fù)合命題“如果p，則q”稱為p與q的蘊涵式，記作p

q，并稱p為蘊涵式的前件，q為蘊涵式的后件，符號

稱為蘊涵聯(lián)結(jié)詞。運算規(guī)則：屬于雙目運算符真值列舉2023/9/1計算機科學(xué)與技術(shù)系17第一章命題邏輯基本概念蘊涵運算p

q表示的邏輯關(guān)系是：q是p的必要條件。自然語言中可用p

q蘊涵式表述命題格式有：“只要p，就q”、“因為p，所以q”、“p僅當(dāng)q”、“只有q才p”、“除非q才p”、“除非q，否則非p”等。與自然語言的不同：前件與后件可以沒有任何內(nèi)在聯(lián)系！例題參見例1.52023/9/1計算機科學(xué)與技術(shù)系18例1.5將下列命題符號化，并指出其真值

如果3+3＝6，則雪是白的。如果3+3≠6，則雪是白的。如果3+3＝6，則雪不是白的。如果3+3≠6，則雪不是白的。解：令p：3+3＝6，p的真值為1。

q：雪是白色的，q的真值也為1。

p→q┐p→q p→┐q ┐p→┐q 11012023/9/1計算機科學(xué)與技術(shù)系19例1.5將下列命題符號化，并指出其真值

以下命題中出現(xiàn)的a是一個給定的正整數(shù)：(5)只要a能被4整除，則a一定能被2整除。(6)a能被4整除，僅當(dāng)a能被2整除。(7)除非a能被2整除，a才能被4整除。(8)除非a能被2整除，否則a不能被4整除。(9)

只有a能被2整除，a才能被4整除。(10)只有a能被4整除，a才能被2整除。解：令r：a能被4整除

s：a能被2整除(5)至(9)五個命題均敘述的是a能被2整除是a能被4整除的必要條件，因而都符號化為r→s。其真值為1在(10)中，將a能被4整除看成了a能被2整除的必要條件，因而應(yīng)符號化為s→r。a值不定時，真值未知。2023/9/1計算機科學(xué)與技術(shù)系20第一章命題邏輯基本概念定義1.5設(shè)p,q為二命題，復(fù)合命題“p當(dāng)且僅當(dāng)q”稱為p與q的等價式，記作p

q，符號

稱為等價聯(lián)結(jié)詞。運算規(guī)則：屬于雙目運算符真值列舉2023/9/1計算機科學(xué)與技術(shù)系21第一章命題邏輯基本概念等價運算p

q表示的邏輯關(guān)系是：p與q互為充分必要條件。相當(dāng)于(p

q)∧(q

p)例題參見例1.62023/9/1計算機科學(xué)與技術(shù)系22例1.6將下列命題符號化，并討論它們的真值

π是無理數(shù)當(dāng)且僅當(dāng)加拿大位于亞洲。2+3＝5的充要條件是π是無理數(shù)。若兩圓A，B的面積相等，則它們的半徑相等；反之亦然。當(dāng)王小紅心情愉快時，她就唱歌；反之，當(dāng)她唱歌時，一定心情愉快。設(shè)p：π是無理數(shù)，q：加拿大位于亞洲。

符號化為p

q，真值為0。設(shè)p：2+3＝5，q：π是無理數(shù)。

符號化為p

q，真值為1。設(shè)p：兩圓A，B的面積相等，q：兩圓A，B的半徑相等。

符號化為p

q，真值為1。設(shè)p：王小紅心情愉快，q：王小紅唱歌。

符號化為p

q，真值由具體情況而定。2023/9/1計算機科學(xué)與技術(shù)系23第一章命題邏輯基本概念以上5種最基本、最常用、最重要的聯(lián)結(jié)詞可以組成一個集合{

，∧，∨，，}，成為一個聯(lián)結(jié)詞集，其運算的優(yōu)先級為：，∧，∨，，，對于同一級者，先出現(xiàn)者先運算。例題參見例1.72023/9/1計算機科學(xué)與技術(shù)系24第一章命題邏輯基本概念1.2命題公式及其賦值基本概念簡單命題/命題常項/命題常元：真值唯一確定的陳述句。命題變項/命題變元：真值可以變化的陳述句。

命題常項與命題變項都可以用p,q,r…等表示，具體情況由上下文確定。合式公式/命題公式：將命題變項用聯(lián)結(jié)詞和圓括號按一定的邏輯關(guān)系聯(lián)結(jié)起來的符號串。當(dāng)使用聯(lián)結(jié)詞集{

，∧，∨，，}時，合式公式定義如下：2023/9/1計算機科學(xué)與技術(shù)系25第一章命題邏輯基本概念定義1.6（1）單個命題變項是合式公式，并稱為原子命題公式。（2）若A是合式公式，則(

A)也是合式公式。（3）若A，B是合式公式，則(A∧B)，(A∨B)，(A

B)，(A

B)也是合式公式。（4）只有有限次地應(yīng)用(1)~(3)形成的符號串才是合式公式。合式公式也稱為命題公式或命題形式，并簡稱為公式。2023/9/1計算機科學(xué)與技術(shù)系26第一章命題邏輯基本概念(p

q),(r∧t)∨

e,p，(p)等均為合式公式，而pq∨t,(p

w)∧q)等不是合式公式。上述歸納定義方式中的符號A,B不同于具體公式里面的p,q,r等符號，可以用來表示任意的合式公式,屬于元語言符號。2023/9/1計算機科學(xué)與技術(shù)系27第一章命題邏輯基本概念定義1.7——公式層次（1）若公式A是單個的命題變項，則稱A為0層合式公式。（2）稱A是n+1(n≥0)層公式是指下列情況之一：

(a)A=

B,B是n層公式；

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

(c)A=B∨C,其中B,C的層次及n同(b);(d)A=B

C,其中B,C的層次及n同(b);(e)A=B

C,其中B,C的層次及n同(b);（3）若公式A的層次為k，則稱A是k層公式。2023/9/1計算機科學(xué)與技術(shù)系28第一章命題邏輯基本概念例:公式p

p

q(p

q)∧r

((p

q)

(

qp))的層次分別為

0、1、3、42023/9/1計算機科學(xué)與技術(shù)系29第一章命題邏輯基本概念定義1.8——公式賦值設(shè)p1，

p2，

…，pn是出現(xiàn)在公式A中的全部的命題變項，給p1，

p2，

…，pn各指定一個真值，稱為對A的一個賦值或解釋。比如：對公式(p

q)∧r一組賦值為011(意即令p=0,q=1,r=1)可得真值為1，另一組賦值為010可得真值為0；還有000，001，111……考慮：含有n個命題變項的公式共有多少個不同的賦值？2023/9/1計算機科學(xué)與技術(shù)系30第一章命題邏輯基本概念若指定的一組值使A的真值為1，則稱這組值為A的成真賦值。

如對公式(p

q)∧r賦值011，還有…???若指定的一組值使A的真值為0，則稱這組值為A的成假賦值。

如對公式(p

q)∧r賦值010，還有…???2023/9/1計算機科學(xué)與技術(shù)系31第一章命題邏輯基本概念定義1.9——真值表將命題公式A在所有賦值下取值情況列成表，稱做A的真值表。對公式A構(gòu)造真值表的具體步驟為：（1）找出公式中所有的全體命題變項p1，

p2，

…，pn，列出2n個賦值。（2）按從低到高的順序?qū)懗龉降母鱾€層次。（3）對應(yīng)各個賦值計算出各層次的真值，直到最后計算出公式的真值。2023/9/1計算機科學(xué)與技術(shù)系32第一章命題邏輯基本概念例：構(gòu)造公式(p

q)∧r真值表。pqrp

q(p

q)∧r00010001110101001111100001010011010111112023/9/1計算機科學(xué)與技術(shù)系33第一章命題邏輯基本概念練習(xí)1：構(gòu)造公式(p

q)

(

qp)真值表。練習(xí)2：構(gòu)造公式

(p

q)∧q真值表。2023/9/1計算機科學(xué)與技術(shù)系34第一章命題邏輯基本概念公式的又一種分類方式定義1.10設(shè)A為任一命題公式，（1）若A在其各種賦值下的取值均為真，則稱A是重言式或永真式。（2）若A在其各種賦值下的取值均為假，則稱A是矛盾式或永假式。（3）若A不是矛盾式，則稱A為可滿足式。2023/9/1計算機科學(xué)與技術(shù)系35第一章命題邏輯基本概念真值表的作用：（1）表示出公式的成真或成假賦值。（2）判斷公式類型：

(a)若真值表最后一列全為1，則為重言式；

(b)若真值表最后一列全為0，則為矛盾式；

(c)若真值表最后一列至少有一個1，則為可滿足式；2023/9/1計算機科學(xué)與技術(shù)系36第一章命題邏輯基本概念考慮：含有n個命題變項的公式的真值表有???種不同的情況？因此，必有很多公式具有相同的真值表。如：pqp

q

(p∧

q)00110111100011112023/9/1計算機科學(xué)與技術(shù)系37第一章命題邏輯基本概念設(shè)公式A，B中共含有命題變項p1，

p2，

…，pn

，而A或B不全含這些命題變項，比如A中不含pi，

pi+1，

…，pn

，稱這些命題變項為A的啞元，A的取值與啞元無關(guān)，因此在討論A與B是否有相同的真值表時，將A，B都看成含p1，

p2，

…，pn的命題公式。具體例題參見例1.102023/9/1計算機科學(xué)與技術(shù)系38本章主要內(nèi)容命題與真值（或真假值）。簡單命題與復(fù)合命題。聯(lián)結(jié)詞：┐，∧，∨，→，

。命題公式（簡稱公式）。命題公式的層次和公式的賦值。真值表。公式的類型：重言式（永真式），矛盾式（永假式），可滿足式。

2023/9/1計算機科學(xué)與技術(shù)系39本章學(xué)習(xí)要求在5種聯(lián)結(jié)詞中，要特別注意蘊涵聯(lián)結(jié)的應(yīng)用，要弄清三個問題：p→q的邏輯關(guān)系p→q的真值p→q的靈活的敘述方法寫真值表要特別仔細(xì)認(rèn)真，否則會出錯誤。深刻理解各聯(lián)結(jié)詞的邏輯含義。熟練地將復(fù)合命題符號化。會用真值表求公式的成真賦值和成假賦值。2023/9/1計算機科學(xué)與技術(shù)系40本章典型習(xí)題命題符號化求復(fù)合命題的真值與命題公式的賦值判斷公式的類型2023/9/1計