离散数学关系纲要

2.1 关系

序偶

• <x, y>: 两个数值形成一个pair, 有顺序;
• <x1,x2, ..., xn>: 有序n元组;

笛卡尔积

• 集合A<1, 2> X 集合B<a, b, c> = {<1,a>, <1,b>,<1,c>,<2,a>,<2,b>,<2,c>} (AXB)
• 是矩阵的创建运算;

关系(二元关系为主)

• AXB的关系就是AXB的子集;
• A上的关系就是AXA的子集;
• 记号: xRy;

恒等关系

• 记号: Ix = {<x, x>|x∈X}; 换句话说, 所有X矩阵主对角线上的序偶的集合叫做X的恒等关系;
• X={a, b ,c}; then Ix = {<a,a>, <b,b>, <c,c>};
• 恒等关系必须遍历整个对角线;

自反和反自反关系

• 所有的<x, x>都属于R的话, R就是自反的; 换句话说, Ix是R的子集;
• 所有的<x, x>都不属于R的话, R就是反自反的; 换句话说对任意元素∈Ix, 都不在R中;

对称和反对称关系

• 对称关系: 所有的xRy都有yRx, R就是对称的;
  • xRy and yRx coexists ==> R是对称的;
  • 可以是x==y也可以是x!=y
  • {<1,2>, <2,1>, <3,3>}
• 反对称关系: if (xRy && yRx), then {x==y must be true}; 换句话说, no (x!=y) && (xRy && yRx) shall exist;
  • {<1, 1>, <1, 3>, <3, 2>}
• 反对称和对称关系的交集
  • {<1,1>, <2,2>, <3,3>}, 也就是恒等关系Ix的一个子集;

传递关系

• 类似反对称关系
• if (xRy && yRz) {xRz shall exists;} 换句话说: 不允许已经出现xRy&&yRz 却没有xRz;
• e.g. R1 = {<1, 2>, <2, 3>, <1, 3>} R2 = {<1, 3>, <2, 3>}

2.2. 关系矩阵和关系图

关系矩阵

• 把R中的序偶在矩阵中填上1, 其余XXY的其他位置填上0.
• 注意: XXY矩阵大小为|X|行|Y|列;
• 例如: X={1, 2, 3} Y={5,6,7} XXY矩阵(记住笛卡尔积可以创建矩阵)是3*3规模;

关系图

2.3, 2.4 关系的运算(连接, 逆, 闭包)

连接运算

• 对于XXY, YXZ上的关系R和S, 生成一个包含所有满足<x,y>&&<y,z>的<x, z>的集合;
• 记号: R·S;
• 例如: R={<1,1>, <1,2>} S={<2,3>}, 那么R·S = {<1,3>}
• 关系的连接本质上可以用逻辑门化的矩阵乘法来表示, 换句话说矩阵上只有1 and 0;
• 矩阵运算的规则, 矩阵左第一行逐个乘矩阵右第一列, 第二列, 第n列; 第二行逐个乘矩阵右第一列, 第二列, 第n列.......

逆运算

• 对XXY的关系R, R的逆, R^(-1), 是YXX上的关系, 满足R^(-1) = {<y,x>| <x,y>∈R};
• 相当于矩阵的逆关系;
• 逆关系的类指数运算性质对交际, 并集和差集运算起作用;

闭包运算

设R是集合X上的二元关系(也就是R在X×X上)

• 自反闭包
  • 包含R 最小的 自反关系 r(R)
  • r(R) = R∪Ix;
• 对称闭包
  • 包含R 最小的 对称关系 s(R)
  • s(R) = R∪R逆
• 传递闭包
• 包含R 最小的 传递关系 t(R) R^+
• t(R) = ∪(1~无穷) R^i
• 总存在一个正整数k<=n (X为n元集), 使得t(R) = R∪R^2∪...∪Rk;

2.5 等价关系和相容关系

覆盖和划分

• 覆盖: ∪(1~n)A[i] = S, 则 集合{A[1], ..., A[n]}是集合S的一个覆盖;
• A[1], A[2]等集合可能会有重叠, 交集的部分;
• 划分: ∪(1~n)A[i] = S, 且A[1]∩A[2]∩...∩A[n]=∅. 则集合{A[1], ..., A[n]}是集合S的一个划分;

• 其中A[1]等单个子集会被叫做划分块.

  
  这是一个划分, 划分属于覆盖的特殊形式

等价关系

• X上的关系R, R同时又自反性, 对称性和传递性, 那么R是等价关系.
  • 比如X={1, 2, 3} R1={<1,1>, <2,2>, <3,3>}是等价关系, R2={<1,1>, <2,2>, <3, 3>, <1,2>,<2,1> } 也是等价关系
• 若X×X上有R是等价关系, 那么其中属于X的一个元素a, 和同样属于X的一个元素b, 有<a, b>∈R, 那么我们说a等价于b, 即aRb等价于<a,b>∈R;
  • [x][R]称为x关于R的等价类, 也写作[x]; 举例子, 上面例子R1中的[1] = {1}, R2中[1] = {1, 2};
• 同余类是等价关系;

等价产生划分定理

• 如果R是X上的一个等价关系, 那么由R可以产生唯一的一个对X的划分;
• 例子: 有一个动物园, 有一个等价关系是猫科动物, 那么动物园的动物们就自动形成了一个划分, 要么是猫科动物, 要么不是猫科动物. 一只动物, 只能属于或者不属于;

相容关系

• X上的一个关系R, 如果只是自反的和对称的, 而不能保证传递性, 那么则称R是一个相容关系;
• 相容关系的实例化: the pair has something in common. compatible relation实际上显示了两个元素之间有一定的相同性质, 但是不能保证两两之间相同的属性是一致的; 比如苹果a, b都有属性>500g, 而b, c都有属性sweet, 我们说a, b是相容的, b, c也是相容的; 但是我们不能确定 a,c相容, 也就是说不能确定他们有交集;

偏序关系

偏序关系定义

• 集合X上的关系R, 具有自反性, 反对称性, 传递性, 那么就叫做一个偏序关系(≤, Partial Order Relation).
• 注意≤是个特殊的记号, 不等同于"小于等于", 尽管小于等于是一个例子.
• 称呼R为一个偏序, 一个集合A与A上的偏序关系R一起叫作偏序集，记作<A,R>或<A, ≦>, 这么写是为了强调这个偏序关系集合是A的一个子集, 是建立在A集合上的, 区别于<B,≤>, <C,≤>。
• 举例子: 整除关系. X = {3, 5, 6, 12} R = {<3,3>,<3,6>, <3,12>, <6, 12>}, 3能被3自己整除, 满足自反性; 6能被3整除, 3反过来不能被6整除, 反对称; 而6能被3整除, 12能被6整除, 那么12一定能被3整除, 传递性;

全序=线性序, 全序集=链

• <X, ≤>, 即建立在集合X上的偏序关系R, 对所有的, 任意的a, b∈X, 也就是C(2, n)都有a≤b or b≤a(即<a, b>∈R||<b,a>∈R 为true), 那么<X, ≤>是全序集, 此处的≤是X的一个全序/线性序.
  上的一个全序;
• 实例化: 实数关系中的大于等于关系 比如X={2,3,4} <X, ≤> = {<3,2>, <4,2>, <4,3>}.
• 全序在HASSE图上自动地体现为一条线;

盖住

• 偏序关系中, 如果去掉自反性, 也就是R中删掉所有<a, a>这种后所剩下的集合, 记作＜;
• 如果a<b且没有间隙, 即不存在a<i且i<b; 称作b盖住a;

偏序关系画HASSE图

• 小圆圈表示集合X中的元;
• x<y, 那么x的小圆圈在下面, y的校园选在上面;
• 当y盖住x的是时候, x和y之间连一条线;

最小元, 最大元, 极小元, 极大元

• 最小, 最大元: 总是的故事: 集合X中若存在有一个元素z, 满足所有的元素和其的序偶<e,z>都落在偏序关系R中, 即e≤z总是对所有e都成立, 那么称z为最大元; 最小元同理;
• 极小, 极大元: 不存在的故事: 对元素a来说, 如果集合X中不存在元e, 使得a≤e, 那么我们称a为一个极大元; 极小元同理;
• 显然, 全序集中极大元和最大元是同一个; 对不是全序的偏序来说, 没有最大元, 最小元, 因为X中存在着a,b无论如何无法组成偏序, 所以假设真的有最小元, 会出现最小元和其中某元素无法建立任何偏序关系的问题, 导致矛盾;

上界, 下界, 最小上界(上确界), 最大上界(下确界)

• 集合X的子集A, 存在b∈X, 使得所有a∈A, 有a≤b, 那么b为A的一个上界; 在X的子集A的在所有上界的集合B中, 若有m满足了m和任意B中的e组成的序偶<m,e>都是偏序, 也就是m≤e总是成立, 那么说m是最小上界, 上确界.

良序

• 对X上的偏序关系R, 如果说X的每个非空子集都有最小元, 那么说R是一个良序关系, 简称良序, 那么<X,≤>被称为良序集, 良序集强调了良序关系集合(关系是一种集合)所在是X集合, 用来区别于<Y,≤>这种建立在Y集合上的良序关系;
  说人话: 偏序关系有最小元.