离散数学答案.pdf

习题答案习题答案 第 1 章 1 1 3 4 5 6 7 8 9 2 3 1 1 3 3 0 1 0 0 1 1 1 0 2 1 2 0 2 abcda ba ca db cb dc da b ca b da c db c da b c d 3 1 3AB 1 2 3 4 5 6ABC 4 6CA 2 5AB 4 45ABxx 3ABx x 34ABxx 345ABxxx 或 5 6 12MN 2 3 4 6 8 9 10 12MN 6 10 11 12 13 14 15ABC ABC 10 11 12 13 14 15ABC 7 1 2 3 8 1 不一定 如 1 A 2 B 1 C 2 不一定 如 1 A 1 B CB 3 不一定 如 1 A 1 2 B 1 C 4 一定 A是B中元素 而B中任一元素都在C中 故CA 5 不一定 如 1 A 1 2B CB 6 不一定 如 1 A 1 2 B CB 7 不一定 如 1 A 1 2 B CB 8 不一定 如 1 A 1 2B 1 C 9 正确的有 1 3 对 1 因为 a b中每个元素 只有a和b 均在集合 a b c a b c中 对 3 因为 a b中每个元素 只有a和b 均在集合 a ba b中 对 2 集合 a b c a b c中含有 4 个元素 分别为 a b ca b c 没有 a b 对 4 集合 a ba b中含有 3 个元素 分别为 a ba b 没有 a b 10 1 2 可以用定义证明 3 由集合差运算的等价定义YXYX 有 ABCABCABC ABCABCABC ACBACBABC ACBCACBCACBC ACBACCABCABC 故有 ABCABCACBACBC 11 1 ABBAB 2 ABCBCAA 3 BACABCB 4 ABCABAB 5 ABCABCABCABCA 12 1 2 4 错误 3 5 正确 1 如 A 1 B 2 C 2 如 1 2 A 1 B 2 C 3 证 由条件有AABABB 同理有BA 得AB 4 如 1 A 1 2 B 3 C 3 4 D 5 证 CDDC 又由AB 得ADBC 即ADBC 13 1 Paa 2 Paa 3 P 4 P 5 Pababababab 6 P 14 由题意有 P A B 根据元素与集合的关系及集合与集合的 关系 1 2 3 均正确 15 1 3 4 正确 2 错误 16 P AP BP AB 因为 AP A 有AB 但其逆不成立 例如 令 A B 则AB 但 P A P B 显然 P AP B 17 ABabab BAabab AAa ab aa bb b BB 18 3 3ABCab 3 3ABA Cab 1 2 3 1 2 3ABaaabbb 3 4 3 4A Caabb 19 32 20XYx yxy 32 20YXy xxy 其图形表示分别如右所示 20 直接由定义可证 21 1 x yABAB 有xAB yAB 从而xA 或xB yA 且yB 故 x yAA 或 x yBB 得证 ABABAABB 2 证明类似 22 不构成划分 除非A是单元集 23 1 2 4 均不是划分 3 是划分 24 依题意 n个人每个人握手的次数均在 1 和1n 之间 由鸽巢原理 相当于将n个介于 1 和1n 之 间的整数根据其数值的多少对应放入1n 个编号从 1 到1n 的盒子中 至少有两个数在同一个盒子里 知至少有两个人握手次数相同 25 1 记每个整数被 3 除后的余数分别为 A B C D 则四个数只能取 0 1 2 因此至少有两个数相 同 从而至少有两个数除以 3 的余数相同 2 若记每个数被 p 除后的余数分别为 121 p b bb 则此 p 1 个数只能取 0 1 p 故至少有两个 数相同 从而 121 p a aa 至少有两个数模 p 同余 26 1 否则若每一种颜色至多有 12 个小球 四种颜色至多有 48 个小球 矛盾 本题可用鸽巢原理的推广形式来证明 这相当于把 50 个小球放入 4 个盒子中 则至少有一个盒子 至 少有 50 1 113 4 个小球颜色相同 2 依题意 有 42 个三种颜色的小球 同上推理 至少有 14 个小球有相同颜色 27 3 元素集的非空子集共有 3 217 个 其和共有 7 个 考虑被 6 除后的余数 至少有两个是相同的 XY YX XX Y Y 从而至少有两个不同的非空子集 其和是模 6 同余的 28 用n个编号的盒子分别放 12 n a aa 现将 i b分别放到编号为i的盒子里 1 2 in 由于n为 奇数 12 n a aa 中存在有 2 1 n 个奇数 则必存在一个盒子 其中的两元素的奇偶性相同 否则对应 装有 2 1 n 个奇数元素 i a的盒子里应该对应地放入 2 1 n 个偶数 而1 2 n 中只有 2 n 个偶数 矛盾 29 为简单起见 设做对A题的学生构成的集合为A 做对B题的学生构成的集合为B 做对C题的学 生构成的集合为C 由题意可知 12ABC 20AB 16AC 28BC 48A 56B 16ABC 12016104ABC 根据容斥原理可知 ABCABCABACBCABC 20162810412485652C 故做对C题的学生有 52 个 30 1 不含有 3 和 7 的有7 8 8448 故至少含有 3 或 7 的有 900 448 452 2 用 A 表示含有数字 3 的集合 用 B 表示含有数字 7 的集合 则 8 9 9A 为不含 3 的集合的 基数 8 9 9B 为不含 7 的集合的基数 7 8 8448AB 为不含 3 和 7 的集合的基数 而 648648448848ABABAB 故由 ABUAB 有 90084852AB 第 2 章 1 这里只给出关系矩阵 关系图略去 1 1 00000 00000 11100 11100 11100 R M 2 2 10000 11000 11100 11110 01111 R M 3 3 00000 01111 01010 01101 01010 R M 4 4 01111 00111 11111 11111 00000 R M 5 5 00010 00010 00010 11110 00000 R M 2 1 0 0 0 2 2 0 2 2R 2 1 1 4 2R 3 0 1 2 3 4R 1 2 3 4R 0 0 1S 1 1 0S 0 0 1 2 3 4T 1 1 2 3 4T 4 1 0 0 0 1 0 2 1 1 1 2 2 2R 2 0 1 0 2 1 2R 3 0 0 1 1 2 2R 4 0 0 0 1 0 2 1 0 2 0R 5 0 0 0 1 0 2 1 1 2 1R 6 0 0 0 1 0 2 1 0 1 1 2 0R 7 1 1R 8 R 9 1 0 1 1 2 2R 5 1 因acbd 可写为abcd 直线xyK K为整常数 上任意的两整数点具有关系 1 R 不在同一直线上的点不具有关系 1 R 2 平面上两整数点之间的距离若小于等于 10 则它们具有关系 2 R 若两整数点在直线xyK K为整常数 上或两整数点之间的距离小于等于 10 则两整数点具有关系 12 RR 若两整数点在直线xyK K为整常数 上且两整数点之间的距离大于 10 则两整数点具有 关系 12 RR 若两整数点在直线xyK K为整常数 上且两整数点之间的距离大于 10 或者两整数点 之间的距离小于等于 10 且两整数点不同时在任何直线xyK K为整常数 上 则两整数点具有关系 12 RR 6 12 RRa ca da b 21 RRc d 2 1 Ra d 2 2 Rb bc c 7 0 2 0 3 1 3R R 8 1 1 1 1 2 2 2 2 3 3 1 3 3R 2 R为全关系 2 1 1 1 3 2 2 3 1 3 3R 2 1 1 1 3 2 2 3 1 3 3R 3 2 2 3 1R 2 2 2R 关系矩阵分别为 1 1 1 1 1 1 1 1 1 1 2 101 010 111 3 000 010 000 9 1 Ra bb cc a 2 Ra cb ac b 10 1 反对称 传递 2 自反 反对称 3 对称 4 都不具有 5 对称 11 R对称 S自反 对称 传递 12 有许多组例子可以作为答案 下面是一组可能的答案 1 1 1 2 2R 2 1 2 2 1 2 3R 3 1 2R 13 101 001 100 010 M R 1010 0001 1100 T M RM R 1 因为 1110 1100 1010 0001 M R RM RM R 对称 所以R R 对称 2 因为 101 010 101 M R RM RM R 对称 所以R R 对称 3 显然由上面关系矩阵可以判断两个关系均是自反 对称的 要判断是否等价只需判断传递性 可以根据关系矩阵是否出现这样情形 有1 ij r 1 jk r 而0 ik r 若发生了 则不是传递的 否 则是传递的 因 RRM 没有发生此情形 故R R 是传递的 而对 RRM 因 21 1r 131r 而 23 0r 故R R 不是可传递的 14 根据条件可直接得到关系矩阵 1100 0001 0000 0000 M R 0001 0011 0100 0000 M S 0011 0000 0000 0000 M R S 0000 0000 1000 1000 M R S 2 0000 0000 0000 0000 MR S 由矩阵可知 2 R S 是空关系 从而可知它是反自反 反对称 对称 传递的 15 若S是反自反的 则xX x xS 从而IS 反过来 若IS 则 x xI 有 x xS 从而S是反自反的 16 x zR R 由关系复合的定义 存在yA 使得 x yR y zR 因R传递 有 x zR 可得R RR 另一方面 x yR 因R自反 y yR 由R传递 x yRR 可得RR R 综合可得RRR 17 用反证法 若R不是反对称的 则 x yX xy 使得 xRy yRx 由R RR 有xRx 与 R反自反矛盾 故假设不成立 R是反对称的 18 R是传递 2 RR R RR R RR R 传递 本题也可直接利用定义证明 19 这个推论不正确 根据定义 R对称指 如果aRb可得bRa 但对每一个元素Aa 可能不存在 满足这一条件的不同的b 上面的假设是建立在每个元素都存在有与它有关系R的其它元素的假设之 上的 而当此假设不满足时 则全部论证失效 例如 Aa b c A上的关系 Ra bb aa ab b 则R是对称的 传递的 但不 是自反的 因为 c cR 20 因任一关系R对称的充分必要条件是 RR 证明分两个方面 若R S 对称 即 R SR S 由关系复合与其逆的复合之间的关系 有 R SS R 由条件 R S 对称 有 RR SS 从而有 R SSR 另一方面 若R SSR 则两边取逆 并利用关系的对称性及复合关系所具有的性质 有 R SSRR SR S 从而SR 对称 21 因4 3R 3 1R 但4 1R 故R是不可传递的 取 1 1 2 4 3 2 2 2 1 1 1 3 1 4 1R 则 1 R是可传递的 且 1 RR 取 2 1 2 4 3 2 2 2 1 1 1 3 1 4 1 3 3R 则 2 R是可传递的 且 2 RR 实际上 S上的全关系就是满足条件的一个传递关系 22 1 t Ra aa ba ca db ab bb cb dc a c bc cc dd ad bd cd d 实际上是集合上的全关系 2 t R Ra aa ba ca db cb dd cd d 23 其传递闭包右图 2 1 所示 24 根据关系矩阵与其对应关系的闭包的关系矩阵之间的联系 有 110 010 001 M r R 010 100 001 M s R 110 110 001 M rs R 110 110 001 M sr R 110 110 001 M tsr R 25 0100 1010 0001 0000 R M 1100 1110 0011 0001 r R M 0100 1010 0101 0010 s R M 1111 1111 0001 0000 t R M 下面图 2 2 分别是R及R对应的自反闭包 r R 对称闭包 s R和传递闭包 t R a b c d 图 2 1 26 2 0 0 1 0 1 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 R M 3 1 0 0 0 1 0 0 1 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 R M 4 0 1 0 0 1 0 0 0 1 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 R M 5 0 0 1 0 1 0 1 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 R M 63 1 0 0 0 1 0 0 1 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 RR MM 故 2345 111010 111010 111010 000000 000010 111010 t RR RRRR MMMMMM 由 t R M易确定 rst R M 1 111011 111011 111011 000100 111011 111011 A rst Rt RI t R MMMM 27 1 xN xx 是偶数 有xRx R自反 若 x yR 即xy 是偶数 则xy 是偶数 有 y xR R对称 若 x yR y zR 即xy 是偶数 yz 是偶数 则 2xzxyyzy 是偶 数 有 x zR R传递 由以上证明 R是等价关系 2 关系R的等价类有 1 1 3 5 R 0 0 2 4 6 R 3 设 fNN 0 1 x f x x 为偶数 为奇数 则f所诱导的等价关系是R 28 1 因为任意整数m 有 22 mm 故mRm 自反 若mRn 即 22 mn 则 22 nm 即nRm 对称 若 mRn nRp 即 22 mn 22 np 则 22 mp 即mRp 传递 由此得证R等价 2 R iii 则R的等价类有 0 1 2 RRR a b a b a b a b d c d c d c d c R r R s R t R 图 2 2 29 首先证明R是等价的 a 对任意的 x yA 因xyxy 故 x yRx y R自反 b 对任意 x yAu vA 若 x yR u v 即xyuv 则uvxy 从而 u vRx y R对称 c 若 x yR u v u vRp q 即xyuv uvpq 从而xypq 得证 x yRp q R传递 综上所述 R是等价关系 由定理知由R的等价类确定对集合A的划分 1 1 1 1 2 2 3 3 R 1 2 1 2 2 1 2 3 3 2 3 4 R 1 3 1 3 3 1 2 4 R 1 4 1 4 R 即划分 1 1 1 2 1 3 1 4 RRRR 30 等由于集合A为笛卡尔积 即序偶的集合 因此R考虑的是序偶与序偶之间的关系 1 只需证明三个方面 对 a bA 因为abab 有 a bRa b R自反 对 a bc dA 若 a bRc d 即abcd 有cdab 从 而 c dRa b R对称 对 a bc de fA 若 a bRc d c dRe f 即abcd cdef 有abef 从而 a bRe f R传递 由 可知R是等价关系 2 因A中元素为 ASS 1 1 1 2 1 3 1 4 2 1 2 2 2 3 2 4 3 1 3 2 3 3 3 4 4 1 4 2 4 3 4 4 根据等价类的定义 可求得 1 11 1 R 1 21 2 2 12 1 RR 1 31 3 2 2 3 12 23 1 RRR 1 41 4 2 3 3 2 4 12 33 24 1 RRRR 2 42 4 3 3 4 23 34 2 RRR 3 43 4 4 34 3 RR 4 44 4 R 从而 有 1 1 1 2 1 3 1 4 2 4 3 4 4 4 RRRRRRR A R 31 当R等价时 容易证明结论 下面证明另一方面 需证R等价 1 R自反 已知条件 显然 2 R对称 若 a bR 因R自反 有 a aR 从而由条件有 b aR 3 R传递 若 a bR b cR 则由已证对称 b aR 加上 b cR 由条件有 a cR 32 1 x yAB 则有xA yB 1 R和 2 R分别为A和B上的自反关系 因 1 x xR 2 y yR 故 x yx yR 所以R具有自反性 2 1122 x yxyAB 若 1122 x yxyR 则 121 x xR 且 122 y yR 1 R 和 2 R分别为A和B上的对称关系 有 211 xxR 212 yyR 从而 2211 xyx yR R具 有对称性 3 11 x y 22 xy 33 xyAB 若 1122 x yx yR 且 2233 xyx yR 则有 121 x xR 122 y yR 231 xxR 232 yyR 因 1 R和 2 R分别为A和B上传递关系 有 131 x xR 132 y yR 从而 1133 x yxyR R具有传递性 综上所述 可知R是BA 上的等价关系 33 RSSR 不一定自反 也不一定传递 从而不一定是等价关系 例如 1 2 3 A R为全关系 从而一定等价 1 1 1 2 2 1 S 则 2 2 3 3 1 3 3 1 2 3 3 2RSSR 显然 RSSR 不自反也不传递 但 RSSR 一定具有对称性 下面给出证明 因S对称 从而SS 从而 RSSRRSSR 因两对称关系的差仍然对称 且两对称关系的并也对称 从而 RSSR 对称 34 1 AAR 不 是A上 的 等 价 关 系 例 如 1 2A 1 1 2 2R 则 1 2 2 1AAR 不是自反的 当然不等价 2 RS 不等价 例如 1 2A 1 1 2 2 1 2 2 1R 1 1 2 2S 则 1 2 2 1RS 不是传递的 不等价 3 是等价的 4 不是等价的 例如 1 2 3A 1 1 2 2 3 3 2 3 3 2S R为A上全关 系 则 1 1 2 2 3 3 1 2 2 1 1 3 3 1r RS 不是传递的 因为2 1 r RS 1 3 r RS 而2 3 r RS 35 R是等价关系 A的关于R的等价类为 1 1 4 R 2 2 3 6 R 5 5 R 36 显然R是A上的等价关系 有 1 5 2 4 6 3 8 7 A R 37 根据划分可以得到等价关系 从而可得 acaccbabcabaccbbaaR ffeggedggddeedggeedd edddbdebbbccaccaaaS ggfggfffeedebedb 从而关系SR 为 deedaccaggffeeddccbbaaSR 对应的关系图如图 2 3 所示 其商集 gfedbcaSRA 38 根据集合间的相互关系 可得 ABE c AB ABB AB cc BA cc AB ABB BA c AB AB a c d e b f g 图 2 3 即 q r u相互等价 s w z相互等价 y v相互等价 p t相互等价 且相互之间不等价 从而可得 X Rp tq r us w zy v 39 由于不同的等价关系对应不同的划分 不同的划分也对应着不同的等价关系 故只需求出集合A的不 同的划分 1 有 15 个不同的划分 有 15 个不同的等价关系 首先注意A的每个划分包含或 1 或 2 或 3 或 4 个不同的块 具体划分是 1 0 1 2 3 A 2 0 1 2 3 A 3 1 0 2 3 A 4 2 0 1 3 A 5 3 0 1 2 A 6 0 1 2 3 A 7 0 2 1 3 A 8 0 3 1 2 A 9 0 1 2 3 A 10 0 2 1 3 A 11 0 3 1 2 A 12 1 2 0 3 A 13 1 3 0 2 A 14 2 3 0 1 A 15 0 1 2 3 A 2 对 5 个元素构成的集合的划分 分下面几种情况 a 只有一块 有 1 种分法 b 分为两块 即一块有 1 个元素 另一块有 4 个元素 共有 1 5 5C 种分法 或一块有 2 个元素 另一块有 3 个元素 共有 2 5 10C 种分法 b 分为三块 即两块各 1 个元素 第三块 3 个元素 共有 2 5 10C 种分法 或两块各 2 个元素 第三块 1 个元素 共有 12 54 215CC 种分法 d 分为四块 即三块各 1 个元素 第四块 2 个元素 共有 3 5 10C 种分法 e 分为五块 每块 1 个元素 共有 1 种分法 故共有 1510101510152 种不同的分法 40 RS RS 均为相容关系 41 易证S是自反 对称的 从而是相容关系 42 由极大相容类的定义 可得 图 1 中的极大相容类为 5 6 1 2 3 4 3 6 2 5 图 2 中的极大相容类为 1 2 3 1 3 6 3 5 6 4 43 由于R是自反 对称的 它是X上的相容关系 它的极大相容类的全体构成X的一个完全覆盖 1253424 x xxx xxx 44 1 不是偏序关系 因为R不传递 事实上 若aRb bRc 即2ab 2bc 则有4ac 一 般来说2ac 即aRc 2 是偏序关系 因为集合的包含关系是自反 反对称 传递的 45 1 R的关系矩阵为 11111 01101 00111 00011 00001 R M 2 因为 b cR c dR 但 b dR 故R不具备传递性 不是偏序关系 实际上 也可通过计算 2 R的关系矩阵来说明 2 11111 01111 00111 00011 00001 R M 从而 2 R R MM 不成立 故不具有传递性 46 R所对应的关系矩阵为 11111 01101 00101 00011 00001 M R 由关系矩阵可知 对角线上所有元素全为 故R自反 1 jiij rr 故R反对称 可计算出 2 R对 应的矩阵为 2 11111 01101 00101 00011 00001 M RM R 由以上矩阵可知R传递 所以 R是偏序关系 所对应的哈斯图如图 2 4 所示 47 偏序集 A R的哈斯图如图 2 5 所示 48 不是偏序 不满足反对称性 例如 Z 则 且 说明 不具 有反对称性 49 直接由定义证明即可 50 略 51 1 所对应的哈斯图如图 2 6 所示 它的最大元为 24 极大元为 5 24 最小元为 1 极小元为 1 2 所对应的哈斯图如图 2 7 所示 它的最大元不存在 极大元为 8 9 10 11 最小元不存在 极 小元为 2 3 11 52 1 A R的哈斯图如图 2 8 所示 2 写出集合A中的最大元 24 最小元不存在 极大元 24 极小元 2 和 3 3 2 3 6 12B 的上界有 12 24 下界不存在 最小上界为 12 最大下界不存在 53 A R的哈斯图如图 2 9 所示 A的最大元为e 最小元为a 极大元为e 极小元为a 54 由 B可知A非空且至少含有 2 个元素 Ax x为极小元 因为不存在A的子集 xY 使得 xY xA 为极大元 因为不存在A的子集 xAY 使得 xAY 除非AY 而 BA 不存在最小元和最大元 55 B的最大元为 6 最小元为 3 极大元为 6 极小元为 3 上界有 6 18 下界有 3 上确界为 6 下确 e d c b a 图 2 4 54 18 27 6 9 2 3 1 图 2 5 24 8 12 5 4 3 2 1 图 2 6 8 10 9 4 2 11 3 图 2 7 24 8 12 4 6 2 3 图 2 8 e b d c a 图 2 9 界为 3 56 B的上界为 e f 下界为 a b 上确界为e 下确界不存在 57 1 是偏序关系 2 是拟序关系 3 以原点为圆心 5 为半径的圆面 圆周上只含3 4 点 4 以原点为圆心 5 为半径的圆面 包括整个圆周 说明 不是偏序关系 因为不具有反对称性 如3 44 3 4 33 4 58 它们的哈斯图分别如图 2 10 所示 其中 2 是全序 也是良序 59 所有不同的偏序集的哈斯图有 5 个 如图 2 11 中 1 至 5 所示 第 3 章 1 1 3 是函数 根据函数的定义 若每一个元素存在惟一的象 则为函数 2 1 是函数 不是单射 也不是满射 2 不是函数 3 不是函数 4 是函数 是双射 5 是函数 不是单射 也不是满射 3 1 1 1 2 2 3 3 4 4 5 5 S I 1 5 2 4 3 3 4 2 5 1f 1 3 2 3 3 3 4 4 5 5g 1 1 2 1 3 2 4 3 5 4h 2 关系图如下图所示 3 S I和f是单射 也是满射 g h不是单射也不是满射 4 单 满 双 函数的象 集合S 的原象 若f为双射 写出 1 f 1 f xx 单 满 双 R 8 f xx 2 2xf x 单 满 双 R 0 2 logf xx 3 1f nn n 单 1 n nnN 空集 4 21f nn 单 全体正奇数 1 5 f xx 满 N 0 1 1 6 1 24 x f x 单 31 44 1 2 0 7 3f x 3 R 8 1 1 x f x 单 0 1 1 3 4 2 1 2 4 3 2 4 2 1 1 4 3 1 3 1 2 3 4 图 2 10 1 2 3 4 5 图 2 11 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 S I f g h 图 3 1 9 1 x f x 单 1 空集 5 由复合函数的定义 有 3 3 191fgzg f zzz 3 31 295g h zh g zzz 3 3 3 12275fg h zh g f zzz 6 1 1 1ffnn 2 22fg nn 3 21gfnn 4 0g h n 5 0 2 n h g n n 为偶数 为奇数 6 0fgh nh g f n 7 1 因为 AP N 有union A AAAA inter A AAAA sym AAA 因此它们都是满射 2 因为union union NA inter inter NA sym sym N NA AAN 故都不是单射 8 1 若 f nf m 则11nm 从而nm 故f为单射 但 0 不存在原象 故不是满射 2 1 0nN g nn n 故g是满射 但 0 1 gg 故不是单射 3 max 0 1 max 0 N fg xg f xf xxxIx 故 N Ifg 但 0 0 1 1 1 gff gf gfg 故fg 不是单射 从而不相等 9 2 N fg ng f ngnnIn 所以 N gfI 2 1 2 1 f nnn gf nf g n fnnn 为偶数 为奇数 nIN 所以有 N fgI 10 先证S是一个偏序关系 a 因 0 1 x 对任意fX 有 0f xf x 故 f fS 即S在X上是自反的 b 若对 0 1 x 对 f gX 有 f gS 且 g fS 则对 0 1 x 有 0f xg x 且 0g xf x 从而 f xg x 即S在X上反对称 c 若 对 0 1 x 有 f g hX 使 得 f gS 且 g hS 即 对 0 1 x 有 0f xg x 且 0g xh x 从而 0f xh x 故 f hS 得证S在X上传递 综上可得 S是X上的偏序关系 下面说明S不是全序 例如 1f xx g xx 因 0 0 1fg 1 1 1gf 故f 与g是不可比的 即S在X上不是全序关系 11 由f的定义 因xx 有 xf x x yA 若 f xf y 则有 xf xf y 即xy 同理可证yx 由于偏序是反对称的 有xy 证得f是单射 当ba 时 xf a 有xa 由于偏序是传递的 有xb 即 xf b 证得 f af b 12 根据定义可得 1 1 2 G 2 3 G 3 G G显然是单射 不是满射 P A中有 8 个 元素 其值域 ran 1 2 3 G 13 1 1122 x yxyRR 若 1122 fx yfxy 即 11112222 xy xyxyxy 则 1122 1122 xyxy xyxy 易得 1212 xxyy 从而f是单射 2 p qRR 由 fx yp q 通过计算可得 2 2 xpq ypq 从而 p q 的原 象存在 f是满射 3 由上面的证明可知 f存在反函数 且 1 22 xy xy fx y 4 1 22 xy xy ffx yfx y 2 2ffx yfx y x yx yx yx yx yx y 14 1 0010 0100 0100 0100 f M R 0001 0010 0100 1000 g M R 2 0100 0010 0010 0010 fg M RR 0100 0010 0010 0010 g f M R 3 对应矩阵的转置即为所求 0000 0111 1000 0000 f M R 0001 0010 0100 1000 g M R f R 不是函数 g R 是函数 15 三者之间的关系是 11 ffBBff B 下面给出证明 1 yffB 则 1 xfB 从而yB 使得 f xy 使得 f xy 从而有 yyB 得证 11 ffBBff B xB f xf B 从而有 1 xff B 得证 1 Bff B 综上所述 有 11 f fBBff B 16 法 1 对任意yY 因为g是映射 故存在 zg yZ 由于gf 是满射 对zZ 存在xX 使得 gf xg f xz 由于g是单射 有 f xy 所以对任意的Yy 存在xX 使得 f xy 故f是满射 法 2 假定f不是满射 则有 f XY 即存在yY yf X 又由g是函数 则有 g yzZ 因gf 是满射 故对zZ 必存在xX 使得 gfxz 取 f xy 有 g yz 而yy 但 g yg y 故g不是单射 与假设矛盾 得证f是满射 17 3 个命题均错误 例如 1 2 S Ta 1 2 faa 1 1 A 2 2 A 则有 1 12 f Af Aa 而 12 f AAf 2 12 f Af Aaa 而 12 1 f AAfa 3 21 AfaAf 但 12 AA 18 1 sS 由条件知 gfshfs 即 shfsgf 因为f为单射 所以 有 g sh s 从而gh 2 例如 1 S Ta b 0 U 0f x 1 ga 1 hb 则 0gf xf g x 0hf xf h x 但gh 3 f为满射时 结论成立 下面证明 对任意bB 因f是满射 存在aA 使得 f ab 由fgfh 得 g f ah f a 即 g bh b 从而gh 19 1 因为 1 2 121 2 1 ff 但1 22 1 从而f不是单射 因为0N 没有原象 从而f不是满射 1 1 12fNnnNnN n 2 显然f是单射 若 f xf y 即 1 1x xy y 易得xy 又因2 4NN 没有原象 从而f不是满射 0 1 2 0 1 1 2 2 3f 3 容易说明f不是单射 1 42 2ff 但1 42 2 f是满射 yN 有 1 1fyyy 任一元素都存在有原象 1 1f NnnNN 1 0 0 0 0 fx yxyNN 20 1 由定义易知f不是单射 因为 3 4250 5ff 但3 40 5 2 f不是满射 因不存在 x yNN 使得 22 6fx yxyN 即N 6无原象 3 122 0 00 0fx yxy 4 2222 0 0 1 2 00 12 0 5 f 21 这里函数 222 XXX f g fA BABBAB g A BBABBA 根据集合相等的定义可以证明 1 2 4 是正确的 3 式左右两边不相等 事实上 1 因 ABBA 故 fA Bg A B 2 因 fA BAB g B AAB 从而 fA Bg B A 3 ffA BBf A BBABBAB fA fA BAf A BAABAB 故 ffA BBfA fA B 4 fA g A BAg A BABAA g f B AAAf B AABAA 故 fA g A Bg f B AA 从而有结论 1 正确 2 正确 3 错误 4 正确 第 4 章 1 D 对运算不封闭 2 2 5 6 对运算可结合 3 1 f 2 f 3 f可交换 4 f满足幂等律 2 f有单位元 1 f有零元 4 给出的例子如下所示 a 0 1 a b a b a a 0 0 0 a a b a a a 1 0 1 b b a b a a ba bb ab 0 1 均为左零元 1 为右单位元 a b 0 1 0 1 a a b 0 0 0 0 1 0 b a a 1 1 1 1 1 1 5 1 可交换 a是单位元 a b c d均可逆 且 1 aa 1 bd 1 cc 1 db 2 不可交换 b是单位元 b可逆 且 1 bb a c d均不可逆 6 A C D 均构成半群 7 D 构成独异点 8 1 S 3 S是子代数 9 0 0 2 0 1 2 3共有三个子代数 10 1 满足交换律 x y zR 因 2224446 xyzxyzxyxzyzxyzxyz 故满足结合律 2 设226xyxyxyx 即 2 3 0 xy 故2x 或3y 2 是零元 3 是单位 元 3 对任意元素xR 设2263xyxyxy 则当2x 即不为零元 时 有逆元为 23 2 x y x 11 1 a b cQ 易证 abcabc 故 Q 是半群 因a bba a bQ 故 可 交换 2 设e为其单位元 则应有 aQ aeeaa 即aeaea 由a的任意性 有0e 所以单位元为 0 3 设a有逆元b 则应有 0ababab 故当1a 时 有逆元为 1 1 a a a 当1a 时 没有逆元 12 显然 是S上二元运算 对于任意的Szyx 有 xyzxyazxayazxayaz xayzxyz 是可结合的 故 S 也是一个半群 13 1 1 N 自然数集 2 0 0 3 1 2 Z 4 ZZ 5 2 3 2 3 4 6 6 9 18N 正整数集 14 1 010100 100 010 001001 2 023080000 004 000 000 000001001 3 010001100010 100 100 010 001 001010001100 15 1 是 2 不是 因为当0 n时 n在P中无逆元 3 是 4 不是 结合律不成立 5 是 6 是 7 不是 结合律不成立 8 是 9 不是 除零次多项式外 均没有逆元 10 是 16 2 是不可结合 不是半群 除 2 外运算均满足结合律 对 1 存在单位元 但不是每个元素均存在逆元 故是含幺半群 对 3 不存在单位元 故是半群 对 4 存在单位元 但不是每个元素均存在逆元 故是含幺半群 可以验证 对 5 存在单位元 10 01 且 1 01 x G 有 111110 0101010101 xxxx 故每个元素 1 01 x G 存在逆元 1 01 x 是群 17 4 5 6 构成群 18 由A生成的子群为 1 4 5 2 3 方程 2 3 4AX 的解为 1 2 3 5 X 19 由a aa 两边同时左乘 1 a 即得 11 aaa aaae 20 显然 是二元运算 根据群的定义 需证运算满足结合律 有单位元 每个元素有逆元 a b cZ 有 2 2 24 a bca bcabcabcab c 故 a bcab c 结合律成立 2 是单位元 事实上 222aaa 222aaa aZ aZ 由 4 4 22aaaa 4 4 22aaaa 可知4a 是a的逆元 由上可知 Z是群 21 M对运算 构成群 首先 a bc dM 有 a b c dR 且 0a c 于是 ac adbR 且0ac 从 而 a bc dac adbM 是M上的二元运算 其次 a bc de fM 有 a bc de fa bc de f 结合律成立 1 0 是M上关于 的单位元 事实上 a bM 有 1 0 1 0 a baaba b 1 01 10 a baba b 最后 a bM 11 aa b 是 a b 的逆元 事实上 1111 1 0a baa ba aaa bb 11111 1 0aa ba ba aa ba b 得证 M是群 22 由条件 有 ab abaa bb 由于是群 运算满足结合律和消去律 有 a ba ba ab b 故 abba 23 x和 1 x 的阶数相同 又当x的阶数大于 时 1 xx 注意到映射 1 fxx 是群的一个双射 从 而阶数大于 2 的元素成对出现 x和 1 x 是一对 故其个数必为偶数 24 由于群中阶数大于 2 的元素个数是偶数 上题 又单位元是群中惟一的一个阶数为 的元素 而群中 总元素个数 群的阶 为偶数 故阶为 的元素必有奇数个 25 当 1 xx 时 x和 1 x 在群中成对出现 其总的个数必为偶数 因此 在群中 1 xx 即 2 xe 的元 素个数也为偶数 e满足 2 ee 故除e以外 至少还有一个a 使得 2 ae 26 因G为群 x yG 且 12 yxyx 故 2 42111122 xxyxyyxyy yxyyy xy 因y是 2 阶元 有 2 ye 且 2 ye 故 4 xx 有 3 xe 又x的阶不可能为 2 或 1 否则 2 xe 由 12 yxyx 可得yxy 从而xe 矛盾 故x的阶为 3 27 由H非空 知 1 x H x 非空 1 a bx H x 即存在 12 h hH 使得 11 12 ax hxbx hx 有 11111111111 121212 a bx hxx hxx hxxhxxh hx 因H为 子 群 有 1 12 hhhH 从而 111 a bx h xx H x 所以 1 x H x 为子群 28 因 4 S是有限群 只需说明运算封闭就可以了 1 4 是子群 可以举例说明 2 3 均不为子群 对 2 或 3 如 12341234 22413412 fgA fgA 对运算不封闭 29 需证R具有自反 对称 传递性 xG 因为 1 xexe 其中e为G中单位元 故xRx R自反 a bG 若aRb 即G 使 1 ba 则 1111 abb 因G为群 G 有 1 G 故bRa R对称 a b cG 若aRb bRc 即 1 G 使 1 11 ba 2 G 使 1 22 cb 则 111 21122121 caa 因 12 G 有 12 G 故aRc R传递 得证R等价 30 假设AG 且BG 则 aA aB 且 bB bA 否则对任意的aA 有aB 从而AB 即ABB 得BG 矛盾 对元素a bG 若a bA 因A是子群 1 aA 从而 1 aa bbA 故矛盾 得a bA 同理可证a bB 综合有a bABG 综上所述 假设不成立 得证AG 或BG 31 不构成 32 设G的单位元为e 则eHH 是G的一个子群 因H的左陪集的全体构成G的划分 即H的左陪 集或者相同 或者不相交 故其它左陪集均不含e 而作为子群 至少必须含有单位元 故除H外 其它 左陪集均不是G的子群 33 设 Ga 为循环群 则对任意 x yG k xa l ya 从而 k ll k xyaay x 故G是 循环群 34 略 35 x y zB 因f是满射 存在 x y zA 使得 f xx f yy f zz 于是 由f是 同态 有 xyzf xf yf zf xyf zfxyz f xyzf xf yzf xf yf zxyz 所以 是可结合的 设eA 是G的单位元 ef eB 则 xef xf e f x ef x x 同理可证 exx 故e 是B的单位元 又对于xB 因为 111 xf xf xf xf xxf ee 同理可证 1 f xxe 故Bxf 1 是x 的逆元 综上所述 证得H是一个群 且f是G到H的同构映射 从而G与H同构 36 1 Ker 0 h 2 Ker hZ 3 Ker 5hZ 4 Ker 0 h 37 1 12121212 f x xx xxxf xf x f xx 是G到G的 同 态 Im fR Ker 1 1 f 2 121212121212 2 4 f x xx xf xf xx xf x xf xf x 故 2f xx 不是G到G的同态 3 222 12121212 f x xx xx xf xf x 故 2 f xx 是G到G的同态 Im fR Ker 1 1 f 4 12121212 1 11 f x xx xxxf xf x 故 1f xx 是G到G的同态映射 Im fG Ker 1 f f是G的自同构 5 1212121212 f x xx xf xf xxxx x 有 1212 f x xf xf x 故 f xx 不 是G到G的同态映射 6 1212 1f x xx x 1212 1 1 f xf xxx 1212 f x xf xf x 故 1f xx 不 是G到G的同态映射 38 需证f是双射且为同态 若 f xf y 即 11 ax aay a 由群的消去律可知xy 故f 是单射 又对gG 有 111 f agaaagaag 故f是满射 因对任意的 x yG 有 111 f xyaxyaax aayaf xf y 故f是自同态映射 综上所述 f是G的自同构 39 A的一一变换共有3 6 个 它们分别是 1 a b c 2 abc 3 a bc 4 acb 5 ab c 6 ac b 其中只有 1 和 5 是自同构 首先 1 和 5 都是双射 再由于 f xyf ccf xf y 故f是同态映射 故只有 1 5 是自同构 而 2 3 4 6 不是 40 1 ae对运算封闭 单位元为ae 的逆元为a 运算满足结合律 故 ae在 下是群 2 设 e aM 则M的所有右陪集有 M Mba bMcb c Mdc e 若G 为群 则应满足GG MM 而实际上 5G 2M 4G M 故G不是群 41 1 由同态基本定理的推论 12 34KGh G 2 4K 3 12 43G KGK 42 1 因为对任意的 11 0101 xy H 有 111 010101 xyxy H 故H对运算是封 闭的 且因矩阵运算是可结合的 只需说明H存在单位元 每个元素有逆元即可 显 然 10 01 H 是 单 位 元 且 因 111110 0101010101 xxxx 故 1 11 0101 xx 每个元素都存在逆元 2 因 010