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

1、,制作時(shí)間：2008年2月最后修改：2011年3月,離散數(shù)學(xué),離散數(shù)學(xué),仝輝北京郵電大學(xué)理學(xué)院數(shù)學(xué)系Tel: 62281308 / 15311706220E-mail：tonghui@bupt.edu.cn learnmath@qq.com公用郵箱：learnmath@sina.com,聯(lián)系方式,課程安排,總學(xué)時(shí)：32課程類別：選修考核原則：以學(xué)有所得為目的，以掌握方法和思

2、 路為要求，摒棄死記硬背?？己朔绞剑洪]卷考試平時(shí)作業(yè)要認(rèn)真且誠(chéng)實(shí)地完成平時(shí)成績(jī)占一定的比重教材：《離散數(shù)學(xué)》，耿素云，屈婉玲，張立昂 清華大學(xué)出版社 （建議學(xué)時(shí)120）,希望,圓滿完成本課程的學(xué)習(xí)，需要我們共同努力。如果發(fā)現(xiàn)教材和講義中有錯(cuò)誤，請(qǐng)大家積極指出?？梢栽谡n間討論，或者發(fā)Email，或者以你喜歡的其他方式。,謝謝！,,命題邏輯,——理學(xué)院數(shù)學(xué)系仝 輝,

3、第一章 命題邏輯,命題符號(hào)化及聯(lián)結(jié)詞命題公式及分類等值演算聯(lián)結(jié)詞全功能集對(duì)偶與范式推理理論,什么是命題,數(shù)理邏輯研究的中心問(wèn)題是推理，而推理的前提和結(jié)論都是表達(dá)判斷的命題。命題：具有唯一真值的陳述句。真值：命題的判斷結(jié)果，也稱為值。真、假：命題真值的兩種可能。,判斷下面句子是否是命題,2是素?cái)?shù).雪是黑色的.2+3=5.明年十月一日是晴天.3能被2整除.這朵花多好看呀!明天下午有會(huì)嗎?請(qǐng)關(guān)上門(mén)!x+y&g

4、t;5.地球外的星球上也有人.,簡(jiǎn)單命題與復(fù)合命題,簡(jiǎn)單命題（原子命題）：命題不能分成更簡(jiǎn)單的句子的命題，又稱為命題常項(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ù)）：真值可以變化的陳述

5、句。如：x+y>5. 命題變項(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+y>5; --命題變項(xiàng)（不是命題）命題的真值表示：

6、1(T)表示真;0(F)表示假.,否定聯(lián)結(jié)詞,設(shè)p為任一命題,復(fù)合命題“非p”（或“p的否定”）稱作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”）稱作p與q的合取式，記作p ∧ q ， ∧為合取聯(lián)結(jié)詞。 p ∧ q為真當(dāng)且僅當(dāng)p與q同時(shí)為真。 合取聯(lián)結(jié)詞是邏輯“與”的意思。李平既聰明(p)又用功(q

7、):（p ∧ q）李平雖然聰明,但不用功:（p ∧ ┐ q）李平不但聰明(p),而且用功(q):（p ∧ q）李平不是不聰明(p),而是不用功(q):（ ┐ (┐ p) ∧ ┐ q）不能見(jiàn)到“和”、“與”就用“∧”李文和李武是兄弟： p,析取聯(lián)結(jié)詞,設(shè)p，q為兩個(gè)命題,復(fù)合命題“p或q” 稱作p與q的析取式，記作p ∨ q ， ∨為析取聯(lián)結(jié)詞。 p ∨ q為真當(dāng)且僅當(dāng)p與q中至少一個(gè)為真。 析取聯(lián)結(jié)詞是邏輯“或”的意思

8、。王燕學(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” 稱作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就q,只有q 才p.只要不下雨,我就

9、騎自行車上班: ┐p → q只有不下雨,我才騎自行車上班: q → ┐ p 若2+2=4,則太陽(yáng)就從東方升起:p → q,等價(jià)聯(lián)結(jié)詞,設(shè)p，q為兩個(gè)命題,復(fù)合命題“p當(dāng)且僅當(dāng)q” 稱作p與q的等價(jià)式，記作p ? q ， ?為等價(jià)聯(lián)結(jié)詞p ? q為真當(dāng)且僅當(dāng)p與q真值相同:P當(dāng)且僅當(dāng)q2+2=4當(dāng)且僅當(dāng)3是奇數(shù):p?q2+2=4當(dāng)且僅當(dāng)3不是奇數(shù):p? ┐ q2+2≠4當(dāng)且僅當(dāng)3是奇數(shù): ┐ p? q,習(xí)題,小王是游泳冠軍或百

10、米賽跑冠軍: p ∨ q小王現(xiàn)在在宿舍或在圖書(shū)館: (┐ p ∧ q) ∨ (p ∧ ┐q) 或 p ∨ q選小王或小李中的一人當(dāng)班長(zhǎng): (┐ p ∧ q) ∨ (p ∧ ┐q)如果我上街，我就去書(shū)店看看，除非我很累: ┐r →( p → q)王一樂(lè)是計(jì)算機(jī)系的學(xué)生，他生于1968年或1969年，他是三好學(xué)生:

11、 p ∧( q ∨r) ∧s,聯(lián)結(jié)詞運(yùn)算規(guī)則,我們所學(xué)的5種基本聯(lián)結(jié)詞也稱為邏輯運(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é)詞命題公式及分類等值演算聯(lián)結(jié)詞全功能集對(duì)偶與范式推理理論,第一章 命題邏輯,什么是命題公式或公式,命題公式是由命題常項(xiàng)

12、、命題變項(xiàng)、聯(lián)結(jié)詞、括號(hào)等組成的符號(hào)串.遞歸定義：?jiǎn)蝹€(gè)命題常項(xiàng)或變項(xiàng)p,q,r,...,pi,qi,ri,...,0,1是合式公式；如果Ａ是合式公式，則┐Ａ是合式公式；如果Ａ,B是合式公式，則(A ∧ B), (A ∨ B), (A → B), (A ? B)是合式公式；只有有限次地應(yīng)用(1)-(3)組成的符號(hào)串才是合式公式.合式公式稱為命題公式,簡(jiǎn)稱公式.,(p ∧q) ? r √,(┐p ∧q) ? r√,(┐p q)

13、 ? r ×,┐p ∨ →r ×,p ∧ ┐ q ?r √,p ┐ ∧ q ?r ×,命題公式的層次定義,若A是單個(gè)命題(常項(xiàng)或變項(xiàng))p,q,r,...,pi,qi,ri,...,0,1,則稱A為0層公式；稱A是n+1(n≥0)層公式是指A符合下列情況之一：A? ┐B，B是n層公式；A? B ∧ C，其中B，C分別為i層公式和j層公式,且n=max(i,j);A? B ∨ C，其中B，C分別為i

14、層公式和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);若Ａ的最高層次為Ｋ，則稱Ａ是K層公式.┐p ∨q : 2p ∧ q ∧ r : 2┐(┐p ∧ q) →(r ∨s) :┐(┐p)∧(q→(r ∨

15、s)) :,3,4,成真賦值,成假賦值,設(shè)A為一命題公式, p1,p2,...,pn為出現(xiàn)在Ａ中的所有的命題變項(xiàng)。給p1,p2,...,pn指定一組真值，稱為對(duì)Ａ的一個(gè)賦值或解釋．若指定的這一組真值使A的值為真，則稱這組值為A的成真賦值，若使A的值為假，則稱這組值為A的成假賦值。,A=( p∧q) →r,真值表,含n(n>1)個(gè)命題變項(xiàng)的命題公式,共有2n組賦值,將命題公式A在所有的賦值之下取值的情況列成表,稱為A的真值表.,

16、01234567,如計(jì)算 p ∧ (q ∨ ┐r ) 的真值表,真值表,p∧(q∨┐r) 有成真賦值，也有成假賦值（P7.表1-1)(p∧(p→q)) →q 全是成真賦值（P7.表1-2)┐(p→q) ∧q 全是成假賦值（P7.表1-3)重言式：A在它的各種賦值下取值均為真矛盾式：A在它的各種賦值下取值均為假可滿足式：A至少有一組賦值是成真賦值,重言式一定是可滿足式，但可滿

17、足式未必是重言式,命題符號(hào)化及聯(lián)結(jié)詞命題公式及分類等值演算聯(lián)結(jié)詞全功能集對(duì)偶與范式推理理論,第一章 命題邏輯,等值演算,設(shè)A,B是兩個(gè)命題,若等價(jià)式A?B是重言式,則A與B是等值的,記為AB。注意和“”、“=”的關(guān)系。A?B是重言式（說(shuō)明只出現(xiàn)A與B 的值同時(shí)為真或同時(shí)為假的兩種情況），所以肯定A B 。注意和“”、“?”的關(guān)系。如A B則A?B必是重言式。若A?B，未必A B因?yàn)锳?B有4種情況.,判斷下列命題公

18、式是否等值,┐(pVq)與 ┐pV ┐q┐(pVq)與 ┐p∧┐q,真值表法（1）,┐(pVq)與 ┐pV ┐q 不等值,真值表法（2）,┐(pVq)與┐p∧┐q 等值,等值式(1),等值式（2）,等值式（3）,等值演算,(置換定理)：設(shè)Φ(A)是含命題公式A的命題公式，Φ(B)是命題公式B置換了Φ(A)中A之后得到的命題公式。如果A?B，則Φ(A)?Φ(B)。例如：P∧┐(q∧r)?P∧(┐qV┐r)注意：(A?B)

19、→Φ(A)?Φ(B)，反之不然。 設(shè)：Φ(A)?A→B，Φ(B)?B→B?1 如果A?B，有Φ(A)?B→B，則Φ(A)?Φ(B) 但當(dāng)Φ(A)?Φ(B)?1時(shí)，A?0，能使Φ(A)?1， B?1，也能使Φ(B)?1，顯然此時(shí)A、B不等值。根據(jù)上述等值式，不用真值表法就可以推出更多的等值式，這個(gè)過(guò)程為等值演算。,習(xí)題,驗(yàn)證下列等值式: p→(q →r)?(p ∧q)→r（P10例1.9(1)),

20、p→(q→r) ? ┐p∨(q→r) ? ┐p∨(┐q∨r) ?(┐p∨┐q)∨r ?┐(p∧q)∨r ?(p∧q)→r,(p∧q)→r ? (q∧p) →r ? ┐(q∧p)∨r ?(┐q∨┐p)∨r ?┐q∨(┐p∨r) ?┐q∨(p→r) ?q→(p→r),習(xí)題,驗(yàn)證下列等式: p?(p ∧q)∨ (p ∧┐q) （P10例1.9

21、(2)) p?p∧1?p∧(q ∨ ┐q)?(p∧q)∨(p ∧┐q),講解P11.例11,p-A; q-B; r-C; s-D,命題符號(hào)化及聯(lián)結(jié)詞命題公式及分類等值演算聯(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è)成立”稱為p與q的排斥或或異或記作p∨q，∨稱作排斥或

22、或異或聯(lián)結(jié)詞。 p∨q為真當(dāng)且僅當(dāng)p，q中恰有一個(gè)為真。ｐＶｑ?(ｐ∧┐ｑ)Ｖ(┐ｐ∧ｑ)(ｐＶｑ)∧(ｐ?ｑ)?0(ｐＶｑ)Ｖ(ｐ?ｑ)?1,,,,與非聯(lián)結(jié)詞,設(shè)p,q兩個(gè)命題, 復(fù)合命題“p與q的否定”稱為p與q的與非式，記作p↑q，↑稱作與非聯(lián)結(jié)詞。 p↑q為真當(dāng)且僅當(dāng)p，q不同時(shí)為真。p↑q?┐(p ∧ q) (p↑q) ∧(p ∧ q)?0 (p↑q) ∨(p ∧ q)?1,或非聯(lián)結(jié)詞,設(shè)p,q兩個(gè)命

23、題, 復(fù)合命題“p或q的否定”稱為p與q的或非式，記作p↓q，↓稱作或非聯(lián)結(jié)詞。p↓q為真當(dāng)且僅當(dāng)p，q同時(shí)為假。p↓q?┐(p V q) (p↓q) ∧(p V q)?0 (p↓q) ∨(p V q)?1,n元真值函數(shù),一個(gè)n(n≥1)維卡氏積{0，1}n到{0，1}的函數(shù)稱為一個(gè)n元真值函數(shù)。設(shè)F是一個(gè)n元真值函數(shù)，則可記為F ：{0，1}n →{0，1}。 {0，1}{x | x(x-1)=0} n個(gè)命題變項(xiàng)

24、，共有2n個(gè)可能的賦值（橫行），有 個(gè)不同的真值函數(shù)（豎列）。其中，一個(gè)真值函數(shù)對(duì)應(yīng)著一個(gè)真值相同的命題公式，而這個(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é)詞表示，則稱此連接詞為冗余聯(lián)結(jié)詞，否則稱為獨(dú)

25、立聯(lián)結(jié)詞。現(xiàn)給定聯(lián)結(jié)詞{┐,∧,V,?,→}p→q? ┐pVq? ┐(p∧┐q)p?q?(p→q)∧(q→p)?(┐pVq)∧(┐qVp) ? ┐(p∧ ┐q)∧┐(q∧┐p)pVq? ┐┐(pVq)? ┐(┐p∧┐q)所以{v,?,→}為冗余聯(lián)結(jié)詞 {┐, ∧} 為獨(dú)立聯(lián)結(jié)詞,全功能集，極小功能集,若任一真值函數(shù)都可以用含某一聯(lián)結(jié)詞集中的聯(lián)結(jié)詞的命題公式表示，則稱該聯(lián)

26、結(jié)詞集為全功能集。若一聯(lián)結(jié)詞的全功能集中不含冗余的聯(lián)結(jié)詞，則稱它為極小全功能集。 {┐,∧,V,?,→}， { ┐, ∧,V,?,→，↓，↑}， { ┐,∧,V}，{┐，V}，{┐,∧}，{↑}，{↓} 為全功能集。{ ┐, V}， { ┐,∧}， { ↑}，{↓}為極小全功能集。,用{↓}表示下列命題公式：,極小功能集例題,1. p∧q?┐┐p∧┐┐q?┐(┐p∨┐q)?┐ ((p↓p)∨(q ↓q )

27、)? (p ↓p)↓(q ↓q),2. p∨q?┐┐(p∨q)?┐(p↓q)? (p↓q) ↓(p↓q),p→q?┐p∨q?(p↓p)∨q ? A∨q ?(A↓q)↓(A↓q)?((p↓p)↓q)↓((p↓p)↓q),(p↓p)A,第一章 命題邏輯,命題符號(hào)化及聯(lián)結(jié)詞命題公式及分類等值演算聯(lián)結(jié)詞全功能集對(duì)偶與范式推理理論,對(duì)偶式,在含有聯(lián)結(jié)詞┐,∧,V的命題公式A中,將V換成∧, ∧換成V,若A中含0或1, 將0

28、換成1，1換成0，所得到命題公式稱為A的對(duì)偶式，記作A*。p∧q 與 pVq是對(duì)偶式；┐(p∧q) 與┐(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

29、(p,q,r)?p∧(┐qVr) ┐A(p,q,r)? ┐(p∧(┐qVr))? ┐pV(q∧┐r) A*(p,q,r)?pV(┐q∧r) A*(┐p, ┐q, ┐r)? ┐pV(q∧┐r) ┐A*(p,q,r)? ┐(pV(┐q∧r))? ┐p∧(qV ┐r) A(┐p, ┐q, ┐r)? ┐p∧(qV ┐r),性質(zhì)2:對(duì)偶原理,設(shè)A,B為兩命題公式,若A?B,則A

30、*?B*,其中A*,B*分別為A,B的對(duì)偶式.（為了便于書(shū)寫(xiě)，本課件有時(shí)把“┐”寫(xiě)為“7”）例如: (p^q)V(7pV(7pVq))?7pVq(p^q)V(7pV(7pVq))?(p^q)v(7pvq) ?(pv(7pvq))^(qv(7pvq)) ?1^(7pvq)? 7pVq對(duì)偶式(pvq)^(7p^(7p^q))?7p^q (pvq)^(7p^(7p^q))?(pvq)^(7p^q)

31、 ?(p^(7p^q))v(q^(7p^q)) （兩個(gè)方法） ?0v(7p^q)?7p^q,簡(jiǎn)單析取式,簡(jiǎn)單合取式,僅有限個(gè)命題變項(xiàng)或其否定構(gòu)成的析取式稱為簡(jiǎn)單析取式,僅有限個(gè)命題變項(xiàng)或其否定構(gòu)成的合取式稱為簡(jiǎn)單合取式.簡(jiǎn)單析取式:pvq,7pvq,7pv7q簡(jiǎn)單合取式:p^q, 7p^q,7p^7q一個(gè)簡(jiǎn)單析取式為重言式,當(dāng)且僅當(dāng)同時(shí)含有一個(gè)命題變項(xiàng)及其否定.一個(gè)簡(jiǎn)單合取式為矛盾式,當(dāng)且僅當(dāng)同時(shí)含有一

32、個(gè)命題變項(xiàng)及其否定.,析取范式,合取范式,僅由有限個(gè)簡(jiǎn)單合取式構(gòu)成的析取式稱為析取范式.A?A1VA2VA3…..一個(gè)析取范式為矛盾式,當(dāng)且僅當(dāng)含有的每個(gè)簡(jiǎn)單合取式為假.僅由有限個(gè)簡(jiǎn)單析取式構(gòu)成的合取式稱為合取范式.A?A1∧A2∧A3…..一個(gè)合取范式為重言式,當(dāng)且僅當(dāng)含有的每個(gè)簡(jiǎn)單析取式為真.,范式存在定理,任一命題公式都存在與之等值的析取范式與合取范式，但不唯一.由于{7,∧,V}是全功能集,因而可以用這些聯(lián)結(jié)詞來(lái)代

33、替→,?,V,↑↓。(目的是變成合取或析取范式).p→q?7pvqp?q? (7pvq)^ (pv7q)……,,極小項(xiàng),在含有n個(gè)命題的簡(jiǎn)單合取式中,若每個(gè)命題變項(xiàng)與其否定不同時(shí)存在,而兩者之一必出現(xiàn)且僅出現(xiàn)一次,且第i個(gè)命題變項(xiàng)或其否定出現(xiàn)在從左起的第i位上(若命題變項(xiàng)無(wú)角標(biāo),則按字典順序排序),這樣的簡(jiǎn)單合取式稱為極小項(xiàng)。7p^7q^7r------- 000 -----0記為m0;7p^7q^r ------- 001

34、 -----1記為m1;7p^q^7r ------- 010 -----2記為m2;7p^q^r ------- 011 -----3記為m3;p^7q^7r ------- 100 -----4記為m4;p^7q^r ------- 101 -----5記為m5;p^q^7r ------- 110 -----6記為m6;p^q^r ------- 111 -----7記為m7;,主析取范

35、式,設(shè)命題公式A中含有n個(gè)命題變項(xiàng)，如果A的析取范式中的簡(jiǎn)單合取式全是極小項(xiàng)，則A稱為主析取范式。任何命題公式的主析取范式是存在的，且唯一。求解方式（P18）求A的析取范式對(duì)命題中不含某個(gè)變項(xiàng)的采用 B?B^1?(B^p)V(B^7p),命題公式A中含有n個(gè)命題變項(xiàng),如果A是重言式，當(dāng)且僅當(dāng)A的主析取范式中含全部的2n個(gè)極小項(xiàng)。命題公式A中含有n個(gè)命題變項(xiàng),如果A是矛盾式，當(dāng)且僅當(dāng)A的主析取范式中不含任何極小項(xiàng)。

36、命題公式A中含有n個(gè)命題變項(xiàng),如果A是可滿足式（協(xié)調(diào)式），則A的主析取范式中至少含一個(gè)極小項(xiàng)。,主析取范式,例題,求((pvq)→r) →p的主析取范式 ((pvq)→r) →p ?7((pvq)→r)vp ?7(7(pvq)vr)vp ?((pvq)^7r)vp?(p^7r)v(q^7r)vp ?(p^q^7r)v(p^7q^7r)v(p^q^7r)v(7p^q^7r) v(p^q^

37、r)v(p^7q^r)v(p^q^7r)v(p^7q^7r) ?(p^q^7r)v(p^7q^7r)v(7p^q^7r)v(p^q^r)v(p^7q^r) ?m6 v m4 v m2 vm7 vm5 ?∑(2,4,5,6,7),,,,,,極大項(xiàng),在含有n個(gè)命題的簡(jiǎn)單析取式中，若每個(gè)命題變項(xiàng)與其否定不同時(shí)存在，而兩者之一必出現(xiàn)且僅出現(xiàn)一次，且第i個(gè)命題變項(xiàng)或其否定出現(xiàn)在從左起的第i 位上(若命題變項(xiàng)無(wú)角標(biāo)，按字典順

38、序排序)，這樣的簡(jiǎn)單析取式稱為極大項(xiàng)。pVqVr-------000-----0記為M0;pVqV7r-----001-----1記為M1;pV7qVr-----010-----2記為M2;pV7qV7r---011-----3記為M3;7pVqVr-----100-----4記為M4;7pVqV7r---101-----5記為M5;7pV7qVr---110-----6記為M6;7pV7qV7r -111-----7記

39、為M7;,主合取范式,設(shè)命題公式A中含有n個(gè)命題變項(xiàng)，如果A的合取范式中的簡(jiǎn)單析取式全是極大項(xiàng)，則A稱為主合取范式。任何命題公式的主合取范式是存在的，且唯一。求解方式求A的合取范式對(duì)命題中不含某個(gè)變項(xiàng)的采用 B?BV0?(BVp)^(BV7p),命題公式A中含有n個(gè)命題變項(xiàng),如果A是重言式，當(dāng)且僅當(dāng)A的主合取范式中不含任何極大項(xiàng)。命題公式A中含有n個(gè)命題變項(xiàng),如果A是矛盾式，當(dāng)且僅當(dāng)A的主合取范式中含全部的2n個(gè)極

40、大項(xiàng)。命題公式A中含有n個(gè)命題變項(xiàng),如果A是可滿足式（協(xié)調(diào)式），則A的主合取范式中至多含2n-1個(gè)極大項(xiàng)。,主合取范式,例題,求(p^q)vr的主合取范式 (p^q)vr?(pvr)^(qvr) ?(pvqvr)^(pv7qvr)^(pvqvr)^(7pvqvr)?(pvqvr)^(pv7qvr)^(7pvqvr)?M0^M2^M4?∏(0,2,4),,,主析取范式與主合取范式的關(guān)系,存在7mi ? Mi關(guān)系（單個(gè)）.

41、所以 A?m0Vm1Vm5Vm7 ?∑(0,1,5,7) ?7M0V7M1V7M5V7M7 ?7(M0^M1^M5^M7) ?(M2^M3^M4^M6) ?∏(2,3,4,6),第一章 命題邏輯,命題符號(hào)化及聯(lián)結(jié)詞命題公式及分類等值演算聯(lián)結(jié)詞全功能集對(duì)偶與范式推理理論,什么是推

42、理,推理是從前提推出結(jié)論的思維過(guò)程,前提是已知的命題公式,結(jié)論是從前提出發(fā)應(yīng)用推理規(guī)則推出的命題公式.,邏輯結(jié)論,若(A1^A2^………^AK)→B為重言式,則稱A1^A2^………^AK推結(jié)論B的推理正確, B是A1^A2^………^AK的邏輯結(jié)論或有效結(jié)論, 稱(A1^A2^………^AK)→B為由前提A1^A2^………^AK推結(jié)論B的推理的形式結(jié)構(gòu).,與用“AB”表示“A?B”是重言式類似，用“A=>B”表示 “A→B”是重言式。

43、因而，若由前提“(A1^A2^………^AK)”推結(jié)論“B”的推理正確，也記為：,(A1^A2^………^AK) => B,判斷推理是否正確的方法就是重言蘊(yùn)涵式的方法。我們已學(xué)過(guò)三種方法：(1) 真值表法；(2) 等值演算；(3)主析取范式。,下面介紹第四種方法：構(gòu)造證明法,構(gòu)造證明法,例題(1),判斷下面各推理是否正確如果天氣涼快,小王就不去游泳.天氣涼快,所以小王沒(méi)去游泳. p:天氣涼快; q:小王去游泳 前提 p→

44、7q , p 結(jié)論 7q. 推理形式: ((p→7q)^p)→7q推理方法有三種: (1) 真值表法(2) 等值演算(3) 主析取范式,例題(2),等值演算((p→7q)^p)→7q ?((7pv7q)^p)→7q ?((p^7p)V(p^7q))→7q ?(p^7q)→7q ?7(p^7q)v7q ?7pvqv7q?1主析取范式((p→7q)^p)→7q?m0

45、vm1vm2vm3?∑(0,1,2,3),推理定律,推理規(guī)則,例題,構(gòu)造下列推理的證明前提: pvq,p->7r, s->t, 7s->r, 7t結(jié)論: q 證明:(1) s->t 拿出其中的一條前提,臨時(shí)結(jié)論為t(2) 7t 發(fā)現(xiàn)有前提是7t(3) 7s 得出7s結(jié)論(4) 7s->r(5) r(6) p->7r(7

46、) 7p(8) pVq(9) q,附加前提證明法,(A1^A2^……^AK)→(A→B) ?7(A1^A2^……^AK)V(7AVB) ? (7(A1^A2^……^AK) V7A)VB ?7 (A1^A2^……^AK^A)VB ? (A1^A2^……^AK^A)→B,令：(A1^A2^……^AK)?C 故 C→(A→B)?(C∧A)→B,原習(xí)題已經(jīng)做過(guò)[例1.9(1)],,,例題,用附加證明法

47、證明下面推理前提:p->(q->r),7svp,q結(jié)論:s->r 證明:(1) 7svp (2) s 附加前提 (3) p (4) p->(q->r) (5) q->r (6) q (7) r,歸繆法,A1^A2^┅

48、^AK是可滿足式,則稱A1,A2,┅,AK是相容的.否則 (A1^A2^ ┅ ^AK為矛盾式), 稱A1,A2, ┅ ,AK是不相容的.,(A1^A2^┅^AK-1)→AK?7(A1^A2^ ┅ ^7AK), 因此，若 A1,A2, ┅ ,7AK是不相容的，則說(shuō)明AK是公式A1,A2, ┅ ,AK－1的邏輯結(jié)論。這種將7AK作為附加前提推出矛盾的證明方法叫歸謬論。,令：A1^A2^┅^AK-1?B,因?yàn)锽→AK => B^7AK