離散數(shù)學(xué)—第一章命題邏輯

1、,制作時(shí)間：2008年2月 最后修改：2011年3月,離散數(shù)學(xué),離散數(shù)學(xué),仝輝 北京郵電大學(xué)理學(xué)院數(shù)學(xué)系 Tel: 62281308 /E-mail： 公用郵箱：,聯(lián)系方式,課程安排,總學(xué)時(shí)：32 課程類(lèi)別：選修 考核原則：以學(xué)有所得為目的，以掌握方法和思 路為要求，摒棄死記硬背。 考核方式：閉卷考試 平時(shí)作業(yè)要認(rèn)真且誠(chéng)實(shí)地完成 平時(shí)成績(jī)占一定的比重 教材：離散數(shù)學(xué)，耿素云，屈婉玲，張立昂 清華大學(xué)出版社 （建議學(xué)時(shí)120）,希望,圓滿(mǎn)完成本課程的學(xué)習(xí)，需要我們共同努力。 如果發(fā)現(xiàn)教材和講義中有錯(cuò)誤，請(qǐng)大家積極指出。 可以在課間討論，或者發(fā)Email，或者以你喜歡的其

2、他方式。,謝謝！,命題邏輯,理學(xué)院數(shù)學(xué)系 仝 輝,第一章 命題邏輯,命題符號(hào)化及聯(lián)結(jié)詞 命題公式及分類(lèi) 等值演算 聯(lián)結(jié)詞全功能集 對(duì)偶與范式 推理理論,什么是命題,數(shù)理邏輯研究的中心問(wèn)題是推理，而推理的前提和結(jié)論都是表達(dá)判斷的命題。 命題：具有唯一真值的陳述句。 真值：命題的判斷結(jié)果，也稱(chēng)為值。 真、假：命題真值的兩種可能。,判斷下面句子是否是命題,2是素?cái)?shù). 雪是黑色的. 2+3=5. 明年十月一日是晴天. 3能被2整除. 這朵花多好看呀! 明天下午有會(huì)嗎? 請(qǐng)關(guān)上門(mén)! x+y5. 地球外的星球上也有人.,簡(jiǎn)單命題與復(fù)合命題,簡(jiǎn)單命題（原子命題）：命題不能分成更簡(jiǎn)單的句子的命題，又稱(chēng)為命題常

3、項(xiàng)（命題常元）。 2是素?cái)?shù). 雪是黑色的. 2+3=5. 明年十月一日是晴天. 3能被2整除. 復(fù)合命題：由簡(jiǎn)單命題用聯(lián)結(jié)詞聯(lián)結(jié)而成的命題。 3不是偶數(shù); 2是素?cái)?shù)和偶數(shù); 林芳學(xué)過(guò)英語(yǔ)或日語(yǔ); 如果角A和角B是對(duì)頂角，則角A等于角B,命題變項(xiàng)（命題變?cè)⒚}函數(shù)）,命題變項(xiàng)（命題變?cè)?、命題函數(shù)）：真值可以變化的陳述句。 如：x+y5. 命題變項(xiàng)不是命題。 命題常項(xiàng)（命題常元）：真值唯一確定的陳述句。 如：2是偶數(shù). 命題常項(xiàng)是命題。,簡(jiǎn)單命題、命題變項(xiàng)的符號(hào)化,簡(jiǎn)單命題符號(hào)化： p: 2是素?cái)?shù); -命題常項(xiàng) q: 雪是白的; -命題常項(xiàng) 命題變項(xiàng)符號(hào)化： P: x+y5; -命題變項(xiàng)（不是命

4、題） 命題的真值表示： 1(T)表示真; 0(F)表示假.,否定聯(lián)結(jié)詞,設(shè)p為任一命題,復(fù)合命題“非p”（或“p的否定”）稱(chēng)作p的否定式，記作P， 為否定聯(lián)結(jié)詞。 p為真當(dāng)且僅當(dāng)p為假。 p ：3是偶數(shù)。 p ：3不是偶數(shù),合取聯(lián)結(jié)詞,設(shè)p，q為兩個(gè)命題,復(fù)合命題“p并且q”（或“p和q”）稱(chēng)作p與q的合取式，記作p q ， 為合取聯(lián)結(jié)詞。 p q為真當(dāng)且僅當(dāng)p與q同時(shí)為真。 合取聯(lián)結(jié)詞是邏輯“與”的意思。 李平既聰明(p)又用功(q):（p q） 李平雖然聰明,但不用功:（p q） 李平不但聰明(p),而且用功(q):（p q） 李平不是不聰明(p),而是不用功(q):（ ( p) q） 不

5、能見(jiàn)到“和”、“與”就用“” 李文和李武是兄弟： p,析取聯(lián)結(jié)詞,設(shè)p，q為兩個(gè)命題,復(fù)合命題“p或q” 稱(chēng)作p與q的析取式，記作p q ， 為析取聯(lián)結(jié)詞。 p q為真當(dāng)且僅當(dāng)p與q中至少一個(gè)為真。 析取聯(lián)結(jié)詞是邏輯“或”的意思。 王燕學(xué)過(guò)英語(yǔ)(p)或法語(yǔ)(q) p q “或”具有“相容性”和“相斥性”兩重意義。 派小王或小李中的一人去開(kāi)會(huì)： （p q） （ p q）,蘊(yùn)涵聯(lián)結(jié)詞,設(shè)p，q為兩個(gè)命題,復(fù)合命題“如果p，則q” 稱(chēng)作p與q的蘊(yùn)涵式，記作p q ，p為蘊(yùn)涵式的前件，q為蘊(yùn)涵式的后件， 為蘊(yùn)涵聯(lián)結(jié)詞。 p q為假當(dāng)且僅當(dāng)p為真q為假。 p是q的充分條件, q 是p的必要條件:只要p就

6、q,只有q 才p. 只要不下雨,我就騎自行車(chē)上班: p q 只有不下雨,我才騎自行車(chē)上班: q p 若2+2=4,則太陽(yáng)就從東方升起:p q,等價(jià)聯(lián)結(jié)詞,設(shè)p，q為兩個(gè)命題,復(fù)合命題“p當(dāng)且僅當(dāng)q” 稱(chēng)作p與q的等價(jià)式，記作p q ， 為等價(jià)聯(lián)結(jié)詞 p q為真當(dāng)且僅當(dāng)p與q真值相同:P當(dāng)且僅當(dāng)q 2+2=4當(dāng)且僅當(dāng)3是奇數(shù):pq 2+2=4當(dāng)且僅當(dāng)3不是奇數(shù):p q 2+24當(dāng)且僅當(dāng)3是奇數(shù): p q,習(xí)題,小王是游泳冠軍或百米賽跑冠軍: p q 小王現(xiàn)在在宿舍或在圖書(shū)館: ( p q) (p q) 或 p q 選小王或小李中的一人當(dāng)班長(zhǎng): ( p q) (p q) 如果我上街，我就去書(shū)店看看

7、，除非我很累: r ( p q) 王一樂(lè)是計(jì)算機(jī)系的學(xué)生，他生于1968年或1969年，他是三好學(xué)生: p ( q r) s,聯(lián)結(jié)詞運(yùn)算規(guī)則,我們所學(xué)的5種基本聯(lián)結(jié)詞也稱(chēng)為邏輯運(yùn)算符，其運(yùn)算順序?yàn)椋?，,如果出現(xiàn)的基本聯(lián)結(jié)詞相同，又無(wú)括號(hào)時(shí)，則按從左到右的運(yùn)算順序；,如果遇有括號(hào)時(shí)，不管出現(xiàn)的基本聯(lián)結(jié)詞如何，都先進(jìn)行括號(hào)中的運(yùn)算。,真值表,命題符號(hào)化及聯(lián)結(jié)詞 命題公式及分類(lèi) 等值演算 聯(lián)結(jié)詞全功能集 對(duì)偶與范式 推理理論,第一章 命題邏輯,什么是命題公式或公式,命題公式是由命題常項(xiàng)、命題變項(xiàng)、聯(lián)結(jié)詞、括號(hào)等組成的符號(hào)串. 遞歸定義： 單個(gè)命題常項(xiàng)或變項(xiàng)p,q,r,.,pi,qi,ri,.,0,

8、1是合式公式； 如果是合式公式，則是合式公式； 如果,B是合式公式，則(A B), (A B), (A B), (A B)是合式公式； 只有有限次地應(yīng)用(1)-(3)組成的符號(hào)串才是合式公式. 合式公式稱(chēng)為命題公式,簡(jiǎn)稱(chēng)公式.,(p q) r ,(p q) r,(p q) r ,p r ,p q r ,p q r ,命題公式的層次定義,若A是單個(gè)命題(常項(xiàng)或變項(xiàng))p,q,r,.,pi,qi,ri,.,0,1,則稱(chēng)A為0層公式； 稱(chēng)A是n+1(n0)層公式是指A符合下列情況之一： A B，B是n層公式； A B C，其中B，C分別為i層公式和j層公式,且n=max(i,j); A B C，其中B

9、，C分別為i層公式和j層公式,且n=max(i,j); A B C，其中B，C分別為i層公式和j層公式,且n=max(i,j); A B C，其中B，C分別為i層公式和j層公式,且n=max(i,j); 若的最高層次為，則稱(chēng)是K層公式. p q : 2 p q r : 2 (p q) (r s) : (p)(q(r s) :,3,4,成真賦值,成假賦值,設(shè)A為一命題公式, p1,p2,.,pn為出現(xiàn)在中的所有的命題變項(xiàng)。給p1,p2,.,pn指定一組真值，稱(chēng)為對(duì)的一個(gè)賦值或解釋若指定的這一組真值使A的值為真，則稱(chēng)這組值為A的成真賦值，若使A的值為假，則稱(chēng)這組值為A的成假賦值。,A=( pq)

10、r,真值表,含n(n1)個(gè)命題變項(xiàng)的命題公式,共有2n組賦值,將命題公式A在所有的賦值之下取值的情況列成表,稱(chēng)為A的真值表.,0 1 2 3 4 5 6 7,如計(jì)算 p (q r ) 的真值表,真值表,p(qr) 有成真賦值，也有成假賦值（P7.表1-1) (p(pq) q 全是成真賦值（P7.表1-2) (pq) q 全是成假賦值（P7.表1-3) 重言式：A在它的各種賦值下取值均為真 矛盾式：A在它的各種賦值下取值均為假 可滿(mǎn)足式：A至少有一組賦值是成真賦值,重言式一定是可滿(mǎn)足式，但可滿(mǎn)足式未必是重言式,命題符號(hào)化及聯(lián)結(jié)詞 命題公式及分類(lèi) 等值演算 聯(lián)結(jié)詞全功能集 對(duì)偶與范式 推理理論,第

11、一章 命題邏輯,等值演算,設(shè)A,B是兩個(gè)命題,若等價(jià)式AB是重言式,則A與B是等值的,記為AB。 注意和“”、“=”的關(guān)系。 AB是重言式（說(shuō)明只出現(xiàn)A與B 的值同時(shí)為真或同時(shí)為假的兩種情況），所以肯定A B 。 注意和“”、“”的關(guān)系。如A B則AB必是重言式。若AB，未必A B因?yàn)锳B有4種情況.,判斷下列命題公式是否等值,(pVq)與 pV q (pVq)與 pq,真值表法（1）,(pVq)與 pV q 不等值,真值表法（2）,(pVq)與pq 等值,等值式(1),等值式（2）,等值式（3）,等值演算,(置換定理)：設(shè)(A)是含命題公式A的命題公式，(B)是命題公式B置換了(A)中A之后

12、得到的命題公式。如果AB，則(A)(B)。 例如：P(qr)P(qVr) 注意：(AB)(A)(B)，反之不然。 設(shè)：(A)AB，(B)BB1 如果AB，有(A)BB，則(A)(B) 但當(dāng)(A)(B)1時(shí)，A0，能使(A)1， B1，也能使(B)1，顯然此時(shí)A、B不等值。 根據(jù)上述等值式，不用真值表法就可以推出更多的等值式，這個(gè)過(guò)程為等值演算。,習(xí)題,驗(yàn)證下列等值式: p(q r)(p q)r（P10例1.9(1),p(qr) p(qr) p(qr) (pq)r (pq)r (pq)r,(pq)r (qp) r (qp)r (qp)r q(pr) q(pr) q(pr),習(xí)題,驗(yàn)證下列等式:

13、p(p q) (p q) （P10例1.9(2) p p1 p(q q) (pq)(p q),講解P11.例11,p-A; q-B; r-C; s-D,命題符號(hào)化及聯(lián)結(jié)詞 命題公式及分類(lèi) 等值演算 聯(lián)結(jié)詞全功能集 對(duì)偶與范式 推理理論,第一章 命題邏輯,聯(lián)結(jié)詞的擴(kuò)展,異或聯(lián)結(jié)詞 與非聯(lián)結(jié)詞 或非聯(lián)結(jié)詞,異或聯(lián)結(jié)詞,設(shè)p,q為兩個(gè)命題, 復(fù)合命題“p，q中恰有一個(gè)成立”稱(chēng)為p與q的排斥或或異或記作pq，稱(chēng)作排斥或或異或聯(lián)結(jié)詞。 pq為真當(dāng)且僅當(dāng)p，q中恰有一個(gè)為真。 ()() ()()0 ()()1,與非聯(lián)結(jié)詞,設(shè)p,q兩個(gè)命題, 復(fù)合命題“p與q的否定”稱(chēng)為p與q的與非式，記作pq，稱(chēng)作與非聯(lián)

14、結(jié)詞。 pq為真當(dāng)且僅當(dāng)p，q不同時(shí)為真。 pq(p q) (pq) (p q)0 (pq) (p q)1,或非聯(lián)結(jié)詞,設(shè)p,q兩個(gè)命題, 復(fù)合命題“p或q的否定”稱(chēng)為p與q的或非式，記作pq，稱(chēng)作或非聯(lián)結(jié)詞。pq為真當(dāng)且僅當(dāng)p，q同時(shí)為假。 pq(p V q) (pq) (p V q)0 (pq) (p V q)1,n元真值函數(shù),一個(gè)n(n1)維卡氏積0，1n到0，1的函數(shù)稱(chēng)為一個(gè)n元真值函數(shù)。設(shè)F是一個(gè)n元真值函數(shù)，則可記為F ：0，1n 0，1。 0，1x | x(x-1)=0 n個(gè)命題變項(xiàng)，共有2n個(gè)可能的賦值（橫行），有 個(gè)不同的真值函數(shù)（豎列）。其中，一個(gè)真值函數(shù)對(duì)應(yīng)著一個(gè)真值相同

15、的命題公式，而這個(gè)命題公式又和許多命題公式彼此間是等值的。即: n個(gè)命題變項(xiàng)，必有且僅有 個(gè)不同真值的命題公式，其余的命題公式必然與這 個(gè)命題公式中的一個(gè)是等值的。,冗余聯(lián)結(jié)詞、獨(dú)立聯(lián)結(jié)詞,在一個(gè)聯(lián)結(jié)詞的集合中，如果一個(gè)聯(lián)結(jié)詞可由集合中的其他聯(lián)結(jié)詞表示，則稱(chēng)此連接詞為冗余聯(lián)結(jié)詞，否則稱(chēng)為獨(dú)立聯(lián)結(jié)詞。 現(xiàn)給定聯(lián)結(jié)詞,V, pq pVq (pq) pq(pq)(qp)(pVq)(qVp) (p q)(qp) pVq (pVq) (pq) 所以v,為冗余聯(lián)結(jié)詞 , 為獨(dú)立聯(lián)結(jié)詞,全功能集，極小功能集,若任一真值函數(shù)都可以用含某一聯(lián)結(jié)詞集中的聯(lián)結(jié)詞的命題公式表示，則稱(chēng)該聯(lián)結(jié)詞集為全功能集。若一聯(lián)結(jié)詞的

16、全功能集中不含冗余的聯(lián)結(jié)詞，則稱(chēng)它為極小全功能集。 ,V,， , ,V,， ,V，V，,， 為全功能集。 , V， ,， ，為極小全功能集。,用表示下列命題公式：,極小功能集例題,1. pq pq (pq) (pp)(q q ) (p p)(q q),2. pq (pq) (pq) (pq) (pq),pqpq (pp)q Aq (Aq)(Aq) (pp)q)(pp)q),(pp)A,第一章 命題邏輯,命題符號(hào)化及聯(lián)結(jié)詞 命題公式及分類(lèi) 等值演算 聯(lián)結(jié)詞全功能集 對(duì)偶與范式 推理理論,對(duì)偶式,在含有聯(lián)結(jié)詞,V的命題公式A中,將V換成, 換成V,若A中含0或1, 將0換成1，1換成0，所得到命題

17、公式稱(chēng)為A的對(duì)偶式，記作A*。 pq 與 pVq是對(duì)偶式； (pq) 與(pVq)是對(duì)偶式。,性質(zhì)1,設(shè)A和A*互為對(duì)偶式,p1, p2,.,pn是出現(xiàn)在A和A*中的全部的命題變項(xiàng),若將A和A*寫(xiě)成n元函數(shù)形式,則(1) A(p1, p2,.,pn)A*(p1, p2,., pn);(2) A(p1, p2,., pn) A*(p1, p2,.,pn). 例如:A(p,q,r)p(qVr) A(p,q,r) (p(qVr) pV(qr) A*(p,q,r)pV(qr) A*(p, q, r) pV(qr) A*(p,q,r) (pV(qr) p(qV r) A(p, q, r) p(qV r)

18、,性質(zhì)2:對(duì)偶原理,設(shè)A,B為兩命題公式,若AB,則A*B*,其中A*,B*分別為A,B的對(duì)偶式. （為了便于書(shū)寫(xiě)，本課件有時(shí)把“”寫(xiě)為“7”） 例如: (pq)V(7pV(7pVq)7pVq (pq)V(7pV(7pVq)(pq)v(7pvq) (pv(7pvq)(qv(7pvq) 1(7pvq) 7pVq 對(duì)偶式(pvq)(7p(7pq)7pq (pvq)(7p(7pq)(pvq)(7pq) (p(7pq)v(q(7pq) （兩個(gè)方法） 0v(7pq)7pq,簡(jiǎn)單析取式,簡(jiǎn)單合取式,僅有限個(gè)命題變項(xiàng)或其否定構(gòu)成的析取式稱(chēng)為簡(jiǎn)單析取式,僅有限個(gè)命題變項(xiàng)或其否定構(gòu)成的合取式稱(chēng)為簡(jiǎn)單合取式. 簡(jiǎn)單析取式:pvq,7pvq,7pv7q 簡(jiǎn)單合取式:pq, 7pq,7p7q 一個(gè)簡(jiǎn)單析取式為重言式,當(dāng)且僅當(dāng)同時(shí)含有一個(gè)命題變項(xiàng)及其否定. 一個(gè)簡(jiǎn)單合取式為矛盾式,當(dāng)且僅當(dāng)同時(shí)含有一個(gè)命題變項(xiàng)及其否定.,析取范式,合取范式,僅由有限個(gè)簡(jiǎn)單合取式構(gòu)成的析取式稱(chēng)為析取范式. AA1VA2VA3. 一個(gè)析取范式為矛盾式,當(dāng)且僅當(dāng)含有的每個(gè)