四川大学出版编的离散数学课后习题答案.pdf

1 习习题题参考解答参考解答 习题习题 1 1 1 3 P 银行利率降低 Q 股价没有上升 P Q 5 P 他今天乘火车去了北京 Q 他随旅行团去了九寨沟 QP 7 P 不识庐山真面目 Q 身在此山中 Q P 或 P Q 9 P 一个整数能被 6 整除 Q 一个整数能被 3 整除 R 一个整数能被 2 整除 T 一个整数的各位数字之和能被 3 整除 P Q R Q T 2 1 T 2 F 3 F 4 T 5 F 6 T 7 F 8 悖论 习题习题 1 3 1 3 RPQP RPQPRQPRQP 2 4 PQQRRPPRQRP PRRPQRP PRPRQRQP 右 2 不 不 能 习题习题 1 4 1 3 PRQPPRQP PRTPRPRQQ PRQPRQ 主合取范式 QPRPQRPQR RQPRQPRQP QPRQPRPQRPQR RQPRQPRQPRQP QQPRPPQRRRQQP PRQRP PQRP PQRP 主析取范式 2 PQPRPQPR PQRRPRQQ PQRPQRPRQ 2 PQRPQR PQPR PQRPQRPRQ 等价 3 3 解 解 根据给定的条件有下述命题公式 根据给定的条件有下述命题公式 A C D B C C D A C D C D B C C D A B C D B C D B A C C D C C D C C D 3 A B C D B C D B A C C D C C D A B C C D B C C D B C A C C C D C C A B D C D B D C D B D A C D C D C D 由题意和矛盾律 C D B A C C D C D B C D B A C D B A A C B A C B C D A C D A C D B A C D B A C D B A A C B D A C B D A C B D A C B D C D A B C D A B C D A B C D A B C D B A C D B A C D B A A C B D C D A B C D A B C D B A C D B A A C B D C D B A 三种方案 三种方案 A 和和 D B 和和 D A 和和 C 习题习题 1 5 1 1 需证 PQPPQ 为永真式 PQPPQPQPPQ PP PQPQ T PQPQT PQPPQ 3 需证SRPP 为永真式 SRPP TSFSRFSRPP 4 3ABAB 为永真式 即 AB 永真 ABBABA 永真 AB 当且仅当 BA 4 设 P 珍宝藏在东厢房 Q 藏宝的房子靠近池塘 R 房子的前院栽有大柏树 S 珍宝藏在花园正中地下 t 后院栽有香樟树 m 珍宝藏在附近 后院 命题化后进行推理 QpRPQRStm pRPRStm RRStm Stm 即 S 为真 珍宝藏在花园正中地下 5 1 F P 0 Q 1 2 F P 1 Q R 0 3 F P 0 Q 1 习题习题 1 6 1 1 PQ RQPR 证 利用 CP 规则 P P 附加前提 PQP QT I RQP 5 RT I 结论成立 CP 规则 2 PQRSS V EBPB 证 PP 附加 P Q T PQRSP RST ST S E T S E B P BT PBCP 2 2 P 无任何痕迹 Q 失窃时 小花在 OK 厅 R 失窃时 小英在 OK 厅 S 失窃时 小胖在附近 T 金刚是偷窃者 M 瘦子是偷窃者 命题可符号化为 MRRSTQPSRQP 证 P P PS P 6 S T RS P R T RQ P Q T TQ P T T 金刚是窃贼 3 1 不相容 2 相容 0 1 SQRP 3 不相容 4 不相容 4 1 证 PQPQSSRQP PQPQSSRQP 即 PQPQSSRQP 利用消解原理 P P P QP P Q QP P P FPP 7 习题习题 2 12 1 1 1 xA x是实数 xB x是有理数 xAxBx xBxAx xBxAx 2 xA x是直线 yxF x与y平行 yxG x与y相交 baGbaFbAaAba 3 xA x是会员 xC x有意义 yxF x参加y a 这个活动 axFxAxaC 或者 aCaxFxAx 4 xA x是正整数 xB x是合数 xC x是质数 xCxBxAx 5 xA x是人 B x x 存钱 a 利息 P 存钱有利息 yxF x想有y xBxAPaxFxBxAx 2 1 210210QRRPPP 2 221100QPQPQP 4 1 zyxRztyQyxPyx 8 习题习题 2 22 2 1 1 D D 数 数 xyyxfxxA 0 1 11 xxfAxAyAxAyxfAyx 可满足式 2 xxA 是诚实的人 xxB 讲实话 a 小林 aBaAxBxAx 可满足式 3 xxA 不便宜 xxB 是好货 xyxF 买的y a 衣服 b 小王 aBaAbaFxBxAx 可满足式 4 xxA 是作家 xxB 懂得人性本质 xxC 是诗人 xxD 是真正的 xxE 能刻画人们内心世界 xxF 很高明 xyxP 创作了y a 莎士比亚 b 哈姆雷特 xDbxPxCxxExBxAx baPxDxExCxFxBxAx 2 1 T 3 1 F 2 T 4 0 yyQeyyxPD x 实数实数 习题习题 2 32 3 1 1 yQxPyx 9 yQxPyx yyQxPyx yyQxPx yyQxxP yQyxPAx 2 不成立 D 0 1 2 1 2 0 1 1 0 0 2 1 1 0 0 QQQPPP 3 1 yPyxPx yPyxPx yPyxPx yPyxPx yPxPyx skolem 范式 2 zyQzyxPx zyQzyxPx zyQzyxPx zyQxPzyx 前束范式 yxfyQxPyx skolem 范式 10 习题习题 2 42 4 1 1 证 在某个解释下 yQxPyx 取值 1 必有Dba bQaP 取值 1 因此 Da aP取值 1 xPx 取值 1 由定义 蕴含关系成立 2 aQxPxaQxPx aQxPx 2 证 在某个解释下 aQxPx 取值 1 即 aQxPx 取值 0 分二种情况 i 0 xPx 则无论 aQ为何值 aQxPx 取值 1 ii 10 xPxaQ 则 aQxPx 取值 1 由定义 蕴含关系成立 11 习题习题 2 52 5 1 2 反证法 xQxPx P xQxPx T E xQxPx T I xQxPx T I xQxP US xP T I xPx UG xQxxPx P xQx T I xQ T I 11 xQ US 12 T 11I 2 1 错误 应换元 即 xQxPx xQyP 2 正确 3 错误 a b 应是同一个常元 4 错误 因为在 xRxQxxP 中 x 并不是自由出现 5 错误 因为在 xQxPx 中 前件是命题 而后件不是命题 12 6 错误 因为 a b 并不是同一个常量 7 错误 和 的顺序不对 应先使用 ES 再使用 US 3 1 解 设 F x y x y G z z 0 f x y x y 前提 x y F x y G f x y x y F x y G f x y x y G f x y G f y x 结论 x y G f x y G f y x 证明 反证法 x y G f x y G f y x G f x y G f y x G f a b G f b a x y F x y G f x y F a b G f a b G f a b F a b x y G f x y G f y x G f b a G f a b x y F x y G f x y F a b G f a b G f a b F a b F a b F a b 13 4 2 证 首先 将结论否定否作为前提加入到原有前提中 xQxxPxxRxQxPxxPx xRxRyx vQvuPuxRxQxPxxPx yRwRyw xRxQxPxRxPywvux wRwRuRuP bQaPxRxQxPxRxPywx yRwR Skolem 范式 子句集为 yRwRbRaPxRxQxPxRxP xRxP aP xR 代换 a x cR 代换 c x yRwR yR 代换 c w cR 代换 c y 14 习题习题 3 43 4 3 习题习题 5 25 2 2 关系 性质 R1 R2 R3 R4 R5 自反性 反自反性 对称性 反对称性 传递性 习题习题 5 35 3 2 3 R 是对称的 设Ryx 则 Rxy 1 Ryx RxyRyxRxy 1 即RR 1 RyxRR 1 由 1 R的定义 1 Rxy Rxy 即 R 是对称的 5 R 是传递的 对 2 Rzx BAA A BABA A BABA xx xxxx xxx xxxx xxx 222 2BABA 22222 BA 2 BABA 2222 1 B B B 由于上述过程可逆 由于上述过程可逆 如 如 和和 和和 等号成立的条件为 等号成立的条件为 或或 或或 15 即RR 2 R R 2 对RzyRyx 由 R 2的定义 有RzxRRzx 2 即 R 是可传递的 4 解 解 21 RRR 且 21 RR 21 21 AAARRR mmm 21 5 2 3 1AA IRIR 需需 3 m3 m 5 m5 m 15 m 即 即 16 n RRRRRR 21 16 2 16 1 16 故使故使 nm RR 的最小正整数的最小正整数 16 1 nm 习题习题 5 45 4 2 2 解 解 0001 1000 0100 0010 0000 0000 0000 0000 0001 0000 0000 0000 0000 0001 0100 0010 R M 1111 1111 1111 1111 1000 1000 1000 1000 1111 0000 0000 0000 1000 0111 0111 0111 Rt M 3 3 证 2 1 1 2 1 1 i RURt i RURt ii i i RRURRt 21 1 21 由归纳法可证 对 i RR i R i RNi 21 21 RzxRzyRyxAy 16 21 21 2121 1111 21 RRtRRU i R i RU i RU i RURtRt i iiii 4 证 i i RURtRRR 1 j j RtURtR 1 由归纳法可证 RtRtNj j RRtRtURtUR j j j11 RtIRRRR A RtRIRRtIRRR AA RRtRtRR 习题习题 5 55 5 1 证 NbabaA bcaddcbaR 自反性 由 A 的定义 Nbabaab Rbaba 对称性 设 Rdcba 则bcad 即 Rbadcdacb 传递性 设 Rdcba 1111 则 1111 cbda Rdcdc 2211 则 2121 cddc 2121211211211 cbdacdbdcbdda Rdcba 2211 3 解 3 4 2 1 4 3 2 1 0 SA 17 设 3 4 3 2 1 21 AA 33442414422212412111 R 4 解 每个集合的划分就可以确定一个等价关系 集合有多少个划分就可以确定多少个等价关系 15 4 1 4 2 4 3 4 4 CCCC种 5 解 21UR R不是 A 上的等价关系 21 RR 是 A 上的等价关系 21 RRr 是 A 上的等价关系 21oR R不是 A 上的等价关系 习题习题 5 65 6 2 解 cbaA cbacbcabacba A 2 3 解 集合 A 上的空关系 恒等关系 IA都是等价关系和偏序关系 6 解 dcbaA 2 a a b b c c a b a b a c a c b c b c a b c a b c 18 dcbadcadcbdbacbadcdbcbdacabadcba A 2 dbacbadcdbcbdacabadcba dcbadcbdca 7 证 i 自反性 对 RbbABb R的自反性 显然 BBRbbBBbb ii 反对称性 对 BBRabBBRbaBba 即 RabRba 由 R 的反对称性 ba iii 传递性 对Bcba 设 BBRcbBBRba 则 Rba Rcb 由 R 的传递性 Rca 显然 BBca BBRca 19 习题习题 6 26 2 4 4 证 证 2121 bbBbb1 对 对 221121 Aaab f ab f af x 是满射 是满射 b ga b ga b ga b ga x g 12212211 且 且的定义 的定义 由由 12211221 b ga b ga b f a b f a 有 有否则 如否则 如 为单射为单射即即与函数的定义相矛盾 与函数的定义相矛盾 g x g b g b 21 不一定是满射不一定是满射 并不能保证并不能保证为单射时 对为单射时 对 而 而 x f b g Bb 2 xg 7 7 证 证 习题习题 6 4 6 4 3 3 证明 非空有限集 证明 非空有限集 A A 与可数集与可数集 B B 的笛卡尔积的笛卡尔积 A A B B 也是可数集 也是可数集 证明 设证明 设 A aA a1 1 a a2 2 a an n B bB b1 1 b b2 2 b bn n 令令 B Bi i a ai i b b1 1 a ai i b b2 2 a ai i b bn n i i n n 则则 为满射为满射即即 令令 对对 为满射为满射 为单射矛盾为单射矛盾与与 即即 反证法 设不是单射 反证法 设不是单射 g x g2 g g g g g 1 2211 2121 zygBy Byxf zxfgfg AxC z f f xf f x f x f x f x f xA xx CBgBAf 20 A A B B 因为因为 B B 为可数集 所以为可数集 所以 B Bi i为可数集 为可数集 A A B B 为有限个可数集的为有限个可数集的 并集 下面用归纳法证明有限个并集 下面用归纳法证明有限个 m m 个个 可数集的并集为可数集 可数集的并集为可数集 设设 C Cm m c cm1 m1 c cm2m2 c cmnmn 当当 m 2m 2 时 时 构造双射构造双射 f Nf N C C1 1 C C2 2 N N 1 2 3 4 5 6 1 2 3 4 5 6 n n 1 n 1 n f N cf N c11 11 c c2121 c c1212 c c2222 c c1313 c c2323 c c1 n 2 1 n 2 c c2 n 2 2 n 2 所以所以 2 2 个可数集的并集为可数集 个可数集的并集为可数集 假设假设 m km k 1 k1 k 3 3 时结论成立 即时结论成立 即 k k 1 1 个可数集的并集为可数集 记个可数集的并集为可数集 记 为为 D D 则则 m km k 时 可以构造类似的双射时 可以构造类似的双射 g Ng N D D C Ck k 所以为可数集 因而有所以为可数集 因而有 限个可数集的并集为可数集 所以限个可数集的并集为可数集 所以 A A B B 是可数是可数集 集 习题习题 9 19 1 1 1 设设 G G 是一个是一个 n m n m 简单图 证明 简单图 证明 m m 等号成立当且仅当等号成立当且仅当 G G 是完全图是完全图 证明 由欧拉定理 证明 由欧拉定理 2m 2m d k d k 表示第表示第 k k 个结点的度个结点的度 因为因为 G G 是简单图 所以是简单图 所以 d k d k n n 1 1 等号成立当且仅当等号成立当且仅当 G G 是完全图是完全图 2m 2m 所以所以 2m2m n nn n 1 1 即即 m m 1 k i i B 2 n C 1 n k d k 1 n k d k 1 1 n k n 1 2 n n 2 n C 21 3 3 解 解 1 1 不是图的序列 因为奇数度结点的 不是图的序列 因为奇数度结点的 个数不是偶数 个数不是偶数 2 2 3 3 4 4 都是图的序列 都是图的序列 4 4 证 证 9 9 若 称若 称 G G 是自补图 确定一个图为自补图的最是自补图 确定一个图为自补图的最低条件 画出一个低条件 画出一个 自补图来 自补图来 解 设解 设 G n m G n m G n m G n m 则则 m m n nm m n n 1 2 1 2 所以所以 m m n nm m n n 1 41 4 习题习题 9 29 2 1 1 若若 u u 和和 v v 是图中仅有的两个奇度数结点 证明是图中仅有的两个奇度数结点 证明 u u 和和 v v 必是连通的 必是连通的 证 反证法 设证 反证法 设 v v 与与 u u 不连通不连通 v v2 2 v v1 1 v v3 3 v v4 4 G G v v2 2 v v1 1 v v3 3 v v4 4 n 2m n2mn 2 G GGG G v vvv v d v d v d v m 由欧拉定理 由欧拉定理 22 G V1G V1 V2 V2 v v 与与 u u 分别属于分别属于 V1V1 V2V2 二个子图二个子图 v v 与与 u u 是是 G G 中仅有的二个奇数度结点中仅有的二个奇数度结点 v v 与与 u u 即是即是 V1V1 与与 V2V2 中仅有的一个奇数度结点 与中仅有的一个奇数度结点 与欧拉定理的欧拉定理的 推论推论 9 9 1 1 11 1 1 相矛盾相矛盾 故故 v v 与与 u u 必连通必连通 3 3 设设 n m n m 简单图简单图 G G 满足满足 m m n n 1 n1 n 2 22 2 证明 证明 G G 必是连通图 构必是连通图 构 造一个造一个 m nm n 1 n1 n 2 22 2 的非连通简单图 的非连通简单图 书上证明更好 书上证明更好 5 5 设设 G VG V E E 是点度均为偶数的连通图 证明 对任何是点度均为偶数的连通图 证明 对任何 v v V V G G v v d v 2d v 2 证 反证法 设结论不成立 即存在证 反证法 设结论不成立 即存在 v v V V G G v v d v 2 d v 2 因为因为 G G 是连通的 所以是连通的 所以 G G v v 的每个分支都至少有一个点与的每个分支都至少有一个点与 v v 相邻接 相邻接 而且存在一个分支 其与而且存在一个分支 其与 v v 相邻接的点只有一条边与相邻接的点只有一条边与 v v 相连 因为如相连 因为如 每个分支中有二个以上的点与每个分支中有二个以上的点与 v v 相连 则相连 则 出现矛盾 出现矛盾 存在一个分支 其中只有一条边与 存在一个分支 其中只有一条边与 v v 相连 因为相连 因为 G G 中每个结点的度中每个结点的度 数为偶数 所以在这个分支中就会出现一个奇度数结点 其余结点的数为偶数 所以在这个分支中就会出现一个奇度数结点 其余结点的 度数全为偶数 与欧拉定理的推论相矛盾 故度数全为偶数 与欧拉定理的推论相矛盾 故故对任何故对任何 v v V V G G v v d v 2d v 2 9 9 证明 恰有两个非割点的简单连通图必是证明 恰有两个非割点的简单连通图必是 Pn nPn n 2 2 证明 归纳法 证明 归纳法 n 2n 2 时 结论显然成立 时 结论显然成立 设设 n kn k 时结论成立 时结论成立 2 1 vdG vVv 23 当当 n k 1n k 1 时 设时 设 v v1 1 v vk k是是 P Pk k上的两个非割点 上的两个非割点 v vk 1 k 1是在是在 P Pk k上增上增 加的一个割点 如果结点加的一个割点 如果结点 v vk 1 k 1不在不在 P Pk k上的任意两个结点之间 则必与上的任意两个结点之间 则必与 P Pk k上某两个结点构成一个回路 上某两个结点构成一个回路 v vk 1 k 1就就不是割点 与只有两个非割点不是割点 与只有两个非割点 矛盾 故结论成立 矛盾 故结论成立 习题习题 9 39 3 3 3 解 解 v1e2 v7 v6 v5 v4 v3 v2 e8 e7 e6 e5 e4 e3 e1 e12 e11 e10 e9 0 1 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 7654321 vvvvvvv A 1 1 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 1 1 1 1 1 0 0 1 1 1 1 1 0 0 1 1 1 1 1 7654321 vvvvvvv P 1 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 0 0 1 1 1 1 7654321 vvvvvvv PP T 24 三个强分图三个强分图 5 5 证明 支数为证明 支数为 k k 阶数为 阶数为 n n 的无环图的无环图 G G 其关联矩阵的秩是 其关联矩阵的秩是 n n k k 证明 将各支结点和边集中编号后 证明 将各支结点和边集中编号后 G G 的关联矩阵的关联矩阵 由分块矩阵子公式及定理由分块矩阵子公式及定理 9 9 3 23 2 M M M M1 1 M M2 2 M Mk k n n1 1 1 n1 n2 2 1 n1 nk k 1 1 n n k k 76 5 4321 vvG vG vvvvG 1 1 1 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 0 0 0 0 0 0 0 1 1 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 121110987654321 eeeeeeeeeeee MG 1 2 000 000 00 000 k M M M M 25 习习题题 10 110 1 1 1 设一个树中度为设一个树中度为 k k 的结点数是的结点数是 nknk 求它的叶的数目 求它的叶的数目 解 设解 设 L L 是叶的数目 是叶的数目 m m 是树的边数是树的边数 由由 EulerEuler 定理定理 由树的定义由树的定义 习题习题 10 210 2 6 6 证明正则二叉树必有奇数个结点 证明正则二叉树必有奇数个结点 证明 由正则二叉树的定义 其叶结点的个数必为偶数 设叶数证明 由正则二叉树的定义 其叶结点的个数必为偶数 设叶数 为为 t t 分支数为 分支数为 i i 由定理由定理 1010 2 12 1 m m 1 i t1 i t 1 1 m 1 m 1 i ti t 1 1 有分支点数是奇数有分支点数是奇数 故结点数故结点数 i t i t 奇数奇数 习题习题 10 410 4 3 3 证 反证法 证 反证法 设设 G G n n m m 和 和 G G n n m m 都是平面图 都是平面图 mLkn i k k 2 2 1 2 Lnm i k k 2 2 2 222 2 22 kinkL LnLkn i k k i k k i k k 26 由由 G G 的定义的定义 m mm m n n n n 1 2 1 2 由定理由定理 1010 4 2 m4 2 m 3n3n 6 m6 m 3n3n 6 6 m mm m n n n n 1 2 1 2 6n6n 1212 有有 n2n2 13n 24 n13n 24 n 11 2 9n11 2 9n 97 97 0 0 又 又 n n 11 2 11 2 0 0 n n 1111 时时 9n 9n 97 97 2 2 n n 11 2 9n11 2 9n 97 97 2 2 与上式相矛盾 与上式相矛盾 故故 G G 与与 G G 至少有一个是非平面图至少有一个是非平面图 4 4 证明 具有证明 具有 6 6 个结点 个结点 1212 条边的简单连通平面图 它的面度都是条边的简单连通平面图 它的面度都是 3 3 证 由证 由 EulerEuler 公式 公式 n n m f 2m f 2 6 6 12 f 2 f 812 f 2 f 8 即面数为即面数为 8 8 对每个面 其度数 对每个面 其度数 3 3 总面度 总面度 3 3 8 248 24 总面度 总面度 2 2 m 24m 24 每个面的度数为 每个面的度数为 3 3 5 5 少于少于 3030 条边的简单平面图至少有一个顶点的度不大于条边的简单平面图至少有一个顶点的度不大于 4 4 证 反证法 设所有顶点的度数证 反证法 设所有顶点的度数 5 5 由由 EulerEuler 公式 公式 由定理由定理 1010 4 2 m4 2 m 3n3n 6 6 3n3n 6 6 5n 2 5n 2 即即 n n 1212 则则 m m 5n 25n 2 5 5 12 2 30 12 2 30 与与 m m 3030 矛盾矛盾 因此 因此 至少存在一个顶点的度数不超过至少存在一个顶点的度数不超过 4 4 27 习题习题 10 610 6 2 证明 证明 4k 14k 1 阶的所有阶的所有 2k2k 正则简单图都是哈密顿图 正则简单图都是哈密顿图 证 证 G G 是是 2k2k 正则图 正则图 对任意的对任意的 u u v v G G d u d v 4kd u d v 4k 由定理由定理 1010 6 6 2 2 在在 G G 中存在一条中存在一条 HamiltonHamilton 道路 设为 道路 设为 v v1 1v v2 2 v v4k 1 4k 1 1 1 v v1 1v v4k 1 4k 1 E E 则则v v1 1v v2 2 v v4k 14k 1v v1 1构成一个构成一个 HamiltonHamilton 圈圈 2 2 v v1 1v v4k 1 4k 1 E E 则则 邻接邻接与与 1 221 vvvv k iii G G 的阶数为的阶数为 4k 14k 1 中的一个点邻接 中的一个点邻接 必与必与 11114 221 k iiik vvvv 否则 否则 d d v v4k 1 4k 1 4k 4k 1 1 2k 2k2k 2k 1 1 与与 d d v v4k 14k 1 2k 2k 矛盾矛盾 设设 Evv kit 14 可构造 可构造 141411 vvvvvv tt ikki 即为即为 G G 的一个的一个 HamiltonHamilton 圈 故圈 故 G G 是一个是一个 HamiltonHamilton 图图 5 5 设设 G G 是是 n m n m 简单图 若简单图 若 证明证明 G G 必是哈必是哈 密顿图 密顿图 证 反证法 假设证 反证法 假设 G G 不是哈密尔顿图 则不是哈密尔顿图 则 nvm tsvvm ntsGts tsGv tsGvGv deg 2 deg deg deg deg 2 deg deg 因为因为 G G 除结点除结点 s ts t 外的其余外的其余 n n 2 2 结点之间最多可以构成完全结点之间最多可以构成完全 图 所以图 所以 2m n2m n 2 n2 n 3 n n n23 n n n2 3n 3n 6 n6 n 1 n1 n 2 42 4 从而从而 22 2 1 2 1 2 1 n Cnnm 2 2 1 n Cm 28 与已知与已知 矛盾 故结论成立 矛盾 故结论成立 习题习题 11 111 1 4 4 设设 S 是一个含有幺元是一个含有幺元 e e 的代数系统 的代数系统 a a S S 如果存在元如果存在元 b cb c S S 使使 b b a e a e 或或 a a c e c e 则称则称 b b 是是 a a 的左逆元的左逆元 或或 c c 是是 a a 的右逆元的右逆元 证 证 明 如果一个元既有左逆元明 如果一个元既有左逆元 b b 又有右逆元又有右逆元 c c 则必 则必 b c b c 证明 证明 S S 上的运算 是可结合的 上的运算 是可结合的 b bb b e b e b a a c b c b a a c e c e c cc c 习题习题 11 211 2 4 设半群设半群 A 中任何两个不同元素关于运算 不可交换 证明 中任何两个不同元素关于运算 不可交换 证明 对任何对任何 a a A aA a a aa a 证明 反证法 证明 反证法 设设 a a A A 使得使得 a a a a a a 构造构造 b a b a a a 则 则 a a b a b a a a a b a b a a 即即 a a b b 可交换 与已知条件相矛盾可交换 与已知条件相矛盾 a a A aA a a aa a 5 5 设设 S 00 111 1010 S 00 111 1010 是字符集是字符集 0 1 0 1 上的字集合 试构造上的字集合 试构造 的一 的一 个包含集合个包含集合 S S 的最小的含幺子半群 的最小的含幺子半群 解 令空字符为解 令空字符为 m n k m n k 为正整数 为正整数 T T 00 m 111 n 1010 k 00 m 111 n 1010 k 00 m 1010 k 111 n 111 n 00 m 1010 k 2 2 1 n Cm 29 111 n 1010 k 00 m 1010 k 00 m 111 n 1010 k 111 n 00 m 习题习题 11 311 3 1 证明 群中只有幺元是幂等元 证 反证法 设 aaeaAa 2 eaaaaaa 1121 5 写出 3 s 中的全部子群 解 1 1 2 1 1 3 1 2 3 1 1 2 3 1 3 2 和二个平凡子群 6 设设 S 和和 T 都是都是 G 的子群 令的子群 令 S S T x xT x x S S S S T ST sT ST s t st s S S t t T T 证明 证明 S 和和 ST 也都也都 是是 G 的子群 的子群 证明 1 S T 是 G 的子群 e S e T 即 e S T 设 a b S T 即 a b S 和 a b T 111 101 0 矛盾 30 b 1 S 和 b 1 T a b 1 S 和 a b 1 T 即 a b 1 S T S T 是 G 的子群 2 e ST 设 c d ST 则 a1 S b1 T c a1b1 a2 S b2 T d a2b2 d 1 b2 1a2 1 又 S 和 T 中的元素关于 可交换 c d 1 a1b1b2 1a2 1 a1a2 1b1b2 1 ST 即 ST 是子群 习题习题 11 11 4 4 1 1 阶数小于阶数小于 6 6 的群必是交换群 的群必是交换群 证明 证明 1 1 阶群阶群 是平凡的是平凡的 显然是交换群显然是交换群 2 32 3 和和 5 5 都是素数都是素数 由拉格朗日定理的推论由拉格朗日定理的推论 2 2 可知可知