离散数学命题逻辑4.ppt

第一章 命题逻辑,推理理论,推理理论,前提与有效结论 证明方法 推理定律和规则 直接证明法 间接证明法,推理,推理：由前提，依据推理规则，推导出结论的思维过程。 命题逻辑中，前提和结论都用命题公式表示 若前提为：P1、P2、Pn ；有效结论：Q 由前提P1、P2、Pn推出有效结论Q 证明当前提P1、P2、Pn都成立（为真）时，Q成立（为真） P1 P2 Pn Q （P1, P2, , Pn Q ）,证明永真蕴涵式的方法：,证 明:AB： 真值表法 命题(等价)演算法 利用等价公式和永真蕴涵公式证明 假设推理法。(假设前提为真，证明结论必为真) 主析取范式法,所以， P (PQ)( (PQ) Q 1,例1.6.1 证明Q是前提P，PQ, (PQ)的有效结论 证明: 等价于证明P (PQ)( (PQ) Q (1) 真值表法,(2) 命题演算 (3) 利用等价公式和永真蕴涵公式证明,(4)假设推理法 P (PQ)( (PQ) Q 假设P(PQ)(PQ)为真， 则P和(PQ)为真, 所以PQ为假，因而Q为假。即Q为真。这就证明了P(PQ)(PQ) Q。,(5)主范式法,推理理论,前提与有效结论 证明方法 直接证明法 间接证明法,直接证明法,由一组前提，利用一些公认的推理规则，根据已知的等价或 蕴含公式，推演得到有有效的结论。 直接证明法遵循两条规则(TP规则)： P规则：前提在推导过程中的任何时候都可以引入使用 T规则：在推导中，如果有一个或多个公式、永真蕴含着公式S，则S可引入推导中,推理定律永真蕴涵式,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) (AB)(AB)(AA) B (AB)(CD)( BD) (AC),直接证明法例1：,请用直接证明法证明： (PQ), (PR), (QS)RS 证明: (1) PQ p (2) PQ T(1) (3) QS P (4) PS T(2) (3) (5) PR P (6) R P T(5) (7) RS T(4) (6) (8) RS T(7),直接证明法例 2,证明：P Q, Q R, R, (P S) S. /* 逗号“,”和“”的含义相同 */ 证明 (1) QR 利用P规则，引入前提 (2) QR 利用P规则，引入前提 (3) R 利用P规则，引入前提 (4) Q 由(2),(3) ，利用T规则 (5) P Q 利用P规则，引入前提 (6) P 由(4),(5)，利用T规则 (7) (PS) P利用P规则，引入前提 (8) PS 由(7)，利用T规则 (9) S 由(6),(8)，利用T规则,直接证明法例 3,证明(A B) (C D), (D F) E A E /* 逗号“,”和“”的含义相同 */ 证明 (1) (AB)(CD) P (2) (AB) (CD) T(1) (3) (AB)C) (AB)D) T(2) (4) (AB)D T(3) (5) (AB)D T(4) (6) (AD)(BD) T(5),直接证明法例3,证明(A B) (C D), (D F) E A E 证明（续） (6) (AD)(BD) T(5) (7) A D T(6) (8) A D T(7) (9) (D F) E P (10) (D F) E T(9) (11) (D F) E T(10) (12) (D E) (F E) T(11) (13) D E T(12) (14) D E T(13) (15) A E T(8),(14),例 4：请给出下面语句的前提和结论以及推理过程 ： 或者天晴，或者下雨。 如果天晴，我去看电影。 如果我去看电影，我就不看书。 我在看书。 所以天在下雨。,推理过程： “如果我去看电影，我就不看书” 但“我在看书” 所以“我没去看电影” 而“如果天晴，我去看电影” 所以“天不晴” 由于“或者天晴，或者下雨。 所以”天在下雨“,或者天晴，或者下雨。 如果天晴，我去看电影。 如果我去看电影，我就不看书。 我在看书。 所以天在下雨。,推理过程： “如果我去看电影，我就不看书” 但“我在看书” 所以“我没去看电影” 而“如果天晴，我去看电影” 所以“天不晴” 由于”或者天晴，或者下雨“ 所以”天在下雨“,M：天晴。 Q：下雨。 S：我看电影。 R：我看书。,MQ,MS,SR,R,Q,SR P,R P,S T,MS P,M T,MQ P,Q T,MQ, MS, SR, R Q,推理理论,前提与有效结论 证明方法 直接证明法 间接证明法,间接证明法(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加入到前提中去，然后证明能推出一个永假式。,间接证明法 例1,证明PQ, QR, R, (PS) S 等价于证明: PQ, QR, R, (PS) , S 0 (1) S P(附加前提) (2) (PS) P (3) PS T(2) (4) S P T(1),(3) (5) P T(1),(4) (6) PQ P (7) Q T(5),(6) (8) QR P (9) Q R T(7),(8) (10) R T(7), (9) (11) R P (12) R R(永假) T(10),(11),间接证明法 例2,证明 (AB)C,CDE, EF, D F A 等价于证明: (AB)C,CDE, EF, D F, A 0 (1) A P(附加前提) (2) AB T(1) (3) (AB)C P (4) C T(2),(3) (5) CDE P (6) DE 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) DD (永假) T(11),(12),间接证明法(2)CP规则,间接证明法的另一种情况是使用CP规则。 设有一组前提P1、P2、Pn，要推出结论Q，证明 P1 P2 Pn (AB) 即证明 (P1 P2 Pn ) (AB) 1 即证明 (P1 P2 Pn)(AB) 1 即证明 ( P1 P2 Pn A) B 1 即证明 P1 P2 Pn A B 即所需推出的结论是A B的形式时，可先将A作为附加前提，只需证明B是有效结论即可,CP规则 例1,证明：(A B) (C D), (D F) E A E 根据CP规则，等价于证明：(A B) (C D), (D F) E , A E 证明： (1) A P(附加前提) (2) AB T(1) (3) (AB)(CD) P (4) CD T(2),(3) (5) D T(4) (6) DF T(5) (7) (DF)E P (8) E T(6),(7) (9) AE CP规则,CP规则例2,证明： A (B C), (C D) E, F (D E) A (B F) 证明 利用CP规则，即证： A(BC), (CD)E, F(DE), A, B F (1) A P附加前提 (2) A(BC) P (3) BC T(1),(2) (4) B P(附加前提) (5) C T(3),(4) (6) (CD)E P (7) CDE T(6) (8) C(DE) T(7),(9) DE T(5),(8) (10) F(DE) P (11) F(DE) T(10) (12) (DE)F T(11) (13) F T(9),(12) (14) BF CP规则 (15) A(BF) CP规则,综合练习例1