离散数学习题解
(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
前提引入 ①置换 ②化简 前提引入 ④化简 ③⑤假言推理 前提引入 ⑦置换 ⑧化简 ⑥⑥假言推理