离散数学习题与解答.docx

1、作业题与解 答 第一 章 19 (2)、 (4)、 (6) 21 (1)、 (2)、 (3) 19、 (2) 解答 : (p p) q真值表如下 : p q p q p p (p p) q 0 0 1 1 1 1 0 1 1 0 1 0 1 0 0 1 0 1 1 1 0 0 0 1 19、 (4) 所以公式 (p q) q为 可 满足 式 解答 : (p q) ( q p)真值表如下 : p q p q p q q p (p q) ( q p) 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 0 0 1 1 1 所以公式 (p q) ( q p)为

2、永真 式 19、 (6)解答 : (p q) (q r) (p r)真值表如下 : p q r p q q r p r (p q) (q r) (p q) (q r) (p r) 0 0 0 1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 1 0 1 1 1 0 1 0 0 0 1 1 1 1 1 1 1 1 1 所以公式 (p q) (q r) (p r)为永真 式 21、 (1)解答 : ( p q) r真值表如下 : p q r p r p q ( p q) ( p q

3、) r 0 0 0 1 1 0 1 1 0 0 1 1 0 0 1 1 0 1 0 1 1 1 0 1 0 1 1 1 0 1 0 0 1 0 0 0 1 0 1 1 1 0 1 0 0 0 1 1 1 1 0 0 1 0 1 1 1 1 1 0 0 0 1 1 所以成假赋值为 :011 21、 (2) 解答 : ( q r) (p q)真 值 表如下 : p q r q q r p q ( q r) (p q) 0 0 0 1 1 1 1 0 0 1 1 1 1 1 0 1 0 0 0 1 0 0 1 1 0 1 1 1 1 0 0 1 1 0 0 1 0 1 1 1 0 0 1 1 0 0

4、 0 1 0 1 1 1 0 1 1 1 所以成假赋值为 :010,100,101,110 21、 (3)解答 : (p q) ( (p r) p)真值表如下 : p q r p q p r (p r) (p r) p (p q) ( (p r) p) 0 0 0 1 0 1 1 1 0 0 1 1 0 1 1 1 0 1 0 1 0 1 1 1 0 1 1 1 0 1 1 1 1 0 0 0 0 1 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 1 1 1 1 1 1 1 0 1 1 所以成假赋值为 :100,101 第二 章 5、 (1)(2)(3) 6、 (1)(2)(

5、3) 7、 (1)(2) 8、 (1)(2)(3) 5、求 下 列公式的主析 取 范式 ,并求成真 赋值 (1) ( p q) ( q p) ( p q) ( q p) ( ( p) q) ( q p) ( p q) ( q p) ( p q) (p q) (p q) m0 m2 m3， 所 以 00， 10， 11为成真赋值 。 (2) ( p q) (q r) ( p q) (q r) (p q) (q r) (p q r) (q r) (p q r) (p q r) ( p q r) (p q r) ( p q r) m3 m7， 所 以 011， 111为 成真赋值 。 (3) (p

6、(q r) (p q r) (p (q r) (p q r) ( p ( q r) (p q r) ( p q) ( p r) (p q r) ( p q) ( p r) (p q r) ( p q) ( p p q r) ( r p q r) ( p q) (1 1) ( p q) 1 1 m0 m1 m2 m 3 m4 m5 m6 m7， 所 以 000,001,010,011,100,101,110,111为 成 真 赋 值 。 7、求下列公 式 的主析取范式 ， 再用主析取范 式 求主合取范 式 (1) (p q) r (p q r) (p q r) (p r) ( p r) (p q

7、 r) (p q r) (p r q) (p r q) ( p r q) ( p r q) (p q r) (p q r) (p q r) ( p q r) ( p q r) m1 m3 m5 m6 m7 由主析取范式 和 主合取范式之 间的关系，所以 公 式的主 合 取范式为 ： (p q) rM0 M2 M4 (2)(p q) (q r) ( p q) ( q r) ( p ( q r) (q ( q r) ( p q) ( p r) (q q) (q r) ( p q) ( p r) (q r) ( p q r) ( p q r) ( p q r) ( p q r) (p q r) (

8、p q r) ( p q r) ( p q r) ( p q r) (p q r) m0 m1 m3 m7 由主析取范式 和 主合取范式之 间 的关系，所以 公 式 的 主合取范式为 ： (p q) (q r)M2 M4 M5 M6 8、 求 下 列公式的主合 取 范式，再用主 合 取范式求主析 取 范 式(1)(p q) q (p q) q ( p q) q p ( q q) p 1 1该公式无主合 取 范式，所以公 式的 主析取范式为 ： (p q) qm0 m1 m2 m3 (2)(pq) r ( p q) (p q) r (p q) ( p q) r (p ( p q) ( q ( p

9、 q) r (p p) (p q) ( q p) ( q q) r (p q) ( q p) r (p q r) ( p q r) M0 M6 由主合取范式 和 主析取范式之 间 的关系，所以公 式的主 析 取范式为： (pq) rm1 m2 m3 m4 m5 m7 (3) (r p) p q ( r p) p q (r p) p q r ( p p) q r 0 q0 M0 M1 M2 M3 M4 M5 M6 M7 该公式无主析 取 范 式 第三 章 14 (2)、 (4)、 (5) 15 (1)、 (2) 16 (1) 14、 在自 然推理系 统 P中 构造下面推理 的 证 明(2)前提

10、： p q, (q r),r 结 论： p 证 明： (q r) 前 提引 入 q r 置 换 r 前提引 入 q 析取三段 论 p q 前提引 入 p 拒取 式 （ 4）前提 ： q p,q s,s t,t r 结论 ： p q 证明： 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,p q 结论 ： r s 证明 : p q 前提引 入 p 化 简 q

11、化 简 p r 前提引 入 r 假言推 理 qs 前提引 入 s 假言推 理 r s 合 取 15、在自然推 理 系 统 P中用附 加 前提法证明下 面 各推理 ：(1)前提： p (q r),s p,q 结论 ： s r 证明： s 附加前提引 入 s p 前提引 入 p 假言推 理 p (q r)前提引 入 q r 假言推 理 q 前提引 入 r 假言推 理 (2)前提： (p q) (r s),(s t) u 结 论 ： p u 证 明 ： p 附加前提引 入 p q 附 加 (p q) (r s) 前提引 入 r s 假言推 理 s 化 简 s t 附 加 (s t) u 前提引 入

12、u 假言推 理 16、在自然推 理 系 统 P中用归 谬 法证明下面推 理：(1)前提： p q, r q,r s 结 论 ： p 证 明 : p 结论 否 定引 入 p q 前提 引入 q 假言推 理 r q 前提引 入 r 析取三段 论 r s 前提引 入 r 化 简 r r 合取 (矛 盾 ) 为 矛 盾式， 由 归谬法可知， 推 理正确 。 第四 章 5、 (1)(2)(3)(4) 10、 (2)(4) 11、 (2)(6) 5、 在 一 阶逻辑中将下 列 命题符号化 ：(1)火车都比轮船 快。 xy(F(x) G(y) H(x,y)， 其中， F(x)： x是火车， G(y)： y是轮船 ， H(x,y):x比 y快 。 (2)有的火车 比 有的汽车快 。 xy(F(x) G(y) H(x,y)，其 中， F(x):x是 火车 ， G(y)： y是 汽 车， H(x,y):x比 y快 。 (3)不存在 比 所有火车都快 的 汽车 。 x(F(x) y(G(y) H(x,y)