教材：《离散数学》第2版 屈婉玲 耿素云 张立昂 高等教育出版社
源文档高清截图在最后

第7章 二元关系

7.1 有序对与笛卡尔积

1、由两个元素x、y（可以相同）有序排列成的二元组称为有序对或有序偶，记作<x，y>，x和y分别称作它的第一元素、第二元素。有序对<w, x>和<y, z>相等的充分必要条件是：w = y且x = z。这个性质是二元集{x, y}不具备的，因为有序对中的元素有序而集合中的元素无序。

2、设集合A、B。分别用A和B的一个元素作第一、第二元素构成有序对，所有这样的有序对的集合称为A和B的笛卡尔积，记作A×B。其符号化表示为：{<x, y> | x∈A且y∈B}。易证：若|A| = m，|B| = n，则|AB| = mn。

3、笛卡尔积的性质：
【1】由定义，设集合A，则A×∅ = ∅，∅×A = ∅。
【2】笛卡尔积一般不满足交换律，即A×B≠B×A（当A、B≠∅且A≠B）。
【3】笛卡尔积一般不满足结合律，即(A×B)×C≠A×(B×C)（当A、B、C≠∅）
【4】笛卡尔积运算×对并∪和交∩满足分配律，即：
A×(B∪C) = (A×B)∪(A×C)
(B∪C)×A = (B×A)∪(C×A)
A×(B∩C) = (A×B)∩(A×C)
(B∩C)×A = (B×A)∩(C×A)
这里只证明第一式。
证明 任取<x, y>。

【5】
该性质的证明方法同【4】类似。但性质【5】的逆命题不一定成立：
（1）当A = B = ∅时，逆命题显然成立。
（2）当A、B≠∅时，逆命题成立。
证明 任取x∈A、y∈B，则

所以。同理可证
（3）当A = ∅而B≠∅时，仅有成立，不一定有成立。反例：A = ∅，B = {1}，C = {3}，D = {4}。
（4）当A≠∅而B = ∅时，仅有成立，不一定有成立。反例：A = {1}，B = ∅，C = {3}，D = {4}。

7.2 二元关系

1、如果一个集合的元素全部是有序对，或者集合为空，就说这个集合是一个二元关系，简称关系，记作R。<x, y>∈R可记作xRy。

2、如果A、B为集合，A×B的任何子集定义的二元关系都称作从A到B的二元关系。特别地，A = B时可以直接称A上的二元关系。

3、对n元集合A，|A×A| = n2，一共能构造个不同的关系，其中空集∅称作A上的空关系。对任意集合A，又有全域关系UA = {<x，y> | x∈A∧y∈A}，恒等关系IA = {<x, x> | x∈A}。显然A上的任何关系都是全域关系的子集。除了这3种特殊关系以外，常用的关系还有：小于等于关系LA = {<x, y> | x, y∈A，x≤y}，整除关系DA = {<x, y> | x, y∈A，x | y}，包含关系。类似地，还可以定义大于等于关系、小于关系、大于关系、真包含关系等。

4、表述一个关系的方法有：列元素法、集合表达式、关系矩阵、关系图等。设A = {x1，x2，……，xn}及A上的关系R。令，则可以构造R的关系矩阵。还可以构造R的关系图GR。GR有n个顶点x1，x2，……，xn，如果<xi, xj>∈R，在中就有一条从xi到xj的有向边。