离散课后作业答案.pdf

第一章第一章 命题逻辑命题逻辑 1 第 7 页第 3 题 1 解 逆命题 如果我去公园 则天不下雨 反命题 如果天下雨 则我不去公园 逆反命题 如果我不去公园 则天下雨了 2 解 此题注意 P 仅当 Q 翻译成PQ 逆命题 如果你去 那么我逗留 反命题 如果我不逗留 那么你没去 逆反命题 如果你没去 那么我不逗留 3 解 逆命题 如果方程 nnn xyz 无整数解 那么 n 是大于 2 的正整数 反命题 如果 n 不是大于 2 的正整数 那么方程 nnn xyz 有整数解 逆反命题 如果方程 nnn xyz 有整数解 那么 n 不是大于 2 的正整数 4 解 逆命题 如果我不完成任务 那么我不获得更多的帮助 反命题 如果我获得了更多的帮助 那么我能完成任务 逆反命题 如果我能完成任务 那么我获得了更多的帮助 2 第 15 页第 1 题 4 解 PQPT PQPQ PQPQ 重言式 9 解 PPQFQT 重言式 10 解 PQQTQQ 可满足式 3 第 16 页第 5 题 2 证明 PQP PQP PQP PQP PPQ FQ F 因此 PQPF 得证 4 证明 PPPP PPPP PP F 因此 PPPPF 得证 4 第 16 页第 6 题 1 PQPQ 证明 设PQ 为真 那么 P 为真 并且 Q 为真 因此PQ 为真 所以PQPQ 2 PQRPQPR 证明 设 PQPR 为假 于是PQ 为真 PR 为假 得 P 为真 Q 为真 R 为 假 于 是 得QR 为 假 由 P 为 真 可 得 PQR 为 假 因 此 PQRPQPR 得证 5 PPQPPRQR 证明 PPQPPR TQTR QR 因此 PPQPPRQR 得证 5 补充 试证明 QACAPCAPQC 证明 QACAPC QACAPC ACQACP ACPQ APQC APQC APQC APQC ACPQ 因此 QACAPCAPQC 得证 6 第 21 页第 1 题 2 解 PQPQPQ 0 PPQPQ QPQ PQQQ PQ 7 第 21 页第 2 题 只求主析取范式 4 解 PQSPQR 5 7 10 11 PQSRPQSRPQSRPQSR 8 第 25 页第 3 题 证明 1 B P 规则 2 BAC P 规则 3 AC T 规则 1 2 4 ABC P 规则 5 AC T 规则 1 4 6 ACAC T 规则 5 7 AC T 规则 3 8 AC T 规则 6 7 9 AC T 规则 8 因此 AC 是题目的有效结论 AC 不是 9 第 26 页第 7 题 a PQQRRP 证明 1 R P 规则 2 QR P 规则 3 Q T 规则 1 2 4 PQ P 规则 5 PQ T 规则 4 6 P T 规则 3 5 b PQRRS SPQ 证明 1 S P 规则 2 RS P 规则 3 R T 规则 1 2 4 PQR P 规则 5 PQ T 规则 3 4 6 PQ T 规则 5 c PQR RS QTP 证明 题目有问题 10 第 26 页第 8 题 a PQQR RSPS 证明 1 P P 规则 假设前提 2 PQ P 规则 3 Q T 规则 1 2 4 QR P 规则 5 R T 规则 3 4 6 RS P 规则 7 S T 规则 5 6 8 PS CP 规则 1 7 b PQPPQ 证明 1 P P 规则 假设前提 2 PQ P 规则 3 Q T 规则 1 2 4 PQ T 规则 1 3 5 PPQ CP 规则 1 4 c PQRPQR 证明 1 PQ P 规则 假设前提 2 P T 规则 1 3 Q T 规则 1 4 PQ T 规则 2 3 5 PQR P 规则 6 R T 规则 4 5 7 PQR CP 规则 1 6 11 第 26 页第 9 题 a RQ RS SQ PQP 证明 1 P P 规则 假设前提 2 P T 规则 1 3 PQ P 规则 4 Q T 规则 2 3 5 SQ P 规则 6 S T 规则 4 5 7 RS P 规则 8 R T 规则 6 7 9 RQ P 规则 10 Q T 规则 8 9 11 QQ T 规则 4 10 12 P F 规则 1 11 b SQ RSR PQP 证明 1 P P 规则 假设前提 2 P T 规则 1 3 PQ P 规则 4 Q T 规则 2 3 5 SQ P 规则 6 S T 规则 4 5 7 RS P 规则 8 R T 规则 6 7 9 R P 规则 10 RR T 规则 8 9 11 P F 规则 1 10 c PQRSQPR RPQ 证明 1 R P 规则 2 QPR P 规则 3 QP T 规则 1 2 4 RS T 规则 1 5 PQRS P 规则 6 PQ T 规则 4 5 7 PQ T 规则 6 8 PQQP T 规则 3 7 9 PQ T 规则 8 第二章第二章 谓词逻辑谓词逻辑 1 第 39 页第 1 题 b x A xx B xx A xB x 证明 x A xx B x x A xx B x xA xx B x xA xB x x A xB x 还可以用推理的方法证明 证明 1 xA xB x P 假设前提 2 xA xB x T 3 xA xB x T 4 x A xxB x T 5 x A x T 6 xB x T 7 x A xx B x P 8 x B x T 5 7 9 B a ES 6 10 B a US 8 11 B aB a T 9 10 12 xA xB x F 1 11 d x A xB xx B xC xx C xx A x 证明 1 x C x P 2 C x US 1 3 xB xC x P 4 B xC x US 3 5 B x T 2 4 6 xA xB x P 7 A xB x US 6 8 A x T 5 7 9 x A x UG 8 2 第 39 页 2 a x P xQ xx P xx Q x 证明 1 x P x P 假设前提 2 P x US 1 3 xP xQ x P 4 P xQ x US 3 5 Q x T 2 4 6 x Q x UG 5 7 x P xx Q x CP 1 6 b x P xQ xx P xx Q x 证明 由于 x P xx Q xxQ xx P x xQ xx P x 因此 原题等价于证明 x P xQ xxQ xx P x 1 xQ x P 假设前提 2 Q x US 1 3 xP xQ x P 4 P xQ x US 3 5 P x T 2 4 6 x P x UG 5 7 xQ xx P x CP 1 6 3 第 39 页第 3 题 a 所有的有理数是实数 某些有理数是整数 因此某些实数是整数 解 首先定义如下谓词 P xx是有理数 R xx是实数 I xx是整数 于是问题符号化为 x P xR xx P xI xx R xI x 推理如下 1 xP xI x P 2 P aI a ES 1 3 xP xR x P 4 P aR a US 3 5 P a T 2 6 I a T 2 7 R a T 4 5 8 R aI a T 6 7 9 xR xI x EG 8 b 任何人如果他喜欢步行 他就不喜欢乘汽车 每一个人或者喜欢乘汽车或者喜欢骑自 行车 有的人不爱骑自行车 因而有的人不爱步行 解 首先定义如下谓词 P xx是人 F xx喜欢步行 C xx喜欢乘汽车 B xx 喜欢骑自行车 于是问题符号化为 x P xF xC xx P xC xB x x P xB xx P xF x 推理如下 1 xP xB x P 2 P aB a ES 1 3 P a T 2 4 B a T 2 5 xP xC xB x P 6 P aC aB a US 5 7 C aB a T 3 6 8 C a T 4 7 9 xP xF xC x P 10 P aF aC a US 9 11 P aF a T 8 10 12 P aF a T 11 13 F a T 3 12 14 P aF a T 3 13 15 xP xF x EG 14 c 每个科学工作者都是刻苦钻研的 每个刻苦钻研而且聪明的科学工作者在他的事业中 都将获得成功 华为是科学工作者并且他是聪明的 所以 华为在他的事业中将获得成功 解 首先定义如下谓词 P xx是科学工作者 Q xx是刻苦钻研的 R xx是聪明的 S xx在他的事业中将获得成功 定义个体 a 华为 于是命题符号化为 x P xQ xx P xQ xR xS x P aR aS a 推理如下 1 xP xQ x P 2 P aQ a US 1 3 P aR a P 4 P a T 3 5 R a T 3 6 Q a T 2 4 7 xP xQ xR xS x P 8 P aQ aR aS a US 7 9 P aQ aR a T 3 6 10 S a T 8 9 d 每位资深名士或是中科院院士或是国务院参事 所有的资深名士都是政协委员 张伟 是资深名士 但他不是中科院院士 因此 有的政协委员是国务院参事 解 首先定义如下谓词 P xx是资深名士 Q xx是中科院院士 R xx是国务院参事 S xx是政协委员 定义个体 a 张伟 于是命题符号化为 x P xQ xR xx P xS x P aQ ax S xR x 推理如下 1 P aQ a P 2 P a T 1 3 Q a T 1 4 xP xS x P 5 P aS a US 4 6 S a T 2 5 7 xP xQ xR x P 8 P aQ aR a US 7 9 Q aR a T 2 8 10 R a T 3 9 11 S aR a T 6 10 12 xS xR x EG 11 e 每一个自然数不是奇数就是偶数 自然数是偶数当且仅当它能被 2 整除 并不是所有 的自然数都能被 2 所整除 因此 有的自然数是奇数 解 首先定义如下谓词 N xx是自然数 Q xx是奇数 O xx是偶数 P xx能被 2 整除 于是命题符号化为 x N xQ xO xx N xO xP x x N xP xx N xQ x 推理如下 1 x N xP x P 2 xN xP x T 1 3 N aP a ES 2 4 N a T 3 5 P a T 3 6 xN xO xP x P 7 N aO aP a US 6 8 O aP a T 4 7 9 O a T 5 8 10 xN xQ xO x P 11 N aQ aO a US 10 12 Q aO a T 4 11 13 Q a T 9 12 14 N aQ a T 4 13 15 xN xQ x EG 14 f 如果一个人怕困难 那麽他就不会获得成功 每个人或者获得成功或者失败过 有些 人未曾失败过 所以 有些人不怕困难 解 首先定义如下谓词 P xx是人 Q xx怕困难 R xx曾获得成功 S xx曾获得失败 于是命题符号化为 x P xQ xR xx P xR xS x x P xS xx P xQ x 推理如下 1 xP xS x P 2 P aS a ES 1 3 P a T 2 4 S a T 2 5 xP xR xS x P 6 P aR aS a US 5 7 R aS a T 3 6 8 R a T 4 7 9 xP xQ xR x P 10 P aQ aR a US 9 11 P aQ a T 8 10 12 P aQ a T 11 13 Q a T 3 12 14 P aQ a T 3 13 15 xP xQ x EG 14 4 第 40 页第 5 题 解 错误 第 2 行的 y 是泛指 第 4 行的 y 是特制 更改如下 1 x P x P 2 P y ES 1 3 x P xQ x P 4 P yQ y US 3 5 Q y T 2 4 6 x Q x EG 5 5 第 40 页第 6 题 a x P xxP xQ xR x x P xx Q xxy R xR y 证明 1 2 1 3 4 3 5 6 1 5 7 6 8 2 9 7 8 10 x P xP P aES x Q xP Q bES x P xxP xQ xR xP xP xQ xR xT P aQ aR aUS P aQ aT R aT P bQ bR bUS 6 11 4 12 10 11 13 9 12 14 13 15 14 P bQ bT R bT R aR bT y R aR yEG xy R xR yEG b x P xx Q xx P xQ x 证明 1 x P xx Q x P 2 x P xx Q x T 1 3 xP xx Q x T 2 4 xP xQ x T 3 5 xP xQ x T 4 6 第 42 页第 1 题 a x P xy Q y 解 x P xy Q y xP xy Q y xyP xQ y b xyz P x yP y zu Q x y u 解 xyz P x yP y zu Q x y u xyz P x yP y zu Q x y u xyzP x yP y zu Q x y u xyzuP x yP y zQ x y u c xy A x yxy B x yy A y xB x y 解 xy A x yxy B x yy A y xB x y xy A x yxy B x yy A y xB x y xy A x yxy B x yyA y xB x y xy A x yuv B u vzA z u B u z xyuvzA x yB u vA z uB u z 7 第 42 页第 2 题 b x P xyz Q x zz R x y 解 前束析取范式 x P xyz Q x zy R x y xP xyz Q x zy R x y xP xyz Q x zy R x y xP xyz Q x zu R x u xP xyzQ x zuR x u xyzuP xQ x zR x u xyzuP xQ x zR x u 由于 P xQ x zR x u 是基本和 因此前束合取范式与前束析取范式一样 x P xyz Q x zz R x y xyzuP xQ x zR x u d x P xQ x yy P yz Q y z 解 前束析取范式 x P xQ x yy P yz Q y z x P xQ x yy P yz Q y z xP xQ x yy P yz Q y z x P xQ x yy P yz Q y z x P xQ x uy P yz Q u z xyzP xQ x uP yQ u z 前束合取范式 x P xQ x yy P yz Q y z xyzP xQ x uP yQ u z xyzP xP yQ u zQ x uP yQ u z xyzP xP yP xQ u zQ x uP yQ x u Q u z 第三章第三章 集合论集合论 1 第 46 页第 3 题 给出集合A B和C的例子 使得AB BC 而AC 解 Aa Ba b Ca b c 2 第 46 页第 6 题 2 1 2 3 解 设 1 2 3 A 则 1 2 3 A 5 解 3 第 46 页第 9 题 1 解 子集个数 101 2 2 解 元素的奇数的子集个数为 101 100 2 2 2 3 解 不会有 102 个元素的子集 4 第 46 页第 10 题 解 把 17 化为二进制 是 00010001 1748 Ba a 把 31 化为二进制 是 00011111 3145678 Ba a a a a 267 a a a 编码为 01000110 为 70 B 18 a a 编码为 10000001 为 129 B 5 第 53 页第 5 题 1 ABCABC 证明 ABC ABC ABC ABC ABC ABC 上面是一种简单的方法 还可以利用文字叙述 任取 x 属于 ABC 证明 还有一种方法 就是利用第五章的特征函数证明 下面给出过程 1 1 1 A BC A BA BC AABAABC AABC ABC 1 1 1 AB C AAB C AABCBC ABCBC ABC 所以 A BCAB C 从而可得 ABCABC 2 ABCA CB 证明 ABC ABC ABC ACB ACB ACB 3 ABCA CBC 证明 ACBC ACBC ACBC ACBC ACBACC ABC ABC ABC 因此 ABCA CBC 6 第 53 页第 9 题 1 ABA CA 解 由于 ABA CA 因此必有ABA 且A CA 也就是AB 并且AC 2 ABA C 解 由于 ABA C 因此必有AB 且A C 也就是AB 并且 AC 3 ABA C 解 ABAC ABAC ABC ABC 因此 ABA C 意味着 ABC 4 ABA C 解 ABAC ABAC ABACACAB ABACACAB ABCABC ABC 两种可能 第一种BC 即 B C 第二种 ABC 或者 ABC 因此 此题答案为 BCABCABC 或者或者 7 第 53 页第 11 题 1 ABCABAC 证明 ABAC ABACACAB ABACACAB ABAABCACAACB ABCACB ABCCB ABC 因此 ABCABAC 2 ABCABAC 注意 这个题目本身不正确 举例如下 全集为 1 2 3 A 1 B 2 C 3 则 1 2 3 ABC 2 3 ABAC 不相等 8 第 57 页第 3 题 解 设 A B C 分别表示骑木马 坐滑行轨道和乘宇宙飞船的儿童集合 由公园的总收入知 70 0 5 140ABC 20ABC 55ABCABCABCABC 因此 3 552 5540 95 ABACBC ABCABCABCABC ABC 没有坐过任何一种的儿童总数为 75 75 75 1409520 10 ABC ABC ABCABACBCABC 答 一共 10 个儿童没有坐过其中任何一种游乐设备 9 第 57 页第 5 题 解 设 A B C 分别是学习数学 物理 生物的大一学生集合 由题意可知 67 47 95 28 26 27 50 ABC ABACBC ABC 200 200 200 674795262728 50 ABC ABC ABCABACBCABC ABC 解方程 得 22ABC 因此 一共有 22 人三门功课都学 数学 物理 生物 E 22 4 6 5 35 14 64 50 10 第 59 页第 1 题 1 1 AB 解 1 AB 2 2 AB 解 2 0 0 1 0 1 1 1 0 1 1 1 1 0 0 2 0 1 2 1 0 2 1 1 2 AB 3 2 BA 解 1 0 1 1 2 0 2 1 BA 2 1 0 1 0 1 0 1 1 1 0 2 0 1 0 2 1 1 1 1 0 1 1 1 1 1 1 2 0 1 1 2 1 2 0 1 0 2 0 1 1 2 0 2 0 2 0 2 1 2 1 1 0 2 1 1 BA 1 2 1 2 0 2 1 2 1 11 第 60 页第 2 题 解 XY 表示在在笛卡尔坐标系中 32x 且20y 的矩形区域内的点集 12 第 60 页第 3 题 1 ABCDA CB D 证明 任取 x yABCD 有 x yABCD xAByCD xAxByCyD xAyCxByD x yA Cx yBD x yA CBD 由 x y 取值的任意性知 ABCDA CB D 2 当且仅当才 才有 ABCABC 证明 当CA 时 ACA 于是 ABCACBCABC 当 ABCABC 时 任取xC 可知 xABC 由 ABCABC 知 xABC 于是得到xA 所以 CA 13 第 60 页第 5 题 这种题目也可以不推理 只要举出反例即可 1 ABCDA CB D 解 任取 x yABCD 有 x yABCD xAByCD xAxByCyD xAyCyDxByCyD xAyCxAyDxByCxByD x yA CADBCBD 选择 A 1 B 2 C a D b 则 1 1 2 2 ABCDabab 1 2 A CB Dab 因此该等式不成立 2 ABCDA CB D 解 任取 x yABCD 有 x yABCD x yABCD xAByCD xAxByCyD xAyCxByD xAyCxByD xAyCxByD 选择 A 1 2 B 1 C a b D a 2 ABCDb 1 2 2 A CB Dbab 因此 该等式不成立 3 ABCDA CB D 解 设 A 1 2 B 2 C 3 4 D 4 则 1 3 ABCD 1 3 1 4 2 3 A CB D 因此 该等式不成立 4 ABCA CB C 解 取 x yABC 有 x yABC x yABC xAByC xAxByC xAyCxByC xAyCxByC x yA Cx yBC x yA CBC 因此 该等式成立 5 ABCA CB C 解 任取取 x yA CB C 有 x yA CBC xAyCxByCxByCxAyC xAyCxByCxByCxAyC xAyCxBxAxByC xAxBxAxByC xABAByC xAByC x y ABC 因此 该等式成立 第四章第四章 二元关系二元关系 1 第 63 页第 2 题 解 12 1 2 2 4 3 3 1 3 4 2 RR 12 2 4 RR 1 1 2 3 D R 2 1 2 4 D R 1 2 3 4 R R 2 2 3 4 R R 12 1 2 3 4 D RR 12 4 R RR 2 第 63 页第 3 题 解 1 1 1 2 1 3 1 6 2 2 2 3 2 6 3 3 3 6 6 6 L 1 1 1 2 1 3 1 6 2 2 2 6 3 3 3 6 6 6 D 1 1 1 2 1 3 1 6 2 2 2 6 3 3 3 6 6 6 LD 3 第 63 页第 4 题 证明 设 D R A D S B 1 任取xAB 则分为两种情况 xA 或xB 当xA 时 由 R 是自反的 知 x xR 于是 x xRS 当xB 时 由 S 是自反的 知 x xS 于是 x xRS 因此不管任何情况 x xAB x xRS RS是自反的 2 任取xAB 则xA 且xB 由 R 和 S 都是自反的 知 x xR 并且 x xS 于是 x xRS 因此RS是自反的 4 第 63 页第 5 题 证明 设 D R A D S B 1 任取xAB 则xA 且xB 由 R 和 S 都是自反的 知 x xR 并且 x xS 于是 x xRS 因此RS是自反的 2 任取 x yRS 则 x yR 并且 x yS 由 R 和 S 是对称的 知 y xR 并且 y xS 于是 y xRS 因此 RS是对称的 3 任取 x yRS y zRS 可得 x yR y zR 并 且 x yS y zS 由 R 是可传递的 知 x zR 由 S 是可传递的 知 x zS 于是 x zRS 因此 RS是可传递的 5 第 63 页第 7 题 解 任取xS 除 5 外 x xR 但5 5R 因此 R 是不自反的 若 x yR 即10 xy 可得10 yxy xR 知 R 是对称的 3 7R 7 3R 但3 3R 可得 R 是不可传递的 综上 R 是不自反的 对称的 不可传递的 6 第 63 页第 8 题 解 1 R 是集合 A 上的二元关系 A 为空集 2 R 是集合 A 上的二元关系 1 2 A 1 1 R 3 R 是集合 A 上的二元关系 A 为空集 4 R 是集合 A 上的二元关系 1 2 3 A 1 1 1 2 2 1R 1 3 7 第 69 页第 1 题 解 0 3 21 123 0 1 2101 3 0010 R M 0 1001 0000 1 8 第 69 页第 2 题 解 设 1 2 3 X X 中的二元关系有 2 3 2512 个 9 第 69 页第 3 题 证明 集合 X 中的每个二元关系都是XX 的子集 X有n个元素 XX 有 2 n个元素 XX 有 2 2n个元素 每一个元素都是XX 的一个子集 也是一种二元关系 因而 在X中有 2 2n个不同的二元关系 10 第 69 页第 4 题 仅说明关系的性质 a 自反的 不对称的 不可传递的 b 不自反的 反对称的 不可传递的 c 自反的 对称的 可传递的 d 自反的 不对称的 不可传递的 e 不自反的 不对称的 不可传递的 f 不自反的 对称的 不可传递的 g 自反的 反对称的 可传递的 h 自反的 不对称的 不可传递的 i 不自反的 对称的 可传递的 j 自反的 反对称的 不可传递的 k 自反的 反对称的 可传递的 l 不自反的 反对称的 可传递的 11 第 70 页第 5 题 解 1 0 1 1 2 2 3 0 0 2 1 R 2 2 0 3 1 R 1 12 1 0 2 1 RR 2 21 2 0 2 1 3 2 RR 3 121 1 0 1 1 2 2 RRR 4 3 1 0 0 0 1 0 2 0 3 1 2 2 1 2 3 R 5 3 2 R 12 第 70 页第 6 题 1 证明 任取xX 由于 1 R和 2 R是自反的 因此 1 x xR 2 x xR 可得 12 x xRR 由 x 取值的任意性可知 12 RR是自反的 2 设 12 1 2 3 1 3 3 1 XRR 则 12 1 1 RR 不是反自 反的 3 设 12 1 2 3 1 2 2 1 3 2 2 3 XRR 则 12 1 3 RR 不是对称的 4 设 12 1 2 3 1 2 3 1 1 1 2 3 XRR 则 12 1 3 3 1 RR 不是反对称的 5 设 12 1 2 3 4 5 1 2 2 3 1 3 5 4 2 3 XRR 3 5 2 5 4 4 则 12 1 3 1 5 2 5 5 4 RR 不可传递 13 第 70 页第 7 题 证明 1 任取 13 x zRR 则一定存在某一个yX 使得 1 x yR 3 y zR 由 12 RR 知 13 23 23 yx yRy zR yx yRy zR x zRR 根据 x z 取值的任意性 问题得证 1323 RRRR 2 任取 31 x zRR 则一定存在某一个yX 使得 3 x yR 1 y zR 由 12 RR 知 31 32 32 yx yRy zR yx yRy zR x zRR 根据 x z 取值的任意性 问题得证 3132 RRRR 14 第 75 页第 4 题 证明 设 R 是 A 上的二元关系 1 若 R 是自反的 则 A IR 由于 A I的转置仍是 A I 因此 A IR 故R是自反 的 2 若 R 是反自反的 则 A IR 把 A I和 R 都取转置 由于 A I的转置仍是 A I 因 此 A IR 故R是反自反的 3 若 R 是对称的 任取 y xR 则 x yR 由 R 的对称性可知 y xR 于是 x yR 由 x y 取值的任意性知 R是对称的 4 若 R 是反对称的 任取 y xR 则 x yR 由 R 的反对称性可知 y xR 于是 x yR 由 x y 取值的任意性知 R是反对称的 5 若 R 是可传递得 任取 x yRy zR 则 yxR z yR 由 R 的可传递性 可知 z xR 于是 x zR 故R是可传递的 15 第 75 页第 5 题 解 R 的关系矩阵上 主对角线有多少个非零值 RR的关系矩阵中就有多少非零记入值 16 第 79 页第 2 题 画图略去 解 a r Ra ab b s R t R b r Ra ab ba b s Ra aa bb a t Ra aa b c 图中假设 b 与 c 的连线箭头方向指向 c r Ra ab bc ca bb cc a s Ra bb ab cc ba cc a t Ra bb cc aa cb ac b 17 第 85 页第 2 题 解 121 1 22 21 22 nn n nnn CCC 18 第 85 页第 5 题 改为判断这两个关系是否是等价关系 解 左侧的关系不是等价关系 因为不满足可传递性 右侧的关系是等价关系 19 第 85 页第 7 题 证明 1 当 R 是个等价关系时 由等价关系的定义知 等价关系满足自反性 即 R 是自反的 任取 x y zX x yRy zR 由 R 的可传递性 知 x zR 再 由 R 的对称性 知 z xR 根据 x y z 取值的任意性 知 R 是循环的 2 当 R 是自反的 可知对任意xX x xR 任取yX 使得 x yR 因为 R 是循环的 故当 x xR x yR 时 y xR 由 x y 取值的 任意性知 R 是对称的 任取 x y zX x yRy zR 由 R 的循环性知 z xR 因为 R 是对称的 因此 x zR 由 x y z 取值的任意性 知 R 是 可传递的 因为 R 是自反的 对称的和可传递的 因此 R 是一个等价关系 20 第 86 页第 8 题 证明 设等价关系 1 R造成的集合 X 的划分为 111121 m CCCC 等价关系 2 R造成 的集合 X 的划分为 221222 n CCCC 1 当 1 C中的每一个等价类都包含于 2 C的某一个等价类之中时 任取 1 C中的一个等价 类 1i C 则必包含在 2 C的一个等价类里 设包含在 2 j C中 12ij CC 任取 1i C中 两元素 x y 由等价类的性质知 1 xR y 由 12ij CC 可知若 1 x yR 则 2 x yR 即 2 xR y 由 i j x y 取值的任意性知 12 RR 2 如果 12 RR 那么对任意的 1 x yR 2 x yR 永真 1 x yR 等价于 x y 落入 1 C的某个等价类 1i C中 2 x yR 等价于 x y 落入 2 C的某个 等价类 2 j C中 即若 1 i x yC 则 2 j x y C 由 x y 的任意性可知 12ij CC 由 i 的任意性可知 1 C中的每一个等价类都包含在 2 C的某一个等价类之中 综上所述 当且仅当 1 C中的每一个等价类都包含于 2 C的某一个等价类之中 才有 12 RR 21 第 89 页第 1 题 解 x1 x4 x5 x3 x6x2 1 56 x x 2 56 x x 45 x x 3 56 x x 45 x x 34 x x 35 x x 36 x x 合并后 有 345 x x x 356 x x x 4 345 x x x 356 x x x 23 x x 5 345 x x x 356 x x x 23 x x 12 x x 13 x x 16 x x 合并 得 123 x x x 136 x x x 345 x x x 356 x x x 综上 最大相容类有四个 分别是 123 x x x 136 x x x 345 x x x 356 x x x 22 第 90 页第 4 题 证明 设 X SIRR 1 由于 XX IIRR 因此xX x xS 知 X IRR是自反的 2 任 取 x yX x yS 则 X x yI 或 者 x yR 或 者 x yR 若 X x yI 则xy X y xI y xS 若 x yR 则 yxR y xS 若 xyR 则 yxR R y xS 可知无论任何情况 x yS 则 y xS 故 X IRR是对 称的 综上所述 X IRR既是自反的又是对称的 因此 X IRR是相容关系 23 第 90 页第 5 题 解 23 1111 1 11 1 11 1 1 011 1 1 1 1 1 1 1 1 1 1011 1 11 1 11 1 1 RR RRR MMMM 24 第 90 页第 6 题 证明 11 1 11 1 01 1 R S M 可知R S不是对称的 因此 R S不是等价关系 25 第 90 页第 7 题 举个例子即可 解 1 1 2 2 1 1 3 3 1 X RI 2 1 2 2 1 X RI 26 第 95 页第 1 题 1 1 2 3 4 6 8 24 12 2 1 2 3 4 6 8 12 5 10 9 7 11 27 第 95 页第 4 题 解 集合 X 上的恒等关系 既是偏序关系又是等价关系 28 第 95 页第 5 题 证明 设 R 是 A 上的二元关系 a 若 R 是自反的 则 A IR 由于 A I的转置仍是 A I 因此 A IR 故R是自反 的 b 若 R 是反自反的 则 A IR 把 A I和 R 都取转置 由于 A I的转置仍是 A I 因 此 A IR 故R是反自反的 c 若 R 是对称的 任取 y xR 则 x yR 由 R 的对称性可知 y xR 于是 x yR 由 x y 取值的任意性知 R是对称的 d 若 R 是反对称的 任取 y xR 则 x yR 由 R 的反对称性可知 y xR 于是 x yR 由 x y 取值的任意性知 R是反对称的 e 若 R 是可传递得 任取 x yRy zR 则 yxR z yR 由 R 的可传递性 可知 z xR 于是 x zR 故R是可传递的 从上述 5 条可以证明 1 3 1 若 R 是拟序关系 即 R 是反自反的和可传递得 由 b e 可知 R也是反自反的 和可传递得 因此 R是拟序关系 2 若 R 是偏序关系 即 R 是自反的 反对称的 可传递的 由 a d e 可知 R 也是自反的 反对称的 可传递的 因此 R是偏序关系 3 若 R 是全序关系 则 R 是偏序关系 由 2 知R也是偏序关系 另知 x yA xRy或yRx成立 当xRy时 yRx 当y R x时 xRy 因此不论任何情况 x yA xRy或yRx总成立 综上 R也是全序关系 4 举例子 设 S RN N 是自然数集合 则 S RN 是良序 但是 S RN 不是良序 因为取全集 N 在 S RN 中没有最小成员 第五章第五章 函数函数 1 第 100 页第 3 题 解 Rf 为正奇数的集合 2 第 100 页第 4 题 证明 f 的陪域为 E 设值域为 f R 假定 f 的陪域与值域不相等 即 f RE 那么一定存在 E 的一个元素 A 使得 f AR 因为 1212 f S SSS 因此 不存 在任何一个 12 S S 使得 12 SSA 设 1 SE 则对于任何 2 SE 122 SSS 由 12 SSA 知 2 SA 由 2 S取值的任意性可知 AE 这与 A 的取值在 E 中 相矛盾 因此 f 的陪域与值域不相等不成立 即f的陪域与值域相等 3 第 100 页第 5 题 1 1 1 0 1 0 1 1 1 2 0 1 1 0 0 0 0 1 1 1 1 2 1 0 1 1 1 0 f 2 2 1 0 1 2 f R 3 2 0 1 0 0 0 0 1 1 1 0 1 1 1 0 f 4 f 定义域元素的个数是 9 值域元素的个数是 5 求 2 g AB 的个数 等同于求从 9 个元素的集合到 5 个元素集合满射函数的个数 4 第 103 页第 1 题 解 3 2 3 127gfg xxx 21 21 324fgfxxx 3 3 36fff xxx 21 2 21 143g ggxxx 2 23fhf xx 21 21 21 2h ghxxx 3 3 2hfh xx 1 2 0 5 33 5fh gf h gf xxx 5 第 103 页第 2 题 1 10 种情况 0 0 1 1 2 2 0 0 1 0 2 2 0 1 1 1 2 2 0 0 1 1 2 0 0 2 1 1 2 2 0 0 1 1 2 1 0 0 1 2 2 2 0 1 1 1 2 1 0 2 1 2 2 f f f f f f f f f 一对一 二对一 2 0 0 1 0 2 0 f 三对一 2 4 种情况 0 0 1 1 2 2 0 1 1 0 2 2 0 2 1 1 2 0 0 0 1 2 2 1 f f f f 3 3 种情况 0 1 1 2 2 0 0 2 1 0 2 1 0 0 1 1 2 2 f f f 6 第 105 页第 2 题 1 当存在从 X 到 Y 的单射函数时 mn 单射函数有 m n Cm 2 当存在从 X 到 Y 的满射函数时 mn 满射函数的个数有 1 1 1 2 2 1 1 1 mmmnm nC nnC nnC n n 3 当存在从 X 到 Y 的双射函数时 mn 双射函数的个数有 m个 7 第 115 页第 1 题 证明 任取 x yI g y xy xyxyxxyxyg x y 因此 二元运 算 是可交换的 任取 x y zI g x g y z xyz xyzyz xyzyzx yzyz xyzxyxzyzxyz g g x y z xyz xyxyz xyxyzxyxy z xyzxyxzyzxyz g x g y z 因此 运算 是可结合的 该运算的么元是 0 0 的逆元是 0 2 的逆元是 2 其余元素没有逆元 8 第 116 页第 2 题 证明 任取 x yN xy 由 xyx y xyx 知 y xxy 运算不 是可交换的 任 取 x y zN 由 xyzxzx xy zxyx 知 xyzxyz 运算是可结合的 任取xN x xx 可知 N 中的所有元素都是等幂的 运算有右么元 任取 x yN xyx 知 N 中的所有元素都是右么元 运算没有左么元 证明 采用反证法 假定e为 运算的左么元 取 bN be 由 的运算公式知 e be 由么元的性质知 e bb 得eb 这与be 相矛盾 因此 运算没有左么元 第六章第六章 代数系统代数系统 1 第 121 页第 1 题 证明 首先 U 和 V 都只含有一个二元运算 因此是同类型的 第二 f的定义域是自然数集合N 值域是 0 1 是 V 定义域的子集 第三 验证是否运算的像等于像的运算 任取 x yN 分情况讨论 1 x 和 y 都可以表示成2k 设 12 2 2 kk xy 那么 1212 22 2 1 kkkk f x yff 1f xf y 11 1 f xf yf x y 2 x 和 y 都不能表示成2k 那么x y也不能表示成2k 0f x y 0f xf y 0 00 f xf yf x y 3 x 可以表示成2k y 不能表示成2k 那么x y也不能表示成2k 0f x y 1 0f xf y 1 00 f xf yf x y 4 x 不可以表示成2k y 能表示成2k 那么x y也不能表示成2k 0f x y 0 1f xf y 010 f xf yf x y 可知 无论 x 和 y 如何取值 都能够保证 f xf yf x y 综上所述 f是 U 到 V 的同态映射 2 第 121 页第 2 题 证明 设 Ua b c 1 2 3 V 首先 U 和 V 都仅有一个二元运算 因此 U 和 V 是同类型的 第二 U 和 V 的定义域大小相同 具备构成双射函数的条件 第三 寻找特异元素 U 中么元是 a 右零元是 c 三个元素都是等幂元 V 中么元是 3 右零元是 1 三个元素都是等幂元 第四 在 U 和 V 的定义域之间构造双射函数f 使得 3 2 1f af bf c 把 运算表中的元素都用 f 下的像点代替 得 调整表头的顺序为 1 2 3 转变为下表 跟 V 中 运算表完全相同 因此代数系统 a b c 和 1 2 3 是同构的 3 第 121 页第 3 题 解 首先 判断两个代数系统是否同类型 两个代数系统都只含有一个二元运算 因此满足 同类型 第二 判断两个代数系统定义域的基数是否相同 都是 4 也满足 第三 寻找特异元 为了方便起见 画出其运算表 5 1 2 3 4 1 1 2 3 4 2 2 4 1 3 3 3 1 4 2 4 4 3 2 1 4 0 1 2 3 0 0 1 2 3 1 1 2 3 0 2 2 3 0 1 3 3 0 1 2 3 2 1 3 2 1 3 2 1 2 2 2 1 1 1 1 2 3 1 2 3 1 1 1 2 2 2 1 2 3 V1 和 V2 都有么元 都没有零元 除么元外 都只有一个与自身互为逆元的元素 都没有 等幂元 都满足交换律 第四 构造映射 么元对应么元 10 与自身互为逆元的元素对应与自身互为逆元的元素 42 剩下两个元素不是特异元素 因此我随意指定一种指派 21 33 把 5的运算表中元素都换成对应的像点 构造一张新表 0 1 3 2 0 0 1 3 2 1 1 2 0 3 3 3 0 2 1 2 2 3 1 0 为了便于比较跟 4 是否一致 调整表头的顺序为 0 1 2 3 如下 也就是交换表头 2 和 3 所在的列 交换表头 2 和 3 所在的行 0 1 2 3 0 0 1 2 3 1 1 2 3 0 2 2 3 0 1 3 3 0 1 2 可以看出 上表跟 4 的运算表完全一致 因此 代数系统 5 1 1 2 3 4 V 和 4 2 0 1 2 3 V 是同构的 f 为其同构 映射 定义如下 1 0 2 1 3 3 4 2ffff 4 第 123 页第 1 题 解 首先 判断 m 是否是等价关系 任取xI 由于0 xxm 因此 m xx m 是自反的 任取 x yI 若 m xy 即xya m aI 则yxa m m yx 因此 m 是对称的 任取 x y zI 若 mm xy yz 则xya m aI y z bm bI 于是 xzxyyzabm abI 因此 m xz 可知 m 是可传递的 因此 m 是等价关系 其次 判断 m 关于 是否满足代换性质 任取 x yI 若 m xy 即存在某个pI 满足xyp m mod k xxm mod k yym 则 01112220 1122101 mod k kkkkk kkkk kkkkk kkk xyp mm C yC yp mC yp mC yp m yp mC yC yp mC yp m 于是 1122101 1122101 kkkk kkk kkkk kkk xyp mC yC yp mC yp m pC yC yp mC yp mm 由于 1122101 kkkk kkk pCyCypmCypmI 因此 m xy m 关于 是满足代换性质 综上所述 m 是U上的同余关系 5 第 123 页第 2 题 解 1 对于 运算 在二元运算下 任取 1212 x x y yI 验证下式是否成立 11 22 1212 2 x Ry x Ry xx Ryy 行 取 1212 1 2 1 2xxyy 可知满足 11 x Ry 22 x Ry 但 1212 xxyy 即 12 xx R 12 yy 可知对于运算 R 不满足代换性质 2 对于 运算 在二元运算下 任取 1212 x x y yI 若 11 x Ry 22 x Ry 则必然满足 1122 xyxy 于是 12121212 xxxxyyyy 可得 1212 xx Ryy 由 1212 x x y y取值的任意性可知 对于运算 R 满足代换性质 6 第 123 页第 5