离 散 数 学
期 末 总 复 习
复 习 时 注 意
准确掌握每个概念
灵活应用所学定理
注意解题思路清晰
证明问题时,先用反向思维 (从结
论入手 )分析问题,再按正向思维
写出证明过程,
全书知识网络,
图
论
篇
<{T,F},?,?,?,?,?>
<p(E),~,∩,∪,－,?>
格与布尔代数
半群,独异点,群,环,域
<P(A× A),~,∩,∪,－,?,?,c,r,s,t>
<YX,~,∩,∪,－,?,?,-1>
代数系统篇
n 元运算
命题逻辑
谓词逻辑
集合初步
二元关系
函 数
集合论篇
数理逻辑篇
总 复 习
复习重点 (注, 标有 *的内容,对网络学院学生不作要求 )
第一章 命题逻辑
1.联结词的定义 (含义及真值表定义 ).
2.会命题符号化,
3.永真式的证明,
4.永真蕴涵式的证明,记住并能熟练应用常用公式,
5.等价公式的证明,记住并能熟练应用常用公式,
6.会写命题公式的范式,*能应用范式解决问题,
7.熟练掌握命题逻辑三种推理方法,
第二章 谓词逻辑
1.准确掌握有关概念,
2.会命题符号化,(如 P60题 (2))
3.掌握常用的等价公式和永真蕴涵式,包括,
带量词的公式在论域内展开式,量词否定,量词辖域扩充,
量词分配公式,
4.会用等价公式求谓词公式的真值,(如 P66题 (3))
*5.会写前束范式
6.熟练掌握谓词逻辑推理,
第三章 集合论初步
1.集合的表示,幂集,全集,空集,
2.集合的三种关系 (包含,相等,真包含 )的定义及证明,
3.集合的五种运算及相关性质,
*4.应用包含排斥原理,
第四章 二元关系
1.关系的概念,表示方法,
2.二元关系的 性质的定义,熟练掌握性质的判断及证明,
3.掌握关系的复合,求逆及闭包运算 (计算方法及有关性质 )
4.掌握等价关系的判断,证明,求等价类和商集,
*4.掌握相容关系定义,简化图和简化矩阵,相容类,最大相
容类,完全覆盖,
5.偏序关系的判断,会画 Hasse图,会求一个子集的极小 (大 )
元,最小 (大 )元,上界与下界,最小上界及最大下界,
第六章 函数
1.函数的定义,
2.函数的类型,会判断,会证明,
3.会计算函数的复合 (左复合 ),求逆函数,知道有关性质,
*4.了解集合的特征函数,了解集合的基数,可数集合,
第六章 代数系统
1.掌握运算的定义,
2.熟练掌握二元运算的性质的判断及证明,
3.掌握代数系统的同构定义,会证明,了解同构性质的保持,
4.了解半群,独异点,*环和 *域的概念,
5.熟练掌握群,子群,交换群 (会证明 ),了解循环群,
*6,子群的陪集,Lagrange定理及其推论,(会应用 ).
*第七章 格与布尔代数
* 1.掌握格的定义,了解格的性质,
* 2.会判断格,分配格,有补格和布尔格,
* 3.重点掌握两个元素的布尔代数的性质 (10个 ).
* 4.会写两个元素的布尔表达式的范式,(实质是第一章的
主析取和主合取范式 ).
第八章 图论
1.掌握图的基本概念,(特别注意相似的概念 )
2.熟练掌握图中关于结点度数的定理, (会应用 )
3.无向图的连通性的判定,连通分支及连通分支数的概念,
4.有向图的可达性,强连通,单侧连通和弱连通的判定,求强
分图,单侧分图和弱分图,
5.会求图的矩阵,
6.会判定欧拉图和汉密尔顿图,
*7.会判定平面图,掌握欧拉公式,
*8.了解对偶图,
9.掌握树的基本定义,v和 e间的关系式,会画生成树,会求最
小生成树,根树的概念,完全 m叉树的公式,会画最优树,*会
设计前缀码,
总 复 习
复习重点
第一章 命题逻辑
1.联结词的定义 (含义及真值表定义 ).
2.会命题符号化,
3.永真式的证明,
4.永真蕴涵式的证明,记住并能熟练应用常用公式,
5.等价公式的证明,记住并能熟练应用常用公式,
6.会写命题公式的范式,*能应用范式解决问题,
7.熟练掌握命题逻辑三种推理方法,
第一章 命题逻辑
1.联结词
定义了六个逻辑联结词，分别是：
(1) 否定,?” (2) 合取,∧,
(3) 析取,∨, (4) 异或,”
(5) 蕴涵,?” (6) 等价,?”
要熟练掌握这五个联结词在自然语言中所表示的含义以
及它们的真值表的定义。
? ?,否定 表示“不”
? ∧,合取 表示,不但 …,而且,..”“并且”
? ∨,析取 表示,或者－可兼取的或”
?,异或 表示“或者－不可兼取的或”
? ?：蕴涵 表示“如果 …,则,..”
? ?,等价 表示“当且仅当”“充分且必要”
? 可以将这六个联结词看成六种,运算,。
?
?
联结词的定义 (包括真值表和含义 ).
特别要注意：
“或者”的二义性,即要区分给定的“或”是“可兼取的
或 ∨,还是“不可兼取的或,。
,?”的用法,它既表示“充分条件”也表示“必要条
件”,即要弄清哪个作为前件,哪个作为后件,
P Q P∧ Q P∨ Q P?Q P?Q P Q
F F F F T T F
F T F T T F T
T F F T F F T
T T T T T T F
?
?
2.会命题符号化,
例如 P:我有时间, Q:我上街, R:我在家,
表示 P是 Q的充分条件, 如果 p,则 Q,只要 P,就 Q,P?Q
表示 P是 Q的必要条件, 仅当 P,才 Q,只有 P,才 Q,Q?P
如果 P,则 Q;否则 R,(P?Q)?(?P?R)
3.永真式的证明,
方法 1.列真值表, (?R?(Q?R)??(P??Q))??P
方法 2.用公式的等价变换,化简成 T.
例如证明 (?R?(Q?R)??(P??Q))??P是永真式,
证,上式 ??(?R?(?Q?R)??(P??Q))??P(P?Q??P?Q)
?(R?(Q??R)?(P??Q))??P (公式的否定公式 )
?((R?(Q??R))?((P??Q)??P) (结合律 )
? ((R?Q)?(R??R))?((P??P)?(?Q??P) (分配律 )
?(R?Q)?(?Q??P) ?R?Q??Q??P?T (互补,同一律 )
4.永真蕴涵式的证明,记住常用的公式,
永真蕴涵式, A?B是永真式,则称
A永真蕴涵 B,(A?B)
方法 1.列真值表,
方法 2.假设前件真,推出后件真,
(即直接推理 )
方法 3.假设后件假,推出前件假,(即反证法 )
例证明 (P?(Q?R))?((P?Q)?(P?R))是永真蕴涵式,
证,假设后件 (P?Q)?(P?R)假,则 P?Q为 T,P?R为 F,于
是 P为 T,R为 F,进而又得 Q为 T,所以 Q?R为 F,所以前件
P?(Q?R)为 F,所以 (P?(Q?R))?((P?Q)?(P?R))为
永真式,
对于给定一个题,究竟是用哪种方法,原则上哪种都可以,
但是哪个方法简单,要根据具体题而定,
A B A ?B
F F T
F T T
T F F
T T T
5.等价公式的证明,记住常用的公式,
方法 1.列真值表,
方法 2.用公式的等价变换,
例如,证明 P?(Q?R)?(P∧ Q)?R
P?(Q?R)??P?(?Q?R) ? (?P??Q)?R
??(P?Q)∨ R?(P∧ Q)?R
注意,不论是证明永真蕴涵式,还是证明等价公式以及后边
的求公式的范式,命题逻辑推理,都应用 43页的公式。
必须记忆一些常用的公式 如,P43表中的
永真蕴涵式, I1,I3,I9,I10,I11,I12,I13,
等 价 公 式, E1 ~ E16,E18,E19,E20,E21,
6.命题公式的范式
1)析取范式,A1∨ A2∨,..∨ An (n≥1) Ai (i=1,2..n)是 合取式,
2)合取范式,A1∧ A2∧,..∧ An (n≥1) Ai (i=1,2..n)是 析取式,
3)析取范式与合取范式的写法,
4)小项及 小项的性质,
m3 m2 m1 m0
P Q P∧ Q P∧ ?Q ?P∧ Q ?P∧ ?Q
00 F F F F F T
01 F T F F T F
10 T F F T F F
11 T T T F F F
6)大项及其性质,
M0 M1 M2 M3
P Q P∨ Q P∨ ?Q ?P∨ Q ?P∨ ?Q
00 F F F T T T
01 F T T F T T
10 T F T T F T
11 T T T T T F
7)主析取范式, A1∨ A2∨,..∨ An (n≥1) Ai (i=1,2..n)小项,
8)主合取范式, A1∧ A2∧,..∧ An (n≥1) Ai (i=1,2..n)大项,
9).会写主析取范式和主合取范式,
求下面命题公式的范式,
A(P,Q,R)?(P∨ Q)?R
方法 1.列真值表,
主析取范式
A(P,Q,R)?(P∨ Q)?R
?(?P∧ ?Q∧ ?R )∨ (?P∧ ?Q∧ R )∨ (?P∧ Q∧ R)
∨ (P∧ ?Q∧ R )∨ (P∧ Q∧ R )
主合取范式
A(P,Q,R)?(P∨ Q)?R
?(P∨ ?Q∨ R )∧ (?P∨ Q∨ R )∧ (?P∨ ?Q∨ R)
P Q R (P∨ Q)?R
F F F T
F F T T
F T F F
F T T T
T F F F
T F T T
T T F F
T T T T
方法 2.用公式的等价变换,
主析取范式 ;A(P,Q,R)?(P∨ Q)?R
??(P∨ Q)∨ R ? (?P∧ ?Q)∨ R
? (?P∧ ?Q∧ (R∨ ?R))∨ ((P∨ ?P)∧ (Q∨ ?Q)∧ R)
? (?P∧ ?Q∧ R)∨ (?P∧ ?Q∧ ?R)∨ (P∧ Q∧ R)
∨ (P∧ ?Q∧ R)∨ (?P∧ Q∧ R)∨ (?P∧ ?Q∧ R)
?(?P∧ ?Q∧ ?R )∨ (?P∧ ?Q∧ R )∨ (?P∧ Q∧ R)
∨ (P∧ ?Q∧ R )∨ (P∧ Q∧ R )
主合取范式,A(P,Q,R)?(P∨ Q)?R
??(P∨ Q)∨ R ? (?P∧ ?Q)∨ R
? (? P∨ R )∧ (?Q∨ R)
? (? P∨ (Q∧ ?Q)∨ R )∧ ((P∧ ?P)∨ ?Q∨ R)
? (?P∨ Q∨ R )∧ (?P∨ ?Q∨ R)∧ (P∨ ?Q∨ R )
已知 A(P,Q,R)的主析取范式中含有如下小项,
m0,m3,m4,m5,m7求它的主合取范式,
解,A(P,Q,R)的主合取范式中含有大项,M1,M2,M6
A(P,Q,R)?(P∨ Q∨ ?R )∧ (P∨ ?Q∨ R)∧ (?P∨ ?Q∨ R)
* 范式的应用
如 P39习题 (7),(8),安排工作 (排课表 ),判断比赛名次,携带
工具箱,…
7.会用三种推理方法,进行逻辑推理,
会用三个推理规则,P,T,CP
例如,证明 ((A∧ B)?C)∧ ?D∧ (?C∨ D) ??A∨ ?B
1.直接推理,
⑴ ?D P
⑵ ?C∨ D P
⑶ ?C T ⑴⑵ I10 ?Q,(P∨ Q) ?P
⑷ (A∧ B)?C P
⑸ ?(A∧ B) T ⑶⑷ I12 ?Q,P?Q ??P
⑹ ?A∨ ?B T ⑸ E8 ?(P∧ Q)??P∨ ?Q
((A∧ B)?C)∧ ?D∧ (?C∨ D) ??A∨ ?B
2.条件论证,适用于结论是蕴涵式, ?A∨ ?B ? A??B
⑴ A P(附加前提 )
⑵ (A∧ B)?C P
⑶ A?(B?C) T⑵ E19
⑷ B?C T⑴⑶ I11
⑸ ?D P
⑹ ?C∨ D P
⑺ ?C T ⑸⑹ I10
⑻ ?B T ⑷⑺ I12
⑼ A??B CP
((A∧ B)?C)∧ ?D∧ (?C∨ D) ??A∨ ?B
3.反证法,
⑴ ?(?A∨ ?B) P(假设前提 )
⑵ A∧ B T⑴ E9
⑶ (A∧ B)?C P
⑷ C T ⑵ ⑸ I11
⑸ ?D P
⑹ ?C∨ D P
⑺ ?C T ⑻⑼ I10
⑻ C∧ ?C T ⑷ ⑺ I9
第二章 谓词逻辑
1.准确掌握有关概念,
2.会命题符号化,(如 P60题 (2))
3.掌握常用的等价公式和永真蕴涵式,包括,
带量词的公式在论域内展开式,量词否定,量词辖域扩充,
量词分配公式,
4.会用等价公式求谓词公式的真值,(如 P66题 (3))
*5.会写前束范式
6.熟练掌握谓词逻辑推理,
第二章 谓词逻辑
1.准确掌握有关概念,
客体,
客体变元,
谓词,
量词,
量词后的指导变元,
量词的辖域,
约束变元与自由变元,
论域,
全总个体域,
谓词公式 (WFF),
命题函数,
前束范式,
2.会命题符号化,(如 P60题 (2))
命题的符号表达式与论域有关。 当论域扩大时，需要
添加用来表示客体特性的谓词，称此谓词为 特性谓词 。
特性谓词往往就是给定命题中量词后边的那个名词。
如, 所有 自然数,..”,, 有些 大学生,..”。
? 如何添加特性谓词，这是个十分重要的问题, 这与前
边的量词有关 。
如果 前边是 全称量词, 特性谓词后边是 蕴含联结词
,→, ；
如果 前边是 存在量词, 特性谓词后边是 合取联结词
,∧, 。
另外有些命 题 里有的客体在句中没有明确的量 词,而在
写它的符号表达式 时,,必 须 把 隐 含的量 词 明确的写出来,
例如 ⑴金子闪光,但闪光的不一定都是金子,
设, G(x):x是金子, F(x):x闪光,
?x(G(x)?F(x))???x(F(x)?G(x))
?x(G(x)?F(x))??x(F(x)??G(x))
⑵ 没有大学生不懂外语,
S(x):x是大学生, F(x):x外语, K(x,y):x懂得 y.
??x(S(x)??y(F(y)??K(x,y)))
?x(S(x)??y(F(y)?K(x,y)))
⑶ 有些液体可以溶解所有固体,
F(x):x是液体,S(x):x是固体,D(x,y):x可溶解 y.
?x(F(x)??y(S(y)?D(x,y)))
⑷ 每个大学生都爱好一些文体活动。
S(x):x是大学生,L(x,y):x爱好 y,C(x):x是文娱活动，
P(x):x是体育活动,) ?x(S(x)??y((C(y)∨ P(y))?L(x,y)))
3.掌握常用的等价公式和永真蕴涵式,包括,
带量词的公式在论域内展开式,量词否定,量词辖域扩充,
量词分配公式,
设论域为 {a1,a2,....,an}，则
1),?xA(x)?A(a1)∧A(a 2)∧......∧A(a n)
2),?xB(x)?B(a1)∨B(a 2)∨......∨B(a n)
1),??xA(x)??x?A(x)
2),??xA(x)??x?A(x)
1),?xA(x)∨B ??x(A(x)∨B)
2),?xA(x)∧B ??x(A(x)∧B)
3),?xA(x)∨B ??x(A(x)∨B)
4),?xA(x)∧B ??x(Ａ (x)∧B)
5),B→ ?xA(x)??x(B→A(x))
6),B→ ?xA(x)??x(B→A(x))
7),?xA(x)→B ??x(A(x)→B)
8),?xA(x)→B ??x(A(x)→B)
1),?x(A(x)∨B(x)) ??xA(x)∨ ?xB(x)
2),?x(A(x)∧B(x)) ??xA(x)∧ ?xB(x)
3),?x(A(x)∧B(x)) ??xA(x)∧ ?xB(x)
4),?xA(x)∨ ?xB(x)??x(A(x)∨B(x))
4.会用等价公式求谓词公式的真值,(如 P66题 (3))
例 设论域为 {1,2},A(x,y):x+y=xy,求 ??x?yA(x,y)的真值,
??x?yA(x,y)??x?y?A(x,y)
??y?A(1,y)??y?A(2,y)
?(?A(1,1)??A(1,2))?(?A(2,1)??A(2,2))
?(T?T)?(T?F) ?T
*5.将下面谓词公式写成前束范式
(?xF(x,y)??yG(y)??xH(x,y)
??(??xF(x,y)??yG(y)??xH(x,y) (去 ?)
??xF(x,y) ???yG(y) ??xH(x,y) (摩根 )
??xF(x,y) ??y?G(y) ??xH(x,y) (量词否定 )
??xF(x,z) ??y?G(y) ??tH(t,z) (变元换名 )
??x?y?t((F(x,z) ??G(y) ?H(t,z)) (辖域扩充 )
6.熟练掌握谓词逻辑推理,
1).注意使用 ES,US,EG,UG的限制条件,特别是 ES,UG
2).对于同一个客体变元，既有带 ?也有带 ?的前提，去量
词时,应先去 ?后去 ?，这样 才可以特指同一个客体 c.
3).去量词时，该量词必须是公式的最左边的量词，且此
量词的前边 无任何符号,它的辖域作用到公式末尾。
下面的作法是错误的,正确作法,
⑴ ?xP(x)→ ?xQ(x) P ⑴ ?xP(x)→ ?xQ(x) P
⑵ P(c)→ ?xQ(x) US⑴ ⑵ ??xP(x)∨ ?xQ(x) T ⑴ E
或⑵ ?xP(x)→ Q(c)ES⑴ ⑶ ?x?P(x)∨ ?xQ(x) T ⑵ E
实际上 ?x的辖域扩充后 ⑷ ?x(?P(x)∨ Q(x)) T⑶ E
量词改成为 ?x ⑸ ?P(c)∨ Q(c) ES⑷
⑹ P(c)→ Q(c) T⑸ E
下面的作法是错误的,正确作法,
⑴ ??xP(x) P ⑴ ??xP(x) P
⑵ ?P(c) US⑴ ⑵ ?x?P(x) T⑴ E
实际上⑴ 中量词不是 ⑶ ?P(c) ES⑵
?x而是 ?x
⑴ ?x?yP(x,y) P ⑴ ?x?yP(x,y) P
⑵ ?xP(x,c) ES⑴ ⑵ ?yP(c,y) US⑴
令 P(x,y):y是 x的 生母，
显然 ⑵是个假命题
4).添加量词时，也要加在公式的最左边,(即新加的量词
前也无任何符号 ！！ )且其辖域作用到公式的末尾。
例如下面作法是错误的, ⑴ ?xP(x)→ Q(c) P
⑵ ?xP(x)→ ?yQ(y) EG⑴
例如,证明下面推理的有效性,
证明,⑴ ?x(A(x)∧ ?D(x)) P
⑵ A(a)∧ ?D(a)) ES ⑴
⑶ A(a) T ⑵ I
⑷ ?D(a)) T ⑵ I
⑸ ?x(A(x)→(B(x)→ ?C(x))) P
⑹ A(a)→(B(a)→ ?C(a)) US ⑸
⑺ B(a)→ ?C(a)) T ⑶⑹ I
⑻ ?x(A(x)→(C(x)∨D(x) )) P
⑼ A(a)→(C(a)∨D(a) )) US⑻
⑽ C(a)∨D(a) T ⑶⑼ I
⑾ C(a) T ⑷⑽ I
⑿ ?B(a) T ⑺⑾ I
⒀ A(a)∧ ?B(a)) T ⑶⑿ I
⒁ ?x(A(x)∧ ?B(x)) EG ⒀
”表示否定其中,????????
???????
))()(())()((
) ) ),()(()(() ) ),()(()((
xBxAxxDxAx
xDxCxAxxCxBxAx
第三章 集合论初步
1.集合的表示,幂集,全集,空集,
2.集合的三种关系 (包含,相等,真包含 )的定义及证明,
3.集合的五种运算及相关性质,
*4.应用包含排斥原理,
第三章 集合论初步
基本概念,集合与元素,子集与真子集,空集,全集,幂集,
并集,交集,相对补集 (差集 ),绝对补集 (补集 )
1.集合的表示,元素与集合的属于关系 ∈,
集合的三种表示方法,
枚举法,一一列出集合中的元素,
谓词描述法,用谓词描述集合中元素的性质,
文氏图,用一个平面区域表示,
2.集合的三种关系 (被包含,相等,被真包含 )的定义及证明,
A?B ??x(x∈ A?x∈ B)
A=B? A?B?B?A??x(x∈ A?x∈ B)
A?B?A?B?A≠B??x(x∈ A?x∈ B)??x(x∈ B?x?A)
3空集,全集,幂集
空集 φ:无元素的集合, x∈ Φ是矛盾式, (空集是唯一的 )
全集 E:包含所讨论所有集合的集合, (全集不唯一 )
x∈ E是永真式
幂 集,由 A的所有子集构成的集合,
P(A)={X|X?A} |P(A)|=2|A|
4.掌握集合的五种运算及相关性质,
A∩B={x|x∈ A∧ x∈ B} x∈ A∩B ? x∈ A∧ x∈ B
A∪ B ={x|x∈ A∨ x∈ B} x∈ A∪ B ? x∈ A∨ x∈ B
A-B ={x|x∈ A∧ x ? B} x∈ A-B ? x∈ A∧ x?B
~A =E-A={x|x∈ E∧ x?A}={x|x?A} x∈ ~A?x?A
A-B=A∩ ~B
A?B=(A-B)∪ (B-A)={x|(x∈ A∧ x?B)∨ (x∈ B∧ x?A)}
A?B=(A∪ B)-(A∩B)
例 1.已知全集 E={Φ,{Φ}},A?E,计算,
a)P({Φ})?P({Φ})=( )
b)P(A)∩P(~A)=( )
c)P(E)-P(~{{Φ}})=( )
解,a) 因为任何集合 A,都有 A?A=Φ 所以
P({Φ})?P({Φ})=Φ
b) 因为 Φ?A Φ? ~A,即 Φ∈ P(A) Φ∈ P(~A) 所以
P(A)∩P(~A)={Φ}
c) P(E)={Φ,{Φ},{{Φ}},{Φ,{Φ}}}
~{{Φ}}={Φ}
P(~{{Φ}})=P( {Φ})= {Φ,{Φ}}
P(E)-P(~{{Φ}}) )={Φ,{Φ},{{Φ}},{Φ,{Φ}}}-{Φ,{Φ}}
={{{Φ}},{Φ,{Φ}}}
例 2证明各式彼此等价。 P?Q ?(?P∨ Q)∧ (P∨ ?Q)
c)A∪ B=B,A∩B=A,A?B,~B? ~A.
证明, A∪ B=B ??x(x∈ A∪ B ?x∈ B)
??x((x?A∪ B?x∈ B)?(x∈ A∪ B?x?B))
??x(((x?A?x?B)?x∈ B)?((x∈ A?x∈ B)?x?B))
??x((x?A?x?B)?x∈ B)
??x((x?A?x∈ B)?(x?B?x∈ B))??x((x?A?x∈ B)
??x(x∈ A?x∈ B) ? A?B
??x(x∈ A?x∈ B)??x(x?B?x?A)
??x(x∈ ~B?x∈ ~A) ? ~B ?~A
由 A∪ B=B 得 A? (A∪ B)=A? B A=A? B
类似由 A∩B=A,可以推出 A∪ B=B
所以 A∪ B=B?A∩B=A 从而证得
A∪ B=B,A∩B=A,A?B,~B? ~A 彼此等价。
T
例 3 证明, (A-B)-C=A-(B∪ C)
方法 1,(A-B)-C=(A∩ ~B)∩ ~C=A∩( ~B∩ ~C)
=A∩ ~(B∪ C)=A-(B∪ C)
方法 2.任取 x∈ (A-B)-C?(x∈ A∧ x?B)∧ x?C
?x∈ A∧ ( x?B∧ x?C) ?x∈ A∧ ?( x∈ B∨ x∈ C)
?x∈ A∧ ?( x∈ B∪ C) ?x∈ A∧ x?B∪ C?x∈ A-(B∪ C)
所以 (A-B)-C=A-(B∪ C)
例 4,令全集 E为信息学院的学生的集合,C表示计算机专
业学生的集合,M表示学习了离散数学的学生的集合,D表
示学习了数据结构课学生的集合,F表示一年级的学生的
集合,用集合的关系式表达下面句子,
“学习了离散数学和数据结构课的学生,一定是计算机
专业的非一年级的学生”,
解, (M∩D)?(C∩~F)
例 4,在什么条件下，下面命题为真？
a) (A-B)∪ (A-C)=A
解,(A-B)∪ (A-C)= (A∩~B)∪ (A∩~C)=A∩(~B∪ ~C)
= A∩~(B∩C)=A-(B∩C)=A
所以满足此式的 充要条件 是,A∩B∩C= Φ
b) (A-B)∪ (A-C)=Φ
解,(A-B)∪ (A-C)= A-(B∩C)=Φ 充要条件 是,A ? B∩C
c) (A-B)∩(A-C)=Φ
解,(A-B)∩(A-C)= (A∩~B)∩(A∩~C)=A∩(~B∩~C)
= A∩~(B∪ C)=A-(B∪ C)=Φ 充要条件 是, A ? B∪ C
d) (A-B)?(A-C)=Φ
解, 因为 当且仅当 A=B, 才有 A?B=Φ
所以满足此式的 充要条件 是, A-B=A-C
*例 5,用谓词逻辑推理证明
对任何集合 A,B,C，如果有 A?B且 B?C,则 A?C。
证明, ?x(x∈ A?x∈ B)??x(x∈ B?x?A),
?x(x∈ B?x∈ C)??x(x∈ C?x?B)??x(x∈ A?x∈ C)??x(x∈ C?x?A)
⑴ ?x(x∈ A?x∈ B)??x(x∈ B?x?A) P
⑵ ?x(x∈ A?x∈ B) T ⑴ I
⑶ ?x(x∈ B?x?A) T ⑴ I
⑷ ?x(x∈ B?x∈ C)??x(x∈ C?x?B) P
⑸ ?x(x∈ B?x∈ C) T ⑷ I ⑹ x∈ A?x∈ B US ⑵
⑺ x∈ B?x∈ C US ⑸ ⑻ x∈ A?x∈ C T ⑹⑺ I
⑼ ?x(x∈ A?x∈ C) UG ⑻ ⑽ x∈ B?x?A ES ⑶
⑾ x∈ B T ⑽ I ⑿ x?A T ⑽ I
⒀ x∈ C T ⑺ ⑾ I ⒁ x∈ C?x?A T ⑿ ⒀ I
⒂ ?x(x∈ C?x?A) EG ⒁
⒃ ?x(x∈ A?x∈ C) ??x(x∈ C?x?A) T⑼⒂ I
*有 14位学生参加考试,9位同学数学得了优 ;5位同学物理
得了优 ;4位同学化学得了优 ;其中物理和数学都得优的同
学有 4人 ;数学和化学都得优的同学有 3人 ;物理和化学都得
优的同学有 3人 ;三门都得优的同学有 2人 ;问没有得到优的
有多少人?恰有两门得优的同学有多少人?
解,令 A,B,C分别表示数学、物理、化学得优同学集合,
全集为 E,于是有 |E|=14 |A|=9 |B|=5 |C|=4 |A∩B|=4
|A∩C|=3 |B∩C|=3 |A∩B∩C|=2
|A∪ B∪ C|=|A|+|B|+|C|-|A∩B|-|B∩C|-|B∩C|+ |A∩B∩C|
=9+5+4-4-3-3+2=10 于是得到优的人数是 10人,
∴ 没有得到优的人数是, 14-10=4 人
恰有两门得优的人数, (|A∩B|-|A∩B∩C|)+
(|B∩C|-|A∩B∩C|)+(|B∩C|-|A∩B∩C|)=4-2+3-2+3-2=4
第四章 二元关系
1.关系的概念,表示方法,
2.二元关系的 性质的定义,熟练掌握性质的判断及证明,
3.掌握关系的复合,求逆及闭包运算 (计算方法及有关性质 )
4.掌握等价关系的判断,证明,求等价类和商集,
*5.掌握相容关系的概念,关系图和矩阵的简化,求相容类,
最大相容类和完全覆盖,
6.偏序关系的判断,会画 Hasse图,会求一个子集的极小 (大 )
元,最小 (大 )元,上界与下界,最小上界及最大下界,
注意本章证明题的证明过程的思路
一,关系的概念,表示方法,三个特殊关系,
1.集合的笛卡 尔 积
A× B={<x,y>|x∈ A∧ y∈ B} |A|=m,|B|=n |A× B|=mn
设 A={0,1},B={a,b}，求 A?B 。
A?B={<0,a>,<0,b>,<1,a>,<1,b>}
2.二 元关系的概念
定义 1:设 A、Ｂ是集合,如果Ｒ ?A× B,则称 R是一个从 A到
B的二元关系。如果 R?A× A,则称 R是 A上 的二元 关系,
如果 |A|=m |B|=n 则可以确定 2mn个从 A到 B的不同关系,
定义 2:任何 序偶的集合,都称之为一个二元关系。
3.关系的表示方法
1),枚举法,
即将关系中所有序偶一一列举出，写在大括号内,
如,R={<1,2>,<3,4>,<4,2>}
2).(描述法 )谓词公式法,
即用谓词公式描述序偶中元素的关系。例如
R={<x,y>|x<y}
3).有向图法,
1。
2。
3。
4。
。
。
。
A B
a
b
c
R1,
1。 。
4。 。
2
3
R2,
4).矩阵表示法, (实际上就是图论中的邻接矩阵 )
设 A={a1,a2,?,am},B={b1,b2,?,bn}是个有限集，
R?A× B，定义 R的 m× n阶 矩阵
MR=(rij)m× n，其中
4.三个特殊 关 系
1).空关系 Φ：
Φ?A× B,(或 Φ?A× A)，即无任何元素的关系,
它的关系图中只有结点,无任何边；它的矩阵中全是 0。
2).完全关系 (全域关系 )：
A× B(或 A× A)本身是一个从 A到 B(或 A上 )的完全关系,
即含有全部序偶的关系。它的矩阵中全是 1。
1 若 <ai,bj>∈ R
0 若 <ai,bj>∈ R (1≤i≤m,1≤j≤n)rij=
3),恒等关系 IA：
IA?A× A,且 IA ={<x,x>|x∈ A}称之为 A 上的恒等关系。
例如 A={1,2,3},则 IA ={<1,1>,<2,2>,<3,3>}
A上的 Φ、完全关系 A× A及 IA的关系图及矩阵如下：
MIA =
1 0 0
0 1 0
0 0 1 3× 3
1。
2。 。 3
1。
2。 。 3
1 1 1
1 1 1
1 1 1 3× 3
1。
。2。 3
0 0 0
0 0 0
0 0 0 3× 3
MΦ= MA× A=
Φ A× A IA
二,关系的性质,
熟练掌握性质的判断及证明,
1.自反性
定义,设 R是集合 A中的关系，如果对于任意 x∈ A都有
<x,x>∈ R (xRx)，则称 R是 A中自反关系。即
R是 A中自反的 ??x(x?A?xRx)
2.反自反性
定义,设 R是集合 A中的关系，如果对于任意的 x∈ A都有
<x,x>?R,则称 R为 A中的反自反关系。即
R是 A中反自反的 ??x(x?A?<x,x>?R)
3.对称性
定义,R是集合 A中关系,若对任何 x,y∈ A,如果有 xRy,必有
yRx,则称 R为 A中的对称关系。
R是 A上对称的 ??x?y((x?A?y?A?xRy) ?yRx)
4.反对称性
定义,设 R为集合 A中关系,若对任何 x,y∈ A,如果有 xRy,和
yRx,就 有 x=y,则称 R为 A中反对称关系 。
R是 A上反对称的 ??x?y((x?A?y?A?xRy?yRx)?x=y)
??x?y((x?A?y?A?x?y?<x,y>∈ R)?<y,x>?R)
5,传递性
定义,R是 A中关系，对任何 x,y,z∈ A,如果有 xRy,和 yRz,就
有 xRz,则称 R为 A中传递关系。
即 R在 A上传递
??x?y?z((x?A?y?A?z?A?xRy?yRz)?xRz)
这 些性 质 要求会判断,会 证 明,
这 里特 别 要注意的是,这 些定 义 都是 蕴 涵式,所以当 蕴 涵
式当前件 为 假 时,此 蕴 涵式 为 真,即此性 质 成立 !!
自反性
反自反性
对称性
传递性
反对称性
每个结点都有环 主对角线全是 1
每个结点都无环 主对角线全是 0
不同结点间如果有边,
则有方向相反的两条
边,
是以对角线为对称
的矩阵
不同结点间,最多有一
条边,
以主对角线为对称
的位置不会同时为 1
如果有边 <a,b>,<b,c>,
则也有边 <a,c>,
或者使得前件为假,
如果 aij=1,且 ajk=1,
则 aik=1
从 关 系的矩 阵从 关 系的有向 图性 质 判定,
判断下面关系的性质,
1。
2。 。
1。
2。 。
1。
2。 。
1。
2。 。 33 33
R2R1 R3 R4
自反性 反自反性 对称性 反对称性 传递性
R1 Y N N Y Y
R2 N Y N Y N
R3 Y N Y N Y
R4 Y N Y Y Y
1。
2。 。
1。
2。 。
1。
2。 。
1。
2。 。 33 33
R5 R6 R7 R8
自反性 反自反性 对称性 反对称性 传递性
R5 N Y N Y Y
R6 N N Y N N
R7 N N N N N
R8 N Y Y Y Y
关系性质当证明方法归纳, 设 R是 A上关系，
1.证明 R的 自反性,
方法 1 用自反定义证：任取 x∈ A,证出 <x,x>∈ R.
方法 2 用恒等关系 IA证,证出 IA?R,(见教材 P119(2))
方法 3 用自反闭包证,证出 r(R)=R,即 R∪ IA=R.
2.证明 R的 反自反性,
方法 1 用反自反定义证：任取 x∈ A,证出 <x,x>?R.
3.证明 R的 对称性,
方法 1 用对称定义证：
任取 x,y∈ A,设 <x,y>∈ R,证出 <y,x>∈ R.
方法 2 用求逆关系证,证出 Rc=R.
方法 3 用对称闭包证,证出 s(R)=R,即 R∪ Rc =R.
4.证明 R的 反对称性,
方法 1 用定义 1证：
任取 x,y∈ A,设 <x,y>∈ R,<y,x>∈ R.证出 x=y。
方法 2用定义 2证：
任取 x,y∈ A,x≠y,设 <x,y>∈ R,证出 <y,x>?R.
方法 3 用定理证,证出 R∩Rc ? IA, (见 教材 P118)
5.证明 R的 传递性,
方法 1 用传递定义证：
任取 x,y,z∈ A,设 <x,y>∈ R,<y,z>∈ R,证出 <x,z>∈ R.
方法 2 用传递闭包证,证出 t(R)=R,
即 R∪ R2∪ R3∪,.,=R.
方法 3用定理证,证出 (见教材 P119(2))
同学们可以根据具体情况,选用相应方法证明,其中必须掌
握的是用基本定义证明,
R R?Ro
三,掌握关系复合,求逆及闭包运算 (计算方法及性质 )
(一 )关系的复合
1.定 义,设 R?X× Y,S?Y× Z，则 R?S?X× Z。
R?S={<x,z>|x?X?z?Z??y(y?Y ?<x,y>?R?<y,z>?S)}
2.计算方法 (俗称过河拆桥法 )
⑴ 枚举法 R={<a,b>,<b,c>,<c,a>}
S={<a,b>,<b,c>,<b,b>,<c,a>}
R?S={<a,c>,<a,b>,<b,a>,<c,b>}
⑵ 有向图
a。
b。
c。
X
。
。
。
Y
a
b
c
R S
。
。
。
Z
a
b
c
。
。
。
Z
a
b
c
a。
b。
c。
X SR?
⑶ 矩阵
3.性质
1).满足结合律,R?A× B S?B× C T?C× D 则
R?(S?T)=(R?S)?T
2),R?A× B S?B× C T?B× C
⑴ R? (S∪ T)=(R?S)∪ (R?T)
⑵ R? (S∩T)?(R?S)∩(R?T)
3),R是从 A到 B的关系，则
R? IB=IA? R=R
推论, R?A× A,则 R? IA=IA? R=R (IA是运算 ?的 幺元 )
4).关系的乘幂 R0 =IA,R?A× A,
Rm ?Rn = Rm+n
(Rm)n =Rmn (m,n为非负整数 )
MR? S= 010001
100
010011
100? =
011100
010
(二 ),逆关系
1.定 义,设 R?X× Y,R的逆关系 RC={<y,x>|<x,y>?R}
<y,x>∈ RC ?<x,y>?R
2,计算方法
1),R={<1,2>,<2,3>,<3,4>,<4,5>}
RC ={<2,1>,<3,2>,<4,3>,<5,4>}
2),RC的有向图,是将 R的有向图的所有边的方向颠倒,
3),RC的矩阵 MRC =(MR)T 即为 R矩阵的转置
3.性质
令 R,S都是从 X到 Y的关系，则
1),(RC)C = R
2),(R∪ S)C = RC∪ SC 。
3),(R∩S)C = RC∩SC 。
4),(R－ S)C = RC－ SC 。
5),R?S ? RC?SC 。
6),(~R)C=~RC
7).令 R是从 X到 Y的关系,S是 Y到 Z的关系，则
(R? S)C= SC? RC 。
8),R是 A上关系，则
⑴ R是对称的，当且仅当 RC =R
⑵ R是反对称的，当且仅当 R∩RC ?IA。
(三 ).闭包运算
1.定义,给定 A中关系 R,若 A上另一个关系 R’，满足：⑴
R?R’；
⑵ R’是自反的 (对称的、传递的 )；
⑶ R’是,最小的,，即对于任何 A上自反 (对称、传递 )
的关系 R”,如果 R?R”,就有 R’?R”。 则称 R’是 R的 自反
(对称、传递 )闭包。记作 r(R),(s(R), t(R)) (reflexive、
symmetric,transitive)
2.计算方法 给定 A中关系 R
r(R)=R∪ IA。
s(R)=R∪ RC 。
t(R)=R∪ R2∪ R3∪,..。
t(R)=R∪ R2∪,..∪ Rn
*求 t(R)矩阵的 Warshall算法,
闭包的运算有三种形式,
如 A={a.b.c} R? A× A R={<a,b>,<b,c>,<c,a>}
a).集合形式,
r(R)=R∪ IA ={<a,b>,<b,c>,<c,a>}?{<a,a>,<b,b>,<c,c>}
={<a,b>,<b,c>,<c,a>,<a,a>,<b,b>,<c,c>}
s(R)=R∪ RC ={<a,b>,<b,c>,<c,a>}?{<b,a>,<c,b>,<a,c>}
={<a,b>,<b,c>,<c,a>,<b,a>,<c,b>,<a,c>}
R2={<a,c>,<b,a>,<c,b>} R3={<a,a>,<b,b>,<c,c>}
t(R)=R∪ R2∪ R3
={<a,b>,<b,c>,<c,a>}∪ {<a,c>,<b,a>,<c,b>}∪
{<a,a>,<b,b>,<c,c>}
={<a,b>,<b,c>,<c,a>,<a,c>,<b,a>,<c,b>,<a,a>,
<b,b>,<c,c>}
b)有向图形式,
b?
a?
?c
R3
R
b?
a?
?c b?
a?
?c
IA
∪ =
r(R)
b?
a?
?c
∪
R
b?
a?
?c b?
R2
a?
?c
t(R)
b?
a?
?c
∪ =
?c
∪
R
b?
a?
?c
=b?
RC
a?
s(R)
b?
a?
?c
c)矩阵形式,
Mr(R)=MR∨ MIA=
010001
100
100010
001∨ =
111110
011
Ms(R)=MR∨ MRC
=
010001
100
001100
010∨ =
011101
110
Mt(R)=M ∨ M ∨ M = 010001
100
001100
010
∨ = 111111
111R
2 R3R ∨
100010
001
3.性质
1),R是 A上关系，则
⑴ R是自反的，当且仅当 r(R)=R.
⑵ R是对称的，当且仅当 s(R)=R.
⑶ R是传递的，当且仅当 t(R)=R.
2),R是 A上关系，则
⑴ R是自反的，则 s(R)和 t(R)也自反。
⑵ R是对称的，则 r(R)和 t(R)也对称。
⑶ R是传递的，则 r(R)也传递。
* 3).设 R是 A上关系，则
⑴ sr(R)=rs(R)
⑵ tr(R)=rt(R)
⑶ st(R)?ts(R)
四,等价关系
掌握等价关系的判断,证明,求等价类和商集,
1.了解集合的划分与覆盖的概念,
例 X={1,2,3},A1={{1,2,3}},A2={{1},{2},{3}},
A3={{1,2},{3}},A4={{1,2},{2,3}},A5={{1},{3}}
A1,A2,A3,A4 是覆盖。 A1,A2,A3也是划分。
2.等价关系 定义,设 R是 A上关系,若 R是自反的、对称的
和传递 的，则称 R是 A中的等价关系。
3.等价关系 R的有向图,可能由若干个独立子图构成的，
每个独立子图都是完全关系图 。
1。
2。 。 3
R1 1。
2。 。 3
R2
1。
2。 。
R3
4.等价类,
1).定义,R是 A上的等价关系,a∈A,由 a确定的集合 [a]R
[a]R={x|x∈A∧<a,x>∈R}
称集合 [a]R为由 a形成的 R等价类。
2).由等价关系图求等价类, R图中每个独立子图上的结
点构成一个等价类。不同的等价类个数 =独立子图个数。
3).等价类性质 R是 A上等价关系，任意 a,b,c∈ A
⑴ 同一个等价类中的元素，彼此有等价关系 R。
⑵ [a]R∩[b]R=Φ,当且 仅当 <a,b>?R。
⑶ [a]R=[b]R 当且 仅当 <a,b>∈ R。
⑷,A中任何元素 a,a必属于且仅属于一个等价类。
⑸,任意两个等价类 [a]R,[b]R,
要么 [a]R=[b]R,要么 [a]R∩[b]R=Φ。
⑹ R的所有等价类构成的集合是 A的一个划分。
5.商集,定义, R是 A上等价关系，由 R的所有等价类构成
的集合称之为 A关于 R的商集。记作 A/R。即
A/R={[a]R |a∈ A}
6.商集应用,
1)按照集合的等势关系 (是等价关系 ),~”对集合族 S进行
划分，得到商集 S/~,进而得到基数类的概念。
S={0,Φ,1,{1},{a},…,2,{0,1},{a,b},…,3,{0,1,2},…,N,I,…R,.,}
S/~={[0],[1],[2],[3],…,[N],[R],...}
2).无向图结点之间的连通关系是个等价关系,
令 G=<V,E>是无向图,R是 V上连通关系,即
R={<u,v>|u和 v是连通的 }
例, 给定图 G如右上图所示,
V/R={{a,b,g},{c,d,e,f},{h}}
无元素 1个元素 2个元素 3个元素 可数集 不可数集,..
?gh?
a? ?b
?ef?
c? ?d
3).图的同构关系 ≌ 是个等价关系,
令上述图构成的集合 A={a,b,c,d,e,f,g,h,i,j,},求商集 A/≌,
A/≌ ={{a,h},{b,i},{c,e},{d},{f},{g,j}}
?
? ?
? ?
?
? ?
? ?
?
? ?
? ?
?
? ?
? ?
?
? ?
? ?
?
? ?
? ?
?
? ?
? ?
?
? ?
? ?
?
? ?
? ?
?
? ?
? ?
a b c d e
f g h i j
练习 1.R和 S都是 A上等价关系,下面哪个是 A上等价关系?
证明或举反例说明,
a) R∪ S b) R∩S c) ~R (即 A× A-R)
d) R-S e)R2 f) r(R-S) e) Rc
解,a) c) d) f)不是, 请看反例,
R
。 a
。 cb。
。 a
。 cb。
。 a
。 cb。S R∪ S
。 a
。 cb。 ~R
。 a
。 cb。 R’
。 a
。 cb。 R’-S
。 a
。 cb。 r(R’-S)
b) R∩S是等价关系,
证明, 1,证明 R∩S的自反性
方法 1 用自反定义证：任取 x∈ A,(证出 <x,x>∈ R∩S)
因 R和 S都自反，所以有 <x,x>∈ R,<x,x>∈ S，于是有
<x,x>∈ R∩S，所以 R∩S也自反。
方法 2 用恒等关系 IA证,(证出 IA ?R)
因 R和 S都自反，所以 IA ?R, IA ?S，所以 IA ?R∩S
所以 R∩S也自反。
方法 3 用自反闭包证：
(证出 r(R∩S)=R∩S,即 (R∩S)∪ IA= R∩S)
因 R和 S都自反，所以 r(R)=R,r(S)=S,
r(R∩S)=(R∩S)∪ IA= (R∪ IA)∩(S∪ IA)
=r(R)∩r(S)=R∩S 所以 R∩S也自反。
2.证明 R∩S 的对称性：
方法 1 用对称定义证：
任取 x,y∈ A,设 <x,y>∈ R∩S,(证出 <y,x>∈ R∩S,)
则 <x,y>∈ R,<x,y>∈ S,因为 R和 S对称，所以有
<y,x>∈ R,<y,x>∈ S,于是 <y,x>∈ R∩S 。 ∴ R∩S 对称。
方法 2 用求逆关系证,(证出 (R∩S )c=R∩S,)
因为 R和 S对称，所以有 Rc=R,Sc=S,而
(R∩S )c=Rc∩S c= R∩S, ∴ R∩S 对称。
方法 3 用对称闭包证,(证出 s(R∩S )=R∩S,)
因为 R和 S对称，所以 s(R)=R,s(S)=S
s(R∩S )= (R∩S )∪ (R∩S )c =(R∩S )∪ (Rc∩S c)
=(R∪ Rc)∩ (R∪ Sc)∩ (S∪ Sc)∩ (S∪ Rc)
=(s(R)∩ (R∪ Sc))∩ (s(S)∩ (S∪ Rc))
=(R∩ (R∪ Sc))∩ (S∩ (S∪ Rc))=R∩ S (吸收律 )
∴ R∩S 对称。
3.证明 R∩S 的传递性：
方法 1 用传递定义证：任取 x,y,z∈ A,
设 <x,y>∈ R∩S,<y,z>∈ R∩S,(证出 <x,z>∈ R∩S )
<x,y>∈ R∩S ∧ <y,z>∈ R∩S
? <x,y>∈ R∧ <x,y>∈ S∧ <y,z>∈ R∧ <y,z>∈ S
? (<x,y>∈ R∧ <y,z>∈ R)∧ (<x,y>∈ S ∧ <y,z>∈ S)
? <x,z>∈ R∧ <x,z>∈ S （因为 R,S传递）
? <x,z>∈ R∩S 所以 R∩S 传递 。
所以 R∩S 是 A上等价关系,
e)证明, R2是等价关系,
方法 1.由 P119习题 (3)得,如果 R自反和传递,则 R2 =R,所以
R2也是等价关系,
方法 2.① 证 R2自反,
任取 a∈ A,因为 R自反,所以 <a,a>∈ R,根据关系的复合得,
<a,a>∈ R R,即 <a,a>∈ R2,所以 R2自反。
② 证 R2对称,
(R2)c=(Rc)2=R2 (由 R对称得 Rc=R) ∴ R2对称
③ 证 R2传递,
任取 a,b,c∈ A,设有 <a,b>∈ R2,<b,c>∈ R2,
根据关系的复合得,
(?d∈ A∧ <a,d>∈ R∧ <d,b>∈ R)∧ (?e∈ A∧ <b,e>∈ R∧ <e,c>∈ R),
由于 R传递,所以有 <a,b>∈ R,<b,c>∈ R,∴ <a,c>∈ R2
所以 R2传递。 最后得 R2是等价关系。
g),R是 A上等价关系,则 Rc也是 A上等价关系,
证明 1)证 Rc自反。
因为任取 x∈ A,因 R自反，所以 <x,x>∈ R,∴ <x,x>∈ Rc
2) R对称，证 Rc也对称。
因为 R对称，所以 Rc =R ∴ Rc也对称。
3) R传递，证 Rc也传递。
方法 1,任取 x,y,z∈ A,且有 <x,y>∈ Rc,<y,z>∈ Rc,于是
<y,x>∈ R,<z,y>∈ R，因 R传递,∴ <z,x>∈ R,于是有
<x,z>∈ Rc,∴ Rc传递。
方法 2,t(Rc)=Rc∪ (Rc)2∪ (Rc)3∪ …
= Rc∪ (R2)c∪ (R3)c∪ …= (R ∪ R2∪ R3∪ …) c
= (t(R))c=Rc 所以 Rc传递。
所以 Rc是 A上等价关系,
练习 2.五,设 X={1,2,3} Y={1,2},在 X的幂集 P(X)上定义二
元关系 R如下, 对于任何 A,B∈ P(X),
ARB 当且仅当 A?Y=B?Y
1.画出关系 R的有向图,
2.R是等价关系吗?如果是,请写出商集 P(X)/R,如果不是请
说明原因
解,1.关系 R的有向图,
2,从 R有向图看出 R有自反,对称和传递性,故是等价关系
P(X)/R={{?,{1},{2},{1,2}},{{3},{1,3},{2,3},{1,2,3}}}
?{1,3}
?{1,2,3}{2,3}?
{3}??? ?{1}
{2}? ?{1,2}
*五,相容关系
1.定义,给定集合 X上的关系 r,若 r是自反的、对称的,则 r
是 A上 相容关系 。
2.图的简化,⑴不画环；
⑵两条对称边用一条无向直线代替。
3.矩阵的简化,因为 r的矩阵是对称阵且主对角线全是 1，
用下三角矩阵 (不含主对角线 )代替 r的矩阵。
4.相容类,设 r是集合 X上的相容关系,C?A,如果对于 C
中任意两个元素 x,y有 <x,y>∈ r,称 C是 r的一个 相容类,
5,最大相容类,设 r是集合 X上的相容关系,C是 r的一个相
容类，如果 C不能被其它 相容类所真包含，则称 C是一
个 最大相容类。 ----最大完全多边形,
6.完全覆盖, r是中的相容关系，由 r的所有 最大相容类
为元素构成的集合，称之为 X的完全覆盖。记作 Cr(X)。
练习,已知 X={1,2,3,4,5,6,7}上的相容关系 r的交换矩阵为,
求完全覆盖 Cr(X)
解,先画出 r的简化图,如右上图所示,
于是得完全覆盖为,
Cr(X)={{1,2,4,5},{1,3,7},{1,3,4},{7,6}}
1
1 0
1 1 1
1 1 0 1
0 0 0 0 0
1 0 1 0 0 1
1?
2? 3?
? 4
? 5
? 6
7?
五,偏序关系 判断,会画 Hasse图,会求一个子集的极小
(大 )元,最小 (大 )元,上界与下界,最小上界及最大下界,
1,定义, R是 A上自反、反对称和传递的关系，则称 R
是 A上的偏序关系。并称 <A,R>是偏序集。
2,x与 y是可比较的, <A,≤>是偏序集,x,y∈ A,如果要
么 x≤y,要么 y≤x,则称 x与 y是可比较的。
3.定义, <A,≤>是偏序集，任何 x,y∈ A,如果 x与 y都是可
比较的，则称 ≤是 全序 关系 (线序、链 )。
4.偏序集 Hasse图的画法, 令 <A,≤>是偏序集，
1).用,?”表示 A中元素。
2).如果 x≤y,且 x≠y,则结点 y要画在结点 x的上方。
3),如果 x≤y,且 y盖住 x,x与 y之间连一直线。
4),从最下层结点 (全是射出的边与之相连，逐层向上画，
直到最上层结点 (全是射入的边与之相连 )。
例如
2。
1。
。
6
4 2。
1。
。
8
4
１ 。
２ 。
４ 。６ 。
１ 。
２ 。
４ 。
８ 。
5,重要元素
y是 B的 极小元 ??y(y∈ B∧ ??x(x∈ B∧ x≠y∧ x≤y))
(在 B中没有比 y更小的元素了,y就是 极小元 )
y是 B的 极大元 ??y(y∈ B∧ ??x(x∈ B∧ x≠y∧ y≤x))
(在 B中没有比 y更大的元素了,y就是 极大元 )
y是 B的 最小元 ??y(y∈ B∧ ?x(x∈ B?y≤x))
(最小元 y是 B中元素，该元素比 B中所有元素都小 )
y是 B的 最大元 ??y(y∈ B∧ ?x(x∈ B?x≤y))
(最大元 y是 B中元素，该元素比 B中 所有元素都大 )
y是 B的 上界 ??y(y∈ A∧ ?x(x∈ B?x≤y))
(上界 y是 A中元素，该元素比 B中所有元素都大 )
y是 B的 下界 ??y(y∈ A∧ ?x(x∈ B?y≤x))
(下界 y是 A中元素，该元素比 B中 所有元素都小 )
y是 B的上界，并且对 B的所有上界 x,都有 y≤x,则
称 y是 B的 最小上界 (上确界 )，记作 LUB B=y 。
(即 y是上界中最小的。如果 B有上确界，则是唯一的 )
y是 B的下界，并且对 B的所有下界 x,都有 x≤y,则
称 y是 B的 最大下界 (下确界 )，记作 GLB B=y 。
(即 y是下界中最大的。如果 B有上确界，则是唯一的 )
例如 B={2,3,6}
B的极小元,2,3 极大元, 6
最小元,无 最大元,6
下界,1 上界,6,12,18
下确界,1 上确界,6 １ 。
6。
18。12。
2。 。 3
第六章 函数
1.函数的定义,
2.函数的类型,会判断,会证明,
3.会计算函数的复合 (左复合 ),求逆函数,知道有关性质,
*4.了解集合特征函数和模糊子集的表示及计算,
*5.了解自然数的定义,集合的等势定义,集合基数的定义,
可数集定义,可数集的基数,连续统基数,基数的比较,
一,概念
1.定义, X与 Y集合,f是从 X到 Y的关系，如果 任何 x∈ X，
都存在 唯一 y∈ Y,使得 <x,y>∈ f,则称 f是 从 X到 Y的函数,
(变换、映射 )，记作 f:X?Y.
如果 f:X?X是函数,也称 f是 X上的函数,
要求会判断 某些给定关系是否是函数,
2.函数相等, f:A?B,g:C?D,f=g?A=C?B=D?f(x)=g(x)
3.从 X到 Y函数的集合 YX,YX ={f| f:X?Y}
YX, 它是由 所有 的从 X到 Y函数 构成的集合,
4.特殊函数
1),常值函数,函数 f:X?Y, 如果 ?y0∈ Y,使得对 ?x∈ X,
有 f(x)=y0,即 ran f={y0},称 f是常值函数。
2).恒等函数,恒等关系 IX是 X到 X函数，即 IX:X?X,称
之为恒等函数。显然对于 ?x∈ X，有 IX(x)=x 。
5.函数的类型,会判断,会证明,
1).满射的, f:X?Y是函数，如果 Rf=Y,则称 f 是 满射的 。
证明方法,任取 y∈ Y,看是否能够找到对应的自变元
x∈ X,使得 y=f(x).
2).映内的, f:X?Y是函数，如果 Rf?Y 则称 f 是 映内的 。
3).入射的, f:X?Y是函数，如果对于任何 x1,x2∈ X,如果
x1≠x2 有 f(x1)≠f(x2),(或者若 f(x1)=f(x2),则 x1=x2),则称 f 是
入射的,也称 f 是 单射的,也称 f 是 一对一的 。
证明的方法,如定义中所说,
4).双射的, f:X?Y是函数，如果 f 既是满射的，又是
入射的，则称 f 是 双射的,也称 f 是 一一对应的 。
双射是个重要概念,我们用双射定义了如下概念,
集合的等势关系,~” ;
代数系统的同构关系,≌,
图的同构关系,≌,
练习题,R是实数集合，给定 R上的五个关系如下,
R1={<x,y>|x=y2} R2={<x,y>|y=x+6}
R3={<x,y>|y=(x-1)-1} R4={<x,y>|y=2x}
R5={<x,y>|x2+y2=4}
上述五个关系中，哪些 是从 R到 R的函数。如果是函数，
说明它是属于什么类型的（指满射、入射、双射）。
如果不是函数，说明理由 。
解,R1不 是从 R到 R的函数,x是负数时
无定义,另外当 x>0时,有两个 y值与之对应,
R2是从 R到 R的函数,是双射的,
R3不 是从 R到 R的函数,因为 x=1时,无定义,
R4是从 R到 R的函数,是入射的,不是满射的,
R5不 是从 R到 R的函数,因为 |x|>2时,无定义,|x|<2时
对应的函数值不唯一,
x
y
二,会计算函数复合 (左复合 ),求逆函数,知道有关性质,
1.函数的复合
1)定义, f:X?Y,g:Y?Z是函数,则定义
g?f ={<x,z>|x?X?z?Z??y(y?Y ?<x,y>?f?<y,z>?g)}
则称 g?f 为 f与 g的复合函数 (左复合 ).
注意,这里把 g写在 f的左边了,所以叫左复合,
g?f,X?Z,即 g?f 是 X到 Z的函数,这样写是为了
照顾数学习惯, g?f(x)=g(f(x)) ?x∈ X
2).复合函数的计算
计算方法同复合关系的计算, 但要注意是左复合,
3).函数复合的性质
(1).满足可结合性 。 f:X?Y,g:Y?Z,h:Z?W 是函数,则
(h? g)?f=h?(g? f)
(2).定理 5-2.2 f:X?Y,g:Y?Z是两个函数,则
a).如果 f和 g是 满 射的，则 g?f 也是 满 射的；
b).如果 f和 g是 入 射的，则 g?f 也是 入 射的；
c).如果 f和 g是 双 射的，则 g?f 也是 双 射的。
(3).⑴ 如果 g?f是 满 射的，则 g是 满 射的；
⑵ 如果 g?f是 入 射的，则 f 是 入 射的；
⑶ 如果 g?f 是 双 射的，则 f是 入 射的 和 g是 满 射的。
(4),f:X?Y是函数,则 f ? IX = f 且 IY? f = f。
f:X?X是函数,则 f ? IX=IX? f=f。 IX是运算,?” 的幺
元,
2.逆函数
1).定义,设 f:X?y是双射的函数,fC:Y?X 也是函数,称
之为 f 的逆函数。并用 f-1代替 fC。 f-1存在，也称 f 可逆。
2).性质
(1),设 f:X?y是双射的函数，则 (f-1)-1= f 。
(2),设 f:X?Y是双射的函数，则有 f-1? f= IX 且 f? f-1 = IY。
(3).令 f:X?Y,g:Y?X是两个函数,如果
g?f= IX 且 f?g = IY,则 g= f-1 。
(4).令 f:X?Y,g:Y?X是两个 双射 函数,则 (g?f)-1=f-1? g-1
*证明题
给定函数 f:A→B g:C→D,已知
f?g 并且 ram g ? ran f,其中 ran g 是函数 g的值域
求证：如果 g是入射的，则Ａ＝Ｃ,
证明,先证 A?C 任取 x?A,因为 f:A→B 是函数，必存在
唯一 y?B，使得 <x,y>?f,又因为 f?g,所以 <x,y>?g,而
g:C→D 是函数，所以 x?C,所以 A?C。
再证 C?A,任取 x?C,因为 g:C→D 是函数，必存在
唯一 y?D，使得 <x,y>?g,所以 y?ran g,又 ram g? ran f,
所以 y?ran f,而 f:A→B, 所以 必存在 x’?A,使得 <x’,y>?f,
因为 f?g,所以 <x’,y>?g,可是前边已得 <x,y>?g,而 g是
入射的，所以 x’=x,即得 x?A,所以 C?A。
最后得 A=C。
第六章 代数系统
1.掌握运算的定义,
2.熟练掌握二元运算的性质的判断及证明,
3.掌握代数系统的同构定义,会证明,了解同构性质的保持,
4.了解半群,独异点,*环和域的概念,
5.熟练掌握群,子群,交换群 (会证明 ),
6.了解循环群,
*6,掌握循环群定义,循环群的循环周期以及循环群的同
构,
7.了解 Lagrange定理及其推论,(会应用 ).
*7,掌握 Lagrange定理及其推论 (会应用 ).
*8.了解环的运算法则,
注意本章证明题的思路和技巧
一,掌握运算和代数系统的概念,
1.运算定义,设 X是个集合,f:Xn?Y是个映射，则称 f是
X上的 n元运,(Xn =X× X×,..× X --n个 X的笛卡尔积 )
2代数系统定义, X是非空集合,X上的 m个运算
f1,f2,…f m,构成 代数系统 U,记作 U=<X,f1,f2,…f m> ( m≥1)
二,熟练掌握二元运算的性质的判断及证明,
<X,?>和 <X,?,?>是代数系统,?,?是二元运算：
1.封闭性,?x,y∈ X,有 x?y∈ X。
2.可交换性,?x,y∈ X,有 x?y=y? x。
3.幂等性,?x∈ X,有 x?x=x。
4,有幺元,e∈ X,?x∈ X，有 e?x=x?e=x.
5.有零元, θ∈ x,?x∈ X，有 θ?x=x?θ=θ.
6.可结合性,?x,y,z∈ X,有 (x?y)?z =x?(y?z)。,
7.有逆元,x∈ X,有 x-1∈ X，使得 x-1?x=x?x-1=e
8.可消去性,a∈ X,?x,y∈ X,有
(a?x=a?y)∨ (x?a=y?a) ? x=y.
9.分配律,?对 ?可分配,?x,y,z∈ X，有
x?(y?z)=(x?y)?(x?z) 或 (x?y)?z =(x?z)?(y?z)
10.吸收律,?x,y∈ X，有 x?(x?y)=x 和 x?(x?y)=x
对这些性质要求会判断、会证明。
三,掌握代数系统同构定义,会证明,了解同构性质的保持
1.定义设 <X,?>,<Y,?>是两个代数系统,?和 ? 都 是二元
运算，如果存在映射 f:X?Y,使得对任何 x1,x2∈ X，有
f(x1?x2)=f(x1)?f(x2) --------此式 叫 同态 (同构 )关系式
则称 f是从 <X,?>到 <Y,?>的同态映射，简称这两个代数
系统 同态 。记作 X∽ Y。
并称 <f(X),? >为 <X,?>的 同态像 。
如果 f是满射的，称此同态 f是 满同态 。
如果 f是入射的，称此同态 f是 单一同态 。
如果 f是双射的，称 <X,?>与 <Y,?>同构,记作 X≌ Y。
f是 <X,?>到 <X,?>的同态 (同构 ),称之为 自同态 (自同构 )。
2.代数系统 同构性质的保持
代数系统 <X,?>,<Y,?>,X≌ Y,f:X?Y是同构映射,如果
<X,?>中 ?满足交换、结合、有幺元、有零元、每个元
素可逆,则 <Y,?>中 ?也满足上述性质。反之亦然,
*3.同态核
定义, f是从 <X,?>到 <Y,?>的同态映射,(X∽ Y),e?和 e?
分别是 X,Y中幺元。定义 集合 ker (f)为：
ker (f)={x|x∈ X∧ f(x)= e? }
称 ker (f)为 f的同态核。
四,掌握半群,独异点,群,环和域的概念,
半群, 封闭
结合独异点,有幺元
群
可逆
环, <R,+,?><R,+>是交换群
<R,?>是半群
?对 +可分配整环 <R,+,?>
<R,?>是可交换独异点
无零因子 (ab=0则 a=0或 b=0)
域 <F,+,?> <F,
+>是交换群
<F-{0},?>是交换群
?对 +可分配
<R,+>是交换群
?对 +可分配
五,熟练掌握群的阶和元素的阶的概念及群的性质,
1.群的阶,<G,*>是群,如果 K[G]=n (n是正整数 ),则 G是 n
阶群,否则 G是无限阶群,
2.元素的阶,设 <G,?>是个群,a∈ G,如果存在 正整数 k，
使得 ak=e,则称 a的阶是有限的。如果存在 最小的正整数 n，
使得 an=e,则称 a的阶是 n。 否则就称 a的阶是无限的。
定理 6-5.7,<G,?>是群,a∈ G,如果 a的阶为 n,则
ak=e 当且仅当 k=mn (m∈ I)(即 k是 n的整数倍 )
定理 6-5.8,群中的元素与其逆元 具有相同的阶。
定理 6-5.9 有限群中，每个元素的阶都是有限的。
3.群的性质
1).群满足可消去性
定理 6-5.1设 <G,?>是个群，则对任何 a,b,c∈ G,如果 有
⑴ a?b=a?c 则 b=c 。
⑵ b?a= c?a 则 b=c 。
2),群方程可解性
定理 6-5.2 设 <G,?>是个群，则对任何 a,b∈ G,
⑴ 存在唯一元素 x∈ G,使得 a?x=b …….,⑴
⑵ 存在唯一元素 y∈ G,使得 y?a=b …….,⑵
3),群中无零元 。
定理 6-5.3 设 <G,?>是个群,如果 K[G] ≥2,则 G中无零元,
4),群中除幺元外，无其它幂等元 。
5).定理 6-5.5 <G,?>是个群，对任何 a,b∈ G,有
⑴ (a-1)-1 =a ⑵ (a?b)-1=b-1?a-1
6),有限群的运算表的特征
定理 6-5.6 <G,?>是个有限群，则 G中 每个元素 在 ?运算
表中的每一行 (列 )必出现且仅出现一次 。
练习题,给定群 <G,*>,*的运算表如
右图所示,求解下面群的方程,
b*d-1*x*c=d*c-1
解, b*d-1*x*c=d*c-1 ∵ d-1=b c-1=c
∴ b*b*x*c=d*c ∵ b*b=c ∴ c*x*c=d*c
消去 c得 c*x=d
解得, x=c-1*d=c*d=b
* a b c d
a a b c d
b b c d a
c c d a b
d d a b c
六,掌握交换群 (会证明 )
练习题 1.给定集合Ｇ＝ {x|x是有理数且 x≠1},在Ｇ上定
义二元运算 *如下：任何 a,b∈ Ｇ a*b=a+b-ab
求证 <Ｇ,*>是个交换群。
证明,1.证封闭性,任取 a,b?G,∴a≠1,b≠1,
a*b=a+b-ab 若 a+b-ab=1,则 b= =1,产生矛盾,
所以 a+b-ab≠1 ∴ a *b?G
2.证可结合性,任取 a,b,c?G,∴a≠1,b≠1,c≠1,
a*(b*c)=a+(b+c-bc)-a(b+c-bc)
=a+b+c-bc-ab-ac+abc=(a+b-ab)+c-(a+b-ab)c=(a*b)*c
3.证有幺元 0,任取 a?G,
a*0=a+0-a0=a 0*a=0+a-0a=a 所以 0是幺元,
___1-a
1-a
4.证可逆性,任取 a?G,a≠1,设有 b,使得
a*b=a+b-ab=0 ∴ a+(1-a)b=0,b= ≠1 ∴b ?G
a*b=0 且 b*a= *a= +a- a= =0
所以 a有逆元 b.即 a-1=
5.证交换性,任取 a,b?G,
a*b=a+b-ab=b+a-ba=b*a
综上所述 <G,*>是个交换群,
___a
a-1
__________a
a-1
___a
a-1
___a
a-1 a-1
a+a(a-1)-aa
___a
a-1
七, 了解循环群,
1.循环群的定义,设 <G,?>是群,如果存在一个元素 g∈ G,
使得对每个 x∈ G,都存在整数 i,有 x=gi,则称 <G,?>是
个 循环群, 并称 g是 G的 生成元,
2.循环群的循环周期,
周期有限,为 k;
周期无限,
3.两种循环群,
<Nk,+k>,周期为 k;
<I,+>, 周期无限,
八,会证明子群,会应用 Lagrange定理及其推论,
1.子群的证明方法,
方法 1.用子群的定义，即证明运算在子集上满足封闭、
有幺元、可逆。
方法 2,设 <G,?>是群,S是 G的非空子集，如果
<S,?>满足,封闭性和 可逆性,则 <S,?>是 <G,?>的子群。
方法 3.设 <G,?>是群,B是 G的 有限子集,如果 ?在 B上满足
封闭性,则 <B,?>是 <G,?>的子群。
方法 4,设 <G,?>是群,S是 G的非空子集，如果 任何 a,b∈ S
有 a?b-1∈ S,则 <S,?>是 <G,?>的子群。
练习题 2:设 f和 g都是群 <G1,?>到 <G2,? >的同态，证明
<C,?>是 <G1,?>的一个子群，其中
C={x| x∈ G1且 f(x)=g(x)}
证明, 方法 1，用子群定义证明 <C,?> 满足：
a)封闭性,任取 x1,x2∈ C,(推出 x1?x2∈ Cf(x1?x2)=g(x1?x2))
∴ f(x1)=g(x1) f(x2)=g(x2)
f(x1?x2) =f(x1) ? f(x2) =g(x1) ? g(x2)=g(x1?x2) ∴ x1?x2∈ C
b)证幺元 e1∈ C,(推出 f(e1)= g(e1))
设 e1和 e2分别是 G1和 G2中的幺元,
因 f(e1)= e2= g(e1) ∴ e1∈ C。
c)可逆性：任取 x∈ C,(推出 x-1∈ C 即 f(x-1)= g(x-1))
f(x)=g(x) x-1∈ G1,f (x-1)= (f(x))-1= (g(x))-1 =g(x-1)
∴ x-1∈ C。 综上所述,<C,?>是 <G1,?>的一个子群。
方法 4,任取 x1,x2∈ C,
(推出 x1?x2-1∈ C 即 f(x1?x2 -1)=g(x1?x2 -1))
∴ f(x1)=g(x1) f(x2)=g(x2) x2-1∈ G1
f(x1?x2-1 ) =f(x1)? f(x2-1) =f(x1)?(f(x2))-1 = g(x1)? (g(x2))-1
= g(x1) ? g(x2-1) = g(x1?x2-1)
∴ x1?x2-1∈ C
所以 <C,?>是 <G1,?>的一个子群。
综合练习题,设 <G,?>是群，定义 G上关系 R如下；
R= {<x,y>| ?z∈ G,使得 y=z?x?z-1 }
1.证明 R是 G上等价关系。
*2.令上述 <G,?>为 <N6,+6>时,求商集 N6/R.
证明 1.a) 证 R自反,任取 x∈ G,幺元 e∈ G,因为
x=e?x?e-1 由 R定义得 <x,x>∈ R，所以 R自反。
b)证 R对称,任取 x,y∈ G,设有 <x,y>∈ R,
由 R定义得 ?z∈ G,使得 y=z?x?z-1,于是有：
z-1?y?z= z-1?(z?x?z-1)?z,
z-1?y?z= (z-1?z)?x?(z-1?z),所以 z-1?y?(z-1) -1 =x
因 z-1∈ G，所以有 <y,x> ∈ R,所以 R对称。
c)证明 R传递,任取 x,y,z∈ G,设有 <x,y>∈ R,<y,z>∈ R
由 R定义得 ?z1,z2∈ G,使得 y=z1?x?z1-1,z=z2?y?z2-1,
于是有 z=z2?y?z2-1 = z2?(z1?x?z1-1)?z2-1
= (z2?z1)?x?(z1-1?z2-1)=(z2?z1)?x?(z2?z1)-1 因
z2?z1∈ R,∴ <x,z>∈ R,∴ R传递。 ∴ R是 G上等价关系。
*2.令上述 <G,?>为 <N6,+6>时,求商集 N6/R.
N6={0,1,2,3,4,5}
R= {<x,y>| ?z∈ N6,使得 y=z?x?z-1 },
<x,y>∈ R??z(y=z?x?z-1)??z(y?z=z?x)
按照上述表达式得关系 R图如下,
因此商集 N6/R={{0},{1},{2},{3},{4},{5}}
2?
0? ?3
5? ?4
* 第七章 格与布尔代数
1.掌握格的定义,了解格的性质,
2.会判断格,分配格,有补格和布尔格,
3.重点掌握两个元素的布尔代数的性质 (10个 ).
4.会写两个元素的布尔表达式的范式,(实质是第一章的主
析取和主合取范式 ).
一,掌握格的定义
1,格的定义
<A,≤>是偏序集，如果任何 a,b∈ A,使得 {a,b}都有最大
下界和最小上界，则称 <A,≤>是格。
2,由格诱导的代数系统
设 <A,≤>是格,在 A上定义二元运算 ∨ 和 ∧ 为,?a,b∈ A
a∨ b=LUB {a,b} {a,b}的最小上界,Least Upper Bound
a∧ b=GLB {a,b} {a,b}的最大下界,Greatest Lower Bound
称 <A,∨,∧ >是由格 <A,≤>诱导的代数系统, (∨ -并,∧ -交 )
二,格的性质
<A,∨,∧ >是由格 <A,≤>诱导的代数系统。 ?a,b,c,d∈ A
1,a≤a∨ b b≤a∨ b a∧ b≤a a∧ b≤b
2.如果 a≤b,c≤d,则 a∨ c≤b∨ d,a∧ c≤b∧ d。
推论,在一个格中，任何 a,b,c∈ A，如果 b≤c，则
a∨ b≤a∨ c,a∧ b≤a∧ c。 此性质称为 格的保序性 。
3,∨ 和 ∧ 都满足 交换律 。即 a∨ b=b∨ a,a∧ b=b∧ a。
4,∨ 和 ∧ 都满足 幂等律 。即 a∨ a=a a∧ a=a
5,∨ 和 ∧ 都满足 结合律 。即
(a∨ b)∨ c =a∨ (b∨ c), (a∧ b)∧ c =a∧ (b∧ c) 。
6,∨ 和 ∧ 都满足 吸收律 。即 a∨ ( a∧ b) =a,a∧ (a∨ b) =a。
7,<A,∨,∧ >是代数系统，如果 ∨ 和 ∧ 是 满足吸收律 的二
元运算，则 ∨ 和 ∧ 必满足幂等律 。
8,∨ 和 ∧ 不 满足 分配律 。但有分配 不等式,
a∨ (b∧ c)≤ (a∨ b)∧ (a∨ c),
(a∧ b)∨ (a∧ c)≤a∧ (b∨ c) 。
9,a≤b? a∨ b=b ? a∧ b=a
三,格的同态,同构
1.设 <A1,≤1> 和 <A2,≤2>是两个格，由它们诱导的代数系
统分别是 <A1,∨ 1,∧ 1>和 <A2,∨ 2,∧ 2>，如果存在映射
f:A1?A2 使得对任何 a,b∈ A1,
f(a∨ 1b)=f(a)∨ 2f(b)
f(a∧ 1b)=f(a)∧ 2f(b)
则称 f是 <A1,∨ 1,∧ 1>到 <A2,∨ 2,∧ 2>的同态映射。
也称 <f(A1),≤2>是 <A1,≤1> 的同态像。
如果 f 是双射的，就称 f是 <A1,∨ 1,∧ 1>到 <A2,∨ 2,∧ 2>，
的格同构，也称格 <A1,≤1> 和 <A2,≤2>同构。
两个格同构,两个格的图同构,
2.格同态和同构的保序性
四,分配格
1.定义 <A,∨,∧ >是由格 <A,≤>诱导的代数系统。如果
对 ?a,b,c∈ A，有
a∨ (b∧ c) =(a∨ b)∧ (a∨ c),
a∧ (b∨ c)= (a∧ b)∨ (a∧ c)
则称 <A,≤>是 分配格。
2,二个重要的五元素非分配格,
3.分配格的判定,
一个格是分配格的 充分且必要条件 是在该格中没有任何
子格与上述两个五元素非分配格之一同构,
4,分配格的性质
1),定理 7-2.1,在格中，如果 ∧ 对 ∨ 可分配，则 ∨ 对 ∧ 也
可分配,反之亦然。
2),定理 7-2.2,所有链均为 分配格。
? 3
? 1
? 30
2? ? 5
? d
? e
? a
b?
? c
3),设 <A,≤>是分配格，对任何 a,b,c∈ A,如果有
a∧ b=a∧ c 及 a∨ b=a∨ c 则必有 b=c,
五,有界格
有界格定义：如果一个格存在 全上界 1与全下界 0，则
称此格为有界格,
六,有补格
1,元素的补元,
设 <A,≤>是个有界格,a∈ A,如果存在 b∈ A,使得
a∨ b=1 a∧ b=0 则称 a与 b互为补元。
2,有补格的定义,一个有界格中，如果每个元素都有补
元，则称之为有补格。
3.在有界分配格中，如果元素有补元，则补元是唯一的。
七, 布尔格 如果一个格既是分配格又是有补格，则称
之为布尔格。布尔格中每个元素都有唯一补元。
练习题,给定集合如下：
A1={1,2,4,8,16} A2={1,2,3,5,6,10,15,30}
A3={1,2,3,5,30} A4={1,2,3,5,10,15,30}
A5={1,2,3,4,9,36} 令 ≤ 是上述集合上的整除关系。
1.请分别画出各个偏序集 <Ai,≤> 的哈斯图 (i=1,2,3,4,5)
1。
2。
4。
8。
16。
2?
?9
36?
4?
1?
?3
30。
3。
１ 。
2。 5 。
10。 15 。6。
<A2,≤><A
1,≤>
3。
１ 。
5。
30。
２ 。
<A3,≤>
30。
3。
１ 。
2。 5。
10。 １ 5。
<A4,≤> <A5,≤>
2.用, Y”表示, 是,,用, N”表示, 否, 填下表。
<A1,≤> <A 2,≤> <A 3,≤> <A 4,≤> <A 5,≤>
分配格
有补格
布尔格
Y Y N N N
N Y Y N Y
N Y N N N
1。
2。
4。
8。
16。
2?
?9
36?
4?
1?
?3
30。
3。
１ 。
2。 5 。
10。 15 。6。
<A2,≤><A
1,≤>
3。
１ 。
5。
30。
２ 。
<A3,≤>
30。
3。
１ 。
2。 5。
10。 １ 5。
<A4,≤> <A5,≤>
八, 布尔代数
1.定义
由布尔格 <B,≤>诱导的代数系统 <B,∨,∧,ˉ> 称之
为布尔代数。其中 ˉ 是取补元运算。
如果 A是有限集合，则称它是有限布尔代数。
2.布尔代数性质
设 <B,∨,∧,ˉ> 布尔代数,任意 x,y,z∈ B,有
⑴交换律 x∨ y=y∨ x x∧ y=y∧ x
⑵ 结合律 x∨ (y∨ z)=(x∨ y)∨ z x∧ (y∧ z)=(x∧ y)∧ z
⑶ 幂等律 x∨ x=x x∧ x=x
⑷ 吸收律 x∨ (x∧ y)=x x∨ (x∧ y)=x
⑸ 分配律 x∨ (y∧ z)=(x∨ y)∧ (x∨ z)
x∧ (y∨ z)=(x∧ y)∨ (x∧ z)
⑹ 同一律 x∨ 0=x x∧ 1=x
⑺ 零律 x∨ 1=1 x∧ 0=0
⑻ 互补律 x∨ =1 x∧ =0
⑼ 对合律
⑽底－摩根定律
3.布尔代数的同构
1),定义,令 <B1,∨ 1,∧ 1,ˉ>和 <B2,∨ 2,∧ 2,~>是两个布尔
代数，如果存在映射 f:B1?B2,对任何 a,b∈ B1,有
f(a∨ 1b)=f(a)∨ 2f(b)
f(a∧ 1b)=f(a)∧ 2f(b)
f( )=
则称 f是 <A1,∨ 1,∧ 1>到 <A2,∨ 2,∧ 2>的同态映射。
a
~f(a)
x x
2),原子
定义 1,设设 <B,∨,∧,ˉ> 布尔代数,元素 a∈ B,a≠0,对
任何元素 x∈ B,有 x∧ a=a,或 x∧ a=0,则称 a是原子。
定义 2:<A,≤>是布尔格,在 <A,≤>的 哈斯图中称盖住全
下界 0的元素为原子。
1。
e。
0。
d。 f。
b。 c。a。
0。
1。
? 0
?1
a? ? b
3),有关引理
⑴ 定理 7-3.2设 a,b是布尔代数 <B,∨,∧,ˉ> 中的原子,如果
a≠b,则 a∧ b=0,(如果 a∧ b≠0,则 a=b)
⑵ 定理 7-3.3设 a,b1,b2…b n是 布尔代数 <B,∨,∧,ˉ> 中的原
子,则 a≤b1∨ b2∨ … ∨ bn的 充分且必要条件为 对于某个 i
(1≤i≤n),有 a=bi.
⑶ 定理 7-3.4 设 b是有限布尔代数 <B,∨,∧,ˉ> 中的 非 0元素，
则必存在原子 a,使得 a≤b.
⑷ 定理 7-3.5 有限布尔代数中,b∧ =0,当且仅当 b≤c。
⑸ 定理 7-3.6设 <B,∨,∧,ˉ> 是有限布尔代数,b非 0元素，
a1,a2 …a k是 B中满足 aj≤b的所有原子 (j=1,2,…k),则
b＝ a1∨ a2 ∨ … ∨ ak且除原子次序不同外，
上述表达式是唯一的。
⑹ 定理 7-3.7 在布尔代数 <B,∨,∧,ˉ> 中,对 B中任何原子 a
和任何非 0元素 b,a≤b和 a≤ 两式中有且仅有一个成立。
⑺ 定理 7-3.8 (Stone定理 )设 <B,∨,∧,ˉ> 是有限布尔代数，
M是 B中所有原子构成的集合，则
<B,∨,∧,ˉ> 与 <P(M),∪,∩,~>同构。
⑻ 推论 1,任何有限布尔代数的元素个数为 2n (n=1,2,3,…)
因为 |P(M)|= 2n
推论 2,两个有限布尔代数同构的充分且必要条件是元素
个数相同。
4,布尔表达式概念
1).定义, 设 <B,∨,∧,ˉ> 是布尔代数，其上的布尔表达式
递归定义如下：
(1)B中任何元素是个布尔表达式。
(2)任何变元 x是个布尔表达式,
(3)如果 E1,E2是个布尔表达式,则,(E1∧ E2),(E1∨ E2)也
是布尔表达式。
(4)有限次地应用规则 1)--3),得到的符号串都是布尔表达式。
1E
2),布尔表达式的范式
1,有两个元素的布尔代数的布尔表达式的范式,
<{0,1},∨,∧,ˉ> 是两个元素的布尔代数
1),析取范式
(1).小项, 含有 n个变元的小项形式为,
其中
例如 都是小项,
(2).布尔表达式的析取范式,
含有变元 x1,x2,…,x n 的布尔表达式 E(x1,x2,…x n),如果写成
如下形式, A1∨ A2∨,..∨ Am(m≥1)
其中每个 Ai (1≤i≤m)都是有 n个变元的小项, 则称此式是
E(x1,x2,…x n)的析取范式,
nxxx ~.,,~~ 21 ???
）（或 nixxxx iiii ???? 1~~
)(),()( 321321321 xxxxxxxxx ??????
2),合取范式
(1),大项,含有 n个变元的大项形式为,
其中
例如 都是大项,
(2).布尔表达式的合取范式,
含有变元 x1,x2,…,x n 的布尔表达式 E(x1,x2,…x n),如果写成
如下形式, A1∧ A2∧,.,∧ Am (m≥1)
其中每个 Ai (1≤i≤m)都是有 n个变元的大项, 则称此式是
E(x1,x2,…x n)的合取范式, 例如,
3),析取范式与合取范式的写法,
方法 1:列真值表
方法 2:表达式的等价变换,
nxxx ?.,,?? 21 ???
）（或 nixxxx iiii ???? 1??
)(),()( 321321321 xxxxxxxxx ??????
)()()(),,( 321321321321 xxxxxxxxxxxxE ?????????
方法 1,用真值表求析取范式,
先介绍小项的性质,以两个变元 x1,x2为例
每一组赋值,有且仅有一个小项为 1.
根据一组赋值,求值为 1的小项, 如果变元 x,被赋值为 0,则
在此小项中,x以 形式出现 ; 如果变元 x,被赋值为 1,则在
此小项中,x以原形 x形式出现,
求 E(x1,x2,…x n)的析取范式,先列出它的真值表,找出表中
每个 1对应的小项,然后用 ∨ 连接上述小项,
2121212121 xxxxxxxxxx ????
0 0 1 0 0 0
0 1 0 1 0 0
1 0 0 0 1 0
1 1 0 0 0 1
例如,求 布尔代数 <{0,1},∨,∧,ˉ> 上 的布尔表达式
E(x1,x2,x3)=x1∧ (x2∨ ) 的析取范式,
E(x1,x2,x3)=(x1∧ ∧ )∨ (x1∧ x2∧ )∨ (x1∧ x2∧ x3)
x3ˉ
x1 x2 x3 E (x1,x2,x3)
0 0 1 0
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 1
0 0 0 0
1 1 1 1
x3ˉ x3ˉx2ˉ
方法 1,用真值表求合取范式,
先介绍大项的性质,以两个变元 x1,x2为例
每一组赋值,有且仅有一个大项为 0.
根据一组赋值,求值为 0的大项, 如果变元 x,被赋值为 1,则
在此小项中,x以 形式出现 ; 如果变元 x,被赋值为 0,则在
此小项中,x以原形 x形式出现,
求 E(x1,x2,…x n)的合取范式,先列出它的真值表,找出表中
每个 0对应的大项,然后用 ∧ 连接上述大项,
2121212121 xxxxxxxxxx ????
0 0 0 1 1 1
0 1 1 0 1 1
1 0 1 1 0 1
1 1 1 1 1 0
例如,求 布尔代数 <{0,1},∨,∧,ˉ> 上 的布尔表达式
E(x1,x2,x3)
=x1∧ (x2∨ )
的合取范式,
E(x1,x2,x3)=(x1∨ x2∨ x3)∧ (x1∨ x2∨ ) ∧ (x1∨ ∨ x3)∧
(x1∨ ∨ ) ∧ ( ∨ x2∨ )
x3ˉ x1 x2 x3 E (x1,x2,x3)
0 0 1 0
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 1
0 0 0 0
1 1 1 1
x3ˉ x2ˉ
x3ˉ x1ˉx2ˉ x3ˉ
方法 2,用表达式的等价变换求析取范式,
E(x1,x2,x3)=x1∧ (x2∨ ) =(x1∧ x2)∨ (x1∧ )
=(x1∧ x2∧ (x3∨ ))∨ (x1∧ (x2∨ )∧ )
=(x1∧ x2∧ x3)∨ (x1∧ x2∧ )∨ (x1∧ x2∧ )∨ (x1∧ ∧ )
=(x1∧ x2∧ x3)∨ (x1∧ x2∧ )∨ (x1∧ ∧ )
结果与前相同,
用表达式的等价变换求合取范式,
E(x1,x2,x3)=x1∧ (x2∨ )
=(x1∨ (x2∧ )∨ (x3∧ ))∧ ((x1∧ )∨ x2∨ )
=(x1∨ x2∨ x3 )∧ (x1∨ x2∨ )∧ (x1∨ ∨ x3 )∧ (x1∨ ∨ )
∧ (x1∨ x2∨ )∧ ( ∨ x2∨ )
=(x1∨ x2∨ x3 )∧ (x1∨ x2∨ )∧ (x1∨ ∨ x3 )∧ (x1∨ ∨ )
∧ ( ∨ x2∨ )
x3ˉ x3ˉ
x2ˉ
x2ˉ
x3ˉ
x3ˉ
x3ˉx3ˉ
x3ˉ
x3ˉ
x2ˉ
x3ˉ
x3ˉ
x3ˉx2ˉ x1ˉ x3ˉ
x3ˉx2ˉ
x1ˉ x3ˉ
x3ˉ x2ˉ
x3ˉ
x3ˉx2ˉ
x1ˉ x3ˉ
x3ˉ x2ˉ
*2,一般的布尔代数的布尔表达式的范式,
< B,∨,∧,ˉ> 是布尔代数,含有变元 x1,x2,…,x n 的布尔表
达式 E(x1,x2,…x n),
1),小项, 是由 n个变元和 B中元素构成的如下形式,称为小
项,
其中
Cδ1δ2...δn为 B中元素,我们称之为小项的系数,
例如 B={0,1,a,b},下面就是 E(x1,x2,x3)中的小项,
2),布尔表达式 E(x1,x2,...xn)的 析取范式,
含有变元 x1,x2,…,x n 的布尔表达式 E(x1,x2,…x n),如果写成
如下形式, A1∨ A2∨,..∨ Am(m≥1)
其中每个 Ai (1≤i≤m)都是有 n个变元的小项, 则称此式是
E(x1,x2,…x n)的析取范式,
nxxxC n ~...~~ 21.,,21 ???????
）（或 nixxxx iiii ???? 1~~
)1(),(),( 321321321 xxxxxxbxxxa ?????????
E(x1,x2,…x n)写析取范式形式,
)]1,1,.,,1,1(...[
)]0,1,.,,1,1(...[
...)]1,0,.,,0,0(...[
)]0,.,,0,0(...[
.,,,
))]}.,,,,1,1([)].,,,,0,1({[
))]}.,,,,1,0([)].,,,,0,0({[
))]}.,,,,1,1(()).,,,,0,1([({
))]}.,,,,1,0(()).,,,,0,0([({
)),.,,,,1((),.,,,,0((),.,,,(
21
21
121
21
321321
321321
32321
32321
212121
Exxx
Exxx
Exxxx
Exxx
xxExxxxExx
xxExxxxExx
xxExxxExx
xxExxxExx
xxExxxExxxxE
n
n
nn
n
nn
nn
nn
nn
nnn
????
?????
???????
??????
?
?????
???????
????
??????
????
?
类似地,E(x1,x2,…x n)的合取范式为,
E(x1,x2,…x n)=(x1∨ x2∨,..∨ xn ∨ E(0,0,…,0)) ∧
(x1∨ x2∨,..∨ xn-1∨ ∨ E(0,0,…0,1)) ∧,.,∧
( ∨ ∨,..∨ ∨ xn∨ E(1,1,…,1,0)) ∧
( ∨ ∨,..∨ ∨ E(1,1,…,1))
其中
E(0,0…,0),E(0,0,…0,1),…,E(1,1,…1,0) 和 E(1,1,…,1)
就是所谓的“系数”,
实际上,求 E(x1,x2,…x n)的析取或者合取范式时,就是求这
些“系数”,
xnˉ
x1ˉ x2ˉ
xnˉ
x1ˉ x2ˉ
xn-1ˉ
已知 <B,∨,∧,ˉ>是布尔代数,其中 B={0,a,b,1}
分别求出下面布尔表达式的析取范式和合取范式,
解, 先求四个系数,
析取范式为,
))(())((),( 212121 axxbxxxxE ??????
0)0()0())1(1())11(()1,1(
0)00()1())0(1())01(()0,1(
)1()0())1(0())10(()1,0(
)01()0())0(0())00(()0,0(
?????????????
???????????
???????????
???????????
abababE
babE
bababE
bbabE
)()(
)0()0()()(
)1,1(())0,1((
))1,0(())0,0((),(
2121
21212121
2121
212121
bxxbxx
xxxxbxxbxx
ExxExx
ExxExxxxE
??????
????????????
?????
???????
合取范式为,
)0()0()()(
))1,1(())0,1((
))1,0(())0,0((),(
21212121
2121
212121
????????????
?????
???????
xxxxbxxbxx
ExxExx
ExxExxxxE
第八章 图论
1.掌握图的基本概念,(特别注意相似的概念 )
2.熟练掌握图中关于结点度数的定理, (会应用 )
3.无向图的连通性的判定,连通分支及连通分支数的概念,
4.有向图的可达性,强连通,单侧连通和弱连通的判定, 求强
分图,单侧分图和弱分图,
5.会求图的矩阵,
6.会判定欧拉图和汉密尔顿图,
*7.会判定平面图,掌握欧拉公式,
*8.了解对偶图,
9.掌握树的基本定义,v和 e间的关系式,会画生成树,会求最
小生成树,根树的概念,完全 m叉树的公式,会画最优树,
*会设计前缀码,
一,图的概念
图的定义,有向边,无向边,平行边,环
邻接点,邻接边,孤立结点
有向图,无向图,简单图,混合图,零图,平凡图,多重图,
完全图,子图,生成子图,补图,
结点的度,结点的出度,结点的入度,
图的最大度 Δ(G),最小度 δ(G),
图所有结点度数总和与边的关系,出度和与入度和关系
图的同构
二,路与回路
路,回路,迹,闭迹,通路,圈
无向图的连通性,连通图,连通分支,连通分支数 W(G),
点割集,割点,点连通度 k(G),
边割集,割边 (桥 ),边连通度 λ(G)
结点间的距离,图的直径
有向图的连通性,可达性,
强连通,单侧连通,弱连通,强分图,单侧分图,弱分图,(会
求这些分图 )
三,图的矩阵
邻接矩阵 A:结点与结点之间的邻接关系矩阵,
根据邻接矩阵判断,各结点的度,有向图结点出,入度,
由 Ak可以求一个结点到另一个结点长度为 k的路条数,
可达矩阵 P:结点 u到结点 v的可达性的矩阵,
用 P可以判定,各结点的度, 有向图的强分图,
关联矩阵 M:是结点与边的关联关系矩阵,
用 M判定,各结点的度
四,欧拉图与汉密尔顿图 (会判定 )
欧拉路,欧拉回路,欧拉图,
判定,有欧拉路的充要条件,无或有两个奇数度的结点,
有欧拉回路的充要条件,所有结点度数均为偶数,
汉密尔顿路,汉密尔顿回路,汉密尔顿图
汉密尔顿图的判定,
必要条件,V的任何非空子集 S,有 W(G-S)≤|S|
充分条件,每对结点的度数和 ≥|V| =n
*五,平面图
平面图的定义,平面的边界,
欧拉公式, v-e+r=2
判定,必要条件, e≤3v-6
*充要条件,G不含与 K5或 K3,3在 2度结点内同构子图,
*六,对偶图与着色
会画对偶图,会对图正常着色,
*七, 二部图 作为一般了解,掌握 K3.3
八,树与生成树
树的定义,6个定义,其中最主要的是连通无回路,e=v-1
分支结点,叶结点
会求最小生成树
九, 根树
m叉树,完全 m叉树,(m-1)i=t-1
会画最优树,*会设计前缀码
练习题
1.请画出 K5 的所有不同构的生成树。
解, K5的生成树 T边数为 4,T的度数和为 8
2.一棵完全二叉树有 e条边,t个叶结点，请推导出 e与 t
的关系式。
解,根据完全 m叉树的公式,(m-1)i=t-1
得分支结点数 i=t-1 又根据树中 e=v-1 v是结点数,
所以 e=(i+t)-1=t-1+t-1=2t-2
?
? ?
? ?
?
? ?
? ?
?
? ?
? ?
?
? ?
? ?
(11114) (11123) (11222)
3.今有 a,b,c,d,e,f,g七个人,已知下列事实,
a:会讲英语, b:会讲英语和汉语,
c:会讲英语,意大利语和俄语 d:会讲日语和汉语,
e:会讲德语和意大利语 f:会讲法语,日语,俄语
g:会讲法语和德语,
试问能否将这七个人适当安排座位,使得每个人都能和他
两边的人 直接交谈?若能,请给予安排,若不能,说明理由,
解, 以 a,b,c,d,e,f,g为结点,如果两个
人之间讲同一种语言,则它们之间
连一条直线,得到右图,
从此图中找到 H回路, abdfgeca
按照此回路坐成一个圆圈,就可以
使得每个人都可以和它两边的人直接交谈,
e?
a?
?b
?c
?d
g?
f?
4,下面序列哪些可以构成一个无向连通图的结点度数序
列?哪些不能?哪些可以构成连通简单图?哪些可能构成
欧拉图?哪些可能构成汉密尔顿图?哪些可能是完全图?
哪些可能是树?如果能,请画出一个那样的图, 如果不能
请说明原因,
a.(1,2,3,3) b.(3,3,3,3) c.(1,1,1,1,2,4)
d.(2,3,3,4,4) e.(2,3,4,4,5) f.(2,2,2,2,4)
解,a.(1,2,3,3) 不能构成 无向连通图的结点度数序列,
因为此序列中有三个奇数,不附和握手定理,
b.(3,3,3,3) 可以是个完全图 K3,是个 H图,
c.(1,1,1,1,2,4) 可以是棵树,
d.(2,3,3,4,4) 构成 无向连通图的
结点度数序列,是个 H图,
??
? ?
? ? ?? ??
??
? ?
?
e.(2,3,4,4,5)可构成连通图的结点序列,但不是简单图,5个
结点中有一个结点度为 5,所以不是有环,就是有平行边,
f.(2,2,2,2,4)是个欧拉图,
??
? ?
?
??
? ?
?
??
? ??
模 拟 试 题 (网络学院 ) 2002.1
离 散 数 学 试 卷
班级, 学号 姓名,
总分 1 2 3 4 5 6 7 8 9 10
一,(12分 )试将下面命题符号化。
1.仅当天不下雨且我有时间，才上街。
2.如果小张出差，那么小王和小李两人中要有一个出差。
3.每个大学生都爱好一些文体活动。
(S(x):x是大学生,L(x,y):x爱好 y,C(x):x是文娱活动，
P(x):x是体育活动。 )
4.没有大学生不懂外语。 ( S(x):x是大学生,K(x,y):x
懂得 y,F(x):x是外语。 )
二,(6分 )写出下面命题公式 (P→Q)→P 的主合取范式。
三,(6分 )求下面谓词公式的真值。要求有解题的过程。
?x(P?Q(x))∨ R(a),其中 P:2>1,Q(x):x≤3,R(x):x>5,
a:5,论 域 为 {-2,6}.
四,(6分 )令全集 E={Φ,{Φ}},P(A)表示 A的幂集,分别计算,
1,P(Φ)?P({Φ})
2,P(A)?P(~A)
3,P(E)-P(~{{Φ}})
五,(12分 )用谓词逻辑推理证明下面推理的有效性。
（要求按照谓词逻辑推理格式，书写推理过程。）
六,(16分 )已知 R1,R2是集合Ａ上的等价关系，问 R1∪R 2、
R1∩R 2, R1-R2, r((A× A)-R1)中哪些是 A上的等价关
系？如果不是说明理由,或举反例。如果是请给予证明
七,(10分） R是实数集合，给定 R上的五个关系如下,
R1={<x,y>|x=y2} R2={<x,y>|y=x+6}
R3={<x,y>|y=(x-1)-1} R4={<x,y>|y=2x}
R5={<x,y>|x2+y2=4}
上述五个关系中，哪些是从 R到 R的函数。如果是函数，
说明它是属于什么类型的（指满射、入射、双射）。
如果不是函数，说明理由 。
”表示否定其中,????????
???????
))()(())()((
) ) ),()(()(() ) ),()(()((
xBxAxxDxAx
xDxCxAxxCxBxAx
八,(12分 )给定集合Ｇ＝ {x|x是有理数且 x≠1},在Ｇ上
定义二元运算 *如下：
对任何 a,b∈ Ｇ a*b=a+b-ab
求证 <Ｇ,*>是个交换群。
九,(12分 )
1.请画出 K5 的所有不同构的生成树。
2.一棵完全二叉树有 e条边,t个叶结点，请推导出 e与 t
的关系式。
*3.今有 a,b,c,d,e,f,g七个人,已知下列事实,
a:会讲英语, b:会讲英语和汉语,
c:会讲英语,意大利语和俄语 d:会讲日语和汉语,
e:会讲德语和意大利语 f:会讲法语,日语,俄语
g:会讲法语和德语,
试问能否将这七个人适当安排座位,使得每个人都能和他
两边的人 直接交谈?如果能,请给予安排,如果不能,说明
理由,
*4,下面序列哪些可以构成一个无向连通图的结点度数序
列?哪些不能?哪些可以构成连通简单图?哪些可能构成
欧拉图?哪些可能构成汉密尔顿图?哪些可能是完全图?
哪些可能是树?如果能,请画出一个那样的图, 如果不能
请说明原因,
a.(1,2,3,3) b.(3,3,3,3) c.(1,1,1,1,2,4)
d.(2,3,3,,4,4) e.(2,3,4,4,5) f.(2,2,2,2,4)
*5 给定一组权值,1,3,5,2,7,1,8,6,9,2,画最优树。
十,(10分 )给定集合如下：
A1={1,2,4,8,16} A2={1,2,3,5,6,10,15,30}
A3={1,2,3,5,30} A4={1,2,3,5,10,15,30}
A5={1,2,3,4,9,36} 令 ≤ 是上述集合上的整除关系。
1.请分别画出各个偏序集 <Ai,≤> 的哈斯图 (i=1,2,3,4,5)
2.用, √, 表示, 是,,用, ×,表示, 否, 填下表。
<A1,≤> <A 2,≤> <A 3,≤> <A 4,≤> <A 5,≤>
分配格
有补格
布尔格
补充题型
一,填空
1.设 A,B是集合,且 |A|=m,|B|=n,则 |A× B|=( ),可以构造
( )个从 A到 B的二元关系, 其中有 ( )个是从 A到 B的
函数, 在 ( )条件下,有从 A到 B的入射函数,有 ( )
个入射函数 ; 在 ( )条件下,有从 A到 B的双射函数,
有 ( )个双射函数,
2.A(P,Q,R)是个永真的命题公式,则 A(P,Q,R)的主析取范
式中有 ( )个小项,
3.A(P,Q,R)是个命题公式,如果 A(P,Q,R)的主析取范式中
有 k个小项,则它的主合取范式中有 ( )个大项,
4.一个图是欧拉图,当且仅当它的所有结点的度 ( ).
5.一棵完全 m叉树,有 t个叶结点,则它有 ( )分支结点,
二,判断下面命题的真值,并说明理由,或举反例,
1,R和 S都是 A上关系，
a) R和 S都自反，则 R?S也 自反。
b) R和 S都反自反，则 R?S也反自反。
c) R和 S都对称，则 R?S也对称。
d) R和 S都传递，则 R?S也传递。
2.如果 A∈ B,B?C，则 A?C。
3,(A-B)∪ (A-C)=A 当且仅当 B=C=Φ.
4,含有三个以上元素的链,不是有补格,
5,所有链都是分配格,
6.不是所有格都是有界格,
7.任何两个结点都有边相关联的无向图是完全图,
8.圈就是回路,回路也是圈,
三,给定集合 A={1,2,3}，在 A上定义五个关系如下：
MR1= R2：
R3 ={<1,1>,<1,2>,<2,1>,<2,2>,<3,3>}
R4 =A× A （完全关系） R5=φ （空关系）
1,求复合关系 R1?R2c,2.求 R2的传递闭包 t(R2).
3.用, ∨, 表示, 是,, 用, ×,表示, 否,,填下
表：
自反的 反自反的 对称的 反对称的 传递的
R1
R2
R3
R4
R5
?1
2? ?3
111
011001
4.上述五个关系中，哪些是等价关系？哪些是偏序关系？
哪些是 A到 A的函数?
如果是等价关系,请写出它对 A的商集。如果是偏序关系,
请画出它的哈斯图。如果是函数,请指出它的类型,
四, 名词解释
n元谓词,原子谓词公式,论域,
群中元素的阶,循环群,布尔格,拉格朗日定理,
迹,圈,通路,生成子图,
图 G的 Δ(G),δ(G),k(G),λ(G),W(G),
平面图的欧拉公式,
零图,平凡图,简单图,
*五,设 X={1,2,3} Y={1,2},在 X的幂集 P(X)上定义二元关
系 R如下, 对于任何 A,B∈ P(X),
ARB 当且仅当 A?Y=B?Y
1.画出关系 R的有向图,
2.R是等价关系吗?如果是,请写出商集 P(X)/R,如果不是请
说明原因,
重点掌握的习题,(网络学院 )
1.P8(3),P12(5)(7),P19(7)d)g),(8)c),P23(8)ef,P39(4)d,
2.P60(2),P66(3)b,P78(3),
3.P86(4)(7),P94(5)(7)(9),
4.P109(2),P113(1)(3)(4),P118(1)(2)(3)(5),P127(1),P134(1)
(2)(4)(7),P145(1)(6)(7),
5.P151(1)(3)(5)(6),P156(3),
6.P184(1),P190(3)(5),P197(3),P200(1),P211(3)P221(2)(11)
7.P242(1)(2),P248(2),P252(1),P269(1)(3)
8.P279(2)(5),P287(3)(7),P300(3),P311(1)(2)(3)(6),P317(5)
P321(1)(3),P327(2)(3)(6),P337(1)(2)(3)(5)(8)
9.前边的 模拟题以及补充题,
预 祝
同 学 们 取 得
优异成绩
期 末 总 复 习
复 习 时 注 意
准确掌握每个概念
灵活应用所学定理
注意解题思路清晰
证明问题时,先用反向思维 (从结
论入手 )分析问题,再按正向思维
写出证明过程,
全书知识网络,
图
论
篇
<{T,F},?,?,?,?,?>
<p(E),~,∩,∪,－,?>
格与布尔代数
半群,独异点,群,环,域
<P(A× A),~,∩,∪,－,?,?,c,r,s,t>
<YX,~,∩,∪,－,?,?,-1>
代数系统篇
n 元运算
命题逻辑
谓词逻辑
集合初步
二元关系
函 数
集合论篇
数理逻辑篇
总 复 习
复习重点 (注, 标有 *的内容,对网络学院学生不作要求 )
第一章 命题逻辑
1.联结词的定义 (含义及真值表定义 ).
2.会命题符号化,
3.永真式的证明,
4.永真蕴涵式的证明,记住并能熟练应用常用公式,
5.等价公式的证明,记住并能熟练应用常用公式,
6.会写命题公式的范式,*能应用范式解决问题,
7.熟练掌握命题逻辑三种推理方法,
第二章 谓词逻辑
1.准确掌握有关概念,
2.会命题符号化,(如 P60题 (2))
3.掌握常用的等价公式和永真蕴涵式,包括,
带量词的公式在论域内展开式,量词否定,量词辖域扩充,
量词分配公式,
4.会用等价公式求谓词公式的真值,(如 P66题 (3))
*5.会写前束范式
6.熟练掌握谓词逻辑推理,
第三章 集合论初步
1.集合的表示,幂集,全集,空集,
2.集合的三种关系 (包含,相等,真包含 )的定义及证明,
3.集合的五种运算及相关性质,
*4.应用包含排斥原理,
第四章 二元关系
1.关系的概念,表示方法,
2.二元关系的 性质的定义,熟练掌握性质的判断及证明,
3.掌握关系的复合,求逆及闭包运算 (计算方法及有关性质 )
4.掌握等价关系的判断,证明,求等价类和商集,
*4.掌握相容关系定义,简化图和简化矩阵,相容类,最大相
容类,完全覆盖,
5.偏序关系的判断,会画 Hasse图,会求一个子集的极小 (大 )
元,最小 (大 )元,上界与下界,最小上界及最大下界,
第六章 函数
1.函数的定义,
2.函数的类型,会判断,会证明,
3.会计算函数的复合 (左复合 ),求逆函数,知道有关性质,
*4.了解集合的特征函数,了解集合的基数,可数集合,
第六章 代数系统
1.掌握运算的定义,
2.熟练掌握二元运算的性质的判断及证明,
3.掌握代数系统的同构定义,会证明,了解同构性质的保持,
4.了解半群,独异点,*环和 *域的概念,
5.熟练掌握群,子群,交换群 (会证明 ),了解循环群,
*6,子群的陪集,Lagrange定理及其推论,(会应用 ).
*第七章 格与布尔代数
* 1.掌握格的定义,了解格的性质,
* 2.会判断格,分配格,有补格和布尔格,
* 3.重点掌握两个元素的布尔代数的性质 (10个 ).
* 4.会写两个元素的布尔表达式的范式,(实质是第一章的
主析取和主合取范式 ).
第八章 图论
1.掌握图的基本概念,(特别注意相似的概念 )
2.熟练掌握图中关于结点度数的定理, (会应用 )
3.无向图的连通性的判定,连通分支及连通分支数的概念,
4.有向图的可达性,强连通,单侧连通和弱连通的判定,求强
分图,单侧分图和弱分图,
5.会求图的矩阵,
6.会判定欧拉图和汉密尔顿图,
*7.会判定平面图,掌握欧拉公式,
*8.了解对偶图,
9.掌握树的基本定义,v和 e间的关系式,会画生成树,会求最
小生成树,根树的概念,完全 m叉树的公式,会画最优树,*会
设计前缀码,
总 复 习
复习重点
第一章 命题逻辑
1.联结词的定义 (含义及真值表定义 ).
2.会命题符号化,
3.永真式的证明,
4.永真蕴涵式的证明,记住并能熟练应用常用公式,
5.等价公式的证明,记住并能熟练应用常用公式,
6.会写命题公式的范式,*能应用范式解决问题,
7.熟练掌握命题逻辑三种推理方法,
第一章 命题逻辑
1.联结词
定义了六个逻辑联结词，分别是：
(1) 否定,?” (2) 合取,∧,
(3) 析取,∨, (4) 异或,”
(5) 蕴涵,?” (6) 等价,?”
要熟练掌握这五个联结词在自然语言中所表示的含义以
及它们的真值表的定义。
? ?,否定 表示“不”
? ∧,合取 表示,不但 …,而且,..”“并且”
? ∨,析取 表示,或者－可兼取的或”
?,异或 表示“或者－不可兼取的或”
? ?：蕴涵 表示“如果 …,则,..”
? ?,等价 表示“当且仅当”“充分且必要”
? 可以将这六个联结词看成六种,运算,。
?
?
联结词的定义 (包括真值表和含义 ).
特别要注意：
“或者”的二义性,即要区分给定的“或”是“可兼取的
或 ∨,还是“不可兼取的或,。
,?”的用法,它既表示“充分条件”也表示“必要条
件”,即要弄清哪个作为前件,哪个作为后件,
P Q P∧ Q P∨ Q P?Q P?Q P Q
F F F F T T F
F T F T T F T
T F F T F F T
T T T T T T F
?
?
2.会命题符号化,
例如 P:我有时间, Q:我上街, R:我在家,
表示 P是 Q的充分条件, 如果 p,则 Q,只要 P,就 Q,P?Q
表示 P是 Q的必要条件, 仅当 P,才 Q,只有 P,才 Q,Q?P
如果 P,则 Q;否则 R,(P?Q)?(?P?R)
3.永真式的证明,
方法 1.列真值表, (?R?(Q?R)??(P??Q))??P
方法 2.用公式的等价变换,化简成 T.
例如证明 (?R?(Q?R)??(P??Q))??P是永真式,
证,上式 ??(?R?(?Q?R)??(P??Q))??P(P?Q??P?Q)
?(R?(Q??R)?(P??Q))??P (公式的否定公式 )
?((R?(Q??R))?((P??Q)??P) (结合律 )
? ((R?Q)?(R??R))?((P??P)?(?Q??P) (分配律 )
?(R?Q)?(?Q??P) ?R?Q??Q??P?T (互补,同一律 )
4.永真蕴涵式的证明,记住常用的公式,
永真蕴涵式, A?B是永真式,则称
A永真蕴涵 B,(A?B)
方法 1.列真值表,
方法 2.假设前件真,推出后件真,
(即直接推理 )
方法 3.假设后件假,推出前件假,(即反证法 )
例证明 (P?(Q?R))?((P?Q)?(P?R))是永真蕴涵式,
证,假设后件 (P?Q)?(P?R)假,则 P?Q为 T,P?R为 F,于
是 P为 T,R为 F,进而又得 Q为 T,所以 Q?R为 F,所以前件
P?(Q?R)为 F,所以 (P?(Q?R))?((P?Q)?(P?R))为
永真式,
对于给定一个题,究竟是用哪种方法,原则上哪种都可以,
但是哪个方法简单,要根据具体题而定,
A B A ?B
F F T
F T T
T F F
T T T
5.等价公式的证明,记住常用的公式,
方法 1.列真值表,
方法 2.用公式的等价变换,
例如,证明 P?(Q?R)?(P∧ Q)?R
P?(Q?R)??P?(?Q?R) ? (?P??Q)?R
??(P?Q)∨ R?(P∧ Q)?R
注意,不论是证明永真蕴涵式,还是证明等价公式以及后边
的求公式的范式,命题逻辑推理,都应用 43页的公式。
必须记忆一些常用的公式 如,P43表中的
永真蕴涵式, I1,I3,I9,I10,I11,I12,I13,
等 价 公 式, E1 ~ E16,E18,E19,E20,E21,
6.命题公式的范式
1)析取范式,A1∨ A2∨,..∨ An (n≥1) Ai (i=1,2..n)是 合取式,
2)合取范式,A1∧ A2∧,..∧ An (n≥1) Ai (i=1,2..n)是 析取式,
3)析取范式与合取范式的写法,
4)小项及 小项的性质,
m3 m2 m1 m0
P Q P∧ Q P∧ ?Q ?P∧ Q ?P∧ ?Q
00 F F F F F T
01 F T F F T F
10 T F F T F F
11 T T T F F F
6)大项及其性质,
M0 M1 M2 M3
P Q P∨ Q P∨ ?Q ?P∨ Q ?P∨ ?Q
00 F F F T T T
01 F T T F T T
10 T F T T F T
11 T T T T T F
7)主析取范式, A1∨ A2∨,..∨ An (n≥1) Ai (i=1,2..n)小项,
8)主合取范式, A1∧ A2∧,..∧ An (n≥1) Ai (i=1,2..n)大项,
9).会写主析取范式和主合取范式,
求下面命题公式的范式,
A(P,Q,R)?(P∨ Q)?R
方法 1.列真值表,
主析取范式
A(P,Q,R)?(P∨ Q)?R
?(?P∧ ?Q∧ ?R )∨ (?P∧ ?Q∧ R )∨ (?P∧ Q∧ R)
∨ (P∧ ?Q∧ R )∨ (P∧ Q∧ R )
主合取范式
A(P,Q,R)?(P∨ Q)?R
?(P∨ ?Q∨ R )∧ (?P∨ Q∨ R )∧ (?P∨ ?Q∨ R)
P Q R (P∨ Q)?R
F F F T
F F T T
F T F F
F T T T
T F F F
T F T T
T T F F
T T T T
方法 2.用公式的等价变换,
主析取范式 ;A(P,Q,R)?(P∨ Q)?R
??(P∨ Q)∨ R ? (?P∧ ?Q)∨ R
? (?P∧ ?Q∧ (R∨ ?R))∨ ((P∨ ?P)∧ (Q∨ ?Q)∧ R)
? (?P∧ ?Q∧ R)∨ (?P∧ ?Q∧ ?R)∨ (P∧ Q∧ R)
∨ (P∧ ?Q∧ R)∨ (?P∧ Q∧ R)∨ (?P∧ ?Q∧ R)
?(?P∧ ?Q∧ ?R )∨ (?P∧ ?Q∧ R )∨ (?P∧ Q∧ R)
∨ (P∧ ?Q∧ R )∨ (P∧ Q∧ R )
主合取范式,A(P,Q,R)?(P∨ Q)?R
??(P∨ Q)∨ R ? (?P∧ ?Q)∨ R
? (? P∨ R )∧ (?Q∨ R)
? (? P∨ (Q∧ ?Q)∨ R )∧ ((P∧ ?P)∨ ?Q∨ R)
? (?P∨ Q∨ R )∧ (?P∨ ?Q∨ R)∧ (P∨ ?Q∨ R )
已知 A(P,Q,R)的主析取范式中含有如下小项,
m0,m3,m4,m5,m7求它的主合取范式,
解,A(P,Q,R)的主合取范式中含有大项,M1,M2,M6
A(P,Q,R)?(P∨ Q∨ ?R )∧ (P∨ ?Q∨ R)∧ (?P∨ ?Q∨ R)
* 范式的应用
如 P39习题 (7),(8),安排工作 (排课表 ),判断比赛名次,携带
工具箱,…
7.会用三种推理方法,进行逻辑推理,
会用三个推理规则,P,T,CP
例如,证明 ((A∧ B)?C)∧ ?D∧ (?C∨ D) ??A∨ ?B
1.直接推理,
⑴ ?D P
⑵ ?C∨ D P
⑶ ?C T ⑴⑵ I10 ?Q,(P∨ Q) ?P
⑷ (A∧ B)?C P
⑸ ?(A∧ B) T ⑶⑷ I12 ?Q,P?Q ??P
⑹ ?A∨ ?B T ⑸ E8 ?(P∧ Q)??P∨ ?Q
((A∧ B)?C)∧ ?D∧ (?C∨ D) ??A∨ ?B
2.条件论证,适用于结论是蕴涵式, ?A∨ ?B ? A??B
⑴ A P(附加前提 )
⑵ (A∧ B)?C P
⑶ A?(B?C) T⑵ E19
⑷ B?C T⑴⑶ I11
⑸ ?D P
⑹ ?C∨ D P
⑺ ?C T ⑸⑹ I10
⑻ ?B T ⑷⑺ I12
⑼ A??B CP
((A∧ B)?C)∧ ?D∧ (?C∨ D) ??A∨ ?B
3.反证法,
⑴ ?(?A∨ ?B) P(假设前提 )
⑵ A∧ B T⑴ E9
⑶ (A∧ B)?C P
⑷ C T ⑵ ⑸ I11
⑸ ?D P
⑹ ?C∨ D P
⑺ ?C T ⑻⑼ I10
⑻ C∧ ?C T ⑷ ⑺ I9
第二章 谓词逻辑
1.准确掌握有关概念,
2.会命题符号化,(如 P60题 (2))
3.掌握常用的等价公式和永真蕴涵式,包括,
带量词的公式在论域内展开式,量词否定,量词辖域扩充,
量词分配公式,
4.会用等价公式求谓词公式的真值,(如 P66题 (3))
*5.会写前束范式
6.熟练掌握谓词逻辑推理,
第二章 谓词逻辑
1.准确掌握有关概念,
客体,
客体变元,
谓词,
量词,
量词后的指导变元,
量词的辖域,
约束变元与自由变元,
论域,
全总个体域,
谓词公式 (WFF),
命题函数,
前束范式,
2.会命题符号化,(如 P60题 (2))
命题的符号表达式与论域有关。 当论域扩大时，需要
添加用来表示客体特性的谓词，称此谓词为 特性谓词 。
特性谓词往往就是给定命题中量词后边的那个名词。
如, 所有 自然数,..”,, 有些 大学生,..”。
? 如何添加特性谓词，这是个十分重要的问题, 这与前
边的量词有关 。
如果 前边是 全称量词, 特性谓词后边是 蕴含联结词
,→, ；
如果 前边是 存在量词, 特性谓词后边是 合取联结词
,∧, 。
另外有些命 题 里有的客体在句中没有明确的量 词,而在
写它的符号表达式 时,,必 须 把 隐 含的量 词 明确的写出来,
例如 ⑴金子闪光,但闪光的不一定都是金子,
设, G(x):x是金子, F(x):x闪光,
?x(G(x)?F(x))???x(F(x)?G(x))
?x(G(x)?F(x))??x(F(x)??G(x))
⑵ 没有大学生不懂外语,
S(x):x是大学生, F(x):x外语, K(x,y):x懂得 y.
??x(S(x)??y(F(y)??K(x,y)))
?x(S(x)??y(F(y)?K(x,y)))
⑶ 有些液体可以溶解所有固体,
F(x):x是液体,S(x):x是固体,D(x,y):x可溶解 y.
?x(F(x)??y(S(y)?D(x,y)))
⑷ 每个大学生都爱好一些文体活动。
S(x):x是大学生,L(x,y):x爱好 y,C(x):x是文娱活动，
P(x):x是体育活动,) ?x(S(x)??y((C(y)∨ P(y))?L(x,y)))
3.掌握常用的等价公式和永真蕴涵式,包括,
带量词的公式在论域内展开式,量词否定,量词辖域扩充,
量词分配公式,
设论域为 {a1,a2,....,an}，则
1),?xA(x)?A(a1)∧A(a 2)∧......∧A(a n)
2),?xB(x)?B(a1)∨B(a 2)∨......∨B(a n)
1),??xA(x)??x?A(x)
2),??xA(x)??x?A(x)
1),?xA(x)∨B ??x(A(x)∨B)
2),?xA(x)∧B ??x(A(x)∧B)
3),?xA(x)∨B ??x(A(x)∨B)
4),?xA(x)∧B ??x(Ａ (x)∧B)
5),B→ ?xA(x)??x(B→A(x))
6),B→ ?xA(x)??x(B→A(x))
7),?xA(x)→B ??x(A(x)→B)
8),?xA(x)→B ??x(A(x)→B)
1),?x(A(x)∨B(x)) ??xA(x)∨ ?xB(x)
2),?x(A(x)∧B(x)) ??xA(x)∧ ?xB(x)
3),?x(A(x)∧B(x)) ??xA(x)∧ ?xB(x)
4),?xA(x)∨ ?xB(x)??x(A(x)∨B(x))
4.会用等价公式求谓词公式的真值,(如 P66题 (3))
例 设论域为 {1,2},A(x,y):x+y=xy,求 ??x?yA(x,y)的真值,
??x?yA(x,y)??x?y?A(x,y)
??y?A(1,y)??y?A(2,y)
?(?A(1,1)??A(1,2))?(?A(2,1)??A(2,2))
?(T?T)?(T?F) ?T
*5.将下面谓词公式写成前束范式
(?xF(x,y)??yG(y)??xH(x,y)
??(??xF(x,y)??yG(y)??xH(x,y) (去 ?)
??xF(x,y) ???yG(y) ??xH(x,y) (摩根 )
??xF(x,y) ??y?G(y) ??xH(x,y) (量词否定 )
??xF(x,z) ??y?G(y) ??tH(t,z) (变元换名 )
??x?y?t((F(x,z) ??G(y) ?H(t,z)) (辖域扩充 )
6.熟练掌握谓词逻辑推理,
1).注意使用 ES,US,EG,UG的限制条件,特别是 ES,UG
2).对于同一个客体变元，既有带 ?也有带 ?的前提，去量
词时,应先去 ?后去 ?，这样 才可以特指同一个客体 c.
3).去量词时，该量词必须是公式的最左边的量词，且此
量词的前边 无任何符号,它的辖域作用到公式末尾。
下面的作法是错误的,正确作法,
⑴ ?xP(x)→ ?xQ(x) P ⑴ ?xP(x)→ ?xQ(x) P
⑵ P(c)→ ?xQ(x) US⑴ ⑵ ??xP(x)∨ ?xQ(x) T ⑴ E
或⑵ ?xP(x)→ Q(c)ES⑴ ⑶ ?x?P(x)∨ ?xQ(x) T ⑵ E
实际上 ?x的辖域扩充后 ⑷ ?x(?P(x)∨ Q(x)) T⑶ E
量词改成为 ?x ⑸ ?P(c)∨ Q(c) ES⑷
⑹ P(c)→ Q(c) T⑸ E
下面的作法是错误的,正确作法,
⑴ ??xP(x) P ⑴ ??xP(x) P
⑵ ?P(c) US⑴ ⑵ ?x?P(x) T⑴ E
实际上⑴ 中量词不是 ⑶ ?P(c) ES⑵
?x而是 ?x
⑴ ?x?yP(x,y) P ⑴ ?x?yP(x,y) P
⑵ ?xP(x,c) ES⑴ ⑵ ?yP(c,y) US⑴
令 P(x,y):y是 x的 生母，
显然 ⑵是个假命题
4).添加量词时，也要加在公式的最左边,(即新加的量词
前也无任何符号 ！！ )且其辖域作用到公式的末尾。
例如下面作法是错误的, ⑴ ?xP(x)→ Q(c) P
⑵ ?xP(x)→ ?yQ(y) EG⑴
例如,证明下面推理的有效性,
证明,⑴ ?x(A(x)∧ ?D(x)) P
⑵ A(a)∧ ?D(a)) ES ⑴
⑶ A(a) T ⑵ I
⑷ ?D(a)) T ⑵ I
⑸ ?x(A(x)→(B(x)→ ?C(x))) P
⑹ A(a)→(B(a)→ ?C(a)) US ⑸
⑺ B(a)→ ?C(a)) T ⑶⑹ I
⑻ ?x(A(x)→(C(x)∨D(x) )) P
⑼ A(a)→(C(a)∨D(a) )) US⑻
⑽ C(a)∨D(a) T ⑶⑼ I
⑾ C(a) T ⑷⑽ I
⑿ ?B(a) T ⑺⑾ I
⒀ A(a)∧ ?B(a)) T ⑶⑿ I
⒁ ?x(A(x)∧ ?B(x)) EG ⒀
”表示否定其中,????????
???????
))()(())()((
) ) ),()(()(() ) ),()(()((
xBxAxxDxAx
xDxCxAxxCxBxAx
第三章 集合论初步
1.集合的表示,幂集,全集,空集,
2.集合的三种关系 (包含,相等,真包含 )的定义及证明,
3.集合的五种运算及相关性质,
*4.应用包含排斥原理,
第三章 集合论初步
基本概念,集合与元素,子集与真子集,空集,全集,幂集,
并集,交集,相对补集 (差集 ),绝对补集 (补集 )
1.集合的表示,元素与集合的属于关系 ∈,
集合的三种表示方法,
枚举法,一一列出集合中的元素,
谓词描述法,用谓词描述集合中元素的性质,
文氏图,用一个平面区域表示,
2.集合的三种关系 (被包含,相等,被真包含 )的定义及证明,
A?B ??x(x∈ A?x∈ B)
A=B? A?B?B?A??x(x∈ A?x∈ B)
A?B?A?B?A≠B??x(x∈ A?x∈ B)??x(x∈ B?x?A)
3空集,全集,幂集
空集 φ:无元素的集合, x∈ Φ是矛盾式, (空集是唯一的 )
全集 E:包含所讨论所有集合的集合, (全集不唯一 )
x∈ E是永真式
幂 集,由 A的所有子集构成的集合,
P(A)={X|X?A} |P(A)|=2|A|
4.掌握集合的五种运算及相关性质,
A∩B={x|x∈ A∧ x∈ B} x∈ A∩B ? x∈ A∧ x∈ B
A∪ B ={x|x∈ A∨ x∈ B} x∈ A∪ B ? x∈ A∨ x∈ B
A-B ={x|x∈ A∧ x ? B} x∈ A-B ? x∈ A∧ x?B
~A =E-A={x|x∈ E∧ x?A}={x|x?A} x∈ ~A?x?A
A-B=A∩ ~B
A?B=(A-B)∪ (B-A)={x|(x∈ A∧ x?B)∨ (x∈ B∧ x?A)}
A?B=(A∪ B)-(A∩B)
例 1.已知全集 E={Φ,{Φ}},A?E,计算,
a)P({Φ})?P({Φ})=( )
b)P(A)∩P(~A)=( )
c)P(E)-P(~{{Φ}})=( )
解,a) 因为任何集合 A,都有 A?A=Φ 所以
P({Φ})?P({Φ})=Φ
b) 因为 Φ?A Φ? ~A,即 Φ∈ P(A) Φ∈ P(~A) 所以
P(A)∩P(~A)={Φ}
c) P(E)={Φ,{Φ},{{Φ}},{Φ,{Φ}}}
~{{Φ}}={Φ}
P(~{{Φ}})=P( {Φ})= {Φ,{Φ}}
P(E)-P(~{{Φ}}) )={Φ,{Φ},{{Φ}},{Φ,{Φ}}}-{Φ,{Φ}}
={{{Φ}},{Φ,{Φ}}}
例 2证明各式彼此等价。 P?Q ?(?P∨ Q)∧ (P∨ ?Q)
c)A∪ B=B,A∩B=A,A?B,~B? ~A.
证明, A∪ B=B ??x(x∈ A∪ B ?x∈ B)
??x((x?A∪ B?x∈ B)?(x∈ A∪ B?x?B))
??x(((x?A?x?B)?x∈ B)?((x∈ A?x∈ B)?x?B))
??x((x?A?x?B)?x∈ B)
??x((x?A?x∈ B)?(x?B?x∈ B))??x((x?A?x∈ B)
??x(x∈ A?x∈ B) ? A?B
??x(x∈ A?x∈ B)??x(x?B?x?A)
??x(x∈ ~B?x∈ ~A) ? ~B ?~A
由 A∪ B=B 得 A? (A∪ B)=A? B A=A? B
类似由 A∩B=A,可以推出 A∪ B=B
所以 A∪ B=B?A∩B=A 从而证得
A∪ B=B,A∩B=A,A?B,~B? ~A 彼此等价。
T
例 3 证明, (A-B)-C=A-(B∪ C)
方法 1,(A-B)-C=(A∩ ~B)∩ ~C=A∩( ~B∩ ~C)
=A∩ ~(B∪ C)=A-(B∪ C)
方法 2.任取 x∈ (A-B)-C?(x∈ A∧ x?B)∧ x?C
?x∈ A∧ ( x?B∧ x?C) ?x∈ A∧ ?( x∈ B∨ x∈ C)
?x∈ A∧ ?( x∈ B∪ C) ?x∈ A∧ x?B∪ C?x∈ A-(B∪ C)
所以 (A-B)-C=A-(B∪ C)
例 4,令全集 E为信息学院的学生的集合,C表示计算机专
业学生的集合,M表示学习了离散数学的学生的集合,D表
示学习了数据结构课学生的集合,F表示一年级的学生的
集合,用集合的关系式表达下面句子,
“学习了离散数学和数据结构课的学生,一定是计算机
专业的非一年级的学生”,
解, (M∩D)?(C∩~F)
例 4,在什么条件下，下面命题为真？
a) (A-B)∪ (A-C)=A
解,(A-B)∪ (A-C)= (A∩~B)∪ (A∩~C)=A∩(~B∪ ~C)
= A∩~(B∩C)=A-(B∩C)=A
所以满足此式的 充要条件 是,A∩B∩C= Φ
b) (A-B)∪ (A-C)=Φ
解,(A-B)∪ (A-C)= A-(B∩C)=Φ 充要条件 是,A ? B∩C
c) (A-B)∩(A-C)=Φ
解,(A-B)∩(A-C)= (A∩~B)∩(A∩~C)=A∩(~B∩~C)
= A∩~(B∪ C)=A-(B∪ C)=Φ 充要条件 是, A ? B∪ C
d) (A-B)?(A-C)=Φ
解, 因为 当且仅当 A=B, 才有 A?B=Φ
所以满足此式的 充要条件 是, A-B=A-C
*例 5,用谓词逻辑推理证明
对任何集合 A,B,C，如果有 A?B且 B?C,则 A?C。
证明, ?x(x∈ A?x∈ B)??x(x∈ B?x?A),
?x(x∈ B?x∈ C)??x(x∈ C?x?B)??x(x∈ A?x∈ C)??x(x∈ C?x?A)
⑴ ?x(x∈ A?x∈ B)??x(x∈ B?x?A) P
⑵ ?x(x∈ A?x∈ B) T ⑴ I
⑶ ?x(x∈ B?x?A) T ⑴ I
⑷ ?x(x∈ B?x∈ C)??x(x∈ C?x?B) P
⑸ ?x(x∈ B?x∈ C) T ⑷ I ⑹ x∈ A?x∈ B US ⑵
⑺ x∈ B?x∈ C US ⑸ ⑻ x∈ A?x∈ C T ⑹⑺ I
⑼ ?x(x∈ A?x∈ C) UG ⑻ ⑽ x∈ B?x?A ES ⑶
⑾ x∈ B T ⑽ I ⑿ x?A T ⑽ I
⒀ x∈ C T ⑺ ⑾ I ⒁ x∈ C?x?A T ⑿ ⒀ I
⒂ ?x(x∈ C?x?A) EG ⒁
⒃ ?x(x∈ A?x∈ C) ??x(x∈ C?x?A) T⑼⒂ I
*有 14位学生参加考试,9位同学数学得了优 ;5位同学物理
得了优 ;4位同学化学得了优 ;其中物理和数学都得优的同
学有 4人 ;数学和化学都得优的同学有 3人 ;物理和化学都得
优的同学有 3人 ;三门都得优的同学有 2人 ;问没有得到优的
有多少人?恰有两门得优的同学有多少人?
解,令 A,B,C分别表示数学、物理、化学得优同学集合,
全集为 E,于是有 |E|=14 |A|=9 |B|=5 |C|=4 |A∩B|=4
|A∩C|=3 |B∩C|=3 |A∩B∩C|=2
|A∪ B∪ C|=|A|+|B|+|C|-|A∩B|-|B∩C|-|B∩C|+ |A∩B∩C|
=9+5+4-4-3-3+2=10 于是得到优的人数是 10人,
∴ 没有得到优的人数是, 14-10=4 人
恰有两门得优的人数, (|A∩B|-|A∩B∩C|)+
(|B∩C|-|A∩B∩C|)+(|B∩C|-|A∩B∩C|)=4-2+3-2+3-2=4
第四章 二元关系
1.关系的概念,表示方法,
2.二元关系的 性质的定义,熟练掌握性质的判断及证明,
3.掌握关系的复合,求逆及闭包运算 (计算方法及有关性质 )
4.掌握等价关系的判断,证明,求等价类和商集,
*5.掌握相容关系的概念,关系图和矩阵的简化,求相容类,
最大相容类和完全覆盖,
6.偏序关系的判断,会画 Hasse图,会求一个子集的极小 (大 )
元,最小 (大 )元,上界与下界,最小上界及最大下界,
注意本章证明题的证明过程的思路
一,关系的概念,表示方法,三个特殊关系,
1.集合的笛卡 尔 积
A× B={<x,y>|x∈ A∧ y∈ B} |A|=m,|B|=n |A× B|=mn
设 A={0,1},B={a,b}，求 A?B 。
A?B={<0,a>,<0,b>,<1,a>,<1,b>}
2.二 元关系的概念
定义 1:设 A、Ｂ是集合,如果Ｒ ?A× B,则称 R是一个从 A到
B的二元关系。如果 R?A× A,则称 R是 A上 的二元 关系,
如果 |A|=m |B|=n 则可以确定 2mn个从 A到 B的不同关系,
定义 2:任何 序偶的集合,都称之为一个二元关系。
3.关系的表示方法
1),枚举法,
即将关系中所有序偶一一列举出，写在大括号内,
如,R={<1,2>,<3,4>,<4,2>}
2).(描述法 )谓词公式法,
即用谓词公式描述序偶中元素的关系。例如
R={<x,y>|x<y}
3).有向图法,
1。
2。
3。
4。
。
。
。
A B
a
b
c
R1,
1。 。
4。 。
2
3
R2,
4).矩阵表示法, (实际上就是图论中的邻接矩阵 )
设 A={a1,a2,?,am},B={b1,b2,?,bn}是个有限集，
R?A× B，定义 R的 m× n阶 矩阵
MR=(rij)m× n，其中
4.三个特殊 关 系
1).空关系 Φ：
Φ?A× B,(或 Φ?A× A)，即无任何元素的关系,
它的关系图中只有结点,无任何边；它的矩阵中全是 0。
2).完全关系 (全域关系 )：
A× B(或 A× A)本身是一个从 A到 B(或 A上 )的完全关系,
即含有全部序偶的关系。它的矩阵中全是 1。
1 若 <ai,bj>∈ R
0 若 <ai,bj>∈ R (1≤i≤m,1≤j≤n)rij=
3),恒等关系 IA：
IA?A× A,且 IA ={<x,x>|x∈ A}称之为 A 上的恒等关系。
例如 A={1,2,3},则 IA ={<1,1>,<2,2>,<3,3>}
A上的 Φ、完全关系 A× A及 IA的关系图及矩阵如下：
MIA =
1 0 0
0 1 0
0 0 1 3× 3
1。
2。 。 3
1。
2。 。 3
1 1 1
1 1 1
1 1 1 3× 3
1。
。2。 3
0 0 0
0 0 0
0 0 0 3× 3
MΦ= MA× A=
Φ A× A IA
二,关系的性质,
熟练掌握性质的判断及证明,
1.自反性
定义,设 R是集合 A中的关系，如果对于任意 x∈ A都有
<x,x>∈ R (xRx)，则称 R是 A中自反关系。即
R是 A中自反的 ??x(x?A?xRx)
2.反自反性
定义,设 R是集合 A中的关系，如果对于任意的 x∈ A都有
<x,x>?R,则称 R为 A中的反自反关系。即
R是 A中反自反的 ??x(x?A?<x,x>?R)
3.对称性
定义,R是集合 A中关系,若对任何 x,y∈ A,如果有 xRy,必有
yRx,则称 R为 A中的对称关系。
R是 A上对称的 ??x?y((x?A?y?A?xRy) ?yRx)
4.反对称性
定义,设 R为集合 A中关系,若对任何 x,y∈ A,如果有 xRy,和
yRx,就 有 x=y,则称 R为 A中反对称关系 。
R是 A上反对称的 ??x?y((x?A?y?A?xRy?yRx)?x=y)
??x?y((x?A?y?A?x?y?<x,y>∈ R)?<y,x>?R)
5,传递性
定义,R是 A中关系，对任何 x,y,z∈ A,如果有 xRy,和 yRz,就
有 xRz,则称 R为 A中传递关系。
即 R在 A上传递
??x?y?z((x?A?y?A?z?A?xRy?yRz)?xRz)
这 些性 质 要求会判断,会 证 明,
这 里特 别 要注意的是,这 些定 义 都是 蕴 涵式,所以当 蕴 涵
式当前件 为 假 时,此 蕴 涵式 为 真,即此性 质 成立 !!
自反性
反自反性
对称性
传递性
反对称性
每个结点都有环 主对角线全是 1
每个结点都无环 主对角线全是 0
不同结点间如果有边,
则有方向相反的两条
边,
是以对角线为对称
的矩阵
不同结点间,最多有一
条边,
以主对角线为对称
的位置不会同时为 1
如果有边 <a,b>,<b,c>,
则也有边 <a,c>,
或者使得前件为假,
如果 aij=1,且 ajk=1,
则 aik=1
从 关 系的矩 阵从 关 系的有向 图性 质 判定,
判断下面关系的性质,
1。
2。 。
1。
2。 。
1。
2。 。
1。
2。 。 33 33
R2R1 R3 R4
自反性 反自反性 对称性 反对称性 传递性
R1 Y N N Y Y
R2 N Y N Y N
R3 Y N Y N Y
R4 Y N Y Y Y
1。
2。 。
1。
2。 。
1。
2。 。
1。
2。 。 33 33
R5 R6 R7 R8
自反性 反自反性 对称性 反对称性 传递性
R5 N Y N Y Y
R6 N N Y N N
R7 N N N N N
R8 N Y Y Y Y
关系性质当证明方法归纳, 设 R是 A上关系，
1.证明 R的 自反性,
方法 1 用自反定义证：任取 x∈ A,证出 <x,x>∈ R.
方法 2 用恒等关系 IA证,证出 IA?R,(见教材 P119(2))
方法 3 用自反闭包证,证出 r(R)=R,即 R∪ IA=R.
2.证明 R的 反自反性,
方法 1 用反自反定义证：任取 x∈ A,证出 <x,x>?R.
3.证明 R的 对称性,
方法 1 用对称定义证：
任取 x,y∈ A,设 <x,y>∈ R,证出 <y,x>∈ R.
方法 2 用求逆关系证,证出 Rc=R.
方法 3 用对称闭包证,证出 s(R)=R,即 R∪ Rc =R.
4.证明 R的 反对称性,
方法 1 用定义 1证：
任取 x,y∈ A,设 <x,y>∈ R,<y,x>∈ R.证出 x=y。
方法 2用定义 2证：
任取 x,y∈ A,x≠y,设 <x,y>∈ R,证出 <y,x>?R.
方法 3 用定理证,证出 R∩Rc ? IA, (见 教材 P118)
5.证明 R的 传递性,
方法 1 用传递定义证：
任取 x,y,z∈ A,设 <x,y>∈ R,<y,z>∈ R,证出 <x,z>∈ R.
方法 2 用传递闭包证,证出 t(R)=R,
即 R∪ R2∪ R3∪,.,=R.
方法 3用定理证,证出 (见教材 P119(2))
同学们可以根据具体情况,选用相应方法证明,其中必须掌
握的是用基本定义证明,
R R?Ro
三,掌握关系复合,求逆及闭包运算 (计算方法及性质 )
(一 )关系的复合
1.定 义,设 R?X× Y,S?Y× Z，则 R?S?X× Z。
R?S={<x,z>|x?X?z?Z??y(y?Y ?<x,y>?R?<y,z>?S)}
2.计算方法 (俗称过河拆桥法 )
⑴ 枚举法 R={<a,b>,<b,c>,<c,a>}
S={<a,b>,<b,c>,<b,b>,<c,a>}
R?S={<a,c>,<a,b>,<b,a>,<c,b>}
⑵ 有向图
a。
b。
c。
X
。
。
。
Y
a
b
c
R S
。
。
。
Z
a
b
c
。
。
。
Z
a
b
c
a。
b。
c。
X SR?
⑶ 矩阵
3.性质
1).满足结合律,R?A× B S?B× C T?C× D 则
R?(S?T)=(R?S)?T
2),R?A× B S?B× C T?B× C
⑴ R? (S∪ T)=(R?S)∪ (R?T)
⑵ R? (S∩T)?(R?S)∩(R?T)
3),R是从 A到 B的关系，则
R? IB=IA? R=R
推论, R?A× A,则 R? IA=IA? R=R (IA是运算 ?的 幺元 )
4).关系的乘幂 R0 =IA,R?A× A,
Rm ?Rn = Rm+n
(Rm)n =Rmn (m,n为非负整数 )
MR? S= 010001
100
010011
100? =
011100
010
(二 ),逆关系
1.定 义,设 R?X× Y,R的逆关系 RC={<y,x>|<x,y>?R}
<y,x>∈ RC ?<x,y>?R
2,计算方法
1),R={<1,2>,<2,3>,<3,4>,<4,5>}
RC ={<2,1>,<3,2>,<4,3>,<5,4>}
2),RC的有向图,是将 R的有向图的所有边的方向颠倒,
3),RC的矩阵 MRC =(MR)T 即为 R矩阵的转置
3.性质
令 R,S都是从 X到 Y的关系，则
1),(RC)C = R
2),(R∪ S)C = RC∪ SC 。
3),(R∩S)C = RC∩SC 。
4),(R－ S)C = RC－ SC 。
5),R?S ? RC?SC 。
6),(~R)C=~RC
7).令 R是从 X到 Y的关系,S是 Y到 Z的关系，则
(R? S)C= SC? RC 。
8),R是 A上关系，则
⑴ R是对称的，当且仅当 RC =R
⑵ R是反对称的，当且仅当 R∩RC ?IA。
(三 ).闭包运算
1.定义,给定 A中关系 R,若 A上另一个关系 R’，满足：⑴
R?R’；
⑵ R’是自反的 (对称的、传递的 )；
⑶ R’是,最小的,，即对于任何 A上自反 (对称、传递 )
的关系 R”,如果 R?R”,就有 R’?R”。 则称 R’是 R的 自反
(对称、传递 )闭包。记作 r(R),(s(R), t(R)) (reflexive、
symmetric,transitive)
2.计算方法 给定 A中关系 R
r(R)=R∪ IA。
s(R)=R∪ RC 。
t(R)=R∪ R2∪ R3∪,..。
t(R)=R∪ R2∪,..∪ Rn
*求 t(R)矩阵的 Warshall算法,
闭包的运算有三种形式,
如 A={a.b.c} R? A× A R={<a,b>,<b,c>,<c,a>}
a).集合形式,
r(R)=R∪ IA ={<a,b>,<b,c>,<c,a>}?{<a,a>,<b,b>,<c,c>}
={<a,b>,<b,c>,<c,a>,<a,a>,<b,b>,<c,c>}
s(R)=R∪ RC ={<a,b>,<b,c>,<c,a>}?{<b,a>,<c,b>,<a,c>}
={<a,b>,<b,c>,<c,a>,<b,a>,<c,b>,<a,c>}
R2={<a,c>,<b,a>,<c,b>} R3={<a,a>,<b,b>,<c,c>}
t(R)=R∪ R2∪ R3
={<a,b>,<b,c>,<c,a>}∪ {<a,c>,<b,a>,<c,b>}∪
{<a,a>,<b,b>,<c,c>}
={<a,b>,<b,c>,<c,a>,<a,c>,<b,a>,<c,b>,<a,a>,
<b,b>,<c,c>}
b)有向图形式,
b?
a?
?c
R3
R
b?
a?
?c b?
a?
?c
IA
∪ =
r(R)
b?
a?
?c
∪
R
b?
a?
?c b?
R2
a?
?c
t(R)
b?
a?
?c
∪ =
?c
∪
R
b?
a?
?c
=b?
RC
a?
s(R)
b?
a?
?c
c)矩阵形式,
Mr(R)=MR∨ MIA=
010001
100
100010
001∨ =
111110
011
Ms(R)=MR∨ MRC
=
010001
100
001100
010∨ =
011101
110
Mt(R)=M ∨ M ∨ M = 010001
100
001100
010
∨ = 111111
111R
2 R3R ∨
100010
001
3.性质
1),R是 A上关系，则
⑴ R是自反的，当且仅当 r(R)=R.
⑵ R是对称的，当且仅当 s(R)=R.
⑶ R是传递的，当且仅当 t(R)=R.
2),R是 A上关系，则
⑴ R是自反的，则 s(R)和 t(R)也自反。
⑵ R是对称的，则 r(R)和 t(R)也对称。
⑶ R是传递的，则 r(R)也传递。
* 3).设 R是 A上关系，则
⑴ sr(R)=rs(R)
⑵ tr(R)=rt(R)
⑶ st(R)?ts(R)
四,等价关系
掌握等价关系的判断,证明,求等价类和商集,
1.了解集合的划分与覆盖的概念,
例 X={1,2,3},A1={{1,2,3}},A2={{1},{2},{3}},
A3={{1,2},{3}},A4={{1,2},{2,3}},A5={{1},{3}}
A1,A2,A3,A4 是覆盖。 A1,A2,A3也是划分。
2.等价关系 定义,设 R是 A上关系,若 R是自反的、对称的
和传递 的，则称 R是 A中的等价关系。
3.等价关系 R的有向图,可能由若干个独立子图构成的，
每个独立子图都是完全关系图 。
1。
2。 。 3
R1 1。
2。 。 3
R2
1。
2。 。
R3
4.等价类,
1).定义,R是 A上的等价关系,a∈A,由 a确定的集合 [a]R
[a]R={x|x∈A∧<a,x>∈R}
称集合 [a]R为由 a形成的 R等价类。
2).由等价关系图求等价类, R图中每个独立子图上的结
点构成一个等价类。不同的等价类个数 =独立子图个数。
3).等价类性质 R是 A上等价关系，任意 a,b,c∈ A
⑴ 同一个等价类中的元素，彼此有等价关系 R。
⑵ [a]R∩[b]R=Φ,当且 仅当 <a,b>?R。
⑶ [a]R=[b]R 当且 仅当 <a,b>∈ R。
⑷,A中任何元素 a,a必属于且仅属于一个等价类。
⑸,任意两个等价类 [a]R,[b]R,
要么 [a]R=[b]R,要么 [a]R∩[b]R=Φ。
⑹ R的所有等价类构成的集合是 A的一个划分。
5.商集,定义, R是 A上等价关系，由 R的所有等价类构成
的集合称之为 A关于 R的商集。记作 A/R。即
A/R={[a]R |a∈ A}
6.商集应用,
1)按照集合的等势关系 (是等价关系 ),~”对集合族 S进行
划分，得到商集 S/~,进而得到基数类的概念。
S={0,Φ,1,{1},{a},…,2,{0,1},{a,b},…,3,{0,1,2},…,N,I,…R,.,}
S/~={[0],[1],[2],[3],…,[N],[R],...}
2).无向图结点之间的连通关系是个等价关系,
令 G=<V,E>是无向图,R是 V上连通关系,即
R={<u,v>|u和 v是连通的 }
例, 给定图 G如右上图所示,
V/R={{a,b,g},{c,d,e,f},{h}}
无元素 1个元素 2个元素 3个元素 可数集 不可数集,..
?gh?
a? ?b
?ef?
c? ?d
3).图的同构关系 ≌ 是个等价关系,
令上述图构成的集合 A={a,b,c,d,e,f,g,h,i,j,},求商集 A/≌,
A/≌ ={{a,h},{b,i},{c,e},{d},{f},{g,j}}
?
? ?
? ?
?
? ?
? ?
?
? ?
? ?
?
? ?
? ?
?
? ?
? ?
?
? ?
? ?
?
? ?
? ?
?
? ?
? ?
?
? ?
? ?
?
? ?
? ?
a b c d e
f g h i j
练习 1.R和 S都是 A上等价关系,下面哪个是 A上等价关系?
证明或举反例说明,
a) R∪ S b) R∩S c) ~R (即 A× A-R)
d) R-S e)R2 f) r(R-S) e) Rc
解,a) c) d) f)不是, 请看反例,
R
。 a
。 cb。
。 a
。 cb。
。 a
。 cb。S R∪ S
。 a
。 cb。 ~R
。 a
。 cb。 R’
。 a
。 cb。 R’-S
。 a
。 cb。 r(R’-S)
b) R∩S是等价关系,
证明, 1,证明 R∩S的自反性
方法 1 用自反定义证：任取 x∈ A,(证出 <x,x>∈ R∩S)
因 R和 S都自反，所以有 <x,x>∈ R,<x,x>∈ S，于是有
<x,x>∈ R∩S，所以 R∩S也自反。
方法 2 用恒等关系 IA证,(证出 IA ?R)
因 R和 S都自反，所以 IA ?R, IA ?S，所以 IA ?R∩S
所以 R∩S也自反。
方法 3 用自反闭包证：
(证出 r(R∩S)=R∩S,即 (R∩S)∪ IA= R∩S)
因 R和 S都自反，所以 r(R)=R,r(S)=S,
r(R∩S)=(R∩S)∪ IA= (R∪ IA)∩(S∪ IA)
=r(R)∩r(S)=R∩S 所以 R∩S也自反。
2.证明 R∩S 的对称性：
方法 1 用对称定义证：
任取 x,y∈ A,设 <x,y>∈ R∩S,(证出 <y,x>∈ R∩S,)
则 <x,y>∈ R,<x,y>∈ S,因为 R和 S对称，所以有
<y,x>∈ R,<y,x>∈ S,于是 <y,x>∈ R∩S 。 ∴ R∩S 对称。
方法 2 用求逆关系证,(证出 (R∩S )c=R∩S,)
因为 R和 S对称，所以有 Rc=R,Sc=S,而
(R∩S )c=Rc∩S c= R∩S, ∴ R∩S 对称。
方法 3 用对称闭包证,(证出 s(R∩S )=R∩S,)
因为 R和 S对称，所以 s(R)=R,s(S)=S
s(R∩S )= (R∩S )∪ (R∩S )c =(R∩S )∪ (Rc∩S c)
=(R∪ Rc)∩ (R∪ Sc)∩ (S∪ Sc)∩ (S∪ Rc)
=(s(R)∩ (R∪ Sc))∩ (s(S)∩ (S∪ Rc))
=(R∩ (R∪ Sc))∩ (S∩ (S∪ Rc))=R∩ S (吸收律 )
∴ R∩S 对称。
3.证明 R∩S 的传递性：
方法 1 用传递定义证：任取 x,y,z∈ A,
设 <x,y>∈ R∩S,<y,z>∈ R∩S,(证出 <x,z>∈ R∩S )
<x,y>∈ R∩S ∧ <y,z>∈ R∩S
? <x,y>∈ R∧ <x,y>∈ S∧ <y,z>∈ R∧ <y,z>∈ S
? (<x,y>∈ R∧ <y,z>∈ R)∧ (<x,y>∈ S ∧ <y,z>∈ S)
? <x,z>∈ R∧ <x,z>∈ S （因为 R,S传递）
? <x,z>∈ R∩S 所以 R∩S 传递 。
所以 R∩S 是 A上等价关系,
e)证明, R2是等价关系,
方法 1.由 P119习题 (3)得,如果 R自反和传递,则 R2 =R,所以
R2也是等价关系,
方法 2.① 证 R2自反,
任取 a∈ A,因为 R自反,所以 <a,a>∈ R,根据关系的复合得,
<a,a>∈ R R,即 <a,a>∈ R2,所以 R2自反。
② 证 R2对称,
(R2)c=(Rc)2=R2 (由 R对称得 Rc=R) ∴ R2对称
③ 证 R2传递,
任取 a,b,c∈ A,设有 <a,b>∈ R2,<b,c>∈ R2,
根据关系的复合得,
(?d∈ A∧ <a,d>∈ R∧ <d,b>∈ R)∧ (?e∈ A∧ <b,e>∈ R∧ <e,c>∈ R),
由于 R传递,所以有 <a,b>∈ R,<b,c>∈ R,∴ <a,c>∈ R2
所以 R2传递。 最后得 R2是等价关系。
g),R是 A上等价关系,则 Rc也是 A上等价关系,
证明 1)证 Rc自反。
因为任取 x∈ A,因 R自反，所以 <x,x>∈ R,∴ <x,x>∈ Rc
2) R对称，证 Rc也对称。
因为 R对称，所以 Rc =R ∴ Rc也对称。
3) R传递，证 Rc也传递。
方法 1,任取 x,y,z∈ A,且有 <x,y>∈ Rc,<y,z>∈ Rc,于是
<y,x>∈ R,<z,y>∈ R，因 R传递,∴ <z,x>∈ R,于是有
<x,z>∈ Rc,∴ Rc传递。
方法 2,t(Rc)=Rc∪ (Rc)2∪ (Rc)3∪ …
= Rc∪ (R2)c∪ (R3)c∪ …= (R ∪ R2∪ R3∪ …) c
= (t(R))c=Rc 所以 Rc传递。
所以 Rc是 A上等价关系,
练习 2.五,设 X={1,2,3} Y={1,2},在 X的幂集 P(X)上定义二
元关系 R如下, 对于任何 A,B∈ P(X),
ARB 当且仅当 A?Y=B?Y
1.画出关系 R的有向图,
2.R是等价关系吗?如果是,请写出商集 P(X)/R,如果不是请
说明原因
解,1.关系 R的有向图,
2,从 R有向图看出 R有自反,对称和传递性,故是等价关系
P(X)/R={{?,{1},{2},{1,2}},{{3},{1,3},{2,3},{1,2,3}}}
?{1,3}
?{1,2,3}{2,3}?
{3}??? ?{1}
{2}? ?{1,2}
*五,相容关系
1.定义,给定集合 X上的关系 r,若 r是自反的、对称的,则 r
是 A上 相容关系 。
2.图的简化,⑴不画环；
⑵两条对称边用一条无向直线代替。
3.矩阵的简化,因为 r的矩阵是对称阵且主对角线全是 1，
用下三角矩阵 (不含主对角线 )代替 r的矩阵。
4.相容类,设 r是集合 X上的相容关系,C?A,如果对于 C
中任意两个元素 x,y有 <x,y>∈ r,称 C是 r的一个 相容类,
5,最大相容类,设 r是集合 X上的相容关系,C是 r的一个相
容类，如果 C不能被其它 相容类所真包含，则称 C是一
个 最大相容类。 ----最大完全多边形,
6.完全覆盖, r是中的相容关系，由 r的所有 最大相容类
为元素构成的集合，称之为 X的完全覆盖。记作 Cr(X)。
练习,已知 X={1,2,3,4,5,6,7}上的相容关系 r的交换矩阵为,
求完全覆盖 Cr(X)
解,先画出 r的简化图,如右上图所示,
于是得完全覆盖为,
Cr(X)={{1,2,4,5},{1,3,7},{1,3,4},{7,6}}
1
1 0
1 1 1
1 1 0 1
0 0 0 0 0
1 0 1 0 0 1
1?
2? 3?
? 4
? 5
? 6
7?
五,偏序关系 判断,会画 Hasse图,会求一个子集的极小
(大 )元,最小 (大 )元,上界与下界,最小上界及最大下界,
1,定义, R是 A上自反、反对称和传递的关系，则称 R
是 A上的偏序关系。并称 <A,R>是偏序集。
2,x与 y是可比较的, <A,≤>是偏序集,x,y∈ A,如果要
么 x≤y,要么 y≤x,则称 x与 y是可比较的。
3.定义, <A,≤>是偏序集，任何 x,y∈ A,如果 x与 y都是可
比较的，则称 ≤是 全序 关系 (线序、链 )。
4.偏序集 Hasse图的画法, 令 <A,≤>是偏序集，
1).用,?”表示 A中元素。
2).如果 x≤y,且 x≠y,则结点 y要画在结点 x的上方。
3),如果 x≤y,且 y盖住 x,x与 y之间连一直线。
4),从最下层结点 (全是射出的边与之相连，逐层向上画，
直到最上层结点 (全是射入的边与之相连 )。
例如
2。
1。
。
6
4 2。
1。
。
8
4
１ 。
２ 。
４ 。６ 。
１ 。
２ 。
４ 。
８ 。
5,重要元素
y是 B的 极小元 ??y(y∈ B∧ ??x(x∈ B∧ x≠y∧ x≤y))
(在 B中没有比 y更小的元素了,y就是 极小元 )
y是 B的 极大元 ??y(y∈ B∧ ??x(x∈ B∧ x≠y∧ y≤x))
(在 B中没有比 y更大的元素了,y就是 极大元 )
y是 B的 最小元 ??y(y∈ B∧ ?x(x∈ B?y≤x))
(最小元 y是 B中元素，该元素比 B中所有元素都小 )
y是 B的 最大元 ??y(y∈ B∧ ?x(x∈ B?x≤y))
(最大元 y是 B中元素，该元素比 B中 所有元素都大 )
y是 B的 上界 ??y(y∈ A∧ ?x(x∈ B?x≤y))
(上界 y是 A中元素，该元素比 B中所有元素都大 )
y是 B的 下界 ??y(y∈ A∧ ?x(x∈ B?y≤x))
(下界 y是 A中元素，该元素比 B中 所有元素都小 )
y是 B的上界，并且对 B的所有上界 x,都有 y≤x,则
称 y是 B的 最小上界 (上确界 )，记作 LUB B=y 。
(即 y是上界中最小的。如果 B有上确界，则是唯一的 )
y是 B的下界，并且对 B的所有下界 x,都有 x≤y,则
称 y是 B的 最大下界 (下确界 )，记作 GLB B=y 。
(即 y是下界中最大的。如果 B有上确界，则是唯一的 )
例如 B={2,3,6}
B的极小元,2,3 极大元, 6
最小元,无 最大元,6
下界,1 上界,6,12,18
下确界,1 上确界,6 １ 。
6。
18。12。
2。 。 3
第六章 函数
1.函数的定义,
2.函数的类型,会判断,会证明,
3.会计算函数的复合 (左复合 ),求逆函数,知道有关性质,
*4.了解集合特征函数和模糊子集的表示及计算,
*5.了解自然数的定义,集合的等势定义,集合基数的定义,
可数集定义,可数集的基数,连续统基数,基数的比较,
一,概念
1.定义, X与 Y集合,f是从 X到 Y的关系，如果 任何 x∈ X，
都存在 唯一 y∈ Y,使得 <x,y>∈ f,则称 f是 从 X到 Y的函数,
(变换、映射 )，记作 f:X?Y.
如果 f:X?X是函数,也称 f是 X上的函数,
要求会判断 某些给定关系是否是函数,
2.函数相等, f:A?B,g:C?D,f=g?A=C?B=D?f(x)=g(x)
3.从 X到 Y函数的集合 YX,YX ={f| f:X?Y}
YX, 它是由 所有 的从 X到 Y函数 构成的集合,
4.特殊函数
1),常值函数,函数 f:X?Y, 如果 ?y0∈ Y,使得对 ?x∈ X,
有 f(x)=y0,即 ran f={y0},称 f是常值函数。
2).恒等函数,恒等关系 IX是 X到 X函数，即 IX:X?X,称
之为恒等函数。显然对于 ?x∈ X，有 IX(x)=x 。
5.函数的类型,会判断,会证明,
1).满射的, f:X?Y是函数，如果 Rf=Y,则称 f 是 满射的 。
证明方法,任取 y∈ Y,看是否能够找到对应的自变元
x∈ X,使得 y=f(x).
2).映内的, f:X?Y是函数，如果 Rf?Y 则称 f 是 映内的 。
3).入射的, f:X?Y是函数，如果对于任何 x1,x2∈ X,如果
x1≠x2 有 f(x1)≠f(x2),(或者若 f(x1)=f(x2),则 x1=x2),则称 f 是
入射的,也称 f 是 单射的,也称 f 是 一对一的 。
证明的方法,如定义中所说,
4).双射的, f:X?Y是函数，如果 f 既是满射的，又是
入射的，则称 f 是 双射的,也称 f 是 一一对应的 。
双射是个重要概念,我们用双射定义了如下概念,
集合的等势关系,~” ;
代数系统的同构关系,≌,
图的同构关系,≌,
练习题,R是实数集合，给定 R上的五个关系如下,
R1={<x,y>|x=y2} R2={<x,y>|y=x+6}
R3={<x,y>|y=(x-1)-1} R4={<x,y>|y=2x}
R5={<x,y>|x2+y2=4}
上述五个关系中，哪些 是从 R到 R的函数。如果是函数，
说明它是属于什么类型的（指满射、入射、双射）。
如果不是函数，说明理由 。
解,R1不 是从 R到 R的函数,x是负数时
无定义,另外当 x>0时,有两个 y值与之对应,
R2是从 R到 R的函数,是双射的,
R3不 是从 R到 R的函数,因为 x=1时,无定义,
R4是从 R到 R的函数,是入射的,不是满射的,
R5不 是从 R到 R的函数,因为 |x|>2时,无定义,|x|<2时
对应的函数值不唯一,
x
y
二,会计算函数复合 (左复合 ),求逆函数,知道有关性质,
1.函数的复合
1)定义, f:X?Y,g:Y?Z是函数,则定义
g?f ={<x,z>|x?X?z?Z??y(y?Y ?<x,y>?f?<y,z>?g)}
则称 g?f 为 f与 g的复合函数 (左复合 ).
注意,这里把 g写在 f的左边了,所以叫左复合,
g?f,X?Z,即 g?f 是 X到 Z的函数,这样写是为了
照顾数学习惯, g?f(x)=g(f(x)) ?x∈ X
2).复合函数的计算
计算方法同复合关系的计算, 但要注意是左复合,
3).函数复合的性质
(1).满足可结合性 。 f:X?Y,g:Y?Z,h:Z?W 是函数,则
(h? g)?f=h?(g? f)
(2).定理 5-2.2 f:X?Y,g:Y?Z是两个函数,则
a).如果 f和 g是 满 射的，则 g?f 也是 满 射的；
b).如果 f和 g是 入 射的，则 g?f 也是 入 射的；
c).如果 f和 g是 双 射的，则 g?f 也是 双 射的。
(3).⑴ 如果 g?f是 满 射的，则 g是 满 射的；
⑵ 如果 g?f是 入 射的，则 f 是 入 射的；
⑶ 如果 g?f 是 双 射的，则 f是 入 射的 和 g是 满 射的。
(4),f:X?Y是函数,则 f ? IX = f 且 IY? f = f。
f:X?X是函数,则 f ? IX=IX? f=f。 IX是运算,?” 的幺
元,
2.逆函数
1).定义,设 f:X?y是双射的函数,fC:Y?X 也是函数,称
之为 f 的逆函数。并用 f-1代替 fC。 f-1存在，也称 f 可逆。
2).性质
(1),设 f:X?y是双射的函数，则 (f-1)-1= f 。
(2),设 f:X?Y是双射的函数，则有 f-1? f= IX 且 f? f-1 = IY。
(3).令 f:X?Y,g:Y?X是两个函数,如果
g?f= IX 且 f?g = IY,则 g= f-1 。
(4).令 f:X?Y,g:Y?X是两个 双射 函数,则 (g?f)-1=f-1? g-1
*证明题
给定函数 f:A→B g:C→D,已知
f?g 并且 ram g ? ran f,其中 ran g 是函数 g的值域
求证：如果 g是入射的，则Ａ＝Ｃ,
证明,先证 A?C 任取 x?A,因为 f:A→B 是函数，必存在
唯一 y?B，使得 <x,y>?f,又因为 f?g,所以 <x,y>?g,而
g:C→D 是函数，所以 x?C,所以 A?C。
再证 C?A,任取 x?C,因为 g:C→D 是函数，必存在
唯一 y?D，使得 <x,y>?g,所以 y?ran g,又 ram g? ran f,
所以 y?ran f,而 f:A→B, 所以 必存在 x’?A,使得 <x’,y>?f,
因为 f?g,所以 <x’,y>?g,可是前边已得 <x,y>?g,而 g是
入射的，所以 x’=x,即得 x?A,所以 C?A。
最后得 A=C。
第六章 代数系统
1.掌握运算的定义,
2.熟练掌握二元运算的性质的判断及证明,
3.掌握代数系统的同构定义,会证明,了解同构性质的保持,
4.了解半群,独异点,*环和域的概念,
5.熟练掌握群,子群,交换群 (会证明 ),
6.了解循环群,
*6,掌握循环群定义,循环群的循环周期以及循环群的同
构,
7.了解 Lagrange定理及其推论,(会应用 ).
*7,掌握 Lagrange定理及其推论 (会应用 ).
*8.了解环的运算法则,
注意本章证明题的思路和技巧
一,掌握运算和代数系统的概念,
1.运算定义,设 X是个集合,f:Xn?Y是个映射，则称 f是
X上的 n元运,(Xn =X× X×,..× X --n个 X的笛卡尔积 )
2代数系统定义, X是非空集合,X上的 m个运算
f1,f2,…f m,构成 代数系统 U,记作 U=<X,f1,f2,…f m> ( m≥1)
二,熟练掌握二元运算的性质的判断及证明,
<X,?>和 <X,?,?>是代数系统,?,?是二元运算：
1.封闭性,?x,y∈ X,有 x?y∈ X。
2.可交换性,?x,y∈ X,有 x?y=y? x。
3.幂等性,?x∈ X,有 x?x=x。
4,有幺元,e∈ X,?x∈ X，有 e?x=x?e=x.
5.有零元, θ∈ x,?x∈ X，有 θ?x=x?θ=θ.
6.可结合性,?x,y,z∈ X,有 (x?y)?z =x?(y?z)。,
7.有逆元,x∈ X,有 x-1∈ X，使得 x-1?x=x?x-1=e
8.可消去性,a∈ X,?x,y∈ X,有
(a?x=a?y)∨ (x?a=y?a) ? x=y.
9.分配律,?对 ?可分配,?x,y,z∈ X，有
x?(y?z)=(x?y)?(x?z) 或 (x?y)?z =(x?z)?(y?z)
10.吸收律,?x,y∈ X，有 x?(x?y)=x 和 x?(x?y)=x
对这些性质要求会判断、会证明。
三,掌握代数系统同构定义,会证明,了解同构性质的保持
1.定义设 <X,?>,<Y,?>是两个代数系统,?和 ? 都 是二元
运算，如果存在映射 f:X?Y,使得对任何 x1,x2∈ X，有
f(x1?x2)=f(x1)?f(x2) --------此式 叫 同态 (同构 )关系式
则称 f是从 <X,?>到 <Y,?>的同态映射，简称这两个代数
系统 同态 。记作 X∽ Y。
并称 <f(X),? >为 <X,?>的 同态像 。
如果 f是满射的，称此同态 f是 满同态 。
如果 f是入射的，称此同态 f是 单一同态 。
如果 f是双射的，称 <X,?>与 <Y,?>同构,记作 X≌ Y。
f是 <X,?>到 <X,?>的同态 (同构 ),称之为 自同态 (自同构 )。
2.代数系统 同构性质的保持
代数系统 <X,?>,<Y,?>,X≌ Y,f:X?Y是同构映射,如果
<X,?>中 ?满足交换、结合、有幺元、有零元、每个元
素可逆,则 <Y,?>中 ?也满足上述性质。反之亦然,
*3.同态核
定义, f是从 <X,?>到 <Y,?>的同态映射,(X∽ Y),e?和 e?
分别是 X,Y中幺元。定义 集合 ker (f)为：
ker (f)={x|x∈ X∧ f(x)= e? }
称 ker (f)为 f的同态核。
四,掌握半群,独异点,群,环和域的概念,
半群, 封闭
结合独异点,有幺元
群
可逆
环, <R,+,?><R,+>是交换群
<R,?>是半群
?对 +可分配整环 <R,+,?>
<R,?>是可交换独异点
无零因子 (ab=0则 a=0或 b=0)
域 <F,+,?> <F,
+>是交换群
<F-{0},?>是交换群
?对 +可分配
<R,+>是交换群
?对 +可分配
五,熟练掌握群的阶和元素的阶的概念及群的性质,
1.群的阶,<G,*>是群,如果 K[G]=n (n是正整数 ),则 G是 n
阶群,否则 G是无限阶群,
2.元素的阶,设 <G,?>是个群,a∈ G,如果存在 正整数 k，
使得 ak=e,则称 a的阶是有限的。如果存在 最小的正整数 n，
使得 an=e,则称 a的阶是 n。 否则就称 a的阶是无限的。
定理 6-5.7,<G,?>是群,a∈ G,如果 a的阶为 n,则
ak=e 当且仅当 k=mn (m∈ I)(即 k是 n的整数倍 )
定理 6-5.8,群中的元素与其逆元 具有相同的阶。
定理 6-5.9 有限群中，每个元素的阶都是有限的。
3.群的性质
1).群满足可消去性
定理 6-5.1设 <G,?>是个群，则对任何 a,b,c∈ G,如果 有
⑴ a?b=a?c 则 b=c 。
⑵ b?a= c?a 则 b=c 。
2),群方程可解性
定理 6-5.2 设 <G,?>是个群，则对任何 a,b∈ G,
⑴ 存在唯一元素 x∈ G,使得 a?x=b …….,⑴
⑵ 存在唯一元素 y∈ G,使得 y?a=b …….,⑵
3),群中无零元 。
定理 6-5.3 设 <G,?>是个群,如果 K[G] ≥2,则 G中无零元,
4),群中除幺元外，无其它幂等元 。
5).定理 6-5.5 <G,?>是个群，对任何 a,b∈ G,有
⑴ (a-1)-1 =a ⑵ (a?b)-1=b-1?a-1
6),有限群的运算表的特征
定理 6-5.6 <G,?>是个有限群，则 G中 每个元素 在 ?运算
表中的每一行 (列 )必出现且仅出现一次 。
练习题,给定群 <G,*>,*的运算表如
右图所示,求解下面群的方程,
b*d-1*x*c=d*c-1
解, b*d-1*x*c=d*c-1 ∵ d-1=b c-1=c
∴ b*b*x*c=d*c ∵ b*b=c ∴ c*x*c=d*c
消去 c得 c*x=d
解得, x=c-1*d=c*d=b
* a b c d
a a b c d
b b c d a
c c d a b
d d a b c
六,掌握交换群 (会证明 )
练习题 1.给定集合Ｇ＝ {x|x是有理数且 x≠1},在Ｇ上定
义二元运算 *如下：任何 a,b∈ Ｇ a*b=a+b-ab
求证 <Ｇ,*>是个交换群。
证明,1.证封闭性,任取 a,b?G,∴a≠1,b≠1,
a*b=a+b-ab 若 a+b-ab=1,则 b= =1,产生矛盾,
所以 a+b-ab≠1 ∴ a *b?G
2.证可结合性,任取 a,b,c?G,∴a≠1,b≠1,c≠1,
a*(b*c)=a+(b+c-bc)-a(b+c-bc)
=a+b+c-bc-ab-ac+abc=(a+b-ab)+c-(a+b-ab)c=(a*b)*c
3.证有幺元 0,任取 a?G,
a*0=a+0-a0=a 0*a=0+a-0a=a 所以 0是幺元,
___1-a
1-a
4.证可逆性,任取 a?G,a≠1,设有 b,使得
a*b=a+b-ab=0 ∴ a+(1-a)b=0,b= ≠1 ∴b ?G
a*b=0 且 b*a= *a= +a- a= =0
所以 a有逆元 b.即 a-1=
5.证交换性,任取 a,b?G,
a*b=a+b-ab=b+a-ba=b*a
综上所述 <G,*>是个交换群,
___a
a-1
__________a
a-1
___a
a-1
___a
a-1 a-1
a+a(a-1)-aa
___a
a-1
七, 了解循环群,
1.循环群的定义,设 <G,?>是群,如果存在一个元素 g∈ G,
使得对每个 x∈ G,都存在整数 i,有 x=gi,则称 <G,?>是
个 循环群, 并称 g是 G的 生成元,
2.循环群的循环周期,
周期有限,为 k;
周期无限,
3.两种循环群,
<Nk,+k>,周期为 k;
<I,+>, 周期无限,
八,会证明子群,会应用 Lagrange定理及其推论,
1.子群的证明方法,
方法 1.用子群的定义，即证明运算在子集上满足封闭、
有幺元、可逆。
方法 2,设 <G,?>是群,S是 G的非空子集，如果
<S,?>满足,封闭性和 可逆性,则 <S,?>是 <G,?>的子群。
方法 3.设 <G,?>是群,B是 G的 有限子集,如果 ?在 B上满足
封闭性,则 <B,?>是 <G,?>的子群。
方法 4,设 <G,?>是群,S是 G的非空子集，如果 任何 a,b∈ S
有 a?b-1∈ S,则 <S,?>是 <G,?>的子群。
练习题 2:设 f和 g都是群 <G1,?>到 <G2,? >的同态，证明
<C,?>是 <G1,?>的一个子群，其中
C={x| x∈ G1且 f(x)=g(x)}
证明, 方法 1，用子群定义证明 <C,?> 满足：
a)封闭性,任取 x1,x2∈ C,(推出 x1?x2∈ Cf(x1?x2)=g(x1?x2))
∴ f(x1)=g(x1) f(x2)=g(x2)
f(x1?x2) =f(x1) ? f(x2) =g(x1) ? g(x2)=g(x1?x2) ∴ x1?x2∈ C
b)证幺元 e1∈ C,(推出 f(e1)= g(e1))
设 e1和 e2分别是 G1和 G2中的幺元,
因 f(e1)= e2= g(e1) ∴ e1∈ C。
c)可逆性：任取 x∈ C,(推出 x-1∈ C 即 f(x-1)= g(x-1))
f(x)=g(x) x-1∈ G1,f (x-1)= (f(x))-1= (g(x))-1 =g(x-1)
∴ x-1∈ C。 综上所述,<C,?>是 <G1,?>的一个子群。
方法 4,任取 x1,x2∈ C,
(推出 x1?x2-1∈ C 即 f(x1?x2 -1)=g(x1?x2 -1))
∴ f(x1)=g(x1) f(x2)=g(x2) x2-1∈ G1
f(x1?x2-1 ) =f(x1)? f(x2-1) =f(x1)?(f(x2))-1 = g(x1)? (g(x2))-1
= g(x1) ? g(x2-1) = g(x1?x2-1)
∴ x1?x2-1∈ C
所以 <C,?>是 <G1,?>的一个子群。
综合练习题,设 <G,?>是群，定义 G上关系 R如下；
R= {<x,y>| ?z∈ G,使得 y=z?x?z-1 }
1.证明 R是 G上等价关系。
*2.令上述 <G,?>为 <N6,+6>时,求商集 N6/R.
证明 1.a) 证 R自反,任取 x∈ G,幺元 e∈ G,因为
x=e?x?e-1 由 R定义得 <x,x>∈ R，所以 R自反。
b)证 R对称,任取 x,y∈ G,设有 <x,y>∈ R,
由 R定义得 ?z∈ G,使得 y=z?x?z-1,于是有：
z-1?y?z= z-1?(z?x?z-1)?z,
z-1?y?z= (z-1?z)?x?(z-1?z),所以 z-1?y?(z-1) -1 =x
因 z-1∈ G，所以有 <y,x> ∈ R,所以 R对称。
c)证明 R传递,任取 x,y,z∈ G,设有 <x,y>∈ R,<y,z>∈ R
由 R定义得 ?z1,z2∈ G,使得 y=z1?x?z1-1,z=z2?y?z2-1,
于是有 z=z2?y?z2-1 = z2?(z1?x?z1-1)?z2-1
= (z2?z1)?x?(z1-1?z2-1)=(z2?z1)?x?(z2?z1)-1 因
z2?z1∈ R,∴ <x,z>∈ R,∴ R传递。 ∴ R是 G上等价关系。
*2.令上述 <G,?>为 <N6,+6>时,求商集 N6/R.
N6={0,1,2,3,4,5}
R= {<x,y>| ?z∈ N6,使得 y=z?x?z-1 },
<x,y>∈ R??z(y=z?x?z-1)??z(y?z=z?x)
按照上述表达式得关系 R图如下,
因此商集 N6/R={{0},{1},{2},{3},{4},{5}}
2?
0? ?3
5? ?4
* 第七章 格与布尔代数
1.掌握格的定义,了解格的性质,
2.会判断格,分配格,有补格和布尔格,
3.重点掌握两个元素的布尔代数的性质 (10个 ).
4.会写两个元素的布尔表达式的范式,(实质是第一章的主
析取和主合取范式 ).
一,掌握格的定义
1,格的定义
<A,≤>是偏序集，如果任何 a,b∈ A,使得 {a,b}都有最大
下界和最小上界，则称 <A,≤>是格。
2,由格诱导的代数系统
设 <A,≤>是格,在 A上定义二元运算 ∨ 和 ∧ 为,?a,b∈ A
a∨ b=LUB {a,b} {a,b}的最小上界,Least Upper Bound
a∧ b=GLB {a,b} {a,b}的最大下界,Greatest Lower Bound
称 <A,∨,∧ >是由格 <A,≤>诱导的代数系统, (∨ -并,∧ -交 )
二,格的性质
<A,∨,∧ >是由格 <A,≤>诱导的代数系统。 ?a,b,c,d∈ A
1,a≤a∨ b b≤a∨ b a∧ b≤a a∧ b≤b
2.如果 a≤b,c≤d,则 a∨ c≤b∨ d,a∧ c≤b∧ d。
推论,在一个格中，任何 a,b,c∈ A，如果 b≤c，则
a∨ b≤a∨ c,a∧ b≤a∧ c。 此性质称为 格的保序性 。
3,∨ 和 ∧ 都满足 交换律 。即 a∨ b=b∨ a,a∧ b=b∧ a。
4,∨ 和 ∧ 都满足 幂等律 。即 a∨ a=a a∧ a=a
5,∨ 和 ∧ 都满足 结合律 。即
(a∨ b)∨ c =a∨ (b∨ c), (a∧ b)∧ c =a∧ (b∧ c) 。
6,∨ 和 ∧ 都满足 吸收律 。即 a∨ ( a∧ b) =a,a∧ (a∨ b) =a。
7,<A,∨,∧ >是代数系统，如果 ∨ 和 ∧ 是 满足吸收律 的二
元运算，则 ∨ 和 ∧ 必满足幂等律 。
8,∨ 和 ∧ 不 满足 分配律 。但有分配 不等式,
a∨ (b∧ c)≤ (a∨ b)∧ (a∨ c),
(a∧ b)∨ (a∧ c)≤a∧ (b∨ c) 。
9,a≤b? a∨ b=b ? a∧ b=a
三,格的同态,同构
1.设 <A1,≤1> 和 <A2,≤2>是两个格，由它们诱导的代数系
统分别是 <A1,∨ 1,∧ 1>和 <A2,∨ 2,∧ 2>，如果存在映射
f:A1?A2 使得对任何 a,b∈ A1,
f(a∨ 1b)=f(a)∨ 2f(b)
f(a∧ 1b)=f(a)∧ 2f(b)
则称 f是 <A1,∨ 1,∧ 1>到 <A2,∨ 2,∧ 2>的同态映射。
也称 <f(A1),≤2>是 <A1,≤1> 的同态像。
如果 f 是双射的，就称 f是 <A1,∨ 1,∧ 1>到 <A2,∨ 2,∧ 2>，
的格同构，也称格 <A1,≤1> 和 <A2,≤2>同构。
两个格同构,两个格的图同构,
2.格同态和同构的保序性
四,分配格
1.定义 <A,∨,∧ >是由格 <A,≤>诱导的代数系统。如果
对 ?a,b,c∈ A，有
a∨ (b∧ c) =(a∨ b)∧ (a∨ c),
a∧ (b∨ c)= (a∧ b)∨ (a∧ c)
则称 <A,≤>是 分配格。
2,二个重要的五元素非分配格,
3.分配格的判定,
一个格是分配格的 充分且必要条件 是在该格中没有任何
子格与上述两个五元素非分配格之一同构,
4,分配格的性质
1),定理 7-2.1,在格中，如果 ∧ 对 ∨ 可分配，则 ∨ 对 ∧ 也
可分配,反之亦然。
2),定理 7-2.2,所有链均为 分配格。
? 3
? 1
? 30
2? ? 5
? d
? e
? a
b?
? c
3),设 <A,≤>是分配格，对任何 a,b,c∈ A,如果有
a∧ b=a∧ c 及 a∨ b=a∨ c 则必有 b=c,
五,有界格
有界格定义：如果一个格存在 全上界 1与全下界 0，则
称此格为有界格,
六,有补格
1,元素的补元,
设 <A,≤>是个有界格,a∈ A,如果存在 b∈ A,使得
a∨ b=1 a∧ b=0 则称 a与 b互为补元。
2,有补格的定义,一个有界格中，如果每个元素都有补
元，则称之为有补格。
3.在有界分配格中，如果元素有补元，则补元是唯一的。
七, 布尔格 如果一个格既是分配格又是有补格，则称
之为布尔格。布尔格中每个元素都有唯一补元。
练习题,给定集合如下：
A1={1,2,4,8,16} A2={1,2,3,5,6,10,15,30}
A3={1,2,3,5,30} A4={1,2,3,5,10,15,30}
A5={1,2,3,4,9,36} 令 ≤ 是上述集合上的整除关系。
1.请分别画出各个偏序集 <Ai,≤> 的哈斯图 (i=1,2,3,4,5)
1。
2。
4。
8。
16。
2?
?9
36?
4?
1?
?3
30。
3。
１ 。
2。 5 。
10。 15 。6。
<A2,≤><A
1,≤>
3。
１ 。
5。
30。
２ 。
<A3,≤>
30。
3。
１ 。
2。 5。
10。 １ 5。
<A4,≤> <A5,≤>
2.用, Y”表示, 是,,用, N”表示, 否, 填下表。
<A1,≤> <A 2,≤> <A 3,≤> <A 4,≤> <A 5,≤>
分配格
有补格
布尔格
Y Y N N N
N Y Y N Y
N Y N N N
1。
2。
4。
8。
16。
2?
?9
36?
4?
1?
?3
30。
3。
１ 。
2。 5 。
10。 15 。6。
<A2,≤><A
1,≤>
3。
１ 。
5。
30。
２ 。
<A3,≤>
30。
3。
１ 。
2。 5。
10。 １ 5。
<A4,≤> <A5,≤>
八, 布尔代数
1.定义
由布尔格 <B,≤>诱导的代数系统 <B,∨,∧,ˉ> 称之
为布尔代数。其中 ˉ 是取补元运算。
如果 A是有限集合，则称它是有限布尔代数。
2.布尔代数性质
设 <B,∨,∧,ˉ> 布尔代数,任意 x,y,z∈ B,有
⑴交换律 x∨ y=y∨ x x∧ y=y∧ x
⑵ 结合律 x∨ (y∨ z)=(x∨ y)∨ z x∧ (y∧ z)=(x∧ y)∧ z
⑶ 幂等律 x∨ x=x x∧ x=x
⑷ 吸收律 x∨ (x∧ y)=x x∨ (x∧ y)=x
⑸ 分配律 x∨ (y∧ z)=(x∨ y)∧ (x∨ z)
x∧ (y∨ z)=(x∧ y)∨ (x∧ z)
⑹ 同一律 x∨ 0=x x∧ 1=x
⑺ 零律 x∨ 1=1 x∧ 0=0
⑻ 互补律 x∨ =1 x∧ =0
⑼ 对合律
⑽底－摩根定律
3.布尔代数的同构
1),定义,令 <B1,∨ 1,∧ 1,ˉ>和 <B2,∨ 2,∧ 2,~>是两个布尔
代数，如果存在映射 f:B1?B2,对任何 a,b∈ B1,有
f(a∨ 1b)=f(a)∨ 2f(b)
f(a∧ 1b)=f(a)∧ 2f(b)
f( )=
则称 f是 <A1,∨ 1,∧ 1>到 <A2,∨ 2,∧ 2>的同态映射。
a
~f(a)
x x
2),原子
定义 1,设设 <B,∨,∧,ˉ> 布尔代数,元素 a∈ B,a≠0,对
任何元素 x∈ B,有 x∧ a=a,或 x∧ a=0,则称 a是原子。
定义 2:<A,≤>是布尔格,在 <A,≤>的 哈斯图中称盖住全
下界 0的元素为原子。
1。
e。
0。
d。 f。
b。 c。a。
0。
1。
? 0
?1
a? ? b
3),有关引理
⑴ 定理 7-3.2设 a,b是布尔代数 <B,∨,∧,ˉ> 中的原子,如果
a≠b,则 a∧ b=0,(如果 a∧ b≠0,则 a=b)
⑵ 定理 7-3.3设 a,b1,b2…b n是 布尔代数 <B,∨,∧,ˉ> 中的原
子,则 a≤b1∨ b2∨ … ∨ bn的 充分且必要条件为 对于某个 i
(1≤i≤n),有 a=bi.
⑶ 定理 7-3.4 设 b是有限布尔代数 <B,∨,∧,ˉ> 中的 非 0元素，
则必存在原子 a,使得 a≤b.
⑷ 定理 7-3.5 有限布尔代数中,b∧ =0,当且仅当 b≤c。
⑸ 定理 7-3.6设 <B,∨,∧,ˉ> 是有限布尔代数,b非 0元素，
a1,a2 …a k是 B中满足 aj≤b的所有原子 (j=1,2,…k),则
b＝ a1∨ a2 ∨ … ∨ ak且除原子次序不同外，
上述表达式是唯一的。
⑹ 定理 7-3.7 在布尔代数 <B,∨,∧,ˉ> 中,对 B中任何原子 a
和任何非 0元素 b,a≤b和 a≤ 两式中有且仅有一个成立。
⑺ 定理 7-3.8 (Stone定理 )设 <B,∨,∧,ˉ> 是有限布尔代数，
M是 B中所有原子构成的集合，则
<B,∨,∧,ˉ> 与 <P(M),∪,∩,~>同构。
⑻ 推论 1,任何有限布尔代数的元素个数为 2n (n=1,2,3,…)
因为 |P(M)|= 2n
推论 2,两个有限布尔代数同构的充分且必要条件是元素
个数相同。
4,布尔表达式概念
1).定义, 设 <B,∨,∧,ˉ> 是布尔代数，其上的布尔表达式
递归定义如下：
(1)B中任何元素是个布尔表达式。
(2)任何变元 x是个布尔表达式,
(3)如果 E1,E2是个布尔表达式,则,(E1∧ E2),(E1∨ E2)也
是布尔表达式。
(4)有限次地应用规则 1)--3),得到的符号串都是布尔表达式。
1E
2),布尔表达式的范式
1,有两个元素的布尔代数的布尔表达式的范式,
<{0,1},∨,∧,ˉ> 是两个元素的布尔代数
1),析取范式
(1).小项, 含有 n个变元的小项形式为,
其中
例如 都是小项,
(2).布尔表达式的析取范式,
含有变元 x1,x2,…,x n 的布尔表达式 E(x1,x2,…x n),如果写成
如下形式, A1∨ A2∨,..∨ Am(m≥1)
其中每个 Ai (1≤i≤m)都是有 n个变元的小项, 则称此式是
E(x1,x2,…x n)的析取范式,
nxxx ~.,,~~ 21 ???
）（或 nixxxx iiii ???? 1~~
)(),()( 321321321 xxxxxxxxx ??????
2),合取范式
(1),大项,含有 n个变元的大项形式为,
其中
例如 都是大项,
(2).布尔表达式的合取范式,
含有变元 x1,x2,…,x n 的布尔表达式 E(x1,x2,…x n),如果写成
如下形式, A1∧ A2∧,.,∧ Am (m≥1)
其中每个 Ai (1≤i≤m)都是有 n个变元的大项, 则称此式是
E(x1,x2,…x n)的合取范式, 例如,
3),析取范式与合取范式的写法,
方法 1:列真值表
方法 2:表达式的等价变换,
nxxx ?.,,?? 21 ???
）（或 nixxxx iiii ???? 1??
)(),()( 321321321 xxxxxxxxx ??????
)()()(),,( 321321321321 xxxxxxxxxxxxE ?????????
方法 1,用真值表求析取范式,
先介绍小项的性质,以两个变元 x1,x2为例
每一组赋值,有且仅有一个小项为 1.
根据一组赋值,求值为 1的小项, 如果变元 x,被赋值为 0,则
在此小项中,x以 形式出现 ; 如果变元 x,被赋值为 1,则在
此小项中,x以原形 x形式出现,
求 E(x1,x2,…x n)的析取范式,先列出它的真值表,找出表中
每个 1对应的小项,然后用 ∨ 连接上述小项,
2121212121 xxxxxxxxxx ????
0 0 1 0 0 0
0 1 0 1 0 0
1 0 0 0 1 0
1 1 0 0 0 1
例如,求 布尔代数 <{0,1},∨,∧,ˉ> 上 的布尔表达式
E(x1,x2,x3)=x1∧ (x2∨ ) 的析取范式,
E(x1,x2,x3)=(x1∧ ∧ )∨ (x1∧ x2∧ )∨ (x1∧ x2∧ x3)
x3ˉ
x1 x2 x3 E (x1,x2,x3)
0 0 1 0
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 1
0 0 0 0
1 1 1 1
x3ˉ x3ˉx2ˉ
方法 1,用真值表求合取范式,
先介绍大项的性质,以两个变元 x1,x2为例
每一组赋值,有且仅有一个大项为 0.
根据一组赋值,求值为 0的大项, 如果变元 x,被赋值为 1,则
在此小项中,x以 形式出现 ; 如果变元 x,被赋值为 0,则在
此小项中,x以原形 x形式出现,
求 E(x1,x2,…x n)的合取范式,先列出它的真值表,找出表中
每个 0对应的大项,然后用 ∧ 连接上述大项,
2121212121 xxxxxxxxxx ????
0 0 0 1 1 1
0 1 1 0 1 1
1 0 1 1 0 1
1 1 1 1 1 0
例如,求 布尔代数 <{0,1},∨,∧,ˉ> 上 的布尔表达式
E(x1,x2,x3)
=x1∧ (x2∨ )
的合取范式,
E(x1,x2,x3)=(x1∨ x2∨ x3)∧ (x1∨ x2∨ ) ∧ (x1∨ ∨ x3)∧
(x1∨ ∨ ) ∧ ( ∨ x2∨ )
x3ˉ x1 x2 x3 E (x1,x2,x3)
0 0 1 0
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 1
0 0 0 0
1 1 1 1
x3ˉ x2ˉ
x3ˉ x1ˉx2ˉ x3ˉ
方法 2,用表达式的等价变换求析取范式,
E(x1,x2,x3)=x1∧ (x2∨ ) =(x1∧ x2)∨ (x1∧ )
=(x1∧ x2∧ (x3∨ ))∨ (x1∧ (x2∨ )∧ )
=(x1∧ x2∧ x3)∨ (x1∧ x2∧ )∨ (x1∧ x2∧ )∨ (x1∧ ∧ )
=(x1∧ x2∧ x3)∨ (x1∧ x2∧ )∨ (x1∧ ∧ )
结果与前相同,
用表达式的等价变换求合取范式,
E(x1,x2,x3)=x1∧ (x2∨ )
=(x1∨ (x2∧ )∨ (x3∧ ))∧ ((x1∧ )∨ x2∨ )
=(x1∨ x2∨ x3 )∧ (x1∨ x2∨ )∧ (x1∨ ∨ x3 )∧ (x1∨ ∨ )
∧ (x1∨ x2∨ )∧ ( ∨ x2∨ )
=(x1∨ x2∨ x3 )∧ (x1∨ x2∨ )∧ (x1∨ ∨ x3 )∧ (x1∨ ∨ )
∧ ( ∨ x2∨ )
x3ˉ x3ˉ
x2ˉ
x2ˉ
x3ˉ
x3ˉ
x3ˉx3ˉ
x3ˉ
x3ˉ
x2ˉ
x3ˉ
x3ˉ
x3ˉx2ˉ x1ˉ x3ˉ
x3ˉx2ˉ
x1ˉ x3ˉ
x3ˉ x2ˉ
x3ˉ
x3ˉx2ˉ
x1ˉ x3ˉ
x3ˉ x2ˉ
*2,一般的布尔代数的布尔表达式的范式,
< B,∨,∧,ˉ> 是布尔代数,含有变元 x1,x2,…,x n 的布尔表
达式 E(x1,x2,…x n),
1),小项, 是由 n个变元和 B中元素构成的如下形式,称为小
项,
其中
Cδ1δ2...δn为 B中元素,我们称之为小项的系数,
例如 B={0,1,a,b},下面就是 E(x1,x2,x3)中的小项,
2),布尔表达式 E(x1,x2,...xn)的 析取范式,
含有变元 x1,x2,…,x n 的布尔表达式 E(x1,x2,…x n),如果写成
如下形式, A1∨ A2∨,..∨ Am(m≥1)
其中每个 Ai (1≤i≤m)都是有 n个变元的小项, 则称此式是
E(x1,x2,…x n)的析取范式,
nxxxC n ~...~~ 21.,,21 ???????
）（或 nixxxx iiii ???? 1~~
)1(),(),( 321321321 xxxxxxbxxxa ?????????
E(x1,x2,…x n)写析取范式形式,
)]1,1,.,,1,1(...[
)]0,1,.,,1,1(...[
...)]1,0,.,,0,0(...[
)]0,.,,0,0(...[
.,,,
))]}.,,,,1,1([)].,,,,0,1({[
))]}.,,,,1,0([)].,,,,0,0({[
))]}.,,,,1,1(()).,,,,0,1([({
))]}.,,,,1,0(()).,,,,0,0([({
)),.,,,,1((),.,,,,0((),.,,,(
21
21
121
21
321321
321321
32321
32321
212121
Exxx
Exxx
Exxxx
Exxx
xxExxxxExx
xxExxxxExx
xxExxxExx
xxExxxExx
xxExxxExxxxE
n
n
nn
n
nn
nn
nn
nn
nnn
????
?????
???????
??????
?
?????
???????
????
??????
????
?
类似地,E(x1,x2,…x n)的合取范式为,
E(x1,x2,…x n)=(x1∨ x2∨,..∨ xn ∨ E(0,0,…,0)) ∧
(x1∨ x2∨,..∨ xn-1∨ ∨ E(0,0,…0,1)) ∧,.,∧
( ∨ ∨,..∨ ∨ xn∨ E(1,1,…,1,0)) ∧
( ∨ ∨,..∨ ∨ E(1,1,…,1))
其中
E(0,0…,0),E(0,0,…0,1),…,E(1,1,…1,0) 和 E(1,1,…,1)
就是所谓的“系数”,
实际上,求 E(x1,x2,…x n)的析取或者合取范式时,就是求这
些“系数”,
xnˉ
x1ˉ x2ˉ
xnˉ
x1ˉ x2ˉ
xn-1ˉ
已知 <B,∨,∧,ˉ>是布尔代数,其中 B={0,a,b,1}
分别求出下面布尔表达式的析取范式和合取范式,
解, 先求四个系数,
析取范式为,
))(())((),( 212121 axxbxxxxE ??????
0)0()0())1(1())11(()1,1(
0)00()1())0(1())01(()0,1(
)1()0())1(0())10(()1,0(
)01()0())0(0())00(()0,0(
?????????????
???????????
???????????
???????????
abababE
babE
bababE
bbabE
)()(
)0()0()()(
)1,1(())0,1((
))1,0(())0,0((),(
2121
21212121
2121
212121
bxxbxx
xxxxbxxbxx
ExxExx
ExxExxxxE
??????
????????????
?????
???????
合取范式为,
)0()0()()(
))1,1(())0,1((
))1,0(())0,0((),(
21212121
2121
212121
????????????
?????
???????
xxxxbxxbxx
ExxExx
ExxExxxxE
第八章 图论
1.掌握图的基本概念,(特别注意相似的概念 )
2.熟练掌握图中关于结点度数的定理, (会应用 )
3.无向图的连通性的判定,连通分支及连通分支数的概念,
4.有向图的可达性,强连通,单侧连通和弱连通的判定, 求强
分图,单侧分图和弱分图,
5.会求图的矩阵,
6.会判定欧拉图和汉密尔顿图,
*7.会判定平面图,掌握欧拉公式,
*8.了解对偶图,
9.掌握树的基本定义,v和 e间的关系式,会画生成树,会求最
小生成树,根树的概念,完全 m叉树的公式,会画最优树,
*会设计前缀码,
一,图的概念
图的定义,有向边,无向边,平行边,环
邻接点,邻接边,孤立结点
有向图,无向图,简单图,混合图,零图,平凡图,多重图,
完全图,子图,生成子图,补图,
结点的度,结点的出度,结点的入度,
图的最大度 Δ(G),最小度 δ(G),
图所有结点度数总和与边的关系,出度和与入度和关系
图的同构
二,路与回路
路,回路,迹,闭迹,通路,圈
无向图的连通性,连通图,连通分支,连通分支数 W(G),
点割集,割点,点连通度 k(G),
边割集,割边 (桥 ),边连通度 λ(G)
结点间的距离,图的直径
有向图的连通性,可达性,
强连通,单侧连通,弱连通,强分图,单侧分图,弱分图,(会
求这些分图 )
三,图的矩阵
邻接矩阵 A:结点与结点之间的邻接关系矩阵,
根据邻接矩阵判断,各结点的度,有向图结点出,入度,
由 Ak可以求一个结点到另一个结点长度为 k的路条数,
可达矩阵 P:结点 u到结点 v的可达性的矩阵,
用 P可以判定,各结点的度, 有向图的强分图,
关联矩阵 M:是结点与边的关联关系矩阵,
用 M判定,各结点的度
四,欧拉图与汉密尔顿图 (会判定 )
欧拉路,欧拉回路,欧拉图,
判定,有欧拉路的充要条件,无或有两个奇数度的结点,
有欧拉回路的充要条件,所有结点度数均为偶数,
汉密尔顿路,汉密尔顿回路,汉密尔顿图
汉密尔顿图的判定,
必要条件,V的任何非空子集 S,有 W(G-S)≤|S|
充分条件,每对结点的度数和 ≥|V| =n
*五,平面图
平面图的定义,平面的边界,
欧拉公式, v-e+r=2
判定,必要条件, e≤3v-6
*充要条件,G不含与 K5或 K3,3在 2度结点内同构子图,
*六,对偶图与着色
会画对偶图,会对图正常着色,
*七, 二部图 作为一般了解,掌握 K3.3
八,树与生成树
树的定义,6个定义,其中最主要的是连通无回路,e=v-1
分支结点,叶结点
会求最小生成树
九, 根树
m叉树,完全 m叉树,(m-1)i=t-1
会画最优树,*会设计前缀码
练习题
1.请画出 K5 的所有不同构的生成树。
解, K5的生成树 T边数为 4,T的度数和为 8
2.一棵完全二叉树有 e条边,t个叶结点，请推导出 e与 t
的关系式。
解,根据完全 m叉树的公式,(m-1)i=t-1
得分支结点数 i=t-1 又根据树中 e=v-1 v是结点数,
所以 e=(i+t)-1=t-1+t-1=2t-2
?
? ?
? ?
?
? ?
? ?
?
? ?
? ?
?
? ?
? ?
(11114) (11123) (11222)
3.今有 a,b,c,d,e,f,g七个人,已知下列事实,
a:会讲英语, b:会讲英语和汉语,
c:会讲英语,意大利语和俄语 d:会讲日语和汉语,
e:会讲德语和意大利语 f:会讲法语,日语,俄语
g:会讲法语和德语,
试问能否将这七个人适当安排座位,使得每个人都能和他
两边的人 直接交谈?若能,请给予安排,若不能,说明理由,
解, 以 a,b,c,d,e,f,g为结点,如果两个
人之间讲同一种语言,则它们之间
连一条直线,得到右图,
从此图中找到 H回路, abdfgeca
按照此回路坐成一个圆圈,就可以
使得每个人都可以和它两边的人直接交谈,
e?
a?
?b
?c
?d
g?
f?
4,下面序列哪些可以构成一个无向连通图的结点度数序
列?哪些不能?哪些可以构成连通简单图?哪些可能构成
欧拉图?哪些可能构成汉密尔顿图?哪些可能是完全图?
哪些可能是树?如果能,请画出一个那样的图, 如果不能
请说明原因,
a.(1,2,3,3) b.(3,3,3,3) c.(1,1,1,1,2,4)
d.(2,3,3,4,4) e.(2,3,4,4,5) f.(2,2,2,2,4)
解,a.(1,2,3,3) 不能构成 无向连通图的结点度数序列,
因为此序列中有三个奇数,不附和握手定理,
b.(3,3,3,3) 可以是个完全图 K3,是个 H图,
c.(1,1,1,1,2,4) 可以是棵树,
d.(2,3,3,4,4) 构成 无向连通图的
结点度数序列,是个 H图,
??
? ?
? ? ?? ??
??
? ?
?
e.(2,3,4,4,5)可构成连通图的结点序列,但不是简单图,5个
结点中有一个结点度为 5,所以不是有环,就是有平行边,
f.(2,2,2,2,4)是个欧拉图,
??
? ?
?
??
? ?
?
??
? ??
模 拟 试 题 (网络学院 ) 2002.1
离 散 数 学 试 卷
班级, 学号 姓名,
总分 1 2 3 4 5 6 7 8 9 10
一,(12分 )试将下面命题符号化。
1.仅当天不下雨且我有时间，才上街。
2.如果小张出差，那么小王和小李两人中要有一个出差。
3.每个大学生都爱好一些文体活动。
(S(x):x是大学生,L(x,y):x爱好 y,C(x):x是文娱活动，
P(x):x是体育活动。 )
4.没有大学生不懂外语。 ( S(x):x是大学生,K(x,y):x
懂得 y,F(x):x是外语。 )
二,(6分 )写出下面命题公式 (P→Q)→P 的主合取范式。
三,(6分 )求下面谓词公式的真值。要求有解题的过程。
?x(P?Q(x))∨ R(a),其中 P:2>1,Q(x):x≤3,R(x):x>5,
a:5,论 域 为 {-2,6}.
四,(6分 )令全集 E={Φ,{Φ}},P(A)表示 A的幂集,分别计算,
1,P(Φ)?P({Φ})
2,P(A)?P(~A)
3,P(E)-P(~{{Φ}})
五,(12分 )用谓词逻辑推理证明下面推理的有效性。
（要求按照谓词逻辑推理格式，书写推理过程。）
六,(16分 )已知 R1,R2是集合Ａ上的等价关系，问 R1∪R 2、
R1∩R 2, R1-R2, r((A× A)-R1)中哪些是 A上的等价关
系？如果不是说明理由,或举反例。如果是请给予证明
七,(10分） R是实数集合，给定 R上的五个关系如下,
R1={<x,y>|x=y2} R2={<x,y>|y=x+6}
R3={<x,y>|y=(x-1)-1} R4={<x,y>|y=2x}
R5={<x,y>|x2+y2=4}
上述五个关系中，哪些是从 R到 R的函数。如果是函数，
说明它是属于什么类型的（指满射、入射、双射）。
如果不是函数，说明理由 。
”表示否定其中,????????
???????
))()(())()((
) ) ),()(()(() ) ),()(()((
xBxAxxDxAx
xDxCxAxxCxBxAx
八,(12分 )给定集合Ｇ＝ {x|x是有理数且 x≠1},在Ｇ上
定义二元运算 *如下：
对任何 a,b∈ Ｇ a*b=a+b-ab
求证 <Ｇ,*>是个交换群。
九,(12分 )
1.请画出 K5 的所有不同构的生成树。
2.一棵完全二叉树有 e条边,t个叶结点，请推导出 e与 t
的关系式。
*3.今有 a,b,c,d,e,f,g七个人,已知下列事实,
a:会讲英语, b:会讲英语和汉语,
c:会讲英语,意大利语和俄语 d:会讲日语和汉语,
e:会讲德语和意大利语 f:会讲法语,日语,俄语
g:会讲法语和德语,
试问能否将这七个人适当安排座位,使得每个人都能和他
两边的人 直接交谈?如果能,请给予安排,如果不能,说明
理由,
*4,下面序列哪些可以构成一个无向连通图的结点度数序
列?哪些不能?哪些可以构成连通简单图?哪些可能构成
欧拉图?哪些可能构成汉密尔顿图?哪些可能是完全图?
哪些可能是树?如果能,请画出一个那样的图, 如果不能
请说明原因,
a.(1,2,3,3) b.(3,3,3,3) c.(1,1,1,1,2,4)
d.(2,3,3,,4,4) e.(2,3,4,4,5) f.(2,2,2,2,4)
*5 给定一组权值,1,3,5,2,7,1,8,6,9,2,画最优树。
十,(10分 )给定集合如下：
A1={1,2,4,8,16} A2={1,2,3,5,6,10,15,30}
A3={1,2,3,5,30} A4={1,2,3,5,10,15,30}
A5={1,2,3,4,9,36} 令 ≤ 是上述集合上的整除关系。
1.请分别画出各个偏序集 <Ai,≤> 的哈斯图 (i=1,2,3,4,5)
2.用, √, 表示, 是,,用, ×,表示, 否, 填下表。
<A1,≤> <A 2,≤> <A 3,≤> <A 4,≤> <A 5,≤>
分配格
有补格
布尔格
补充题型
一,填空
1.设 A,B是集合,且 |A|=m,|B|=n,则 |A× B|=( ),可以构造
( )个从 A到 B的二元关系, 其中有 ( )个是从 A到 B的
函数, 在 ( )条件下,有从 A到 B的入射函数,有 ( )
个入射函数 ; 在 ( )条件下,有从 A到 B的双射函数,
有 ( )个双射函数,
2.A(P,Q,R)是个永真的命题公式,则 A(P,Q,R)的主析取范
式中有 ( )个小项,
3.A(P,Q,R)是个命题公式,如果 A(P,Q,R)的主析取范式中
有 k个小项,则它的主合取范式中有 ( )个大项,
4.一个图是欧拉图,当且仅当它的所有结点的度 ( ).
5.一棵完全 m叉树,有 t个叶结点,则它有 ( )分支结点,
二,判断下面命题的真值,并说明理由,或举反例,
1,R和 S都是 A上关系，
a) R和 S都自反，则 R?S也 自反。
b) R和 S都反自反，则 R?S也反自反。
c) R和 S都对称，则 R?S也对称。
d) R和 S都传递，则 R?S也传递。
2.如果 A∈ B,B?C，则 A?C。
3,(A-B)∪ (A-C)=A 当且仅当 B=C=Φ.
4,含有三个以上元素的链,不是有补格,
5,所有链都是分配格,
6.不是所有格都是有界格,
7.任何两个结点都有边相关联的无向图是完全图,
8.圈就是回路,回路也是圈,
三,给定集合 A={1,2,3}，在 A上定义五个关系如下：
MR1= R2：
R3 ={<1,1>,<1,2>,<2,1>,<2,2>,<3,3>}
R4 =A× A （完全关系） R5=φ （空关系）
1,求复合关系 R1?R2c,2.求 R2的传递闭包 t(R2).
3.用, ∨, 表示, 是,, 用, ×,表示, 否,,填下
表：
自反的 反自反的 对称的 反对称的 传递的
R1
R2
R3
R4
R5
?1
2? ?3
111
011001
4.上述五个关系中，哪些是等价关系？哪些是偏序关系？
哪些是 A到 A的函数?
如果是等价关系,请写出它对 A的商集。如果是偏序关系,
请画出它的哈斯图。如果是函数,请指出它的类型,
四, 名词解释
n元谓词,原子谓词公式,论域,
群中元素的阶,循环群,布尔格,拉格朗日定理,
迹,圈,通路,生成子图,
图 G的 Δ(G),δ(G),k(G),λ(G),W(G),
平面图的欧拉公式,
零图,平凡图,简单图,
*五,设 X={1,2,3} Y={1,2},在 X的幂集 P(X)上定义二元关
系 R如下, 对于任何 A,B∈ P(X),
ARB 当且仅当 A?Y=B?Y
1.画出关系 R的有向图,
2.R是等价关系吗?如果是,请写出商集 P(X)/R,如果不是请
说明原因,
重点掌握的习题,(网络学院 )
1.P8(3),P12(5)(7),P19(7)d)g),(8)c),P23(8)ef,P39(4)d,
2.P60(2),P66(3)b,P78(3),
3.P86(4)(7),P94(5)(7)(9),
4.P109(2),P113(1)(3)(4),P118(1)(2)(3)(5),P127(1),P134(1)
(2)(4)(7),P145(1)(6)(7),
5.P151(1)(3)(5)(6),P156(3),
6.P184(1),P190(3)(5),P197(3),P200(1),P211(3)P221(2)(11)
7.P242(1)(2),P248(2),P252(1),P269(1)(3)
8.P279(2)(5),P287(3)(7),P300(3),P311(1)(2)(3)(6),P317(5)
P321(1)(3),P327(2)(3)(6),P337(1)(2)(3)(5)(8)
9.前边的 模拟题以及补充题,
预 祝
同 学 们 取 得
优异成绩
