离散数学 复习题1．设A 和B 都是命题，则A →B 的真值为假当且仅当 。

A. A 为假，B 为真B. A 为假，B 为假C. A 为真，B 为真D. A 为真，B 为假2．下列公式中为重言式的是 。

A. P →(P ∨Q ∨R)B. ┐(Q →P)∧PC. (P →Q)→(Q →┐P)D. (P ∧┐P)←→Q 3．设A ＝{a ，{a}}，P(A)表示A 的幂集，下面各式中错误的是 。

A. {a}∈P(A)B. {a}⊆P(A)C. {{a}}∈P(A)D. {{a}}⊆P(A)4．设A ＝{1,2,3,4,5,6}上的关系为R ＝{<x,y>|x>y}，则R -1具有 。

A. 对称性B. 自反性C. 反自反性、反对称性、传递性D. 以上都不对5．设R 是非空集合A 上的二元关系，则R 的对称闭包S(R)＝ 。

A. R ∪I AB. R ∪R CC. R-I AD. R ∩R C6．映射的复合运算满足 。

A. 交换律B. 结合律C. 幂等律D. 分配律7．设R 、I 分别是实数集合和整数集合，-、×、/ 分别是普通的减法、乘法 和除法运算，则 是半群。

A. <I ，->B. <R ，->C. <R ，×>D. <R ，/>8．在一个格<A ，≤>中，对任意的a ，b ，c ∈A ，都有 。

A. a ∨(b ∧c)≤(a ∨b)∧(a ∨c)B. a ∧(b ∨c)≤(a ∧b)∨(a ∧c)C. a ∨(b ∧c)＝(a ∨b)∧(a ∨c)D. A 、B 、C 都正确9．无向简单图G 中结点间的连通关系是 。

A. 偏序关系B. 等价关系C. 既是偏序关系又是等价关系D. A 、B 、C 都错误10.设G 是一个有v 个结点e 条边的连通简单平面图，若v ≥3，则 。

A. v ≤3e-6B. e ≤3v-6C. v ≤3e+6D. e ≤3v+611．设P 和Q 是命题，P ，⌝P ∨Q ⇒Q 。

( )12．设A 和B 是集合，A-B ＝A 当且仅当B ＝Φ。

( )13．一个不是自反的关系，一定是反自反的。

( )14．若A 和B 是任意两个集合，则A ×B ＝B ×A 。

( )15．关系f ＝{<m,n>|m,n ∈N,m+n ＜10}是函数，其中N 是自然数集合。

( )16．集合B 是集合A 的真子集，则K[B]＜K[A]。

( )17．整环一定是域。

( )18．任何两个具有2n 个元素的有限布尔代数都是同构的。

( )19．已知无向连通图G 中有n 个结点，m 条边，G 中无回路，则m ＝n-1。

( )20.如果两个图的结点数相同、边数相等、度数相同的结点数目也相等，那么这两个图是同构的。

( )21.设命题P 表示“我今天将去公园”，命题Q 表示“天下雨”，则命题“我今天去公园，除非下雨”可以符号化为 (1) 。

22.命题“只有教师才有教师资格证(T(x)，C(x))”可符号为： (2) 。

23.设P(A)是集合A的幂集，如果|A|＝n，则|P(A)|＝(3) ，|A×P(A)|＝(4) 。

24.设A＝{a,b,c}，P(A)为A的幂集，{P(A)，⊆}是偏序集。

则P(A)的子集＝{Φ，{a}，{b}，{a,b}，{b,c}}的极大元是(5) ，最大元是 (6) ，上界是(7)，下确界是 (8) 。

25.设f和g是从整数集到整数集合的函数，其定义为f(x)＝2x+3和g(x)＝3x+2，则g f(x)＝ (9) ，f g(x)＝ (10) 。

26.设<A，*>是一个代数系统，并设R是A上的一个等价关系，如果<a1，a2>和<b1，b2>∈R时， (11) ，则称R为A上的同余关系。

27.设<A，≤>是一个格，由它诱导的代数系统为<A，∨，∧>，如果对于任意的a,b,c∈A，当b≤a时，有 (12) ，则称<A，≤>为模格。

28.一个图是平面图，当且仅当它不包含与 (13) 或 (14) 在2度结点内同构的子图。

29.无向图G具有一条欧拉路，当且仅当G是 (15) ，且有（16）奇数度结点。

30.无向图G如右图所示，则G的点连通度 (17) ，边连通度为 (18) ，它的生成树有 (19) 条树枝和 (20) 条弦。

31.求(A→(B∧C))∧(﹁A←→(﹁B∧﹁C))的主析取范式和主合取范式。

32.将下列推理形式化，并推证其结论所有牛都有角，有些动物是牛，所以有些动物有角。

33.设正整数的序偶集合A，在A上定义的二元关系R如下：<<x,y>,<u,v>>∈R，当且仅当xv＝yu，证明R是一个等价关系。

34.设<G，*>是群，S是G的非空子集，如果对于S中的任意元素a和b，有a*b-1∈S，则<S，*>是<G，*>的子群。

35.令g f是一个复合函数，若g和f是双射的，则g f是双射的。

36.判断彼德森(Petersen)图是否为汉密尔顿图？若是，请写出汉密尔顿回路。

若不是，请予以证明。

37．下列是两个命题变元p，q的小项是（）A．p∧┐p∧q B．┐p∨qC．┐p∧q D．┐p∨p∨q38．令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（）A．p→┐q B．p∨┐qC．p∧q D．p∧┐q39．下列语句中是命题的只有（）A．1+1=10 B．x+y=10C．sinx+siny<0 D．x mod 3=240．下列等值式不正确的是（）A．┐(∀x)A⇔(∃x)┐AB．(∀x)(B→A(x))⇔B→(∀x)A(x)C．(∃x)(A(x)∧B(x))⇔(∃x)A(x)∧(∃x)B(x)D ．(∀x)(∀y)(A(x)→B(y))⇔(∃x)A(x)→(∀y)B(y)41．谓词公式(∃x)P(x,y)∧(∀x)(Q(x,z)→(∃x)(∀y)R(x,y,z)中量词∀x 的辖域是（ ）A ．(∀x)Q(x,z)→(∃x)(∀y)R(x,y,z))B ．Q(x,z)→(∀y)R(x,y,z)C ．Q(x,z)→(∃x)(∀y)R(x,y,z)D ．Q(x,z)42．设R 为实数集，函数f ：R →R ，f(x)=2x ，则f 是（ ）A ．满射函数B ．入射函数C ．双射函数D ．非入射非满射43．设A={a,b,c,d}，A 上的等价关系R={<a,b >,<b,a >,<c,d >,<d,c >}∪I A ，则对应于R 的A 的划分是（ ）A ．{{a},{b,c},{d}}B ．{{a,b},{c},{d}}C ．{{a},{b},{c},{d}}D ．{{a,b},{c,d}}44．设A={Ø}，B=P(P(A))，以下正确的式子是（ ）A ．{Ø,{Ø}}∈B B ．{{Ø,Ø}}∈BC ．{{Ø},{{Ø}}}∈BD ．{Ø,{{Ø}}}∈B45．设X ，Y ，Z 是集合，一是集合相对补运算，下列等式不正确的是（ ）A ．(X -Y)-Z=X -(Y ∩Z)B ．(X -Y)-Z=(X -Z)-YC ．(X -Y)-Z=(X -Z)-(Y -Z)D ．(X -Y)-Z=X -(Y ∪Z)46．设*是集合A 上的二元运算，称Z 是A 上关于运算*的零元，若（ ）A ．,A x ∈∀有x*Z=Z*x=ZB ．Z ∈A ，且A x ∈∀有x*Z=Z*x=ZC ．Z ∈A ，且A x ∈∀有x*Z=Z*x=xD ．Z ∈A ，且A x ∈∃有x*Z=Z*x=Z47．在自然数集N 上，下列定义的运算中不可结合的只有（ ）A ．a*b=min(a,b)B ．a*b=a+bC ．a*b=GCD(a,b)(a,b 的最大公约数)D ．a*b=a(mod b)48．设R 为实数集，R +={x|x ∈R ∧x>0}，*是数的乘法运算，<R +，*>是一个群，则下列集合关于数的乘法运算构成该群的子群的是（ ）A ．{R +中的有理数}B ．{R +中的无理数}C ．{R +中的自然数}D ．{1，2，3}49．设<A,*, >是环，则下列正确的是（ ）A ．<A, >是交换群B ．<A,*>是加法群C ． 对*是可分配的D ．*对 是可分配的50．下列各图不是欧拉图的是（ ）51．设G是连通平面图，G中有6个顶点8条边，则G的面的数目是（）A．2个面B．3个面C．4个面D．5个面52．一公式为之充分必要条件是其析取范式之每一析取项中均必同时包含一命题变元及其否定；一公式为之充分必要条件是其合取范式之每一合取项中均必同时包含一命题变元及其否定。

53．前束范式具有形式(Q1V1)(Q2V2)…(Q n V n)A，其中Q i(1≤i≤n)为，A为的谓词公式。

54．设论域是{a,b,c}，则(∀x)S(x)等价于命题公式；(x∃)S(x)等价于命题公式。

55．设R为A上的关系，则R的自反闭包r(R)= ，对称闭包s(R)= 。

56．某集合A上的二元关系R具有对称性，反对称性，自反性和传递性，此关系R是，其关系矩阵是。

57．设<S,≤>是一个偏序集，如果S中的任意两个元素都有和，则称S关于≤构成一个格。

58．设Z是整数集，在Z上定义二元运算*为a*b=a+b+a·b，其中+和·是数的加法和乘法，则代数系统<Z,*>的幺元是，零元是。

59．如下平面图有2个面R1和R2，其中deg(R1)= ，deg(R2)= 。

60．无向图G具有一条欧拉回路，当且仅当G是，并且所有结点的度数都是。

61．在下图中，结点v2的度数是，结点v5的度数是。

62．（4分）求出从A={1,2}到B={x,y}的所有函数，并指出哪些是双射函数，哪些是满射函数。

63．（4分）如果论域是集合{a,b,c}，试消去给定公式中的量词：)0(=+y∀∃。

)(y)(xx64．（5分）设A={a,b,c }，P（A）是A的幂集，⊕是集合对称差运算。

已知<P(A),⊕>是群。

在群<P(A),⊕>中，①找出其幺元。

②找出任一元素的逆元。

③求元素x使满足{a}⊕x={b}。

65．（6分）用等值演算法求公式┐(p→q)→←(p→┐q)的主合取范式66．（5分）画出5个具有5个结点5条边的非同构的无向连通简单图。