一.集合代数

设集合A，B

幂集：A的所有子集组成的集合，记作P(A);

对称差集(异或)：A⊕B=(A-B)∪(B-A)

绝对补集：~A=E-A；

广义并：∪A=A元素的元素相∪构成的集合

广义交：∩A=A元素的元素相∩构成的集合

例：N！末尾有多少个0：

N/5+N/25+N/125+N/625+....

设集合A，B

笛卡尔积：AxB=A的集合元素与B的集合元素排列组合（A的元素在前）

全域关系E：AxA；自反，对称，传递

恒等关系I：{|x∈A};  自反，对称，反对称，传递

空关系∅：反自反，对称，反对称，传递

设R，S为二元关系

domR为R的第一元素组成的集合（定义域）；

ranR为R的第二元素组成的集合（值域）；

R^-1为R的逆，即组成的集合

R ○ S为S对R的右复合（R对S的左复合）

例：R={,,}；S={}

则：R ○ S={,}

       S ○ R={,}

R(二元关系)在A(集合)上的限制:R↾A=R中第一元素是A集合中的元素的项组成的集合

A在R上的像：R[A]=ran(R↾A)=取上述集合的第二元素

例：R={,,,,,}

则：R↾{1,2}={,,,}

       ran(R↾{1,2})={2,3,5,8}

二元关系的性质在不同表现形式下的反映：集合表达式；关系图；关系矩阵A

R在A上是自反的：

含有所有；每个结点一定都有自己指向自己的环；主对角线全为1

R在A上是反自反的：

不含任意一个；每个结点一定都没有自己指向自己的环；主对角线全为0

R在A上是对称的：

在R中，所有都存在与之对应的；如果两个结点有一个有向边，一定还有反向边；矩阵是对称矩阵

R在A上是反对称的：

在R中，所有都没有对应的（除了）；如果两结点有一个有向边，则一定没有反向边；如果rij=1，则rji=0（i！=j）

R在A上是传递的：

在R中，若含有，，则一定要含有,才是传递的,否则不是.若只有一个元素，则该二元关系也是传递的；如果结点a->b,同时b->c，则一定有a->c;若A^2中rij=1，则A中rij=1

闭包：

自反闭包：r（R）=R∪R^0        (R^0=IA)

在关系图中就是把所有结点加上自己指向自己的有向边，一定满足自反

对称闭包：s（R）=R∪R^-1

在关系图中若是只有a->b的边，则加上b->a的边，一定满足对称

传递闭包：t（R）=R∪R^2∪R^3∪……        （最高次数与集合A的元素个数相等）

一定满足传递

R在A上是等价的：自反，对称，传递。若∈R，记作x~y

商集：所有等价集合构成的集合，记作A/R

例：A={2，3，4，5，6}，R为A除2的余数

于是有：{2，4，6}和{3，5}各为一个等价集合

这时商集就为A/R={{2，4，6}，{3，5}}

偏序关系：自反，反对称，传递

该关系是可以用来比较顺序（大小）的关系，记作≼

则有最大，最小元，极大，极小元

例：设≼是整除关系，A={2，3，4}

则2可以被4整除，记作2，4可比

2不能被3整除，记作2，3不可比

若R中的二元项,  x,y都是可比的，则称R为A上的全序（线序）关系

根据偏序关系画哈斯图