六章节命题逻辑-资料.ppt

六章节命题逻辑-资料
2022/5/29
推理理论
前提与有效结论
证明方法
推理定律和规则
直接证明法
间接证明法
推理
推理：由前提，依据推理(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
证明P→Q, ┓Q∨R, ┓R, ┓(┓P∧S) ⇒ ┓S
等价于证明:　 P→Q, ┓Q∨R, ┓R, ┓(┓P∧S) , S ⇒0
(1)　 S P(附加前提)
(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)
间接证明法 例2
证明 (A∨B)→C,C→D∨E, E→F, ┓D∧ ┓F ⇒ ┓A
等价于证明: (A∨B)→C,C→D∨E, E→F, ┓D∧ ┓F, A ⇒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)
间接证明法(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是有效结论即可
CP规则 例1
证明：(A ∨ B) → (C ∧ D), (D∨ F) → E ⇒ A → E
根据CP规则，等价于证明：(A ∨ B