離散數(shù)學(xué)單元1

1、1,離數(shù)數(shù)學(xué),主講者:吝維軍、趙俊,2,緒言,一、離散數(shù)學(xué)研究離散量的結(jié)構(gòu)和相互間的關(guān)系整數(shù): ...,-3,-2,-1,0,1,2,3,...序群現(xiàn)實(shí)問題能否從河的兩岸或兩個(gè)小島中的任何一處出發(fā),經(jīng)過每座橋一次且僅僅一次,再返回到出發(fā)點(diǎn)?從任一點(diǎn)出發(fā),經(jīng)過每條邊一次且僅次,回到起點(diǎn)?二、離散數(shù)學(xué)是現(xiàn)代數(shù)學(xué)的一個(gè)分支（形成于70年代）數(shù)理邏輯、集合論、代數(shù)系統(tǒng)、圖論三、離散數(shù)學(xué)與計(jì)算機(jī)科學(xué)的關(guān)系離散數(shù)學(xué)是計(jì)算機(jī)

2、科學(xué)與技術(shù)的理論基礎(chǔ)，是計(jì)算機(jī)科學(xué)與技術(shù)的核心骨干課程它給數(shù)據(jù)結(jié)構(gòu)、編譯系統(tǒng)、操作系統(tǒng)、數(shù)據(jù)庫原理、人工智能提供必要的數(shù)學(xué)基礎(chǔ)。形式化、符號化的方法，培養(yǎng)和提高了學(xué)生的抽象思維能力、邏輯推理能力。,3,緒言,四、離散數(shù)學(xué)學(xué)習(xí)要點(diǎn)描述問題的方式：公式(符號)和圖公式：用符號描述對象或?qū)ο箝g的關(guān)聯(lián)或概念特點(diǎn)：嚴(yán)密、抽象、一般圖：用點(diǎn)和線描述對象或?qū)ο箝g的關(guān)聯(lián)或概念特點(diǎn)：直觀、具體重要性有趣性五、參考書目《離散數(shù)學(xué)》，王

3、遇科，北京理工大學(xué)《離散數(shù)學(xué)》，李盤林等，高等教育出版社《離散數(shù)學(xué)及其在計(jì)算機(jī)中的應(yīng)用》，徐潔磐，人民郵電出版社,4,第一篇 數(shù)理邏輯,一、邏輯學(xué)研究人的思維形式和規(guī)律的科學(xué)形式邏輯_代表人：Hilbert辯證邏輯_代表人物：羅素?cái)?shù)理邏輯二、數(shù)理邏輯形成于17世紀(jì)中葉代表人物：萊布尼茲、布爾、哥德爾、德.摩根研究推理：用數(shù)學(xué)方法（形式化、公理化）研究前提和結(jié)論之間的形式關(guān)系。特別是數(shù)學(xué)中的推理的科學(xué)。各門學(xué)科中都

4、要進(jìn)行推理，從具體的前提出發(fā)，得出具體的結(jié)論。例（1）函數(shù)f(x)在閉區(qū)間[a,b]上連續(xù)（2）f(a).f(b)<0（3）存在c∈(a,b)使f(c)=0.又如：（1）a=0或a<0（2）a不等于0（3）a<0數(shù)理邏輯研究的推理的特點(diǎn)：不注重內(nèi)容，注重形式關(guān)系 (1）A ∨ B（2）?A（3）B,5,,三、數(shù)理邏輯的內(nèi)容集合論模型論遞歸論證明論共同的邏輯基礎(chǔ)：邏輯演算（命題邏輯和

5、謂詞邏輯） —也是本課程學(xué)習(xí)的內(nèi)容四、學(xué)習(xí)的要點(diǎn)掌握使用符號形式地刻劃概念、推理和思維的基本思想和方法掌握形式的描繪和直觀念義之間的關(guān)系形意相通,6,第一章 命題邏輯,1-1 命題及其表示數(shù)理邏輯研究的中心問題是推理推理的前題和結(jié)論都是表達(dá)判斷的陳述句。表達(dá)判斷的陳述句構(gòu)成了推理的基本單位稱能判斷真假的陳述句為命題注：真值，命題的值判斷為正確的命題的真值為真

6、，用T表示判斷為錯誤的命題的真值為假，用F表示,7,例1:判斷下列句子哪些是命題？,請止步!你聽懂了嗎？我是學(xué)生．６不是自然數(shù)．張校長的頭發(fā)有一萬根．我所說的是假的．如果天氣好，那么我去散步．哥德巴赫猜想是正確的．,不是命題不是命題是命題是命題，假命題是命題不是命題，是悖論是命題是命題,8,幾個(gè)概念,命題的種類原子命題（簡單命題）、復(fù)合命題命題的表示大寫英文字母：A、B、C、…P、Q、…帶下標(biāo)的大寫

7、英文字母： P1、Q1、…數(shù)字加方括號：[1]、[2]、……命題標(biāo)識符：表示命題的符號命題常量：T、F命題變元、原子變元,9,1-2 聯(lián)結(jié)詞,否定聯(lián)結(jié)詞? ?P讀作:非Ｐ?P的真值為T當(dāng)且僅當(dāng)P為F合取聯(lián)結(jié)詞∧ P∧Q讀作:Ｐ與Ｑ、P合取Q P∧Q為T當(dāng)且僅當(dāng)P和Q均為T析取聯(lián)結(jié)詞∨P∨Q讀作: P或Q、要么P要么QP∨Q為F當(dāng)且僅當(dāng)P和Q均為F,條件聯(lián)結(jié)詞（蘊(yùn)涵聯(lián)結(jié)詞）

8、 →P→Q讀作:如果P那么QP→Q為F當(dāng)且僅當(dāng)P為T，Q為F雙條件聯(lián)結(jié)詞（等值聯(lián)結(jié)詞） ?P?Q讀作: P當(dāng)且僅當(dāng)QP?Q為T當(dāng)且僅當(dāng)P和Q的真值相同,聯(lián)結(jié)詞是邏輯聯(lián)結(jié)詞或命題聯(lián)結(jié)詞的抽象是自然語言中連詞的抽象,10,五種聯(lián)結(jié)詞的定義,P,?P,,T,F,F,T,P,Q,P∧Q,T,T,T,F,F,T,F,F,T,F,F,F,P,Q,P∨Q,T,T,T,F,P,Q,P→Q,T,F,T,T,P,Q,P ? Q,

9、T,F,F,T,11,注,析取聯(lián)結(jié)詞是“或”的抽象可兼或：a.b=0即a=0或b=0或a=b=0 (至少有一發(fā)生)排斥或：他的死或重于泰山或輕于鴻毛．表示近似的或:去文昌樓需6分鐘或8分鐘．條件聯(lián)結(jié)詞P→Q,P稱為前件,Q稱為后件當(dāng)前件為F時(shí),P→Q為T復(fù)合命題的真值只取決于構(gòu)成它們的各原子命題的真值，而與其內(nèi)容、含義無關(guān)聯(lián)結(jié)詞有操作或運(yùn)算的含義可看作一元運(yùn)算符、二元運(yùn)算符，……,12,例2：將下列命題符號化,(1)他

10、既聰明又用功。(2)他雖聰明但不用功。(3)如果2+2=4,太陽將從東方升起．(4)除非你努力，否則你將失敗。(5)除非天氣好，我才騎自行車上班。(6)張明正在睡覺或游泳。(7)A中沒元素，A就是空集。,解：(1) P：他聰明。 Q：他用功。則(1)可表示為：P∧Q(2)可表示為：P∧?Q(3) P： 2+2=4。 Q：太陽將從東方升起。(3)可表示為: P→Q(4) P:你努力. Q:你將失敗.則(4

11、)可表示為：?P→Q(5) P:我騎自行車上班。Q:天氣好。則(5)可表示為P→Q　或?Q→?P(6) P:張明在睡覺.Q:張明在游泳.則(6)可表示為(P∧?Q)∨(?P∧Q)(7) P: A中沒元素.Q: A是空集.則(7)可表示為：P?Q,13,1-3命題公式與翻譯,定義1-3.1命題演算的合式公式（wff）:(1)單個(gè)命題變元是合式公式.(2)如果A是合式公式,則(?A)是合式公式.(3)如果A和B是合式

12、公式,則(A∧B),(A∨B),(A→B),(A?B)是合式公式.(4)有限次地使用(1),(2),(3)所得到的結(jié)果是合式公式.注:(1) 定義是以遞歸形式給出的(2) 合式公式有無窮多個(gè)(3) 合式公式?jīng)]有真值,只有對其命題變元指派真值后,方有真值.,14,,約定:(1) 公式最外層的括號可省略(2) 聯(lián)結(jié)詞運(yùn)算的優(yōu)先次序:?,∧,∨,→, ?(3) 結(jié)合性 ?右結(jié)合 ∧,∨,→, ?左結(jié)合,15,命題翻譯

13、,文字?jǐn)⑹龅拿} 由命題標(biāo)識符,聯(lián)結(jié)詞,括號所組成的合式公式.步驟:(1)分析出各原子命題,并用符號表示(2)使用合適的聯(lián)結(jié)詞,將原子命題聯(lián)結(jié)起來,并加適當(dāng)?shù)睦ㄌ?來組成復(fù)合命題的符號化表示.,,16,例3: 將下列命題符號化,(1)如果我上街,我就去書店看看,除非我很累.P:我上街. Q: 我去書店. R:我很累.(1)可符號化為: ?R→ (P→Q)(2)王一樂是數(shù)學(xué)系的學(xué)生,他生于1968

14、年或1969年,他是三好學(xué)生.P:王一樂是數(shù)學(xué)系的學(xué)生.Q:他生于1968年.R:他生于1969年.S:他是三好學(xué)生.(2)可符號化為: P∧(Q∨R)∧S,17,1-4,5 真值表 等價(jià)公式 重言式 蘊(yùn)涵公式,1.真值表定義1-4.1 在命題公式中,對于分量指派真值的各種可能組合,就確定了這個(gè)命題公式的各種真值情況,把它匯成表,就是命題公式的真值表.,18,例4:給出下列公式的真

15、值表,(1) (P∧Q)∧?P,P,Q,P∧Q,(P∧Q)∧?P,F,F,F,F,P,Q,P∧Q,?P∧?Q,(2),(2) (P∧Q)∨(?P∧?Q),解: (1)的真值表如下:,解: (2)的真值表如下:,19,(3) ?(P∧Q) ?(?P∨?Q),P,Q,?(P∧Q),?P∧?Q,? (P∧Q) ?(?P∨?Q),注:10:有一類公式無論命題變元作何種指派,其真值為永真(永假)20:含n個(gè)命題變元的命題公式，其真值表有2n

16、行,20,2.重言式　矛盾式,定義1-5.1 給定一命題公式,若無論對分量作怎樣的指派,其對應(yīng)的真值永為T,則稱該命題公式為重言式或永真公式.定義1-5.2 給定一命題公式,若無論對分量作怎樣的指派,其對應(yīng)的真值永為F,則稱該命題公式為矛盾式或永假公式.定理1-5.1 任何兩個(gè)重言式的合取或析取,仍是重言式.,21,3. 等價(jià)公式,定義1-4.2 設(shè)A和B是兩個(gè)命題公式,若A?B是重言式,則稱A和B是等價(jià)的或邏輯相等.記作

17、A?B.例5 證明: (1) P→Q??P∨Q(2) P?Q? (P→Q)∧(Q→P),注:A?B 即對A和B的任一真值指派,有A和B的真值相同.在邏輯相等意義下,含n 個(gè)原子變元的公式的個(gè)數(shù)為?與?的區(qū)別?是邏輯符號?是語義符號基本特性A?A若A?B則B?A若A?B且B?C則A?C,22,,??P ? P,P∨P ? P, P∧P ? P,(P∨Q)∨R ? P∨(Q∨R)(P∧Q)∧R ? P∧(Q∧R)

18、,P∨Q ? Q∨P, P∧Q ? Q∧P,P∨(Q∧R) ?(P∨Q)∧(P∨R)P∧(Q∨R) ?(P∧Q)∨(P∧R),P∨(P∧Q) ?,P∨F ?,P∨T ?,P∨┐P ? T, P∧┐P ? F,常用的命題定律,P∧(P∨Q) ?,P,P,P,P,P∧T ?,F,T,P∧F ?,23,4.蘊(yùn)涵公式(邏輯蘊(yùn)涵),定義1-5.3 設(shè)A,B是公式,若A→B是重言式,則稱A蘊(yùn)涵B,記作A?B.定理 1-5.4 設(shè)A

19、,B是命題公式.A?B的充要條件是A?B且B?A.證明:利用A ? B? (A→B)∧(B→A)來證.,24,注:,→與?的區(qū)別.幾個(gè)類似的公式P→Q, Q→P, ?P→?Q, ?Q→?P稱為 逆換式 反換式 逆反式有P→Q??Q→?PP?Q的證明方法真值表假設(shè)前件真,推出后件真假設(shè)后件假,推出前件假?的特性若A?B且A為重言式,則B為

20、重言式.A?B,B?C則A?CA?B,A?C則A?B∧CA?B,C?B則A∨C?B,25,,P∧Q?P, P∧Q?Q,P?P∨Q,?P?P→Q,Q?P→Q,?(P→Q) ?P,?(P→Q) ??Q,P∧(P→Q) ?,?Q∧(P→Q) ?,?P∧(P∨Q) ?,(P→Q)∧(Q→R) ?,(P∨Q)∧(P→R)∧(Q→R) ?,(P→Q)∧(R→S) ?(P∧R)→(Q∧S),(P ? Q)∧(Q ? R) ?(P ? R),常用

21、的蘊(yùn)涵式,Q,?P,Q,(P→R),R,26,例5 推證?Q∧(P→Q) ??P,證明:法一:設(shè)?Q∧(P→Q)為T,則?Q為T從而Q為F由(P→Q)為T及Q為F可知P為F故?P為T.,法二:設(shè)?P為F,則P為T.若Q為F,則(P→Q)為F 從而?Q∧(P→Q)為F.若Q為T,則?Q為F, 從而?Q∧(P→Q)為F.綜上有?Q∧(P→Q) ??P法三:列真值表,27,5.替換規(guī)則 代入規(guī)則,替換

22、(置換)規(guī)則定義1-4.3 若X是合式公式A的一部分且為合式公式,則稱X為A的子公式.定理1-4.1 設(shè)X是合式公式A的子公式,Y是一公式.若X?Y,如果將A中的X用Y來置換所得公式B,則A ? B.注滿足定理1-4.1的置換稱為等價(jià)轉(zhuǎn)換或等價(jià)代換.替換規(guī)則又提供了一種證明公式等價(jià)的方法.,28,例7 證明: Q→(P∨(P∧Q)) ? Q→P證明: 因?yàn)镻∨(P∧Q) ? P, (吸收律)故有 Q→(P∨(P∧Q)

23、) ? Q→P (替換規(guī)則),例8 證明: (P∧Q)∨(P∧┐Q) ? P證明: (P∧Q)∨(P∧┐Q) ? P∧(Q∨┐Q) (分配律) ? P∧T (否定律,替換規(guī)則) ? P (同一律),29,例9 證明 P→(Q→R) ? Q→(P→R) ? ?R→(Q→?P)證明: P→(Q→R)?P→(?

24、Q∨R) ? ?P∨(?Q∨R) ? ?Q∨(?P∨R) ? ?Q∨(P→R) ? Q→(P→R),核心: P→Q ? ?P∨Q,?R→(Q→?P) ? ??R∨(?Q∨?P) ? R∨(?Q∨?P) ? ?P∨(?Q∨R) ? P→(Q→R),30,例10 證明 ((P∨Q)∧? (?P∧(?Q∨?R)))∨(?P∧?Q)∨(?P∧?R) ?T證明: ((P∨Q)∧? (?P∧(?Q∨?R)))∨(?P∧?Q)∨

25、(?P∧?R) ? ((P∨Q)∧(P∨(Q∧R)))∨(?P∧?Q)∨(?P∧?R) (德.摩根律) ? ((P∨Q)∧((P∨Q)∧(P∨R)))∨(?P∧?Q)∨(?P∧?R) (分配律)? ((P∨Q)∧(P∨R))∨(?P∧?Q)∨(?P∧?R) (結(jié)合律, 冪等律)? ((P∨Q)∧(P∨R))∨? (P∨Q)∨? (P∨R) (德.摩根律)((P∨Q)∧(P∨R))∨? ((

26、P∨Q)∧(P∨R)) (德.摩根律) ?T (否定律),31,代入規(guī)則,定理1-5.2(代入規(guī)則) 一個(gè)重言式,對同一分量全部用同一合式公式代換所得結(jié)果為重言式.注:全部代又提供了判定重言式的方法例:已知P→P為重言式,則有下列重言式:(P→Q)→(P→Q)(P∨Q→R)→(P∨Q→R)A→A,32,1-6 其它聯(lián)結(jié)詞,聯(lián)結(jié)詞 符號 復(fù)合

27、命題 含義,不可兼析取,條件否定,與非,合非,或非,謝孚豎,33,與非的特性,合非的特性,(1),(2),(3),(1),(2),(3),34,2.最小聯(lián)結(jié)詞組(聯(lián)結(jié)詞的完全集),T F P Q ?P ?Q,問:在邏輯相等意義下,兩個(gè)命題變元P和Q可構(gòu)成的不同的命題公式有多少個(gè)?,由T,F,P,Q及9個(gè)命題聯(lián)結(jié)詞可以表示16個(gè)命題公式. 但有幾個(gè)就夠了?,35,(2),(3),(4),結(jié)論: {?

28、,∨}, {?,∧},{?,→}是最小聯(lián)結(jié)詞組 {↑},{↓}也是最小聯(lián)結(jié)詞組 {?},{∧},{∨},{∧,V}均不是最小聯(lián)結(jié)詞組,36,1-7對偶和范式,1.對偶定義1-7.1 在給定的僅用聯(lián)結(jié)詞?,∧和∨的命題公式A中,若把∧和∨互換,F和T互換,所得公式A*稱為A的對偶式.例1:寫出下列公式的對偶式.(1) (P∨Q)∧R(2) (P∧Q)∨T(3) ?(P∨Q)∧(P∨? (Q∧?S))例2:求P↑Q,

29、P↓Q的對偶式.P↑Q的對偶式為P↓Q P↓Q的對偶式為P↑Q,37,定理1-7.1 若A和A*是對偶式,P1,P2,…,Pn是出現(xiàn)在A和A*中的原子變元, 則?A(P1,P2,…,Pn) ?A*(?P1, ?P2,…, ?Pn)A(?P1, ?P2,…, ?Pn) ??A*(P1,P2,…,Pn)注:德.摩根律的推廣?(P1∧P2∧…∧Pn) ??P1∨?P2∨…∨?Pn設(shè)A1,A2,…,An是任意命題變元,則?(

30、A1∧A2∧…∧An) ??A1∨?A2∨…∨?An例3. 設(shè)A*(S,W,R)是?S∧(?W∨R),驗(yàn)證: A*(?S, ?W, ?R) ??A(S,W,R)例4. 如果A(P,Q,R)是P↑(Q∧?(R↓P)),求它的對偶式A*(P,Q,R),分別求與A及A*等價(jià),但僅包含聯(lián)結(jié)詞∧,∨和?的公式.,38,定理1-7.2 設(shè)P1,P2,…,Pn是出現(xiàn)在公式A和B中的所有原子變元,如果A?B,則A*?B*.證明:由于

31、A?B,則A(P1,P2,…,Pn) ? B(P1,P2,…,Pn)是重言式,故A(?P1, ?P2,…, ?Pn) ? B(?P1, ?P2,…, ?Pn)是重言式.即A(?P1, ?P2,…, ?Pn) ? B(?P1, ?P2,…, ?Pn)由定理1-7.1A(?P1, ?P2,…, ?Pn) ? ?A*(P1,P2,…,Pn)B(?P1, ?P2,…, ?Pn) ? ?B*(P1,P2,…,Pn)故A*?B*,39

32、,2.范式-公式的標(biāo)準(zhǔn)型,(1)析取范式,合取范式定義 1-7.2 　一個(gè)命題公式稱為合取范式,當(dāng)且僅當(dāng)它具有型式: A1∧A2∧…∧An 　 (n≥1)其中A1，A2，…，An都是由命題變元或其否定所組成的析取式．定義 1-7.3 　一個(gè)命題公式稱為析取范式,當(dāng)且僅當(dāng)它具有型式: A1∨A2∨…∨An 　 (n≥1)其中A1，A2，…，An都是由命題變元或其否定

33、所組成的合取式．,40,例5. 求(P∧(Q→R))→S的合取范式.解: (P∧(Q→R))→S?(P∧(?Q∨R))→S??(P∧(?Q∨R))∨S??P∨ (Q∧ ? R)∨S?(?P∨S)∨(Q∧?R)?(?P∨S∨Q)∧(?P∨S∨?R),,41,例6.求?(P∨Q) ?(P∧Q)的析取范式.解: ?(P∨Q) ?(P∧Q)?(?(P∨Q) →(P∧Q))∧((P∧Q)→ ?(P∨Q))?(??(P∨Q) ∨(

34、P∧Q))∧(?(P∧Q)∨ ?(P∨Q))?((P∨Q) ∨(P∧Q))∧(?P∨?Q)∨ (?P∧?Q))?(P∨Q) ∧(?P∨?Q)?((P∨Q) ∧?P)∨((P∨Q)∧?Q))?(P∧?P)∨(Q∧?P)∨(P∧?Q)∨(Q∧?Q)?(Q∧?P)∨(P∧?Q),42,(2) 主析取范式,定義1-7.4n個(gè)命題變元的合取式,稱作布爾合取式或小項(xiàng),其中每個(gè)變元與它的否定出現(xiàn)且僅出現(xiàn)一個(gè).注:三個(gè)命題變元P,Q,

35、R其小項(xiàng):P∧Q∧R, P∧Q∧?R, P∧?Q∧R, P∧?Q∧?R,?P∧Q∧R, ?P∧Q∧?R, ?P∧?Q∧R, ?P∧?Q∧?Rn個(gè)命題變元的小項(xiàng)共有2n個(gè)一小項(xiàng)僅對應(yīng)一組真值指派使其真值為真.任兩個(gè)小項(xiàng)均不等價(jià),且其合取為假.全體小項(xiàng)的析取永為真.,43,小項(xiàng)的編碼表示,命題變元P,Q,R的小項(xiàng)m000= ?P∧?Q∧?R, m001= ?P∧?Q∧Rm010 = ?P∧Q∧?R,

36、m011 =?P∧Q∧R m100 = P∧?Q∧?R, m101 = P∧?Q∧R m110 = P∧Q∧?R, m111 = P∧Q∧R, 記真值T和F分別為1和0,小項(xiàng)的真值指派與編碼相同時(shí),真值為Ｔ.小項(xiàng)也可記為:m0, m1, m2, m3, m4, m5, m6, m7.,44,主析取范式,定義1-7.5對于給定的命題公式，如果有一個(gè)等價(jià)公式，它僅有小項(xiàng)的析取所組成，則該等價(jià)式稱

37、作原式的主析取范式．例6.求?(P∧Q)的主析取范式.解:列出其真值表:(P∧?Q)∨(?P∧Q)∨(?P∧?Q)? ?(P∧Q),定理1-7.5 (主析取范式的求法)在真值表中,公式的真值為T的指派所對應(yīng)的小項(xiàng)的析取即為此公式的主析取范式.,45,例8. 求(P∧Q)∨(?P∧R)∨(Q∧R)的主析取范式.,解:首先列出其真值表:,,(P∧Q)∨(?P∧R)∨(Q∧R),T,T,F,F,T,F,T,F,真值為T所對應(yīng)的小項(xiàng)為

38、:P∧Q∧RP∧Q∧?R?P∧Q∧R?P∧?Q∧R故原公式的主析取范式為:(P∧Q∧R)∨(P∧Q∧?R)∨(?P∧Q∧R)∨(?P∧?Q∧R),46,法二:(P∧Q)∨(?P∧R)∨(Q∧R)?((P∧Q)∧(R∨?R))∨((?P∧R)∧(Q∨?Q))∨((Q∧R)∧(P∨?P))?(P∧Q∧R)∨(P∧Q∧?R)∨(?P∧R∧Q)∨ (?P∧R∧?Q)∨(

39、Q∧R∧P)∨(Q∧R∧?P)?(P∧Q∧R)∨(P∧Q∧?R)∨(?P∧Q∧R)∨(?P∧?Q∧R),47,(3) 主合取范式,定義1-7.6 n個(gè)命題變元的析取式,稱作布爾析取式或大項(xiàng),其中每個(gè)變元與它的否定出現(xiàn)且僅出現(xiàn)一個(gè).注:n個(gè)命題變元的大項(xiàng)共有2n個(gè)三個(gè)命題變元P,Q,R其大項(xiàng):M000=P∨Q∨R, M001=P∨Q∨?R, M010=P∨?Q∨R, M011=P∨?Q∨

40、?R,M100=?P∨Q∨R, M101=?P∨Q∨?R, M110=?P∨?Q∨R, M111=?P∨?Q∨?R一大項(xiàng)僅對應(yīng)一組真值指派使其真值為假.任兩個(gè)大項(xiàng)均不等價(jià),且其析取為真.全體大項(xiàng)的合取永為假.,48,主合取范式,定義1-7.7 對于給定的命題公式，如果有一個(gè)等價(jià)公式，它僅有大項(xiàng)的合取所組成，則該等價(jià)式稱作原式的主合取范式．定理1-7.4 (主合取范式的求法)在真值表中,公式的真值為

41、F的指派所對應(yīng)的大項(xiàng)的合取即為此公式的主合取范式.,,49,例10. 求(P∧Q)∨(?P∧R)的主合取范式與主析取范式.,解:首先列出其真值表:,,(P∧Q)∨(?P∧R),T,T,F,F,T,F,T,F,真值為F所對應(yīng)的大項(xiàng)為:?P∨Q∨?R?P∨Q∨RP∨?Q∨RP∨Q∨R故原公式的主合取范式為:(?P∨Q∨?R)∧(?P∨Q∨R)∧(P∨?Q∨R)∧(P∨Q∨R)同理,原公式的主析取范式為(P∧Q∧R)∨(P∧Q∧

42、?R)∨(?P∧Q∧R)∨(?P∧?Q∧R),50,例10:化(P∧Q)∨(?P∧R)為主合取范式.解: (P∧Q)∨(?P∧R)?((P∧Q)∨?P)∧((P∧Q)∨R)?(P∨?P)∧(Q∨?P)∧(P∨R)∧(Q∨R)?(Q∨?P)∧(P∨R)∧(Q∨R)?((Q∨?P)∨(R∧ ?R))∧((P∨R)∨(Q∧ ?Q))∧

43、 ((Q∨R)∨(P∧ ?P))?(Q∨?P∨R)∧(Q∨?P∨?R)∧(P∨R∨Q)∧ (P∨R∨?Q)∧(Q∨R∨P)∧(Q∨R∨?P)?(Q∨?P∨R)∧(Q∨?P∨?R)∧(P∨R∨Q)∧(P∨R∨?Q),51,(4)主析(合)取范式的簡潔表達(dá),∑表示小項(xiàng)的析取, ∑i,j,k表示mi∨mj∨mk∏表示大項(xiàng)的合取, ∏ i

44、,j,k表示Ｍi∧Ｍj∧Ｍk例10可表示為(P∧Q)∨(?P∧R) ?(P∧Q∧R)∨(P∧Q∧?R)∨(?P∧Q∧R)∨(?P∧?Q∧R)? m111∨m110∨m011 ∨m001?∑1,3,6,7(P∧Q)∨(?P∧R) ? (?P∨Q∨?R)∧(?P∨Q∨R)∧(P∨?Q∨R)∧(P∨Q∨R)? M101∨M100∨M010 ∨M000? ∏0,2,4,5命題公式A主析取范式為∑i1,i2,…ik命題公式

45、A主合取范式為 ∏1,2,… i1-1, i1+1,…i2-1, i2+1,… ik-1, ik+1,…2n-1,52,1-8 推理理論,定義1-8.1設(shè)A和C是兩個(gè)命題公式,若A?C,稱C是A的有效結(jié)論.或稱C可由A邏輯地推出.稱C是一組前提H1,H2,…Hn的有效結(jié)論,當(dāng)且僅當(dāng)H1∧H2∧…∧Hn?C記作: H1,H2,…Hn ?C判別有效結(jié)論的過程就是論證過程．常用的論證方法：真值表法,真接證法

46、, 間接證法.(1)真值表法,53,例1.一份統(tǒng)計(jì)表格的錯誤或者是由于材料不可靠,或者是由于計(jì)算有錯誤;這份統(tǒng)計(jì)表格的錯誤不是由于材料不可靠,所以這份統(tǒng)計(jì)表格是由于計(jì)算有錯誤.解: 設(shè)各命題變元為P:統(tǒng)計(jì)表格的錯誤是由于材料不可靠.Q:統(tǒng)計(jì)表格的錯誤是由于計(jì)算有錯誤.本例可譯為:Q是前提P∨Q, ?P的有效結(jié)論,即?P∧(P∨Q) ?Q.為此列出真值表如下:,由真值表可看到,僅在第三行,前提P∨Q, ?P均為真,而此時(shí)結(jié)

47、論Q為T.故?P∧(P∨Q) ?Q成立,54,例2. 如果張老師來了,這個(gè)問題可以得到解答,如果李老師來了,這個(gè)問題也可以得到解答,總之張老師或李老師來了,這個(gè)問題就可以得到解答.解: 若設(shè) P:張老師來了.Q:李老師來了.R:這個(gè)問題可以得到解答.上述語句可譯成下述命題關(guān)系式:(P→R)∧(Q→R)∧(P∨Q) ?R通過真值表可驗(yàn)證上述關(guān)系式成立.,55,(2)直接證法,直接證法就是由一組前提,利用一些公認(rèn)的推理規(guī)則,根

48、據(jù)已知的等價(jià)或蘊(yùn)涵重言式,推演得到有效的結(jié)論.推理規(guī)則P規(guī)則(也稱前提引入規(guī)則)在推導(dǎo)過程中,前提可視需要引入使用T規(guī)則(也稱結(jié)論引入規(guī)則)在推導(dǎo)過程中,前面導(dǎo)出的有效結(jié)論都可作為后繼推導(dǎo)的前提引入CP規(guī)則(也稱條件證明引入規(guī)則)若推出的有效結(jié)論為條件式R→C,只需將前件R加入到前提中作為附加前提,再推出后件C即可.事實(shí)上,若H1∧H2∧…∧Hn∧R?C則H1∧H2∧…∧Hn?R→C常用的蘊(yùn)涵式和等價(jià)式 P43,56,

49、例1. 證明(P∨Q)∧(P→R)∧(Q→S) ?S∨R,證明:(1) P∨Q P(2) ?P→Q T(1) E(3) Q→S P(4) ?P→S T(2)(3), I(5) P→R P(6) ?S→P T(4),E(7) ?S→R T(6) (5) E(8) S∨R

50、 T(7) E,證明(二)(1) P→R P(2) P∨Q→R∨Q T(1),I(3) Q→S P(4) Q∨R→S∨R T(3),I(5) P∨Q→S∨R T(2)(4),I (6) P∨Q P(7) S∨R T(5)(6), I,57,例2.

51、W∨R→V,V→C∨S,S→U,?C∧?U??W,證明:?C∧?U P?C T(1),I ?U T(1),IS→U P?U→?S T(4), I?S T(3)(5),I?C ∧?S T(2)(7),E?(C∨S) T(7),E,V→C∨S P ?(C∨S) →?V

52、T(9),I ?V T(8)(10),I W∨R→V P ?V→?(W∨R) T(12),E ?(W∨R) T(11)(13)I ?W∧?R T(14),E ?W T(15),I,58,例3.證明：A→(B→C), ?D∨A, B?D→C,證明D

53、 P(附加前提)?D∨AD→AAA→(B→C)B→CCD→C CP(1)(7),59,(3)間接證法,公式H1,H2,…Hn相容：存在某些指派使H1∧H2∧…∧Hn的真值為Ｔ,否則稱不相容.欲證H1∧H2∧…∧Hn?C,即(H1∧H2∧…∧Hn)→C為永真,即?C→ ? (H1∧H2∧…∧Hn)為永真,即C∨? (H1∧H2∧…∧Hn)為永真,故? C∧

54、(H1∧H2∧…∧Hn)永假.只需證H1,H2,…Hn, ?C不相容.,60,例4. 證明：A→B, ?(B∨C) ??A,證明:A→B PA P(附加前提)B T(1)(2),I?(B∨C) P?B∧?C T(4),E?B

55、 T(5),I B∧?B T(3)(6),E,61,例5.證明：(P∨Q)∧(P→R)∧(Q→S) ?S∨R,證明:?(S∨R) P(附加前提)?S∧?R T(1),EP∨Q P P→R P ?R→?P

56、 T(4),E?R T(2),I ?P T(5)(6),IQ→S?S→?Q?S?Q?P∧?Q T(7)(11),E ?(P∨Q) T(12),E(P∨Q) ∧ ?(P∨Q) T(3)(13),E,62,例6.設(shè)有下列情況,結(jié)論是否有效?(a)或者是

57、天晴,或者是下雨.(b)如果是天晴,我就去看電影.(c)如果我去看電影,我就不看書.結(jié)論:如果我在看書則天下雨.解: M:天晴; Q:下雨; S:我看電影; R:我看書.前提: (M∧?Q)∨(?M∧Q) M→S S→?R結(jié)論: R→Q即需證: (M∧?Q)∨(?M∧Q), M→S, S→?R? R→Q,63,證: (M∧?Q)∨(?M∧Q), M→S, S→?R? R→Q,證一:RS→?R?SM→

58、S?M(M∧?Q)∨(?M∧Q)((M∧?Q)∨(?M∧Q)) ∧?M((M∧?Q) ∧?M )∨((?M∧Q) ∧?M)F∨((?M∧Q) ∧?M) ?M∧QQR→Q,64,證: (M∧?Q)∨(?M∧Q), M→S, S→?R? R→Q,證二:設(shè)R→Q為F 則R為T且Q為F. 設(shè)S→?R和M→S均為T, 則由R為T和S→?R為T知S為F, 由S為F和M→S為T知M為F.