离散数学试题库——填空题（每空2分）1 命题: ∅ ⊆ {{a }} ⊆ {{a },3,4,1} 的真值 = __ __ . 2. 设A= {a,b}, B = {x | x 2－(a+b) x+ab = 0}, 则两个集合的关系为: __ __. 3. 设集合A ＝{a ,b ,c },B ={a ,b }, 那么 P(B )－P(A )=__ __ .4. 无孤立点的有限有向图有欧拉路的充分必要条件为:5.公式))(),(()),()((x S z y R z y x Q x P x →∃∨→∀的自由变元是 , 约束变元是 .6.)))()()(()),()(()((x R z Q z y x P y x →∃→∃⌝∃的前束范式是 .7．设 }7|{)},5()(|{<∈=<∈=+x E x x B x N x x A 且且（N ：自然数集，E + 正偶数） 则 =⋃B A 。

8．A ，B ，C。

9．设P ，Q 的真值为0，R ，S 的真值为1，则)()))(((S R P R Q P ⌝∨→⌝∧→∨⌝的真值= 。

10．公式P R S R P ⌝∨∧∨∧)()(的主合取范式为。

11．若解释I 的论域D 仅包含一个元素，则 )()(x xP x xP ∀→∃ 在I 下真值为。

12．设A={1，2，3，4}，A 上关系图为则 R 2 = 。

13．设A={a ，b ，c ，d}，其上偏序关系R 的哈斯图为则 R= 。

14．图的补图为。

15．设A={a，b，c，d} ，A上二元运算如下：那么代数系统<A，*>的，元的元素为，它们的逆元分别为。

16. P：你努力，Q：你失败。

“除非你努力，否则你将失败”的翻译为；“虽然你努力了，但还是失败了”的翻译为。

17. 论域D={1，2}，指定谓词P则公式),(x y yP x ∃∀真值为 。

18.设S={a 1 ，a 2 ，…，a 8}，B i 是S 的子集，则由B 31所表达的子集是 。

19.设A={2，3，4，5，6}上的二元关系}|,{是质数x y x y x R ∨<><=，则R=（列举法）。

R 的关系矩阵M R = 。

20. 设A={1，2，3}，则A 上既不是对称的又不是反对称的关系R= ；A 上既是对称的又是反对称的关系R= 。

21.设代数系统<A ，*>，运算表如右图。

其中A={a ，b ，c},则幺元是 ；是否有幂等性 ；是否有对称性 。

22. 4阶群必是 群或 群。

23. n 个结点的无向完全图K n 的边数为 ，欧拉图的充要条件是 。

24.公式RQ P Q P P ⌝∧∨⌝∧∧⌝∨)(())((的根树表示为 。

25. 设 f ，g 是自然数集N 上的函数x x g x x f N x 2)(,1)(,=+=∈∀，则=)(x g f 。

26.设A={a ，b ，c}，A 上二元关系R={< a, a > , < a, b >,< a, c >, < c, c>} ,则s （R ）= 。

27.A={1，2，3，4，5，6}，A 上二元关系}|,{是素数y x y x T ÷><=，则用列举法T= ； T 的关系图为； T 具有 性质。

28.集合}}2{},2,{{Φ=A 的幂集A 2= 。

29.P ，Q 真值为0 ；R ，S 真值为1。

则))()(())((S R Q P S R P wff ∧∧∨→∨∧的真值为 。

30.RR Q P wff →∨∧⌝))((的主合取范式为 。

31.P （x ）：x 是素数， E(x)：x 是偶数，O(x)：x 是奇数 N (x,y)：x 可以整数y 。

则谓词))),()(()((x y N y O y x P x wff∧∃→∀的自然语言是 。

32.谓词)),,()),(),(((u y x uQ z y P z x P z y x wff ∃→∧∃∀∀的前束范式为33. 若P ，Q ，为二命题，Q P →真值为0 当且仅当 。

34.命题“对于任意给定的正实数，都存在比它大的实数”令F(x)：x 为实数，yx y x L >:),(则命题的逻辑谓词公式为 。

35.谓词合式公式)()(x xQ x xP ∃→∀的前束范式为 。

36.将量词辖域中出现的 和指导变元交换为另一变元符号，公式其余的部分不变，这种方法称为换名规则。

37.设x 是谓词合式公式A 的一个客体变元，A 的论域为D ，A(x)关于y 是自由的，则被称为存在量词消去规则，记为ES 。

38. 设G 为9阶无向图，每个结点度数不是5就是6，则G 中至少有 个5度结点。

39. n 阶完全图，K n 的点数X (K n ) = 。

40. 有向图 中从v 1到v 2长度为2的通路有条。

41. 设[R ，+，·]是代数系统，如果①[R ，+]是交换群 ②[R ，·]是半群 ③ 则称[R ，+，·]为环。

42. 设],,[⊕⊗L 是代数系统，则],,[⊕⊗L 满足幂等律，即对L a ∈∀有 。

43.n 阶完全图结点v 的度数d(v) = 。

44.设n 阶图G 中有m 条边，每个结点的度数不是k 的是k+1，若G 中有N k 个k 度顶点，N k+1个k+1度顶点，则N k = 。

45.算式)*()*)*(((f e d c b a ÷+的二叉树表示为 。

46.如右图给出格L ，则e 的补元是 。

47.一组学生，用二二扳腕子比赛法来测定臂力的大小，则幺元是 。

48.任何(n,m) 图G = (V,E) , 边与顶点数的关系是 。

49.当n 为 时,非平凡无向完全图K n 是欧拉图。

50.已知一棵无向树T 有三个3顶点,一个2度顶点,其余的都是1度顶点,则T 中有 个1度顶点。

51.n 阶完全图K n 的点色数X(K N )= 。

52.一组学生,用两两扳腕子比赛来测定臂力大小,则幺元是 。

53.n 阶完全图K n 的边数为 。

54.右图 的邻接矩阵A= 。

55.图 的对偶图为 。

56.完全二叉树中，叶数为n t ，则边数m= 。

57.设< {a,b,c}, * >为代数系统，* 运算表如下：；零元为 ；58.a 、b 、c 的逆元分别为 。

59.选择合适的论域和谓词表达集合A=“直角坐标系中，单位元（不包括单位圆周）的点集”则A= 。

60.集合A={Φ,{Φ}}的幂集P(A)= 。

61.设A={1，2，3，4}，A 上二元关系R={<1，2>，<2，1>，<2，3>，<3，4>}画出R的关系图 。

62.设A={<1,2>,<2 , 4 >,<3 , 3 >} , B={<1,3>,<2,4>,<4,2>},则B A ⋃= 。

BA =。

63. 设|A|=3，则A 上有 个二元关系。

64.A={1，2，3}上关系R= 时，R 既是对称的又是反对称的。

65.偏序集><≤R A ,的哈斯图为，则≤R =。

66. 设|X|=n ，|Y|=m 则（1）从X 到Y 有 个不同的函数。

（2） 当n , m 满足 时，存在双射有 个不同的双射。

67.2是有理数的真值为 。

68.Q ：我将去上海，R ：我有时间，公式)()(Q R R Q →∧→的自然语言为 。

69.公式)()(Q P P Q ∧⌝∧→的主合取范式是 。

70.若} ,, , {21m S S S S =是集合A的一个分划，则它应满足 。

71. 称为命题。

72.命题P→Q的真值为，当且仅当 。

73.一个命题含有4个原子命题，则对其所有可能赋值有 种。

74.所有小项的析取式为 。

75.令P （x ）：x 是质数，E （x ）：x 是偶数，Q （x ）：x 是奇数，D （x ，y ）：x 除尽y.则)))(),(()((y E y x D y x E x →∀→∀的汉语翻译为 。

76.设S={a，b,c}则S 6的集合表示为 。

77.P（P(Φ)）= 。

78.BA ⊕=。

79.设R为集合A上的关系，则t （R ）= 。

80.若R是集合A上的偏序关系，则R满足 。

81.设集合A={1，2，3，4，5，6，7，8，9，10}，定义A 上的二元关系“≤”为x≤y=x|y,则y x ∨= 。

82.设},2|{N n x x A n∈==，定义A 上的二元运算为普通乘法、除法和加法，则代数系统<A,*>中运算*关于 运算具有封闭性。

83.设集合S={α，β，γ，δ，ζ}，S 上的运算*定义为左逆元是 ，无左逆元的元素是 。

84. 在群坯、半群、独异点、群中 满足消去律。

85. 设<G,*>是由元素G a ∈生成的循环群，且|G|=n ，则G= 。

86.拉格朗日定理说明若<H , *>是群<G,*>的子群，则可建立G 中的等价关系R= 。

87.若|G|=n,|H|=m则m和n关系为 。

88.设f 是由群<G,☆>到群<G ',*>的同态映射，e '是G '中的幺元， 89.则f的同态核Ker(f )= 。

90.}0|{>∧∈=+x Z x x Z ，*表示求两数的最小公倍数的运算（Z 表示整数集合），对于*运算的幺元是 ，零元是 。

91.代数系统<A,*>中，|A|>1，如果θ和e 分别为<A,*>的幺元和零元，则θ和e 的关系为 。

92.设<G,*>是一个群，<G,*>是阿贝尔群的充要条件是 。

93.图的完全关联矩阵为 。

94.一个图是平面图的充要条件是 。

95.设I 是整数集合，Z 3是由模3的同余类组成的同余类集，在Z 3上定义+3如下：]3mod )[(][][3j i j i +=+，则+3的运算表为 ；<Z +,+3>是否构成群 。

96.设G 是n 阶完全图，则G 的边数m= 。

97.如果有一台计算机，它有一条加法指令，可计算四数的和。

现有28个数需要计算和，它至少要执行 次这个加法指令。

98.如果有限集合A 有n 个元素，则|2A |= 。

99.某集合有101个元素，则有 个子集的元素为奇数。

100.设S={a 1，a 2,…，a 8}，B i 是S 的子集，由B 17表达的子集为 ， 子集{a 2,a 6,a 7}规定为 。