离散数学期末复习题
第一章集合论
一、判断题
（1）空集是任何集合的真子集． （ 错 ） （2）???是空集． （ 错 ） （3）?a???{a},a? （ 对 ） （4）设集合A???,则??1,2???2A. ( 对 ） 1,2,?1,2?（5）如果a?A?B，则a?A或a?B． （ 错 ） 解 a?A?B则a?A?B?A?B，即a?A且a?B，所以a?A且a?B （6）如果A∪B?B,则A?B. （ 对 ） （7）设集合A?{a1,a2,a3}，B?{b1,b2,b3}，则
A?B?{?a1,b1?,?a2,b2?,?a3,b3?} （ 错 ）
A
（8）设集合A?{0,1}，则??{??,0?,??,1?,?{0},0?,?{0},1?}是2到A的关
系． （ 对 ） 解 2?{?,{0},{1},A}，
A
2A?A?{??,0?,??,1?,?{0},0?,?{0},1?,?{1},0?,?{1},1?,?A,0?,?A,1?}
（9）关系的复合运算满足交换律． （ 错 ） （10）?????是集合A上的关系?具有传递性的充分必要条件. （ 错 ）
~也是A上的传递关系（11）设?是集合A上的传递关系,则?. ( 对 )
（12）集合A上的对称关系必不是反对称的. （ 错 ） （13）设?1,?2为集合A上的等价关系, 则?1??2也是集合A上的等价关系( 对 ) （14）设?是集合A上的等价关系, 则当?a,b???时， [a]??[b]? ( 对 )
（15）设?1,?2为集合 A 上的等价关系, 则
( 错 )
二、单项选择题
（1）设R为实数集合，下列集合中哪一个不是空集 （ A ） A. x|x?1?0,且x?R B．x|x?9?0,且x?R C. ?x|x?x?1,且x?R? D. x|x??1,且x?R
2?2??2???1
（2）设A,B为集合，若A\\B??，则一定有 （ C ） A. B?? B．B?? C. A?B D. A?B
（3）下列各式中不正确的是 （ C ） A. ??? B．????? C. ??? D. ????,{?}?
（4）设A??a,{a}?，则下列各式中错误的是 （ B ） A. ?a??2A B．?a??2A C. ?{a}??2A {a}??2A D. ?（5）设A??1,2?，B??a,b,c?，C??c,d?，则A?(B?C)为 （ B ） A. ??c,1?,?2,c?? B．??1,c?,?2,c?? C. ??1,c?,?c,2?? D. ??c,1?,?c,2??
（6）设A??0,b?，B??1,b,3?，则A?B的恒等关系为 （ A ） A. ??0,0?,?1,1?,?b,b?,?3,3?? B．??0,0?,?1,1?,?3,3?? C. ??0,0?,?b,b?,?3,3?? D. ??0,1?,?1,b?,?b,3?,?3,0?? （7）设A??a,b,c?上的二元关系如下，则具有传递性的为 （ D ） A. ?1???a,c?,?c,a?,?a,b?,?b,a?? B． ?2???a,c?,?c,a??
C. ?3???a,b?,?c,c?,?b,a?,?b,c?? D. ?4???a,a??
（8）设?为集合A上的等价关系，对任意a?A，其等价类?a??为 （ B ） A. 空集； B．非空集； C. 是否为空集不能确定； D. {x|x?A}. （9）映射的复合运算满足 （ B ） A. 交换律 B．结合律 C. 幂等律 D. 分配律 （10）设A，B是集合，则下列说法中（ C ）是正确的. A．A到B的关系都是A到B的映射 B．A到B的映射都是可逆的 C．A到B的双射都是可逆的
D．A?B时必不存在A到B的双射
2
（11）设A是集合，则（ B ）成立. A．#2?2AA#A
B．X?2?X?A C．????2A D．?A??2A
（12）设A是有限集（#A?n），则A上既是?又是～的关系共有（ B ）. A．0个 B．1个 C．2个 D．n个 三、填空题
1. 设A?{1,2,{1,2}}，则2?____________.
填2A?{?,{1},{2},{{1,2}},{1,2},{1,{1,2}},{2,{1,2}},A}
2.设A?{?,{?}}，则2= . 填2A?{?,{?},{{?}},A} 3. 设A,B 都是有限集，#A?7,#B?5，则可以定义_____________个不同的A到B的关系，可以定义_______________个不同的A到B的映射. 填235,4.设集合A?{x|1?x?100,x是4的倍数，x?Z}，
A
A57
B?{x|1?x?100,x是5的倍数，x?Z}，则A?B中元素的个数为 .40 5.设 A?{a,b}, ? 是 2 上的包含于关系，,则有
?= . {??,??,??,{a}?,??,{b}?,??,A?,?{a},{a}?,?{a},A?,?{b},{b}?,?{b},A?,?A,A?} 6.设?1,?2为集合 A 上的二元关系, 则?1??2? .?2??1 7.集合A上的二元关系?为传递的充分必要条件是 ．????? 8. 设集合A??0,1,2?上的关系?1???0,2?,?2,0??及集合A到集合B??0,2,4?的关系?2?｛?a,b?|?a,b??A?B且a,b?A∩B?,则?1??2?___________________. 填 {?0,0?,?0,2?,?2,0?,?2,2?} 四、解答题
1. 设 A?{a,b,c,d},A上的关系
~~A
??{?a,a?,?b,b?,?c,c?,?d,d?,?a,b?,?b,a?,?c,d?,?d,c?} （1）写出?的关系矩阵；
（2）验证?是A上的等价关系；
（3）求出A的各元素的等价类。 解 （1）?的关系矩阵为
3
?1??1 M???0??0?又由于
110000110??0? ?1?1??（2）从?的关系矩阵可知：?是自反的和对称的。
?1100??1100??1100????????1100??1100??1100? M??M????????M? ???001100110011???????0011??0011??0011???????或?????满足????? 所以?是传递的。
因为?是自反的、对称的和传递的，所以?是A上的等价关系。 （3） [a]?[b]?{a,b}，[c]?[d]?{c,d} 2. 设A?{1,2,3,4,6,12}，?为A上的整除关系 （1）写出?的关系矩阵M? （2）画出?A,??的哈斯图
（3）求子集B?{2,3,6}的最小上界lubB和最大下界glbB
?111111????010101??001001?? 解：（1）M????000100??000010????000001???（2）
（3）lubB=6, glbB=1
五、证明题
1. 设?1,?2为集合A上的等价关系, 试证?1??2也是集合A上的等价关系。
4
证明：由于?1,?2是自反的，所以对任意a?A,?a,a???1,?a,a???2, 因而
?a,a???1??2，即?1??2是自反的。
若?a,b???1??2，则?a,b???1,?a,b???2,由于?1,?2是对称的，所以?b,a???1,?b,a???2, 从而?b,a???1??2，即?1??2是对称的。 若，则 ?a,b?,?b,c???1??2?a,b?,?b,c???1,?a,b?,?b,c???2,由于?1,?2是传递的，所以?a,c???1,?a,c???2, 从而?a,c???1??2，即?1??2是传递的。 由于?1??2是自反的、对称的和传递的，所以?1??2是等价关系。
第二章 代数系统
一、判断题
（1）集合A上的任一运算对A是封闭的． （ 对 ） （2）代数系统的零元是可逆元. （ 错 ） （3）设A是集合，?:A?A?A，a?b?b，则?是可结合的． （ 对 ） （4）设a,b是代数系统?A,??的元素，如果a?b?b?a?e(e是该代数系统的单位元），则
a?1?b. ( 对 )
（5）设a,b是群?G,??的元素,则(a?b)?1?a?1?b?1. （ 错 ） （6）设?G,??是群．如果对于任意a,b?G，有 (a?b)2?a2?b2，则?G,??是阿贝尔群． （ 对 ） （7）设?L,?,??是格,则运算?满足幂等律. （ 对 ） （8）设集合A?{a,b}，则?{?,{a},{b},A},?,??是格． （ 对 ） （11）<{0，1，2，3，4}，max，min>是格． （ 对 ） （9）设?B,?,?,?是布尔代数，则?B,?,??是格． （ 对 ） （10）设?B,?,?,?是布尔代数，则对任意a,b?B，有
a?b?a?b． （ 对 ） 二、单项选择题
（1）在整数集Z上，下列哪种运算是可结合的 （ B ）
a,b} A. a?b?a?b B．a?b?max{C. a?b?a?2b D. a?b?|a?b|
（2）下列定义的实数集R上的运算 * 中可结合的是. （ C ）
A．a?b?a?a?b
5