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

1、是否為陳述句；

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

p：羅納爾多是球星。

q：5是負數。

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

p，符號

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

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

(1)p∧q(2)p∧q(3)q∧┐p(4)r∧s(5)t解題要點：正確理解命題含義。找出原子命題并符號化。選擇恰當的聯結詞。

2023/9/1計算機科學與技術系13合取舉例p：我們去看電影。

q：房間里有十張桌子。

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

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

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

而應描述為(p∧

q)∨(

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

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

稱為蘊涵聯結詞。運算規則：屬于雙目運算符真值列舉2023/9/1計算機科學與技術系17第一章命題邏輯基本概念蘊涵運算p

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

q蘊涵式表述命題格式有：“只要p，就q”、“因為p，所以q”、“p僅當q”、“只有q才p”、“除非q才p”、“除非q，否則非p”等。與自然語言的不同：前件與后件可以沒有任何內在聯系！例題參見例1.52023/9/1計算機科學與技術系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計算機科學與技術系19例1.5將下列命題符號化，并指出其真值

以下命題中出現的a是一個給定的正整數：(5)只要a能被4整除，則a一定能被2整除。(6)a能被4整除，僅當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整除的必要條件，因而應符號化為s→r。a值不定時，真值未知。2023/9/1計算機科學與技術系20第一章命題邏輯基本概念定義1.5設p,q為二命題，復合命題“p當且僅當q”稱為p與q的等價式，記作p

q，符號

稱為等價聯結詞。運算規則：屬于雙目運算符真值列舉2023/9/1計算機科學與技術系21第一章命題邏輯基本概念等價運算p

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

q)∧(q

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

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

符號化為p

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

符號化為p

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

符號化為p

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

符號化為p

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

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

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

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

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

B)，(A

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

q),(r∧t)∨

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

w)∧q)等不是合式公式。上述歸納定義方式中的符號A,B不同于具體公式里面的p,q,r等符號，可以用來表示任意的合式公式,屬于元語言符號。2023/9/1計算機科學與技術系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計算機科學與技術系28第一章命題邏輯基本概念例:公式p

p

q(p

q)∧r

((p

q)

(

qp))的層次分別為

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

p2，

…，pn是出現在公式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計算機科學與技術系30第一章命題邏輯基本概念若指定的一組值使A的真值為1，則稱這組值為A的成真賦值。

如對公式(p

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

如對公式(p

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

p2，

…，pn，列出2n個賦值。（2）按從低到高的順序寫出公式的各個層次。（3）對應各個賦值計算出各層次的真值，直到最后計算出公式的真值。2023/9/1計算機科學與技術系32第一章命題邏輯基本概念例：構造公式(p

q)∧r真值表。pqrp

q(p

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

q)

(

qp)真值表。練習2：構造公式

(p

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

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

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

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

q

(p∧

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

p2，

…，pn

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

pi+1，

…，pn

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

p2，

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

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

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