离散数学基础 · 第 3 讲：笛卡尔积与二元关系
本页目录
离散数学基础
第三讲
2026年9月15日
1. 有序对与笛卡尔积
有序对 的两个位置不能随意交换； 当且仅当 且 。笛卡尔积定义为
若 、，则 。
1.1. 基本性质
- 。
- 一般没有交换律： 与 的序偶位置不同。
- 一般没有结合律： 的元素是 ，而 的元素是 。
对并、交有分配律：
左侧因子为并、交时也成立。- 若 且 ，则 。反过来只有在 均非空时，才可推出两个因子的包含关系；若某个因子为空，乘积为空，便无法由乘积判断另一因子。
分配律的元素证明： 当且仅当 且 ，等价于 。
1.2. 课件例题：判断真伪
- ：一般为假。取 、、，两边乘积均为空。若另加 ，则命题为真。
- ：一般为假。取 、，左边为 ，右边为空集。
- 、：真，由等量代入即可。
- 存在 ：真，取 。
2. 二元关系
定义： 非空且所有元素都是有序对的集合，以及空集，都称为二元关系。 记作 ；不成立时可写作 ，避免把带斜线的关系符号误读为另一个关系。
称为从 到 的关系； 称为 上的关系。若 ，则 上共有 个关系，因为 有 个序偶，每个序偶都可独立选择是否属于关系。
2.1. 常见关系
- 空关系：；全域关系：。
- 恒等关系：。
- 若 ，小于等于关系为 。
- 若 ，整除关系为 ，这里 表示 整除 。
- 在集族 上，包含关系由 定义。
2.2. 关系矩阵与关系图
设 ， 为 上的关系。按固定顺序排列行、列，定义
关系图以 的元素为顶点，每个 对应一条从 指向 的边； 对应自环。矩阵、图与关系本身一一对应。
例如 ，，按 排序，
3. 关系的运算
3.1. 定义域、值域与域
例如 ，则定义域为 ，值域为 ，域为 。
3.2. 逆关系与复合
逆关系交换每个序偶的两个位置：
所以 ，，。
本课程采用右复合： 表示先经过 ，再经过 ，
例如 、，则 ，而 ；复合一般不交换。
复合满足结合律 ，并有 。若 是 上的关系，则 。
对并有分配律，对交一般只有包含关系：
第二式可能严格包含，因为右侧两种复合可以分别使用不同的中间元素。
3.3. 限制与像
关系 在集合 上的限制只保留第一元素位于 的序偶：
这里 称为 在 下的像。对于集合 ，
像的交式未必取等号：同一个像元素可分别由 、 中不同的原像得到。
3.4. 关系的幂与布尔矩阵
若 是 上的关系，定义 ，。由结合律得
图中 当且仅当存在从 到 的恰好 步有向走法。
若 为关系矩阵，则 是 的 次布尔矩阵乘积；其中乘法为“且”，加法为“或”：
例如课件关系 、 有
于是 （路径 ），但 ；此例还满足 。
3.5. 有穷集上关系幂的最终周期性
定理： 若 且 ，则存在自然数 使 。
证明： 上只有 个不同关系，而 共列出 个关系。由鸽巢原理，至少两个相等。
令 。由幂的加法公式，对任意 ，
因此从 开始，幂序列以 为一个周期；对 ，。所有高次幂都等于 中的某一个。
课件例： 若关系图由一个长度为 2 的环和一个长度为 3 的环组成，两部分周期的最小公倍数为 6，所以 ，之后每隔 6 次幂重复。对一般关系，周期可能从某个正指数才开始，未必从 开始。