离散数学定义定理（上）(3)

定理3.3.2 设A，B，C，D，为非空集合，则A×B C×D的充要条件为A C，B D。

定义3..3.4 设A，B是任意两个集合，A×B的子集R称为从A到B的二元关系。当A=B是，称R为A上的二元关系。

从这个定义可以表明A到B的二元关系，也是序偶的集合。

故∈R，即称a与b有关系R，记作aRb。

若 R，则称a与b没有关系R，记作aRb。

若R=Φ称为空关系，若R=A×B称R为全关系，当A=B时，全关系EA={|x∈A∧y∈A}=A×A，A上的恒等关系IA={|x∈A}

定义3.3.5 设R为二元关系，由∈R的所有x所组成的集合domR，称为R的前域。domR={x|( y)(∈R)}

使∈R得所有y组成的集合ranR称为R的值域。 ranR={y|( x)(∈R)}

R的前域和值域一起称为R的域，记作FLDR,即：FLDR=domR∪ranR。

定理3.3.3 若Z和S是从集合X到Y的两个关系，则Z，S的交，并，差，补仍是X到Y的关系。

定义3.4.1 设R是集合X上的二元关系，

（1）如果对任意x∈X，必有xRx，则称关系R在X上是自反的。

（2）如果对任意x∈X，必有xRx，则称关系R在X上是反自反的。

（3）如果对任意x，y∈X，若xRy必有yRx，则称关系R在X上是对称的。

（4）如果对任意x，y∈X，若xRy且yRx必有x=y，则称R是反对称的。也可叙述为：若xRy，且x<>Y，必有xRy。

（5）如果对任意x，y，z∈X，xRy且yRz必有xRz，则称关系R在X上是传递的。

定义3.5.1 设R是从X到Y的二元关系，如将R中每一序偶的元素顺序互换，所得到的集合称为R的逆关系，记作R-1（或Rc）

即：R-1={|∈R}

定义3.5.2 设R为A到B的关系，S为从B到C的关系，则R○S称为R和S的复合关系表示为：

R○S={|x∈A∧z∈C∧( y)(y∈B∧∈R∧∈S)}，R○S称为关系的合成运算。(复合运算不满足交换律)

定理3.5.2 设A={a1，a2，…，am}，B={b1，b2，……，bn}，C={c1，c2，……，cr}

从A到B的关系R1关系矩阵MR1=（xij）是m×n阶矩阵。从B到C的关系R2的关系矩阵MR2=(yij)是n×r阶矩阵，那么从A到C的关系矩阵：

MR1○R2=(zij)是m×r阶矩阵，

其中 ，i=1，2，……，m， j=1，2，……，r。

定义3.5.3 设R是A上二元关系，如果有另一个关系R’，满足：

（1）R’是自反的（对称的，可传递的）；

（2）R’ R；

（3）对于任何自反的（对称的，可传递的）关系R”，如果有R” R，就有R” R’，则称关系R’为R的自反（对称，传递）闭包，记作r(R)(s(R)，t(R))。

定理3.5.3 设R为非空有穷集合A上的二元关系。

（1）r(R)=R∪IA；（2）s(R)=R∪R-1；（2）t(R)=R∪R2∪……∪Rn，其中n是集合A中元素的数目。

定义3.6.1 给定集合A上的关系ρ，若ρ是自反的，对称的，则称ρ是Ａ上的相容关系。

定义3.6.2 若把一个集合A分成若干叫做分块的非空子集，使得A中每个元素，至少属于一个分块，那么这些分块的全体构成的集合叫做Ａ的覆盖。

定义3.6.1 给定集合A的覆盖，S=｛S1,S2,……Sn｝，由它确定的关系：ρ=S1×S1∪S2×S2∪……∪Sn×Sn是相容的。

定义3.7.1 设R为定义在集合A上的一个关系，若R是自反的，对称的和传递的，则R称为等价关系。

定义3.7.2 设给定非空集合A，若有集合S=｛S1,S2,……Sm｝，其中Si A，Si (i=1,2,…，m)，且Si∩Sj= (i j)，同时有 ，称S是A的划分。

定义3.7.3 设R为集合Ａ上的等价关系，对任何a∈A，集合[a]R={x|x∈A,aRx}称为元素a形成的等价类。简记[a]或 。

定理3.7.1 设给定非空集合A上等价关系R，对于：a，b∈A有aRb iff[a]R=[b]R。

定义3.7.4 集合A上的等价关系R，其等价类集合｛[a]R|a∈A｝称为A关于R的商集记作A/R。

定理3.7.2 集合A的等价关系R，确定了Ａ的一个划分，该划分就是商集Ａ/R。

定理3.7.3 集合A的一个划分确定A的元素间的一个等价关系。

设集合A有一个划分S=｛S1,S2,……Sm｝，现定义一个关系R，当aRb，当且仅当a，b在同一分块中，这样：

（1）a与a在同一分块中，故必有aRa，即R是自反的。

（2）若a，b在同一分块中，则b，a也在同一分块，即aRb=>bRa，故R是对称的。

（3）若a与b在同一分块中，b与c在同一分块中，因为Si∩Sj= (i j)，即b属于且属于一个分块，故a与c必在同一个分块中，故有：aRb∧bRc=>aRc，即R是传递的。

定义3.8.1 设Ａ是一个集合，如果Ａ上的关系Ｒ满足自反性，反对称性，以及传递性，则称Ｒ是A上的一个偏序关系，并记作“≤”，序偶称作偏序关系。

定义3.8.2 设集合A上有二元关系，R若是反自反和传递的，称R为A上的拟序关系。并把称为拟序集，或记作。

定理3.8.1 集合A上二元关系是拟序的，则R必为反对称的。

定义3.8.3 集合A上二元关系是拟序集，对于任意x，y∈A，如果x≤y或者y≤x成立，称x和y可比。

定义3.8.4 在偏序集中，如果想x，y∈A，x≤y，且x y，且没有其他元素，z满足x≤z，z≤y，则称元素y盖住元素x。

记COVA{|x，y∈A；y盖住x}

(设R是非空集合A上的偏序集，a，b是A中两个不同元素，如果∈R，且在A中没有其他元素c，使得∈R和∈R，称元素b盖住元素a。)

定义3.8.5 设≤是集合A上的二元关系，如果对于A中任意两个元素a，b∈A，必有a≤b或b≤a，则称≤是A上的全序关系（或称线序关系）。若≤是A上的全序关系，称是全序集。

定义 3.8.6 设是一个偏序关系，钱B是Ａ的子集，对于Ｂ中的一个元素b，如果B中没有任何元素x，满足b x，且b≤x称b为B的极大元。同理对于b∈B，如果B中没有任何元素x，满足b x，且x≤b，则称b为B的极小元。

定义3.8.7 令是一个偏序集，B A，若有某个元素b∈B，对B中每一个元素，x有x≤b，称b为的最大元，同理，若有某个元素b∈B，对于每个x∈B有，b≤x，则称b为 的最小元。

定义3.8.8 设 为偏序集，对于B A，如果有a∈A，且对于B的任意元素x都满足x≤a，则称a为子集B的上界，同样对于B的任意元素x，都满足a≤x，则称a为B的下界。

定义3.8.9 设为偏序集，若有子集B A，若a为B的任一上界，若对B的所有上界y均有a≤y，则称a是B的最小上界（上确界），同样若b为B的任一下界，若对B的所有下界z，均有z小于等于b，则称b为B的最大下界（下确界）。