命題邏輯的基本概念

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

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

下列句子中那些是命題？

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

(5)這個蘋果真大呀！

(6)請不要講話！

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

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

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

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

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

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

為真當且僅當p為假.定義1.2

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

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

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

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

將下列命題符號化(1)2或4是素數(shù).(2)2或3是素數(shù).(3)4或6是素數(shù).(4)小元元只能拿一個蘋果或一個梨.(5)王小紅生于1975年或1976年.析取聯(lián)結詞的實例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)結詞的實例10第十頁，共三十二頁，編輯于2023年，星期五定義1.4

設p,q為兩個命題，復合命題“如果p,則q”稱作p與q的蘊涵式，記作pq，并稱p是蘊涵式的前件，q為蘊涵式的后件，稱作蘊涵聯(lián)結詞.規(guī)定：pq為假當且僅當p為真q為假.蘊涵聯(lián)結詞(1)pq的邏輯關系：q為p的必要條件(2)“如果p,則q”有很多不同的表述方法：若p，就q

只要p，就qp僅當q

只有q

才p

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

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

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

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

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

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

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

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

r:蘋果是方的，s:太陽繞地球轉(zhuǎn)則復合命題(pq)((rs)p)是假命題.小結聯(lián)結詞的運算順序：,,,,,同級按先出現(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)只有有限次地應用(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

設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之間不加標點符號

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的真值表.構造真值表的步驟:(1)找出公式中所含的全部命題變項p1,p2,…,pn(若無下角標則按字母順序排列),列出2n個全部賦值,從000開始,按二進制加法,每次加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年，星期五第一章習題課主要內(nèi)容命題、真值、簡單命題與復合命題、命題符號化聯(lián)結詞,,,,及復合命題符號化命題公式及層次公式的類型真值表及應用基本要求深刻理解各聯(lián)結詞的邏輯關系,熟練地將命題符號化會求復合命題的真值深刻理解合式公式及重言式、矛盾式、可滿足式等概念熟練地求公式的真值表，并用它求公式的成真賦值與成假賦值及判斷公式類型25第二十五頁，共三十二頁，編輯于2023年，星期五1.將下列命題符號化

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

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

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

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

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

q:北京比天津人口多

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

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

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