离散数学第二版课后答案.docx

1、离散数学第二版课后答案离散数学第二版课后答案【篇一：离散数学答案 屈婉玲版 第二版 高等教育出版社课后答案】第二版 高等教育出版社课后答案 第一章部分课后习题参考答案 16 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。 （1）p(qr)? 0(01) ?0 （2）（p?r）(qs) ?（0?1）(11) ?01?0. （3）（?p?qr）?(pqr) ?（111） ? (000)?0 (4)（?rs）(p?q) ?（01）(10) ?00?1 17判断下面一段论述是否为真：“?是无理数。并且，如果3是无理数，则2也是无理数。另外6能被2整除，6才能被4整除。” 答：p: ?是

2、无理数 1 q: 3是无理数 0 r: 2是无理数 1 s: 6能被2整除 1 t: 6能被4整除 0 命题符号化为： p(qr)(ts)的真值为1，所以这一段的论述为真。 19用真值表判断下列公式的类型： （4）(pq) (?q?p) （5）(pr) ?(?p?q) （6）(pq) (qr) (pr) 答： （4） p q pq ?q?p?q?p (pq)(?q?p) 0 01 111 1 0 11 011 1 1 00 100 1 1 11 001 1所以公式类型为永真式 （5）公式类型为可满足式（方法如上例） （6）公式类型为永真式（方法如上例） 第二章部分课后习题参考答案3.用等值演算

3、法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) ?(pqq) (2)(p(pq)(pr) (3)(pq)(pr) 答：(2)（p(pq)）(pr)?(?p(pq)(?pr)?ppqr?1 所以公式类型为永真式 (3) p qr pq pr （pq）(pr) 0 0000 1 0 0100 1 0 1010 0 0 1110 0 10 010 0 10 111 1 11 010 0 11 111 1 所以公式类型为可满足式 4.用等值演算法证明下面等值式： (2)(pq)(pr)?(p(qr) (4)(p?q)(?pq)?(pq) ?(pq) 证明（2）(pq)

4、(pr) ? (?pq)(?pr) ?p(qr) ?p(qr) （4）(p?q)(?pq)?(p(?pq) (?q(?pq) ?(p?p)(pq)(?q?p) (?qq) ?1(pq)?(pq)1 ?(pq)?(pq) 5.求下列公式的主析取范式与主合取范式，并求成真赋值 (1)(?pq)(?qp) (2)?(pq)qr (3)(p(qr)(pqr)解： （1）主析取范式 (?pq)(?q?p) ?(p?q)?(?q?p) ?(?p?q)?(?q?p) ? (?p?q)?(?q?p)?(?q?p)?(p?q)?(p?q) ? (?p?q)?(p?q)?(p?q) ?m0?m2?m3 ?(0,2

5、,3) 主合取范式： (?pq)(?q?p) ?(p?q)?(?q?p) ?(?p?q)?(?q?p) ?(?p?(?q?p)?(?q?(?q?p) ?1?(p?q) ?(p?q) ? m1 ?(1) (2) 主合取范式为： ?(pq)?q?r?(?p?q)?q?r ?(p?q)?q?r?0 所以该式为矛盾式. 主合取范式为(0,1,2,3,4,5,6,7) 矛盾式的主析取范式为 0 (3)主合取范式为： (p?(q?r)(p?q?r) ?(p?(q?r)(p?q?r) ?(?p?(?q?r)?(p?q?r) ?(?p?(p?q?r)?(?q?r)?(p?q?r) ?1?1 ?1所以该式为永真

6、式. 永真式的主合取范式为 1 主析取范式为(0,1,2,3,4,5,6,7) 第三章部分课后习题参考答案 14. 在自然推理系统p中构造下面推理的证明： (2)前提：p?q,?(q?r),r 结论：?p (4)前提：q?p,q?s,s?t,t?r 结论：p?q 证明：（2） ?(q?r) 前提引入 ?q?r 置换 q?r蕴含等值式 r前提引入 ?q 拒取式 p?q前提引入 p（3） 拒取式 证明（4）： t?r 前提引入 t化简律 q?s 前提引入 s?t 前提引入 q?t 等价三段论 （q?t）?(t?q) 置换 （q?t） 化简 q 假言推理 q?p前提引入 p假言推理 (11)p?q

7、合取 15在自然推理系统p中用附加前提法证明下面各推理： (1)前提：p?(q?r),s?p,q 结论：s?r 证明 s附加前提引入 s?p前提引入 p 假言推理 p?(q?r) 前提引入 q?r假言推理 q 前提引入 r假言推理 16在自然推理系统p中用归谬法证明下面各推理： (1)前提：p?q,?r?q,r?s 结论：?p 证明： p结论的否定引入 p?q 前提引入 q 假言推理 r?q 前提引入 r 化简律 r?s 前提引入 r化简律 r?r 合取 由于最后一步r?r 是矛盾式,所以推理正确. 第四章部分课后习题参考答案 3. 在一阶逻辑中将下面将下面命题符号化,并分别讨论个体域限制为(

8、a),(b)条件时命【篇二：离散数学课后答案(第1,2,4章)武汉大学出版社】）否 （2）否 （3）是，真值为0 （4）否 （5）是，真值为1 2、（1）p：天下雨 q：我去教室 p q （2）p：你去教室 q：我去图书馆 p q （3）p，q同（2） q p （4）p：2是质数q：2是偶数 pq 3、（1）0 （2）0 （3）1 4、（1）如果明天是晴天，那么我去教室或图书馆。 （2）如果我去教室，那么明天不是晴天，我也不去图书馆。 （3）明天是晴天，并且我不去教室，当且仅当我去图书馆。 习题1.2 1、（1）是 （2）是 （3）否 （4）是 （5）是 （6）否 2、（1）(p q) r，p

9、 q，r，p，q （2）(pq) （rp），p q，rp，p，q，r，p （3）(p q) (q p) (p q)，(p q) (q p)，(p q)，p q，(q p)，p q，p，q，q，p，p，q 3、（1）(p q) (q p) (p q) （2）(p q) (p q) r) (p q) (p q) r) （3）(q pp) (pp q) 4、(p q) (pq) (pq) (pq) 习题1.3 1、（1）i(p(qr) = i(p)(i(q)i(r) = 1(10) = 1 （2）i(pqr)(pq)(rs) = (110)(11)(01) = 0(00) = 0 （3）i(pr)(

10、qs) = (10)(11) = 01 = 0 （4）i(p(qrp)(qs) = (1(1(01)(11) = 11 = 1（5）i(pq)r(qp)rs) = (11)0(11)(01) = 011 = 1 2、（1） p q pq q(pq) q(pq)p 0 0 1 0 1 0 1 1 1 0 1 0 0 0 1 1 1 1 1 1 （2） p q r qr (p(qr) pq pr (pq)(pr) 原式 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 1 0 0 0 1 0 0 1 1 0 0 0 0 1 1 1 0 1 1 1 0 1 0 0 0 0 1 1 1 0

11、1 0 1 0 0 1 1 1 0 1 1 0 0 0 1 1 1 0 1 1 1 1 0 1 1 1 0 （3） p q r pq qp pqqp pr 原式 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 1 0 1 0 0 0 1 0 1 1 1 0 0 0 1 1 0 0 1 0 0 1 1 1 0 1 1 0 0 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 0 3、（1）原式 = fq = t原式为永真式 （2）原式 = t(pq)(qp) = (pq)(qp) = (pq)(pq) = t原式为永真式 （3）原式 = (pq) (pq)

12、= t原式为永真式 （4）原式 = p(qr) p(qr) = t原式为永真式 （5）原式 = (pq)q = (pq)q = q原式为可满足式 （6）原式 = (pq)p = pqp = tq = t 原式为永真式 （7）原式 = (ppq)p = (tq)p = tp = p 原式为可满足式 （8）原式 = (pq) (qr)(pr) = (pq)(qr)(pr) = (pq)p)(qr)r) =( pp)(qp)( qr)(rr) = (qp)( qr) = t原式为永真式 4、（1）左 = pqp = p(pq) = 右 （2）左 = (pq) = 右 （3）左 = (pq)p = p

13、qp = tq = 右 （4）左 = (pq)(qp) = (pq)(qp) = 中 = (pq)q)(pq)p) = (pq)(qq)(pp)(qp) = (pq)(pq) = 右 (5)左 ( p q) ( r q) (p q) q 右 5.(1)左 q p q 右 (2)(p (q r) (p q) (p r) ( p q r) ( p q) ( p r) (p q r) (p q) p r (p q r) (p p) ( q p) r (p q r) ( q p r) (p q r)(p q r) t 故p (q r) (p q) (p r) (3).(p q) (p p q) ( p

14、 q) p (p q) ( p q) ( p p) ( p q) ( p q) ( p q) t 故p q p p q (4).(p q) q) p q ( ( p q) q) p q ( p q) q) p q ( p q) (q q) p q (p q) (p q) t 故(p q) q p q (5).(p p) q) (p p) r) (q r) ( t q) ( t r)q r (q r) q r q r q r q t t 故(p p) q) (p p) r) q r (6)左 (q f) (r f) ( q f) ( r f)q r r r q 右 6.(1)原式 ( p q r

15、) (2)原式 p q p (p q p) (3)原式 p (q r p) p q r ( p q r) 7.(1)原式 ( p q p) (2)原式 ( p q r)p q ( ( p q r) p q) (3)原式 p q (r p)(p q (r p) 8. (1) (p q) ( p ( p q) r) p (2)(p q r) ( p r) (3)(p f) (q t) 习题1.4 1.(1)原式 ( p q) ( p q) (q p) ( p q) (q p) (p q) q p q p,既是析取范式又是合取范式 (2)原式 ( p q) ( p q) ( ( p q)( p q)

16、 (p q) (p q) 析取范式 p (q q)合取范式 (3)原式 p q s ( p q)析取范式 ( p ( p q) q s p q s合取范式 (4)原式 p p q q r既是析取范式又是合取范式 2.(1)原式 p q r为真的解释是：000，001，011，100，101，110，111 故原式的主析取范式为: ( p q r) ( p q r) ( p q r) (p q r) (pqr) (p q r) (p q r) (2)原式 (p q) r (p q (r r) (p p) r) (p q r) (p q r) (p q) ( p r) (p q r) (p q r

17、) (p (q q) r) ( p (q q) r) (p q r) (p q r) (p q r) (p q r) ( p q r) ( p q r) (p q r) (p q r) (p q r) ( p q r) ( p q r)为真的解释是101，100，111，011，001 (3)原式 ( p (q r) (p ( q r) ( p (q r) p) ( p (q r) ( q r)( p p) (q p r) ( p q r) (q r q r) (p q r) ( p q r) 为真的解释是：000,111 (4)原式 p p q q r p q r为真的解释是：001，010

18、，011，100，101，110，111 故原式的主析取范式为： ( p q r) ( p q r) ( p q r) (p q r) (p q r) (p q r) (p q r) 3.(1)原式 p q p q t主合取范式，无为假的解释。 (2)原式 (p q r) ( p q r) ( p q r) ( p q r) 为真的解释为：111，011，001，000，故为假的解释为：010，100，101，110 原式的主合取范式为： (p q r) ( p q r) ( p q r) ( p q r) (3)由2.(2)知，原式为真的解释是：101，100，111，011，001，故为假

19、的解释是：000，010，110. 故原式的主合取范式为：(p q r) (p q r) ( p q r) (4)由2.(4)知，原式为假的解释是：000，故原式的主合取范式为：p q r 4.(1)左式 ( p q) ( p r) ( p q (r r) ( p (q q) r) ( p q r) ( p q r) ( p q r) 右式 p (q r) ( p q) ( p r) ( p q r) ( p q r) ( p q r) 故原式成立。 (2)左式 （pq）（pq）， 右式 （pp）(qp) p（pq） p （pq）（pq）， 故原式成立 (3)左式 （pq）（pq） f，主析取

20、范式 右式 （pq）（pq） f， 故原式成立 (4)左式 t（pq） t，主合取范式 右式 （pq）（pq） t， 故原式成立 习题1.5 1.（1）pq 前提 p ，化简 p(qr) 前提 qr ，mp q ，化简 r ，mp【篇三：离散数学课后习题答案二】列出关系?a，b，c，d?|a，b，c，d?z且a?b?c?d?6中所有有序4元解 ?a，b，c，d?|a，b，c，d?z且a?b?c?d?6 ? ? 组。 ?1,1,1,6?,?1,1,6,1?,?1,6,1,1?,?6,1,1,1?,?1,1,2,3?,?1,1,3,2?,?1,2,1,3?,?1,3,1,2?, ?1,2,3,1?

21、,?1,3,2,1?,?2,3,1,1?,?3,2,1,1?,?2,1,3,1?,?3,1,2,1?,?2,1,1,3?,?3,1,1,2? 2. 列出二维表3.18所表示的多元关系中所有5元组。假设不增加新的5元组，找出二维表3.18所有的主键码。 表3.18 航班信息 解 略 3. 当施用投影运算?2,3,5到有序5元组?a，b，c，d?时你能得到什么？ 解 略 4. 哪个投影运算用于除去一个6元组的第一、第二和第四个分量？ 解 略 5. 给出分别施用投影运算?1,2,4和选择运算?航空公司nadir到二维表3.18以后得到的表。 解?2,3,5对航班信息二维表进行选择运算?航空公司nad

22、ir后得到的二维表 6. 把连接运算j3用到5元组二维表和8元组二维表后所得二维表中有序多元组有多少个分量？ 解 略 7. 构造把连接运算j2用到二维表3.19和二维表3.20所得到的二维表。 解 零件供应商二维表与零件数量和颜色代码二维表连接运算2结果 第4章：群、环、域 习题4.1 1. 判断下列集合对所给的二元运算是否封闭。 （1）集合nz?n?z|z?z关于普通加法和普通乘法运算，其中n是正整数。 ，n?z关于普通加法和普通乘法运算。 （2）集合s?x|x?2n?1 1关于普通加法和普通乘法运算。 （3）集合s?0， n? s?x|x?2，n?z关于普通加法和普通乘法运算。 （4）集合

23、 ? （5）n阶(n?2)实可逆矩阵集合mn(r)关于矩阵加法和矩阵乘法运算。 ? 对于封闭的二元运算，判断它们是否满足交换律、结合律和分配律，并在存在的情况下求出它们的单位元、零元和所有可逆元素的逆元。 解 略 2. 判断下列集合对所给的二元运算是否封闭。 （1）正实数集合r和*运算，其中*运算定义为： ? ?a，b?r?，a?b?a?b?a?b ?，an，n?2。*运算定义为： （2）a?a1，a2， ?a，b?a，a?b?b 对于封闭的二元运算，判断它们是否满足交换律、结合律和等幂律，并在存在的情况下求出它们的单位元、零元和所有可逆元素的逆元。 解 （1）不封闭，例如：0.5?0.5?0

24、.5?0.5?0.5?0.5?0.75?r （2）封闭。 不满足交换律：?a,b?a，a?b?b?a?b?aa?b?bb?a?a 满足结合律：?a,b?a(a?b)?c?b?c?c，a?(b?c)?a?c?c 满足等幂律：?a?aa?a?a ? a1，a2，?，an都是左单位元，但无右单位元。 a1，a2，?，an都是右零元，但无左零元。 因为无单位元，所以无逆元。 3. 设s?q?q，这里q是有理数集合，*为s上的二元运算， ?u，v?，?x，y?s， ?u，v?x，y?ux，uy?v? （1）*运算在s上是否可交换、可结合？是否为等幂的？ （2）*运算是否有单位元、零元？如果有，请指出，并

25、求s中所有可逆元素的逆元。 （3）*运算在s上是否满足消去律？ 解 略 ?，f6。?x，y?r有 4. r为实数集合，定义以下六个函数f1， f1(?x，y?)?x?y f3(?x，y?)?|x?y| f2(?x，y?)?x?y f4(?x，y?)?xy f6(?x，y?)?max(x，y) f5(?x，y?)?min(x，y)（1）指出哪些函数是r上的二元运算。 （2）若是r上的二元运算，说明是否是可交换的、可结合的、等幂的？ （3）若是r上的二元运算，在存在的情况下求出单位元、零元以及每个可逆元素的逆元。 （4）若是r上的二元运算，说明是否满足消去律。 解 略 ，2，?，10，问下面定义的

26、运算*在g上是否封闭？对于封闭的二元运5. 设g?1 算，请说明运算是否满足交换律、结合律，并并在存在的情况下求出运算的单位元、零元和所有可逆元素的逆元。 （1）x?y?gcd(x，y)，gcd(x，y)表示x与y的最大公因数。 （2）x?y?lcm(x，y)，lcm(x，y)表示x与y的最小公倍数。 （3）x?y?大于等于x和y的最小整数。 （4）x?y?质数p的个数，其中x?p?y。 解 （1）封闭。满足交换律，满足结合律，满足等幂律。无单位元，1是零元。因为无单位元，所以无逆元。 5)?15?g （2）不封闭，例如：3?5?lcm(3， （3）封闭。满足交换律，满足结合律，满足等幂律。1

27、是单位元，10是零元。1的逆元为1，其他无逆元。 （4）封闭。不满足交换律，不满足结合律，不满足等幂律。无单位元，无零元。因为无单位元，所以无逆元 4.2 半群与群 习题4.2 1. 设g是所有形如 a12?0? ?是半群吗？是有么半群吗？这里的矩阵组成的集合， *表示矩阵乘法。试问?g， ?a11 ?0? a11、a12是实数。 ?a11a12?b11b12?0?00?0g?、 a?b?解 任取中的2个元素 、 ?a11a12?b11b12?a11b11a11b12?0?0?00?00?g a?b? ?g，?是一个代数系统。?是 且因为矩阵的乘法满足结合律，所以?g， 半群。 又因为，只要a111，则 ?a11 ? a?b?0a12?b11b12?a11b11 ?00?0?*?0a11b12?b11b12? ?00?0?b?1a12?00? ?是左单位元（不论a12取什么值）对任何的b?g成立，即?。但右单位元不存在， 因为不论b11，b12取什么值， ?a11a12?b11b12?a11b11?0?0?00?0 a?b? 不可能对任何的a?g成立。 ?不是有么半群。 所以?g， 2. 在正实数集合r上定义运算*如下 ? a11b12?a1