《离散数学导论》例题和习题
专业：计算机专业独立本科（脱产）
教材：《离散数学导论》徐洁磐著。
一、集合论初步
重点：集合概念、集合运算、幂集和笛卡尔乘积。
1、 求集合A={Ø,a,{a}}幂集。
解：
｛Ø，{Ø}，{a},{{a}},{Ø,a},{Ø,{a},{a,{a}},A}
2、 设A={0，1}，B={1，2}，求：（1）A×B，（2）
×B，（3）（A×B
解：（1）A×B={(0, 1), (0, 2), (1, 1), (1, 2)}
(2)
×B=A×A×B={(0,0,1),(0,0.2),(0,1,1),(0,1,2),(1,0,1),(1,0,2),(1,1,1),(1,1,2)
(3)
（A×B
=(A×B)×(A×B)={(0,1),(0,2),(1,1)(1,2)}×{(0,1),(0,2),(1,1)(1,2)}={(（0,1）,(0,1)),((0,1),(0,2)),((0,1),(1,1)),((0,1),(1,2)),((0,2),(0,1)),((0,2),(0,2)),((0,2),(1,1)),((0,2),(1,2)),((1,1),(0,1)),((1,1),(0,2)),((1,1)(1,1)),(
(1,1),(1,2)),((1,2),(0,1)),( (1,2),(0,2)),( (1,2),(1,1)),( (1,2), (1,2))
３、设Ａ、Ｂ、Ｃ为任新集合，试证：
证：对任意的（
）
,有
且
且
或
，即
且
或
且
或
，故
于是
反之，对任意的
或
即
且
或
且
且
或
故（
）
于是
综上可得
二、关系与映射
重点：关系与复合关系概念；关系的集合表示法，图的表示法和矩阵表示法；关系的五种性质及关系的闭包；偏序关系与哈斯图，相容关系与完全复盖，等价关系与等价类，商集。
4、设X上关系R满足对称性和传递性，问R是否一定满足自反性？并说明理由。
解：X上的关系R满足对称性和传递性时，不一定满足自反性。例如X={1，2，3}上的关系R={（1，3），（3，1），（1，1），（3，3）}满足对称性和传递性。但存在2
X，（2，2）
R。故R不是自反的。
5、设X上的关系
，
满足对称性，证明：如果
则
=
证：
已知
只须证
任取
，则有
X，至少存在一个
X，使
且
，
是对称的 
至少存在一个
X，有
，（
）
（
，
）
，又
（
，
）
，即存在
X，使
，
又
，
是对称的，
，
从而
于是
。
6、设有X上的关系
、
且
。证明：S（
）
S（
）
证：
S（
）=
，S（
）=
要证
。只要证
且
。
任取（a,b）
,
(b,a)
,