大学离散数学《集合与关系》课堂讲授课件

离散数学：集合与关系集合·关系·性质·结构2026课程导览01集合与运算建立集合语言与运算工具02关系与表示从序偶到二元关系的三种表示03性质与闭包五大性质判定与闭包运算04等价与偏序两大特殊关系与哈斯图05对比与演练对比辨析与题型实战01集合与运算集合是离散结构的起点，运算是推理的语言集合是对象的整体集合是由一些确定的、彼此不同的对象组成的整体，组成集合的对象称为元素。空集是任何集合的子集，∅⊆A

恒成立。定义属于a∈A，表示对象a是集合A的元素。不属于a∉A，表示对象a不是集合A的元素。两条判定标准确定性：每个对象要么属于、要么不属于。互异性：同一对象不重复出现。常用记号N

自然数集Z

整数集Q

有理数集R

实数集∅

空集两种表示法列举法：A={1,2,3}描述法：B={x|x∈N且x<6}子集与幂集子集是集合关系的基础，判定、相等与传递构成完整逻辑。幂集：A的全部子集构成P(A)；|A|=n时，|P(A)|=2ⁿ。子集与幂集·核心性质判定A的每个元素都属于B，则

A⊆B；A⊆B且A≠B时为真子集。相等互为子集——同时证

A⊆B

与

B⊆A。传递A⊆B且B⊆C⇒A⊆C。幂集示例A={1,2}⇒P(A)={∅,{1},{2},{1,2}}，共

2²=4

个易混辨析：∅∈{∅}成立，但∅≠{∅}——前者以空集为元素，后者是含空集的单元素集合集合的五种基本运算文氏图直觉：并集是两个圆覆盖的全部区域，交集是重叠区域，差集是去掉重叠后的月牙，对称差是两个圆不重叠的部分。运算结果仍是集合，这是后续用运算律化简集合表达式的依据。并集A∪B属于

A

或属于

B

的元素。交集A∩B同时属于

A

与

B

的元素。差集A−B属于

A

但不属于

B

的元素。绝对补~A在全集

E

中减去

A，即

~A=E−A。对称差A⊕B或属于

A

或属于

B，但不能同时属于二者，即

A⊕B=(A−B)∪(B−A)。运算律与德摩根律基础运算律3项交换律A∪B=B∪A，A∩B=B∩A结合律(A∪B)∪C=A∪(B∪C)分配律A∪(B∩C)=(A∪B)∩(A∪C)；A∩(B∪C)=(A∩B)∪(A∪C)交换律结合律分配律德摩根律2项补运算形式补运算把并变交、交变并：非(A∪B)=非A∩非B，非(A∩B)=非A∪非B差集形式由补形式推出：A−(B∪C)=(A−B)∩(A−C)，A−(B∩C)=(A−B)∪(A−C)考频最高配套律3项吸收律A∪(A∩B)=A零律A∩∅=∅同一律A∪∅=A配合德摩根律与德摩根律配合足以完成大部分集合恒等式证明。包含排斥原理60人阅读调查·文氏图计数三联(25)∩读者(11)∩国家地理(9)，重叠部分需排除核心公式两集合|A∪B|=|A|+|B|−|A∩B|三集合|A∪B∪C|=|A|+|B|+|C|−|A∩B|−|A∩C|−|B∩C|+|A∩B∩C|为什么不能直接相加重叠部分被重复计算，必须减去交叠、加回三重交集。实例·60人阅读调查25人读三联，26人读读者，26人读国家地理9人既读三联又读国家地理，11人既读三联又读读者画好文氏图，逐块看清计数关系，再代公式求解02关系与表示关系是元素之间的关联规则序偶与笛卡尔积序偶：次序即身份定义两个对象按固定次序组成整体记作

<x,y>相等条件<x,y>=<u,v>

当且仅当

x=u

且

y=v有序对笛卡尔积：全配对定义全配对公式A×B={<x,y>|x∈A且y∈B}，用A的元素做第一分量、B的元素做第二分量不满足交换律A≠B

时，一般

A×B≠B×A基数公式若

|A|=m、|B|=n，则

|A×B|=m×n全配对基数m×n几何直觉直观理解平面直角坐标系R×R

正是平面直角坐标系从离散到连续笛卡尔积把离散配对延展为连续平面实例:A={a,b}、B={0,1,2}A×B共2×3=6个有序对二元关系与平凡关系定义2条从A到BA×B的任意子集

R

称为从A到B的二元关系A上关系A=B

时称R为A上的二元关系记法xRy有序对<x,y>表示x与y满足该关系，记作

xRy计数1条关系个数的计算关系本身是集合，从A到B的二元关系共有

2的|A|·|B|次方

个三大平凡关系3项空关系∅不含任何有序对全域关系A×A包含所有有序对恒等关系Ia{<x,x>|x∈A}，只含每个元素与自身的环关系的三种表示法集合枚举法列举法·Roster直接列出全部有序对，把关系R中每一个元素对

都显式写在大括号内。示例R={<1,2>,<2,3>,<3,1>}适合证明与运算——枚举形式最贴近定义，便于逐条验证性质与做集合运算。关系矩阵邻接矩阵·0-1矩阵A有

m

个元素、B有

n

个元素，对应

m×n的0-1矩阵。第i行第j列取1，当且仅当相应有序对属于R；否则取0。示例MR=[[0,1,0],[0,0,1],[1,0,0]]适合计算机处理与闭包计算——矩阵运算规则清晰，便于程序化实现与传递闭包。关系图有向图·自环A、B元素画成结点，每个有序对<x,y>画一条从x指向y的有向边；结点指向自身画成自环。适合直观判断性质——图形一眼看出关系结构。判自反性：看环是否齐全——每个结点都有自环则满足。判对称性：看箭头是否成对出现——有x→y必有y→x。前域、值域与域三个集合，一次提取—从关系的有序对中，分离出前域、值域与域三种集合定义前域dom(R)所有有序对第一元素的集合值域ran(R)所有有序对第二元素的集合域FLD(R)前域与值域的并集，即

FLD(R)=dom(R)∪ran(R)生活实例对照同学关系中，前域与值域同为班上所有有同学的人。父子关系中，前域是全体父亲，值域是全体子女，两者不重合。意义前域与值域的分离是理解复合关系定义域变化、以及函数作为特殊关系的基础。03性质与闭包性质是关系的品格，闭包是关系的补完自反性与反自反性设R是集合A上的关系，按自环的有无区分第一对性质：自反性对任意

x∈A，都有

<x,x>∈R上面的内容提到了自环的有无反自反性对任意

x∈A，都有

<x,x>∉R下面的内容也提到了自环的有无自反性关系图表现：每个结点都必须有自环典型例子：实数集上的

≤、集合间的

⊆、恒等关系反自反性关系图表现：绝不能出现任何自环典型例子：实数集上的

<、父子关系自反与反自反不是非此即彼：部分元素有自环、部分没有时，两者都不满足；但非空集合上的关系不可能同时满足两者。VS对称性与反对称性口诀：对称关系看箭头，有去必有回。01两者并非非此即彼恒等关系：既对称又反对称——除自身外无跨元素关系某些关系：既不满足对称也不满足反对称理解这两种共存与互斥情形，是避免性质判定想当然的关键。对称性若<x,y>∈R时必有

<y,x>∈R关系图中不同结点间的边必成对出现同学关系、相等关系均满足反对称性定义若<x,y>∈R且

<y,x>∈R时必有x=y图视角不同结点间至多一条边实例实数集的

≤、集合的

⊆、整除关系均满足传递性关系也能“顺延”：若

x→y

且

y→z，则必有

x→z，这一性质就是传递性。“判定传递性：有前件就查后件——中转之后必须直达，穷举路径勿遗漏。”关系图判定路径存在

x→y→z

路径，则必须有

x直接到z

的边。

看图有中转就要有直达，这是图上判断传递性的核心原则。

满足实数集

≤集合

⊆祖先关系

不满足父子关系爷爷不是父亲的父亲判定要点传递性是蕴含式，前件假时自动为真；只有前真后假才破坏。易漏“路径中转”情形，应在图上穷举所有两段相连的三角形路径逐一核对。VS复合关系与逆关系复合关系R∘S定义<a,c>∈R∘S

当且仅当存在中间元素b，使

<a,b>∈S

且

<b,c>∈R。顺序易错第二个关系

S先作用，第一个关系

R后作用。例题A={1,2,3,4}，R={<2,4>,<3,3>,<4,2>}，S={<2,1>,<3,2>,<4,3>}，按定义逐对检查中间元素，得

R∘S={<2,3>,<3,2>,<4,1>}。注意复合运算不满足交换律，做题须按题目顺序核对中间元素。逆关系R⁻¹定义序偶分量对调：<a,b>∈R⁻¹

当且仅当

<b,a>∈R。矩阵对应逆关系的关系矩阵即原矩阵的转置矩阵。考点期末计算题经典考点，注意与复合顺序区分。闭包的定义与自反对称闭包闭包=最小扩充自反补镜子，对称补回声两个直接公式自反r(R)=R∪IA并入恒等关系，给无自环元素补自环对称s(R)=R∪R-1并入逆关系，把单向边补成双向边矩阵操作自反r(R):M⊕EM与单位矩阵E逻辑加对称s(R):M⊕M'M与转置M′

逻辑加传递闭包与Warshall算法公式定义t(R)=R¹∪R²∪R³∪…∪Rⁿ含

n

个元素的集合A上，把各次幂全部并起来，补全所有可达的间接路径。可达性并运算算法求解Warshall算法：三重循环迭代更新关系矩阵。时间复杂度为

O(n³)。手工易错矩阵迭代图解思路补边只要存在

a→b→c

这样的路径，就补上a→c的直达边。迭代逐轮迭代，直到不再产生新边为止。间接路径直达补全例题A={a,b,c,d}，R={<a,b>,<b,c>,<c,d>}先补自环得自反闭包再补反向边得对称闭包逐轮补齐

<a,c>、<a,d>、<b,d>

等路径得传递闭包运算性质闭包运算具有包含递增性、幂等性和单调性。在路径可达性判断中应用广泛。递增性幂等性单调性04等价与偏序等价揭示分类，偏序揭示层次等价关系的定义与实例将“相等”从精确相等推广到“在某方面相等”等价关系把“相等”从精确相等推广到“在某方面相等”——同余即一类等价。定义非空集合

A

上的关系

R

同时满足自反性、对称性、传递性，则称R为A上的等价关系。<x,y>∈R时记作

x~y。实例A={1,2,…,9}，R={<x,y>|x,y∈A且

x≡y(mod3)}，即除以3余数相同。三步验证：①

自反——任意x与自身余数相同；②

对称——x与y余数相同，则y与x也相同；③

传递——x~y且y~z，则x~z。等价类定义设

R

是非空集合

A

上的等价关系，对任意

x∈A，令[x]R={y|y∈A且xRy}称

[x]R

为x关于

R

的等价类，简记为[x]。等价关系非空集合A含义等价类就是所有与

x等价的元素构成的集合。把与

x

满足等价关系的所有成员收拢在一起，就得到一个等价类。代表元x

可以是类中任意一个成员，选谁都不影响这个类本身。直观理解按「是否等价」把元素分到同一个组，组里任选一个成员当代表即可。模3实例余1[1]=[4]=[7]={1,4,7}，除以3都余1余2[2]=[5]=[8]={2,5,8}，除以3都余2余0[3]=[6]=[9]={3,6,9}，除以3都余0整除关系把1–9分成

3

个等价类结构特征类内元素彼此等价，代表元可任取。不同等价类之间没有公共元素，互不相交。等价关系把复杂集合按等价标准装进若干互不相交的抽屉。分类视角每个抽屉就是一个等价类：先定标准，再分抽屉。等价类的性质与商集四条基本性质任意

x∈A，[x]是A的非空子集xRy

时，[x]=[y]x与y不等价时，[x]与[y]不相交所有等价类的并集恰好等于A等价类把A切成互不相交、合起来刚好铺满A

的块。商集quotientset以R的所有等价类为元素构成的集合，记作

A/R。模3关系：A/R={{1,4,7},{2,5,8},{3,6,9}}三种关系的商集形态关系商集形态类数恒等关系Ia每个元素单独成类9模3关系三个同余类3全域关系只有A本身1商集元素个数，反映等价标准把集合"切得多细"等价关系与划分的对应等价关系与集合的划分是一一对应的，这是等价关系最深刻的结论。理解这一对应，就抓住了等价关系“分类”的本质。等价关系⇄集合划分等价类划分

子集笛卡尔积并集，两类结构互相诱导一一对应双向对应：等价类⇄划分若R是A上的等价关系，则它的全体等价类构成A的一个划分任给A的一个划分π={S₁,S₂,…,Sₖ}，把每个子集内部的所有有序对并起来，即

R=∪(Sᵢ×Sᵢ)，就诱导出A上的一个等价关系示例对应让计数变得可算集合A={1,2,3,4,5,6,7}的划分{{1,2},{3,4,5},{6,7}}，对应等价关系含有的有序对个数为

2²+3²+2²=4+9+4=17

个类越大贡献的有序对越多，因为类内每两个元素（含自身）都两两等价17个有序对|=2²+3²+2²偏序关系的定义并非任意两个元素都能比较大小，刻画元素间的层次与先后。“偏”在何处？——2与3互不整除、互不可比，即元素间未必都能比较定义：集合A上的关系R满足自反性、反对称性、传递性，则称R为偏序关系，记作≤；<A,≤>称为偏序集整除关系验证（A={1,2,3,4,5,6}）自反任意

a

整除

a反对称a

整除

b

且

b

整除

a⇒a=b传递a

整除

b

且

b

整除

c⇒a

整除

c