四川大学计算机学院 离散数学(第14讲)
- 格式：ppt
- 大小：681.00 KB
- 文档页数：24
文档推荐
-
四川大学计算机学院多媒体基础量化页数:30
-
2009年四川大学计算机学院录取名单页数:12
-
四川大学计算机学院石兵代数系统页数:40
下载文档原格式
合集下载
离散数学(第14讲)二元关系
13
Discrete Mathematics 2）反之，在非空集合A上给定一个划分π，则可将A 分割成若干个划分块。 根据以下条件定义A上的二元关系R，即对任何元 素x,y∈A，如果x和y在同一划分块中，则xRy。显 然，R是A上的等价关系，称为由划分π所诱导的 等价关系，并且该等价关系的商集就等于π 。 结论 的划分是一一对应的。 集合A上的等价关系与集合crete Mathematics 在非空集合A上给定一个划分 在非空集合 上给定一个划分π={A1,A2,…,Am}， 上给定一个划分 ， 找出由π所唯一确定的 所唯一确定的A上的等价关系的方法如 找出由 所唯一确定的 上的等价关系的方法如 下： 把划分π的每一块 都拿出来， 把划分 的每一块Ai都拿出来，并且作其笛卡 的每一块 尔积A 尔积 i× Ai(i=1,2,..,m) ，然后求这些笛卡尔积的 并集，即为所求， 并集，即为所求，即
1
Discrete Mathematics 例 设A={1,2,3,4,5,6,7,8}， ， R={<x,y>|x,y∈A∧x =y(mod3)}，其中 =y(mod3) ∈ ∧ ，其中x 的含义是x和 分别除以 后的余数相等， 分别除以3后的余数相等 的含义是 和y分别除以 后的余数相等，即x-y可以 整除。 上的等价关系， 被3整除。不难验证 为A上的等价关系，它的关系 整除 不难验证R为 上的等价关系 图如下图所示： 下图所示 图如下图所示：
Discrete Mathematics
Discrete Mathematics 3、商集 、 为非空集合A上的等价关系， 定义 设R为非空集合 上的等价关系，以R的不相 为非空集合 上的等价关系 的不相 交的等价类为元素的集合叫做A在 下的商集， 下的商集 交的等价类为元素的集合叫做 在R下的商集，记 作A/R，即 ， A/R={[a]R |a∈A} ∈ 显然， 显然，在例1中，A在R下的商集是 中 在 下的商集是 A/R ={{1,4,7},{2,5,8},{3,6}}。 。
四川大学离散数学(冯伟森版)课后习题答案习题参考解答(图论部分)
习题十1. 设G 是一个(n ，m)简单图。
证明：，等号成立当且仅当G 是完全图。
证明：（1）先证结论：因为G 是简单图，所以G 的结点度上限 max(d(v)) ≤ n-1, G 图的总点度上限为 max(Σ(d(v)) ≤ n ﹒max(d(v)) ≤ n(n-1) 。
根据握手定理，G 图边的上限为 max(m) ≤ n(n-1)/2,所以。
（2） =〉G 是完全图 因为G 具有上限边数，假设有结点的点度小于n-1,那么G 的总度数就小于上限值，边数就小于上限值，与条件矛盾。
所以，G 的每个结点的点度都为n-1，G 为完全图。
G 是完全图 =〉 因为G 是完全图，所以每个结点的点度为n-1, 总度数为n(n-1)，根据握手定理，图G 的边数 。
■2. 设G 是一个（n ，n +1）的无向图，证明G 中存在顶点u ，d （u ）≥3。
证明：反证法，假设,则G 的总点度上限为max(Σ(d(u)) ≤2 n ，根据握手定理，图边的上限为max(m) ≤ 2n/2=n 。
与题设m = n+1，矛盾。
因此，G 中存在顶点u ，d （u ）≥3。
■3．确定下面的序列中哪些是图的序列，若是图的序列，画出一个对应的图来: （1）（3，2，0，1，5）； （2）（6，3，3，2，2） （3）（4，4，2，2，4）； （4）（7，6，8，3，9，5）解：除序列（1）不是图序列外，其余的都是图序列。
因为在（1）中，总和为奇数，不满足图总度数为偶数的握手定理。
可以按如下方法构造满足要求的图：序列中每个数字ai 对应一个点，如果序列数字是偶数，那么就在对应的点上画ai/2个环，如果序列是奇数，那么在对应的点上画(ai-1)/2个环。
最后，将奇数序列对应的点两两一组，添加连线即可。
下面以（2）为例说明：(6 , 3, 3, 2, 2 ) 对应图G 的点集合V= { v 1,v 2,v 3,v 4,v 5}每个结点对应的环数(6/2, (3-1)/2, (3-1)/2, 2/2,2/2) = (3,1,1,1,1)v 1v 5v 3v 4v 2将奇数3，3 对应的结点v 2,v 3一组，画一条连线其他序列可以类式作图，当然大家也可以画图其它不同的图形。
离散数学第14章课件PPT-高等教育出版社-屈婉玲-耿素云-张立昂主编(高等教学)
v的 后 继 元 集 D (v) {u | u V ( D) v, u E( D) u v}
v的 先 驱 元 集 D (v) {u | u V ( D) u, v E( D) u v}
v的邻 域
N D (v) D (v) D (v)
v的 闭 邻 域 N D (v) ND (v) {v}
d+(v)——v的入度 d(v)——v的出度 d(v)——v的度或度数 (3) (G), (G) (4) +(D), +(D), (D), (D), (D), (D) (5) 奇顶点度与偶度顶点
行业材料
8
握手定理
定理14.1 设G=<V,E>为任意无向图，V={v1,v2,…,vn}, |E|=m, 则
行业材料
15
实例
例2 画出K4的所有非同构的生成子图
行业材料
16
补图
定义14.9 设G=<V,E>为n阶无向简单图，以V为顶点集，以 所有使G成为完全图Kn的添加边组成的集合为边集的图， 称为G的补图，记作G . 若G G , 则称G是自补图. 例：见书P280 图14.6
行业材料
17
14.2 通路与回路
性质 具有自反性(vi vi)、传递性 具有自反性、对称性、传递性
vi 到vj 的短程线与距离 类似于无向图中，只需注意距离表示法的不同 (无向图中d(vi,vj)，有向图中d<vi,vj>) 及 d<vi,vj>无对称性
行业材料
26
有向图的连通性及分类
定义14.22 D=<V,E>为有向图 D弱连通(连通)——基图为无向连通图 D单向连通——vi,vjV，vivj 或 vjvi D强连通——vi,vjV，vivj
四川大学出版编的离散数学课后习题答案
2、不， 不， 能 习题 1.4
1、 (3) P ( R (Q P)) ~ P ( R (~ Q P)) (~ P R) (T ) ~ P R (~ P R (~ Q Q)) (~ P R ~ Q) (~ P R Q)
习题参考解答
习题 1.1 1、 （3）P：银行利率降低 Q：股价没有上升 P∧Q （5） P：他今天乘火车去了北京 Q：他随旅行团去了九寨沟
PQ
（7） P：不识庐山真面目 Q：身在此山中 Q→P，或 ～P→～Q （9） P：一个整数能被 6 整除 Q：一个整数能被 3 整除 R：一个整数能被 2 整除 T：一个整数的各位数字之和能被 3 整除 P→Q∧R 2、 （1）T （6）T 习题 1（3）
P ( Q R ) P ( Q R ) ( P Q ) ( P R ) ( P Q ) ( P R)
，Q→T （3）F （8）悖论 （4）T （5）F
（2）F （7）F
1.3
1
（4）
( P Q) (Q R) ( R P) (( P R) Q) ( R P) (( P R) ( R P)) (Q ( R P)) ( P R) ( P R) (Q R) (Q P) 右
2.(1) T 3.(1) F 4. 习题
D : 实数
(2) T
P ( x, y ) : y e x , Q( y ) : y 0
2.3
1.（1） xyPx Q y
8
xy~ Px Q y xy ~ Px yQ y
2.(1) P 0 P 1 P 2 R0 R1 Q2 (2) P 0 Q0 P 1 Q1 P 2 Q2 4.(1)
四川大学离散数学课后习题一解答或提示
习题一鮮答或提示1•⑴设P:他是本片的编剧，Q:他是本片的导決。
P A Q(2) 瑕P：级行利率吟低.Q:肢价上扬。
P→Q(3) 沒P:级行利率阵低.Q:股价上升。
〜(P→Q)(4) 设P：这个对象是占堀空问的∙Q:这个对象是有质量的R：这个对象是不飾变化的、S:这个对象称为场填。
P A Q A R→S(5) 沒P:他今天乘火车去了，Q：他今天随嵌行团去了九杀沟。
PVQ(6) 瑕P:小身体单萍，瑕Q:小圾少生病■没R:小头脑好使。
P A Q A R(7) 役P：这个人不枳庐丄真面Iu 设Q：这个人身A庐丄中。
QTR(8) 锻P：両个三角形柯似.没Q：两个三角形的对应角相普或者对应边成比例。
P<→Q(9) 沒P:-个整數能彼6整除，沒Q:这个整欽能彼2和3整除。
P→Q设R:-个整數能後3整徐，很S:这个整数的各住.数字之和也能彼3整除。
RTS2、(1)命題T(2) 命题T/F(3) 不是命题，因为真值无出确主。
⑷命题T(5)不是命题。
⑹命题T(7) 命题T/F(8) 不是命題，是悸论。
5、CU 证：〜((〜PAQJ V (〜PA〜Q丿)V CPAQJO (〜C〜PAQJ A〜(〜PA〜Q丿)V CPAQ丿o ( CPV 〜Q丿A CPVQJ ) V (PAQJO CPV (〜QVQJ ) V (PAQ)OPV CPAQ) OP(3) ⅛: Pf(QVR)o 〜PV(QVR)O 〜PVQV 〜P∖∕Ro C〜PVQJ V C〜PVR丿O(PfQ丿V (PfR丿6. 解：如系PVQoQ∖∕R∙不能靳走POR。
Q=T⅛, PVQ O QVR艳成立。
⅛r> PΛQ<=>QΛR,不能餅丈PoRO 因Q=F J⅛,PAQ O QAR怛成丈。
如系〜Po〜R, JK PORo8、把下刃冬丸用f寻价表承出来：(1) 豹CPAQJ 7〜TO C(PfQ) f (Pf Q丿V CPfP丿OCC(PfQf(PfQ)丿t C(PfQ)I(PtQ)J ) t (CPtPJ t (P↑?)) ⑶鮮：CP→ (QV〜R丿)A〜PO (〜PV (QV〜R丿)A〜Po ( CPtPJ V ΓQV CRtRJ )丿A (PtPJ ；O((PfP丿V ( CQ↑QJ t (CRtR) ↑ (^↑R) ) ) ) A CPtPJo ( ( CPtPJ t CP↑P> JtCC (QtQJ t ( (Rf R丿↑ CRtR) ) ) ↑(CQtQ) t ( (RfR丿t CRfR丿))))^ CPtP)OCL CPtPJ t CPtP) JtCr CQtQJ t ( CRtRJ t CRfR丿))↑ (ΓQtQJ ↑ ( CR↑RJ t CRfR丿))))↑(PW JtCCr CPtPJ ↑ (PfP丿) t (((Q↑Q) ↑ CCRtR丿t fR↑RJ ) ) ↑( CQtQJ t CfRfR丿t CRtRJJ))J t CPtP))9. ⅛E: ∙.∙ PVQ<=>---------- P VQ<=> (r~P∕ →QPAQ<≡>~ (〜PV〜Q丿O〜CPf〜Q丿而｛〜，V,八｝是功能克备.°.｛〜，f｝是功能完务集，〜，一►不能JL相表示，故｛〜・f｝是最小功能克备為。
四川大学离散数学第一章
பைடு நூலகம்
1.7 命题逻辑的推理方法
例25 应用题：证明以下推理是正确的。 如果小张和小王去看电影，则小李也去看电影。 小赵不去看电影或小张去看电影。 小王去看电影。 所以，当小赵去看电影时，小李也去。 解：设P：小张去看电影。Q：小王去看电影。 R：小李去看电影。S：小赵去看电影。 前提：P∧Q→R，¬S∨P，Q 结论：S→R
理解为：公式集合G中前提和由某些前提得到的中间结论 结论B
1.7 命题逻辑的推理方法
我们有下述结论： 公式B是公式集合G＝{A1,A2,…,An}的逻辑结果 当且仅当A1∧A2∧…∧An→B为永真公式。
1.7 命题逻辑的推理方法
定义说明：
(1) 若A1∧A2∧… ∧AnB，则A1∧A2∧… ∧An从推 出B，这样的推理是正确的。但是，推理正确不等于结论为 真（正确，真实），结论的真假还取决于前提 A1∧A2∧… ∧An 的真假，前提为真时，结论 B 为真；前提为假时， B可 能真也可能假，这就是定义中说 B 是 A1∧A2∧… ∧An 的有 效结论而不是说正确结论的原因。
⑤ 如AB，AC， iff AB∧C
【证明】“” 由 AB 且 AC 得到AB和AC都是永真式，于是 （AB）∧（AC）也是永真式；但是， （AB）∧（AC） （～A∨B）∧(～A∨C) ～A∨(B∧C)A→(B∧C)， 所以A(B∧C)是永真式，即AB∧C。 “”从证明过程看，性质5反过来也对，即由 AB∧C可以得到AB 且 AC 。
1.7 命题逻辑的推理方法
直接证明法 A1∧A2∧… ∧An B形式命题，从前提出发，利 用已知的基本等价式和蕴涵式构造中间命题，直至导出 最后结论。
1.7 命题逻辑的推理方法
例22 求证S∨R是前提{P∨Q，P→R，Q→S}的有效结论。(构 造性二难推论) 证：步骤 ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ 公式 P∨Q ～P→Q Q→S ～P→S ～S→P P→R ～S→R S∨R 依据（注释） P T ①，E1，E2 P T ②, ③,I9 T ④，E23 P T ⑤，⑥，I9 T ⑦，E2，E1
1.7 命题逻辑的推理方法
例25 应用题：证明以下推理是正确的。 如果小张和小王去看电影，则小李也去看电影。 小赵不去看电影或小张去看电影。 小王去看电影。 所以，当小赵去看电影时，小李也去。 解：设P：小张去看电影。Q：小王去看电影。 R：小李去看电影。S：小赵去看电影。 前提：P∧Q→R，¬S∨P，Q 结论：S→R
理解为：公式集合G中前提和由某些前提得到的中间结论 结论B
1.7 命题逻辑的推理方法
我们有下述结论： 公式B是公式集合G＝{A1,A2,…,An}的逻辑结果 当且仅当A1∧A2∧…∧An→B为永真公式。
1.7 命题逻辑的推理方法
定义说明：
(1) 若A1∧A2∧… ∧AnB，则A1∧A2∧… ∧An从推 出B，这样的推理是正确的。但是，推理正确不等于结论为 真（正确，真实），结论的真假还取决于前提 A1∧A2∧… ∧An 的真假，前提为真时，结论 B 为真；前提为假时， B可 能真也可能假，这就是定义中说 B 是 A1∧A2∧… ∧An 的有 效结论而不是说正确结论的原因。
⑤ 如AB，AC， iff AB∧C
【证明】“” 由 AB 且 AC 得到AB和AC都是永真式，于是 （AB）∧（AC）也是永真式；但是， （AB）∧（AC） （～A∨B）∧(～A∨C) ～A∨(B∧C)A→(B∧C)， 所以A(B∧C)是永真式，即AB∧C。 “”从证明过程看，性质5反过来也对，即由 AB∧C可以得到AB 且 AC 。
1.7 命题逻辑的推理方法
直接证明法 A1∧A2∧… ∧An B形式命题，从前提出发，利 用已知的基本等价式和蕴涵式构造中间命题，直至导出 最后结论。
1.7 命题逻辑的推理方法
例22 求证S∨R是前提{P∨Q，P→R，Q→S}的有效结论。(构 造性二难推论) 证：步骤 ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ 公式 P∨Q ～P→Q Q→S ～P→S ～S→P P→R ～S→R S∨R 依据（注释） P T ①，E1，E2 P T ②, ③,I9 T ④，E23 P T ⑤，⑥，I9 T ⑦，E2，E1
计算机科技专业《离散数学》教学大纲
《离散数学》教学大纲安徽大学计算机科学与技术学院二OO六年六月前言《离散数学》课程是计算机科学与技术专业高等教育的专业基础课程。
《离散数学》是现代数学的一个重要分支，是学习计算机科学与技术专业理论必不可少的数学工具。
本课程主要研究离散对象的结构及相互关系，对提高学生的抽象思维与逻辑推理能力有重要作用。
设置本课程的目的是：培养学生的数学思维能力，使学生得到良好的数学训练，提高学生的抽象思维和逻辑推理能力，并使学生掌握处理离散结构所必须的描述工具和方法，为其从事计算机的应用提供坚实的理论基础。
学习本课程的要求是：通过本课程的学习，学生应正确理解和熟练掌握基本概念、基本定理及其证明方法，提高运用基本理论分析和解决实际问题的能力，为在后续专业课和实际工作中运用本课程的基本知识打下基础。
先修课程要求：高等数学。
本课程计划144学时，7学分，分两学期完成，分别称为离散数学（上）和离散数学（下）。
离散数学（上）计划72学时，3.5学分；离散数学（下）计划72学时，3.5学分。
选用教材：《离散数学》，方世昌，西安电子科技大学出版社，2000出版。
教学手段：多媒体教学。
考核方法：考试。
教学进程安排表：第一章数理逻辑一、学习目的通过本章的学习，理解命题、联结词、命题公式、（主）析/合取范式、个体、谓词、量词、谓词公式、指派等概念；掌握公式真值表的构造及命题符号化方法、常用的基本等值式及其应用、常用的永真蕴涵式及其在逻辑推理中的应用、（主）析/合取范式的计算、命题演算和谓词演算的推理规则和证明方法。
第一章计划26学时。
二、课程内容1.1 命题（一）命题的概念。
（二）命题联结词及其真值表。
（三）命题符号化。
（四）命题变元和命题公式的概念。
1.2 重言式（一）指派、重言式、逻辑恒等式、永真蕴含式等基本概念。
（二）常见的逻辑恒等式和永真蕴含式。
（三）逻辑恒等式和永真蕴含式的基本性质。
（四）命题演算的基本规则：代入规则、替换规则。
四川大学离散数学课后习题一解答或提示
习题一解答或提示1. (1) 设P:他是本片的编剧，Q: 他是本片的导演。
P∧Q(2) 设P:银行利率降低，Q:股价上扬。
P→Q(3) 设P:银行利率降低，Q:股价上升。
～(P→Q)(4) 设P:这个对象是占据空间的,Q: 这个对象是有质量的,R: 这个对象是不断变化的,S: 这个对象称为物质。
P∧Q∧R→S(5) 设P:他今天乘火车去了，Q: 他今天随旅行团去了九寨沟。
P∇Q(6) 设P:小身体单薄，设Q:小极少生病, 设R:小头脑好使。
P∧Q∧R(7) 设P:这个人不识庐山真面目，设Q:这个人身在庐山中。
Q→R(8) 设P:两个三角形相似, 设Q:两个三角形的对应角相等或者对应边成比例。
P↔Q(9) 设P:一个整数能被6整除，设Q:这个整数能被2和3整除。
P→Q设R:一个整数能被3整除，设S:这个整数的各位数字之和也能被3整除。
R→S 2、(1) 命题T(2) 命题T/F(3) 不是命题，因为真值无法确定。
(4) 命题T(5) 不是命题。
(6) 命题T(7) 命题T/F(8) 不是命题，是悖论。
5、（1）证：～（（～P∧Q）∨（～P∧～Q））∨（P∧Q）⇔（～（～P∧Q）∧～（～P∧～Q））∨（P∧Q）⇔（（P∨～Q）∧（P∨Q））∨（P∧Q）⇔（P∨（～Q∨Q））∨（P∧Q）⇔ P∨（P∧Q）⇔P（3）证：P→(Q∨R)⇔～P∨(Q∨R)⇔～P∨Q∨～P∨R⇔（～P∨Q）∨（～P∨R）⇔ (P→Q）∨（P→R）6、解：如果P∨Q⇔Q∨R，不能断定P⇔R。
因为当Q=T时，P∨Q⇔Q∨R恒成立。
如果P∧Q⇔Q∧R，不能断定P⇔R。
因为当Q=F时，P∧Q⇔Q∧R恒成立。
如果～P⇔～R，则P⇔R。
8、把下列各式用↑等价表示出来：(1)解：（P∧Q）∨～P⇔（( P↑Q)↑( P↑Q)）∨（P↑P）⇔（（( P↑Q)↑( P↑Q)）↑（( P↑Q)↑( P↑Q)））↑（（P↑P）↑（P↑P））（3）解：（P→（Q∨～R））∧～P⇔（～P∨（Q∨～R））∧～P⇔（（P↑P）∨（Q∨（R↑R）））∧（P↑P）；⇔（（P↑P）∨（（Q↑Q）↑（（R↑R）↑（R↑R））））∧（P↑P）⇔（（（P↑P）↑（P↑P））↑（（（Q↑Q）↑（（R↑R）↑（R↑R）））↑（（Q↑Q）↑（（R↑R）↑（R↑R）））））∧（P↑P）⇔（（（（P↑P）↑（P↑P））↑（（（Q↑Q）↑（（R↑R）↑（R↑R）））↑（（Q↑Q）↑（（R↑R）↑（R↑R）））））↑（P↑P））↑（（（（P↑P）↑（P↑P））↑（（（Q↑Q）↑（（R↑R）↑（R↑R）））↑（（Q↑Q）↑（（R↑R）↑（R↑R）））））↑（P↑P））9、证：∵P∨Q⇔～～P∨Q⇔（～P）→QP∧Q⇔～（～P∨～Q）⇔～（P→～Q）而{～，∨，∧}是功能完备集，∴{～，→}是功能完备集，～，→不能互相表示，故{～，→}是最小功能完备集。
四川大学计算机学院 离散数学(第14讲)
I0
2013-7-5
计算机学院
19
2) 对任何的子集A1U，A2U,｛I0,I1,I2,I3}构成 了集合U的一个划分，其中，I0＝∩2 ， A1 A I1＝∩A2， A1 I2＝A1∩2 ，I3＝A1∩A2。 A
U A1 I2 I3 I1 I0
2013-7-5 计算机学院 20
A2
定理5.2
1若r是自反的则srtr也是自反的2若r是对称的则rrtr也是对称的3若r是传递的则rr也是传递的201375计算机学院4多重闭包1集合a上的关系的自反对称闭包定义为rsrrsr2集合a上的关系的自反传递闭包定义为rtrrtr3集合a上的关系的对称传递闭包定义为strstr同上我们还可定义srrtrrtsr
2013-7-5 计算机学院 9
这m个Z的子集具有的特点：在同一个子集中 的元素之间都有关系R，而不同子集的元素之间 无关系R。也就是说，通过等价关系，将集合分 成若干子集，使这些子集构成的集合就是Z的一 个划分。 事实上，对任意正整数m，Z的任意非空子集A ，关系R={<x,y>|(x,y∈A)∧(m|(x-y))}都是A上 的等价关系。
传递闭包和自反传递闭包，常用于形式语言与 程序设计中，在计算机文献中，常把关系R的传递 闭包t(R)记作R+，而自反传递闭包rt(R)记作R*。 显然有(R+)+=R+。
2013-7-5 计算机学院 5
§5.1
等价关系
我们知道，一个事物常常可以有很多种表 现形式，如1/2可以写成2/4，3/6，5/10等等， 一个命题公式也可以表示成很多不同然而等价 的形式。当我们以某种尺度来看待这些表面不 同而实质上具有相同特征的事物时，归类分析 的想法就产生了，这就是等价关系的核心思想。 定义5.1设R是定义在集合A上的关系，如果R是自 反的、对称的、传递的，则称此关系R为A上的 等价关系。
《离散数学专科期末复习提要
《离散数学》专科期末复习提要四川电大孙继荣2004年5月《离散数学》是四川电大数学与应用数学专业开设的课程。
使用的教材为中央电大出版的《离散数学》（刘叙华等编）和《离散数学学习指导书》（虞恩蔚等编）。
离散数学主要研究离散量结构及相互关系，使学生得到良好的数学训练，提高学生抽象思维和逻辑推理能力，为从事计算机的应用提供必要的描述工具和理论基础。
其先修课程为：高等数学、线性代数；后续课程为：数据结构、数据库、操作系统、计算机网络等。
课程的主要内容1、集合论部分（集合的基本概念和运算、关系及其性质）；2、数理逻辑部分（命题逻辑、谓词逻辑）；3、图论部分（图的基本概念、树及其性质）。
4、布尔代数（此部分对专科要求不高）学习建议离散数学是理论性较强的学科，学习离散数学的关键是对离散数学（集合论、数理逻辑和图论）有关基本概念的准确掌握，对基本原理及基本运算的运用，并要多做练习。
教学要求的层次各章教学要求的层次为了解、理解和掌握。
了解即能正确判别有关概念和方法；理解是能正确表达有关概念和方法的含义；掌握是在理解的基础上加以灵活应用。
一、各章复习要求与重点第一章集合[复习知识点]1、集合、元素、集合的表示方法、子集、空集、全集、集合的包含、相等、幂集2、集合的交、并、差、补等运算及其运算律（交换律、结合律、分配律、吸收律、De Morgan 律等），文氏（Venn）图3、序偶与迪卡尔积本章重点内容：集合的概念、集合的运算性质、集合恒等式的证明[复习要求]1、理解集合、元素、子集、空集、全集、集合的包含、相等、幂集等基本概念。
2、掌握集合的表示法和集合的交、并、差、补等基本运算。
3、掌握集合运算基本规律，证明集合等式的方法。
4、了解序偶与迪卡尔积的概念，掌握迪卡尔积的运算。
[疑难解析]1、集合的概念因为集合的概念学生在中学阶段已经学过，这里只多了一个幂集概念，重点对幂集加以掌握，一是掌握幂集的构成，一是掌握幂集元数为2n。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
8
13
等价类的性质
定理5.1 设R是非空集合A上的等价关系，有 下面结论成立： 1) 对任意xA，[x]R≠Φ；
x R
2)
xA
＝A；
3) 对 任 意 x,y∈A ， 或 者 [x]R=[y]R ， 或 者
[x]R∩[y]R＝Φ。
2013-7-5
计算机学院
14
证明：1）对任意x∈A，因为R是等价关系，所以R 是自反的，因此<x,x>∈R，即x∈[x]R，[x]R≠Φ。
2013-7-5 计算机学院 9
这m个Z的子集具有的特点：在同一个子集中 的元素之间都有关系R，而不同子集的元素之间 无关系R。也就是说，通过等价关系，将集合分 成若干子集，使这些子集构成的集合就是Z的一 个划分。 事实上，对任意正整数m，Z的任意非空子集A ，关系R={<x,y>|(x,y∈A)∧(m|(x-y))}都是A上 的等价关系。
2013-7-5
计算机学院
7
例5.1-2
设m为正整数，考虑整数集合Z上的关系如下： R={<x,y>|{x,y∈Z}∧(m|(x-y))} 证明R是一个等价关系。
证明 (1) 对任意xZ，有m|(x-x)，所以<x,x>R，即R 是自反的。 (2) 对任意x,yZ，若<x,y>R，即m|(x-y)，所以 m|(y-x)，所以，<y,x>R，即R是对称的。 (3) 对任意x,y,zZ，若<x,y>R且<y,z>R，有m|(x-y) 且m|(y-z)，所以由(x-z)=(x-y)+(y-z)得m|(x-z)， 所以，<x,z>R，即R是传递的。 由(1)、(2)、(3)知，R是Z上的等价关系。 ■
2013-7-5 计算机学院 21
证明
1）对任意x∈A，因为П(A)是A的一个划
分，所以存在一个划分块Ai∈П(A)，使得x∈Ai，
即x和x同属于П(A)的一个划分块Ai，故
<x,x>∈R，所以R是自反的。
2) 对任意x,y∈A，若<x,y>∈R，则x和y同属于
П(A)的一个划分块Ai，因此y和x同属于П(A)
2013-7-5
计算机学院
10
例5.1-3
我们常见的时钟上的时针重复关系即为 m=12，A={0,1,2,3,…,23}，此等价关系R的关系
图如下图所示，A被分成了12个子集{0,12}、
{1,13}、{2,14}、…、{11,23}。
0
12
1
13
2
14
3
… 15
11
23
2013-7-5
计算机学院
2013-7-5 计算机学院 4
例4-4.3
设A＝{1,2},R＝{<1,2>},则：
st(R)＝s(t(R))＝s({<1,2>}) ＝{<1,2>,<2,1>} ts(R)＝t(s(R))＝t({<1,2>,<2,1>}) ＝{<1,2>,<2,1>,<1,1>,<2,2>} 即：st(R)ts(R)
2013-7-5 计算机学院 3
多重闭包
1）集合A上的关系的自反对称闭包定义为rs(R) ＝r(s(R)) 2）集合A上的关系的自反传递闭包定义为rt(R) ＝r(t(R)) 3）集合A上的关系的对称传递闭包定义为st(R) ＝s(t(R)) 同上，我们还可定义sr(R),tr(R),ts(R),… 定理4.9 设R是集合A上的关系，则： 1)rs(R)＝sr(R) 2)rt(R)＝tr(R) 3)st(R)ts(R)
m
则称集合П(A)＝{A1,A2,A3,....,Am｝为集合A的
一个划分,而A1,A2,A3,...Am称为这个划分的块。
2013-7-5 计算机学院 18
例5.1-5
设对于全集U,考虑：
1) 对任何的子集AU,{I0,I1}构成了集合U的一个
划分，其中，I0＝ A 1＝A。 ,I
U A
I1
的一个划分块Ai ，故<y,x>∈R，所以R是对称
的。
2013-7-5 计算机学院 22
3) 对任意x,y,z∈A，若<x,y>∈R，<y,z>∈R， 则x和y同属于П(A)的一个划分块Ai，y和z同 属于П(A)的一个划分块Aj，因此y∈Ai∩Aj， 由于不同的划分块的交为空，所以Ai=Aj ，因 此 x 和 z 同 属 于 П(A) 的 一 个 划 分 块 Ai ， 即 <x,z>∈R，所以R是传递的。 综上，由1)、2)、3)知，R是A上的等价关系。
设П(A)＝{A1,A2,A3,....,Am}是非空集合A
的一个划分，则A上的关系
RП＝{<a,b>|(a,b∈A)∧(a,b同属П(A)的一个划分块)｝
=（a，b∈A）[（a，b）∈R （i）[1≤i≤m∧ a∈Ai ∧ b∈Ai]]
是A上的等价关系，称之为由П(A)所导出的等价关 系。 反之，每个A上的等价关系都能决定A的一个划分。
xA
2）因为对任意x∈A，[x]R A，所以 xR A。 对任意x∈A，因R是自反的，所以<x,x>∈R，即 x∈[x] 。所以x∈ xR ，即A xR 。 故 xR =A。
xA
R
xA
xA
2013-7-5
计算机学院
15
3) 对任意x,y∈A，分y∈[x]R和y[x]R进行讨论
11
等价类
定义5.2 称集合 [x]R＝{y|(y∈A)∧(<x,y>∈R)} 为x关于R的等价类,或称为由x生成的一个R 等价类。其中x称为[x]R的生成元(或叫代表元，或 典型元)。 在不会引起混淆时，简记为[x]。
2013-7-5 计算机学院 12
设R是集合A上的等价关系,对任意x∈A,
例5.1-4
传递闭包和自反传递闭包，常用于形式语言与 程序设计中，在计算机文献中，常把关系R的传递 闭包t(R)记作R+，而自反传递闭包rt(R)记作R*。 显然有(R+)+=R+。
2013-7-5 计算机学院 5
§5.1等价关系来自我们知道，一个事物常常可以有很多种表 现形式，如1/2可以写成2/4，3/6，5/10等等， 一个命题公式也可以表示成很多不同然而等价 的形式。当我们以某种尺度来看待这些表面不 同而实质上具有相同特征的事物时，归类分析 的想法就产生了，这就是等价关系的核心思想。 定义5.1设R是定义在集合A上的关系，如果R是自 反的、对称的、传递的，则称此关系R为A上的 等价关系。
2013-7-5 计算机学院 8
以m为模的同余关系
上述R称为Z上以m为模的同余关系，一般记xRy为 x＝y(mod m),称为同余式。 如用resm(x)表示x除以m的余数， 即 x=km+ resm(x) 则 x＝y(mod m) resm(x)＝resm(y)。 注意：x、y关于m1同余，但x、y关于m2不同余。 此时，R将Z分成了如下m个子集： {…,-3m,-2m,-m,0,m,2m,3m,…} {…,-3m+1,-2m+1,-m+1,1,m+1,2m+1,3m+1,…} {…, -3m+2,-2m+2,-m+2,2,m+2,2m+2,3m+2,…} … {…,-2m-1,-m-1,-1,m-1,2m-1,3m-1,4m-1,…}
所以[x]R∩[y]R＝Φ。■
2013-7-5 计算机学院 17
集合的划分
定义5.3设A是一个集合，A1,A2,A3...Am是A的任 何m个子集，如果A1,A2,A3...Am满足：
1) 对 一 切 的 i≠j(i,j ＝ 1,2,3,....,m) ， 都 有
Ai∩Aj＝Φ。
2)
i 1
Ai A
I0
2013-7-5
计算机学院
19
2) 对任何的子集A1U，A2U,｛I0,I1,I2,I3}构成 了集合U的一个划分，其中，I0＝∩2 ， A1 A I1＝∩A2， A1 I2＝A1∩2 ，I3＝A1∩A2。 A
U A1 I2 I3 I1 I0
2013-7-5 计算机学院 20
A2
定理5.2
冯伟森
Email：fws365@ 2013年7月5日星期五
主要内容
1、闭包运算的性质
2、等价关系 3、等价类及其性质
2013-7-5
计算机学院
2
闭包运算的性质
定理4.7 设R1，R2是集合A上的关系， 且R1R2，则：
1)r(R1)r(R2)
2)s(R1)s(R2) 3)t(R1)t(R2) 定理4.8 设R是集合A上的关系，则： 1) 若R是自反的，则s(R),t(R)也是自反的 2) 若R是对称的，则r(R),t(R)也是对称的 3) 若R是传递的，则r(R)也是传递的
2013-7-5 计算机学院 23
习题五
1、3、4、5、6
2013-7-5
计算机学院
24
设A＝{1,2,3,4,5,8}，考虑R是A上的以3为模 的同余关系，求其等价类。 解：从例5-1.2易知，该R是一个等价关系，为 此可求[x]R(x∈A)。 [1]R＝{1,4}＝[4]R； [2]R＝{2,5,8}＝[5]R＝[8]R； [3]R＝{3}。
1 2 3
5
4
2013-7-5 计算机学院
(1)若y∈[x]R，则<x,y>∈R。
（要证明[x]R＝[y]R ）
(a)对任意z∈[x]R，则有：<x,z>∈R，又