关于亲情的诗-英语教师自我介绍

离散数学试题与答案试卷一
一、填空 20% （每小题2分）
1．设
A{x|(xN)且(x5)},B{x|xE且x7}
（N：自然数集，E+
正偶
数） 则
AB
。
2．A，B，C表示三个集合，文图中阴影部分的集合表达式为
。

3．设P，Q 的真值为0，R，S的真值为1，则
A B

C

(P(Q(RP)))(RS)
的真值=

。
4．公式
(PR)(SR)P
的主合取范式为
。
5．若解释I的论域D仅包含一个元素，则
xP(x)xP(x)
在I下真值为
。
6．设A={1，2，3，4}，A上关系图为




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





则 R= 。
8．图的补图为 。
9．设A={a，b，c，d} ，A上二元运算如下：

*
a
b
c
d
a b c d
a b c d
b c d a
c d a b
d a b c
那么代数系统的幺元是 ，有逆元的元素为 ，它们的
逆元分别为 。
10．下图所示的偏序集中，是格的为 。





二、选择 20%
（每小题 2分）
1、下列是真命题的有（ ）
A．
{a}{{a}}
； B．
{{}}{,{}}
；
C．
{{},}
； D．
{}{{}}
。
2、下列集合中相等的有（ ）
A．{4，3}

；B． {

，3，4}；C．{4，

，3，3}；D． {3，4}。
3、设A={1，2，3}，则A上的二元关系有（ ）个。
A． 2
3
；

B． 3
2
；

C．
2
33
22
； D．
3
。
4、设R，S是集合A上的关系，则下列说法正确的是（ ）
A．若R，S 是自反的， 则
RS
是自反的；
B．若R，S 是反自反的， 则
RS
是反自反的；
C．若R，S 是对称的， 则
RS
是对称的；
D．若R，S 是传递的， 则
RS
是传递的。
5、设A={1，2，3，4}，P（A）（A的幂集）上规定二元系如下
R{s,t|s,tp(A)(|s||t|}
则P（A） R=（ ）
A．A ；B．P(A) ；C．{{{1}}，{{1，2}}，{{1，2，3}}，{{1，2，3，4}}}；

D．{{

}，{2}，{2，3}，{{2，3，4}}，{A}}
6、设A={

，{1}，{1，3}，{1，2，3}}则A上包含关系“

”的哈斯图为（ ）

7、下列函数是双射的为（ ）
A．f : I

E , f (x) = 2x ； B．f : N

N

N, f (n) = ；
C．f : R

I , f (x) = [x] ； D．f :I

N, f (x) = | x | 。
（注：I—整数集，E—偶数集， N—自然数集，R—实数集）
8、图 中 从v
1
到v
3
长度为3 的通路有（ ）条。

A． 0； B． 1； C． 2； D． 3。
9、下图中既不是Eular图，也不是Hamilton图的图是（ ）

10、在一棵树中有7片树叶，3个3度结点，其余都是4度结点则该树有（ ）个4
度结点。
A．1； B．2； C．3； D．4 。

三、证明 26%
１、R是集合X上的一个自反关系，求证：R是对称和传递的，当且仅当
< a, b> 和在R中有<.b , c>在R中。（8分）
２、f和g都是群1
,★>到< G
2,
*>的同态映射，证明是1
, ★>的一个子

群。其中C=
{x|xG
1
且f(x)g(x)}
(8分)
３、G= (|V| = v，|E|=e ) 是每一个面至少由k（k

3）条边围成的连通平面
图，则

e
k(v2)
k2
， 由此证明彼得森图（Peterson）图是非平面图。（11分）
四、逻辑推演 16%
用CP规则证明下题（每小题 8分）
1、
ABCD,DEFAF

2、
x(P(x)Q(x))xP(x)xQ(x)


五、计算 18%
1、设集合A={a，b，c，d}上的关系R={ ,< b , a > ,< b, c > , < c , d >}用矩阵运算
求出R的传递闭包t (R)。 （9分）

2、如下图 所示的赋权图表示某七个城市
v
1
,v
2
,,v
7
及预先算出它们之间的一些直接通
信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总 造价最小。 （９分）

试卷二试题与答案
一、填空 20% （每小题2分）
1、 P：你努力，Q：你失败。“除非你努力，否则你将失败”的翻译为
；“虽然你努力了，但还是失败了”的翻译为
。
2、论域D={1，2}，指定谓词P
P (1,1)
T
P (1,2)
T
P (2,1)
F
P (2,2)
F
则公式
xyP(y,x)
真值为 。
2、 设S={a
1
，a
2
，…，a
8
} ，B
i
是S的子集，则由B
31
所表达的子集是

。
3、 设A={2，3，4，5，6}上的二元关系
R{x,y|xyx是质数}
，则R=

（列举法）。
R的关系矩阵M
R
=

。
5、设A={1，2，3}，则A上既不是对称的又不是反对称的关系
R= ；A上既是对称的又是反对称的关系
R= 。
6、设代数系统，其中A={a，b，c},
*
a
b
c
a b c
a b c
b b c
c c b



则幺元是 ；是否有幂等
性 ；是否有对称性 。
7、4阶群必是 群或 群。
8、下面偏序格是分配格的是 。

9、n个结点的无向完全图K
n
的边数为 ，欧拉图的充要条件是
。
10、公式
(P(PQ))((PQ)R
的根树表示为



。
二、选择 20% （每小题2分）
1、在下述公式中是重言式为（ ）
A．
(PQ)(PQ)
；B．
(PQ)((PQ)(Q P))
；

C．
(PQ)Q
； D．
P(PQ)
。
2、命题公式
(PQ)(QP)
中极小项的个数为（ ），成真赋值的个数
为（ ）。
A．0； B．1； C．2； D．3 。
S
3、设
S{,{1},{1,2}}
，则
2
有（ ）个元素。
A．3； B．6； C．7； D．8 。
4、 设
S{ 1, 2, 3 }
，定义
SS
上的等价关系
R{a,b,c,d | a,bSS,c,dSS,adbc}
则由 R产 生
的
SS
上一个划分共有（ ）个分块。
A．4； B．5； C．6； D．9 。
5、设
S{ 1, 2, 3 }
，S上关系R的关系图为

则R具有（ ）性质。
A．自反性、对称性、传递性； B．反自反性、反对称性；
C．反自反性、反对称性、传递性； D．自反性 。
6、设
,
为普通加法和乘法，则（ ）
S,,
是域。
A．
S{x|xab3,
C．S{x|x2n1,
a,bQ}
B．
S{x|x2n,a,bZ}

nZ}
D．
S{x|xZx0}
= N 。
7、下面偏序集（ ）能构成格。

8、在如下的有向图中，从V
1
到V
4
长度为3 的道路有（ ）条。

A．1； B．2； C．3； D．4 。
9、在如下各图中（ ）欧拉图。
10、
设R是实数集合，“

”为普通乘法，则代数系统 是（ ）。
A．群； B．独异点； C．半群 。
三、证明 46%
1、 设R是A上一个二元关系，
S{a,b|(a,bA)(对于某一个cA,有a,c R且c,bR)}
试证
明若R是A上一个等价关系，则S也是A上的一个等价关系。（ 9分）

2、 用逻辑推理证明：
所有的舞蹈者都很有风度，王华是个学生且是个舞蹈者。因此有些学生很有风度。
（11分）

3、 若
f:AB
是从A到B的函数，定义一个函数
g:B2
对任意
bB
有
A
g(b){x|(xA)(f(x)b) }
，证明：若f是A到B的满射，则g是从B到
2

A
的单射。（10分）

4、 若无向图G中只有两个奇数度结点，则这两个结点一定连通。（8分）

5、 设G是具有n个结点的无向简单图，其边数
Hamilton图（8分）
m
1(n1)(n2)2
2
，则G是

四、计算 14%
1、 设6
,+
6
>是一个群，这里+
6
是模 6加法，Z
6
={[0 ]，[1]，[2]，[3]，[4]，[5]}，
试求出< Z
6
,+
6
>的所有子群及其相应左陪集。（7分）

2、 权数1，4，9，16，25，36，49，64，81，100构造一棵最优二叉树。（7分）
试卷三试题与答案
一、 填空 20% （每空 2分）
1、 设 f，g是自然数集N上的函数
xN,f(x)x1,g(x)2x
，
则
fg(x)
。
2、 设A={a，b，c}，A上二元关系R={< a, a > , < a, b >,< a, c >, < c, c>} ,
则s（R）= 。
3、 A={1，2，3，4，5，6}，A上二元关系
T{x,y|xy是素数 }
，则用列举
法
T= ；
T的关系图为
；
T具有 性质。
4、 集合
A{{,2},{2}}
的幂集
2
A
= 。
5、 P，Q真值为0 ；R，S真值为1。则
wff(P(RS))((PQ) (RS))
的
真值为 。
6、
wff((PQ)R)R
的主合取范式
为 。
7、 设 P（x）：x是素数， E(x)：x 是偶数，O(x)：x是奇数 N (x,y) ：x可以整数y。
则谓词
wffx(P(x)y(O(y)N(y,x)))
的自然语言是
。
8、 谓词
wffxy(z(P(x,z)P(y,z))uQ(x,y,u ))
的前束范式为

。

二、 选择 20% （每小题 2分）
1、 下述命题公式中，是重言式的为（ ）。
A、
(pq)(pq)
； B、
(pq)((pq))(qp))
；
C、
(pq)q
； D、
(pp)q
。
2、
wff(pq)r
的主析取范式中含极小项的个数为（ ）。
A 、2； B、 3； C、5； D、0； E、 8 。
3、 给定推理
①
x(F(x)G(x))

②
F(y)G(y)

③
xF(x)

④
F(y)

⑤
G(y)

⑥
xG(x)

P
US①
P
ES③
T②④I
UG⑤
x(F(x)G(x))xG(x)

推理过程中错在（ ）。
A、①->②; B、②->③; C、③->④; D、④->⑤; E、⑤->⑥
4、 设S
1
={1，2，…，8，9}，S2
={2，4，6，8}，S
3
={1，3，5，7，9}，S
4
={3，4，5}，
S
5
={3，5}，在条件
XS
1
且XS
3
下X与（ ）集合相等。
A、 X=S
2
或S
5
； B、X=S
4
或S
5
；
C、X=S
1
，S
2
或S
4
； D、X与S
1
，…，S
5
中任何集合都不等。
5、 设R和S是P 上的关系，P是所有人的集合，
R{x,y|x,yPx是y的父亲}
，
S {x,y|x,yPx是y的母亲}
则
S
1
R
表示关 系 （ ）。
A、
{x,y|x,yPx是y的丈夫}
；
B、
{x,y|x,yPx是y的孙子或孙女}
；
C、

； D、
{x,y|x,yPx是y的祖父或祖母}
。
6、 下面函数（ ）是单射而非满射。
A、
f:RR,
< br>f:ZR,
B、
f(x)x
2
2x1
；
f(x)lnx
；

C、
f:RZ,
D、
f:RR,
f(x)[x],[x]表示不大于x的最大整数
；
f(x)2x1
。
其中R为实数集，Z为整数集，R
+
，Z< br>+
分别表示正实数与正整数集。
7、 设S={1，2，3}，R为S上的关系，其关系图为

则R具有（ ）的性质。
A、 自反、对称、传递； B、什么性质也没有；
C、反自反、反对称、传递； D、自反、对称、反对称、传递。
8、 设
S{,{1},{1,2}}
，则有（ ）
S
。
A、{{1,2}} ；B、{1,2 } ； C、{1} ； D、{2} 。
9、 设A={1 ,2 ,3 }，则A上有（ ）个二元关系。
A、2
3
； B、3
2
； C、
2
； D、
2
。
10、全体小项合取式为（ ）。
A、可满足式； B、矛盾式； C、永真式； D、A，B，C 都有可能。
三、 用CP规则证明 16% （每小题 8分）
1、ABCD,DEF
2
3
3
2
AF

2、
x(P(x)Q(x))xP(x)xQ(x)

四、（14%）
集合X={<1,2>, <3,4>, <5,6>,… }，R={< 1
,y
1
>,2
,y
2
>>|x
1
+y
2 =
x
2
+y
1
} 。
1、 证明R是X上的等价关系。 （10分）
2、 求出X关于R的商集。（4分）
五、（10%）
设集合A={ a ,b , c , d }上关系R={< a, b > , < b , a > , < b , c > , < c , d >}
要求 1、写出R的关系矩阵和关系图。（4分）
2、用矩阵运算求出R的传递闭包。（6分）

六、（20%）
1、（10分）设f和g是函数，证明
fg
也是函数。
2、（10分）设函数
g:ST
入射函数。

卷号：4
湖北师范学院期末考试试卷
离散数学

本题
得分
< br>一、选择题（选择真确答案，并将其代号写在题干后面的括号里，本题共
6小题,每小题3分，共 18分)
f:TS
，证明
f:TS
有一左逆函数当且仅当f是
1 命题“小李和小王学习努力”的否定是：（ ）
(A)小李或小王学习不努力； (B) 小李和小王学习都不努力；
(C)小李学习努力和小王学习不努力；(D) 小李和小王至少有一人学习努力。
2 设个体域
A{a,b}
，公式
x P(x)xS(x)
在
A
中消去量词后应为: ( )
(A)
P(x)S(x)
； (B)
P(a)P(b)(S(a)S(b))
；
(C)
P(a)S(b)
； (D)
P(a)P(b)S(a)S(b)
。
3 A={1，2，3}，A上的如下二元关系中， ( )是函数。
(A)R1={<1，2>，<2，1>，,<2，2>}； (B)R2={<1，2>，<1，1>，<3，2>}；
(C)R3={<1，1>，<2，2>}； (D)R4={<1，2>，,<2，3>，<3，3>}。
4下列代数系统
(S,)
，哪个是群？ （ ）
(A)
S{0,1,3,5},
是模7加法；
(B)
SQ
（有理数集合），

是一般乘法；
(C)
SZ
(整数集合)，

是一般减法；
(D)
S{1,3,4,5,9},
是模11乘法。
5下面集合（ ）关于整除关系构成格。
(A){2，3，6，12，24，36} ； (B){1，2，3，4，6，8，12} ；
(C){1，2，3，5，6，15，30} ； (D){3，6，9，12}。
6
V{a,b,c,d,e,f}
，
E {a,b,b,c,c,aa,d,d,e,

f,e}
，则有向图
GV,E
是（ ）。
(A)强连通的 ； (B)单侧连通的 ； (C)弱连通的 ； (D)不连通的。
本题
得分

二、填空题（请将正确答案填入空格内，每小题3分，共18分）
1 设P：它占据空间， Q：它有质量，R：它不断运动，S：它叫做物质。

命题“占据空间的，有质量的而且不 断运动的叫做物质”的符号化为
_____________________。
2 设A={1，2}，P(A)表示A的幂集，,则P(A)  A =_____________________。
3．设
A{a,b,c}
考虑下列子集：
S
1
{{a ,b},{b,c}}
，
S
2
{{a},{a,b},{a,c}}
，
S
3
{{a},{b,c}}
，
S
4
{{ a,b,c}}
，
S
5
{{a},{b},{c}}
，
S
6
{{a},{a,c}}

则A的覆盖有 ，A的划分有 。
4 设
(A,)是分配格，若对任意的
a,b,cA
，如果有
(abac,aba c
成立，则
有 。
5 若连通平面图
GV,E
共 有r个面，其中
|V|v,|E|e
，则它满足的Euler公式
为 。
6 5个结点可以构成 棵非同构得无向树。
本题
得分

三、判断题（请在你认为正确的题后括号内打“√”，错误的打“×”，本
题共6小 题，每小题1分，共6分）
1设P，Q是两个命题，当且仅当P，Q的真值均为T时，
PQ
的值为T。（ ）
2
{}{,{}}
且
{}{,{}}
。（ ）
3 集合
A{a,b,c}
上的关系
R{a,b,a,c}
是传递的。（ ）
4任何循环群必定是阿贝尔群，反之亦真。（ ）
5设G为无向图，若G中恰好n个结点，n-1条边，则G必为一棵树。（ ）
6平面图一定是连通图。( )
本题
得分

四、计算题（本题共4小题,每小题6分，共24 分）

1求下式的主析取范式和主合取范式：
（PQ)(PQ)
。
2设集合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）求出
R1R2
。
3 设S = R {-1}（R为实数集），
ababab
。
（1）说明
(S,)
是否构成群；
（2）在
S
中解方程
2x37
。
4 一棵树T中，有3个2度结点，一个3度结点，其余结点都是树叶。
问T中有几个结点?

本题
得分

五、应用题（本题共1小题,每小题10分，共10分）

下图给出的赋权图表示六 个城市
a,b,c,d,e,f
及架起城市间直接通讯线路的预测造价。
给出一个设计 方案使得各城市间能够通讯且总造价最小，并计算出
最小总造价。
。



本题
得分

六、证明题（本题共3小题,每小题8分，共24分）

1．设
A{1, 2
当
,,
，
9
在
AA
上定义关系
R:a,bc,dR
且仅当
adbc
，证明
R
是
AA
上的等价关系，并求出
[2,5]
R
.
2． 设
G
是群，
H
是G的子群，
xG
，证明：
xHx
1
{xhx
1
|hH}
是
G
的子群。 < br>3．将下列命题形式化，并证明结论的有效性：所有有理数都是实数，某些有理数是整数。
因此， 某些实数是整数。
《离散数学》试题五

一、判断题（每题1分，共10分）

1.在命运题逻辑中，任何命题公式的主合取范式都是存在的，并且是惟一的。
（ ）
2. 011是公式
(pq)r
的成真赋值 ( )
3.
(xF(x)yG(y))(xF(x))(yG(y))
( )
4.
x(F(x)G(x))xF(x)xG(x)
（ ）
5.三种重要的二元关系是等价关系、偏序关系和函数关系，它们的共同特点是都具有自反
性 。 ( )
6. 设F,R都是二元关系,则(F·R)=F·R。 ( )
7.设n是任意一个正整数,则一定存在阶是n的群. ( )
8. 布尔代数是有界格,也是分配格. ( )
9.无向完全图
K
n
（n>2）一定是哈密顿图 ( )
10.阶数至少是2 树的每一条边都是桥,因而它的
-1-1-1

边连通度是1. （ ）

二、空题（每小题２分，共２０分）
1. 谓词公式

x(P(x,y)∧

tQ(t,z)→R(x,y,t))中量词

的辖域是
___________________。
2.设F(x):x是人，H(x,y):x与 y一样高，在一阶逻辑中，命题“人都不一样高”的符号化
形式为_______ ___。
3.
(pq)pq
从公式分类角度来看，它为__________式。
4.设R={<1,1>,<1,2>,<2,3>}，则R的对称闭包是 。
5.设A,B是集合，
A3,B4,AB2,那么，AB

6.<
Z
6
，

〉是模6加群， 则它的生成元是 。2

4=
7．整数加群是循环群，其生成元是 和 。
8.设
A,
是偏序集,如果_________ ____, 则称
A,
是(偏序)格。
9.一棵二叉树先序遍历得ABDECF，中序遍历 得DBEACF,则后序遍历的结果是
________________。
10. r=5,当s= 时，完全二部图
K
r,s
才可能存在完美匹配。 。
三、计算题（1-4题每题8分；5-6题每题10分，共52分）

1.R
1
={<1,2>,<2,1>,<2,3>,<3,2>},R
2
={<2,2> ,<2,3>,<3,1>}
求：(1) R
1
(2) R
1
·R
2
(3)R
2
(4)t(R
1
)(传递闭包)
2．设G=

a

0


-12


10

10

01

01



,b,c,d

，G上的运算是矩

1

01

10

10


阵乘 法。已知G构成群。
（1）指出个元素的阶；
（2）找出G的全部子群；
（3）在同构的意义下G是4阶循环群还是Klein四元群？
3.(1)在一棵有2个2度 顶点，4个3度顶点，其余顶点都是树叶的无向树中应该有几片树
叶？
(2)画出两棵非同构的满足上述条件的无向树

。
4.设为一 个偏序集，其中，A={1，2，3，4，6，9，24，54},R是A上的整除关系。

（1）画出的哈斯图；
（2）求A的极大元和极小元；
（3）求B={4,6}的上确界和下确界。
5.求公式
(pq)r
的 主和取范式(化成M
1

M
2

M
3
的形 式)。
６．画一棵带权为2，2，2，3，3，4，5，8的最优二叉树T，并计算它的权W（T）。
四、证明题（每小题6分，共18分）
1.前提：
p(qr),q(rs)

结论:
(pq)s
2.定理（子群判别法1)设H是群
>的非空子集，则H

G当 且仅当
(1)

a，b∈H， a

b∈H；
(2)

a∈H，a∈H。
利用上述定理证明：设H是群
>的非空有限子集。若H关于

封闭，则H是G的子群。
3.用数学归纳法证明n阶无向树T有n-1边。
《离散数学》试题六


一、判断题（每题1分，共10分）
1.任何命题公式都存在惟一的析取范式。 （ ）
2. 封闭的公式在任何解释下都变成命题。 ( )
3.
(pq)(rs)
的层数是3 （ ）
4.
x(BA(x))x(BA(x))
. ( )
5. 设A,B,C是三集合，已知A

B＝A

C，则一定有B＝C. ( )
6.矩阵的等价、相似、合同都是等价关系。 ( )
7.已知a是群集的二阶元，则={a,a}. ( )
8.有界格中某元的的补元不止一个，则它不是分配格。 ( )
9.有向图是强连通的，则它一定是单向连通的，也弱连通的。 ( )
10.二部图
K
3,3
是欧拉图也是哈密顿图。 ( )
二、填空题（每小题2分，共20分）
1.
((pq)q)p
从公式的类型看，它属于 式。
2
－1

2.
x(A(x)B(x))
___________________。
3.设F(x):x是人，H(x):x呼吸，在一阶逻辑中，命题“凡人
都呼吸”的符号化形式为_______ _________。
4.6阶循环群有 个子群。
5. A={a,b},则A的幂集P(A)到自身的双射有__ _个。

123


6. A={1,2,3}，S是A上所有置换构成的集合，则单位元是 ，
S,
构成群 ，

321



的逆元是 ，该元是 阶元。
7.一个3阶有向图的度序列是2，2，4，入度序列是2，0，2，出度序列是 。
8.一无向图存在生成树的充分必要条件是 。
9.最优二叉树有n片树叶，则它有 分支点。
10. 下图的点连通度等于 ，边连通度等于_________。
三、计算题（每小题10分，共50分）
1.设A={ a,b,c},B={b,c,d},C={d,e,f},R
1
={<1,2>,<2,2> ,
<2,3>,<3,3>},R
2
={<2,2>,<2,3>,<3,4>} 求
(1)
AB
(2) A⊕B (3) R
1

(4) R
1
·R
2
(5) R
1
在A上的限制。
2.其中，A={1，2，3，4}，R={ <1,2>,<2,2>,<2,3>,<3,4>},R是A上的二元关系。
（1）画出的R的关系图；
（2）求R的自反、对称、传递闭包；
3.S=Q×Q,其中Q为有理数集合，定义S上的二元运算*，
-1


,∈S，*=,
(1)求<3,4>*<1,2>.
(2)已知<-1,3>*=<-5,1>,求a,b.
(3)*是可交换的吗？是可结合的吗？
4.在一个无向图中有6条边，3度顶点和5度顶点 各1个，其余顶点都是2度点，该图有几
个顶点？
5.在下图中，用克鲁斯卡尔算法构造最小 生成树，写出边添加到生成树的边序列，并画出生

成树。
5
a5
f
1
b
2
7
h
6
6
48
e
6
d
3
c

四、证明题（共20分）
1.前提：
x(F(x)H(x)),x(G(x)H(x))

结论:
x(G(x)F(x))

2.已知
M
n< br>(Z),
(即整数集上2阶方阵构成的集合关于矩阵的加法)构成

< br>
a0



aZ
群,H=





0a





(1)
M
n
(Z),
的单位元是什么?


(2)证明: H是
M
n
(Z),
的子群.
3.叙述并证明关于连通平面图的欧拉公式。


《离散数学》试题七

一、选择题（每小题 2 分，共 20 分）
1、使命题公式p→(p∧q)为假的赋值是 ( )
A.10 B.01 C. 00 D.11
2、令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（ ）
A. p∧┐q B．p∨┐q
C.p∧q D．p→┐q
3、设B不含有x，下列一阶逻辑等值式不正确的是 ( )
．．．
A.
x(A(x)B)xA(x)B

B.
x(A(x)B)xA(x)B

C.
x(A(x)B(x))xA(x)xB(x)


12


的逆元是什么?


34


D.
x(A(x)B(x))xA(x)xB(x)

4、 设X，Y，Z是集合，下列结论不正确的是（ ）
．．．
A．若X

Y,则X

Y=X B．(X-Y)-Z=X-(Y∩Z)
C．
XX
D．
XYX(~Y)

5、设R是集合A上的二元关系，I
A
是上的恒等关系，I
A

R下面四个命题为真的是 ( )
A.R是自反的 B.R是传递的 C.R是对称的 D.R是反对称的
6、设函数f：N→N（N 为自然数集），f(n)=n+1，下面四个命题为真的是 ( )
A. f是单射 B. f是满射 C. f是双射的 D.f非单射非满射
7、集合A={1，2，3，4}，则对 A 的元素进行分类正确的是（ ）
A. {

,{1,2},{3,4}} B. {{1,2,3},{3,4}}
C. {{1},{3,4}} D. {{1,2,3,4}}
8、无向完全图
K
n
有 ( )条边
A. n B. n C. n(n-1) D. n(n-1)2
9、 设G是连通平面图，G中有6个顶点8条边，则G的面的数目是（ ）
A．2 B．3 C．4 D．5
10、一颗二叉树后序遍历的结果是bdeca，中序遍历的结果是badce，则
根结点的右子树有（ ）结点。
A．1 B．2 C．3 D．4
二、填空题（每题2分，共10分）
1、量词否定等值式
xA(x)
___________________。
2、设R是A={1，2，3，4}上的二元关系,R={<1,1>,<1,2>,<2,3>,<3 ,4>},则R的对称闭包
是 。
3、A={1， 2}，
P(A),
是群，

是集合的对称差运算。该群的单位元是
，{1}的逆元是 。
4、图G是平面图的充分必要条件是没有收缩到___或 的子图。
5、无向图G= ,V={a,b,c,d},E={(a,b),(a,c),(a,d),(b,c)},则它的邻 接矩阵
为 ，该图的补图有 条边。
三、计算题（每题8分，共 48分）
1、求公式
(pq)r
的主和取 范式(化成M
1

M
2

M
3
的形式)。
2

2、R
1
={<1,2>,<1,3>,<2,3>,<3 ,3>}, R
2
={<2,2>,<2,3>,<3,4>},
(1) 求 R
1
(2) 求
R
2
R
1

(3)R
1
是函数吗？
3、(1)叙述等价关系的定义；
(2) 设A={1，2，3，4},R={<1,1>,<2,2>,<3,3>,<4,4>,<2,3>,<3,2 >}是A上的等价关系
吗？如果是,给出R确定的对A的分类；如果不是,请说明理由。
4、 已知
M
2
(R),,
(即实数集上2阶方阵构成的集合关于矩阵的加 法和乘法)构成的环。
(1)
M
2
(R),,
的零位元是什么?单位元是什么?
(2)说明
M
2
(R),,
不是无零因子环；
(3)举例说明

不满足消去律。
5、求A到其余顶点的最短路径。 -1
B
8
A
1
C
2
4
2
2< br>6
D
5
F
1
E

6、求下PERT图中各顶 点的最早完成时间TE(v
i
)和最迟完成时间TL(v
i
)，并求出关键路 径。
c
9
a
3
b
1
2
4
d2
8
g
4
j
3
f


1
h
6
2
2
1
e
得分

阅卷人

四、证明题（ 22分）

1、前提：
x(F(x)G(x)H(x)),x(F(x)R(x))

结论:
x(F(x)R(x)G(x))

2、设
>是可交 换群，H={a∈G｜

k∈N(正整数集)，使a=e}，
k
证明H是G的子群。
3、用数学归纳法证明，含有n片树叶的最优二叉树有n-1个分支点.

《离散数学》试卷 八

得分

阅卷人

题号
答案
1

2

3

4

5

6

7

8

9

10

一、选择题（每小题 2分，共 20 分。请将答案填在下面的表格内）

1、从集合分类的角度
看,命题公式可分为
( )
A.永真式、矛盾式 B. 永真式、可满足式、矛盾式
C. 可满足式、矛盾式 D. 永真式、可满足式
2、设B不含有x，
x(A(x)B)
等值于 ( )
A.
xA(x)B
B.
x(A(x)B)
C.
xA(x)B
D.
x(A(x)B)

3、设S,T,M是集合，下列结论正确的是（ ）
A．如果S∪T=S∪M，则T=M B．如果S-T=Φ，则S=T
C．
SSS
D．
STS(~T)

4、设R是集合A上的偏序关系，则R不一定是( )
A.自反的 B. 对称的 C. 反对称的 D. 传递的
5 设R为实数集，定义R上4个二元运算，不满足结合律的是（ ）。
A. f
1
(x,y)= x+y B. f
2
(x,y)=x-y
C. f
3
(x,y)=xy D. f
4
(x,y)=max{x,y}
6、设,
>是一个格，则它不满足( )
A.交换律 B. 结合律 C. 吸收律 D. 消去律
7、设A={1,2},则群
P(A),
的单位元和零元是( )
A.

与A B. A 与

C. {1}与

D. {1}与A
8、下列编码是前缀码的是( ).
A.{1,11,101} B.{1,001,0011} C. {1,01,001,000} D.{0,00,000}
9、下图中既是欧拉图又是哈密顿图的是（ ）
A．
K
9
B．
K
10
C．
K
2,3
D．
K
3,3

10、下图所示的二叉树中序遍历的结果是（ ）

a
b
d
c
e

A．abcde B．edcba C．bdeca D．badce

得分 阅卷人
二、填空题（每题3分，共24分）


1、含3个命题变项的命题公式的主合取范式为
M
0
M
3
M
4
M
6
M
7
,
则它的主析取范式为 。(
表示成mm的形势
)
2、〈
Z
4
，

〉模4加群， 则3是 阶元，3

3= ，3的逆元是 。
3、设V=,其中“+”是普通加法。令

1
(x)=x,
xZ
，
其中有 个自同构.
4、设

< br>

2


2
(x)=-x,

3
(x)=x+5,

4
(x)=2x，

123456< br>

是集合A={1，2，3，4,5,6}上的一个置换，则把它表示成
< br>31546

不相交的轮换的积是 。
4、已知n阶无向简单图G有m条边，则G的补图有 条边。
5、一个有向图是强连通的充分必要条件是 。
7、已知n阶无向图G中有m条边，各顶点的度数均为3。又已知2n-3=m，
则m= .
8、在下图中从A点开始，用普里姆算法构造最小生成树，加入生成树的第三条边是
（ ）。
A
5
B
1
7
2
6
E
8C
3
4
D

得分

阅卷人

三、计算题（每题9分，共 36分）

1、已知命题公式
(pq)(qp)
，
(1) 构造真值表。 (2) 求主析取范式(要求通过等值演算推出)。

2、R
1
={<1,2>,<1,3>,<2,3>}, R
2
={<2,2>,<2,3>,<3,4>},求：
(1)
R
1
R
2
（２）
R
1
(３) 求
R
2
R
1

３、设 为一个偏序集，其中，A={1，2，3，4，6，9，12，24},R是A上的整除关系。
（1）画R出的哈斯图；
（2）求A的极大元和极小元；
（3）求B={4,6}的上确界和下确界。
４、画一棵带权为1，1，1，3，3，5，8的最优二叉树T，并计算它的权W（T）。

得分

阅卷人

四、证明题（共 20分）

1、（7分）前提：
p(qs),q,pr

结论:
rs

2、（7分）A={(0,0),(0,1),(1,0),(1,3),( 2,2),(2,3),(3,1)},
R={<(a,b),(c,d)>| (a,b),(c,d)

A且a+b=c+d }.
(1)证明：R是A上的等价关系．
(2)给出R确定的对A的划分(分类).
3、（6分）设
G,
是群,
S{x|xG且对于yG,xyyx}
,
证明S是G的子群.
《离散数学》试题九

一、选择题（每小题2分，共20分）
1．一个命题公式或一阶逻辑公式的（ ）是不惟一的。
A．主析取范式 B．主合取范式 C．前束范式 D．对偶式
2．下列四个公式正确的是
①
x(A(x)B(x))xA(x)xB(x)
②
x(A(x)B(x))xA(x)xB(x)

③
x(A(x)B(x))xA(x)xB(x)
④
xA(x)xB(x)x(A(x)B(x))

A.①③ B.①④ C.③④ D.②④
3．设集合A={a，b， c，d，e}，偏序关系R的哈斯图下图所示，则元素的关系不正确的是
（ ）。
1

e
c
a
b
d
g

f
A．
cd
B．
ae
C．
ac
D．
de

4．已知A,B是集合│A│=15，│B│=10，│A∪B│=20，则│A∩B│=（ ）
A．10 B．5 C．20 D．13
5．X={a，b，c，d，e}，Y={1，2，3，4}，f从X到Y的映射，其中f(a)=2,
f(b)=4,f(c)=1,f(d)=3,f(e)=4,则f是（ ）
A.双射 B. 满射 C. 单射 D. 不是单射也不是满射
6．设A,B,C是三个非空集合,则( )是正确的.
A.
ABACBC
B.
ABACBC

C.
ABACBC
D.
ABACBC

7．在下图所示的哈斯图中的偏序集不是格的是（ ）

8．下图中,（ ）是欧拉图。

A B C D
9.关于无向树的描述,不正确的是( ).
A. 无向树是连通图、没有回路,每个边都是桥；
B. 无向树是连通图、边数比顶点数少１,任意两个顶点的路径是惟一的；
C. 无向树是连通图、没有回路,每个顶点都是割点；
D. 无向树是连通图、没有回路，每条边都是割边。
10.关于含有n片树叶的最优二叉树描述,不正确的是( ).
A. 含有n片树叶的最优二叉树每个分支点都有两个孩子；

B. 含有n片树叶的最优二叉树分支点的个数是n-1；
C. W(T)等于个分支点的权重（构造最优二叉树时产生）之和；
D. 在权重一定的前提下，含有n片树叶的最优二叉树是惟一的。
二、计算题（每小题10分，共40分）
1.(1)求
((pq)r)p
的主析取范式；
(2)根据主析取范式直接写出主合取范式；
(3)根据主析取范式直接写出真值表。
2.设集合A={a，b，c，d}，A上的关系R={,,,,< d,c>} 求：
（1）画出R的关系图；
（2）求出R的传递闭包tr(R) ；
(3) tr(R)中再添加一些元素后得D(R)，若使D(R)是等价关系，则tr(R)中再 添哪些元
素后得D(R)?
3.(1)下图的最下生成树；
(2)求该图的点连通度和边连通度；
(3)求A到B的最短路径的长度。
A


B
4.(10分)对于下有向图,
(1) 写出度序列和出度序列；
(2) 写出邻接矩阵A，第一行元素之和的含义是什么？
(3) 求
A
,据此说明从A到A的长度为4的回路用多少？
4
A
D
B
三、证明题（每小题10分，共40分）
1.利用推理规则证明。
前提：
xP(x)xQ(x)

C

结论：
x(P(x)Q(x))

2. 设A是正整数集合，在
AA
上定义二元关系R如下：
x,y ,u,vR
当且仅当
xvyu
,证明：R为等价关系。
3. 设 R为实数集，+为普通加法，为普通乘法，是一个代数系统，*是R上的一个二
元运算，使 得
x,yR
，都有
x*y=x+y+xy
证明:是含幺独异点。
4.设f
1
，f
2
都是 一从代数系统到代数系统的同态。设g是从A到B的一个
映射，使得对任意aA ，都有g(a)=f
1
(a) f
2
(a)；证明：如果为一个 可交换半群，
那么g是一个由到的同态映射
卷号：十
离散数学

本题
得分

一、 选择题（选择正确答案，并将其代号写在题干后面的括号里，本
题共6小题,每小题3分，共18分)
1 下列语句中 哪个是真命题？ （）
(A) 我正在说谎。 (B) 请讲普通话。
(C) 如果1＋2＝5，那么雪是黑的。 (D) 如果1+2=3,那么雪是黑的。
2 集合
A{1,2,,10}
上的关系
R{(x,y)|x y10,xA,yA}
,则R的性质为：（ ）
(A) 自反的 (B)对称的 (C) 传递的、对称的 (D) 反自反的、传递的
3下面集合( )关于减法运算是封闭的。
(A) N (B)
{x|x是质数}
； (C)
{2x1|xI}
； (D)
{2x|xI}
。
4设< br>G
1
{0,1,2},
，
G
2
{0,1 },*
，其中

表示模3加法，*表示模2加法，则积代
数
G1
G
2
的单位元是（ ）。
(A)<0,0>； (B) <0,1>； (C) <1,0>； (D) <1,1>
5 下列偏序集中能构成格的是 （ ）。

6 图
G
和
G

的结点 和边分别存在一一对应关系是
G
和
G

同构的 ( ) 。
(A) 必要条件 (B) 充分条件 (C) 充要条件 (D) 既不充分也不必要条件

本题
得分

二、填空题（请将正确答案填入空格内，每小题3分，共18分）
1 命题公式p→q的真值为假，当且仅当_________________。
2 设
G (x):x
是金子,
F(x):x
是闪光的,则命题“金子是闪光的,但闪光的不一定 是金子”
符号化为: 。
3 设整数集合
I
上的二元关系
R{(a,b)|ab},
则
R的对称闭包为： 。

))(bx
1
x
2
)
是布尔代数
{0,a,b,1},
4
f (x
1
,x
2
)((ax
1
)(x
1
x
2
,,

,0,1
上的布尔表达式，则
f(a,b)
。
5 设树T有m个顶点，n条边，则T中顶点与边的关系为: 。
6 不同构的5阶无向树有_______棵。
本题
得分

三、判断题（请在 你认为正确的题后括号内打“√”，错误的打“×”，本
题共6小题，每小题1分，共6分）
1 （PQ）（PQ）是永真式。（ ）
2
{}{,{}}
且
{}{,{}}
。（ ）
3 一种关系，不是自反的，就是反自反的。（ ）
4代数系统中一个元素的左逆元并一定等于该元素的右逆元。（ ）
5 设G为无向图，若G无回路，则G必为一棵树。 （ ）
6 5阶完全图是平面图。（ ）

本题
得分

四、计算题（本题共4小题,每小题6分，共24 分）

1 给定3个命题：P：北京比天津人口多；Q：2大于1；R：15是素数。 求复合命题：
(QR)(PR)
的真值。
2 集合
A{1, 2,3,4}
上的关系
R{(1,1),(1,3),(2,2),(3,1),(3,3) ,(3,4),

(4,3),(4,4)}
，写出关系矩阵
M
R
，并讨论R的性质。
3 设6
,+
6
>是一个群，这里+
6
是 模6加法，Z6={[0 ]，[1]，[2]，[3]，[4]，[5]}，试求出
的所有子群及其相应左陪集。
4 给定一组权值为：2，3，5，7，8，9，请构造一棵最优二叉树，并求W（T）。
本题
得分

五、应用题（本题共1小题,每小题10分，共10分）

下列前提下结论是否有效？
今天或者天晴或者下雨。如果天晴，我去看电影；若我 去看电影，我就不看书。故我在
看书时，说明今天下雨。

本题
得分

六、证明题（本题共3小题,每小题8分，共24分）

1 设
R
是集合A上的一个具有传递和自反性质的关系，
T
是A上的关系，使得
 T
当且仅当
R且R
,证明T是一个等价关系。
2 设
A,,,
是一个布尔代数，如果在A上定义二元运算“☆”为：
a
☆
b
(ab)(ab)
，则是一阿贝尔群。
3 设 T是非平凡无向树，T中结点数大于等于2，T中度数最大的结点有2个，它们的度
数为
k(k 2)
，证明：T中至少有
2k2
个叶结点。