离散数学5.1-二元关系一

一、有序对和笛卡尔积

1、有序对（序偶）：由两个元素 x 和 y 按照确定顺序排列组成的二元组，记作⟨x, y⟩

2、笛卡尔积：以 A 中元素为第一元、B 中元素为第二元，构造所有有序对⟨x,y⟩； 由全部这类有序对构成的集合，称为 A 与 B 的笛卡尔积，记作 AXB

例题：

已知 A={a,b}, B={0,1,2}，求笛卡尔积 A × B、B × A

• A × B（前元取自 A，后元取自 B）

  A × B = {<a,0>,<a,1>,<a,2>,<b,0>,<b,1>,<b,2> }

• B × A（前元取自 B，后元取自 A）

  B × A = {<0,a>,<0,b>,<1,a>,<1,b>,<2,a>,<2,b> }

tips：可以当线性代数来理解，都是A × B 不等于 B × A

二、二元关系

1、基本概念

例题：设集合X={1，2，3}，R 为 X 上的小于关系，求 R=________。

解题思路：当X=X的时候就称为X上的二元关系，而小于关系就是<a,b>其中a<b

所以X x X={<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<2,3>,<3,1>,<3,2>,<3,3>}

而小于关系则R={<1,2>,<1,3>,<2,3>}

所以答案为：R={<1,2>,<1,3>,<2,3>}

例题：设集合 A，且 |A|=3，则 A 上最多可定义___个不同二元关系。

• 若集合元素个数|A|，笛卡尔积 A x A的有序对总数：n^2

• A 上的二元关系是 A x A 的子集；一个含 m 个元素的集合，子集总数为 2^(m^2)

所以答案为：2^(3^3)=512

2、关系矩阵和关系图

关系矩阵：N个元素的集合下，NxN大小的矩阵，根据<行,列>在矩阵中画1，其余为0

关系图：N个元素的集合下，1~N个端点，根据<起点,终点>连线

根据原理：关系矩阵：N个元素的集合下，NxN大小的矩阵，根据<行,列>在矩阵中画1，其余为0，那么可以得出答案：

注意：因为原题没出现数字元素，所以要用出现的字母元素来表示

3、定义域、值域、域

1、概念：

tips：<第一元素，第二元素>

例题：

4、逆关系和右复合

简单来说：

逆关系R⁻¹：全部反着写

比如 R = {<1,2>,<3,1>} → R⁻¹ = {<2,1>,<1,3>}

右复合R∘S：从R的终点出发，能找到S里以它为起点的，就连过去，并以R的起点和S的终点为一个元素。

比如 R = {<1,2>,<2,3>}，S = {<2,a>,<3,b>} → R∘S = {<1,a>,<2,b>}