离散数学1.(12)

证明：

①┐p∨r 前提引入 ②p∧q 前提引入 ③p ②化简

④r ①③析取三段论 ⑤┐q∨s 前提引入 ⑥q ②化简

⑦s ⑤⑥析取三段论 ⑧r∧s ④⑦合取

（4）前提：p→(q→r)，s→q，q； 结论：s→r 证明：用附加前提证明法

①s 附加前提引入 ②s→p 前提引入

③p ①②假言推理 ④p→(q→r) 前提引入

⑤q→r ③④假言推理 ⑥q 前提引入 ⑦r ⑤⑥假言推理 由附加前提证明法可知，推理是正确的。

本推理也可以直接证明

①s→p 前提引入 ②p→(q→r) 前提引入

③s→(q→r) ①②假言三段论 ④┐s∨(┐q∨r) ③置换 ⑤┐q∨(┐s∨r) ④置换 ⑥q→(s→r) ⑤置换 ⑦q 前提引入 ⑧s→r ⑥⑦假言推理

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

如果今天是星期六，我们就到颐和园或圆明园去玩；如果颐和园游人太多，我们就不去颐和园玩；今天是星期六，并且颐和园游人太多。所以我们去圆明园玩。

提示 参看命题符号化，推理的前提、结论，构造证明，推理规则，基本等值式。 答案 先将简单命题符号化

解：令p：今天是星期六， q：我们到颐和园去玩， r：我们到圆明园去玩， s：颐和园游人太多。

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

结论：r

证明：①p→(q∨r) 前提引入 ②p 前提引入 ③q∨r ①②假言推理 ④s→┐q 前提引入 ⑤s 前提引入

⑥┐q ④⑤假言推理 ⑦r ③⑥析取三段论

习题

1．判断下面推理是否正确。先将简单命题符号化，再写出前提、结论、推理的形式结构（以蕴涵式的形式给出）和判断过程（至少给出两种判断方法）：

（1）若今天是星期一，则明天是星期三；今天是星期一。所以明天是星期三。 （2）若今天是星期一，则明天是星期二；明天是星期二。所以今天是星期一。 （3）若今天是星期一，则明天是星期三；明天不是星期三。所以今天不是星期一。 （4）若今天是星期一，则明天是星期二；今天不是星期一。所以明天不是星期二。 （5）若今天是星期一，则明天是星期二或星期三。

（6）今天是星期一当且仅当明天是星期三；今天不是星期一。所以明天不是星期三。

1．设p：今天是星期一，q：明天是星期二，r：明天是星期三。

（1）推理的形式结构为 (p→r)∧p→r

此形式结构为重言式，即 (p→r)∧p r 所以推理正确。

（2）推理的形式结构为 (p→q)∧q→p

此形式结构不是重言式，故推理不正确。

（3）推理形式结构为 (p→r)∧┐r→┐p 此形式结构为重言式，即 (p→r)∧┐r ┐p 故推理正确。

（4）推理形式结构为 (p→q)∧┐p→┐q

此形式结构不是重言式，故推理不正确。

（5）推理形式结构为 p→(q∨r)

它不是重言式，故推理不正确。

（6）推理形式结构为 (p r)∧┐p→┐r

此形式结构为重言式，即 (p r)∧┐p ┐r 故推理正确。

推理是否正确，可用多种方法证明。证明的方法有真值表法、 等式演算法。证明推理正确还可用构造证明法。 下面用构造证明法证明（6）推理正确。

前提: p r, ┐p 结论: ┐r

证明: ① p r 前提引入 ② (p→r)∧(r→p) ①置换 ③ r→p ②化简律 ④ ┐p 前提引入 ⑤ ┐r ③④拒取式

所以，推理正确。

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

（1）前提：p→(q→r), p, q 结论：r∨s

（2）前提：p→q, ┐(q∧r), r 结论：┐p

（3）前提：p→q

结论：p→(p∧q)

（4）前提：q→p, q s, s t, t∧r 结论：p∧q

（5）前提：p→r, q→s, p∧q 结论：r∧s

（6）前提：┐p∨r, ┐q∨s, p∧q 结论：t→(r∨s)

答案2． （1）证明：

①p→(q→r) 前提引入 ②p 前提引入

③q→r ①②假言推理 ④q 前提引入 ⑤r ③④假言推理 ⑥r∨s ⑤附加律 （2）证明：

①┐(q∧r) 前提引入 ②┐q∨┐r ①置换 ③r 前提引入

④┐q ②③析取三段论 ⑤p→q 前提引入 ⑥┐p ④⑤拒取式 （3）证明： ①p→q 前提引入 ②┐p∨q ①置换 ③(┐p∨q)∧(┐p∨p) ②置换 ④┐p∨(p∧q) ③置换 ⑤p→(p∧q) ④置换

也可以用附加前提证明法，更简单些。 （4）证明： ①s t 前提引入 ②(s→t)∧(t→s) ①置换 ③t→s ②化简 ④t∧r 前提引入 ⑤t ④化简 ⑥s ③⑤假言推理 ⑦q s 前提引入 ⑧(s→q)∧(q→s) ⑦置换 ⑨s→q ⑧化简 ⑩q ⑥⑨假言推理 q→p 前提引入 p

⑩ 假言推理 p∧q ⑩ 合取

（5）证明：

①p→r 前提引入 ②q→s 前提引入