对偶与范式版.ppt

1-8 推理理论 定义1-8.1 设A和C是两个命题公式，当且仅当A?C为一重言式，即A?C ，称C是A的有效结论。或C可由A逻辑地推出。 定义1-8.2 设H1，H2，…，Hm 和C为命题公式，若H1 ?H2 ? … ? Hm ? C，则称C为一组前提H1，H2，…，Hm 的有效结论。 证明方法如下： ⑴真值表法（分析法） ⑵公式推导： 分为①直接证法、 ②反证法和③CP规则， 后两种称为间接证法。 1-8 推理理论 要证H1 ? H2 ?… ? Hm ? C是重言式 设P1，P2，…，Pn 是出现在H1，H2，…，Hm 和C中的所有命题变元。 真值表： P1，P2，…，Pn ， H1，H2，…，Hm，C 共n+m+1列 1-8.1 真值表法 如果有n个命题变元，则真值表n+m+1列，使得H1，H2，…，Hm 均为T的真值指派，C也为T； 或者看使得C为F的真值指派的行，在每一个这样的行中H1，H2，…，Hm 中至少有一个为F也可。 1-8 推理理论 例：P47 (2) a) 证明：A??C是前提 ?A?B，C??B的有效结论。 A B C ?A?B C??B A??C T T T T F F T T F T T T T F T F T F T F F F T T F T T T F T F T F T T T F F T T T T F F F T T T 1-8.2 直接证法 任务是构造命题公式序列 P 规则：前提在论证过程中随时可以引用。 (premise) T规则：在推导中，如果有一个或多个公式蕴含着公式S，则公式S可以引入推导之中。 1-8.2 直接证法 例题：如果张老师来了，这个问题可以得到解答，如果李老师来了，这个问题也可以得到解答，总之张老师或李老师来了，这个问题就可以得到解答。 解：设 P：张老师来了。Q：李老师来了。 R：这个问题可以得到解答。 (P?R)?(Q?R)?(P?Q) ?R 1-8.2 直接证法 证：(P?R)?(Q?R)?(P?Q) ?R 证明：(1) P?R P (2) Q?R P (3) P?Q P (4) ?P?Q T(3) E (5) ?P?R T(4),(2) I13 (6) (P?R)?(?P?R) T(1),(5) I9 (7) R T(6) E E: Equivalent I: Implication 1-8.2 直接证法 请做P47 (1) b) 证明：J ?(M?N), (H?G) ?J, H?G ? M?N 证明：(1) J ?(M?N) P (2) (H?G) ?J P (3) (H?G) ?(M?N) T(1),(2) I13 (4) H?G P (5) M?N T(3),(4) I11 1-8.3 间接证法 1.反证法 反证法的根据如下： 要证 H1 ? H2 ? …? Hm ? C 记A=H1 ? H2 ? …? Hm ， 即是要证 A ? C，A ?C是重言式， ?A ?C是重言式，A ? ?C是矛盾式， 即是要证H1 ? H2 ? …? Hm ? ?C是矛盾式 等于多了一个前提?C，用直接证明方法证得矛盾即可 1-8.3 间接证法 例：证：S??Q, S?R, ?R, ?P Q ?P [P47 (4) b)] 证明: (1) ?P P(附加前提) (2) S?R P (3) ?R P (4) S T(2),(3) I10 (5) S??Q P (6) ?Q