离散数学期末复习
离散数学期末复习
一、选择题
1、下列各选项错误的是
A、
B、
C、{ }
D、{}
2、命题公式(p∧q) →p 是
A、矛盾式
B、重言式
C、可满足式
D、等值式
3、如果是R是A上的偏序关系，R-1是R的逆关系，则R∪R-1是
A、等价关系
B、偏序关系
C、全序关系
D、都不是
4、下列句子中那个是假命题？
A、是无理数.
B、2 + 5 ＝8.
C、x + 5 ＞ 3
D、请不要讲话！
5、下列各选项错误的是？
A、
B、{}
C、{ }
D、{}
6、命题公式p→（p q r）是？
A、重言式
B、矛盾式
C、可满足式
D、等值式
7、函数f : N→N, f(x)=x+5,函数f是
A、单射
B、满射
C、双射
D、都不是
8、设D=
V={a,b,c,d,e,f},R={
A、强连通
B、单向连通
C、弱连通
D、不连通的
9、关系R1和R2具有反自反性，下面运算后，不能保持自反性的是
A、R1R2
B、R1-1
C、R1R2
D、R1-R2
10、连通平面图G有4个结点，3个面，则G有（）条边。
A、7
B、6
C、5
D、4
二、填空题
1、将下面命题符号化。设p:天冷，q:小王穿羽绒服。只要天冷，小王就穿羽绒服.符号化
为
2、将下面命题符号化，设p:天冷，q:小王穿羽绒服。因为天冷，所以小王穿羽绒服. 符号化为
3、将下面命题符号化，设p:天冷，q:小王穿羽绒服。若小王不穿羽绒服，则天不冷.符号化为
4、将下面命题符号化，设p:天冷，q:小王穿羽绒服。只有天冷，小王才穿羽绒服.符号化为
5、将下面命题符号化，设p:天冷，q:小王穿羽绒服。除非天冷，小王才穿羽绒服.符号化为
6、将下面命题符号化，设p:天冷，q:小王穿羽绒服。除非小王穿羽绒服，否则天不冷.符号化为
7、将下面命题符号化，设p:天冷，q:小王穿羽绒服。小王穿羽绒服仅当天冷的时候.符号化为
8、将下面命题符号化，设p:天冷，q:小王穿羽绒服。如果天不冷，则小王不穿羽绒服.符号化为
号化
为
。
号化
为
。
（6）命题“王蓉取得好成绩，仅当她努力学习了。”符号化为
。
10、公式?xF(x)→?xF(x)的类型为
11、公式?xF(x)→(?x?yG(x,y)→?xF(x))的类型
为
12、公式?xF(x)→(?xF(x)∨?yG(y))的类型
为
13、公式(F(x,y)→R(x,y))∧R(x,y)的类型
14、公式?x?yF(x,y)→?x?yF(x,y)的类型
为
15、公式?xF(x,y)的类型
16、令F(x)：x是人，G(x)：x犯错误.则命题“没有不犯错误的人”符号化
为
17、令F(x)：x是人，G(x)：爱看电影.则命题“不是所有的人都爱看电影”符号化
为
18、公式x(M(x)F(x))的前束范式
为：
19、公式xF(x)xG(x)的前束范式
为：
20、公式xF(x)xG(x)的前束范式
为
21、公式xF(x)y(G(x,y)H(y))的前束范式
为
22、公式x(F(x,y)y(G(x,y)H(x,z)))的前束范式
为
23、集合A=?,B={1,{a,b}},C={?,{?}},D={2,2,2,3};则幂集P(A)= ;P(B)= ;P(C)=
;P(D)= ;
24、设A={1,2,3}, B={a,b,c}
则A B=
；
B A =
。
25、设集合A={}, 则
P(A)A=
。
A|=
, A×A的子集
有个. 集合A上
有个不同的二元关系.
E A=
；
I A=
。
28、集合A={2，3，4，5，6，10，12，24}，R是A上的整除关系，则R的极大元
是，极小元
是。29、设A={1，2，3}上的关系R={<1，1>，<1，2>，<1，3>，<3，3>} ，则关系R具
备性质。30、设集合A={1,2,3},关系R={<1,2>, < 2,1>, <2,3>，
<3,3>}, 则自反闭包
r(R)= , 对称闭包s(R)=
。
31、已知图G有10条边, 4个3度顶点, 其余顶点的度数均小于等于2, 问G至少有个顶点。
32、n阶无向完全图K n，边数m= 。
33、n阶有向完全图K n，边数m= 。
34、设无向图G 有10 条边, 3 度与 4 度顶点
各 2 个, 其余顶点的度数均小于3, 则G 中至少
有个顶点，在最少顶点的情况下, 图G 的度数列，
⊿(G)=
, (G)=
.
35、设无向图中有6 条边, 3 度与 5 度顶点各一个, 其余的都是 2 度顶点, 则该图有个顶点。
36、已知n阶连通平面图G有r个面，则G的边数
m= 。
37、设A={1，2，3}上的关系R={<1，2>，<2，3>，<3，1> } ，则
R R=
。
38、设F(x)：x是兔子，M(x)：y是乌龟，H(x,y): x比y跑得快,则命题“兔子比乌龟跑得快”符号
为
三、计算题
1、给出公式A= (q p) q p的真值表。
2、给出公式A= (q p) q p的真值表。
3、给出公式C= (p q) r的真值表
4、用等值演算法判断公式q(p q)的类型
5、求公式A=(p q)r的析取范式与合取范式。
6、求公式B=(p q)r的析取范式与合取范式。
7、求公式A=(p q)r的主析取范式与主合取范式.
8、在一阶逻辑中将下面命题符号化
(1) 人都爱美;
(2) 有人用左手写字分别取(a) D为人类集合, (b) D为全总个体域.
9、在一阶逻辑中将下面命题符号化(1) 正数都大于负数
10、在一阶逻辑中将下面命题符号化(1) 有的无理数大于有的有理数
11、试画出4阶3条边的所有非同构的无向简单图
12、画出所有 K4的所有非同构的生成子图。
13、给定下面的图(前两个为无向图, 后两个为有向图)的集合表示, 画出它们的图形表示G1 = V1, E1, 其
中, V1 = {v1, v2, v3, v4, v5}, E1 = {(v1, v2 ), (v2, v3), (v3, v4), (v3, v3), (v4, v5)};
G2 = V2, E2, 其中V2 = V1, E2 =
{(v1, v2), (v2, v3), (v3, v4), (v4, v5), (v5, v1)};
D1 = V3, E3, 其
中V3 = V1, E3 = {v1, v2,
v2, v3, v3, v2, v4,
v5, v5, v1}; D2 = V4, E
4, 其
中V4 = V1, E4 = {v1, v2,
v2, v5, v5, v2, v3, v4, v4, v3}.
14、先将图中各图的顶点标定顺序, 然后写出各图的集合表示.
15、写出图中各图的度数列, 对有向图还要写出出度列和入度列.
16、画一个简单无向图，使它是欧拉图，但不是哈密顿图。
17、已知集合A={a, b, c, d, e, f}和关系
R={ > }∪I A，请画出偏序集 18、设A={a, b, c, d}, R={ b>},求R的关系矩阵M R和关系图G R。 19、有向图D如图所示，写出D的邻接矩阵和可达矩阵 20、设A=Z+×Z+，在A上定义二元关系R如下：< 21、求公式（P∨Q）→R的主析取范式。 22、求公式x(F(x)∧yG(x,y,z))xH(x,y,z)的前束范式。 23、已知偏序集 24、设A={1,2,3,4}, 定义A上的关 R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>}。求R的关系矩阵M R和关系图G R？