第六章命题逻辑.ppt

第六章第六章 命题逻辑命题逻辑第三部分：第三部分：6.5 推理理论推理理论离散数学26.5 推理理论推理理论³6.5.1 前提与有效结论前提与有效结论³6.5.2 证明方法证明方法²6.5.1 推理定律和规则推理定律和规则²6.5.2 直接证明法直接证明法²6.5.3 间接证明法间接证明法离散数学3推理推理³推理推理：由前提，依据推理规则，推导出结论的思维过程由前提，依据推理规则，推导出结论的思维过程³命题逻辑中，前提和结论都用命题公式表示命题逻辑中，前提和结论都用命题公式表示²若前提为：若前提为：P1、、P2、、···、、Pn ；有效结论：；有效结论：Q 由前提由前提P1、、P2、、···、、Pn推出有效结论推出有效结论Q 证明当前提证明当前提P1、、P2、、···、、Pn都成立（为真）时，都成立（为真）时，Q成立（为真）成立（为真） P1∧ ∧ P2∧ ∧ ··· ∧ ∧ Pn ⇒⇒ Q （（P1, P2, ··· , Pn ⇒⇒ Q ）） 离散数学4证明永真蕴涵式的方法：证明永真蕴涵式的方法：证明证明A AB B：：•真值表法真值表法•命题命题( (等价等价) )演算法演算法•利用等价公式和永真蕴涵公式证明利用等价公式和永真蕴涵公式证明•假设推理法。

假设推理法 (假设前提为真，证明结论必为真假设前提为真，证明结论必为真) )•主析取范式法主析取范式法离散数学5所以， P ∧ ∧ (P∨ ∨Q)∧ ∧(﹁﹁ (P∧ ∧Q)) ﹁﹁Q  1例例1.6.1 证明证明﹁﹁Q是前提是前提P，，P∨∨Q, ﹁﹁ (P∧∧Q)的有效结论的有效结论证明证明: 等价于证明等价于证明P ∧∧ (P∨∨Q)∧∧(﹁﹁ (P∧∧Q)) ﹁﹁Q(1) 真值表法真值表法 离散数学6 (2) 命题演算命题演算 (3) 利用等价公式和永真蕴涵公式证明利用等价公式和永真蕴涵公式证明离散数学7(4)假设推理法假设推理法 P ∧∧ (P∨∨Q)∧∧(﹁﹁ (P∧∧Q)) ﹁﹁Q 假设假设P∧∧(P∨∨Q)∧∧﹁﹁(P∧∧Q)为真，为真， 则则P和和﹁﹁(P∧∧Q)为真为真, 所以所以P∧∧Q为假，因而为假，因而Q为假。

为假即即﹁﹁Q为真这就证明了为真这就证明了P∧∧(P∨∨Q)∧∧﹁﹁(P∧∧Q)⇒⇒ ﹁﹁Q 离散数学8(5)主范式法主范式法 离散数学96.5 推理理论推理理论³6.5.1 前提与有效结论前提与有效结论³6.5.2 证明方法证明方法²6.5.2.1 直接证明法直接证明法²6.5.2.2 间接证明法间接证明法离散数学10直接证明法直接证明法³ 由一组前提，利用一些公认的推理规则，根据已知的等价或由一组前提，利用一些公认的推理规则，根据已知的等价或 蕴含公式，推演得到有有效的结论蕴含公式，推演得到有有效的结论³直接证明法遵循两条规则直接证明法遵循两条规则(TP规则规则)：：²P规则规则：前提在推导过程中的任何时候都可以：前提在推导过程中的任何时候都可以引入使用引入使用²T规则规则：在推导中，如果有一个或多个公式、永真蕴含着：在推导中，如果有一个或多个公式、永真蕴含着公式公式S，则，则S可可引入推导引入推导中中离散数学11推理定律推理定律——永真蕴涵式永真蕴涵式 A  (A   B) (A Ù Ù B)  A (A   B) Ù Ù A  B (A   B) Ù Ù B   A (A   B) Ù Ù B  A (A   B) Ù Ù (B   C)  (A   C) (A « « B) Ù Ù (B « « C)  (A « « C) (A   B) Ù Ù (C   D) Ù Ù (A   C)  (B   D) (AB)Ù Ù( AB)Ù Ù(AA)  B (AB)Ù Ù(CD)Ù Ù(  BD)  ( AC)离散数学12直接证明法例直接证明法例1：：³请用直接证明法证明：请用直接证明法证明： (P∨ ∨Q), (P→R), (Q→S)⇒⇒R∨ ∨S 证明证明: (1) 　　P∨ ∨Q 　　　　　　　　p (2)　　┓┓P→Q　　　　　　 T(1) (3) 　　Q→S 　　　　　　　　P (4)　　┓┓P→S　　　　　　 T(2) (3) (5)　　P→R　　　　　　　　 P (6)　　┓┓R → ┓┓P 　　　　T(5) (7) 　　┓┓R→S 　　　　　　 T(4) (6) (8) 　　R∨ ∨S 　　　　　　　　 T(7)离散数学13直接证明法例直接证明法例 2证明：证明：P → Q, ┓┓Q ∨ ∨ R, ┓┓R, ┓┓(┓┓P ∧ ∧ S) ⇒￿⇒￿┓┓S./* 逗号逗号“,”和和“∧∧”的含义相同的含义相同 */³证明证明　　 (1)　　┓┓Q∨ ∨R 利用利用P规则，引入前提规则，引入前提 (2) Q→R 利用利用P规则，引入前提规则，引入前提 (3)　　┓┓R 利用利用P规则，引入前提规则，引入前提 (4)　　┓┓Q 由由(2),(3) ，利用，利用T规则规则 (5) P → Q 利用利用P规则，引入前提规则，引入前提 (6)　　┓┓P由由(4),(5)，利用，利用T规则规则 (7)　　┓┓(┓┓P∧ ∧S)P利用利用P规则，引入前提规则，引入前提 (8)　　P∨ ∨┓┓S由由(7)，利用，利用T规则规则 (9) ┓┓S由由(6),(8)，利用，利用T规则规则 离散数学14直接证明法例直接证明法例 3³证明证明(A ∨ ∨ B) → (C ∧ ∧ D), (D ∨ ∨ F) → E ⇒￿⇒￿A → E/* 逗号逗号“,”和和“∧∧”的含义相同的含义相同 */³证明证明(1)　　(A∨ ∨B)→(C∧ ∧D) P(2)　　┓┓(A∨ ∨B) ∨ ∨(C∧ ∧D) T(1)(3)　　(┓┓(A∨ ∨B)∨ ∨C)) ∧ ∧(┓┓(A∨ ∨B)∨ ∨D) T(2)(4)　　┓┓(A∨ ∨B)∨ ∨D T(3)(5)　　(┓┓A∧ ∧┓┓B)∨ ∨D T(4)(6)　　(┓┓A∨ ∨D)∧ ∧(┓┓B∨ ∨D) T(5)离散数学15直接证明法例直接证明法例3³证明证明(A ∨ ∨ B) → (C ∧ ∧ D), (D ∨ ∨ F) → E ⇒￿⇒￿A → E³证明（续）证明（续）(6)　　 (┓┓A∨ ∨D)∧ ∧(┓┓B∨ ∨D) T(5)(7)　　 ┓┓A ∨ ∨ DT(6)(8) A → D T(7)(9) (D ∨ ∨ F) → E P(10) ┓┓(D ∨ ∨ F) ∨ ∨ ET(9)(11)　　(┓┓D ∧ ∧ ┓┓F) ∨ ∨ ET(10)(12)　　(┓┓D ∨ ∨ E) ∧ ∧ (┓┓F ∨ ∨ E) T(11)(13)　　┓┓D ∨ ∨ ET(12)(14)　　D → ET(13)(15)　　A → E T(8),(14) 离散数学16例例 4：：请给出下面语句的前提和结论以及推理过程请给出下面语句的前提和结论以及推理过程 ：： 或者天晴，或者下雨。

或者天晴，或者下雨 如果天晴，我去看电影如果天晴，我去看电影 如果我去看电影，我就不看书如果我去看电影，我就不看书 我在看书我在看书 所以天在下雨所以天在下雨推理过程：推理过程： “如果我去看电影，我就不看书如果我去看电影，我就不看书” 但但“我在看书我在看书” 所以所以“我没去看电影我没去看电影” 而而“如果天晴，我去看电影如果天晴，我去看电影” 所以所以“天不晴天不晴” 由于由于“或者天晴，或者下雨或者天晴，或者下雨 所以所以”天在下雨天在下雨“离散数学17 或者天晴，或者下雨或者天晴，或者下雨 如果天晴，我去看电影如果天晴，我去看电影 如果我去看电影，我就不看书如果我去看电影，我就不看书 我在看书我在看书 所以天在下雨所以天在下雨³推理过程：推理过程： “如果我去看电影，我就不看书如果我去看电影，我就不看书” 但但“我在看书我在看书” 所以所以“我没去看电影我没去看电影” 而而“如果天晴，我去看电影如果天晴，我去看电影” 所以所以“天不晴天不晴” 由于由于”或者天晴，或者下雨或者天晴，或者下雨“ 所以所以”天在下雨天在下雨“MM：天晴。

天晴S S：我看电影我看电影我看电影我看电影R R：我看书MM   MMS SS SR RR RS SR PR PR PR P   S TS TMMS PS P   M TM TMM   Q PQ PQ Q T TMM   Q, Q, MMS, S, S SR, R R, R  Q Q离散数学186.5 推理理论推理理论³6.5.1 前提与有效结论前提与有效结论³6.5.2 证明方法证明方法²6.5.2.1 直接证明法直接证明法²6.5.2.2 间接证明法间接证明法离散数学19间接证明法间接证明法(1)设有一组前提设有一组前提P1、、P2、、···、、Pn，要推出结论，要推出结论Q，，证明证明 P1 ∧ ∧ P2 ∧ ∧ ··· ∧ ∧ Pn ⇒⇒ Q即证明即证明 (P1 ∧ ∧ P2 ∧ ∧ ··· ∧ ∧ Pn) → Q ⇔⇔ 1即证明即证明 ┓┓(P1 ∧ ∧ P2 ∧ ∧ ··· ∧ ∧ Pn) ∨ ∨ Q ⇔⇔ 1即证明即证明 ┓┓(┓┓(P1 ∧ ∧ P2 ∧ ∧ ··· ∧ ∧ Pn) ∨ ∨ Q) ⇔⇔ 0利用利用摩根律摩根律，即，即证明证明 (P1 ∧ ∧ P2 ∧ ∧ ··· ∧ ∧ Pn) ∧ ∧ ┓┓Q ⇔⇔ 0等价于证明：等价于证明： (P1 ∧ ∧ P2 ∧ ∧ ··· ∧ ∧ Pn) ∧ ∧ ┓┓Q  0即将即将┓┓Q加入到前提中去，然后证明能推出一个永假式。

加入到前提中去，然后证明能推出一个永假式离散数学20间接证明法间接证明法 例例1³证明证明P→Q, ┓┓Q∨ ∨R, ┓┓R, ┓┓(┓┓P∧ ∧S) ⇒￿⇒￿┓┓S³等价于证明等价于证明:　　 P→Q, ┓┓Q∨ ∨R, ┓┓R, ┓┓(┓┓P∧ ∧S) , S ⇒0⇒0 (1)　　 SP(附加前提附加前提) (2)　　 ┓┓(┓┓P∧ ∧S)P (3)　　 P∨ ∨┓┓S T(2) (4)　　 S→ P T(1),(3) (5)　　 P T(1),(4) (6)　　 P→Q P (7)　　Q T(5),(6) (8)　　┓┓Q∨ ∨R P (9)　　Q → R T(7),(8) (10)　　R T(7), (9) (11) ┓┓R P (12)　　R ∧ ∧ ┓┓R(永假永假) T(10),(11)离散数学21间接证明法间接证明法 例例2³证明证明 (A∨ ∨B)→C,C→D∨ ∨E, E→F, ┓┓D∧ ∧ ┓┓F ⇒￿⇒￿┓┓A³等价于证明等价于证明: (A∨ ∨B)→C,C→D∨ ∨E, E→F, ┓┓D∧ ∧ ┓┓F, A ⇒0⇒0 (1)　　A P(附加前提附加前提)　　　　 (2)　　A∨ ∨B T(1)　　　　 (3)　　(A∨ ∨B)→C P　　 　　(4)　　C T(2),(3)　　 　　(5)　　C→D∨ ∨E P　　　　 (6)　　D∨ ∨E T(4),(5) (7) 　　┓┓D ∧ ∧ ┓┓ F P　　　　 (8) ┓┓ F T(7)　　　　 (9) E → F P　　　　 (10) ┓┓E T(8),(9)　　　　 (11) D 　　 P　　　　 (12)　　┓┓D T(7)　　　　 (13) D∧ ∧┓┓D (永假永假) T(11),(12)离散数学22间接证明法间接证明法(2)－－CP规则规则³间接证明法间接证明法的另一种情况是使用的另一种情况是使用CP规则规则。

³设有一组前提设有一组前提P1、、P2、、···、、Pn，要推出结论，要推出结论Q，，证明证明 P1∧ ∧ P2∧ ∧ ··· ∧ ∧ Pn ⇒⇒ (A→B) 即证明即证明 (P1∧ ∧ P2∧ ∧ ··· ∧ ∧ Pn ) → (A→B) ⇔⇔ 1 即证明即证明 ┓┓(P1∧ ∧ P2∧ ∧ ··· ∧ ∧ Pn)∨ ∨(┓┓A∨ ∨B) ⇔⇔ 1 即证明即证明 ( P1∧ ∧ P2∧ ∧ ··· ∧ ∧ Pn ∧ ∧ A) →B ⇔⇔ 1 即证明即证明 P1∧ ∧ P2∧ ∧ ··· ∧ ∧ Pn ∧ ∧ A ⇒⇒ B 即所需即所需推出的推出的结论结论是是A → B的形式时，可先将的形式时，可先将A作为作为附加前提，只需附加前提，只需证明证明B是有效结论即可是有效结论即可离散数学23CP规则规则 例例1³证明：证明：(A ∨ ∨ B) → (C ∧ ∧ D), (D∨ ∨ F) → E ⇒￿⇒￿A → E 根据根据CP规则，等价于证明：规则，等价于证明：(A ∨ ∨ B) → (C ∧ ∧ D), (D∨ ∨ F) → E , A ⇒⇒ E³证明：证明： (1)　　AP(附加前提附加前提) (2)　　A∨ ∨B T(1) (3)　　(A∨ ∨B)→(C∧ ∧D) P (4)　　C∧ ∧D T(2),(3) (5)　　D T(4) (6)　　D∨ ∨F T(5) (7)　　(D∨ ∨F)→E P (8)　　E T(6),(7) (9)　　A→E CP规则规则离散数学24CP规则例规则例2³证明：证明：A → (B → C), (C ∧ ∧ D) → E, ┓┓F → (D ∧ ∧ ┓┓E) ⇒⇒A → (B → F)证明证明 利用利用CP规则，即证：规则，即证：A→(B→C), (C∧ ∧D)→E, ┓┓F→(D∧ ∧┓┓E), A, B ⇒￿⇒￿F(1)　　AP附加前提附加前提(2)　　A→(B→C)P(3)　　B→CT(1),(2)(4)　　BP(附加前提附加前提)(5)　　CT(3),(4)(6)　　(C∧ ∧D)→EP(7)　　┓┓C∨ ∨┓┓D∨ ∨ET(6)(8)　　C→(┓┓D∨ ∨E)T(7)(9)　　┓┓D∨ ∨E T(5),(8)(10)　　┓┓F→(D∧ ∧┓┓E) P(11)　　F∨ ∨(D∧ ∧┓┓E) T(10)(12)　　(┓┓D∨ ∨E)→F T(11)(13)　　F T(9),(12)(14)　　B→F CP规则规则(15)　　A→(B→F) CP规则规则离散数学25综合练习例综合练习例1³分析下列事实：分析下列事实： 如果我的论文通过答辩，那么我拿到毕业证；如果我拿到毕业证，如果我的论文通过答辩，那么我拿到毕业证；如果我拿到毕业证，那么我很高兴；但我不高兴，所以我的论文没有通过答辩。

那么我很高兴；但我不高兴，所以我的论文没有通过答辩³试指出前提和结论并证明结论为有效结论试指出前提和结论并证明结论为有效结论解：解：令令 P：我的论文通过答辩我的论文通过答辩 Q：我拿到毕业证我拿到毕业证 R：我很高兴我很高兴由题意知，由题意知，前提：前提： (P → Q)，， (Q → R)，， ┐R 有效结论：有效结论： ┐P要证明：要证明： ┐R ∧ ∧ (P→ Q) ∧ ∧ (Q → R) ⇒⇒ ┐P离散数学26例例1解解┐R ∧ ∧ (P→ Q) ∧ ∧ (Q → R) ⇒⇒ ┐P 证明：证明： (1) ┐R P (2) Q → R P (3) ┐Q T(1),(2) (4) P→ Q P (6) ┐P T(3),(4)离散数学27课堂练习课堂练习 P276：：1 (5)、、2 (1)、、3 (3)离散数学28作业作业 P276：：1 (7)、、2 (2)、、3 (2)、、4。