离散数学习题解

(b)先化简公式

F??(?p??q?r) ??(p??q??r) ??(?p?q?r) ??(p?q??r) ??q??((?p?r) ??(p??r)) ?q??((?p?r) ??(p??r)) ??(?q?q) ??((?p?r) ??(p??r)) ??(?p?r) ??(p??r)

???(??(?p?r) ???(p??r)) (已为{?, ?}中公式) (c) F??(?p?r) ??(p??r) ????(?p?r) ??(p??r) ???(?p?r) ??(p??r) ??(p??r) ???(?p?r) ??(r?p) ???(p?r) (已为{?, ?,?}中公式)

9

2.28.一个排队线路, 输入为 A,B,C, 其输出分别为 FA,FB,FC. 本线路中, 在同一时间内只能有一个信号通过, 若同

时有两个和两个以上信号申请输出时, 则按 A,B,C 的顺序输出. 写出 FA,FB,FC 在联结词完备集{?, ?} 中的表达式.

根据题目中的要求, 先写出 FA,FB,FC 的真值表(自己写) 由真值表可先求出他们的主析取范式, 然后化成{?, ?}中的公式 FA?m4?m5?m6?m7 ?p FB?m2?m3 ??p?q FC?m1 ??p??q?r

(已为{?, ?}中公式)

(已为{?, ?}中公式)

(已为{?, ?}中公式)

2.29. 略 2.30. 略

离散数学习题解 10

习题三

3.1. 略 3.2. 略 3.3. 略 3.4. 略 3.5. 略

3.6. 判断下面推理是否正确. 先将简单命题符号化, 再写出前提, 结论, 推理的形式结构(以蕴涵式的形式给

出)和判断过程(至少给出两种判断方法):

(1)若今天是星期一, 则明天是星期三；今天是星期一. 所以明天是星期三. (2)若今天是星期一, 则明天是星期二；明天是星期二. 所以今天是星期一. (3)若今天是星期一, 则明天是星期三；明天不是星期三. 所以今天不是星期一. (4)若今天是星期一, 则明天是星期二；今天不是星期一. 所以明天不是星期二. (5)若今天是星期一, 则明天是星期二或星期三. (6)今天是星期一当且仅当明天是星期三；今天不是星期一. 所以明天不是星期三.

设 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 故推理正确.

11

推理是否正确, 可用多种方法证明. 证明的方法有真值表法, 等式演算法. 证明推理正确还可用构造证明法.

下面用构造证明法证明(6)推理正确. 前提: p?r, ?p 结论: ?r 证明: ① p?r

② (p?r) ??(r?p) ③ r?p ④?p ⑤?r 所以, 推理正确.

前提引入 ①置换 ②化简律 前提引入 ③④拒取式

3.7. 略 3.8. 略

3.9. 用三种方法(真值表法, 等值演算法, 主析取范式法)证明下面推理是正确的:

若 a 是奇数, 则 a 不能被 2 整除. 若 a 是偶数, 则 a 能被 2 整除. 因此, 如果 a 是偶数, 则 a 不是奇数.

令 p: a 是奇数; q: a 能被 2 整除; r: a 是偶数. 前提: p ???q, r ??q. 结论: r ???p.

形式结构: (p ???q) ??(r ??q) ??(r ???p). ……

3.10.略 3.11.略 3.12.略 3.13.略

3.14.在自然推理系统 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) (1)证

明:

12

① ② ③ ④ ⑤ ⑥

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

前提引入 ①置换 ②化简 前提引入 ④化简 ③⑤假言推理 前提引入 ⑦置换 ⑧化简 ⑥⑥假言推理