《离散数学》单元测试(集合论)
3.1集合的基本概念
1.设A、B、C是集合,确定下列命题是否正确,说明理由。
(1)Ф⊆Ф
(2)Ф∈Ф
(3)Ф⊆{Ф}
(4)Ф∈{Ф}
(5)如果A∈B与B⊆C,则A⊆C
(6)如果A∈B与B⊆C,则A∈C
(7)如果A⊆B与B∈C,则A∈C
(8)如果A⊆B与B∈C,则A⊆C
2.有n个元素的集合A的幂集ρ(A)的元素个数为多少?求下列集合的幂集合。
(1)Ф
(2){Ф}
(3){Ф,{Ф}}
(4){a,b}
(5){a,b,{a,b}}
(6){1,{1},2,{2}}
3.2 集合的运算
1.设A,B是两个集合,A={1,2,3},B={2,3,4},则B-A= ,ρ(B)-
ρ(A)= 。
2.全集E={a,b,c,d,e},A={a,d},B={a,b,e},C={b,d},求
,ρ(A)∩ρ(B)
A B C=
()
= 。
3.下列命题正确的是()。
A.φ∩{φ}=φB.φ∪{φ}=φC.{a}∈{a,b,c} D.φ∈{a,b,c}
4.确定下列各式的值:
Ф∩{Ф}=
{Ф,{Ф}}-Ф=
{Ф,{Ф}}-{Ф}=
6.证明下列各等式:
A∩(B-A)=Ф
A∪(A∩B)=A
3.3 有穷集合的计数问题
掌握文氏图和容斥原理求解有穷集合的计数问题的方法,并会简单应用。
以教材的示例为基础。
第4章 二元关系
4.1二元关系的定义、表示方法与特性
1. A 和B 是任意两个集合,若序偶的第一个元素是A 的一个元素,第二个元素是B 的一个
元素,则所有这样的序偶集合称为集合A 和B 的 , 记作A ⨯B ,即A ⨯B= 。
A ⨯B 的子集R 称为A 到B 的一个 。
若|A|=m , B|=n ,则A 到B 共有 个不同的二元关系。
2. 设集合A ={a,b},B ={x,y},求笛卡尔乘积A ×B,B ×A,,A ×ρ(B)。
3. 证明:
(1) (A ∩B)×C=(A ×C)∩(B ×C)
(2) (A ∪B)×C=(A ×C)∪(B ×C)
4. 设A={a,b},B={x,y},则从A 到B 的二元关系共有多少个?请分别列出。
5. 设集合A={a,b,c,d},B={1,2,3},R 是A 到B 的二元关系,R={<a,1>,<a,2>,<b,2>,<c,3>,<d,1>,<d,3>},写出R 的关系矩阵和关系图。
6. 设集合 A={1,2,3},A 上的关系R={<1,1>, <1,2>, <2,2>, <3,3>, <3,2>},则R 不具备( )。
A 自反性 B. 反自反性 C. 对称性 D. 反对称性 E. 传递性
7.
设集合A={a,b,c},R 是A 上的二元关系,R={〈a,a 〉,〈a,b 〉,〈a,c 〉,〈c,a 〉},那么R 具备( )。
A 自反性 B. 反自反性 C. 对称性 D. 反对称性 E. 传递性 4.2 关系的运算(合成、逆运算、闭包运算)
1. 集合A={a 1,a 2,a 3},B={b 1,b 2,b 3,b 4},C={c 1,c 2,c 3,c 4};
R 是A 到B 的二元关系,R={<a 1,b 2>,<a 1,b 3>,<a 2,b 1>,<a 2,b 4>,<a 3,b 3>};
S 是B 到C 的二元关系,S={<b 1,c 1>,<b 1,c 2>,<b 2,c 3>,<b 3,c 4>,<b 4,c 4>}。
求复合关系R оS 。
2. 设集合{1,2,,10}A = ,A 上的二元关系R={<x,y>|x,y ∈A,x+3y=12},试求R n 。
3. 设R ,S 是二元关系,证明:111)(---=R S S R 。
4. 集合},,,{d c b a R =,R 是集合A 上的关系,{,,,,,}R a b b a b c =<><><>,求
)(),(),(R t R s R r ,并分别画出它们的关系图。
4.3 等价关系及划分
1. R 是集合A 上的二元关系,如果关系R 同时具有 性、 性
和 性,则称R 是等价关系。
2. R 是集合A={a ,b ,c ,d ,e ,f }是上的二元关系, R={〈a ,d 〉,〈d ,a 〉,〈a ,e 〉,〈e ,a 〉,
<d ,e>,<e ,d>,<b ,f>,<f ,b>}∪I A
(1) 画出R 的关系图,判断R 是否为等价关系;
(2) 如果是等价关系,则求A 中各元素的等价类,并写出A/R ;否则说明原因。
3. 集合A={a,b,c,d,e,f,g},划分л={{a,c,e},{b,d},{f,g}},求划分л所对应的等价关系R 的关系图表
示。
4. 集合A={1,2,3,4,5},求下列等价关系所对应的划分。
(1) R 是A 上的全域关系(即R=A ×A )。
(2) R 是A 上的相等关系(即R={〈1,1〉,〈2,2〉,〈3,3〉,〈4,4〉,〈5,5〉})。
(3) R 是A 上模2同余关系。
4.4偏序关系
1. 设集合},,,,{e d c b a A =上的关系R 为
{,,,,,,,,,,,,,,R a a b b c c c d d d d e e c e e =<><><><><><><><>
,写出R 的关系矩阵,画出R 的关系图,说明R 是不是偏序关系?
2. 设集合}24,12,8,6,4,3,2{=A ,R 为A 上的整除关系,
(1) 画出偏序集<A , R>的哈斯图;
(2) 写出集合A 中的最大元、最小元、极大元、极小元;
(3) 写出A 的子集}12,6,3,2{=B 的上界、下界、最小上界、最大下界。
4. <A,R>是偏序集,A={a,b,c,d,e},图示为其关系图,试将关系图改画成哈斯图。
5. (A,R )是偏序集,图示为其哈斯图,试写出R 的关系矩阵。
4.5 函数的定义和特殊函数类
1. 集合A={x,y,z},B={1,2,3},试说明下列A 到B 的二元关系中,哪些能构成函数?
(1) {<x,1>,<y,1>,<z,1>}
(2){<x,2>,<y,3>}
(3){<x,3>,<y,2>,<z,3>,<y,3>}
(4){<x,2>,<y,1>,<y,2>}
2.下列函数,哪些是单射函数、满射函数、双射函数?
A.f:N→N,f(n)=2n
B.f:I→I,f(i)=|i|
C.f:A→B,A={0,1,2},B={0,1,2,3,4,} ,f(a)=a2
D.f:R→R,f(r)=r+1
3.设E={a,b,c,d},A={a,d},则A的特征函数ΨA为。
4.设A={a,b,c},B={1,2,3},则:
(1)A到B共可产生个不同的函数。
(2)A到B共可产生个不同的双射函数。