命題邏輯的基本概念

命題邏輯的基本概念1第一頁，共三十二頁，編輯于2023年，星期五第一章命題邏輯的基本概念第一章主要內(nèi)容命題與聯(lián)結(jié)詞命題及其分類聯(lián)結(jié)詞與復(fù)合命題命題公式及其賦值2第二頁，共三十二頁，編輯于2023年，星期五命題與真值命題：判斷結(jié)果惟一的陳述句命題的真值：判斷的結(jié)果真值的取值：真與假真命題與假命題注意：感嘆句、祈使句、疑問句都不是命題陳述句中的悖論，判斷結(jié)果不惟一確定的不是命題

1.1命題與聯(lián)結(jié)詞3第三頁，共三十二頁，編輯于2023年，星期五例1

下列句子中那些是命題？

(1)是有理數(shù).(2)2+5=7.(3)x+5>3.(4)你去教室嗎？

(5)這個蘋果真大呀！

(6)請不要講話！

(7)2050年元旦下大雪.假命題命題概念真命題不是命題不是命題不是命題不是命題命題，但真值現(xiàn)在不知道4第四頁，共三十二頁，編輯于2023年，星期五命題分類：簡單命題（也稱原子命題）與復(fù)合命題簡單命題符號化用小寫英文字母p,q,r,…,pi,qi,ri(i1)表示簡單命題用“1”表示真，用“0”表示假例如，令

p：是有理數(shù)，則p的真值為0，

q：2+5=7，則q的真值為1

命題分類5第五頁，共三十二頁，編輯于2023年，星期五否定、合取、析取聯(lián)結(jié)詞定義1.3

設(shè)p,q為兩個命題，復(fù)合命題“p或q”稱作p與q的析取式，記作p∨q，∨稱作析取聯(lián)結(jié)詞.規(guī)定p∨q為假當(dāng)且僅當(dāng)p與q同時為假.定義1.1

設(shè)p為命題，復(fù)合命題“非p”(或“p的否定”)稱為p的否定式，記作p，符號稱作否定聯(lián)結(jié)詞.規(guī)定p

為真當(dāng)且僅當(dāng)p為假.定義1.2

設(shè)p,q為兩個命題，復(fù)合命題“p并且q”(或“p與q”)稱為p與q的合取式，記作p∧q，∧稱作合取聯(lián)結(jié)詞.規(guī)定p∧q為真當(dāng)且僅當(dāng)p與q同時為真.6第六頁，共三十二頁，編輯于2023年，星期五例2

將下列命題符號化.(1)吳穎既用功又聰明.(2)吳穎不僅用功而且聰明.(3)吳穎雖然聰明，但不用功.(4)張輝與王麗都是三好生.(5)張輝與王麗是同學(xué).合取聯(lián)結(jié)詞的實例7第七頁，共三十二頁，編輯于2023年，星期五解令p:吳穎用功,q:吳穎聰明

(1)pq(2)pq(3)pq(4)設(shè)p:張輝是三好生,q:王麗是三好生

pq(5)p:張輝與王麗是同學(xué)(1)—(3)說明描述合取式的靈活性與多樣性(4)—(5)要求分清“與”所聯(lián)結(jié)的成分合取聯(lián)結(jié)詞的實例8第八頁，共三十二頁，編輯于2023年，星期五例3

將下列命題符號化(1)2或4是素數(shù).(2)2或3是素數(shù).(3)4或6是素數(shù).(4)小元元只能拿一個蘋果或一個梨.(5)王小紅生于1975年或1976年.析取聯(lián)結(jié)詞的實例9第九頁，共三十二頁，編輯于2023年，星期五解(1)令p:2是素數(shù),q:4是素數(shù),pq(2)令p:2是素數(shù),q:3是素數(shù),pq(3)令p:4是素數(shù),q:6是素數(shù),pq(4)令p:小元元拿一個蘋果,q:小元元拿一個梨

(pq)(pq)(5)p:王小紅生于1975年,q:王小紅生于1976年,(pq)(pq)或pq(1)—(3)為相容或(4)—(5)為排斥或,符號化時(5)可有兩種形式，而(4)則不能析取聯(lián)結(jié)詞的實例10第十頁，共三十二頁，編輯于2023年，星期五定義1.4

設(shè)p,q為兩個命題，復(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為假.蘊(yùn)涵聯(lián)結(jié)詞(1)pq的邏輯關(guān)系：q為p的必要條件(2)“如果p,則q”有很多不同的表述方法：若p，就q

只要p，就qp僅當(dāng)q

只有q

才p

除非q,才p或除非q，否則非p，…．

(3)當(dāng)p為假時，pq恒為真，稱為空證明

(4)常出現(xiàn)的錯誤：不分充分與必要條件11第十一頁，共三十二頁，編輯于2023年，星期五例4

設(shè)p：天冷，q：小王穿羽絨服，將下列命題符號化(1)只要天冷，小王就穿羽絨服.(2)因為天冷，所以小王穿羽絨服.(3)若小王不穿羽絨服，則天不冷.(4)只有天冷，小王才穿羽絨服.(5)除非天冷，小王才穿羽絨服.(6)除非小王穿羽絨服，否則天不冷.(7)如果天不冷，則小王不穿羽絨服.(8)小王穿羽絨服僅當(dāng)天冷的時候.蘊(yùn)涵聯(lián)結(jié)詞的實例pq注意：pq與qp等值（真值相同）pqpqqpqppqqpqp12第十二頁，共三十二頁，編輯于2023年，星期五定義1.5

設(shè)p,q為兩個命題，復(fù)合命題“p當(dāng)且僅當(dāng)q”稱作p與q的等價式，記作pq，稱作等價聯(lián)結(jié)詞.規(guī)定pq為真當(dāng)且僅當(dāng)p與q同時為真或同時為假.pq的邏輯關(guān)系：p與q互為充分必要條件等價聯(lián)結(jié)詞例5

求下列復(fù)合命題的真值(1)2+2＝4當(dāng)且僅當(dāng)3+3＝6.(2)2+2＝4當(dāng)且僅當(dāng)3是偶數(shù).(3)2+2＝4當(dāng)且僅當(dāng)太陽從東方升起.(4)2+2＝4當(dāng)且僅當(dāng)美國位于非洲.(5)函數(shù)f(x)在x0

可導(dǎo)的充要條件是它在x0連續(xù).1001013第十三頁，共三十二頁，編輯于2023年，星期五本小節(jié)中p,q,r,…均表示命題.聯(lián)結(jié)詞集為{,,,,}，p,pq,pq,pq,pq為基本復(fù)合命題.其中要特別注意理解pq的涵義.反復(fù)使用{,,,,}中的聯(lián)結(jié)詞組成更為復(fù)雜的復(fù)合命題.

設(shè)p:是無理數(shù)，q:3是奇數(shù)，

r:蘋果是方的，s:太陽繞地球轉(zhuǎn)則復(fù)合命題(pq)((rs)p)是假命題.小結(jié)聯(lián)結(jié)詞的運算順序：,,,,,同級按先出現(xiàn)者先運算.14第十四頁，共三十二頁，編輯于2023年，星期五1.2

命題公式及其賦值命題變項與合式公式命題變項合式公式合式公式的層次公式的賦值公式賦值公式類型真值表15第十五頁，共三十二頁，編輯于2023年，星期五命題變項與合式公式命題常項命題變項（命題變元）常項與變項均用p,q,r,…,pi,qi,ri,…,等表示.定義1.6合式公式（簡稱公式）的遞歸定義：

(1)單個命題變項和命題常項是合式公式,稱作原子命題公式

(2)若A是合式公式，則(A)也是

(3)若A,B是合式公式，則(AB),(AB),(AB),(AB)也是

(4)只有有限次地應(yīng)用(1)—(3)形成的符號串才是合式公式幾點說明：歸納或遞歸定義,元語言與對象語言,外層括號可以省去16第十六頁，共三十二頁，編輯于2023年，星期五合式公式的層次定義1.7(1)若公式A是單個命題變項，則稱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層公式.例如公式A=p,B=p,C=pq,D=(pq)r,E=((pq)r)(rs)

分別為0層，1層，2層，3層，4層公式.17第十七頁，共三十二頁，編輯于2023年，星期五定義1.8

設(shè)p1,p2,…,pn是出現(xiàn)在公式A中的全部命題變項,給p1,p2,…,pn各指定一個真值,稱為對A的一個賦值或解釋.若使A為1,則稱這組值為A的成真賦值;若使A為0,則稱這組值為A的成假賦值.幾點說明：A中僅出現(xiàn)p1,p2,…,pn，給A賦值=12…n是指

p1=1,p2=2,…,pn=n,i=0或1,i之間不加標(biāo)點符號

A中僅出現(xiàn)p,q,r,…,給A賦值123…是指

p=1,q=2,r=3…含n個命題變項的公式有2n個賦值.

如000,010,101,110是(pq)r的成真賦值

001,011,100,111是成假賦值.公式賦值18第十八頁，共三十二頁，編輯于2023年，星期五定義1.9

將命題公式A在所有賦值下取值的情況列成表,稱作A的真值表.構(gòu)造真值表的步驟:(1)找出公式中所含的全部命題變項p1,p2,…,pn(若無下角標(biāo)則按字母順序排列),列出2n個全部賦值,從000開始,按二進(jìn)制加法,每次加1,直至111為止.

(2)按從低到高的順序?qū)懗龉降母鱾€層次.(3)對每個賦值依次計算各層次的真值,直到最后計算出公式的真值為止.真值表19第十九頁，共三十二頁，編輯于2023年，星期五例6

寫出下列公式的真值表,并求它們的成真賦值和成假賦值:(1)(pq)r(2)(qp)qp(3)(pq)q真值表20第二十頁，共三十二頁，編輯于2023年，星期五(1)A=(pq)r成真賦值:000,001,010,100,110;成假賦值:011,101,111

pqrpq

r

(pq)r000001010011100101110111001111111010101011101010真值表121第二十一頁，共三十二頁，編輯于2023年，星期五(2)B＝(qp)qp成真賦值:00,01,10,11;無成假賦值p

q

qp(qp)q(qp)qp00011011101100011111真值表222第二十二頁，共三十二頁，編輯于2023年，星期五(3)C＝

(pq)q的真值表成假賦值:00,01,10,11;無成真賦值p

q

ppq

(pq)

(pq)q000110111100110100100000真值表323第二十三頁，共三十二頁，編輯于2023年，星期五公式的類型定義1.10

(1)若A在它的任何賦值下均為真,則稱A為重言式或永真式;(2)若A在它的任何賦值下均為假,則稱A為矛盾式或永假式;(3)若A不是矛盾式,則稱A是可滿足式.由例1可知,(pq)r,(qp)qp,(pq)q

分別為非重言式的可滿足式,重言式,矛盾式.注意：重言式是可滿足式，但反之不真.真值表的用途:

求出公式的全部成真賦值與成假賦值,判斷公式的類型24第二十四頁，共三十二頁，編輯于2023年，星期五第一章習(xí)題課主要內(nèi)容命題、真值、簡單命題與復(fù)合命題、命題符號化聯(lián)結(jié)詞,,,,及復(fù)合命題符號化命題公式及層次公式的類型真值表及應(yīng)用基本要求深刻理解各聯(lián)結(jié)詞的邏輯關(guān)系,熟練地將命題符號化會求復(fù)合命題的真值深刻理解合式公式及重言式、矛盾式、可滿足式等概念熟練地求公式的真值表，并用它求公式的成真賦值與成假賦值及判斷公式類型25第二十五頁，共三十二頁，編輯于2023年，星期五1.將下列命題符號化

(1)豆沙包是由面粉和紅小豆做成的.(2)蘋果樹和梨樹都是落葉喬木.(3)王小紅或李大明是物理組成員.(4)王小紅或李大明中的一人是物理組成員.(5)由于交通阻塞，他遲到了.(6)如果交通不阻塞，他就不會遲到.(7)他沒遲到，所以交通沒阻塞.(8)除非交通阻塞，否則他不會遲到.(9)他遲到當(dāng)且僅當(dāng)交通阻塞.練習(xí)126第二十六頁，共三十二頁，編輯于2023年，星期五提示：分清復(fù)合命題與簡單命題分清相容或與排斥或分清必要與充分條件及充分必要條件答案:(1)是簡單命題(2)是合取式

(3)是析取式（相容或）(4)是析取式（排斥或）設(shè)p:交通阻塞，q:他遲到

(5)pq,(6)pq或qp(7)qp

或pq,(8)qp或pq(9)pq

或pq可見(5)與(7)，(6)與(8)相同（等值）練習(xí)1解答27第二十七頁，共三十二頁，編輯于2023年，星期五2.設(shè)p:2是素數(shù)

q:北京比天津人口多

r:美國的首都是舊金山求下面命題的真值

(1)(pq)r(2)(qr)(pr)(3)(qr)(pr)(4)(qp)((pr)(rq))0練習(xí)210028第二十八頁，共三十二頁，編輯于2023年，星期五3.用真值表判斷下面公式的類型

(1)pr(qp)(2)((pq)