离散数学
作业要求：
（1）禁止用附件提交作业。
附件提交的作业计0分。
（2）作业按题号顺序作答，乱序、不写题号等视情况扣分。
（3）选择题直接提交答案，不要抄题。
（4）卷面整洁，文字、符号以及图等要清晰可辨。
一、单选题（每题2分，共15小题）
1.集合}}}{{},{,{c b a A =，则下列不属于A 的子集的是（ ）
A.}}{{a
B.}}{{b
C.}}}{{{c
D.}}{,{b a
2.设全集{1,2,...,9,10}U =的子集为A={偶数}，B={奇数}，则下列选项正确的是（ ）
A.A
B =∅ B.A
B =∅ C.A B U =
D. 以上答案都不对
3.已知集合}4,3,2,1{=A ， },,{c b a B =， }8,6,4,2,1{=C ,定义A 到B 的关系c)}(4,b),(3,a),(2,a),{(1,1=ρ，B 到C 的关系(c,1)}(b,6),{(a,4),2=ρ，则下列属于21ρρ的是（ ）
A.)8,1(
B.)4,1(
C.)6,2(
D.)1,3(
4.集合}3,2,1{=A 上的关系)}3,1(),1,2(),2,1{(=R ，则R 具有（ ）
A.对称性
B.自反性
C.可传递性
D.以上说法都不对
5.集合{1,2,3}A =上的下列关系，是由A 到A 的函数的是（ ）
A.{(1,3),(2,3),(3,1)}f =
B.{(1,2),(3,1)}g =
C.{(1,1),(2,1),(3,2),(1,3)}h =
D.{(1,3),(2,1),(2,2)}I =
6.集合},,{},3,2,1{c b a B A ==，则A 到B 的映射中，是单射的是（ ）
A.}b)b)(3,a)(2,(1,{
B.}b)b)(3,a)(1,(1,{
C.}c)b)(3,a)(2,(1,{
D.}b)b)(3,b)(2,(1,{
7. 下面各集合都是N 的子集，（ ）集合在普通加法运算下是封闭的。
A.}16|{整除的幂可以被x x
B.}5|{互质与x x
C.}30|{的因子是x x
D.}30|{<x x
8.设集合A={1，2，3，4，5}上偏序关系图为，
则子集B={2，3，4}的最大下界为（ ）
A.1
B.4
C.5
D.无
9.设,L <≤>是格，则对任意12,l l L ∈，有（ ）
A.12212()()l l l l l ∨=⇔≤
B.12212()()l l l l l ∧=⇔≤
C.12112()()l l l l l ∨=⇔≤
D. 以上答案都不对
10. 设图G 的相邻矩阵为⎥⎥
⎥
⎥⎥
⎥
⎦
⎤
⎢⎢⎢⎢⎢⎢⎣⎡0110110101110110010111110，则G 的顶点数与边数分别为（
） A.5,4
B.6,5
C.10,4
D.8,5
11. 无向简单图>=<E V G ,，},,,,{54321v v v v v V =，则||E 的最大值是（
）
A.8
B.10
C.12
D.16
12.在如下各图中是欧拉图的是（ ）
13. Q P ,是真命题，R 是假命题，则（ ）
A.R Q P ∧→为真
B.Q P R ∨→为真
C.R P Q ∨→为假
D.P Q R ∧→为假
14.设是乌鸦x :P(x )，一样黑y x ,:y),Q(x ，则命题“天下乌鸦一般黑”可符号化为（
）
A.),()(y x Q x xP →∃
B.),()()(y x Q y P x P →∨
C.),())()()(((y x Q y P x P y x →∧∀∀
D.)),()()((y x Q x P x ⌝∧∃⌝
15.谓词公式)())()((x Q y yS x F x →∃∨∀中变元是（ ）。
A. 自由变元
B. 约束变元
C. 既是自由变元也是约束变元
D. 以上答案都不对
二、简答题（每题5分，共6小题）
1.写出集合{,,{}}a a ∅的幂集.
2.设(4,5)}(3,3),(2,4),{(1,2),1=ρ，(5,4)}(4,2),(2,4),{(1,3),2=ρ，试求关系12ρρ的
定义域和值域。
3. 说明什么是等价关系。
4. 请解释什么是群.
5.给定如图所示的图,G V E =<>，求出从A 到E 的所有初级路。
6.用二叉树表示算术表达式()a b c d *+-。
三、证明题（每题10分，共4小题）
1.已知C B g B A f →→:,:，f 是单射，g 是单射，证明gf 是单射。
2.设（L,≤）是一个格， ,,a b c L ∈试证明: 若c b a ≤≤，则 )()()()(c a b a c b b a ∨∧∨=∧∨∧
3. 用推理法证明下式成立：(),,|P Q Q R R P ⌝∧⌝⌝∨⌝-⌝
4.由等值演算证明下列蕴涵式成立: (()())()x y P x Q y xP x ∃∃∧⇒∃。