课后习题答案.doc

部分习题答案及提示第1章1.1答案1 判断下列语句是否为命题，若是，指出其真值。（1） 外面下雨吗？ （否）（2） 7能被2 整除。（是，0）（3） 2x+34，则太阳从西方升起。（1）（2） 若a，则aA。 （1）（3） 胎生动物当且仅当是哺乳动物。 （0）（4） 指南针永指北方，除非它旁边有磁铁。（1）（5） 除非ABCD 是平行四边形,否则它的对边不都平行。（1）2令P：天气好。Q：我去公园。请将下列命题符号化。（1） 如果天气好，我就去公园。（PQ）（2） 只要天气好，我就去公园。（PQ）（3） 只有天气好，我才去公园。（QP）（4） 我去公园，仅当天气好。 （QP）（5） 或者天气好，或者我去公园。（PQ）(6) 天气好，我去公园。（PQ）1.3 答案：1（1）（2）是，其余都不是。2（1）（2）（3）（4）或（5）（6）（7）（8）（9）（10）1.4答案：1（1）000001010011100101110111111101110000100111010110111110000101111101111111（2）000001010011100101110111110111110001100111010000111110011101111100111111（3）0001101110010011111011100010001101101011（4）00011011100100011110101000100010011100012略3甲4上海申花第一，北京国安第二，大连实德第三，长春亚泰第四。5否，否，是6（1）R (2) T (3) 1.5 答案：1（1）重言式（2）可满足式（3）重言式（4）重言式3（1）（2）（3）（4）假；（5）（6）（7）（8）真4（1）表示命题：如果8是偶数，则糖是甜的。（2）：如果糖是甜的，则8是偶数。（3）：如果8不是偶数，则糖不是甜的。（4）：如果糖不是甜的，则8不是偶数。5叙述下列各个命题的逆换式和逆反式，并以符号写出。（1）设：天下雨。：我将留下。则原命题为； 其逆换式为：；其逆反式为：。（2）设：你走。：我不去。则原命题为； 其逆换式为：；其逆反式为：。（3）设：我不能获得更多帮助。：我不能完成这个任务。则原命题为； 其逆换式为：；其逆反式为：。6检验下列论证的有效性。如果我学习（），那么我数学不会不及格（）。 如果我不热衷于玩扑克（），那么我将学习。 但我数学不及格。 因此，我热衷于玩扑克。 7用符号写出下列各式并且验证论证的有效性。如果6是偶数（），则7被2除不尽（）。 或5 不是素数，或7被2除尽。 但5是素数（）。 所以6是奇数。 8 略1.6答案：1（1）（2） （3）2（1）（2）（3）1.7答案：1（1） （2）（3） （4）2（1） （2）3（1）析取范式；合取范式（2）析取范式；合取范式（3）析取范式；合取范式（4）析取范式；合取范式4（1）（2）（3）（4）50；16（1）主析取范式：(PQR)(PQR)(PQR)(PQR)(PQR) ；主合取范式：，(PQR)(PQR)(PQR) （2）主析取范式：（PQ）（QP） 主合取范式：(PQ)(PQ) （3）主析取范式： 主合取范式：=7（1）重言式（2）矛盾式（3）可满足式（4）可满足式8有三种选派方案：去，而、都不去；去，而、都不去；、都去，而不去.9（1）等价（2）不等价1.8答案：1证明证明：2用间接方法证明证明：3设如果2是偶数（），则3是奇数（）；或者2是偶数或者2整除3 （）；结果2不整除3。所以3 是奇数。 上述论断符号化为：，。4某公司若拒绝增加工资，则罢工不会停止，除非罢工超过一年并且公司经理辞职，问：如果公司拒绝增加工资，而罢工又刚刚开始，罢工是否会停止？5“如果下雨，春游就会改期；如果没有球赛，春游就不会改期。结果没有球赛，所以没有下雨。”证明上述论断正确。6如果考试及格，那我高兴。若我高兴，那么我饭量增加。我的饭量没增加，所以我考试没有及格。试对上述论证构造证明。7证明 RS是前提CD，CR，DS的有效结论。8证明PQ , QR, PS , S R(QP)9证明：(ABC)(BA)(DC) (AD)第2 章2.1答案1（1） 其中，：是工人。 ：小王（2） 其中，：是田径运动员。 ：是球类运动员。：他（3）其中，：聪明。 ：漂亮。：小丽（4）其中，：是奇数。 ：， ：2（5）其中，：是有理数。 ：是实数。 （6）其中，：是函数。 ：是连续的。2.2 答案：1（1），其中：是自然数。：比大。（2）或，其中：是鸟。：能飞。（3）或，其中：是麒麟。：是动物。（4）或，其中：是数。：是有理的。2令是人。（特性谓词）（1）令为长头发。则符号化为：（2）令吸烟。则符号化为：（3）令登上过木星。则符号化为：（4令是清华大学的学生。是高素质的。则符号化为：3（1），其中：是人。：是的外祖父。：是的父亲。：是的母亲。（2），其中：是人。：聪明。2.4 答案：1（1）（2）（3）2不正确，第三步的“”应为 “”。3都成立2.5 答案：1（1）（2）（3）（4） 2.6答案：2（1）任何人如果他喜欢步行，他就不喜欢乘汽车。每个人或者喜欢乘汽车或者喜欢骑自行车。有的人不爱骑自行车，因而有的人不爱步行。（设：喜欢步行，：喜欢乘汽车，：骑自行车） 该命题符号化为：证: (1) P (6) P (2) ES (1) (7) US (6) (3) P (8) T(5),(7) I (4) US (3) (9) EG(8) (5) T(2)(4) I （）某学术会议的每个成员都是专家并且是工人，有些成员是青年人，所以，有些成员是青年专家。（3）所有有理数是实数，某些有理数是整数，因此某些实数是整数（设：是有理数，：是实数，：是整数） 该命题符号化为：（2分）证: (1) P (6) T(2) I （1分） (2) ES (1) （1分） (7) T(4),(5) I （1分） (3) P (8) T(6),(7) I （1分） (4) US (3) （1分）(9) EG(8) （1分） (5) T(2) I (4) 每个大学生不是文科生就是理科生，有的大学生是优等生，小张不是理科生，但他是优等生，因而如果小张是大学生，他就是文科生。第3章3.11 （1）； （2）； （3）； （4）2（1）； (2) ；无限集 (3) 3 （1）真； （2）假； （3）真； （4）真； （5）真； （6）假； （7）真； （8）真4 （1）是； （2）否； （3）否； （4）否5 （1）假； （2）假； （3）假； （4）假； （5）真； （6）真； （7）假； （8）假； （9）假6 （1）； （2）； （3）； （4）； （5）7(1) 1）是，是； 2）是，是； 3）是，是； (2) 1）是，是，是，是； 2）是，否，否，是。8， ，3.41 (1) ；(2) ； 3 (1) 否； (2) 是； (3) 是； (4) 去掉；(5) 是； (6) 否； (7) 否； (8) 否； (9) 否；(10) 否 3.51 (1)， (2) ，2，34 3.61（1） 自反性、对称性和传递性； （2）自反性、对称性和传递性；（3）自反性、对称性和传递性；2 的给出证明，对每一个非的给出反例。 自反的反自反的对称的反对称的传递的3，是，不是，因为 但； 不是，因为 但。4， 5设，上的关系的关系矩阵如下，试问是不是自反的、反自反的、对称的、反对称的和传递的？（1）反自反的、反对称的； （2）不具有任何性质； （3）自反的、反对称的；（4）自反的、对称的 （5）自反的、传递的6（1） （2） （3） ？ （4）第4章4.11指出下列各关系是否为到的函数：（1）否 （2）是（3），是，否（4）是，是，否，否。3，4，4.21设分别表示正整数集、整数集、实数集、复数集，试指出下列映射中哪些是单射、满射、双射，并写出定义域和值域。(1) 非单射，非满射， (2) 非单射，非满射， (3) 非单射，满射， (4) 单射 (5) 非单射，非满射，（6）双射，2（1）否， （2）是， (3) 否。3（1）能， （2）能， （3）不能，（4）能，第5章习题5.11（1）封闭 （2）封闭 （3）封闭 （4） 不封闭 （5）不封闭2 是否封闭集 合运 算 是 是 是 是 是 是 是是 否 是 否 是 是 是是 否 是 是 是 是 是否 否 否 是 是 是 是否 否 否 否 是 是 是是 是 是 是 是 是 是3（1）否，乘法运算在上不封闭（2）否，乘法运算在上不封闭（3）是（4）是4（1）否 （2）是 （3）是5（1) 是 （2) 否 （3) 是6（1）否 （2）是7. 7个8 运算表 运算表 1 2 3 4 1 2 3 41 234 0 0 0 01 2 3 42 4 6 83 6 9 121 2341 2 3 42 2 3 43 3 3 44 4 4 49 0 1 2 3 4 5 6 0 1 2 3 4 5 60123456 0 1 2 3 4 5 61 2 3 4 5 6 02 3 4 5 6 0 13 4 5 6 0 1 2 4 5 6 0 1 2 3 5 6 0 1 2 3 4 6 0 1 2 3 4 5 0123456 0 0 0 0 0 0 00 1 2 3 4 5 60 2 4 6 1 3 50 3 6 2 5 1 40 4 1 5 2 6 30 5 3 1 6 4 20 6 5 4 3 2 110证 对于，由于所以，是上的代数运算，因而是代数系统。习题5.21(1)可交换，不幂等，有幺元，每元均可逆：；(2) 不可交换，不幂等，有幺元，有左零元，可逆：，不可逆，但；(3) 不可交换，幂等，有左幺元：，有右零元：； (4)不可交换，不幂等，有左幺元：；2（1）不可结合，不可交换，无幺元，无零元，任何元素均无逆元。（2）可结合，可交换，有幺元0，有零元1，其它元素均无逆元。（3）可结合，可交换，有幺元0，有零元1，当时，无逆元。（4）不可结合，可交换，有无幺元，无零元，任何元素均无逆元。（5）可结合，不可交换，无幺元，无零元，任何元素均无逆元。（6）不可结合，可交换，无幺元，无零元，任何元素均无逆元。3 运 算 可结合性可交换性存在幺元存在零元是 否 是 否 是 是 是 否 是 是 是 是 是 否 是 否 否 否 否 否 是 否 否 否 4 （1）上函数复合运算的运算表为： （2）是的幺元，无零元。（3）和有逆元，且5提示：对一切，记，由于是集合上的可结合的二元运算，所以，故由题设有。6证明：，因为，所以 而 故 即“”对“+”是左可分配的。又因为 而 故 即“”对“+”是右可分配的。因此，“”对“+”是可分配的。7（1）满足幂等律 （2）满足幂等律 （3）不满足幂等律习题5.3 1 不是半群，因为运算“”不满足结合律)。2（2）、（4）和（5）的是半群。3证明：(1) 对封闭。因为是半群，。 (2) 具有结合律。因为：对， (是半群，具有结合律)所以具有结合律。故还是半群。5 是一个独异点，因为关系的复合运算“”是封闭、可结合的，且恒等映射是其幺元。它可交换。6（1）17，-32，14.5 。 2）是半群，可交换。 （3）0。 （4）当时，有逆元素，。10提示：的幺元是4，而的幺元是1，且1。11（2）和都是独异点，是的子独异点，但不是的子独异点。12（1）是半群。（2）的左幺元为，右幺元为。无左幺元，右幺元为。的左幺元为，右幺元为。的左幺元为，右幺元为。无左、右幺元。无左幺元，右幺元为。的左幺元为，无右幺元。（3）左、右零元均为。其它的均无左、右零元。习题5.4 1 是群，因为运算“”是封闭、可结合的，有幺元2，且有逆元，。2只有（1）的是群，其幺元是2，元素的逆元是。8提示：关于矩阵乘法满足封闭性，且矩阵乘法具有结合律，幺元是，而每元的逆元均为自身。9提示：关于映射的复合运算的运算表为： 从该运算表可知，运算封闭，有幺元， ，；而映射复合是可结合的，所以关于映射的复合运算构成群。10提示：(1)设是的子群。 ，由的定义及，都是子群，并从得 ，即；，由是子群知，又由，都是子群，得，所以 ，即；所以。 （2）设。 对，有，使得并且 (结合律) 是子群) （） （结合律） 即知是子群。11提示：因为非空且对，都有，故是的子群。 12提示：既然在左幺元下，都有，使，当然对，存在，满足。于是 且对，有 可见，是的幺元，均有逆元。这就是说是群。 习题5.5 3 是Abel群，而不是Abel群。5提示：因为是非Abel群，必存在使得，这时有，令，则，且。6 的运算表如下表所示。 1 3 4 5 913459 1 3 4 5 93 9 1 4 54 1 5 9 35 4 9 3 19 5 3 1 4从运算表可知，在上封闭、有幺元1，且，再由是可结合的得是循环群，3，4，5和9均为其生成元。7提示：是，生成元有两个：和。 8提示：设，则即为的唯一d阶子群。习题5.6 1是。因为是到的同构映射。2不是到同态映射，因为。3例如：（1）设， 令，则是到的同态。的幺元是，但的幺元是；也是到的同态。的零元是，但的零元是。（2） 6是同构映射，因为是双射。7同态象为或，同态核为。8 ，当均为偶数或均为奇数时，有当为一奇一偶时，有因此f是群的同态映射。因为1是的幺元，所以同态核，同态像为。9（1）是，因为。（2）不是，因为。（3）是，因为。 10提示：是，因为，若，则若，则11证明：首先证是入射。，则有其次证是满射。对综合以上两点，知是双射。 14证明：因为，所以存在，使得。对，若，即，则。由于是有限群，于是，因而，即。所以是单射。又因为是有限群，所以是双射。对于，即保持运算。因此，是上的自同构映射。15证明：假设群和群同构，同构映射为，则,于是，从而，故不是双射，与是同构映射矛盾。所以，群和群不同构。习题5.7 1 是Abel群，故其任一元素关于的左、右陪集均相等。 故对任何非零复数，它是复平面上以原点为圆心，为半径的圆。2 1阶子群有0，其陪集为0，1，2，3，4，5。2阶子群有0，3，其陪集为0，3，1，4，2，5。3阶子群有0，2，4，其陪集为0，2，4，1，3，5。 6阶子群有，其陪集为。3 的左陪集共有个，它们分别是：。4的全部陪集是：，其中是过点以为斜率的直线，因此，的全部陪集是以为斜率的平行直线簇。 5提示：，是子群。但其它的左陪集中均不含，故都不是子群。右陪集的情形一样。6提示：首先证明：(1) ；(2) 对运算“”封闭，且当时，。然后用子群判定命题。7提示：由于左、右陪集集是的划分，故存在使。 下证，即可。事实上，若，则。 若，则存在使，故(否则，由，得到，矛盾!)。习题5.8 1是3（1）不是环，因为除0外，每个元素均无加法逆元。（2）不是环，因为加法不封闭。（3）是交换环、无零因子环，不是含幺环，不是整环。（4）不是环，因为乘法不封闭。（5）是整环。（6）不是环，因为乘法不封闭。6（1）（5）不是域，（6）（7）是域。习题6.11解 是格。不是格，因为不存在。不是格，因为不存在。不是格，因为不存在。2不是格，因为2，3无下确界。3解 (1)是偏序集。 其哈斯图为：(2)是格因为其任意两个元素都有上确界（的最小公倍数）和下确界（的最大公约数）4解 是格，是的子格。5解 由于，的哈斯图如下图所示。根据子格的充要条件知，的所有子格分别为：1个元素的子格：1，2，3，6。2个元素的子格：1，2，1，3 1，6，2，6，3，6。3个元素的子格：1，2，6，1，3，64个元素的子格：.8答案：是格，因为。9证明 设是一个格。若，则是一条只有一个点的链。若，由于，所以或，进而有，于是是一条链。若，由于是的最大元，不妨设为，同时是的最小元，不妨设为，于是有，所以是一条链。习题6.21答案：（a）和(c)是分配格。2（是）4分配格：非分配格：习题6.32答案：（a），(d)和(f)不是有补格。3答案：a与g互补，d与c互补，b和f无补元。4例如：下图中的（a）是分配格不是有补格，而（b）是有补格不是分配格。5答案： 它们都不是有补格，它们都是分配格。习题6.41答案：（b），(e) 和(f) 是布尔代数。 （a）不是布尔代数，因为它没有个元素。 (c) 不是布尔代数，因为没有补元。 (d) 不是布尔代数，因为它不是分配格。（g） 不是布尔代数，因为它没有个元素。（h） 不是布尔代数，因为没有补元。2（1）；（2）；（3）；(4) 。3证明 设是布尔代数且，则中存在唯一的异于0和1的元素，由于，所以，故在中不存在补元，这与是布尔代数矛盾。所以不存在3个元素的布尔代数。4证明：（3）若，则。反之，若，则且，于是有，故有。5（7）若，其中是个不同的素数，则是布尔代数。6设是一个布尔代数，上的二元运算定义为：证明是一个Able群。证明：(1) 因为为一布尔代数，所以=()()，即关于 “”封闭。 （2）对，同理所以“”是可结合的。 （3）对， 所以0是，的幺元。（4）对，所以。（5），综上，是一个交换群7设是一个布尔代数，上的二元运算定义为：证明是一个以1为幺元的环。证明：1.先证是一个Able群。(1) 因为为一布尔代数，所以=()()，即关于 “+”封闭。（2）对，同理所以“+”是可结合的。 （3）对， 所以0是的幺元。（4）对，所以。（5），综上，是一个交换群2.再证为一个半群。(1) 因为为一布尔代数，所以，即关于 “”封闭。（2）对，所以“”是可结合的。故为一个半群。3. 证“”对“+”可分配。对， 4.又，所以1是的幺元。综上知是一个以1为幺元的环。8证明 由于是同构映射，所以。由于，所以。若不是的原子，则存在满足，由于是同构映射，所以存在，使得，又由于，所以，且，因此，这与是原子矛盾。 所以的原子。习题6.51（1）；（2）；（3）；（4）；（5）；（6）；（7）；（8）。2答案： 0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1 0 1 0 0 1 1 1 1 0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 11 0 1 1 1 0 1 13的析取范式为：的合取范式为：4答案：的析取范式为： 的合取范式为：习题6.61第7章7.1 答案：1（3）不是简单图。3由同构定义具体地构造同构映射可证4（1）16；（2）137.2答案：1（3）3；（4）=24()是强连通图，()是单侧连通图，()是弱连通图5强分图1，2，3，4，5，6 单侧分图1，2，3，4，5，6 弱分图1，2，3，4，5，67.31（1）（2），（3）2200个34根据的主对角线元素是否为0可以判断是否有经过的回路。7.4答案：1不可以，可以2为奇数3（1）最少加条边；（2）由（1）即得。4构造一个有9个结点、27条边的具有有向欧拉回路的有向图。5图()、图()是欧拉图。6没有。用汉密尔顿图的必要条件判断。7（1）一个结点的度数表示其对应的人所认识的人数。（2）是连通图表示任意两个人可以通过朋友的一次或多次介绍而相互认识。（3）如果中任何一对结点的度数之和都大于等于，则中存在汉密尔顿路。 8设是的起点为终点为的汉密尔顿路，在中添加连接，的边，得到一新图，则此新图为汉密尔顿图。再利用定理7.4.3证明。7.51求下面两个二部图的最大匹配。答案：图的最大匹配为；图的最大匹配为；2假定是二部图，如何安排中顶点的次序可使的邻接矩阵呈 形式，0为零矩阵。3某单位有7个工作空缺要招聘，有10个应聘者。他们能胜任的工作岗位集合分别为：，。如果规定每个应聘者最多只能安排一个工作，试给出一种分配方案使落聘者最少？4设图是二部图，证明。证明：设，则，。 由，得 （1）将代入（1）式，得推得 ，所以7.61 图7-76