離散第9講 命題與邏輯聯(lián)結(jié)詞new

11級專業(yè)選修課程授課人：王薇信息與計算教研室本教材離散數(shù)學知識結(jié)構(gòu)離散數(shù)學前言PowerPointTemplate_Sub

邏輯學是一門非常古老的學科，它是研究人類推理過程的科學。到現(xiàn)在已經(jīng)有了兩千多年的歷史。古典邏輯學主要起源于古希臘學者亞里士多德的邏輯學說，他創(chuàng)作的《工具論》一書是古代一部最完備的邏輯學著作。古典邏輯學的基本特點是用自然語言描述對邏輯的研究，而一旦超出這個范圍，引入數(shù)學的方法來研究邏輯，就產(chǎn)生了遠遠優(yōu)于古典邏輯學的現(xiàn)代邏輯學。

數(shù)理邏輯也稱符號邏輯，是現(xiàn)代邏輯學研究的主體部分，是一門運用數(shù)學方法研究思維規(guī)律的邊緣性學科。將推理變成數(shù)學演算，這是數(shù)理邏輯的指導思想，并且已經(jīng)成為這門學科的主要特征

。數(shù)理邏輯是用形式化(符號化)方法來研究推理的科學。*

命題邏輯研究命題和命題連接詞的邏輯結(jié)構(gòu)以及命題之間的推理關(guān)系。命題邏輯:推理的基本要素是命題.

引言

先看著名物理學家愛因斯坦出過的一道題：

一個土耳其商人想找一個十分聰明的助手協(xié)助他經(jīng)商，有兩人前來應聘，這個商人為了試試哪個人更聰明些，就把兩個人帶進一間漆黑的屋子里，他打開燈后說：“這張桌子上有五頂帽子，兩頂是紅色的，三頂是黑色的，現(xiàn)在，我把燈關(guān)掉，而且把帽子擺的位置弄亂，然后我們?nèi)齻€人每人摸一頂帽子戴在自己頭上，在我開燈后，請你們盡快說出自己頭上戴的帽子是什么顏色的。”說完后，商人將電燈關(guān)掉，然后三人都摸了一頂帽子戴在頭上，同時商人將余下的兩頂帽子藏了起來，接著把燈打開。這時，那兩個應試者看到商人頭上戴的是一頂紅帽子，其中一個人便喊道：“我戴的是黑帽子?！?/p>

請問這個人說得對嗎？他是怎么推導出來的呢？

要回答這樣的問題，實際上就是看由一些諸如“商人戴的是紅帽子”這樣的前提能否推出“猜出答案的應試者戴的是黑帽子”這樣的結(jié)論來。這又需要經(jīng)歷如下過程：

(1)什么是前提？有哪些前提？

(2)結(jié)論是什么？

(3)根據(jù)什么進行推理？

(4)怎么進行推理？學習命題邏輯將回答這幾個問題。-8-第9講命題與邏輯聯(lián)結(jié)詞PowerPointTemplate_Sub

1命題與邏輯聯(lián)結(jié)詞2邏輯等價式和邏輯蘊涵式3范式4證明技術(shù)（補充）命題與邏輯聯(lián)結(jié)詞《離散數(shù)學》第9講Page56to78-10-第9講命題與邏輯聯(lián)結(jié)詞內(nèi)容提要命題的概念命題、命題真值表示原子命題和復合命題、命題常元、命題變元邏輯聯(lián)結(jié)詞┐、∧、∨、→、

命題公式

公式的歸納定義指派自然語句的形式化-11-第9講命題與邏輯聯(lián)結(jié)詞命題(proposition或statement)命題：是一句有確定真假值的陳述句。命題只有兩個結(jié)果，或是真，或是假，但二者不能得兼（排中律），也不能不真又不假。真、假常被稱為命題的真值。

命題的真值

作為命題的陳述句所表達的判斷結(jié)果稱為命題的真值,

真值只有2個:真或假。用T,F或1,0表示。

當判斷正確或符合客觀實際時，稱該命題真(true)，

否則稱該命題假(false)。任何命題的真值都是唯一的.判斷給定句子是否為命題的步驟:首先判定它是否為陳述句判斷它是否有唯一的真值.疑問句、祈使句、感嘆句和悖論等都不是命題。悖論：由真推出假又由假推出真的陳述句稱為悖論。即自相矛盾的句子。-14-第9講命題與邏輯聯(lián)結(jié)詞命題舉例雪是白的半徑為1的圓的周長為2π2是偶數(shù)且3也是偶數(shù)陳勝起義那天杭州下雨大于2的偶數(shù)均可以分解為兩個質(zhì)數(shù)的和數(shù)學多美啊!X+Y=4

“我正在說謊?！蔽抑唤o那些不給自己刮胡子的人刮胡子√T√T√F√√T××××-15-第9講命題與邏輯聯(lián)結(jié)詞原子命題和復合命題原子命題：一個不能再分解成更簡單語句的命題原子命題是最簡單的陳述句（1）雪是白的。(T)

（2）2+2=5(F)

（3）2是素數(shù)。(T)

（4）北京是中國的首都。(T)上述命題都是簡單陳述句，他們都不能分解為更簡單的陳述句了，稱這樣的命題為原子命題.-16-第9講命題與邏輯聯(lián)結(jié)詞原子命題和復合命題原子命題通常記為p、q、r等小寫字母，f表示恒假命題，t表示恒真命題。例：p：2000年4月5日是星期一。q:星期二的前一天是星期一。恒真

-17-第9講命題與邏輯聯(lián)結(jié)詞原子命題和復合命題命題常元和變元原子命題有確定的真值，又稱為命題常元。命題變元是指一個未確定真值的任意命題，其值在{0，1}上變化。例p:x+y=5不是命題，但x,y一旦確定，它的真值就確定了。這種真值可以變化的簡單陳述句稱為命題變元。命題變元也用p、q、r等小寫字母表示。-18-第9講命題與邏輯聯(lián)結(jié)詞原子命題和復合命題復合命題：相對于原子命題的是復合命題，它是由原子命題通過邏輯聯(lián)結(jié)詞進行適當?shù)慕M合而成的。復合命題的真值不僅依賴于這兩個組成它的命題，而且還依賴于這個聯(lián)結(jié)詞的意義。-19-第9講命題與邏輯聯(lián)結(jié)詞舉例p：3是素數(shù)；q：3是偶數(shù)利用聯(lián)結(jié)詞“不”、“或”、“且”等可分別構(gòu)成新命題：“非p”：3不是素數(shù)“p或q”：3是素數(shù)或偶數(shù)“p并且q”：3是素數(shù)且是偶數(shù)帶連接詞的命題：1）并非2是無理數(shù)。(T)2）4是偶數(shù)且4也是素數(shù)。(F)3）2或4是素數(shù)。(T)4）如果角A和角B是對頂角，則角A=角B。(T)5）兩個三角形全等當且僅當它們的3組對應邊相等。(T)

這幾個命題的真值不僅依賴于這兩個組成它的命題，而且還依賴于這些聯(lián)結(jié)詞的意義。像這樣的聯(lián)結(jié)詞稱為邏輯聯(lián)結(jié)詞（logicalconnectives）。練習

所以復合命題是由若干個簡單命題和若干個連接詞構(gòu)成的。

下面我們將連接詞也符號化。-22-第9講命題與邏輯聯(lián)結(jié)詞常用5個邏輯聯(lián)結(jié)詞一.否定詞(negation)：┐“┐P

表示P不成立”、“并非P”否定詞是一元運算。否定的是整個命題，并不是否定命題中個別的詞。“A和B都大于0”的否定：“A和B都不大于0”“A和B不都大于0”“A和B至少有一個不大于0”“A和B至少有一個小于等于0”“A大于0”的否定：“A不大于0”“A小于等于0”×-23-第9講命題與邏輯聯(lián)結(jié)詞常用的5個邏輯聯(lián)結(jié)詞真值表將復合命題的所有變元的所有取值列成表，就構(gòu)成真值表P┐P0110真值表*練習1：設(shè)P:今天是周三。則┐P表示什么？練習2：設(shè)Q:所有的自然數(shù)都是偶數(shù)。則┐Q表示什么？-25-第9講命題與邏輯聯(lián)結(jié)詞常用5個邏輯聯(lián)結(jié)詞二.合取詞(conjunction)：∧

p∧q表示“p并且q”、“p和q都成立”合取詞是二元運算只有當p和q均為真時，p∧q才是真的，否則，p∧q是假的∧是可交換的pqp∧q000010100111p:今天是星期四；q:今天上離散數(shù)學課；p∧q：今天是星期四并且上離散數(shù)學課；*例1.

如果P表示命題“你去了學?！?Q表示命題“我去了工廠”，那么P∧Q表示命題”你去了學校并且我去了工廠“。

P∧Q為真，當且僅當你、我分別去了學校和工廠。注:使用合取聯(lián)結(jié)詞時，不要求兩命題間一定有任何關(guān)系。例2：P:今天下雨了。

Q:教室里有100把椅子。則,P∧Q：今天下雨了且教室里有100把椅子。離散數(shù)學

第一章：命題邏輯對∧的說明∧是二元連接詞P∧Q中的P，Q可以沒有內(nèi)在聯(lián)系（如例2）∧具有對稱性，P∧Q與Q∧P的真值相同P∧┐P=F∧可以把若干個命題連接在一起.如，

P∧Q∧R∧S

補充練習:

將下列命題符號化。

(1)吳穎既用功又聰明。

(2)吳穎不僅用功而且聰明。

(3)吳穎雖然聰明，但不用功。

(4)張輝和王麗都是三好學生。

(5)張輝與王麗是同學。

步驟：先找原子命題并符號化再找連接詞將原命題符號化解

：首先將原子命題符號化：

p:吳穎用功。,

q:吳穎聰明。

r:張輝是三好學生。

s:王麗是三好學生。

u

:張輝與王麗是同學。

則(1)到(4)分別符號化為

p∧q，p∧q，q∧┐p，r∧s.

(5)是原子命題，符號化為u.補充練習:將下列命題符號化。

(1)吳穎既用功又聰明。

(2)吳穎不僅用功而且聰明。

(3)吳穎雖然聰明，但不用功。

(4)張輝和王麗都是三好學生。

(5)張輝與王麗是同學。

(1)到(4)都是復合命題，它們使用的聯(lián)結(jié)詞表面看來各不相同，但都是合取聯(lián)結(jié)詞，都應符號化為∧，在(5)中，雖然也使用了聯(lián)結(jié)詞“與”，但這個聯(lián)結(jié)詞“與”是聯(lián)結(jié)該句主語的，而整個句子仍是簡單陳述句，所以(5)是原子命題，-30-第9講命題與邏輯聯(lián)結(jié)詞常用5個邏輯聯(lián)結(jié)詞析取詞(disjunction)：∨

p∨q，“p成立或者q成立”、“p或q”析取詞是二元運算只有當p和q的真值均為假時，p∨q才是假的，否則,

p∨q總是真的pqp∨q000011101111p:我上午上離散數(shù)學；q:我上午上概率統(tǒng)計；p∨

q：我上午或者上離散數(shù)學，或者上概率統(tǒng)計；p:我上午一二節(jié)課上離散數(shù)學；q:我上午一二節(jié)課上概率統(tǒng)計；p∨

q：我上午一二節(jié)課要么上離散數(shù)學，要么上概率統(tǒng)計(不會上兩門)；同或異或

總結(jié)：析取∨一般代表漢語中的“或”，但漢語中的“或”是多含義的，見下表：或的含義例子說明可兼或晚會上她唱歌或跳舞二者均發(fā)生或二者之一發(fā)生排斥或

他上“師大”或“南開”非此即彼，不可兼得表示近似值的或他休息5或10分鐘近似數(shù)，5至10分鐘由析取的定義可知，∨表示可兼或。例1：

如果p，q分別表示“今晚我看書”和“今晚我看電視”，那么p∨q表示“今晚我看書或者看電視”。當我今晚看了書，或者看了電視，或者既看了書又看了電視時，p∨q為真，只是在我既不看書也不看電視時p∨q為假。

值得注意的是，這里的“或”是所謂可兼的，即當p和q有一為真時，確認p∨q為真。則原命題可表示為：例2.一晚上他在家看書或出去散步。解：不可兼或

P：他一晚上在家看書。Q：他一晚上出去散步。

不可兼或也稱排斥或，它表示這一新命題當P為真且Q為假時成真，或反過來，當P為假且Q為真時成真。P和Q均為真或均為假時，這一命題為假。即當P和Q中恰有一個為真時它成真，否則它為假。對∨的說明∨是二元連接詞P∨Q中的P，Q可以沒有內(nèi)在聯(lián)系（如例2）∨具有對稱性，P∧Q與Q∧P的真值相同P∨┐P=T∨可以把若干個命題連接在一起.如，

P∨Q∨R∨S-35-第9講命題與邏輯聯(lián)結(jié)詞常用5個邏輯聯(lián)結(jié)詞蘊涵詞(implication)：→

p→q，“如果p，那么q”、“p蘊涵q”、“p是q的充分條件”從真值表可以看出，只有當前提為真，而結(jié)論是假時，p→q才是假的pqp→q001011100111逆命題：q→p；否命題：┐p→┐q逆否命題：┐q→┐p命題和逆否命題有相同的真值（驗證一下）“如果今天是星期三，那么2+3=6”：前提為假，蘊涵命題為真；前提和結(jié)論之間可以沒有關(guān)系，稱為實質(zhì)蘊涵p:天晴；q:我爬山；只要天晴，我就爬山：

p→

q

只有天晴，我才爬山：q

→p

注意：在使用聯(lián)結(jié)詞→時，要特別注意以下幾點：

1．在自然語言中，“如果p，則q”中的前件p與后件q往往具有某種內(nèi)在聯(lián)系。而在數(shù)理邏輯中，p與q可以無任何內(nèi)在聯(lián)系。

2．在數(shù)學或其它自然科學中，“如果p，則q”往往表達的是前件p為真，后件q也為真的推理關(guān)系。但在數(shù)理邏輯中，作為一種規(guī)定，當p為假時，無論q是真是假，p→q均為真。也就是說，只有p為真q為假這一種情況使得復合命題p→q為假。

例1

將命題“如果天氣好，那么我去接你?！狈柣?。解：設(shè)p表示“天氣好”，q表示“我去接你”，那么，p→q表示原命題。

當天氣好時，

我去接了你，這時諾言p→q真；

我沒去接你，則諾言p→q假。

當天氣不好時，我無論去或不去接你均未食言，此時認定p→q為真是適當?shù)摹?/p>

注：較三個聯(lián)結(jié)詞難理解，但若要對命題間因果關(guān)系進行表達，則必須引用。例2：令P:天氣好，Q:我去公園試將下列命題符號化1）若天氣好，我就去公園。符號化為：2）僅當天氣好，我才去公園。符號化為：-39-第9講命題與邏輯聯(lián)結(jié)詞常用5個邏輯聯(lián)結(jié)詞雙向蘊涵詞(two-wayimplication)pq，“p當且僅當q”、

“如果p，那么q；反之亦然”只有當p和q的真值相同時，pq才取真的真值pq與(p→q)∧(q→p)有完全相同的真值。（驗證一下）pqpq001010100111“只有你健康，你才會感到快樂；只有感覺快樂你才健康”*例1

如果p表示命題“△ABC△A‘B’C‘”，

q表示命題“△ABC與△A‘B’C‘的三邊對應相等”，那么pq表示平面幾何中的一個真命題，因為p真時q顯然真，p假時q亦必然假，故p與q同真值。若q表示命題“△ABC與△A‘B’C‘的三內(nèi)角對應相等”那么pq不再是恒真的了，因p假時q未必為假。離散數(shù)學

第一章：命題邏輯練習:

將下列命題符號化，并討論它們的真值。

(1)根號5是無理數(shù)當且僅當加拿大位于亞洲。

(2)2+3＝5的充要條件是根號5是無理數(shù)。

(3)若兩圓A，B的面積相等，則它們的半徑相等；反之亦然。

(4)當王小紅心情愉快時，她就唱歌；反之，當她唱歌時，一定心情愉快。解

(1):令p：根號5是無理數(shù)，真值為1，

q：加拿大位于亞洲，真值為0，

則將(1)符號化為pq，其真值為0.

(2):令r：2＋3＝5，其真值為1，則將(2)符號化為rp，真值為1.

(3):令s：兩圓A，B面積相等，

t：兩圓A，B的半徑相等，

則將(3)符號化為st，雖然不知道s，t的真值，但由s與t的內(nèi)在聯(lián)系可知，st的真值為1.

(4):令u：王小紅心情愉快，

v：王小紅唱歌，

則將(4)符號化為uv.其真值要由具體情況而定。練習：填空已知為T，則P為（），Q為（）。已知為F，則P為（），Q為（）。已知P為F，則為（）。已知P為T，則為（）。已知為T，且P為F，則Q為（）。已知為F，則P為（），Q為（）。已知P為F，則為（）。已知Q為T，則為（）。已知為F，則P為（），Q為（）。已知P為T，為T，則Q為（）。TTTTTFFFFFTTTT

以上定義了五種最基本、最常用、也是最重要的聯(lián)結(jié)詞┐，∧，∨，→，，將它們組成一個集合{┐，∧，∨，→，

}，稱為一個聯(lián)結(jié)詞集。其中┐為一元聯(lián)結(jié)詞，其余的都是二元聯(lián)結(jié)詞。

使用這些聯(lián)結(jié)詞有什么好處呢？可以將復雜命題表示成簡單的符號公式。注意：4個聯(lián)接詞構(gòu)成的復合命題均可不顧及命題間是否有內(nèi)在聯(lián)系，而只是根據(jù)聯(lián)接詞和原子命題的真值確定它們的真值。-45-第9講命題與邏輯聯(lián)結(jié)詞命題公式(propositionformula)命題公式：是一個表達式，它是由命題常元、命題變元、聯(lián)結(jié)詞符號和圓括號所組成的一個字符串

歸納定義：（看16頁歸納定義）命題常元和命題變元是命題公式，也稱為原子公式或原子如果A，B是命題公式，那么（┐A）、（A∧B）、

（A∨B）、（A→B）、（AB）也是命題公式只有有限步引用條款（1）、（2）所組成的符號串是命題公式-46-第9講命題與邏輯聯(lián)結(jié)詞簡寫約定為了減少圓括號的使用，我們約定：省掉最外面的括號聯(lián)結(jié)詞的優(yōu)先級從高到低是┐、（∧、∨）、→、結(jié)合能力平等的聯(lián)結(jié)詞從左到右運算((┐p)→(q∨((r∧q)s)))┐p→q∨(r∧qs)-47-第9講命題與邏輯聯(lián)結(jié)詞指派(assignment)設(shè)公式A含有n個命題變元p1，p2

，…，pn記為A(p1,…,pn)給定這n個變元任意一組確定的值（每一變元都有取真或假兩種可能），公式A得到一個確定的值（1或0），我們稱這一組確定的值為公式A的一組完全指派常用表示指派，若在某一指派下A取真的真值，則稱弄真A，記為

(A)=1,反之稱弄假A，記為

(A)=0

-48-第9講命題與邏輯聯(lián)結(jié)詞指派舉例使公式A:((p∧q)∨┐r)p為真的指派(A)=11.((p∧q)∨┐r)=1，

(p)=1，2.((p∧q)∨┐r)=0，

(p)=0(┐r)=0,(r)=11.1.(q)=11.1.1.(r)=01.1.2.(r)=11.2.(q)=01.2.1.(r)=02.1.(q)=02.2.(q)=1(1,1,0)(1,1,1)(1,0,0)(0,0,1)(0,1,1)-49-第9講命題與邏輯聯(lián)結(jié)詞復合命題公式的真值表首先確定在公式中出現(xiàn)的命題變元的個數(shù)。寫出公式A的所有指派，一個指派為一行，若有n個命題變元，則有2n組指派，也就是說真值表有2n+1行。確定公式中聯(lián)結(jié)詞的個數(shù)，寫出單個聯(lián)結(jié)詞的真值，一般講，一個聯(lián)結(jié)詞對應著一列。

((p∧q)∨┐r)p的真值表pqrp∧q┐r(p∧q)∨┐r((p∧q)∨┐r)p00001100010001010011001100011000111101000011011111111011┐(PQ)0110原命題QP011111100000000000001111例2：上海到北京的14次列車是下午五點半開或六點開。復合命題的真值表

-51-第9講命題與邏輯聯(lián)結(jié)詞語句形式化舉例設(shè)p：a是偶數(shù)q：a是奇數(shù)r：a是質(zhì)數(shù)s：a=2，如何理解下述命題公式p∨q

p∧r→sp→（r→s）r∧┐s→q┐（q∨s）→┐rr→（q∨s）rq∨s-52-第9講命題與邏輯聯(lián)結(jié)詞語句形式化舉例我和他既是兄弟又是同學p∧q，其中：p：我和他是兄弟，q：我和他是同學我和他至少有一個要去外地p∨q，其中：p：我去外地，q：他去外地狗急跳墻p→q，其中：p：狗急了，q：狗跳墻除非他來，否則我不同他和解pq，(p→q)∧(┐p→┐q)，其中：p：他來，q：我同他和解-53-第9講命題與邏