离散数学复习题

单项选择题

1.下列不是命题的是[ ]。 A. 7能被3整除.

B. 5是素数当且仅当太阳从西边升起. C. x加7小于0. D. 华东交通大学位于南昌北区.

2. 设p:王平努力学习，q:王平取得好成绩，命题“除非王平努力学习，否则他不能取得好成绩”的符号化形式为 [ ]。 A. p→q B. p→q

C. q→p D. q→p 3. 下面4个推理定律中，不正确的为 [ ]。 A. A=>(A∨B) (附加律) B. (A∨B)∧A=>B (析取三段论) C. (A→B)∧A=>B (假言推理) D. (A→B)∧B=>A (拒取式)

4. 设解释I如下，个体域D={1,2},F(1,1)=(2,2)=0,F(1,2)=F(2,1)=1，在解释I下，下列公式中真值为1的是 [ ]。 A.x yF(x,y) B. xyF(x,y) C. xyF(x,y) D. xyF(x,y) 5. 下列四个命题中哪一个为真？ [ ]。 A. ∈ B.  ∈{a}

C. ∈{{}} D. 

6. 设S={a,b,c,d}，R={,,}，则R的性质是 [ ]。 A.自反、对称、传递的 B. 对称、反对称、传递的

C.自反、对称、反对称的 D. 只有对称性 7. 设A={a,b,c}，则下列是集合A的划分的是[ ]。

A.{{b,c},{c}} B.{{a,b},{a,c}} C.{{a,b},c} D.{{a},{b,c}} 10. 下列四组数据中，不能成为任何4阶无向简单图的度数序列的为[ ]。

1

A. 2,2,2,2 B. 1,1,1,3 C. 1,1,2,3 D. 1,2,2,3 二、填空题

1. 命题公式p→q的真值为假，当且仅当_____p为真q为假____________。 2．公式p→(q→r)在联结词全功能集{，，}中等值形式之一为p_qr___。 4. 设集合A = {1，4}，B = {2，4}，则 P (A) - P (B) = _____ ___________。 5. R是非空集合上的偏序关系，当且仅当R具有___ ________。 6. 设函数f(x)=x + 1,g(x)= 2x, 则f o g =__2x+1________________。 7. 设σ=(134)(256)，τ=(25)(13)，则στ=____________________。 8. 命题“设G为任意的n阶简单的哈密尔图，则u，v∈V(G)，均有d(u)+d(v)≥n”的真值为___________。

9. 无向连通图G是欧拉图，当且仅当G中每一个顶点的度数都为___偶数____。 10. 设树T有m个顶点，n条边，则T中顶点与边的关系为__m=n-1_____________。

11、设A={1，2}，P(A)表示A的幂集，,则P(A)  A =_____________________。 12在一阶逻辑中符号化命题:“所有的人都是要死的”（只能用存在量词）： _________________________________________________。 14. n阶有向完全图中所有顶点的度数之和为________

15.已知从A到A/R的函数g：AA/R为自然映射，A={1,2,3 }， R=EA,则g(1)=____________________________。

16. 设函数f(x)=2x + 1,g(x)= x2-2,则f o g =___2（x2-2）+1______________。 17．若|P(A∪B)|=256，|P(A)|=，| B |=3，则|AB|= 。

三、判断题：（10分，在括号内划“√”或“×”）

（ ）1．“如果太阳从西边出来，则2+2=4”，此命题值为假。 （ ）2．(1,3,3,3)可以成为无向简单图的度数序列。

（ ）3．有一个函数f：XY，若f具有反函数，则f一定是单射。 （ ）4．（PQ）（PQ）是永真式。

（ ）5．在某集合上二元运算中，若某元素存在左右逆元，则该元素逆元唯一。

2

2

2

（ ）6．命题公式的主析取范式为0，则其主合取范式为1。 （ ）7．有向图的关联矩阵中所有元素之和为该图度之和 。 （ ）8．初级回路一定是简单回路。

（ ）9．若关系R具有自反性，则一定不具有反自反性。 四、简答题

1、设集合A= {1,2,3,4}上的二元关系R1与R2定义如下： R1={<1,1>,<1,3>,<2,2>,<2,4>,<3,3>,<4,4>}， R2={<1,1>,<1,2>,<2,1>,<2,3>,<3,4>,<4,1>}， 1) 写出R1的关系矩阵，并判断R1具有哪些性质？ 2) 求出R1ｏR2

3) 画出t(R2)的关系图。 2、（10分）已知A和A上的偏序关系R，设A = {a,b,c,d,e,f }，R = {,, ,,,,,,,,,}ｕIA 。 1) 画出此偏序集的哈斯图。 2) 找出最大元与最小元。 3、（10分）若D是具有结点v1,v2,v3,v4的有向图，它的邻接矩阵表示如下： 1 2 1 0 0 0 2 0 0 0 0 1 0 0 1 0 1) 画出这个图；

2) D是单向连通还是强连通？说明理由。 3) 该图是否存在欧拉通路？说明理由。

4) 求该图中长度小于等于3的通路与回路总数。

3