《离散数学》试题及答案
一、填空题
1设集合Ａ，B,其中Ａ={1,2,3}, B＝{１,2}, 则A- B＝｛３} ；?ρ(A) - ρ(B）={3},｛1,3｝,｛2,3},{1,2,３}｝.
2n．
2．设有限集合A，|A| = n,则｜ρ(A×Ａ)| =2
３．设集合A= ｛a,b}, B = {１，2｝,则从Ａ到B的所有映射是α1={(ａ,1), (ｂ，1)｝, α２={（a,2), (ｂ,2)}，α3= {（a,１）,(b,2)｝，α4= {(a,2)，（ｂ，1)}, 其中双射的是α3, α4 .
4.已知命题公式G=?(P→Ｑ）∧Ｒ,则G的主析取范式是（P∧?Q∧Ｒ）
５.设G是完全二叉树,G有７个点,其中４个叶点,则G的总度数为１2,分枝点数为3.
６设A、B为两个集合, A= {1，２,４}, B = {3，４｝, 则从Ａ?B={4｝; A?B＝{１,2,3,4};
A-B= {1,2} ．
7.设R是集合Ａ上的等价关系，则Ｒ所具有的关系的三个特性是自反性, 对称性
传递性.
８．设命题公式G＝?（Ｐ→(Q∧R)),则使公式Ｇ为真的解释有(1,0, 0), （1, 0, 1），(1, 1,0)
9. 设集合A＝{１,2,3，4}, A上的关系R１= {（1,4),(2,3）,(3,2)｝, R2=｛（2,1),(3,2）,(4，3)}, 则Ｒ1?R２=｛(1，３),（2,2），（3,1)} , R2?R1 =
{(2,4),(3,3）,(4,2)｝_R1２={(２，2）,(3,3）．
10. 设有限集A,B,|A| = m, |B｜= n, 则||ρ（A?B)| = .
11设A,Ｂ,R是三个集合,其中R是实数集，A ＝{x | -1≤x≤1, x∈R}, B = ｛x | 0≤x < 2,
x∈R},则A－Ｂ= －1＜＝ｘ<0 ，B-A＝｛x ｜1 ＜x <2，x∈R｝, A∩Ｂ={x | ０≤x≤1, x∈Ｒ} , ．
13.设集合A={2, 3，４,5, 6}，Ｒ是A上的整除关系,则R以集合形式(列举法)记为
{(2, 2)，（2,4)，(2，6）,（3, 3）,（3,6）,(4, 4),（５，5),（6,6)｝. １4. 设一阶逻辑公式Ｇ= ?xP（x)→?xQ(x)，则G的前束范式是?x(?P(x)∨Ｑ(x)). 15．设G是具有８个顶点的树，则Ｇ中增加21 条边才能把G变成完全图。(完全图的
边数2
)1(-n n ，树的边数为n －1） 16. 设谓词的定义域为{a , b ｝,将表达式?x Ｒ(x)→?ｘＳ(x)中量词消除 ,写成与之对应的命题公式是_ （Ｒ(a)∧Ｒ(ｂ))→(S （a)∨S(b ）) _．
17． 设集合A ＝｛1, 2, ３, ４},A 上的二元关系R ＝{(1,1)，(1,2)，(2，3)}, Ｓ＝{(1,３),（２,3),(３,2)}。则R ?S ＝ ｛（1, 3）,(2, 2)} ,
R 2＝ {(１， １）,（１, 2)，（1, 3)}．
二、选择题?
1 设集合A={2,{a}，3,4}，B = {｛a},3，4,1}，E 为全集,则下列命题正确的是( C )。 ?(A){2}∈A （Ｂ)｛ａ｝?A (Ｃ）??｛{a}}?B ?E (Ｄ）{{a ｝，1,3，4}?B.
2 设集合A ＝{1,2，3},A 上的关系R={(1,１),(2，2),(2,3),(3,2），（3,3)｝，则R 不具备（ D ）.
(A ）自反性? (B)传递性? （Ｃ)对称性? （D)反对称性
3 设半序集(A,≤)关系≤的哈斯图如下所示，若A 的子集B = ｛２，3,4,5｝,则元素6为B 的（ Ｂ ）。 (A)下界? (Ｂ)上界??(Ｃ）最小上界 (D
4 下列语句中，( B )是命题。
?（A)请把门关上 （Ｂ)地球外的星球上也有人
(C ）x + 5 > 6 (Ｄ)下午有会吗?
5 设I 是如下一个解释：D ＝{a,ｂ｝, 0
1 0 1b) P(b,a) P(b,b) P(a,),(a a P 则在解释Ｉ下取真值为1的公式是（ D ).
(A ）?x ?yP （ｘ,y ） (B)?x ?y Ｐ(ｘ,ｙ)? (Ｃ)?xP （x,x) (D)?x ?yP(x,y).
6. 若供选择答案中的数值表示一个简单图中各个顶点的度，能画出图的是( C ).
?(A)(1,２,2,3,4,5) (Ｂ)（1,2，3,4,５,5)? (C ）（1,1,1,2,3) (D)(2,３，3，４,5,６). ７. 设G 、H 是一阶逻辑公式,P 是一个谓词,G ＝?xP(x ）, H ＝?ｘP(ｘ),则一阶逻辑公式G →H 是( C ）.
?(A)恒真的 （B ）恒假的? (C)可满足的 (D)前束范式.
8 设命题公式G ＝?(P →Q)，H ＝P →(Q →?P),则Ｇ与H 的关系是（ A )。
(A)Ｇ?H （B)H ?G ? (Ｃ)G=H (Ｄ)以上都不是.
9 设A ， B 为集合，当（ D )时A －Ｂ=Ｂ.
?(Ａ)Ａ=B ?(Ｂ)A ?B ?(C)B ?A (D)A=Ｂ=?.
10 设集合A ＝ {1,2,3,4｝, A 上的关系R ＝{(1，1)，(２,３),(2,4),（3,4)}， 则R 具有( B ）。
?(Ａ)自反性? （Ｂ)传递性??(C ）对称性 (D)以上答案都不对
１1 下列关于集合的表示中正确的为( B ）。
?（A ）｛ａ}∈{a,ｂ,c} (B){a ｝?{ａ，ｂ,ｃ}?(C ）?∈{a,ｂ，ｃ｝ (D)｛a,ｂ}∈{a ，b,ｃ} 12 命题?xG （x)取真值1的充分必要条件是（ Ａ ）.
(A) 对任意x,G(x ）都取真值1. (B)有一个ｘ0,使Ｇ（ｘ0)取真值1.
(C)有某些ｘ，使G （x ０)取真值1． (D ）以上答案都不对.
１3. 设G 是连通平面图，有5个顶点，6个面,则Ｇ的边数是（ Ａ ). ?(Ａ) 9条 （B) 5条? （Ｃ) 6条 (D) 1１条.
1４． 设Ｇ是5个顶点的完全图，则从G 中删去( A )条边可以得到树．
?（Ａ)6 (B)5 (C ）1０
(D)4. 15. 设图G 的相邻矩阵为???????
?????????01101101
01110110010111110，则Ｇ的顶点数与边数分别为( D ）． ?(A ）4， ５ (B)5, 6? ?（C)４， 10 （D)5, ８.
三、计算证明题
1.设集合Ａ={1, ２, 3， 4, 6, 8, 9, １２｝,Ｒ为整除关系。
(1) 画出半序集（A,R)的哈斯图；
(2) 写出A 的子集B = {3,6,9,12}的上界，下界，最小上界,最大下界;
(3) 写出Ａ的最大元，最小元，极大元，极小元。
解：(1） 12
4
8
36129
（2） Ｂ无上界,也无最小上界。下界1, 3； 最大下界是3
（3） Ａ无最大元,最小元是1，极大元８, 12， ９; 极小元是1
2. 设集合A=｛1, ２, 3, 4}，Ａ上的关系Ｒ＝｛(ｘ,ｙ） | x, y ∈Ａ 且 x ≥ ｙ}, 求
(1) 画出R 的关系图；
(2) 写出R 的关系矩阵.
解：(1）
（２)1000110011101111R M ??????=??????
3. 设R 是实数集合，σ,τ,?是Ｒ上的三个映射,σ（x) = x+３, τ（x) = 2x, ?(x) = ｘ/4，试求
复合映射σ?τ，σ?σ, σ??， ??τ，σ???τ．
解：
(1)σ?τ=σ(τ（x))=τ(x)+３=2x ＋3=２x ＋3.
(２）σ?σ=σ(σ(x))=σ（x ）+3＝（x+3)+３＝x ＋６,
（3)σ??＝σ(?(x))=?（x)＋3=x/4＋3,