loading优质文档
《离散数学》复习题
一、 填空题 1. 设
，如果为集合的一个覆盖，要使成为的一
个划分，那么必须满足 Ai∩Aj =φ (i,j=1,2,3,…,m,i≠j) 。
2. 合式公式（?x）F(x) ∧G(x,y)中 变元y是___自由___变元.（填自由或约束）
3. 设M＝｛x | (x是整数) ∧ (1≤x≤12) ∧ (x被2整除) ｝,N={x | ( x是整数) ∧ (1≤x≤12) ∧ (x被3整除) }， 则M∩N=__{6,12}___。
4. 若集合A有n个元素，则幂集ρ(A）中有___2 n ____个元素。 5. 若集合中有201个元素，则的子集有 2201 个。 6. 一个命题公式如果______若在它的各种指派下，取值均为假______，则称它为矛盾式。
7. 不含多重边和 环 的图，称为简单图。 8. 任意两个大项的析取为 永真 。
9. 在根树中，若每个结点的出度 小于等于m ，则称这棵树为叉树。 10. 设集合
A={1,2}, B={3,4}, C={5,6}, 则
A×B×C＝
{ ___(1,3,5),(1,3,6),(1,4,5),(1,4,6),(2,3,5),(2,3,6),(2,4 1 / 40
优质文档
,5),(2,4,6)_______}. 11.
为两个命题，当且仅当 P为真，Q为假时 ，
为假。 12.
是 可满足 式（填永真，永假或可满足）。
满足 A中每个元素存在逆元 ，则
13. 如果一个独异点
为群。J88
14. 一个映射
，如果对任意，若，则有 f(xi)≠f(xj) ，则此映射叫从 到的入射。 15.在公式
，量词
的辖域是P(x)?(?y)R(y)。
16. 量词与否定联结词之间有以下关系：??xQ(x) ? ?x?Q(x) 。
17. 设A={1，2}，B={1，2}∪Φ，则A与B 相等 （相等、不相等）。
18.在数理逻辑中, 规定联结词∨,∧,?,→,?的优先次序是 _?,∧, ∨,→,?___.
19. 设P,Q是两个命题，德摩根定律可表示为____ ?(P∨Q) ??P∧
?Q, ?(P∧O) ??P∨?Q ____________。 20.设A?{a,b}，A的幂集?(A)?{?,{a},{b},{a,b}}。
21. 99M=(aij)是无向图G(V,E)的邻接矩阵，V={v1,v2,…,vn}, Mk中的第i行j列的元素值表示_____结点vi到vj的长度为k的路径的数目 25.5______________。
22. 若某连通简单平面图有4个顶点，3 个区域，则有____5____条边。
2 / 40