Question

离散数学：用主析取范式法证明下面推理是正确的。

离散数学：用主析取范式法证明下面推理是正确的。若 a 是奇数, 则 a 不能被2 整除. 若 a 是偶数, 则 a 能被 2 整除. 因此, 如果 a 是偶数, 则 a 不是奇数.

我最后写出来的主析取范式是乛((乛pV乛q)^(qV乛r)^乛(乛pV乛r))，这个不对吧？再往下我写不出来了。

Answer 1

这个显然不是主析取范式。
p: a 是奇数
q: a 能被2 整除
r: a 是偶数
若 a 是奇数, 则 a 不能被2 整除：p→¬q
若 a 是偶数, 则 a 能被 2 整除：r→q
如果 a 是偶数, 则 a 不是奇数: r→¬p
(p→¬q)∧(r→q)
⇔ (¬p∨¬q)∧(¬r∨q) 变成 合取析取
⇔ (¬p∨¬q∨(¬r∧r))∧((¬p∧p)∨q∨¬r) 补项
⇔ ((¬p∨¬q∨¬r)∧(¬p∨¬q∨r))∧((¬p∧p)∨q∨¬r) 分配律
⇔ (¬p∨¬q∨¬r)∧(¬p∨¬q∨r)∧((¬p∧p)∨q∨¬r) 结合律
⇔ (¬p∨¬q∨¬r)∧(¬p∨¬q∨r)∧((¬p∨q∨¬r)∧(p∨q∨¬r)) 分配律
⇔ (¬p∨¬q∨¬r)∧(¬p∨¬q∨r)∧(¬p∨q∨¬r)∧(p∨q∨¬r) 结合律 【1】
得到主合取范式，

而r→¬p
⇔ ¬r∨¬p 变成 合取析取
⇔ ¬r∨¬p ∨（q∧¬q）
⇔ （¬r∨¬p ∨q)∧(¬r∨¬p ∨¬q）【2】
显然【2】式中的合取的子式，蕴含在【1】中
因此，推理正确。
即
(p→¬q)∧(r→q) ⇒ r→¬p