离散数学-习题集.pdf

《离散数学》习题集 第一部分 判断题 一、第一章—集合 1、( )已知集合A的元素个数为10,则集合A的幂集的基=10 2 。 2、( )已知两个集合A、B,若A 中的元素都是B 中的元素,则记为A∈B。 2、( )已知集合A的元素个数为n,则集合A的幂集P(A)的元素个数为n 2 。 3、( ) 已知两个集合A={Ф,{Ф}},B={Ф},则A∩B={Ф}。 4、( )已知两个集合A={Ф,{Ф}},B={Ф},则A∩B=Ф。 5、( )已知两个集合A、B,若A 中的元素都是B 中的元素,则记为A∈B。 6、( )已知集合A的元素个数为n,则集合A的幂集P(A)的元素个数为n 2 。 7、( )已知集合A的元素个数为n,则A×A的幂集的元素个数为n 2 。 8、( )已知两个集合A、B,则A-B 是由属于B 但不属于A 的元素构成的集合。 二、第二章—二元关系 1、( )若R是A上的二元关系,I A 是A上的恒等关系,则当且仅当I A∈R时,R是A上的自反关系。 2、(√)若R 是集合A 上的二元关系,且当(a,b)∈R且(a,c)∈R 时,就有(b,c)∈R,则R 是A 上的可传递关系。 3、( )设 A 是集合, A 1 、 A 2、... A n 都是 A的非空子集,令 S={A 1 , A 2,... ,A n },则如果 S 是集合 A的一个划分,那么S一定是集合A的一个完全覆盖;反之亦然。 5、( )R 是非空集合A 上的等价二元关系,则A 关于R 的商集A/R 是集合A 的一个划分,但不是A 的一个完全覆盖。 6、( )已知集合 A 有 4元素,易知集合 A 共有 2 4个互不相同的子集合,所以在集合 A 上一共可定义 2 4 个互不相同的二元关系。 7、( )若 R 1 和 R 2 都是集合 A 上的可传递二元关系,则 R 1 ∪ R 2 也是 A 上的传递关系。 8、( )设 R是有限的非空集合 A 上的偏序关系,则 A 必有极大(小)元和最大(小)元。 9、( )若 R 1 和 R 2 都是集合 A 上的相容关系,则 R 1 ∩ R 2 也是 A 上的相容关系。 10、( )若 R 1 和 R 2 都是集合 A 的可传递二元关系,则 R 1 ∩ R 2 也是 A 上的传递关系。 11、( )R是集合A 上的等价关系,商集A/R 是A 的划分,但不是A 的完全覆盖。 12、( )设R 是有限的非空集合A 上的偏序关系,则A 至少有一个最大(小)元。 13、( )R是集合A 上的自反二元关系,则R 的传递闭包仍是A 上的自反关系。 三、第三章—函数 1、设集合A={a,b,c},B={x,y,z,e},R 是A 到B 的二元关系,若R={(a,x) ,(b,y) ,(c,z)}, 则R 的逆关系是B 到A 的函数。 2、设I是整数集合,N是自然数集合,f是I到N的函数,且对任意的整数x ∈I都有f(x)=x 3,则f是I到N的双射函数。 3、若f 是集合A 到B 的双射函数,则f 的逆关系称为f 的逆函数。 4、( )设集合A={a,b,c},B={x,y,z,e},R 是A 到B 的二元关系,若R={(a,x) ,(b,y) ,(c, z)},则R 的逆关系是B 到A 的函数。 5、( )设I是整数集合,N是自然数集合,f是I到N的函数,且对任意的整数x ∈I都有f(x)=x 3,则f是 I到N的双射函数。 6、( )若f 是A 到B 的单射函数,则f 的逆关系即为B 到A 的函数。 7、( )若f 是A 到B 的满射函数,则f 的逆关系必为B 到A 的满射函数。 四、第四章—代数系统 1、( )设(G,*)是代数系统的运算*对G 是封闭的、可结合的,且G 中存在幺元,称(G,*)为群。 2、( )对于代数系统(A,*) ,如果A 中存在幺元,则A 中每个元素都有逆元。 3、( )若(A,*)是群,则在(A,*)运算表中,每一列(行)的元素互不相同。 4、( )含有幺元的半群叫独异点,每个元素都有逆元的独异点称为群。 5、( )对于一个代数系统(A,*) ,若A 中每个元素都有右幺元,则也都有左幺元。 6、( )设(G,*)是12 阶群,则(G,*)必存在2 阶子群。 7、( )设(G,*)是有限群,则在(G,*)的运算表中每一行(列)中的元素都是互不相同的。 8、( )可交换群也称为“阿贝尔群”。循环群必是“阿贝尔群”,反之亦然。 9、( )设(G,*)是有限群, (H,*)是其子群,若|G|=m,|H|=n,则 n 必整除m。 五、第五章—图论 1、( )一个无向连通图是半欧拉图的充要条件是图中至少有两个奇度点。 2、( )在有向树T 中,