Question

能给个详细的构造性二难的证明吗

Answer 1

用归谬法

(A→B)∧(C→D)∧(A∨C)=> (B∨D)等价于(A→B)∧(C→D)∧(A∨C)∧(非(B∨D))

(A→B)∧(C→D)∧(A∨C)∧(非(B∨D))

=> (A→B)∧(C→D)∧(非(B∨D))∧(A∨C)

=> ((A→B)∧非B) ∧((C→D)∧非D)∧(A∨C) =>

非A∧非C∧(A∨C)

=> (非A∧非C∧A)∨(非A∧非C∧C)

=> 0∨0 => 0

于是(A→B)∧(C→D)∧(A∨C)=> (B∨D)