序偶与笛卡儿积

两个具有固定次序的元素 a，b 组成一个有序对被称为$\textcolor{red}{序偶}$序偶，记作 $\textcolor{red}{<a，b>}$<a，b>，其中 a 称作第一个元素，b 称作第二个元素

任意给定两个集合 A 和 B ，所有第一元素属于 A，第二元素属于 B 的序偶所组成的集合，称为 A 和 B 的$\textcolor{red}{笛卡尔积}$笛卡尔积，记作 $\textcolor{red}{A×B}$A×B
$A×B＝\{<x,y>|x∈A,y∈B\}$A×B＝{<x,y>∣x∈A,y∈B}

性质:
$Ø×B＝A×Ø＝\textcolor{red}{Ø} \\A×B\textcolor{red}{≠}B×A \\(A×B)×C\textcolor{red}{≠}A×(B×C) \\A×A×...×A=\textcolor{red}{A^n} \\笛卡儿积运算对\textcolor{red}{∪},\textcolor{red}{∩}或\textcolor{red}{-}运算满足\textcolor{red}{分配律}$Ø×B＝A×Ø＝ØA×B​=B×A(A×B)×C​=A×(B×C)A×A×...×A=An笛卡儿积运算对∪,∩或−运算满足分配律

关系的概念、性质及运算

关系的概念

R=A×A	全等关系
R=Ø	空关系
A=B R⊆A×B	二元关系
IA={<x,x>|x∈A}	恒等关系

$\textcolor{red}{二元关系}$二元关系：
$如果<x,y>∈R，则记作\textcolor{red}{xRy} \\如果<x,y>∉R，则记作\textcolor{red}{x\bar{R}y} \\R 中所有序偶的第一个元素称为 R 的\textcolor{red}{定义域}，记作 \textcolor{red}{dom R} \\R 中所有序偶的第二个元素称为 R 的\textcolor{red}{值域}，记作 \textcolor{red}{ran R}$如果<x,y>∈R，则记作xRy如果<x,y>∈/​R，则记作xRˉyR中所有序偶的第一个元素称为R的定义域，记作domRR中所有序偶的第二个元素称为R的值域，记作ranR

关系的表示

$\textcolor{red}{关系矩阵}$关系矩阵
$m_{ij}= \begin{cases} 1, &\text{} 当<x_i,y_i>∈R; \\ 0, &\text{} 当<x_i,y_i>∉R . \end{cases}$mij​={1,0,​当<xi​,yi​>∈R;当<xi​,yi​>∈/​R.​

关系的性质

xRx 对角线均为 1	自反关系
xRy → yRx 成对元素同时为 1	对称关系
xRy∧yRz → xRz	传递关系
x$\bar{R}$Rˉx 对角线均为 0	反自反关系
xRy∧yRx → x=y 成对元素不同时为 1	反对称关系

关系的复合运算

设 R 是从 X 到 Y 的关系，S 是从 Y 到 Z 的关系，则 R 和 S 的复合是一个从 X 到 Z 的二元关系，记作 $\textcolor{red}{R◦S}$R◦S，为 R 和 S 的$\textcolor{red}{复合关系}$复合关系

$(F ◦ G) ◦ H= F ◦ (G ◦ H) \textcolor{red}{结合律} \\R ◦R ◦...◦R=\textcolor{red}{R^n} \\复合运算对\textcolor{red}{∪},\textcolor{red}{∩}运算满足\textcolor{red}{分配律}$(F◦G)◦H=F◦(G◦H)结合律R◦R◦...◦R=Rn复合运算对∪,∩运算满足分配律

关系的逆运算

$\textcolor{red}{逆关系}$逆关系：
$\textcolor{red}{R^{-1}}={<y,x>|<x,y>∈R}$R−1=<y,x>∣<x,y>∈R

关系的闭包运算

自反闭包	$r(R)=R∪I_A$r(R)=R∪IA​
对称闭包	$s(R)=R∪R^{-1}$s(R)=R∪R−1
传递闭包	$t(R)=R∪R^{2}∪...=\bigcup_{i=1}^{n}R^{i}$t(R)=R∪R2∪...=i=1⋃n​Ri

$rs(R)=sr(R) \\rt(R)=tr(R) \\st(R)⊆ts(R)$rs(R)=sr(R)rt(R)=tr(R)st(R)⊆ts(R)

特殊关系

等价关系

设 R 是集合 X 上的二元关系，若 R 是$\textcolor{red}{自反的、对称的和传递的}$自反的、对称的和传递的，则称 R 是$\textcolor{red}{等价关系}$等价关系

A 可以$\textcolor{red}{划分}$划分成两两不相交的非空子集（$\textcolor{red}{划分块}$划分块）的并集
$\textcolor{red}{交叉划分 A\sqcap B}=\{A_i∩B_j|A_i∩B_j≠Ø\}$交叉划分A⊓B={Ai​∩Bj​∣Ai​∩Bj​​=Ø}

设 R 是集合 X 上的等价关系，$\forall x\in X$∀x∈X，则所有与 x 具有等价关系 R 的元素的集合称为元素 x 形成的$\textcolor{red}{等价类}$等价类，记作 $\textcolor{red}{\left [ x \right ]_{R}}$[x]R​，即 $\left [ x \right ]_{R}=\left \{ a|a\in X\wedge xRa \right \}$[x]R​={a∣a∈X∧xRa}

集合 X 上所有元素形成的 R 等价类的集合称为 X 关于 R 的$\textcolor{red}{商集}$商集，用 $\textcolor{red}{X/R}$X/R 表示，即 $X/R=\left \{ \left [ a \right ]_{R}|a\in X \right \}$X/R={[a]R​∣a∈X}

• 例
  $R 是整数集 Z 上的模 4 同余关系，求解 Z/R. \\Z/R=\{[0]_R,[1]_R,[2]_R,[3]_R\}$R是整数集Z上的模4同余关系，求解Z/R.Z/R={[0]R​,[1]R​,[2]R​,[3]R​}

相容关系

设 R 是定义在集合 X 上的二元关系，若 R 满足$\textcolor{red}{自反的、对称的}$自反的、对称的性质，则称 R 是$\textcolor{red}{相容关系}$相容关系

设 R 是集合 X 上的相容关系，且 $C⊆X$C⊆X，若对 C 中任意两个元素 $c_1$c1​ 和 $c_2$c2​ ，有$<c_1,c_2>∈ R$<c1​,c2​>∈R，称 C 是由相容关系 R 产生的$\textcolor{red}{相容类}$相容类
设 R 是集合 X 上的相容关系，不能真包含在其他相容类中的相容类，称作$\textcolor{red}{极大相容类}$极大相容类
在关系简图中，若有子图 G，使子图中$\textcolor{blue}{任何两点都有连线}$任何两点都有连线，则称 G 是$\textcolor{red}{完全多边形}$完全多边形.不能找到别的完全多边形真包含该子图，则称此完全多边形是$\textcolor{red}{极大完全多边形}$极大完全多边形.
极大完全多边形所对应的顶点集合就是极大相容类

$\textcolor{red}{覆盖}$覆盖：
$\\A_{i}\subseteq A(i=1,2,...,m) \\A_{i}\neq \varnothing \\\bigcup_{i=1}^{m}A_{i}=A$Ai​⊆A(i=1,2,...,m)Ai​​=∅i=1⋃m​Ai​=A
所有极大相容类构成的集合称为 X 的$\textcolor{red}{完全覆盖}$完全覆盖

偏序关系

设 R 是集合 X 上的二元关系，如果 R 是$\textcolor{red}{自反的、反对称的和传递的}$自反的、反对称的和传递的，则称 R 是 X 中的$\textcolor{red}{偏序关系}$偏序关系，一般记作 $\textcolor{red}{\leq}$≤.带有偏序关系的集合称为$\textcolor{red}{偏序集}$偏序集，记作$\textcolor{red}{<X,\leq >}$<X,≤>

$设 \leqslant 是集合 X 上的偏序关系，a,b\in X，若 a\leq b 或 b\leq a，则称 a，b $\textcolor{red}{可比较的}$可比较的，否则称a，b是不可比较的.$

$\textcolor{red}{哈塞图}$哈塞图

1. $省略所有节点的自回路$省略所有节点的自回路
2. $都是单向边，若 x<y 就把 x 画在 y 的下方，令所有边的方向都是向上的$都是单向边，若x<y就把x画在y的下方，令所有边的方向都是向上的
3. $若a\leq b，b\leq c，则有a\leq c，故连接a与c的有向边省略$若a≤b，b≤c，则有a≤c，故连接a与c的有向边省略

	b 在集合内，a 不一定
极大元	$没有任何其他元素 x 满足 b\leq x$没有任何其他元素x满足b≤x
极小元	$没有任何其他元素 x 满足 x\leq b$没有任何其他元素x满足x≤b
最大元	$所有子集元素 x 满足 x\leq b$所有子集元素x满足x≤b
最小元	$所有子集元素 x 满足 b\leq x$所有子集元素x满足b≤x
上界	$所有子集元素 x 满足 x\leq a$所有子集元素x满足x≤a
下界	$所有子集元素 x 满足 a\leq x$所有子集元素x满足a≤x
上确界	$最小上界，记作 lub B$最小上界，记作lubB
下确界	$最大下界，记作 glb B$最大下界，记作glbB

	{1,3,4,5,6,12}	{1,2,3,6,12}	{3,5,6}
极大元	5,12	12	5,6
极小元	1	1	3,5
最大元		12
最小元	1	1
上界		12
下界	1	1	1
上确界		12
下确界	1	1	1

全序关系

	任一单元素子集既是链也是反链
全序关系	任何两个元素都是$\textcolor{red}{可比较的}$可比较的
全序集	$<A,\leq >$<A,≤>
链	全序集
链的长度	元素的个数
反链	任何两个不同元素之间都$\textcolor{red}{没有关系}$没有关系
良序关系	任一非空子集都有$\textcolor{red}{最小元}$最小元
拟序关系	反自反的、反对称的、传递的