第5章 习题解答
5.1 A:③; B:⑥; C:⑧; D:⑩; E:⑨
分析 S为n元集,那么有个元素.S上的一个二元运算就是函数SS2
n
.这样的函数有个.因此上的二元运算有个. SSSf:2
n
n},{ba162
n
n
下面说明通过运算表判别二元运算性质及求特导元素的方法.
1 °交换律 若运算表中元素关于主对角线成对称分布,则该运算满足交换
律.
2 °幂等律 设运算表表头元素的排列顺序为如果主对角线元,,,
21nxxx
素的排列也为 则该运算满足幂等律. ,,,
21nxxx
其他性质,如结合律或者涉及到两个运算表的分配律和吸收律,在运算表中
没有明显的特征,只能针对所有可能的元素等来验证相关的算律是否成立. zyx,,
3 ° 幺元设运算表表头元素的排列顺序为如果元素所在的.e,,,
21nxxx
ix
行和列的元素排列顺序也是则为幺元. ,,,
21nxxx
ix
4 ° 零元如果元素所在的行和列的元素都是,则是零元. .
ix
ix
ix
5 ° 幂等元.设运算表表头元素的排列顺序为如果主对角线上,,,
21nxxx
第个元素恰 为那么是幂等元.易见幺元和零元都是幂等元. i},,2,1{nix
i
ix
6 ° 可逆元素及其逆元.设为任意元素,如果所在的行和列都有幺元,并
ix
ix
且这两个幺元关于主对角线成对称分布,比如说第行第列和第行第列的两ijji
个位置,那么与互为逆元.如果所在的行和列具有共同的幺元,则幺元一
jx
ix
ix
定在主对角线上,那么的逆元就是自己.如果所在的和地或者所在的列没
ix
ix
ix
有幺元,那么不是可逆元素.不难看出幺元一定是可逆元素,且;而零
ixeee1
元不是可逆元素.
以本题为例,的运算表是对称分布的,因此,这三个运算是可交换的,
321,,fff而不是可交换的.再看幂等律.四个运算表表头元素排列都是,其中主对角
4fba,
线元素排列为的只有,所以, 遵从幂等律.下面考虑幺元.如果某元素所ba,
主要内容
1.
有序对与笛卡儿积
2.
二元关系（包括空关系, 恒等关系, 全域关系等）及其表示（关系矩阵, 关系图）
3.
关系的五种性质（自反性, 反自反性, 对称性, 反对称性, 传递性）
4.
二元关系的运算（定义域、值域、域、逆、合成、限制、像、幂）
5.
关系的三种闭包（自反闭包, 对称闭包, 传递闭包）
6.
等价关系和划分（包括等价类, 商集, 划分块等）
7.
偏序关系（包括哈斯图, 最大元, 最小元, 极大元, 极小元, 上界, 下界, 最小上界, 最大下界等）
学习要求
1.
掌握：有序对及卡氏积的概念及卡氏积的性质
2.
掌握：二元关系, A到B的二元关系, A上的二元关系, 关系的定义域和值域, 关系的逆, 关系的合成, 关系在集合上的限制, 集合在关系下的象等概念, 掌握关系的定义域、值域、逆、合成、限制、像等的主要性质
3.
掌握：关系矩阵与关系图的概念及求法
4.
掌握：集合A上的二元关系的主要性质（自反性, 反自反性, 对称性, 反对称性, 传递性）的定义及判别法, 对某些关系证明它们有或没有其中的性质
5.
掌握：A上二元关系的n次幂的定义及主要性质
6.
掌握A上二元关系的自反闭包、对称闭包、传递闭包的定义及求法
7.
掌握：等价关系、等价类、商集、划分等概念, 以及等价关系与划分之间的对应
8.
掌握：偏序关系、偏序集、哈斯图、最大元、最小元、极大元、极小元、上界、下界、上确界、下确界等概念
典型习题
1.
下列等式中哪些成立？哪些不成立？为什么？
2.
设A={1,2,3}, R={|x,y∈A且x+3y<8}, S={<2,3>,<4,2>}, 求下列各式：
3.
说明下列关系是否是自反的、对称的、传递的或反对称的. 4.
设R是二元关系, 设S={|存在某个c, 使得∈R且∈R}. 证明如果R是等价关系, 则S也是等价关系.
专题二：欧拉图与欧拉路径
该材料用于图论第2讲课问题说明及自学提示环节与学生课外自学环节
自学章节： 8.2.4
学时安排：课内2学时，课外6学时
重点：欧拉定理及推论、实际问题转换为欧拉图求解
问题一：一笔画问题
有347个顶点的完全图能否一笔画？有1286个顶点的完全图呢？
问题二：蚂蚁比赛问题
甲、乙两只蚂蚁分别位于下图中的结点a，b处，并设图中的边长度是相等的。甲、乙进行比赛：从它们所在的结点出发，走过图中的所有边最后到达结点c处。如果它们的速度相同，问谁先到达目的地？
问题三：展览馆游览问题
一展览馆平面图如下：一参观者来到展览馆门外，他想在参观过程中把所有门都不重复的穿行一遍，问他能办到吗？为什么？
问题提示：
图模型的构建是关键。
问题四：多米诺骨牌问题（例8.2-2）
多米诺骨牌骨牌的一面可以是0,1,2,3,4,5,6中的一个数字，问：是否能将28张不同（只要有一面不同视为牌不同）的多米诺骨牌排成一个圆形,使得在这个排列中,每两块相邻的骨牌其相邻的两个半面是相同的?
提示：
图模型的构建是关键。教材分析很含糊。
问题五：布鲁英(DeBruijn)序列问题
造出一个长度为16的布鲁因序列
提示：
参看例8.2-3，如何构造8长度的布鲁因序列。这是有向欧拉图在译码上面的应用。
主要内容
1.
有序对与笛卡儿积
2.
二元关系（包括空关系, 恒等关系, 全域关系等）及其表示（关系矩阵, 关系图）
3.
关系的五种性质（自反性, 反自反性, 对称性, 反对称性, 传递性）
4.
二元关系的运算（定义域、值域、域、逆、合成、限制、像、幂）
5.
关系的三种闭包（自反闭包, 对称闭包, 传递闭包）
6.
等价关系和划分（包括等价类, 商集, 划分块等）
7.
偏序关系（包括哈斯图, 最大元, 最小元, 极大元, 极小元, 上界, 下界, 最小上界, 最大下界等）
学习要求
1.
掌握：有序对及卡氏积的概念及卡氏积的性质
2.
掌握：二元关系, A到B的二元关系, A上的二元关系, 关系的定义域和值域, 关系的逆, 关系的合成, 关系在集合上的限制, 集合在关系下的象等概念, 掌握关系的定义域、值域、逆、合成、限制、像等的主要性质
3.
掌握：关系矩阵与关系图的概念及求法
4.
掌握：集合A上的二元关系的主要性质（自反性, 反自反性, 对称性, 反对称性, 传递性）的定义及判别法, 对某些关系证明它们有或没有其中的性质
5.
掌握：A上二元关系的n次幂的定义及主要性质
6.
掌握A上二元关系的自反闭包、对称闭包、传递闭包的定义及求法
7.
掌握：等价关系、等价类、商集、划分等概念, 以及等价关系与划分之间的对应
8.
掌握：偏序关系、偏序集、哈斯图、最大元、最小元、极大元、极小元、上界、下界、上确界、下确界等概念
典型习题
1.
下列等式中哪些成立？哪些不成立？为什么？
2.
设A={1,2,3}, R={|x,y∈A且x+3y<8}, S={<2,3>,<4,2>}, 求下列各式：
3.
说明下列关系是否是自反的、对称的、传递的或反对称的. 4.
设R是二元关系, 设S={|存在某个c, 使得∈R且∈R}. 证明如果R是等价关系, 则S也是等价关系.
