离散数学第一次作业--参考答案

4. 用等值演算法证明下面等值式：

(2)(p→q) ∧(p→r) ⇔(p→(q∧r))

(4)(p∧⌝q) ∨(⌝p ∧q) ⇔(p∨q) ∧⌝(p∧q)

证明（2）(p→q) ∧(p→r)

⇔ (⌝p ∨q) ∧(⌝p ∨r)

⇔⌝p ∨(q∧r))

⇔p →(q∧r)

（4）(p∧⌝q) ∨(⌝p ∧q) ⇔(p∨(⌝p ∧q)) ∧(⌝q ∨(⌝p ∧q))

⇔(p∨⌝p) ∧(p∨q) ∧(⌝q ∨⌝p) ∧(⌝q ∨q)

⇔1∧(p∨q) ∧⌝(p∧q) ∧1

⇔(p∨q) ∧⌝(p∧q)

14. 在自然推理系统P 中构造下面推理的证明：

(4)前提：q →p,q s,s t,t ∧r

结论：p ∧q

证明：

② t ∧r

②t

③q s

④s t 前提引入 ①化简律前提引入前提引入

③④等价三段论 ⑤q t

⑥（q →t ）∧(t→q) ⑤ 置换

⑦（t →q ）

⑧q

⑨q →p

⑩p ⑥化简 ②⑥ 假言推理前提引入 ⑧⑨假言推理

⑧⑩合取 11p ∧q ○

P59. 18. 在自然推理系统P 中构造下面推理证明

（1）如果今天是星期六，我们就要到颐和园或圆明园去玩，如果颐和园游人太多，

我们就不去颐和园玩，今天是周末颐和园游人太多，所以我们去圆明园玩。证明：设p ：今天是星期六，q ：我们到颐和园玩，r:我们到圆明园玩，s:颐和园游人太多

前提：p → (q∨r), s →⌝q ,p ,s

结论：r

推理：① s →⌝q

P86. 22. 在自然推理系统N £中，构造下列推理的证明。 ② s ③ ⌝q ④ p 前提引入前提引入 ①②假言推理前提引入前提引入 ④⑤假言推理 ③⑥析取三段论 ⑤ p → (q∨r) ⑥ q∨r ⑦ r

（1）偶数都能被2整除。6是偶数。所以6能被2整除。

设：F （x ）:x为偶数，G （x ）:x能被2整除，a ：6

前提：∀x (F (x ) →G (x )), F(a )

结论：G （a ）

证明：

①任意x （F （x ）—>G（x ））前提引入

②F（a ）—>G（a ） ①全称量词消去规则

③F（a ）前提引入

④G（a ）假言推理