离散数学复习之集合与关系

关系"/>

离散数学复习之集合与关系

目录

鸽巢原理及包含容斥原理的应用

关系定义、性质及运算（特别关系闭包）

基础知识

有序对与笛卡尔积

二元关系

关系的运算（难点）

 1.关系的复合

 2.关系的性质

 3.等价关系

 4.偏序关系

---

鸽巢原理及包含容斥原理的应用

PS：如果一个人握了n-1次手，那么他就与所有人除他自己外握手，那么不会有人没有握手 

关系定义、性质及运算（特别关系闭包）

基础知识

 PS：集合子集个数为2的n次方个（真子集减1），另外不要与复合运算弄混 

                   交集运算               并集运算             差运算               补集运算              对称差

 PS：

Notice：

 

 

 PS：P（A），A的子集集合

 二式到三式只能证明必要性原因：x是A的子集或者是B的子集->x是A∪B的子集，反过来不能，因为x可能同时含有A和B中的元素

 有序对与笛卡尔积

 PS：笛卡尔积即把X前后集合用类似点（a，b）的形式连接起来

PS：遇笛卡尔积取<X，Y> 

         证明子集的方法！！！！！！！！！！！！！！

二元关系

 

 PS：R是A上的关系，即R含于A X A关系的运算（难点）

1.关系的复合

 PS：类似传递性

 PS：逻辑乘，异0同1；逻辑加，同0异1.（不要与线代弄混）

 PS：仅适用于代函数关系式的半抽象集合，R的y对应S的x，代入得复合式

 PS：先设<a,c>,在引入存在b，用复合关系的定义证明类似传递的存在

 PS：证明方法为数学归纳法，首先有n = 0是满足条件

再假设n时满足条件，证明n+1时也满足条件

另例：图中无向树相关证明中（2） =》 （3）

 2.关系的性质

 PS：根据定义证明，值得注意的是，取值均在集合I中 

 PS：P <=> Q，证明必要性：p->q,证明充分性：q->p. 

关系的闭包 

（2） 

 

 PS：证明相等，即证明互相包含

PS：

 3.等价关系

 PS：%3的余数只存在三个。

 

 

 

PS：证明必要性和充分性 

PS：根据条件结果进行划分

PS：其中② 中使用了（A○B）的逆 = B的逆 ○ A的逆

 4.偏序关系

 

PS：画法 ，先列出（x，y），找到y没有的值（除了自反外），标到底层，将这些关系划掉后重复步骤，依次标到2,3……n层，直到只剩自反或没有关系

 

 

 PS：如果子集含哈斯图边界，且存在不可比元（即不存在分支），相应的界不存在。

          如果集合首或尾不存在不可比元，那首或尾元也包含在界中（小于等于的含义）