1、離散數(shù)學,第一章 命題演算,主要內(nèi)容 1.1命題概念 1.2復合命題與聯(lián)結詞 1.3命題公式與真值表 1.4等價變換與蘊含式 1.5最小聯(lián)結詞組與范式 1.6推理理論,1.1 命題概念,命題：具有唯一真值的陳述句 命題的真值：判斷的結果 真值的取值：真與假 注意： （1）命題可以為真，也可以為假，但是不能同時為真又為假 （2）感嘆句、祈使句、疑問句都不是命題,1.1 命題概念,例1 判斷下列句子中哪些構成命題 (1) 8是偶數(shù). (2)雪是黑色的. (3) 明年國慶節(jié)是個晴天. (4)3+89. (5)我是大學生. (6) 火星上有生物. (7) 星期五下午有會嗎？ (8) 請勿吸煙！ (9)

2、 這束花多么好看??！ (10) x+y5.,注意： 一個陳述句的真假暫時不能唯一的確 定，但總有一天可以唯一確定，與一 個陳述句真假不能唯一確定是兩件事,1.1 命題概念,命題的表示 我們將使用大寫字母A,B,P,Q,或用帶下標的大寫字母，或用數(shù)字，如Ak，20等表示命題。 將表示命題的符號放在該命題的前面，稱為命題符號化。例如， P： 8是偶數(shù). 24:雪是黑色的. 表示命題的符號稱為命題標識符。P和24就是標識符。,1.1 命題概念,命題常量與命題變量 命題標識符表示 注意：（1）命題變元不是命題，它可以表示任何命題。 （2）在例1中(10) x+y5不是命題，但給定x與y確定的值后，它的

3、真值也就定下來了。 （3）當命題變元P用一特定命題去代替，此時P可以確定真值，這也稱作對P的指派。,確定的命題,命題常量,命題的位置,命題變元,1.1 命題概念,在數(shù)理邏輯中，將命題的真值也符號化了。一般用“T”（或“1”）表示“真”；用“F”（或“0”）表示“假”。 例如， 令p： 是有理數(shù)，則p 的真值為F（或0)， q：2 + 5 = 7，則q 的真值為T（或1）,1.1 命題概念,練習： 1.下列句子為命題的是（ ） A.全體起立！ B. X=0 C. 我在說謊 D.張三生于1886年的春天 2.下列句子不是命題的是（ ） A.中華人民共和國的首都是北京 B.張三是學生 C.雪是黑色的

4、 D.太好了！,D,D,1.1 命題概念,練習： 課本P6 第1題,1.2 復合命題與聯(lián)結詞,命題分類：原子命題和復合命題 原子命題：不能再分解的命題 復合命題：由一些原子命題，經(jīng)過一些聯(lián)結詞復合而成的命題 例如： 王平既聰明又用功。 也可以表達為：王平聰明并且王平用功。 練習：P6 第4題,1.2 復合命題與聯(lián)結詞,常用的聯(lián)結詞 （1）否定 定義1.2.1 設P為一命題，P的否定是一個新的命題，記作P。 “”表示命題的否定. 例1 P:他是大學生； P：他不是大學生 P的真值： 若P為T， P為F；若P為F， P為T,1.2 復合命題與聯(lián)結詞,常用的聯(lián)結詞 （2）合取 定義1.2.2 兩個命

5、題P和Q的合取是一個復合命題，記作PQ。 稱作合取聯(lián)結詞， 在自然語言中的“并且”、“和”、“既.又.”、“不僅.而且.”、“雖然.但是.”等都可以符號化為 例1 2是素數(shù)和偶數(shù) 設P：2是素數(shù)，Q:2是偶數(shù)，故上述命題可表述為PQ 例2 王乙工作努力且身體好。 設P:王乙工作努力，Q:王乙身體好，故上述命題可表述為PQ,1.2 復合命題與聯(lián)結詞,常用的聯(lián)結詞 （2）合取 注意：聯(lián)結詞 只與定義的真值有關，而與命題的實際語義無關。 例3 設P:王乙工作努力； Q:教室里有20張書桌。 PQ：王乙工作努力且教室里有20張書桌。 在自然語言中，上述PQ是沒有意義的，因為P與Q之間沒有內(nèi)在聯(lián)系，但作

6、為命題邏輯，復合命題仍可根據(jù)P與Q的取值情況，確定真值。,1.2 復合命題與聯(lián)結詞,常用的聯(lián)結詞 （2）合取 PQ的真值 當且僅當P與Q同時為T時，PQ為T.其余情況，PQ為F,1.2 復合命題與聯(lián)結詞,常用的聯(lián)結詞 （2）合取 注意: 命題聯(lián)結詞“合取”可將兩個互為否定的命題聯(lián)結在一起：PP 此時其真值永為F,1.2 復合命題與聯(lián)結詞,常用的聯(lián)結詞 （2）合取 將下列命題符號化. (1) 吳穎既用功又聰明. (2) 吳穎不僅用功而且聰明. (3) 吳穎雖然聰明，但不用功. (4) 張輝與王麗都是三好生.,1.2 復合命題與聯(lián)結詞,常用的聯(lián)結詞 （2）合取 解: 令p:吳穎用功, q:吳穎聰明

7、 (1) pq (2) pq (3) pq (4) 設p:張輝是三好生, q:王麗是三好生 pq,1.2 復合命題與聯(lián)結詞,常用的聯(lián)結詞 （3）析取 定義1.2.3 兩個命題P, Q的析取是個復合命題，記作PQ。 稱作析取聯(lián)結詞， 與自然語言中的“或”有些相似 例4 王強是這次校運動會的跳高或100米短跑的冠軍。 設P: 王強是這次校運動會的跳高冠軍； Q:王強是這次校運動會的100米短跑的冠軍。 所以本例可描述為： PQ,1.2 復合命題與聯(lián)結詞,常用的聯(lián)結詞 （3）析取 注意：在自然語言中的“或”具有二義性，有時表示的是可兼或，有時表示的是不可兼或。 例5 明天下午我乘14次列車或22次列

8、車去北京。 設P: 明天下午我乘14次列車去北京； Q:明天下午我乘22次列車去北京。 本例中不能用PQ去描述這個命題。因為明天下午我乘14次列車去北京，就不可能乘22次列車去北京。如果明天下午我乘22次列車去北京，就不可能乘14次列車去北京。,1.2 復合命題與聯(lián)結詞,常用的聯(lián)結詞 （3）析取 PQ的真值 當且僅當P與Q同時為F時，PQ為F.否則，PQ為T,1.2 復合命題與聯(lián)結詞,常用的聯(lián)結詞 （3）析取 將下列命題符號化,(1)-(3)判斷其真值 (1) 2 或4 是素數(shù). (2) 2 或3 是素數(shù). (3) 4 或6 是素數(shù). (4) 小元元只能拿一個蘋果或一個梨.,1.2 復合命題與

9、聯(lián)結詞,常用的聯(lián)結詞 （3）析取 解: (1) 令p:2是素數(shù), q:4是素數(shù), pq，因為p為T，q為F，pq的真值為T (2) 令p:2是素數(shù), q:3是素數(shù), pq，因為p為T，q為T，pq的真值為T (3) 令p:4是素數(shù), q:6是素數(shù), pq，因為p為F，q為F，pq的真值為F (4) 令p:小元元拿一個蘋果, q:小元元拿一個梨 (pq)(pq),1.2 復合命題與聯(lián)結詞,常用的聯(lián)結詞 （4）條件 定義1.2.4 給定兩個命題P, Q，其條件命題是一個復合命題，記作PQ。 其中P為前件，Q為后件。PQ讀作“如果P那么Q”，“若P則Q” 例6 如果我有就學機會，那么我必用功讀書。

10、設P: 我有就學機會； Q:我必用功讀書。 所以本例可描述為： PQ,1.2 復合命題與聯(lián)結詞,常用的聯(lián)結詞 （4）條件 例 只要天不下雨，我就騎車上班。 設S: 天下雨； R:我騎車上班。 所以本例可描述為： SR 如果我不騎車上班，則天下雨。 R S,1.2 復合命題與聯(lián)結詞,常用的聯(lián)結詞 （4）條件 例 設p：天下雨，q：我就騎自行車上班，將下列命題符號化 (1) 只要不下雨，我就騎自行車上班 pq (2) 除非下雨，否則我就騎自行車上班. pq (3) 我如果不騎自行車上班，那么天下雨. qp,1.2 復合命題與聯(lián)結詞,常用的聯(lián)結詞 （4）條件 注意：聯(lián)結詞 只與定義的真值有關，而與命

11、題的實際語義無關。 例： 如果雪是黑的，則房間里有20張桌子。 設P:雪是黑的 Q:房間里有20張桌子 所以本例可描述為： PQ,1.2 復合命題與聯(lián)結詞,常用的聯(lián)結詞 （4）條件 PQ的真值 當且僅當P的真值為T，Q的真值為F時，PQ 為F.其余情況，PQ為T,1.2 復合命題與聯(lián)結詞,常用的聯(lián)結詞 （4）條件 PQ的真值 判斷命題的真值： 如果雪是黑的，則房間里有20張桌子。 注意：當P為F時，PQ恒為T，稱為“善意推定”,1.2 復合命題與聯(lián)結詞,常用的聯(lián)結詞 （5）雙條件 定義1.2.6 給定兩個命題P, Q，其復合命題PQ稱作雙條件命題，讀作P當且僅當Q。 例 兩個三角形全等，當且僅

12、當它們的三組對應邊相等。 設P: 兩個三角形全等； Q:它們的三組對應邊相等。 所以本例可描述為： PQ,1.2 復合命題與聯(lián)結詞,常用的聯(lián)結詞 （5）雙條件 例 3大于6，當且僅當2不是質(zhì)數(shù)。 設P: 3大于6； Q:2不是質(zhì)數(shù)。 所以本例可描述為： PQ,1.2 復合命題與聯(lián)結詞,常用的聯(lián)結詞 （5）雙條件 PQ 的真值 當P與Q的真值為相同時，PQ 為T.其余情況，PQ 為F,1.2 復合命題與聯(lián)結詞,常用的聯(lián)結詞 （5）雙條件 PQ 的真值 將下列命題符號化并判斷真值： (1) 3大于6，當且僅當2不是質(zhì)數(shù)。 (2) 2 + 2 4 當且僅當3 + 3 6. (3) 2 + 2 4 當

13、且僅當3 是偶數(shù). (4) 2 + 2 4 當且僅當太陽從東方升起. (5) 2 + 2 4 當且僅當美國位于非洲.,1.2 復合命題與聯(lián)結詞,常用的聯(lián)結詞 總結： （1）復合命題的真值只取決于構成它們的各原子命題的真值，而與它們內(nèi)容含義無關，對聯(lián)結詞所聯(lián)結的兩原子命題之間有無關系無關。 （2），具有對稱性，無對稱性,1.2 復合命題與聯(lián)結詞,常用的聯(lián)結詞 練習,1.2 復合命題與聯(lián)結詞,常用的聯(lián)結詞 練習： 課本P6 第3題,1.3 命題公式與真值表,命題公式 定義1.3.1 命題演算的合式公式規(guī)定為： (1) 單個命題變元本身是一個合式公式。 (2) 若A是合式公式，則(A)也是合式公式。

14、 (3) 若A, B是合式公式，則(AB), (AB), (AB), (AB)也是合式公式。 (4) 當且僅當有限次地應用(1)(3) 所得到的包含命題變元，聯(lián)結詞和圓括號的符號串是合式公式。 合式公式也稱作命題公式或簡稱公式。 (AB), (AB)等外層括號可以略去。 聯(lián)結詞優(yōu)先次序：，,1.3 命題公式與真值表,命題公式 定義1.3.1 命題演算的合式公式規(guī)定為： (1) 單個命題變元本身是一個合式公式。 (2) 若A是合式公式，則(A)也是合式公式。 (3) 若A, B是合式公式，則(AB), (AB), (AB), (AB)也是合式公式。 (4) 當且僅當有限次地應用(1)(3) 所得

15、到的包含命題變元，聯(lián)結詞和圓括號的符號串是合式公式。 練習 P10 第1，2題,1.3 命題公式與真值表,命題公式 定義1.3.2 設 Ai是公式A的一部分，且Ai是一個合式公式，稱Ai是A 的子公 式。 例 ： A：（PQ）(R(PQ), A1 :（PQ）, A2:R(PQ),則 A1 , A2 分別是A的子公式。,1.3 命題公式與真值表,真值表 定義1.3.3 設P為一命題公式，P1 , P2, P3,.Pn 為出現(xiàn)在P中的所有命題變元， 對 P1 , P2, P3,.Pn 指定一組真值稱為對P的一種指派。若指定的一種指派，使P的值為真，則稱這組值為成真指派；若指定的一種指派，使P的值為

16、假，則稱這組值為成假指派。 練習：P11 第3題,1.3 命題公式與真值表,真值表 將命題公式P在所有指派下取值情況，列成表，稱為P的真值表。 真值表中，真值T，F(xiàn)可分別用1，0代替。 例： 構造 P Q 的真值表。,1.3 命題公式與真值表,真值表 練習 （1） 給出PQ的真值表。 （2） 給出PQ的真值表 （3）給出 (PQ) ( P Q) 的真值表。 比較 P Q與PQ的真值表，比較PQ與(PQ) ( P Q)的真值表 （4） 給出P(QR)的真值表。,1.3 命題公式與真值表,等價式 定義1.3.4 給定兩個命題公式A和B，設P1 , P2, P3,.Pn為所有出現(xiàn)于A和B中的原子變元

17、，若給P1 , P2, P3,.Pn任一組真值指派，A和B的真值都相同，稱A和B是等價的，記作AB。 從上述真值表的例子中，可以知道： P Q PQ (PQ) ( P Q)PQ 上述二式以后經(jīng)常作為等值公式直接應用。,1.3 命題公式與真值表,定義1.3.5 設A為一命題公式，若A在它的各種指派情況下，其取值均為真, 則稱公式A為重言式或永真式。 定義1.3.6 設A為一命題公式，若A在它的各種指派情況下，其取值均為假, 則稱公式A為矛盾式或永假式。 定義1.3.7 設A為一命題公式，若A在它的各種真值指派下至少存在一組成真指派，則稱A是可滿足式。,1.3 命題公式與真值表,例：用真值表證明(

18、PQ)(PQ)是永真式。,1.3 命題公式與真值表,例：用真值表證明(PQ)Q是永假式。,1.3 命題公式與真值表,對合律 PP 冪等律 PPP, PPP 結合律 (PQ)RP(QR), (PQ)RP(QR) 交換律 PQQP, PQQP 分配律 P(QR)(PQ)(PR), P(QR)(PQ)(PR),1.3 命題公式與真值表,吸收律 P(PQ)P, P(PQ)P 德摩根律 (PQ)PQ, (PQ)PQ 同一律 PFP , PTP 零律 PTT, PFF 否定律 P PT, PPF,兩個等值公式： P Q PQ (PQ) ( P Q)PQ,1.3 命題公式與真值表,練習 P11 第4，5題,

19、1.4 等價變換與蘊含式,等價變換 定理1.4.1 設 X 是合式公式 A 的子公式，若有Y也是一個合式公式，且XY，如果將A中的X用Y置換， 得到公式B,則 AB。 例：證明Q(P(PQ)QP 證：設A：Q(P(PQ)， 因為P(PQ)P（吸收律） 故B:QP，即AB,1.4 等價變換與蘊含式,等價變換 例：驗證下列等值式：P(QR)(PQ)R。,1.4 等價變換與蘊含式,練習 P14 第2題,1.4 等價變換與蘊含式,等價變換 判斷命題公式是重言式或矛盾式 例：驗證Q(PQ)P)是重言式。 證：Q(PQ)P)Q(PP)(QP) （分配律） Q(F(QP) (否定律) Q(QP) （同一律）

20、 Q(QP) （德摩根律） (QQ)P （結合律） TP (否定律) T （零律）,真值表,等價變換,1.4 等價變換與蘊含式,等價變換 判斷命題公式是重言式或矛盾式 例：驗證(PP)(QQ)R)是矛盾式。,真值表,等值演算,1.4 等價變換與蘊含式,練習 P14 第1題,1.5 最小聯(lián)結詞組與范式,最小聯(lián)結詞組 （1）由PQ(PQ)(QP)，故可把包含的公式等價變換為包含“”和“”的公式。 （2）由PQPQ，故可把包含的公式等價變換為包含“”和“”的公式。 （3）由PQ(PQ)，PQ(PQ)說明“”與“”可以相互交換。 故由“”“”“”“”“”這5個聯(lián)結詞中若干個組成的命題公式，必可由,或,

21、組成的命題公式所替代。 我們把,及,稱為命題公式的最小聯(lián)結詞組。,1.5 最小聯(lián)結詞組與范式,練習 P20 第1，2題,1.5 最小聯(lián)結詞組與范式,范式 定義1.5.1 一個命題公式稱為合取范式，當且僅當它具有形式 A1 A2.An （n1） 其中A1 ，A2，.，An 都是由命題變元以其否定組成的析取式。 例如：（PQ）（PR）（PQ）是一個合取范式,1.5 最小聯(lián)結詞組與范式,范式 定義1.5.2 一個命題公式稱為析取范式，當且僅當它具有形式 A1 A2.An （n1） 其中A1 ，A2，.，An 都是由命題變元以其否定組成的合取式。 例如：（PQ）（PR）（PQ）是一個析取范式,1.5

22、最小聯(lián)結詞組與范式,范式 例1: 求（P（QR）S的合取范式 解：（P（QR）S（P（QR）S （P（QR）S P（QR）S P（QR）S （PS）（QR） （PSQ）（PSR）,1.5 最小聯(lián)結詞組與范式,練習 P21 第3題,1.5 最小聯(lián)結詞組與范式,范式 一個命題公式的合取范式或析取范式不是唯一的。 例：P(QR) (PQ)(PR) (PP)(PR)(QP)(QR),1.5 最小聯(lián)結詞組與范式,主范式 定義1.5.3 n個命題變元的合取式，稱作布爾合取或小項，其中每個變元與它的否定不能同時存在，但兩者必須出現(xiàn)僅且出現(xiàn)一次。 例如：2個命題變元P和Q，其小項為： PQ, PQ, PQ,

23、PQ 3個命題變元P，Q和R，其小項為： PQR, PQR, PQR, PQR, PQR, PQR, PQR, PQR,1.5 最小聯(lián)結詞組與范式,小項的表示 一般來說，n個命題變元有2n個小項，n個命題變元的小項，將命題變元看成1，其否定看成0，則每個小項對應著一個二進制數(shù)。 例： m000= PQR m001=PQR m010=PQR m011=PQR m100=PQR m101=PQR m110=PQR m111=PQR,1.5 最小聯(lián)結詞組與范式,主范式 觀察表1.5.1 小項的性質(zhì)： （1）每個小項對應著一個編碼。當編碼與其真實指派相同時，該小項的真值為T，在其余的指派下為F。 （2

24、）任意兩個不同小項的合取式永假。 （3）全體小項的析取式為永真。,1.5 最小聯(lián)結詞組與范式,主范式 定義1.5.4 對于給定的命題公式，如果有一個等價公式，它僅由小項的析取所組成，則該等價式稱作原式的主析取范式。 定理1.5.1 在真值表中，一個公式的真值為T的指派所對應的小項的析取，即為此公式主析取范式。 定理1.5.2 任意含n個命題變元的非永假命題公式，其主析取范式是唯一的。,1.5 最小聯(lián)結詞組與范式,主范式 例： 用真值表法，寫出下列公式： A：（pq）（qp）的主析取范式。 其真值為1的小項有m00，m01，m10，即（pq），（pq），（pq） 故原式可寫成主析取范式為A：（p

25、q）（pq）（pq）,1.5 最小聯(lián)結詞組與范式,主范式 例： 用等值演算法，寫出下列公式： A：（pq）（qp）的主析取范式。 （pq）（qp）（pq）（qp） （pq）（qp） （pq）qppq （1q)(p1)（(pp)q)(p(qq) （pq）（pq）（pq）（pq） （pq）（pq）（pq）=m00m01m10 對主析取范式，根據(jù)小項的對應編碼，可以寫成統(tǒng)一編碼形式，,1.5 最小聯(lián)結詞組與范式,練習 P21 先求析取范式 4.（a）（c）,1.5 最小聯(lián)結詞組與范式,主范式 定義1.5.5 n個命題變元的析取式，稱作布爾析取或大項，其中每個變元與它的否定不能同時存在，但兩者必須出現(xiàn)

26、僅且出現(xiàn)一次。 例如：2個命題變元P和Q，其大項為： PQ, PQ, PQ, PQ 3個命題變元P，Q和R，其大項為： PQR, PQR, PQR, PQR, PQR, PQR, PQR, PQR,1.5 最小聯(lián)結詞組與范式,大項的表示 與小項情況類似，每個大項也可以編碼。具體方法：首先將n個命題變元排序，將每個命題變元對應成0，其否定對應成1，則可將2n個大項按二進制數(shù)編碼，記為Mi，其下標是由二進制化為十進制數(shù)。 例： 2個命題變元P,Q的命題公式，應有4個大項： PQ=M00=M0 PQ=M01=M1, PQ=M10=M2, PQ=M11=M3,1.5 最小聯(lián)結詞組與范式,主范式 定理1

27、.5.3 在真值表中一個公式的真值為F的指派所對應的大項的合取，即為此公式主合取范式。 定理1.5.2 任意含n個命題變元的非永真命題公式A，其主合取范式是唯一的。,1.5 最小聯(lián)結詞組與范式,主范式 例：用真值表法，求pqr的主合取范式。 其真值為0的大項有M000，M010，M100，故原式可寫成主合取范式為M000M010M100 =,1.5 最小聯(lián)結詞組與范式,主范式 例：用等值演算法，求pqr的主合取范式。 解：pqr（pq）r（pr）（qr） （p1r）（1qr） （p(qq)r）（(pp)qr） (pqr)(pqr)(pqr)(pqr) (pqr)(pqr)(pqr) M000M

28、010M100 M0M2M4 與主析取范式一樣，公式可統(tǒng)一表示為：,1.5 最小聯(lián)結詞組與范式,主范式 例：用真值表法，求pqr的主析取范式。 其真值為1的小項有m001，m011，m101，m110，m111 故原式可寫成主析取范式為m001m011m101m110m111=,1.5 最小聯(lián)結詞組與范式,主范式 從A的主析取范式求主合取范式步驟： （1）求出A的主析取范式中為包含小項的下標 （2）把（1）中求出的下標寫成對應大項。 （3）做（2）中寫成的大項合取，即為A的主合取范式。,1.5 最小聯(lián)結詞組與范式,主范式 例：公式A：（pq）（qp） ，則公式A的主合取范式為 例：（PQ）Q

29、=m01m11 （PQ）Q =M00M10,1.5 最小聯(lián)結詞組與范式,練習 P21 第5,6題,1.5 最小聯(lián)結詞組與范式,主范式 根據(jù)主范式的定義和定理,可以判定含n個命題變元的公式: （1）若A可化為與其等價的,含2n個小項的主析取范式,則A為永真式. （2）若A可化為與其等價的,含2n個大項的主合取范式,則A為永假式. （3）若A的主析取范式不含2n個小項,或A的主合取范式不含2n個大項,則A為可滿足式. 判斷公式類型： 1，真值表 2.等值演算 3.主范式,1.5 最小聯(lián)結詞組與范式,練習 P21 第4題 （a）（b）（c）,1.5 最小聯(lián)結詞組與范式,1.5 最小聯(lián)結詞組與范式,1

30、.5 最小聯(lián)結詞組與范式,1.5 最小聯(lián)結詞組與范式,1.5 最小聯(lián)結詞組與范式,1.5 最小聯(lián)結詞組與范式,1.5 最小聯(lián)結詞組與范式,1.4 等價變換與蘊含式,蘊含式 定理1.4.2 設A,B為兩命題公式，AB，當且僅當AB為一個重言式。 定義1.4.1 當且僅當PQ是一個重言式時，我們稱“P蘊含Q”，并記作P Q。 P Q稱作P蘊含Q或蘊含式，亦稱作永真條件式。 蘊含式有下列性質(zhì)： (1)對任意公式A,有A A； (2)對任意公式A,B和C，若A B,B C,則A C; (3)對任意公式A,B和C，若A B,A C,則A (BC) ; (4)對任意公式A,B和C，若A C,B C,則AB

31、 C。,1.4 等價變換與蘊含式,蘊含式 定理1.4.3 設P,Q為任意兩個命題公式，PQ的充分必要條件是P Q,Q P. 要證明蘊含式P Q ，除了用真值表證明PQ是重言式外，另有兩種辦法： (1)對 PQ的前件P指定真值為T，若推出Q的真值亦為T，則PQ是重言式。 （因為對于PQ，除了P的真值取F外，其余情況PQ的真值都為T） (2)證明假定后件Q的真值取F（Q為T），由此推出P的真值為F（P為T）。 （因為（PQ）（QP），所以只需證QP是重言式）,1.4 等價變換與蘊含式,蘊含式 例: 推證Q（PQ） P. 證法1：假定Q（PQ）為T， 則Q為T，且PQ為T。 由Q為F，PQ為T。 則

32、必須P為F，故P為T 證法2：假定 P為F，則P為T。 a)若Q為F，則PQ為F, Q（PQ）為F。 b)若Q為T，則Q為F, Q（PQ）為F。,1.4 等價變換與蘊含式,蘊含式 （1）化簡式 PQ P. PQ Q （3）附加式 P PQ （4）變形附加式 P PQ，Q PQ （5）變形簡化式 （PQ） P;（PQ） Q （6）假言推論 P（PQ） Q （7）拒取式 Q（PQ） P （8）析取三段論 P(PQ) Q （9）條件三段論 （PQ）(QR) PR （10）雙條件三段論 （PQ）（QR） PR （11）合取構造二難 （PQ）（RS）（PR） QS （12）析取構造二難 （PQ）（RS）

33、（PR） QS （13）前后件附加 PQ （PR）（QR）; PQ （PR）（QR）,1.4 等價變換與蘊含式,練習 P14 第5題,1.6 推理理論,有效推理：從前提出發(fā)，根據(jù)確認的推理規(guī)則推導出一個結論，這個過程叫有效推理。 定義1.6.1 設H1，H2，.，Hn，C是命題公式，當且僅當H1H2.Hn C，稱C是一組前提的有效結論。,1.6 推理理論,判別有效結論的方法： （1）真值表法 例：如果張老師來了，這個問題可以得到解答；如果李老師來了，這個問題也可以得到解答，總之只要張老師或李老師來了，這個問題就可以得到解答。 解：設 P:張老師來了 Q：李老師來了 R:這個問題得到解答 (PR

34、)(QR)(PQ) R,1.6 推理理論,判別有效結論的方法： （1）真值表法 (PR)(QR)(PQ) R,1.6 推理理論,判別有效結論的方法： （2）主范式方法及等值演算法 例：如果我上街，我必去新華書店；我沒有上街，所以我沒去新華書店。 解：設 P:我上街 Q：我去新華書店 （(PQ)P） Q需證成立，即需證明 （(PQ)P）Q為永真式。,1.6 推理理論,判別有效結論的方法： （2）主范式方法及等值演算法 例：如果我上街，我必去新華書店；我沒有上街，所以我沒去新華書店。 解：（(PQ)P）Q（(PQ)P）Q （(PQ)P）Q （(PQ)P）Q PQM01=m00m10m11 不是重言

35、式，故（(PQ)P） Q不成立，即Q不是(PQ)P的有效推理。,1.6 推理理論,判別有效結論的方法： （3）構造論證法 在推理過程中，如果命題變元很多，用真值表、等值演算法及主范式法等作推理證明都很不方便。 表1.6.2及表1.6.3的公式可直接應用。 常用的推理規(guī)則： （1）前提引入規(guī)則：在證明的任何步驟上，都可以引入前提，簡稱P規(guī)則。 （2）結論引入規(guī)則：在證明的任何步驟上，所證明的結論都可作為后續(xù)證明的前提。 （3）置換規(guī)則：在證明的任何步驟上，命題公式中的任何子命題公式都可以用與之等值的命題公式置換（表1.6.2，表1.6.3），記為T規(guī)則。,1.6 推理理論,判別有效結論的方法： （3）構造論證法 現(xiàn)在由一組前提H1，H2，.，Hn，利用一些公認的推