2025年【离散数学】集合与关系

大家好，我是讯享网，很高兴认识大家。

1. 集合

2. 序偶

3. 笛卡尔积

4. 关系

5. 复合关系

6. 逆关系

7. 关系的闭包运算

8. 集合的划分与覆盖

9. 等价关系

10. 相容关系

11. 序关系

附：系列文章

1. 集合

① 集合A和集合B相等的充分必要条件是这两个集合互为子集

② 集合的运算：∪(并)、∩(交)、—(差)、⊕(对称差)

对称差A⊕B=A∪B - A∩B

2. 序偶

① 符号：< , >

② 序偶可以看作具有两个元素（两个元素具有顺序）的集合。

3. 笛卡尔积

① 令A、B是任意两个集合，则有A×B={<x,y>|(x∈A)∧(y∈B)}

例：A={1,2} B={a,b,c} 则A×B={<1,a>,<1,b>,<1,c>,<2,a>,<2,b>,<2,c>}

② 若C≠∅，则A⊆B⇔(A×C⊆B×C)⇔(C×A⊆C×B)

③ A×B⊆C×D⇔A⊆C且B⊆D

注：A×B≠B×A（不遵循交换律） A×B×C≠A×(B×C)（不遵循结合律）

4. 关系

① 关系是序偶的集合，关系R中任一序偶<x,y>可记作<x,y>∈R 或 xRy

② domR（定义域）是关系R中所有序偶的x的集合，ranR（值域）是关系R中所有序偶的y的集合

③ 恒等关系：Ix={<x,x>|x∈X}

④ 关系的性质：

自反性⇔(∀x)(x∈X→xRx)

对称性⇔(∀x)(∀y)(x∈X∧y∈X∧xRy→yRx)

传递性⇔(∀x)(∀y)(∀z)(x∈X∧y∈X∧z∈X∧xRy∧yRz→∧xRz)

反自反性⇔(∀x)(x∈X→<x,x>∉R)

反对称性⇔(∀x)(∀y)(x∈X∧y∈X∧xRy∧yRx→x=y)

讯享网

注：可能存在某种关系既是对称的，又是反对称的

5. 复合关系

① 设R为X到Y的关系，S为Y到Z的关系，则R◦S称为R和S的复合关系

② R◦S={<x,z>|x∈X∧z∈Z∧(∃y)(y∈Y∧<x,y>∈R∧<y,z>∈S)}

6. 逆关系

① 将R中每一序偶的元素顺序互换，所得到的集合称为R的逆关系

② A×B的逆关系为B×A

③ R◦S的的逆关系为S逆◦R逆

④ R是对称的⇔R=R逆

⑤ R是反对称的⇔R∩R逆⊆Ix

7. 关系的闭包运算

① 设R是X上的二元关系，则有：

R是自反的⇔r(R)=R

R是对称的⇔s(R)=R

R是传递的⇔t(R)=R

② 求关系的闭包

r(R)=R∪Ix

s(R)=R∪R逆

t(R)=R+

8. 集合的划分与覆盖

① 通过一个例子来区分划分与覆盖

例如：A={a,b,c}

S={ {a,b},{b,c}} Q={ {a},{a,b},{a,c}} D={ {a},{b,c}} G={ {a,b,c}} F={ {a},{a,c}}

S，Q是A的覆盖，D，G是A的划分，F既不是覆盖也不是划分

② 如果是个划分，那么一定是覆盖

9. 等价关系

① 自反+对称+传递

② 集合A上的等价关系R决定了A的一个划分，该划分就是商集A/R

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

10. 相容关系

① 自反+对称

② 等价一定相容

③ 集合A的任意一个覆盖可以确定A的一个相容关系

④ 最大相容类：找最大的完全多边形

⑤ 完全覆盖：最大相容类的覆盖

11. 序关系

① 自反+反对称+传递

③ 哈斯图：去自环→取消所有由于传递性出现的边→箭头全向上

附：系列文章

概念

序号	文章目录	直达链接
1	命题逻辑	https://want595.blog.csdn.net/article/details/
2	谓词逻辑	https://want595.blog.csdn.net/article/details/
3	集合与关系	https://want595.blog.csdn.net/article/details/
4	代数结构	https://want595.blog.csdn.net/article/details/

测试

序号	文章目录	直达链接
测试一	命题逻辑	https://want595.blog.csdn.net/article/details/
测试二	谓词逻辑	https://want595.blog.csdn.net/article/details/
测试三	集合与关系	https://want595.blog.csdn.net/article/details/
期中测试	综合	https://want595.blog.csdn.net/article/details/
测试四	代数系统	https://want595.blog.csdn.net/article/details/
测试五	图论	https://want595.blog.csdn.net/article/details/

2025年【离散数学】集合与关系

1. 集合

2. 序偶

3. 笛卡尔积

4. 关系

5. 复合关系

6. 逆关系

7. 关系的闭包运算

8. 集合的划分与覆盖

9. 等价关系

10. 相容关系

11. 序关系

附：系列文章

相关推荐