命題邏輯的基本概念正規(guī)版資料

命題邏輯的基本概念第一頁，共32頁。1第一章命題邏輯的基本概念第一章主要(zhǔyào)內容命題與聯(lián)結詞命題及其分類聯(lián)結詞與復合命題命題公式及其賦值第二頁，共32頁。2命題與真值命題：判斷結果惟一(wéiyī)的陳述句命題的真值：判斷的結果真值的取值：真與假真命題與假命題注意：感嘆句、祈使句、疑問句都不是命題陳述句中的悖論，判斷結果不惟一(wéiyī)確定的不是命題1.1命題(mìngtí)與聯(lián)結詞第三頁，共32頁。3例1

下列句子中那些是命題？

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

(5)這個蘋果真大呀！

(6)請不要講話！

(7)2050年元旦下大雪.假命題(mìngtí)命題(mìngtí)概念真命題(mìngtí)不是命題不是命題不是命題不是命題命題，但真值現(xiàn)在不知道第四頁，共32頁。4命題分類：簡單命題（也稱原子命題）與復合命題簡單命題符號化用小寫(xiǎoxiě)英文字母p,q,r,…,pi,qi,ri(i1)表示簡單命題用“1”表示真，用“0”表示假例如，令p：是有理數(shù)，則p的真值為0，q：2+5=7，則q的真值為1

命題(mìngtí)分類第五頁，共32頁。5否定(fǒudìng)、合取、析取聯(lián)結詞定義1.3設p,q為兩個命題，復合命題“p或q”稱作(chēnɡzuò)p與q的析取式，記作p∨q，∨稱作(chēnɡzuò)析取聯(lián)結詞.規(guī)定p∨q為假當且僅當p與q同時為假.定義1.1設p為命題，復合命題“非p”(或“p的否定”)稱為p的否定式，記作p，符號稱作(chēnɡzuò)否定聯(lián)結詞.規(guī)定p為真當且僅當p為假.定義1.2

設p,q為兩個命題，復合命題“p并且q”(或“p與q”)稱為p與q的合取式，記作p∧q，∧稱作合取聯(lián)結詞.規(guī)定p∧q為真當且僅當p與q同時為真.第六頁，共32頁。6命題的真值：判斷的結果(5)pq,(6)pq或qp例6寫出下列公式的真值表,并求它們(tāmen)的成真賦值和成假(4)張輝與王麗都是三好生.公式(gōngshì)賦值9將命題公式A在所有賦值下取值的情況列成表,稱作命題：判斷結果惟一(wéiyī)的陳述句第三十一頁，共32頁。(6)除非小王(xiǎowánɡ)穿羽絨服，否則天不冷.pq的邏輯關系：p與q互為充分必要條件其中要特別注意理解pq的涵義.pq(4)王小紅或李大明中的一人是物理組成員.001,011,100,111是成假賦值.第三十一頁，共32頁。(1)若A在它的任何賦值下均為真,則稱A為重言式或永真式;例2將下列命題符號化.(1)吳穎既用功(yònggōng)又聰明.(2)吳穎不僅用功(yònggōng)而且聰明.(3)吳穎雖然聰明，但不用功(yònggōng).(4)張輝與王麗都是三好生.(5)張輝與王麗是同學.合取聯(lián)結詞的實例(shílì)第七頁，共32頁。7解令p:吳穎用功,q:吳穎聰明(1)pq(2)pq(3)pq(4)設p:張輝是三好生,q:王麗是三好生pq(5)p:張輝與王麗是同學(1)—(3)說明描述(miáoshù)合取式的靈活性與多樣性(4)—(5)要求分清“與”所聯(lián)結的成分合取聯(lián)結詞的實例(shílì)第八頁，共32頁。8例3將下列命題符號化(1)2或4是素數(shù).(2)2或3是素數(shù).(3)4或6是素數(shù).(4)小元元只能拿一個(yīɡè)蘋果或一個(yīɡè)梨.(5)王小紅生于1975年或1976年.析取聯(lián)結詞的實例(shílì)第九頁，共32頁。9解(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:小元元拿一個蘋果(píngguǒ),q:小元元拿一個梨(pq)(pq)(5)p:王小紅生于1975年,q:王小紅生于1976年,(pq)(pq)或pq(1)—(3)為相容或(4)—(5)為排斥或,符號化時(5)可有兩種形式，而(4)則不能析取聯(lián)結詞的實例(shílì)第十頁，共32頁。10定義1.4設p,q為兩個命題，復合命題“如果p,則q”稱作p與q的蘊涵式，記作pq，并稱p是蘊涵式的前件(qiánjiàn)，q為蘊涵式的后件，稱作蘊涵聯(lián)結詞.規(guī)定：pq為假當且僅當p為真q為假.蘊涵(yùnhán)聯(lián)結詞(1)pq的邏輯關系：q為p的必要條件(2)“如果p,則q”有很多不同的表述方法：若p，就q只要p，就qp僅當q只有q才p除非q,才p或除非q，否則非p，…．(3)當p為假時，pq恒為真，稱為(chēnɡwéi)空證明(4)常出現(xiàn)的錯誤：不分充分與必要條件第十一頁，共32頁。11例4設p：天冷，q：小王(xiǎowánɡ)穿羽絨服，將下列命題符號化(1)只要天冷，小王(xiǎowánɡ)就穿羽絨服.(2)因為天冷，所以小王(xiǎowánɡ)穿羽絨服.(3)若小王(xiǎowánɡ)不穿羽絨服，則天不冷.(4)只有天冷，小王(xiǎowánɡ)才穿羽絨服.(5)除非天冷，小王(xiǎowánɡ)才穿羽絨服.(6)除非小王(xiǎowánɡ)穿羽絨服，否則天不冷.(7)如果天不冷，則小王(xiǎowánɡ)不穿羽絨服.(8)小王(xiǎowánɡ)穿羽絨服僅當天冷的時候.蘊涵(yùnhán)聯(lián)結詞的實例pq注意(zhùyì)：pq與qp等值（真值相同）pqpqqpqppqqpqp第十二頁，共32頁。12定義1.5設p,q為兩個命題，復合命題“p當且僅當q”稱作p與q的等價(děngjià)式，記作pq，稱作等價(děngjià)聯(lián)結詞.規(guī)定pq為真當且僅當p與q同時為真或同時為假.pq的邏輯關系：p與q互為充分必要條件等價(děngjià)聯(lián)結詞例5求下列復合命題的真值(1)2+2＝4當且僅當3+3＝6.(2)2+2＝4當且僅當3是偶數(shù).(3)2+2＝4當且僅當太陽從東方升起(shēnɡqǐ).(4)2+2＝4當且僅當美國位于非洲.(5)函數(shù)f(x)在x0可導的充要條件是它在x0連續(xù).10010第十三頁，共32頁。13本小節(jié)中p,q,r,…均表示(biǎoshì)命題.聯(lián)結詞集為{,,,,}，p,pq,pq,pq,pq為基本復合命題.其中要特別注意理解pq的涵義.反復使用{,,,,}中的聯(lián)結詞組成更為復雜的復合命題. 設p:是無理數(shù)，q:3是奇數(shù)，r:蘋果(píngguǒ)是方的，s:太陽繞地球轉則復合命題(pq)((rs)p)是假命題.小結聯(lián)結詞的運算順序：,,,,,同級(tónɡjí)按先出現(xiàn)者先運算.第十四頁，共32頁。141.2命題(mìngtí)公式及其賦值命題(mìngtí)變項與合式公式命題(mìngtí)變項合式公式合式公式的層次公式的賦值公式賦值公式類型真值表第十五頁，共32頁。15命題(mìngtí)變項與合式公式命題(mìngtí)常項命題(mìngtí)變項（命題(mìngtí)變元）常項與變項均用p,q,r,…,pi,qi,ri,…,等表示.定義1.6合式公式（簡稱公式）的遞歸定義：(1)單個命題變項和命題常項是合式公式,稱作原子(yuánzǐ)命題公式(2)若A是合式公式，則(A)也是(3)若A,B是合式公式，則(AB),(AB),(AB),(AB)也是(4)只有有限次地應用(1)—(3)形成的符號串才是合式公式幾點說明：歸納或遞歸定義,元語言與對象語言,外層括號可以省去第十六頁，共32頁。16合式公式的層次(céngcì)定義1.7(1)若公式(gōngshì)A是單個命題變項，則稱A為0層公式(gōngshì).(2)稱A是n+1(n≥0)層公式(gōngshì)是指下面情況之一：(a)A=B,B是n層公式(gōngshì)；(b)A=BC,其中B,C分別為i層和j層公式(gōngshì)，且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)若公式(gōngshì)A的層次為k,則稱A為k層公式(gōngshì).例如公式(gōngshì)A=p,B=p,C=pq,D=(pq)r,E=((pq)r)(rs)分別為0層，1層，2層，3層，4層公式(gōngshì).第十七頁，共32頁。17定義1.8設p1,p2,…,pn是出現(xiàn)在公式A中的全部命題變項,給p1,p2,…,pn各指定一個(yīɡè)真值,稱為對A的一個(yīɡè)賦值或解釋.若使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是成假賦值.公式(gōngshì)賦值第十八頁，共32頁。18定義1.9將命題公式A在所有賦值下取值的情況列成表,稱作A的真值表.構造真值表的步驟(bùzhòu):(1)找出公式中所含的全部命題變項p1,p2,…,pn(若無下角標則按字母順序排列),列出2n個全部賦值,從000開始,按二進制加法,每次加1,直至111為止.(2)按從低到高的順序寫出公式的各個層次.(3)對每個賦值依次計算各層次的真值,直到最后計算出公式的真值為止.真值表第十九頁，共32頁。19例6寫出下列公式的真值表,并求它們(tāmen)的成真賦值和成假賦值:(1)(pq)r(2)(qp)qp(3)(pq)q真值表第二十頁，共32頁。20命題(mìngtí)分類(1)單個命題變項和命題常項是合式公式,稱作原子(yuánzǐ)命題公式(3)(qr)(pr)(2)按從低到高的順序寫出公式的各個層次.規(guī)定p∧q為真當且僅當p與q同時為真.給p1,p2,…,pn各指定一個(yīɡè)真值,稱為對A的一個(yīɡè)賦值或解釋.(9)pq或pq練習(liànxí)1如000,010,101,110是(pq)r的成真賦值(4)—(5)為排斥或,符號化時(5)可有兩種形式，而(4)則不能(3)(pq)(pr)例如公式(gōngshì)A=p,B=p,C=pq,D=(pq)r,(6)如果(rúguǒ)交通不阻塞，他就不會遲到.(5)函數(shù)f(x)在x0可導的充要條件是它在x0連續(xù).二進制加法,每次加1,直至111為止.成真賦值:00,01,10,11;無成(wúchéng)假賦值(1)A=(pq)r成真賦值:000,001,010,100,110;成假賦值:011,101,111

pqrpq

r

(pq)r000001010011100101110111001111111010101011101010真值表1第二十一頁，共32頁。21(2)B＝(qp)qp成真賦值:00,01,10,11;無成(wúchéng)假賦值p

q

qp(qp)q(qp)qp00011011101100011111真值表2第二十二頁，共32頁。22(3)C＝

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

q

ppq

(pq)

(pq)q000110111100110100100000真值表3第二十三頁，共32頁。23公式(gōngshì)的類型定義1.10(1)若A在它的任何賦值下均為真,則稱A為重言式或永真式;(2)若A在它的任何賦值下均為假,則稱A為矛盾(máodùn)式或永假式;(3)若A不是矛盾(máodùn)式,則稱A是可滿足式.由例1可知,(pq)r,(qp)qp,(pq)q分別為非重言式的可滿足式,重言式,矛盾(máodùn)式.注意：重言式是可滿足式，但反之不真.真值表的用途:求出公式的全部成真賦值與成假賦值,判斷公式的類型第二十四頁，共32頁。24第一章習題課主要內容命題、真值、簡單命題與復合命題、命題符號化聯(lián)結詞,,,,及復合命題符號化命題公式及層次公式的類型真值表及應用基本要求深刻理解各聯(lián)結詞的邏輯關系,熟練地將命題符號化會求復合命題的真值深刻理解合式公式及重言式、矛盾式、可滿足式等概念熟練地求公式的真值表，并用(bìnɡyònɡ)它求公式的成真賦值與成假賦值及判斷公式類型第二十五頁，共32頁。251.將下列命題符號化(1)豆沙包是由面粉和紅小豆做成的.(2)蘋果樹和梨樹都是落葉喬木.(3)王小紅或李大明是物理組成員.(4)王小紅或李大明中的一人是物理組成員.(5)由于交通阻塞，他遲到了.(6)如果(rúguǒ)交通不阻塞，他就不會遲到.(7)他沒遲到，所以交通沒阻塞.(8)除非交通阻塞，否則他不會遲到.(9)他遲到當且僅當交通阻塞.練習(liànxí)1第二十六頁，共32頁。26提示：分清復合(fùhé)命題與簡單命題分清相容或與排斥或分清必要與充分條件及充分必要條件答案:(1)是簡單命題(2)是合取式(3)是析取式（相容或）(4)是析取式（排斥或）設p:交通阻塞，q:他遲到(5)pq,(6)pq或qp(7)qp或pq,(8)qp或pq(9)pq或pq可見(5)與(7)，(6)與(8)相同（等值）練習(liànxí)1解答第二十七頁，共32頁。272.設p:2是素數(shù)q:北京(běijīnɡ)比天津人口多r:美國的首都是舊金山求下面命題的真值(1)(pq)r(2)(qr)(pr)(3)(qr)(pr)(4)(qp)((pr)(rq))0練習(liànxí)2100第二十八頁，共32頁。283.用真值表判斷(pànduàn)下面公式的類型(1)pr