离散数学学习笔记

第三章集合与关系

集合的概念：把具有相同性质的不同对象的全体称为集合。

集合的特性：互异性，无序性
集合间的关系：包含，相等，
全集，空集
文氏图
幂集：有一个集合所有子集构成的集合

[图片上传失败...(image-8671c9-1604242121168)]

二项式展开证明

真子集个数为2^n-1个

在这里插入图片描述

第二题有2个元，即有2^2个子集

集合的运算

交，并，补，对称差

[图片上传失败...(image-b4d0d5-1604242121168)]

在这里插入图片描述

[图片上传失败...(image-7f7e5a-1604242121168)]

在这里插入图片描述
补集A-B，就是把A中属于B的部分挖去。
对称差，就是把A和B的交集挖去剩下的集合
在这里插入图片描述
tips
在这里插入图片描述

序偶

概念：具有固定次序的客体ab组成的有序序列，
次序不同序偶也是不同的
笛卡尔积，两个集合中的元素分别作为序偶的第一个元素和第二个元素A×B不满足交换律若A中元素个数为m，B中元素个数为n，则A×B中元素个数为mn

在这里插入图片描述

关系

序偶：表示两个客体之间的联系
关系：由序偶构成的集合

在这里插入图片描述

关系矩阵和关系图

在这里插入图片描述

用有向线段来表示关系

第三

关系的性质

在这里插入图片描述

复合关系和逆运算

A）复合关系
R 为 X 到 Y 的关系，S 为 Y 到 Z 的关系，R S 称为复合关系
∨ 代表逻辑加，0 ∨ 0 = 0，0 ∨ 1 = 1，1 ∨ 0 = 1，1 ∨ 1 = 1
∧ 代表逻辑乘，0 ∧ 0 = 0，0 ∧ 1 = 0，1 ∧ 0 = 0，1 ∧ 1 = 1
B）逆关系
R 为 X 到 Y 的二元关系，若将 R 每一序偶的元素顺序互换，得到逆关系 Rc

在这里插入图片描述

在这里述

关系的闭包运算

自反闭包，传递闭包，对称闭包

例如>=是>的自反闭包

划分和覆盖

定义：把集合A中的元素分成若干个叫做分块的子集，使得A中每个元素至少属于一个分块，那么这些分块的全体构成的集合叫做A的一个覆盖。如果A中的每一个元素只属于一个分块，那么这些分块的全体构成的集合叫做A的一个划分
例：A = { a, b, c }
覆盖：S1 = { {a, b}, {a, c} } 、S2 = { {a}, {a, b}, {b, c} }
划分：G = { {a, b}, {c} }
最小划分：G1 = { {a, b, c} } ，最大划分：G2 = { {a}, {b}, {c} }
判断依据：对于覆盖而言,一个元素可以属于两个分块,而对于划分,一个元素仅属于且必属于一个分块，划分一定是覆盖但覆盖未必是划分