第1章 命題邏輯的基本概念課件

數(shù)理邏輯主要內(nèi)容命題邏輯基本概念命題邏輯等值演算命題邏輯推理理論一階邏輯基本概念一階邏輯等值演算與推理第一部分?jǐn)?shù)理邏輯1第1章命題邏輯的基本概念第一章命題邏輯的基本概念第一章主要內(nèi)容命題與聯(lián)結(jié)詞命題及其分類聯(lián)結(jié)詞與復(fù)合命題命題公式及其賦值2第1章命題邏輯的基本概念命題與真值命題：判斷結(jié)果惟一的陳述句命題的真值：判斷的結(jié)果真值的取值：真與假真命題與假命題注意：感嘆句、祈使句、疑問句都不是命題陳述句中的悖論，判斷結(jié)果不惟一確定的不是命題

1.1命題與聯(lián)結(jié)詞3第1章命題邏輯的基本概念例1

下列句子中那些是命題？

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

(5)這個(gè)蘋果真大呀！

(6)請不要講話！

(7)2050年元旦下大雪.

假命題命題概念

真命題不是命題不是命題不是命題不是命題命題，但真值現(xiàn)在不知道4第1章命題邏輯的基本概念命題分類：簡單命題（也稱原子命題）與復(fù)合命題簡單命題符號(hào)化用小寫英文字母p,q,r,…,pi,qi,ri(i

1)表示簡單命題用“1”表示真，用“0”表示假例如，令

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

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

命題分類5第1章命題邏輯的基本概念否定、合取、析取聯(lián)結(jié)詞定義1.3

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

設(shè)p為命題，復(fù)合命題“非p”(或“p的否定”)稱為p的否定式，記作

p，符號(hào)

稱作否定聯(lián)結(jié)詞.規(guī)定

p

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

設(shè)p,q為兩個(gè)命題，復(fù)合命題“p并且q”(或“p與q”)稱為p與q的合取式，記作p∧q，∧稱作合取聯(lián)結(jié)詞.規(guī)定p∧q為真當(dāng)且僅當(dāng)p與q同時(shí)為真.6第1章命題邏輯的基本概念例2

將下列命題符號(hào)化.(1)吳穎既用功又聰明.(2)吳穎不僅用功而且聰明.(3)吳穎雖然聰明，但不用功.(4)張輝與王麗都是三好生.(5)張輝與王麗是同學(xué).合取聯(lián)結(jié)詞的實(shí)例7第1章命題邏輯的基本概念解令p:吳穎用功,q:吳穎聰明

(1)p

q(2)p

q(3)

p

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

p

q(5)p:張輝與王麗是同學(xué)(1)—(3)說明描述合取式的靈活性與多樣性(4)—(5)要求分清“與”所聯(lián)結(jié)的成分合取聯(lián)結(jié)詞的實(shí)例8第1章命題邏輯的基本概念例3

將下列命題符號(hào)化(1)2或4是素?cái)?shù).(2)2或3是素?cái)?shù).(3)4或6是素?cái)?shù).(4)小元元只能拿一個(gè)蘋果或一個(gè)梨.(5)王小紅生于1975年或1976年.析取聯(lián)結(jié)詞的實(shí)例9第1章命題邏輯的基本概念解(1)令p:2是素?cái)?shù),q:4是素?cái)?shù),p

q(2)令p:2是素?cái)?shù),q:3是素?cái)?shù),p

q(3)令p:4是素?cái)?shù),q:6是素?cái)?shù),p

q(4)令p:小元元拿一個(gè)蘋果,q:小元元拿一個(gè)梨

(p

q)(p

q)(5)p:王小紅生于1975年,q:王小紅生于1976年,(p

q)(p

q)或p

q(1)—(3)為相容或(4)—(5)為排斥或,符號(hào)化時(shí)(5)可有兩種形式，而(4)則不能析取聯(lián)結(jié)詞的實(shí)例10第1章命題邏輯的基本概念定義1.4

設(shè)p,q為兩個(gè)命題，復(fù)合命題“如果p,則q”稱作p與q的蘊(yùn)涵式，記作p

q，并稱p是蘊(yùn)涵式的前件，q為蘊(yùn)涵式的后件，

稱作蘊(yùn)涵聯(lián)結(jié)詞.規(guī)定：p

q為假當(dāng)且僅當(dāng)p為真q為假.蘊(yùn)涵聯(lián)結(jié)詞(1)p

q的邏輯關(guān)系：q為p的必要條件(2)“如果p,則q”有很多不同的表述方法：若p，就q

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

只有q

才p

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

(3)當(dāng)p為假時(shí)，p

q恒為真，稱為空證明

(4)常出現(xiàn)的錯(cuò)誤：不分充分與必要條件11第1章命題邏輯的基本概念例4

設(shè)p：天冷，q：小王穿羽絨服，將下列命題符號(hào)化(1)只要天冷，小王就穿羽絨服.(2)因?yàn)樘炖洌孕⊥醮┯鸾q服.(3)若小王不穿羽絨服，則天不冷.(4)只有天冷，小王才穿羽絨服.(5)除非天冷，小王才穿羽絨服.(6)除非小王穿羽絨服，否則天不冷.(7)如果天不冷，則小王不穿羽絨服.(8)小王穿羽絨服僅當(dāng)天冷的時(shí)候.蘊(yùn)涵聯(lián)結(jié)詞的實(shí)例p

q注意：p

q與

q

p等值（真值相同）p

qp

qq

pq

pp

qq

pq

p12第1章命題邏輯的基本概念定義1.5

設(shè)p,q為兩個(gè)命題，復(fù)合命題“p當(dāng)且僅當(dāng)q”稱作p與q的等價(jià)式，記作p

q，

稱作等價(jià)聯(lián)結(jié)詞.規(guī)定p

q為真當(dāng)且僅當(dāng)p與q同時(shí)為真或同時(shí)為假.p

q的邏輯關(guān)系：p與q互為充分必要條件等價(jià)聯(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第1章命題邏輯的基本概念本小節(jié)中p,q,r,…均表示命題.聯(lián)結(jié)詞集為{

,

,

,

,

}，

p,p

q,p

q,p

q,p

q為基本復(fù)合命題.其中要特別注意理解p

q的涵義.反復(fù)使用{

,

,

,

,

}中的聯(lián)結(jié)詞組成更為復(fù)雜的復(fù)合命題.

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

r:蘋果是方的，s:太陽繞地球轉(zhuǎn)則復(fù)合命題(p

q)

((r

s)

p)是假命題.小結(jié)聯(lián)結(jié)詞的運(yùn)算順序：

,

,

,

,

,同級(jí)按先出現(xiàn)者先運(yùn)算.14第1章命題邏輯的基本概念1.2

命題公式及其賦值命題變項(xiàng)與合式公式命題變項(xiàng)合式公式合式公式的層次公式的賦值公式賦值公式類型真值表15第1章命題邏輯的基本概念命題變項(xiàng)與合式公式

命題常項(xiàng)命題變項(xiàng)（命題變元）常項(xiàng)與變項(xiàng)均用p,q,r,…,pi,qi,ri,…,等表示.定義1.6合式公式（簡稱公式）的遞歸定義：

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

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

A)也是

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

B),(A

B),(A

B),(A

B)也是

(4)只有有限次地應(yīng)用(1)—(3)形成的符號(hào)串才是合式公式幾點(diǎn)說明：歸納或遞歸定義,元語言與對象語言,外層括號(hào)可以省去16第1章命題邏輯的基本概念合式公式的層次定義1.7(1)若公式A是單個(gè)命題變項(xiàng)，則稱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層公式.例如公式A=p,B=

p,C=

p

q,D=

(p

q)

r,E=((

p

q)

r)

(

r

s)

分別為0層，1層，2層，3層，4層公式.17第1章命題邏輯的基本概念定義1.8

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

=

1

2…

n是指

p1=

1,p2=

2,…,pn=

n,

i=0或1,

i之間不加標(biāo)點(diǎn)符號(hào)

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

1

2

3…是指

p=

1,q=

2,r=

3…含n個(gè)命題變項(xiàng)的公式有2n個(gè)賦值.

如000,010,101,110是

(p

q)

r的成真賦值

001,011,100,111是成假賦值.公式賦值18第1章命題邏輯的基本概念定義1.9

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

(2)按從低到高的順序?qū)懗龉降母鱾€(gè)層次.(3)對每個(gè)賦值依次計(jì)算各層次的真值,直到最后計(jì)算出公式的真值為止.真值表19第1章命題邏輯的基本概念例6

寫出下列公式的真值表,并求它們的成真賦值和成假賦值:(1)(p

q)

r(2)(q

p)q

p(3)

(

p

q)q真值表20第1章命題邏輯的基本概念(1)A=(p

q)

r成真賦值:000,001,010,100,110;成假賦值:011,101,111

pqrp

q

r

(p

q)

r000001010011100101110111001111111010101011101010真值表121第1章命題邏輯的基本概念(2)B＝(q

p)q

p成真賦值:00,01,10,11;無成假賦值p

q

q

p(q

p)q(q

p)q

p00011011101100011111真值表222第1章命題邏輯的基本概念(3)C＝

(

p

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

q

p

p

q

(

p

q)

(

p

q)q000110111100110100100000真值表323第1章命題邏輯的基本概念公式的類型定義1.10

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

q)

r,(q

p)q

p,

(

p

q)q

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

求出公式的全部成真賦值與成假賦值,判斷公式的類型24第1章命題邏輯的基本概念第一章習(xí)題課主要內(nèi)容命題、真值、簡單命題與復(fù)合命題、命題符號(hào)化聯(lián)結(jié)詞

,

,

,

,

及復(fù)合命題符號(hào)化命題公式及層次公式的類型真值表及應(yīng)用基本要求深刻理解各聯(lián)結(jié)詞的邏輯關(guān)系,熟練地將命題符號(hào)化會(huì)求復(fù)合命題的真值深刻理解合式公式及重言式、矛盾式、可滿足式等概念熟練地求公式的真值表，并用它求公式的成真賦值與成假賦值及判斷公式類型25第1章命題邏輯的基本概念1.將下列命題符號(hào)化

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

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

(5)p

q,(6)

p

q或q

p(7)

q

p

或p

q,(8)q

p或

p

q(9)p

q

或

p

q可見(5)與(7)，(6)與(8)相同（等值）練習(xí)1解答27第1章命題邏輯的基本概念2.設(shè)p:2是素?cái)?shù)

q:北京比天津人口多

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

(1)(p

q)

r(2)(q

r)

(p

r)(3)(q

r)

(p

r)(4)(q

p)

((p

r)

(

r

q))0練習(xí)210028第1章命題邏輯的基本概念3.用真值表判斷下面公式的類型

(1)p

r

(q

p)