《第六章命题逻辑演示教学》由会员分享，可在线阅读，更多相关《第六章命题逻辑演示教学（28页珍藏版）》请在金锄头文库上搜索。
1、第六章 命题逻辑,第三部分：6.5 推理理论,6.5 推理理论,6.5.1 前提与有效结论 6.5.2 证明方法 6.5.1 推理定律和规则 6.5.2 直接证明法 6.5.3 间接证明法,推理,推理：由前提，依据推理规则，推导出结论的思维过程。 命题逻辑中，前提和结论都用命题公式表示 若前提为：P1、P2、Pn ；有效结论：Q 由前提P1、P2、Pn推出有效结论Q 证明当前提P1、P2、Pn都成立（为真）时，Q成立（为真） P1 P2 Pn Q （P1, P2, , Pn Q ）,证明永真蕴涵式的方法：,证明AB： 真值表法 命题(等价)演算法 利用等价公式和永真蕴涵公式证明 假设推理法。(
2、假设前提为真，证明结论必为真) 主析取范式法,(2) 命题演算 (3) 利用等价公式和永真蕴涵公式证明,(4)假设推理法 P (PQ)( (PQ) Q 假设P(PQ)(PQ)为真， 则P和(PQ)为真, 所以PQ为假，因而Q为假。即Q为真。这就证明了P(PQ)(PQ) Q。,(5)主范式法,6.5 推理理论,6.5.1 前提与有效结论 6.5.2 证明方法 6.5.2.1 直接证明法 6.5.2.2 间接证明法,直接证明法,由一组前提，利用一些公认的推理规则，根据已知的等价或 蕴含公式，推演得到有有效的结论。 直接证明法遵循两条规则(TP规则)： P规则：前提在推导过程中的任何时候都可以引入使
3、用 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)
4、 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 /* 逗号“,”和“”的含义相同
5、*/ 证明 (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 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),(1
6、4),例 4：请给出下面语句的前提和结论以及推理过程 ： 或者天晴，或者下雨。 如果天晴，我去看电影。 如果我去看电影，我就不看书。 我在看书。 所以天在下雨。,推理过程： “如果我去看电影，我就不看书” 但“我在看书” 所以“我没去看电影” 而“如果天晴，我去看电影” 所以“天不晴” 由于“或者天晴，或者下雨。 所以”天在下雨“,或者天晴，或者下雨。 如果天晴，我去看电影。 如果我去看电影，我就不看书。 我在看书。 所以天在下雨。,推理过程： “如果我去看电影，我就不看书” 但“我在看书” 所以“我没去看电影” 而“如果天晴，我去看电影” 所以“天不晴” 由于”或者天晴，或者下雨“ 所以”天
7、在下雨“,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,6.5 推理理论,6.5.1 前提与有效结论 6.5.2 证明方法 6.5.2.1 直接证明法 6.5.2.2 间接证明法,间接证明法(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)
8、Q 0 即将Q加入到前提中去，然后证明能推出一个永假式。,间接证明法 例1,证明PQ, QR, R, (PS) S 等价于证明: PQ, QR, R, (PS) , S 0 (1) SP(附加前提) (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,
9、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 即证明 ( P
10、1 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)AP(附加前提) (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
11、 (B F) 证明 利用CP规则，即证： A(BC), (CD)E, F(DE), A, B F (1)AP附加前提 (2)A(BC)P (3)BCT(1),(2) (4)BP(附加前提) (5)CT(3),(4) (6)(CD)EP (7)CDET(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,分析下列事实： 如果我的论文通过答辩，那么我拿到毕业证；如果我拿到毕业证，那么我很高兴；但我不高兴，所以我的论文没有通过答辩。 试指出前提和结论并证明结论为有效结论。 解：令 P：我的论文通过答辩。 Q：我拿到毕业证。 R：我很高兴。 由题意知，前提： (P Q)， (Q R)， R 有效结论： P 要证明： R (P Q) (Q R) P,例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),课堂练习,P276：1 (5)、2 (1)、3 (3),作业,P276：1 (7)、2 (2)、3 (2)、4,
