《离散数学》试题与答案解析.doc

一、填空题
1 设集合A,B,其中A={1,2,3}, B= {1,2}, 则A - B= {3} ; r(A) - r(B)= {3},{1,3},{2,3},{1,2,3}} .
2. 设有限集合A, |A| = n, 则|r(A×A)| = .
3. 设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是a1= {(a,1), (b,1)}, a2= {(a,2), (b,2)},a3= {(a,1), (b,2)}, a4= {(a,2), (b,1)}, 其中双射的是 a3, a4 .
4. 已知命题公式G=Ø(P®Q)∧R,则G的主析取范式是(P∧ØQ∧R)
,G有7个点,其中4个叶点,则G的总度数为 12 ,分枝点数为 3 .
6 设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从AÇB= {4} ; AÈB={1,2,3,4};
A-B= {1,2} .
设R是集合A上的等价关系,则R所具有的关系的三个特性是自反性, 对称性
传递性.
8. 设命题公式G=Ø(P®(QÙR)),则使公式G为真的解释有(1, 0, 0), (1, 0, 1), (1, 1, 0)
9. 设集合A={1,2,3,4}, A上的关系R1 = {(1,4),(2,3),(3,2)}, R2 = {(2,1),(3,2),(4,3)}, 则 R1·R2 = {(1,3),(2,2),(3,1)} , R2·R1 = {(2,4),(3,3),(4,2)} _ R12 = {(2,2),(3,3).
10. 设有限集A, B,|A| = m, |B| = n, 则| |r(A´B)| = .
11 设A,B,R是三个集合,其中R是实数集,A = {x | -1≤x≤1, xÎR}, B = {x | 0≤x < 2, xÎR},则A-B = -1<=x<0 , B-A = {x | 1 < x < 2, xÎR} ,
A∩B = {x | 0≤x≤1, xÎR} , .
设集合A={2, 3, 4, 5, 6},R是A上的整除关系,则R以集合形式(列举法)记为
{(2, 2),(2, 4),(2, 6),(3, 3),(3, 6),(4, 4),(5, 5),(6, 6)} .
14. 设一阶逻辑公式G = "xP(x)®$xQ(x),则G的前束范式是$x(ØP(x)∨Q(x)) .
,则G中增加 21 条边才能把G变成完全图。(完全图的边数,树的边数为n-1)
16. 设谓词的定义域为{a, b},将表达式"xR(x)→$xS(x)中量词消除,写成与之对应的命题公式是_ (R(a)∧R(b))→(S(a)∨S(b)) _.
17. 设集合A={1, 2, 3, 4},A上的二元关系R={(1,1),(1,2),(2,3)}, S={(1,3),(2,3),(3,2)}。则R×S= {(1, 3),(2, 2)} ,
R2= {(1, 1),(1, 2),(1, 3)}.
二、选择题
1 设集合A={2,{a},3,4},B = {{a},3,4,1},E为全集,则下列命题正确的是( C )。
(A){2}ÎA (B){a}ÍA (C)ÆÍ{{a}}ÍBÍE (D){{a},1,3,4}ÌB.
2 设集合A={1,2,3},A上的关系R={(1,1),(2,2),(2,3),(3,2),(3,3)},则R不具备( D ).
(A)自反性(B)传递性(C)对称性(D)反对称性
1
2
3
4
5
6
3 设半序集(A,≤)关系≤的哈斯图如下所示,若A的子集B = {2,3,4,5},则元素6为B的( B )。
(A)下界(B)上界(C)最小上界(D)以上答案都不对
4 下列语句中,( B )是命题。
(A)请把门关上(B)地球外的星球上也有人
(C)x + 5 > 6 (D)下午有会吗?
5 设I是如下一个解释:D={a,b},
则在解释I下取真值为1的公式是( D ).
(A)$x"yP(x,y) (B)"x"yP(x,y) (C)"xP(x,x) (D)"x$yP(x,y).
6. 若供选择答案中的数值表示一个简单图中各个顶点的度,能画出图的是( C ).
(A)(1,2,2,3,4,5) (B)(1,2,3,4,5,5) (C)(1,1,1,2,3) (D)(2,3,3,4,5,6).
7. 设G、H是一阶逻辑公式,P是一个谓词,G=$xP(x), H="xP(x),则一阶逻辑公式G®H是( C ).
(A)恒真的(B)恒假的(C