離散數學單元1

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

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

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

4、要進行推理，從具體的前提出發(fā)，得出具體的結論。例（1）函數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數理邏輯研究的推理的特點：不注重內容，注重形式關系 (1）A ∨ B（2）?A（3）B,5,,三、數理邏輯的內容集合論模型論遞歸論證明論共同的邏輯基礎：邏輯演算（命題邏輯和

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

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

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

8、 →P→Q讀作:如果P那么QP→Q為F當且僅當P為T，Q為F雙條件聯結詞（等值聯結詞） ?P?Q讀作: P當且僅當QP?Q為T當且僅當P和Q的真值相同,聯結詞是邏輯聯結詞或命題聯結詞的抽象是自然語言中連詞的抽象,10,五種聯結詞的定義,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,注,析取聯結詞是“或”的抽象可兼或：a.b=0即a=0或b=0或a=b=0 (至少有一發(fā)生)排斥或：他的死或重于泰山或輕于鴻毛．表示近似的或:去文昌樓需6分鐘或8分鐘．條件聯結詞P→Q,P稱為前件,Q稱為后件當前件為F時,P→Q為T復合命題的真值只取決于構成它們的各原子命題的真值，而與其內容、含義無關聯結詞有操作或運算的含義可看作一元運算符、二元運算符，……,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)單個命題變元是合式公式.(2)如果A是合式公式,則(?A)是合式公式.(3)如果A和B是合式

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

13、,文字敘述的命題 由命題標識符,聯結詞,括號所組成的合式公式.步驟:(1)分析出各原子命題,并用符號表示(2)使用合適的聯結詞,將原子命題聯結起來,并加適當的括號,來組成復合命題的符號化表示.,,16,例3: 將下列命題符號化,(1)如果我上街,我就去書店看看,除非我很累.P:我上街. Q: 我去書店. R:我很累.(1)可符號化為: ?R→ (P→Q)(2)王一樂是數學系的學生,他生于1968

14、年或1969年,他是三好學生.P:王一樂是數學系的學生.Q:他生于1968年.R:他生于1969年.S:他是三好學生.(2)可符號化為: P∧(Q∨R)∧S,17,1-4,5 真值表 等價公式 重言式 蘊涵公式,1.真值表定義1-4.1 在命題公式中,對于分量指派真值的各種可能組合,就確定了這個命題公式的各種真值情況,把它匯成表,就是命題公式的真值表.,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個命題變元的命題公式，其真值表有2n

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

17、A?B.例5 證明: (1) P→Q??P∨Q(2) P?Q? (P→Q)∧(Q→P),注:A?B 即對A和B的任一真值指派,有A和B的真值相同.在邏輯相等意義下,含n 個原子變元的公式的個數為?與?的區(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.蘊涵公式(邏輯蘊涵),定義1-5.3 設A,B是公式,若A→B是重言式,則稱A蘊涵B,記作A?B.定理 1-5.4 設A

19、,B是命題公式.A?B的充要條件是A?B且B?A.證明:利用A ? B? (A→B)∧(B→A)來證.,24,注:,→與?的區(qū)別.幾個類似的公式P→Q, Q→P, ?P→?Q, ?Q→?P稱為 逆換式 反換式 逆反式有P→Q??Q→?PP?Q的證明方法真值表假設前件真,推出后件真假設后件假,推出前件假?的特性若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、的蘊涵式,Q,?P,Q,(P→R),R,26,例5 推證?Q∧(P→Q) ??P,證明:法一:設?Q∧(P→Q)為T,則?Q為T從而Q為F由(P→Q)為T及Q為F可知P為F故?P為T.,法二:設?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 設X是合式公式A的子公式,Y是一公式.若X?Y,如果將A中的X用Y來置換所得公式B,則A ? B.注滿足定理1-4.1的置換稱為等價轉換或等價代換.替換規(guī)則又提供了一種證明公式等價的方法.,28,例7 證明: Q→(P∨(P∧Q)) ? Q→P證明: 因為P∨(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) (結合律, 冪等律)? ((P∨Q)∧(P∨R))∨? (P∨Q)∨? (P∨R) (德.摩根律)((P∨Q)∧(P∨R))∨? ((

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

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

28、,∨}, {?,∧},{?,→}是最小聯結詞組 {↑},{↓}也是最小聯結詞組 {?},{∧},{∨},{∧,V}均不是最小聯結詞組,36,1-7對偶和范式,1.對偶定義1-7.1 在給定的僅用聯結詞?,∧和∨的命題公式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是出現在A和A*中的原子變元, 則?A(P1,P2,…,Pn) ?A*(?P1, ?P2,…, ?Pn)A(?P1, ?P2,…, ?Pn) ??A*(P1,P2,…,Pn)注:德.摩根律的推廣?(P1∧P2∧…∧Pn) ??P1∨?P2∨…∨?Pn設A1,A2,…,An是任意命題變元,則?(

30、A1∧A2∧…∧An) ??A1∨?A2∨…∨?An例3. 設A*(S,W,R)是?S∧(?W∨R),驗證: A*(?S, ?W, ?R) ??A(S,W,R)例4. 如果A(P,Q,R)是P↑(Q∧?(R↓P)),求它的對偶式A*(P,Q,R),分別求與A及A*等價,但僅包含聯結詞∧,∨和?的公式.,38,定理1-7.2 設P1,P2,…,Pn是出現在公式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.范式-公式的標準型,(1)析取范式,合取范式定義 1-7.2 　一個命題公式稱為合取范式,當且僅當它具有型式: A1∧A2∧…∧An 　 (n≥1)其中A1，A2，…，An都是由命題變元或其否定所組成的析取式．定義 1-7.3 　一個命題公式稱為析取范式,當且僅當它具有型式: 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個命題變元的合取式,稱作布爾合取式或小項,其中每個變元與它的否定出現且僅出現一個.注:三個命題變元P,Q,

35、R其小項:P∧Q∧R, P∧Q∧?R, P∧?Q∧R, P∧?Q∧?R,?P∧Q∧R, ?P∧Q∧?R, ?P∧?Q∧R, ?P∧?Q∧?Rn個命題變元的小項共有2n個一小項僅對應一組真值指派使其真值為真.任兩個小項均不等價,且其合取為假.全體小項的析取永為真.,43,小項的編碼表示,命題變元P,Q,R的小項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,小項的真值指派與編碼相同時,真值為Ｔ.小項也可記為:m0, m1, m2, m3, m4, m5, m6, m7.,44,主析取范式,定義1-7.5對于給定的命題公式，如果有一個等價公式，它僅有小項的析取所組成，則該等價式稱

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

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個命題變元的析取式,稱作布爾析取式或大項,其中每個變元與它的否定出現且僅出現一個.注:n個命題變元的大項共有2n個三個命題變元P,Q,R其大項: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一大項僅對應一組真值指派使其真值為假.任兩個大項均不等價,且其析取為真.全體大項的合取永為假.,48,主合取范式,定義1-7.7 對于給定的命題公式，如果有一個等價公式，它僅有大項的合取所組成，則該等價式稱作原式的主合取范式．定理1-7.4 (主合取范式的求法)在真值表中,公式的真值為

41、F的指派所對應的大項的合取即為此公式的主合取范式.,,49,例10. 求(P∧Q)∨(?P∧R)的主合取范式與主析取范式.,解:首先列出其真值表:,,(P∧Q)∨(?P∧R),T,T,F,F,T,F,T,F,真值為F所對應的大項為:?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)主析(合)取范式的簡潔表達,∑表示小項的析取, ∑i,j,k表示mi∨mj∨mk∏表示大項的合取, ∏ 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設A和C是兩個命題公式,若A?C,稱C是A的有效結論.或稱C可由A邏輯地推出.稱C是一組前提H1,H2,…Hn的有效結論,當且僅當H1∧H2∧…∧Hn?C記作: H1,H2,…Hn ?C判別有效結論的過程就是論證過程．常用的論證方法：真值表法,真接證法

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

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

48、據已知的等價或蘊涵重言式,推演得到有效的結論.推理規(guī)則P規(guī)則(也稱前提引入規(guī)則)在推導過程中,前提可視需要引入使用T規(guī)則(也稱結論引入規(guī)則)在推導過程中,前面導出的有效結論都可作為后繼推導的前提引入CP規(guī)則(也稱條件證明引入規(guī)則)若推出的有效結論為條件式R→C,只需將前件R加入到前提中作為附加前提,再推出后件C即可.事實上,若H1∧H2∧…∧Hn∧R?C則H1∧H2∧…∧Hn?R→C常用的蘊涵式和等價式 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.設有下列情況,結論是否有效?(a)或者是

57、天晴,或者是下雨.(b)如果是天晴,我就去看電影.(c)如果我去看電影,我就不看書.結論:如果我在看書則天下雨.解: M:天晴; Q:下雨; S:我看電影; R:我看書.前提: (M∧?Q)∨(?M∧Q) M→S S→?R結論: 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,證二:設R→Q為F 則R為T且Q為F. 設S→?R和M→S均為T, 則由R為T和S→?R為T知S為F, 由S為F和M→S為T知M為F.