離散數(shù)學(xué)自考第一章課后習(xí)題和答案

1、,離散數(shù)學(xué),,楊老師yangjj@scnu.edu.cn,,離散數(shù)學(xué)（又稱計算機數(shù)學(xué)）是現(xiàn)代數(shù)學(xué)的重要分支，是計算機專業(yè)課程中的核心基礎(chǔ)課程之一。離散數(shù)學(xué)以是研究：離散量的結(jié)構(gòu)和相互之間的關(guān)系為主要目標，其研究對象一般為：有限或可數(shù)個元素（例如：自然數(shù)、整數(shù)、真假值、有限個結(jié)點等），而離散性也是計算機科學(xué)的顯著特點。,離散數(shù)學(xué),,離散數(shù)學(xué)與計算機科學(xué)的其他課程如：數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、編譯原理、算法分析、邏輯設(shè)計、系統(tǒng)結(jié)構(gòu)、容錯技術(shù)

2、、人工智能等有密切的聯(lián)系。它是這些課程的先導(dǎo)和基礎(chǔ)課程。第一部分：數(shù)理邏輯 第二部分：集合論第三部分：代數(shù)系統(tǒng) 第四部分：圖論,第一章 命題演算,命題概念基本連接詞與復(fù)合命題合式公式與聯(lián)結(jié)詞優(yōu)先順序命題公式的等價變化、命題符號化構(gòu)造真值表證明等價式不構(gòu)造真值表證明蘊含式范式與主范式，∏，∑互化應(yīng)用P、T規(guī)則的推理證明CP規(guī)則與間接推理證明,1.1 命題概念,命題：具有唯一真值的陳述句叫命題，亦可簡

3、稱為語句。(1)命題可以是真的，或者是假的，但不能同時為真又為假(2)命題所用符號：常用大寫２６個英文字母表示命題。用Ａ、Ｂ、Ｃ．．．．Ｚ表示。(3)命題中所有的“真”用“Ｔ”表示，　 命題中所有的“假”用“Ｆ”表示。(4)命令句，感嘆句，疑問句均不是命題。,判斷下列句子中哪些構(gòu)成命題8是偶數(shù)；雪是黑的；明年國慶節(jié)是個春天；3+8>9我是大學(xué)生；火星上有生物；星期五下午開會嗎？請勿吸煙；這束花多么的好

4、看??！x+y >5.,命題命題命題命題命題命題疑問句 不是命題祈使句 不是命題感嘆句 不是命題無法確定真值 不是命題,,表示命題的符號稱為命題標示符，例：P：今天中午十點下雨； [24]：今天上午十點下雨；此處的P，[24]就是標示符。一個命題標示符如表示確定命題，就稱為命題常量，如果命題標示符只標志命題的位置，就稱為命題變元，因為命題變元可以表示任意命題，他不能確定真值因此不是命題,1.2

5、復(fù)合命題與聯(lián)結(jié)詞,原子命題：不能再分解的命題，不包含任何聯(lián)結(jié)詞的命題。復(fù)合命題：經(jīng)過一些聯(lián)結(jié)詞復(fù)合而成的命題。在命題演算中也有類似的日常生活中的聯(lián)結(jié)詞稱做：“命題聯(lián)結(jié)詞”下面先介紹五個常用的命題聯(lián)結(jié)詞。,,１．否定詞：（否定運算、非運算）（１）符號 ¬ ,讀作“非”，“否定”，設(shè)命題為Ｐ，則在Ｐ的前面加否定詞¬ ，變成¬Ｐ， ¬Ｐ讀做“Ｐ的否定”或“非Ｐ”例：Ｐ：北京是一座城市。

6、 ¬Ｐ：北京不是一座城市。Ｑ：每一種生物均是動物。F¬Ｑ：有一些生物不是動物。T這里¬Ｑ不能講成“每一種生物都不是動物”為假命題了。對量化命題的否定，除對動詞進行否定外，同時對量化詞也要加以否定。（2） ¬Ｐ的真值由P的真值來確定,,２．合取詞（“合取”、“積”、“與”運算）符號　“Λ” 設(shè)Ｐ，Ｑ為兩個命題，則ＰΛＱ稱Ｐ與Ｑ的合取，讀作：“Ｐ與Ｑ”、“Ｐ與Ｑ的合取”、“Ｐ并且Ｑ

7、”等。定義（由真值表給出）：,,當(dāng)且僅當(dāng)Ｐ和Ｑ的真值均為“Ｔ”，則（ＰΛＱ）的真值為“Ｔ”。否則，其真值為“Ｆ”。注意：Ｐ和Ｑ是互為獨立的；地位是平等的，Ｐ和Ｑ的位置可以交換而不會影響ＰΛＱ的結(jié)果。在日常生活中，合取詞應(yīng)用在二個有關(guān)系的命題之間。而在邏輯學(xué)中，合取詞可以用在二個毫不相干的命題之間舉例：（a）P：王華的成績很好 Q：王華的品德很好。 則ＰΛＱ：王華的成績很好并且品

8、德很好。 （b P：我們?nèi)シN樹 Q：房間里有一臺電視機 則ＰΛＱ：我們?nèi)シN樹與房間里有一臺電視機。 (c) P：今天下大雨 Q：3+3=6 則ＰΛＱ：今天下大雨和3+3=6,,３．析取詞（或運算）（１）符號“∨” 設(shè)Ｐ、Ｑ為二個命題，則（Ｐ∨Ｑ）稱作Ｐ與Ｑ的“析取”，讀作：

9、“Ｐ或Ｑ”。（２）定義（由真值表給出）：,,當(dāng)且僅當(dāng)Ｐ、Ｑ均為“Ｆ”時，（Ｐ∨Ｑ）為“Ｆ”。否則，其真值為“Ｔ”區(qū)分“可兼或”與“不可兼或（異或，排斥或）” 析取詞為可兼或即:P和Q均為“T”時（P∨Q）為“T”， “不可兼或”中當(dāng)P和Q均為“T”時，則P異或Q為“F”,可兼“或”：燈泡有故障或開關(guān)有故障。今晚寫字或看書。今天下雨或打雷。,不可兼“或”：他通過電視看雜技或到劇場看雜技。 他乘火車去北京或乘飛機去北

10、京。,,４．單條件聯(lián)結(jié)詞：（１）符號“→”，讀作：“如果…則…”、“如果…那么…”Ｐ、Ｑ為二個命題，（Ｐ→Ｑ）為新的命題，讀作：“如果Ｐ則Ｑ”，“Ｐ僅當(dāng)Ｑ”，“Ｑ當(dāng)且Ｐ”，“Ｐ是Ｑ的充分條件”。（２）定義（由真值表定義）：,,當(dāng)Ｐ為“Ｔ”，Ｑ為“Ｆ”時，則（Ｐ→Ｑ）為“Ｆ”，否則（Ｐ→Ｑ）均為“Ｔ”?！　　　　　　　　。校悍Q為前件、條件、前提、假設(shè)Ｑ：稱為后件、結(jié)論。（３）舉例： （a）P：我拿起一本書

11、 Q：我一口氣讀完了這本書 P→Q：如果我拿起一本書，則我一口氣讀完了這本書。 （b）P：月亮出來了 Q：3×3=9 P→Q：如果月亮出來了，則 3×3=9。（善意推定）,,５．雙條件聯(lián)結(jié)詞（“等價”詞、“同”聯(lián)結(jié)詞、“等同”詞）（１）符號“?”設(shè)Ｐ、Ｑ為二個命題，則Ｐ?Ｑ讀作：“Ｐ當(dāng)且僅當(dāng)Ｑ”，“Ｐ等價Ｑ”,“Ｐ是Ｑ的充分必要條件”。（２

12、）定義（見真值表）：,,每當(dāng)Ｐ和Ｑ的真值相同時，則（Ｐ?Ｑ）的真值為“Ｔ”，否則（Ｐ?Ｑ）的真值為“Ｆ”。（３）舉例：? 春天來了當(dāng)且僅當(dāng)燕子飛回來了。?平面上二直線平行，當(dāng)且僅當(dāng)這二直線不相交。 ?２＋２＝４當(dāng)且僅當(dāng)雪是白色的。 （兩者沒有關(guān)系，但是確實命題）（４）Ｐ,Ｑ中，Ｐ、Ｑ的地位是平等的，Ｐ、Ｑ交換位置不會改變真值表中的值。,,６．命題聯(lián)結(jié)詞在使用中的優(yōu)先級（１）先括號內(nèi)，后括號外（２）運算時聯(lián)結(jié)詞的優(yōu)先次序

13、為： ¬ 　Λ　∨　→ ? （由高到低）（３）聯(lián)結(jié)詞按從左到右的次序進行運算 ¬Ｐ∨（Ｑ∨Ｒ）可省去括號，因為“Ｖ”運算是可結(jié)合的。（ ¬Ｐ∨Ｑ）∨Ｒ可省去括號，因為符合上述規(guī)定而Ｐ→（Ｑ→Ｒ）中的括號不能省去，因為“→”不滿足結(jié)合律?！?（４）最外層的括號一律均可省去（Ｐ→Ｑ∨Ｒ）可寫成Ｐ→Ｑ∨Ｒ,,７．命題聯(lián)結(jié)詞小結(jié)：（1）五個聯(lián)結(jié)詞的含義與日常生活中的聯(lián)結(jié)詞的含義大致相同。（2

14、）“或”可分為可兼或（∨）和異或（ ▽ ）（不可兼或） （3） 除“¬”為一元運算外，其余四個均為二元運算。（4）“→”當(dāng)前件為“Ｆ”時，不論后件怎樣，則單條件命題的真值均為“Ｔ”。（5）命題聯(lián)結(jié)詞是命題或命題之間的聯(lián)結(jié)詞，而不是名詞之間、數(shù)字之間和動詞之間的聯(lián)結(jié)詞。,,以上介紹了五種常用的聯(lián)結(jié)詞及其相應(yīng)的復(fù)合命題形式。數(shù)理邏輯的特點是把邏輯推理變成類似數(shù)學(xué)演算的完全形式化了的邏輯演算，為此，首先要把推理所涉及到的各命題

15、符號化。步驟如下：①找出各簡單命題，分別符號化。②找出各聯(lián)結(jié)詞，把簡單命題逐個聯(lián)結(jié)起來。約定： （1）我們只注意命題的真假值，而不再去注意命題的漢語意義。（2）對命題聯(lián)結(jié)詞，我們只注意真值表的定義，而不注意它日常生活中的含義。,,例. 將下列命題符號化：（1）李明是計算機系的學(xué)生，他住在312室或313室。（2）張三和李四是朋友。（3）雖然交通堵塞，但是老王還是準時到達了車站。（4）只有一個角是直角的三角形才是直角三角

16、形。（5）老王或小李中有一個去上海出差。,,解：（1）首先用字母表示簡單命題。P：李明是計算機系的學(xué)生。Q：李明住在312室。該命題符號化為：P?Q（2）張三和李四是朋友。是一個簡單句該命題符號化為：P（3）首先用字母表示簡單命題。P：交通堵塞。 Q：老王準時到達了車站。該命題符號化為：P?Q,,（4）首先用字母表示簡單命題。P：三角形的一個角是直角。Q：三角形是直角三角形。該命題符號化為：?P? ?Q

17、（5）首先用字母表示簡單命題。P：老王去上海出差。Q：小李去上海出差。也可符號化為： （P??Q）?（?P?Q）或者 （P ? Q） ? ? （P?Q）,,作業(yè)：P61：a、c、d、g、i、k3：a、c、e4：b、d,1.3 命題公式與真值表,１．命題公式命題常元：表示確定的命題｛T，F(xiàn)｝。命題變元：以真假為其變域之變元，或沒有指定真值的命題。常用大寫英文字母Ａ…Ｚ表示。命題公式：由命題變元、常元、聯(lián)結(jié)

18、詞、括號，以規(guī)定的格式聯(lián)結(jié)起來的字符串。命題公式亦可稱為合式公式。,,定義：命題演算的合式公式規(guī)定為：１）單個命題變元是一個合式公式。２）若Ａ是合式公式，¬Ａ也為合式公式。３）若Ａ、Ｂ是合式公式，則（ＡΛＢ）、（Ａ∨Ｂ）、（Ａ→Ｂ）、（Ａ?Ｂ）均為合式公式。 ４）當(dāng)且僅當(dāng)有限次使用 （１）（２）（３）所生成的公式才是命題公式。 （2）（3）即為關(guān)于聯(lián)結(jié)詞的運算是封閉的。子公式：設(shè)Ai為公式的A的一部分，

19、且Ai是一個子公式，稱Ai是A的子公式。,,２．命題公式的真值表 :定義：命題變元用特定的命題來取代，這一過程稱為對該命題變元進行指派。真指派：指定的指派使得命題變元為真；假指派：指定的指派使得命題變元為真。命題公式可以看成是一個以真假值為定義域和真假值為值域的一個函數(shù)。 寫成ｙ＝ｆ(x)例如：公式 P ?(Q ?R) 定義三元函數(shù) Y(P，Q，R)＝ P ?(Q ?R),,《定義》：命題公式A在其所有可能的

20、賦值下取得的值列成的表稱為A的真值表。真值表中，真值T、F可分別用1、0代替構(gòu)造真值表的步驟如下：1)找出給定命題公式中所有的命題變元，列出所有可能的賦值。2)按照從低到高的順序?qū)懗雒}公式的各層次。3)對應(yīng)每個賦值，計算命題公式各層次的值，直到最后計算出整個命題公式的值。,,例１．構(gòu)造命題公式¬（（Ｐ∨Ｑ）ΛＰ）的真值表：,２個命題變元有４組真值指派；３個命題變元有23＝ ８組真值指派，ｎ個則有個2n個真值指派,３

21、．命題公式的永真式、永假式和可滿足式,定義：設(shè)A為一命題公式，若A在它的各種指派情況下，其取值均為真，則稱公式A為重言式或永真式。定義：設(shè)A為一命題公式，若A在它的各種指派情況下，其取值均為假，則稱公式A為矛盾式或永假式定義：設(shè)A為一命題公式，若A在各種真值指派下至少存在一組成真指派，則稱A為可滿足式。（可滿足式為既不是永真式又不是永假式的命題公式）討論：（１）永真式的否定為永假式（¬Ｔ＝Ｆ）；永假式的否定為永真式（

22、¬Ｆ＝Ｔ）。（２）二個永真式的析取、合取、蘊含、等價均為永真式。,,列出A：(P??Q)?(P?Q) 與B：(P??R)?(P?R)的真值表：,1.4.1等價式,定義：如果對兩個公式Ａ，Ｂ不論作何種指派，它們真值均相同，則稱Ａ，Ｂ是邏輯等價的，亦說Ａ（Ｂ）等價于Ｂ（Ａ）。并記作：Ａ?Ｂ,,定理：設(shè)X是合式公式A的子公式，若有Y也是一個合式公式，且X=Y，如果將A中的X用Y置換，得到公式B，則A ?B。例1：證明Q ?（P

23、∨（P ΛQ）） ?Q ?P。設(shè)：A： Q ?（P∨（P ΛQ）） 因為 P∨（P ΛQ） ?P 故B：Q ?P，即A ?BP12例2、3、4P14 題2 a） P ? （Q ?P） ? ¬ P ∨ （ Q ?P ） （ 等值公式） ? ¬ P ∨ （ ¬ Q ∨ P） （ 等值公式）

24、 ? P ∨ ¬ P ∨ ¬ Q （交換律） ? ¬ P ? （¬ P ∨ ¬ Q） （ 等值公式） ? ¬ P ? （ P ? ¬ Q ） （ 等值公式） 得證,,定理：命題公式Ａ?Ｂ的充要條件是Ａ?Ｂ為永真式證明： （１）充分性：Ａ?Ｂ為永真式，即

25、Ａ、Ｂ有相同的真值，所以Ａ?Ｂ。（２）必要性：Ａ?Ｂ，即Ａ、Ｂ有相同的真值表，所以Ａ?Ｂ為永真式。說明：“?”為等價關(guān)系符，Ａ?Ｂ表示Ａ和Ｂ有等價關(guān)系。Ａ?Ｂ不為命題公式　 “?”為等價聯(lián)結(jié)詞（運算符），Ａ、Ｂ為命題公式，則（Ａ?Ｂ）也為一命題公式。,1.4.2蘊含式,定義：命題公式P稱為永真蘊含命題公式Q，當(dāng)且僅當(dāng)P→Q是一個永真式， 記作：P?Q，稱P蘊含Q。 “? ”是關(guān)系符，Ａ? Ｂ不為命題公式例：證明：Ｐ? Ｐ

26、∨Ｑ；ＰΛＱ? P（１）列出真值表 證明：Ｐ→（Ｐ∨Ｑ）和（ＰΛＱ）→Ｐ為永真式（２）可用等價公式證：Ｐ→（Ｐ∨Ｑ） ? ¬Ｐ∨（Ｐ∨Ｑ）? T（ＰΛＱ）→Ｐ? ¬（ＰΛＱ）∨Ｐ ? ¬Ｐ∨ ¬Ｑ∨Ｐ? T,,定理：設(shè)P、Q為任意兩個命題公式，P?Q的充分必要條件是P?Q， Q ? P。證明：　若P ? Q ，則P ? Q為一永真式由定律：

27、（ P ? Q ）?（ P → Q ）Λ（ Q → P ） ∴（ P → Q ）且（ Q → P ）也為一永真式 即： P ? Q且Q ? P成立反之　　 P ? Q且Q ? P 　則P?Q也成立此定理把“?”和“? ”之間建立了相應(yīng)的關(guān)系。說明若是要證明P?Q，只需證明P ? Q且Q ? P,,證明上述永真蘊含式的方法有三種：（１）把“? ”關(guān)系符改為“→”聯(lián)結(jié)詞，證明它為永真式。(a)真值表法 (

28、b)命題演算法（２）＊若前件為真，則命題公式為“Ｔ” ，只需找出使單條件命題前件為“Ｔ”的所有真值指派，試看能否導(dǎo)致后件均為“Ｔ”，若為“Ｔ”，則永真蘊含關(guān)系成立。（３）＊ 由于（ P → Q ） ? （ ¬ Q → ¬ P ），找出使單條件命題的后件均為“Ｆ”的所有真值指派，試看前件的所有真值是否為“Ｆ”，若是，則蘊含成立。,,例：ＰΛ（Ｐ→Ｑ） ? Ｑ前件為“Ｔ”的所有指派為Ｐ、（Ｐ→Ｑ）均為“Ｔ”，

29、Ｐ→Ｑ為“Ｔ”，∵Ｐ為“Ｔ”，∴Ｑ也應(yīng)為“Ｔ”，∴ＰΛ（Ｐ→Ｑ） ? Ｑ成立,例：¬ＱΛ（Ｐ→Ｑ） ? ¬Ｐ后件為“Ｆ”的所有條件是：Ｐ為“Ｔ”， 代入前件得（ⅰ）若Ｑ為Ｔ，則¬ＱΛ（Ｐ→Ｑ）為“Ｆ”；（ⅱ）若Ｑ為Ｆ，則¬ＱΛ（Ｐ→Ｑ）為“Ｆ”；　∴¬ＱΛ（Ｐ→Ｑ） ? ¬Ｐ成立,,討論一下永真式可得出三個結(jié)論：（１）若一個命題公式等價于一個永真式，則該公式一

30、定為永真式。（２）若一個永真的命題公式永真蘊含一個命題公式，則此命題公式一定也為永真式。（３）若一個永假的命題公式永真蘊含一個命題公式，則該公式可能是永真式、永假式或可滿足的。,常用的蘊含式如下：,ＰΛＱ? Ｐ （ＰΛＱ? Ｑ） 化簡式Ｐ?Ｐ∨Ｑ?。ǎ?Ｐ∨Ｑ） 附加式¬P ?Ｐ→Ｑ Ｑ? Ｐ→Ｑ 變形附加式¬（Ｐ→Ｑ） ? Ｐ ¬（Ｐ→Ｑ） ? ¬Ｑ　變形

31、簡化式ＰΛ（Ｐ→Ｑ） ?Ｑ 假言推論¬ＱΛ （Ｐ→Ｑ） ¬Ｐ 拒取式¬ＰΛ（Ｐ∨Ｑ） ? Ｑ 析取三段論（Ｐ→Ｑ）Λ（Ｑ→Ｒ） ? （Ｐ→Ｒ） 條件三段論（Ｐ?Ｑ）Λ（Ｑ?Ｒ） ? （Ｐ?Ｒ） 雙條件三段論（Ｐ→Ｑ）Λ（Ｒ→Ｓ） Λ（Ｐ∨Ｒ）? （Ｑ→Ｓ）合取構(gòu)造二難（Ｐ→Ｑ）Λ（Ｒ→Ｓ） Λ（Ｐ∨Ｒ）? （ＱΛＳ）析取構(gòu)造二難Ｐ→Ｑ? （Ｐ∨Ｒ→Ｑ∨Ｒ） 前后件附加Ｐ→Ｑ? （Ｐ

32、ΛＲ→ＱΛＲ） 前后件附加,,作業(yè)：P14 b、d、fa、c、e,1.5.最小聯(lián)結(jié)詞與范式,任何一個命題公式都可由五個聯(lián)結(jié)詞進行等價代換。（Ｐ?Ｑ） ?（Ｐ→Ｑ） Λ（Ｑ→Ｐ） Ｐ→Ｑ? ¬Ｐ∨Ｑ ＰΛ Ｑ? ¬ （¬Ｐ∨ ¬Ｑ） Ｐ∨ Ｑ? ¬（ ¬ＰΛ ¬Ｑ）由上式公式說明五個聯(lián)結(jié)詞均可以轉(zhuǎn)化為 {¬，∨}，或{¬， Λ}

33、定義：我們把{¬，∨}，或{¬， Λ}稱為命題公式或者最小聯(lián)結(jié)詞。一個命題公式的等價變換，可以有多種不同的形式表達。那如何能化成標準形式及范式的呢？定義：把命題公式化歸為一種標準的形式，稱此標準形式為范式。,,定義：一個命題公式稱為合取范式，當(dāng)且僅當(dāng)他具有形式：A1 Λ A2 Λ…ΛAn ， A1 ， A2 ，…An為命題變元及其否定的所組成的析取式。定義：一個命題公式稱析取范式，當(dāng)且僅當(dāng)他具有形式：

34、A1 ∨ A2 ∨…∨An ， A1 ， A2 ，…An為命題變元及其否定的所組成的合取式。命題變元的析取式亦稱為“和”。合取式亦稱為“積”。所以：合取范式為命題變元及其否定的和之積；析取方式為命題變元及其否定的積之和。,,求命題公式的析取范式方法可按下列三步（或四步）進行：（１）利用等價公式：化去“→”、“?”聯(lián)結(jié)詞，把命題公式變?yōu)榕c其等價的用{¬，∧，∨}表達的公式。 例:

35、 Ｐ→Ｑ?¬Ｐ∨Ｑ， Ｐ?Ｑ?（Ｐ∧Ｑ）∨（¬Ｐ∧¬Ｑ） ?（¬Ｐ∨Ｑ）∧（Ｐ∨¬Ｑ） （２）將“¬”深入到原子命題變元之前，并使變元之前最多只有一個“¬”詞。例： ¬（¬Ｐ∨¬Ｑ）?¬ ¬Ｐ∧ ¬ ¬Ｑ ?Ｐ∧Ｑ（３）利用“

36、∧”對“∨”的分配，將公式化成為析取范式。（４）除去永假項得最簡析取范式。,,（例：求¬（Ｐ∨Ｑ）?（Ｐ∧Ｑ）的析取范式： 解：原式 ?(¬（Ｐ∨Ｑ）∨ （Ｐ∧Ｑ）) ∧ (¬（Ｐ∧Ｑ）∨ ¬（Ｐ∨Ｑ）) ?(¬ （Ｐ∨Ｑ）∧ （Ｐ∧Ｑ）) ∨ (¬ ¬ （Ｐ∨Ｑ）∧ ¬ （Ｐ∧Ｑ）) -----（1）化去?詞 ?（¬Ｐ∧ ¬

37、;Ｑ∧Ｐ∧Ｑ）∨（（Ｐ∨Ｑ）∧（ ¬Ｐ∨ ¬Ｑ）） -----（2）將“¬”深入到變元前面，并最多保留一個? ?（ ¬Ｐ∧ ¬Ｑ∧Ｐ∧Ｑ）∨（（Ｐ∧ ¬Ｐ）∨（Ｐ∧ ¬Ｑ）∨（ ¬Ｐ∧Ｑ）∨（Ｑ∧ ¬Ｑ））-----（3）“∧”對“∨”的分配，化成為析取范式 ?（Ｐ∧¬Ｑ）∨（¬Ｐ∧Ｑ） -----（4）最簡析取范式,

38、,求一個命題公式的合取范式的方法和求析取范式的方法類同：第（１）、（２）步相同；第（３）利用“∨”對“∧”的分配就行；第（４）去掉永真的析取項。,,例：求Ｑ∨¬（Ｐ→Ｑ）∨¬（Ｐ∨Ｑ）的合取范式原式 ? Ｑ∨¬（¬Ｐ∨Ｑ）∨¬（Ｐ∨Ｑ）　　 ——化去“→”詞?Ｑ∨（Ｐ∧ ¬Ｑ）∨（ ¬Ｐ∧ ¬Ｑ）　　 —

39、—“¬”深入到變元前，并最多保留一個?（（Ｑ∨Ｐ）∧（Ｑ∨ ¬Ｑ））∨（ ¬Ｐ∧ ¬Ｑ） ——“∨”對“∧”的分配 ?（Ｑ∨Ｐ∨ ¬Ｐ）∧（Ｑ∨ ¬Ｑ∨ ¬Ｐ）∧（Ｑ∨Ｐ∨ ¬Ｑ）∧（Ｑ∨ ¬Ｑ∨ ¬Ｑ）?Ｔ（最簡合取范式）,,定義：在ｎ個命題變元的合取式中，若每個變元及其否定并不同時存在，且二者之一出現(xiàn)一

40、次且僅出現(xiàn)一次，稱為布爾合取或小項。例：命題變元P和Q，其小項為： P Λ Q， ¬P Λ Q， P Λ ¬Q， ¬P Λ ¬Q對三個命題變元講Ｐ，Ｑ，Ｒ，其小項為：Ｐ∧Ｑ∧Ｒ、 Ｐ∧Ｑ∧¬Ｒ、 Ｐ∧¬Ｑ∧Ｒ、Ｐ∧¬Ｑ∧¬Ｒ、 ¬Ｐ∧Ｑ∧Ｒ、 ¬Ｐ∧Ｑ∧¬Ｒ、¬Ｐ∧¬Ｑ∧Ｒ、

41、2;Ｐ∧¬Ｑ∧¬Ｒ,,有上式可知，若是有2個變元，小項有22=4個，若是有3個變元，小項有23=8個。推廣到一般：ｎ個命題變元構(gòu)成的不同小項有2n個（n∈I+）。使得每個極小項為真的賦值僅有一個?？梢杂枚M制編碼表示。Ｐ與¬Ｐ分別用1、0表示。例：對三個命題變元講Ｐ∧Ｑ∧Ｒ，其小項為：m111=Ｐ∧Ｑ∧Ｒ、 m110=Ｐ∧Ｑ∧¬Ｒ、 m101=Ｐ∧¬Ｑ∧Ｒ、m10

42、0=Ｐ∧¬Ｑ∧¬Ｒ、 m011= ¬Ｐ∧Ｑ∧Ｒ、 m010= ¬Ｐ∧Ｑ∧¬Ｒ、m001= ¬Ｐ∧¬Ｑ∧Ｒ、 m000= ¬Ｐ∧¬Ｑ∧¬Ｒ,,根據(jù)書本P17，表1.5.1可知：（1）每個小項具有一個相應(yīng)編碼，只有編碼與其真是指派相同時，該小項真值為T，在其余2n-1種指派情況下為F。m011= ¬Ｐ∧Ｑ∧Ｒ，只有當(dāng)Ｐ

43、、Ｑ、Ｒ的真值分布為F、T、T是，小項m011= ¬Ｐ∧Ｑ∧Ｒ真值為1，其余7種指派均為F。（2）任意兩個小項的的合取式永假；m100∧ m010=（Ｐ∧¬Ｑ∧¬Ｒ）∧(¬Ｐ∧Ｑ∧¬Ｒ） ?Ｐ∧ (¬Ｐ∧Ｑ∧ ¬Ｑ∧ ¬Ｒ∧¬Ｒ ?T（3）全體小項的析取式為用真。,,定義：對給定的命題公式來講，僅含有小

44、項的析取的等價式稱為給定命題公式的主析取范式。即小項之“和”為主析取范式。定理：在真值表中，一個公式的真值為Ｔ的指派所對應(yīng)的小項的析取，即為此公式的主析取范式。定理：任意含n個命題變元的非永假式命題公式，其主析取式是唯一的。,,例：求出Ｐ→Ｑ、Ｐ∨¬Ｑ、 ¬（Ｐ∧Ｑ）、Ｐ∧¬Ｑ的主析取范式,Ｐ→Ｑ?（¬Ｐ∧ ¬Ｑ）∨（ ¬Ｐ∧Ｑ）∨（Ｐ∧Ｑ）Ｐ∨

45、 ¬Ｑ?（ ¬Ｐ∧ ¬Ｑ）∨（Ｐ∧ ¬Ｑ）∨（Ｐ∧Ｑ） ¬（Ｐ∧Ｑ）? （¬Ｐ∧¬Ｑ）∨（¬Ｐ∧Ｑ）∨（Ｐ∧¬Ｑ）Ｐ∧¬Ｑ?（Ｐ∧¬Ｑ）,,討論此定理：（1）只要命題公式不是永假式，則一定可以根據(jù)該命題公式的真值表直接寫出其主析取范式，其方法是找出該公式為“Ｔ”的行，對應(yīng)寫出小項的析取式，且一定是唯一的。（2）若命題

46、公式是含有n個變元的永真式，則它的主析取范式一定含有2n個極小項。（3）若二個命題公式對應(yīng)的主析取范式相同，則此二個命題公式一定是等價的。（4）命題公式的主析取范式中小項的個數(shù)一定等于對應(yīng)真值表中真值為“Ｔ”的個數(shù)。,,下面介紹不用真值表，直接求命題公式主析取范式的方法，分四步：（１）將命題公式化歸為與其等價的析取范式； （２）除去永假項，合并基本積中相同項（例：Ｐ∧Ｐ∧Ｑ?Ｐ∧Ｑ），變?yōu)樽詈單鋈》妒?。（３）利用添變元的方法?/p>

47、將所有析取范式變?yōu)樾№棥＠憾€變元Ｐ、Ｑ，利用“∧”對或“∨”的分配添項　?。?Ｐ∧（Ｑ∨¬Ｑ） ?（Ｐ∧Ｑ）∨（Ｐ∧¬Ｑ） Ｑ?Ｑ∧（Ｐ∨¬Ｐ） ?（Ｐ∧Ｑ）∨（¬Ｐ∧Ｑ）（４）合并相同的極小項變?yōu)橐豁棥?,例1：求（Ｐ∧（Ｐ→Ｑ））∨Ｑ的主析取范式解：原式?（Ｐ∧¬Ｐ）∨（Ｐ∧Ｑ）∨Ｑ

48、 ----（1）化為析取范式? （Ｐ∧Ｑ）∨Ｑ ----（2）消去永假項，變?yōu)樽詈單鋈》妒?（Ｐ∧Ｑ）∨（Ｑ∧（Ｐ∨¬Ｐ））?（Ｐ∧Ｑ）∨（Ｐ∧Ｑ）∨（¬Ｐ∧Ｑ） ----（3）添項?（Ｐ∧Ｑ）∨（¬Ｐ∧Ｑ）

49、 ----（4）合并相同最小項,,例2：證明Ｐ∨（¬Ｐ∧Ｑ）?Ｐ∨Ｑ 證明方法是寫出二個命題公式的主析范式，看其是否相同：（Ｑ∨¬Ｑ）∧Ｐ∨（¬Ｐ∧Ｑ） ?（Ｐ∧Ｑ）∨（Ｐ∧¬Ｑ）∨（¬Ｐ∧Ｑ）而Ｐ∨Ｑ ? （Ｐ∧（Ｑ∨¬Ｑ））∨（Ｑ∧（Ｐ∨¬Ｐ）） ?（Ｐ∧Ｑ）

50、∨（Ｐ∧¬Ｑ）∨（Ｐ∧Ｑ）∨（¬Ｐ∧Ｑ） ?（Ｐ∧Ｑ）∨（Ｐ∧¬Ｑ）∨（¬Ｐ∧Ｑ）主析范式相同，∴有Ｐ∨（¬Ｐ∧Ｑ） ?Ｐ∨Ｑ,,定義：在ｎ個命題變元的析取式中，若每個變元與其否定，并不同時存在，且二者之一出現(xiàn)一次且僅出現(xiàn)一次，則稱這種布爾析取或大項。Ｐ與¬Ｐ分別用0、1表示例：命題變元P和Q，其大項為： P ∨ Q， ¬P ∨ Q， P ∨ &#

51、172;Q， ¬P ∨ ¬Q對三個命題變元講Ｐ，Ｑ，Ｒ，其大項為：M000=Ｐ∨Ｑ∨Ｒ、 M001=Ｐ∨Ｑ∨ ¬Ｒ、 M010=Ｐ∨ ¬Ｑ∨Ｒ、M011=Ｐ∨ ¬Ｑ∨ ¬Ｒ、 M100= ¬Ｐ∨Ｑ∨Ｒ、 M101= ¬Ｐ∨Ｑ∨ ¬Ｒ、M110= ¬Ｐ∨ ¬Ｑ∨Ｒ、 M111= ¬Ｐ

52、∨ ¬Ｑ∨ ¬Ｒ推廣到一般：ｎ個命題變元構(gòu)成的不同大項有2n個（n∈I+）。使得每個大項為真的賦值僅有一個。,,定理：在真值表中，一個公式的真值為F的指派所對應(yīng)的大項的合取，即為此公式的主合取范式。在真值表中真值為“Ｆ”的個數(shù)等于主合取范式中大項的個數(shù)。定理：任意含有n個命題變元的非永真命題公式A，其主合取范式是唯一的。,,例：求出（Ｐ→Ｑ）、（Ｐ∨Ｑ）、¬（Ｐ∧Ｑ）、（Ｐ∧Ｑ）的主合取范式。

53、直接寫出其主合取范式： （Ｐ→Ｑ） ?（¬Ｐ∨Ｑ）（大項）（Ｐ∨Ｑ） ? （Ｐ∨Ｑ） ¬（Ｐ∧Ｑ） ?（ ¬Ｐ∨ ¬Ｑ）（Ｐ∧Ｑ） ? （Ｐ∨Ｑ）∧（Ｐ∨ ¬Ｑ）∧（ ¬Ｐ∨Ｑ）,,討論（１）與命題公式等價的主合范式中大項的個數(shù)等于其真值表中真值為“Ｆ”的個數(shù)。由真值表找大項的方法為：將表中值為“Ｆ”的對應(yīng)真值指派中，把變元寫成否定，把變元的否定寫成變元。（２）只

54、要命題公式不是永真式，則一定可以寫出對應(yīng)與其等價的唯一的主合取范式。３）若命題公式為含有ｎ個變元的永假式，則主合取范式包含了2n個大項的合取式。（４）可用主合取范式判定二個命題公式是否等價。,,５）已知一個命題公式的主析取范式，則一定可以直接寫出與其等價的主合取范式來。反之也行。例：Ｐ∨ ¬Ｑ ?（ ¬Ｐ∧ ¬Ｑ）∨（Ｐ∧¬Ｑ）∨（Ｐ∧Ｑ）

55、 ……主析范式 ?¬ （ ¬Ｐ∧Ｑ）?Ｐ∨ ¬Ｑ……主合取范式（６）對應(yīng)于有ｎ個變元的命題公式，則一定有：主析范式極小項數(shù)＋主合范式極大項數(shù)＝　2n,,下面介紹不用真值表求一命題公式主合取范式的方法：（1）化為與命題公式等價的合取范式；（2）除去真值為“T”的析取項和除去析取項中相同變元且只保留一個，變?yōu)樽詈喓先∈剑?/p>

56、（3）添項，使析取項均變?yōu)闃O大項；例如：Ｐ、Ｑ為二個變元，即：Ｐ?Ｐ∨（Ｑ∧?Ｑ） ? （Ｐ∨Ｑ）∧（Ｐ∨ ?Ｑ）（4）合并相同的極大項，保留一項。例：求Ｐ∧（Ｐ→Ｑ）∨Ｑ的主合取范式 解：原式 ?Ｐ∧（¬Ｐ∨Ｑ）∨Ｑ　　　　　?（Ｐ∧Ｑ）∨Ｑ　　　　　?（Ｐ∨Ｑ） ∧Ｑ　　　　　? （Ｐ∨Ｑ）∧（ ?Ｐ∨Ｑ）,,根據(jù)小項與大項的剛好相反的編碼規(guī)則，主析取式與主合取式可以寫成統(tǒng)一

57、的編碼：（Ｐ∧（Ｐ→Ｑ））∨Ｑ?（Ｐ∧Ｑ）∨（¬Ｐ∧Ｑ）（主析取式）=m11 ∨m01=∑（1，3）?（Ｐ∨Ｑ）∧ （¬Ｐ∧Ｑ）（主合取式）=M 00∧M10 =∏（0，2）¬（Ｐ∧Ｑ）? （¬Ｐ∧¬Ｑ）∨（¬Ｐ∧Ｑ）∨（Ｐ∧¬Ｑ）（主析取式）= m00 ∨m01 ∨m10 =∑（0，1，2） ?（ ¬Ｐ∨ ¬Ｑ）

58、 （主合取式）= m11 = ∏（3）,m，M的小標為二進制，而∑， ∏的小標為對應(yīng)的十進制,,已知A主析取式范式，如何求主合取式范式？求出A的主析取式中為包含小項的小標。把1的求出的小標寫成與之相反的對應(yīng)大項。把2中寫成的大項合取，幾位A的主合式范式。,1.6.推理理論,按公認的推論規(guī)則，從前提集合中推導(dǎo)出一個結(jié)論來，這樣的推導(dǎo)過程稱為演繹，或者叫形式證明。在任何論證中，若認定前提是真的，且從前提集合推導(dǎo)出結(jié)論的論

59、證是遵守了邏輯規(guī)則的，則我們稱此結(jié)論是合法的。根據(jù)邏輯規(guī)則推導(dǎo)出來的任何結(jié)論稱為有效結(jié)論。推論規(guī)則就是指確定論證的有效性的判據(jù)，常是用命題形式表示這些規(guī)則，而不涉及實際命題和它的真值。,,本節(jié)介紹的證明方法，歸納分成三類：（一）真值表技術(shù)；（二）主范式方法及等值演算法；（三）構(gòu)造論證。 真值表技術(shù)的主要依據(jù)是“→”的真值表定義。若Ｐ?Ｑ當(dāng)且僅當(dāng)（Ｐ→Ｑ）為永真式。,1.6.1真值表技術(shù),定義：設(shè)H1，H2,…Hm,Ｃ都是

60、命題公式，當(dāng)且僅當(dāng)H1 ∧ H2 ∧ … ∧ Hm ?Ｃ，才可以說Ｃ是前提集合｛ H1，H2,…Hm ｝的有效結(jié)論。從給定真值表常用的判斷方法有二種： （１）檢查真值表中H1，H2,…Hm全部為“Ｔ”的所有行，看結(jié)論Ｃ是否也均為“Ｔ”，若Ｃ均為“Ｔ”，則結(jié)論有效。否則結(jié)論無效。（２）看結(jié)論Ｃ為“Ｆ”的所有行，檢查每行前提H1，H2,…Hm中是否至少有一個為Ｆ，若有“Ｆ”，則結(jié)論有效；若有均為“Ｔ”的行，則結(jié)論無效。,,例：試證明

61、下列結(jié)論是否有效，畫出真值表：,由真值表可見：（１）Ｐ，Ｐ→Ｑ?Ｑ　　　　　　　　　　 有效（２）Ｐ→Ｑ，?Ｐ?Ｑ　　　　　　 　　　無效（３）Ｐ→Ｑ， ? （Ｐ∧Ｑ） ? ?Ｐ 　　 　有效（４） ?Ｐ，Ｐ?Ｑ? ? （Ｐ∧Ｑ）　 　　　有效（５）Ｐ→Ｑ，Ｑ?Ｐ　　 　　　　　 　無效,,例：H1：如果大連是一個大城市，則大寨是一個鄉(xiāng)村； Ｐ→Ｑ　 H2：大寨是一個鄉(xiāng)村

62、；　?。选。茫捍筮B是一個大城市；　?。袆t：Ｐ→Ｑ，Ｑ?Ｐ 無效或者稱：Ｐ不能從前提集合中推導(dǎo)出來。,1.6.2主范式方法及等值演算法,表1.6.2及表1.6.3是常用的等值公式及蘊含公式在推理過程中，如果命題變元較多，會多次使用表1.6.2及表1.6.3。每一個推理過程就是一系列命題公式序列，其中命題公式或者是已知的前提，或者是由某些前提應(yīng)用推理規(guī)則得到的結(jié)論。常用的推理規(guī)則有：P規(guī)則：在推導(dǎo)的任何步驟上都可以引入前提（條

63、件）T規(guī)則（1）在證明的任何步驟上，所證明的結(jié)論都可以作為后續(xù)證明的前提。 （2）等價的命題公式置換。,,例2 證明： (P∨Q),(P ?R),(Q ?S)?S∨R 步驟 推理過程 規(guī)則 根據(jù) (1) (P∨Q) P (2) ? P ?Q T(1) E16 (3)

64、 Q ?S P (4) ? P ?S T(2)(3) I6 (5) ? S ?P T(4) E18 (6) P ?R P (7) ? S ?R T(6) I6 (8) S∨R T(7)

65、 E16,1.6.3間接證明（反證法，歸謬法）,定義：由一組前提H1，H2，…，Hn，利用一些公認的推理，根據(jù)已知的等價或蘊含公式推演得到的一個結(jié)論，級命題公式C，記作： H1 ∧ H2 ∧ …∧ Hn┣C定理：推理H1 ∧ H2 ∧ …∧ Hn┣C為有效推理的充分必要條件是H1 ∧ H2 ∧ …∧ Hn ? C為永真式。定義：設(shè)H1 ， H2 ，…， Hn 是可滿足式。則稱H1 ， H2 ，…， Hn 是相容的，

66、若H1 ， H2 ，…， Hn 是永假式稱H1 ， H2 ，…， Hn 是不相容的定理：若H1 ∧ H2 ∧ …∧ Hn ? ? C為永假式，則H1 ∧ H2 ∧ …∧ Hn┣C成立,,例:證明: R?¬Q, R∨S , S?¬Q, P?Q ? ¬P (1) ¬ (¬P) 假設(shè)前提 (2) P T(1)

67、 (3) P?Q P (4) Q T(2)(3) (5) S?¬Q P (6) Q?¬S T(5) (7) ¬S T(4)(6) (8) R∨S P (9) R T(7)(8)

68、 (10) R?¬Q P (11) ¬Q T(9)(10) (12)Q ∧ ¬Q T(4)(11),,CP規(guī)則：如果能從Q和給定的前提集合P中推導(dǎo)出R來，則就能從前提集合中推導(dǎo)出（Q ? R）來。即: (P∧Q?R)則：P ? (Q?R)例2: P?Q ? P?(P ∧Q) (1) P

69、 附加前提 (2) P?Q P (3) Q T(1)(2) I (4) P ∧Q T(1)(3) (5) P?(P ∧Q) CP,,例：一位計算機工作者協(xié)助公安人員審查一起謀殺案，經(jīng)調(diào)查，他認為下列情況均是真的。 （1）會計張某或鄰居王某謀害了廠長。 （2）

70、如果會計張某謀害了廠長，則謀害不可能發(fā)生在半夜。 （3）如果鄰居王某的證詞不正確，則在半夜時房里燈光未滅。 （4）如果鄰居王某的證詞是正確的，則謀害發(fā)生在半夜。 （5）在半夜房子里的燈光滅了，且會計張某曾貪污過。解：設(shè) P：會計張某謀害了廠長 Q：鄰居王某謀害了廠長 N：謀害發(fā)生在半夜 O：鄰居王某的證詞是正確的 R：半夜時房子的

71、燈光滅了 A：會計張某曾貪污過,,列出條件公式： (1) P∨Q (4) O?N (2) P?¬N (5) R?A (3) ¬O? ¬ R推導(dǎo)過程為： (1) R?A P (6) N T

72、(2) R T (7) P?¬N P(3) ¬O? ¬R P (8) ¬P T(4) O T (9) P∨Q P(5) O? N P (10) Q T結(jié)論：鄰居王

73、某謀害了廠長；,,作業(yè)P261 a、c、d4 b,,學(xué)習(xí)第一章要注意以下幾點：（1）弄清命題與陳述句的關(guān)系。（2）弄清由5種基本聯(lián)結(jié)詞聯(lián)結(jié)的復(fù)合命題的邏輯關(guān)系及其真值。特別是要弄清蘊含式”P?Q“的邏輯關(guān)系及其真值。（3）記住常用的蘊含式和等價式，這是學(xué)好命題邏輯的關(guān)鍵問題。（4）會準確地求出給定公式的主析取范式和主合取范式。掌握主析取范式與真值表、成真賦值、主合取范式的關(guān)系。（5）會用多種方法判斷公式的類型及判斷兩個公