当前位置:文档之家› 离散数学 数理逻辑__命题逻辑_(4)

离散数学 数理逻辑__命题逻辑_(4)


所以 (P→Q)∧(Q→R) ⇒ P→R 。 → ∧ → →
EX4:一份统计表格的错误或是由于材料不可靠,或是由于计算有错误,这份 :一份统计表格的错误或是由于材料不可靠,或是由于计算有错误 这份 统计表格的错误不是由于材料不可靠,所以这份统计表格是由于计算有错误。 统计表格的错误不是由于材料不可靠,所以这份统计表格是由于计算有错误。
第15页
2、附加前提证明法(CP规则) 、附加前提证明法( 规则 规则) 欲证明: 欲证明 ( A1 ∧ A2 ∧, …, ∧ Ak )→ (A→B) → →
(1)
而 (A1∧A2∧…∧Ak)→(A→B) ∧ → → ⇔ ¬( A1∧A2∧…∧Ak)∨(¬A∨B) ∧ ∨¬ ∨ ⇔ ¬( A1∧A2∧…∧Ak∧A)∨B ∧ ∨ ⇔ (A1∧A2∧…∧Ak∧A)→B (2) ∧ → 在(2) 式中原结论中的前件 已经变成了前提,如 式中原结论中的前件A已经变成了前提 已经变成了前提, 果能证明(2) 式为永真式, 式也是永真式。 果能证明 式为永真式,则(1)式也是永真式。称 式也是永真式 A为附加前提,称这种将结论中的前件作为前提 为附加前提, 为附加前提 的证明方法为附加前提证明法( 规则 规则)。 的证明方法为附加前提证明法(CP规则)。
第5页
EX3:利用真值表法论证 : ① (P→Q)∧¬ P⇒Q ( ?) → ∧ ⇒ ② (P→Q)∧(Q→R) ⇒ P→R ( ?) → ∧ → 真值表如下: 解: ①真值表如下: P 0 0 1 1 Q 0 1 0 1 ¬P 1 1 0 0
推理理论
P→Q → 1 1 0 1
因使P→ , 同时为T的只有第一 因使 →Q,¬ P同时为 的只有第一、二行, 同时为 的只有第一、二行, 相应的Q:第二行为 ,但第一行为F 相应的 :第二行为T,但第一行为 , 所以Q不是 → , 的有效结论。 所以 不是P→Q,¬ P的有效结论。 不是 的有效结论
即将¬ 作为假设前提补充到原来的前提中去 作为假设前提补充到原来的前提中去, 即将¬ B作为假设前提补充到原来的前提中去,转化成对 A1∧A2∧A3⋅⋅⋅⋅⋅∧An ∧¬B ⇔ F的证明。 ⋅⋅⋅⋅⋅∧ 的证明。 的证明
第12页
推理理论
EX1:用反证法证明:(P→Q)∧(Q→R)∧P ⇒ R :用反证法证明: → ∧ → ∧ 思路:将¬ R作为假设前提补充到原来的前提中去,转化对 思路: 作为假设前提补充到原来的前提中去, 作为假设前提补充到原来的前提中去 (P→Q)∧(Q→R)∧P∧¬ R ⇔ F的证明。 → ∧ → ∧ ∧ 的证明。 的证明 证明: 证明: 编号 公式 (1) (2) (3) (4) (5) (6) (7) P→Q → P Q Q →R R ¬R F 根据 P P T(1),(2) P T(3),(4) 否定结论引入 T(5),(6)
P 0 0 1 1 Q 0 1 0 1 ¬P 1 1 0 0 P∨Q ∨ 0 1 1 1
从表中看到使P∨ , 同时为T的只有第二行 从表中看到使 ∨Q,¬ P同时为 的只有第二行,这时 的真值亦为 同时为 的只有第二行,这时Q的真值亦为 T,所以 是前提 ∨Q,¬ P的有效结论。即: ¬ P∧(P∨Q)⇒ Q。 是前提P∨ , 的有效结论。 ,所以Q是前提 的有效结论 ∧ ∨ ⇒ 。
推理理论
(二)直接证明法
两条推理规则: 两条推理规则: 规则(前提引入规则): ):前提在推导过程中的任何时候 ① P 规则(前提引入规则):前提在推导过程中的任何时候 都可以引入使用。 都可以引入使用。 规则(结论引用规则):在推导过程中得到的结论, ):在推导过程中得到的结论 ② T 规则(结论引用规则):在推导过程中得到的结论,可 以在后继证明过程中的任何地方引用。 以在后继证明过程中的任何地方引用。 EX1:试证:(P→Q),(Q→R),P ⇒ R :试证: → , → , 证:编号 公式 (1) (2) (3) (4 ) (5) P→Q → P Q Q →R R 根据 引入前提, 规则 引入前提,P规则 引入前提, 规则 引入前提,P规则 (1) (2)假言推理,T规则 假言推理, 规则 假言推理 引入前提, 规则 引入前提,P规则 (3) (4)假言推理,T规则 假言推理, 规则 假言推理
第4页
推理理论
二、命题演算的证明方法(推理理论) 命题演算的证明方法(推理理论) (一)真值表法: 真值表法: 检查真值表中使所有A 都取T的那些行 的那些行, ① 检查真值表中使所有 1,A2…An都取 的那些行, 在所有这些行都为真值T, 若B在所有这些行都为真值 , 在所有这些行都为真值 即证得: 即证得 A1,A2…An ⇒ B。 。 检查真值表中B的取值为 的那些行,若在相应行中, 的取值为F的那些行 ② 检查真值表中 的取值为 的那些行,若在相应行中, 至少有一个A 至少有一个 i(i=1,2,…n)取值为 , , , )取值为F, 即证得: 即证得 A1,A2…An ⇒ B。 。
第13页
EX2:用反证法证明: (P∨Q)∧(P→R)∧(Q→S) ⇒ S∨R :用反证法证明: ∨ ∧ → ∧ → ∨
证:编号 (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) (11) 公式 ¬ (S∨R) ∨ ¬ S∧¬ R ∧ ¬S Q→S → ¬Q P∨Q ∨ P P→R → R ¬R F 根据
否定结论引入
T(1) T(2) P T(3),(5) , P T(6) ,(7) P T(8), (9) , T(2) T(9) ,(10)
推理理论
思考:用反证法证明: 思考:用反证法证明:A→B,¬ (B∨C) ⇒ ¬ A 证: 编号 公式 (1) (2) (3) (4) (5) (6) (7) A→B → A B ¬ (B∨C) ∨ ¬ B∧¬ C ∧ ¬B F 根据 P 否定结论引入 T(1),(2) P T(4) T(5) T(3),(6) ,
第9页
推理理论
EX2:试证:P∨Q,Q→R,P→M, ¬ M ⇒ R∧( 编号 公式 (1) (2) (3) (4) (5) (6) (7) (8) ¬M P→M → ¬P P∨Q ∨ Q Q→R → R R∧(P∨Q) ∧ ∨ 根据 P P T(1),(2)(拒取式) , (拒取式) P T(3),(4)(析取三段论) , (析取三段论) P T(5),(6)(假言推理) , (假言推理) T(4),(7) ,
第16页
EX1:试证:(P→Q),(Q→R) ⇒ P → R :试证: → , → 证:编号 公式 (1) (2) (3) (4) (5) (6) P→Q → P Q Q →R R P→R → 根据 P P,附加前提 , T(1) (2) P T(3) (4) CP规则 规则
推理理论
§1.6 推理理论
重言蕴含式) 一、永真蕴含式(重言蕴含式 永真蕴含式 重言蕴含式 定义1 定义1:设A、B是两个命题公式,如果A→B是永真式, 是两个命题公式,如果A 是永真式, 则称A永真蕴含B 记为A 其中称A为前提, 则称A永真蕴含B,记为A⇒B。其中称A为前提,B称为有 效结论,这种从前提推出结论的思维过程叫推理。 效结论,这种从前提推出结论的思维过程叫推理。
解:设各命题变元 P:统计表格的错误是由于材料不可靠。 :统计表格的错误是由于材料不可靠。 Q:统计表格的错误是由于计算有错误。 :统计表格的错误是由于计算有错误。 本例可译为: 是前提 是前提P∨ , 的有效结论, 本例可译为:Q是前提 ∨Q,¬ P的有效结论,即 (P∨Q) ∧ ¬ P ⇒ Q 的有效结论 ∨
第11页
推理理论
(三) 间接证明法 1、反证法(归谬法) 、反证法(归谬法)
原理: 原理: 即 A1∧A2∧A3⋅⋅⋅⋅⋅∧An ⇒B ⋅⋅⋅⋅⋅∧ A1∧A2∧A3⋅⋅⋅⋅⋅∧An →B ⇔ T ⋅⋅⋅⋅⋅∧ ¬(A1∧A2∧A3⋅⋅⋅⋅⋅∧An)∨B ⇔ T ( ⋅⋅⋅⋅⋅∧ 即证 A1∧A2∧A3⋅⋅⋅⋅⋅∧An ∧¬B ⇔ F ⋅⋅⋅⋅⋅∧
证明:(P→Q)∧(Q→ (P→ 证明:(P→Q)∧(Q→R) →(P→R) ⇔((P→Q)∧(Q→R))→(P→R) ((P→Q)∧(Q→R))→(P→ ((P ⇔¬((P→Q)∧(Q→R))∨(P→R) ¬((P→Q)∧(Q→R))∨(P→ ⇔¬((¬P∨Q)∧(¬Q∨R))∨(¬P∨R) ¬((¬ Q)∧(¬ R))∨ ⇔((P∧¬ Q)∨(Q∧¬ R))∨(¬P∨R) ((P∧ Q)∨(Q∧ R))∨ ((P ⇔(P∧¬ Q)∨¬P∨(Q∧¬R)∨R ---结合律 (P∧ Q)∨ (Q∧ R)∨ ---结合律 (P ⇔(P∨¬P)∧(¬Q∨¬P)∨(Q∨R )∧(¬R∨R)---分配律 (P∨ P)∧ ¬ P)∨(Q∨ ∧( ∧(¬ R)-----分配律 (P ⇔(¬Q∨¬P)∨(Q∨R ) ( P)∨(Q∨ ⇔(¬Q∨Q)∨(¬ P∨R ) ( Q)∨ ⇔T T 证毕
更一般的有: 更一般的有: 定义2: 是命题公式, 定义 :设A1、A2…An和B是命题公式,当且仅当 是命题公式 A1∧A2∧A3…∧An ⇒ B,则称 是一组前提 1,A2…An 是一组前提A ∧ ,则称B是一组前提 的有效结论,或称从 推出B。 的有效结论,或称从A1,A2…An推出 。 有时也记为: 有时也记为 A1,A2 ,…,An ⇒ B。 。
第10页
推理理论
EX3:试证:P∨Q,P→R,Q→S ⇒ S∨R :试证: ∨ , , ∨
证: 编号 公式 (1) (2) (3) (4) (5) (6) (7) (8) P∨Q ∨ ¬P→Q → Q→S P∨S ∨ ¬ S→P → P→R ¬ S→R → S∨R ∨ 根据 P T(1) (I:P→Q ⇔ ¬ P∨Q) : → ∨ P T(2),(3) (假言三段论) , 假言三段论) T(4) ( I:P→Q ⇔ ¬ P∨Q) : → ∨ P T(5),(6),(假言三段论) , ,(假言三段论) ,(假言三段论 T(7) (I:P→Q ⇔ ¬ P∨Q) : → ∨
相关主题