离散数学试题及参考答案

1 / 13 一、填空题1 设集合 A,B ，其中 A＝{1,2,3}, B= {1,2}, 则 A - B ＝{3} ; (A) - (B)＝{3},{1,3},{2,3},{1,2,3}} . 2. 设有限集合A, |A| = n, 则 | (A ×A)| = 22n. 3. 设集合 A = { a, b}, B = {1, 2}, 则从 A 到 B 的所有映射是1= {(a,1), (b,1)}, 2= {(a,2), (b,2)},3= {( a,1), (b,2)}, 4= {(a,2), (b,1)}, 其中双射的是3, 4 . 4. 已知命题公式G＝(PQ)∧R，则 G 的主析取范式是(P∧Q∧R) 5.设 G 是完全二叉树， G 有 7 个点，其中4 个叶点，则G 的总度数为12，分枝点数为3. 6 设 A 、B 为两个集合 , A= {1,2,4}, B = {3,4}, 则从 AB＝{4} ; AB＝{1,2,3,4}; A－B＝{1,2} . 7. 设 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, 则| | (A B)| = nm2. 11 设 A,B,R 是三个集合， 其中 R 是实数集， A = {x | -1 ≤x≤1, xR}, B = {x | 0 ≤x < 2, xR},则 A-B = -1<=x<0 , B-A = {x | 1 < x < 2, xR} , A∩B ={x | 0≤x≤1, x R} , . 13. 设集合 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)) . 15.设 G 是具有 8 个顶点的树，则G 中增加21 条边才能把G 变成完全图。 (完全图的边数2)1(nn，树的边数为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)} 。则2 / 13 R S＝{(1, 3),(2, 2)} , R2＝{(1, 1),(1, 2),(1, 3)}. 二、选择题1设集合 A={2,{a},3,4}， B =...