离散数学--集合与关系

集合

集合差集：A-B属于A但不属于B

笛卡尔积：A×B={<x,y>x∈A,y∈B} 注：不符合交换律和结合律

关系

关系概念：R?A×B 表示R为AB上层关系，即AB笛卡尔积子集,关系的种类有2^A*B

	图	集合	关系矩阵
自反	每个点都有自环	xRx	包括单位矩阵
传递		xRy yRz则xRz	R*R=R
对称	任何两点之间都有两条通路	xRy则yRx	矩阵对称
反对称	任何两点之间最多一个弧	xRy yRx则y=x	对角线两侧不全为1

关系封闭:

自反闭包	r(R)=I∩R
对称闭包	s(R)=R∩R逆
传递闭包	t(R)=∪R^n

等价关系：自反、对称、传递

1. 等价类 [a]={x|x∈A，xRa}
2. 商集 A/R={[a] | a∈A} 商集是集合的集合

等价关系和划分：

笛卡尔积的划分可以确定唯一的等价关系，等价关系并集

偏序关系：自反、反对称、传递 <P,<= >

1. Hasse图 只画前后关系，不画自环，不画箭头
2. 全序关系 任何两个元素都可以比较
3. 最大元 极大元 上界(选择范围较大)