二元关系 离散数学
离散数学是数学的一个分支，主要研究离散的数学结构和离散的数学对象。其中，二元关系是离散数学中的一个重要概念。
二元关系是指两个集合之间的关系，通常用一个有序对表示。例如，设A={1,2,3}，B={a,b,c}，则{(1,a),(2,b),(3,c)}就是A和B之间的一个二元关系。在这个关系中，1和a有关系，2和b有关系，3和c有关系。
二元关系有很多种类型，其中比较常见的有等价关系、偏序关系和全序关系。
等价关系是指具有自反性、对称性和传递性的关系。例如，设A={1,2,3}，则{(1,1),(2,2),(3,3),(1,2),(2,1),(2,3),(3,2)}就是A上的一个等价关系。在这个关系中，1和1等价，2和2等价，3和3等价，1和2等价，2和1等价，2和3等价，3和2等价。
偏序关系是指具有自反性、反对称性和传递性的关系。例如，设A={1,2,3}，则{(1,1),(2,2),(3,3),(1,2),(1,3),(2,3)}就是A上的一个偏序关系。在这个关系中，1和1有关系，2和2有关系，3和3有关系，1和2有关系，1和3有关系，2和3有关系，但是2和1没有关系，3和1没有关系，3和2没有关系。
全序关系是指具有自反性、反对称性、传递性和连通性的关系。例如，设A={1,2,3}，则{(1,1),(2,2),(3,3),(1,2),(1,3),(2,3),(3,1),(2,1),(3,2)}就是A上的一个全序关系。在这个关系中，1和1有关系，2和2有关系，3和3有关系，1和2有关系，1和3有关系，2和3有关系，3和1有关系，2和1有关系，3和2有关系。
二元关系在离散数学中有着广泛的应用，例如在图论、集合论、逻辑学等领域都有着重要的作用。因此，对于离散数学的学习和研究，二元关系是一个不可或缺的重要内容。
第3章 二元关系练习题
一、 单项选择题
1. 设集合A＝{0,b},B={1,b,3},则AB上的恒等关系是 ( ).
(A) {<0,0>,<1,1>,<3,3>} (B){<0,0>,<1,1>,,<3,3>}
(C) {<1,1>,,<3,3>} (D) {<0,1>,<1,b>,<3,0>}
2. 已知集合A＝{a,b,c}上的二元关系R的关系矩阵MR＝001011010，那么R＝( )，
(A) {,,,} (B) {,,,}
(C) {,,,} (D) {,,,}
3. 设集合A={1,2,3,4}, A上的二元关系R的关系矩阵为
MR＝0000000001011001
则关系R的表达式是( )
(A) {<1,1>,<1,4>,<2,1>,<2,3>} (B) {<1,1>,<1,2>,<1,4>,<2,3>}
(C) {<1,1>,<2,1>,<3,2>,<1,4>} (D) {<1,1>,<2,1>,<3,2>,<4,1>}
4. 设A={a，b，c}，R={，}，则R具有性质（ ）
(A) 自反的 (B) 反自反的 (C) 反对称的 (D) 等价的
5. 设R是集合A上的二元关系，IA是A上的恒等关系，如果RIA，则下面四个命题中为真的是（ ）
(A) R不是自反的 (B) R不是传递的 (C) R不是对称的 (D) R不是反对称的
二、填空题
1. 设R，S都是集合A上的等价关系，则对称闭包s(RS)=
第七章作业
评分要求：
1. 合计100分
2. 给出每小题得分(注意: 写出扣分理由).
3. 总得分在采分点1处正确设置.
1 设R={|x,y∈N且x+3y=12}.【本题合计10分】
(1) 求R的集合表达式(列元素法);
(2) 求domR, ranR;
(3) 求R◦R;
(4) 求R↾{2,3,4,6};
(5) 求R[{3}];
解
(1) R={<0,4>,<3,3>,<6,2>,<9,1>,<12,0>}【2分】
(2) domR={0,3,6,9,12}, ranR={0,1,2,3,4}【2分】
(3) R◦R={<3,3>, <0,4>}【2分】
(4) R↾{2,3,4,6}={<3,3>, <6,2>}【2分】
(5) R[{3}]={3}【2分】
2 设R,F,G为A上的二元关系. 证明:
(1)R◦(F∪G)=R◦F∪R◦G
(2)R◦(F∩G)⊆R◦F∩R◦G
(3)R◦(F◦G)=(R◦F)◦G.
【本题合计18分：每小题6分，证明格式正确得3分，错一步扣1分】
证明
(1)∀,
∈R◦(F∪G)
⇔ ∃t (xRt∧t(F∪G)y) 复合定义
⇔ ∃t(xRt∧(tFy∨tGy) ∪定义
⇔ ∃t((xRt∧tFy)∨(xRt∧tGy)) ∧对∨分配律
⇔ ∃t(xRt∧tFy)∨∃t(xRt∧tGy) ∃对∨分配律
⇔ x(R◦F)y∨x(R◦G)y 复合定义
⇔ x(R◦F∪R◦G)y ∪定义
得证
(2)∀,
x(R◦(F∩G))y
⇔ ∃t(xRt∧t(F∩G)y) 复合定义
⇔ ∃t(xRt∧(tFy∧tGy)) ∩定义
⇔ ∃t((xRt∧tFy)∧(xRt∧tGy)) ∧幂等律, ∧交换律, ∧结合律
⇒ ∃t(xRt∧tFy)∧∃t(xRt∧tGy) 补充的量词推理定律
⇔ x(R◦F)y∧x(R◦G)y 复合定义
⇔ x(R◦F∪R◦G)y ∪定义 得证
专题二：欧拉图与欧拉路径
该材料用于图论第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长度的布鲁因序列。这是有向欧拉图在译码上面的应用。
