沃顿商学院-历山学院

离散数学试题1
一、单项选择题(本大题共15小题，每小题1分，共15分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、
多选或未选均无分。
1.下列句子为命题的是( )
A.走，看电影去
C.空集是任意集合的真子集
B.x+y>0
D.你明天能来吗?
2.下列式子不是谓词合式公式的是( )
．．
A.(

x)(P(x)→(x)(Q(x) ∧A(x，y)))
C.(

x)P(x)→R(y)
3.下列式子为重言式的是( )
A.P→P∨Q
C.﹁ (P Q)
B.(﹁P∧Q)∧(P∨﹁Q)
D.(P∨Q) (P→Q)
B.(

x)∧(y)∨P(x，y)
D.(x)P(x)∧Q(y，z)
4.设个体域为实数集，特定元素a=0，函数f(x ，y)=x-y，特定谓词F(x，y)为x( )
A.(

x)(

y)F(x，f(f(x，y)，y))
B.(

x)(

y)(﹁F(f(x，y)，x))
C .(

x)(

y)(

z)(F(x，y)→F(f(x ，z)，f(y，z)))
D.(

x)F(f(a，x)，a)
5.对 于公式(

x)(

y)P(x，y)∨Q(x，z)∧(x)P(x，y )，下列说法正确的是( )
A.x是自由变元
C.(

x)的辖域是P(x，y)∨Q(x，z)
B.x是约束变元
D.(

x)的辖域是P(x，y)
6.设论域为{1，2}，与公式(

x)﹁A(X)等价的是( )
A. ﹁A(1) ∨﹁A(2)
C. ﹁A(1) ∧﹁A(2)
B. ﹁A(1)→﹁(A2)
D. A(1) →A(2)
7.设Z
+
是正整 数集，f：Z
+
×Z
+
→Z
+
，f(n，m)=n
m
，则f( )
A.仅是单射
C.是双射
B.仅是满射
D.不是函数
8.下列哪个关系矩阵所对应的关系具有自反性( )

101


A.

111




100



001


C.

001




100



100


B.

011




101



101


D.

010




100



1

10.在整数集上，下面哪个运算不是二元运算( )
．．
A.加法
C.乘法
B.减法
D.除法
11.设A是奇数集合，×为乘法运算，则是( )
A.半群
C.循环群
12.下面不满足结合律的运算是( )
．．．
A.a*b=min(a，b)
C.a*b=2(a+b)
13.右图的最小入度是( )
A.0
B.1
C.2
D.3
14.下面既是汉密尔顿图又是欧拉图的图形是( )
B.a*b=max(a，b)
D.a*b=2ab
B.群
D.交换群

15.一棵树有3个5度点、1个4度点、3个2度点，其它的都是1度，那么它的边数是( )
A.17
C.19
B.18
D.20
二、填空题(本大题共10小题，每小题2分，共20分)
请在每小题的空格中填上正确答案。错填、不填均无分。
16.设命题变元为P，Q，R，则 小项m
100
=________，大项M
010
=________。 < br>18.一个公式，如果量词均在全式的________，其作用域延伸到整个公式的________， 则该公式称为前束范
式。
19.请用联结词﹁，∧表示联结词∨和联结词 ：________，________。
20.设A={l，2，3，4}，A上的二元关系R={ <1，2>，<3，4>，<4，3>}，S={，<3，4>，<4，1>}，
则R

～S=________，(R

S)
-1
=________ 。
21.代数系统
>是整环，则是________，
>是________，且无零因子。

2

22.在实数集R上定义运算a

b=a+b+ab，则幺元为________，元素2的逆 元为________。
23.若回路中，除________外________各不相同，则此回路称为圈(或初级回路)。
24.偶图记为K
n,m
那么当________时，K
n,m
是平 面图，当________时，K
n,m
是非平面图。
25.若图中存在_____ ___，它经过图中所有的边恰好________次，则称该图为欧拉图。
三、计算题(本大题共6小题，每小题5分，共30分)
26.用等值演算求(P→Q)→R的主合取范式。
27.列出(P→(Q∨R)) (P→Q)的真值表。
28．设A={a,b,c,d}，R={，，，，}，求R的传递闭包。
29.设A={2，3，6，12，24，36} ，请画出A上整除关系的哈斯图，并给出子集{6，12，24，36}的下界、
下确界、极大元、最大 元。
31.用矩阵的方法求右图中结点u
2
，u
5
之间长为2的路 径的数目。

四、证明题(本大题共3小题，第32小题8分，第33、34小题各6分，共20分)
32.用推理方法证明：P∨Q，P→R，Q→S├R∨S。
33.设A={|a ，b∈Z
+
，Z
+
为整数集}，A上的关系R={<, >|ad=bc}，证明R是等价关系。
五、综合应用题（本大题共2小题，第35小题6分，第36小题9分，共15分）
35．符号化下面命题，并构造推理证明：人是要死的，苏格拉底是人，所以苏格拉底是要死的。 36．设H是G的有限子集，则
>是群
>的子群当且仅 当
>是群
>的子代数。

离散数学试题2

一、单项选择题(本大题共15小题，每小题1分，共15分)
在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均不得分。
1.下列句子为命题的是( )
A.全体起立!
C.我在说谎
2.下列式子不是谓词合式公式的是( )
．．
A.
(x)(P(x,y)Q(x,z))(z)R(x,z)

B.
(x)(y)P(x,y)Q(x,z)(x)P(x,y)

C.
(x)P(x)Q(x))(x)(P(x)Q(x))


B.x=0
D.张三生于1886年的春天
3

D.
(x)P(x)Q(y,z)

3.下列式子为矛盾式的是( )
A.
PP

C.
PP

B.
P(PQ)

D.
(PQ)

PQ

4.设给定赋值N如 下：个体域为自然数集；特定元素a=0；特定函数f(x,y)=x+y,g(x,y)=xy；特定谓词F( x,y)
为x=y。在赋值N下，下列公式为真的是( )
A.
(x)F(g(x,a),x)

B.
(x)(y)(F(f(x,a),y)F(f(y,a),x))

C.
(x)(y)(z)F(f(x,y),z)

D.
(x)(y)F(f(x,y),g(x,y))

5.对于公式
(x )(P(x,y)Q(x,z))(z)R(x,z)
，下列说法正确的是(
A.y是自由变元
B.x是约束变元
C.
(x)
的辖域是
(P(x,y)Q(x,z))(z)R(x,z)

D.
(x)
的辖域是P(x,y)
6.设论域为{l，2}，与公式
(x)A(x)
等价的是( )
A.A(1)

A(2) B. A(1)

A(2)
C.A(1) D. A(2)

A(1)
7.设Z
+
是 正整数集合，f:Z
+
→Z
+
，f(n)=2
n
-2,则f ( )
A.仅是单射 B.仅是满射
C.是双射 D.不是函数
8.下列关系矩阵所对应的关系具有反自反性的是( )

101

100

A.


011

B.


011







100




101



001

101

C.


001

D.





010




100

< br>

100


10.设A是奇数集合，下列构成独异点的是 ( )
A. B.
C. D.
11.设A是整数集，下列说法正确的是( )
A.有零元 B.有零元
C.有幺元 D.有幺元
12.下列说法不正确
．．．
的是( )

)
4

A.在实数集上，乘法对加法是可分配的
B.在实数集上，加法对乘法是可分配的
C.在某集合的幂集上，∪对∩是可分配的
D.在某集合的幂集上，∩对∪是可分配的
13.右图的最大入度是( )
A.0
B.1
C.2
D.3
14.下列可一笔画成的图形是( )

15.一棵树有5个3度结点，2个2度结点，其它的都是l度结点，那么这棵树的结点数是
( )
A.13
C.16
B.14
D.17
二、填空题(本大题共10小题，每小题2分，共20分)
请在每小题的空格中填上正确答案。错填、不填均不得分。
16.请写出表示分配律的两个命题公式等价定理________,________。
1 7.n个命题变元的________称为大项，其中每个变元与它的否定不能同时出现，但两者必须_____ ___。
19.请用联结词

，

表示联结词

和联结词

：________，________。
20.设A={1，2，3， 4}，B={2，4，6}，则A-B=________，A

B=________。 < br>21.给出A={l，2}上的一个等价关系________，并给出其对应的划分________。
22.设A={l，2，3，4}，A上的二元关系R={<1，2>，<2，3>，<3，2>}，S ={，<2，3>，<4，3>}，
则R∩S=________，(R—S)
-1
=________。
23.代数系统是域，则________和________都是交换群。
24.若图中存在________，它经过图中所有的________，则称该图为汉密尔顿图。
25.n点完全图记为K
n
，那么当________时，K
n
是平 面图，当_____时，K
n
是非平面图。
三、计算题(本大题共6小题，每小题5分，共30分)
26.列出
(QP)

((PR)Q)
的真值表。
27.用等值演算求
P
(Q R)的主析取范式。
28.设A= {1,2,3,4}，给定A上的二元关系R={<1,2>,<2,1>,<2,3>,<3,4>}，求R的 传递闭包。



5

31.用矩阵的方法求右图中结点v
1
，v
3
之间长度为2的路径的数目。





四、证明题(本大题共3小题，第32小题8分，第33、34小题各6分，共20分)
32.用推理方法证明：
PQ,QR,R,(PS)

S
。
33.设H是G的非空子集，则是群的子群当且仅当对 任意a,b

H有a·b
-1

H。
34．证明整数集Z上的大于等于关系“

”是一个偏序关系。
五、综合应用题(本大题共2小题，第35小题6分，第36小题9分，共15分)
35．将下面命题符号化，并构造推理证明：
所有有理数是实数，有些有理数是整数，所以有些实数是整数。
36．某城市拟在六个区之间 架设有线电话网，其网点间的距离如下列有权矩阵给出，请绘出有权图，给出
架设线路的最优方案，并计 算线路的总长度。

0

1


0
< br>
2

9


0

1
0< br>4
0
0
4
0
3
29
08
30
07
0

5


10


< br>6

0


0


8070
51060
离散数学试题3
一、单项选择题（本大题共15小题，每小题1分，共15分）
在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。
1．下列句子不是命题的是（ ）
．．
A．中华人民共和国的首都是北京
C．雪是黑色的
B．张三是学生
D．太好了！
2．下列式子不是谓词合式公式的是（ ）
．．
A．（x）P(x)→R(y)
B．(x) ┐P（x）(x)(P(x)→Q(x))

6

C．(x)(y)(P(x)∧Q(y))→(x)R(x)
D．(x)(P(x,y)→Q(x,z))∨(z)R(x,z)
3．下列式子为重言式的是（ ）
A．(┐P∧R)→Q B．P∨Q∧R→┐R
C．P∨(P∧Q) D．(┐P∨Q)(P→Q)
4．在指定的解释下，下列公式为真的是（ ）
A．(x)(P(x)∨Q(x)),P(x):x=1,Q(x):x=2,论域:{1,2}
B．(x)(P(x)∧Q(x)),P(x):x=1,Q(x):x=2,论域: {1,2}
C．(x)(P(x) →Q(x)),P(x):x>2,Q(x):x=0,论域:{3,4}
D．(x)(P(x)→Q(x)),P(x):x>2,Q(x):x=0,论域:{3,4}
5．对于公式(x) (y)(P(x)∧Q(y))→(x)R(x,y)，下列说法正确的是（ ）
A．y是自由变元 B．y是约束变元
C．(x)的辖域是R(x, y) D．(x)的辖域是(y)(P(x)∧Q(y))→(x)R(x,y)
6．设论域为{1,2}，与公式(x)A(x)等价的是（ ）
A．A(1)∨A(2) B．A(1)→A(2)
C．A(1)∧A(2) D．A(2)→A(1)
7．设Z
+
是正整数集，R是实数集，f:Z
+
→R, f(n)=log
2
n
,
则f（ ）
A．仅是单射 B．仅是满射
C．是双射 D．不是函数
8．下列关系矩阵所对应的关系具有反对称性的是（ ）

101

100

A．


011

B．





011


100






101



001

C．


001



101

D．


010



100




100


10．下列运算不满足
．．．
交换律的是（ ）
A．a*b=a+2b B．a*b=min(a,b)
C．a*b=|a-b| D．a*b=2ab
11．设A是偶数集合，下列说法正确的是（ ）
A．是群 B．是群
C．是群 D．, ,都不是群
12．设*是集合A上的二元运算，下列说法正确的是（ ）
A．在A中有关于运算*的左幺元一定有右幺元
B．在A中有关于运算*的左右幺元一定有幺元

7

C．在A中有关于运算*的左右幺元，它们不一定相同
D．在A中有关于运算*的幺元不一定有左右幺元
13．题13图的最大出度是（ ）
A．0
C．2
14．下列图是欧拉图的是（ ）
B．1
D．3

15．一棵树的3个4度点，4个2度点，其它的都是1度，那么这棵树的边数是（ ）
A．13
C．15
B．14
D．16
二、填空题（本大题共10小题，每小题2分，共20分）
请在每小题的空格中填上正确答案。错填、不填均无分。
16．请写出表示德摩根律的两个命题公式等 价定理___________，___________。
17．n个命题变元的________ ___称为小项，其中每个变元与它的否定不能同时出现，但两者必须
___________。 19．自由变元代入规则是指对某___________出现的个体变元可用个体常元或用与原子公式中所 有个体变
元不同的个体变元去代入，且___________。
20．设A=,B={2 ,4}，则((A)=___________，A×B___________。
21．设A={1,2,3,4}, A上的二元关系R={<1,2>,<2,4>,<3,3>}, S={<1,3>,<2,4>,<4,2>}，则R
2
S=___________，(R
-1
)
2
=___________。
22．设代数系统 是环，则是___________，是___________。 23．在7
-{0},
7
>中，元素2的阶为_________ __，它生成的子群为___________，其中
7
为模7乘法。
三、计算题（本大题共6小题，每小题5分，共30分）
26．给定论域D={1,2}，f(1)=2, f(2)=1, S(1)=F, S(2)=T, G(1,2)=T, G(2,1)=T,在该赋值下，求式子x(S( f(x))
∧G(x, f(x)))的真值。
27．请通过等值演算法求┐(P∧Q)→(P∨Q)的主析取范式。
28．设A={1,2,3,4}，给定A上二元关系R={<1,1>,<1,2>,<2,4>,<4,2 >}，求R的传递闭包。
30．用矩阵的方法求题30图中结点u
i
，u
5
之间长度为2的路径的数目。





8

31．求题31图的最小生成树。




四、证明题（本大题共3小题，第32小题8分，第33、34小题各6分，共20分）
32．用推理方法证明(A∨B)→(C∧D),(D∨F)→E├A→E。
33．证明：设是一个群，则对于任意a,b∈G，必存在惟一的x∈G使得a·x=b。
34．设图G有n个结点，n+1条边，证明：G中至少有一个结点度数≥3。
五、应用题（本大题共2小题，第35小题9分，第36小题6分，共15分）
35．符合化 下列命题，并构造推理证明：三角函数都是周期函数，有些三角函数是连续函数，所以有些周
期函数是连 续函数。
36．两个等价关系的并集不一定是等价关系，试举例说明。

离散数学试题4
一、单项选择题（本大题共15小题，每小题1分，共15分）
在 每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、
多选或 未选均无分。
1．下列为两个命题变元P，Q的小项是（ ）
A．P∧Q∧ P
C． P∧Q
2．下列语句中是真命题的是（ ）
A．我正在说谎
C．如果1+2=3，那么雪是黑的
B．严禁吸烟
D．如果1+2=5，那么雪是黑的
B． P∨Q
D． P∨P∨Q
3．设P：我们划船，Q：我们跑步。命题“我们不能既划船又跑步”符号化为（ ）
A． P∧ Q
C．（PQ）
B． P∨ Q
D．（ P∨ Q）
4．命题公式（P∧（P→Q））→Q是（ ）
A．矛盾式
C．重言式
B．蕴含式
D．等价式
5．命题公式（P∧Q）→R的成真指派是（ ）
A．000，001，110，
C．全体指派
B．001，011，101，110，111
D．无
6．在公式（
x
）F（x，y）→（


y）G（x，y）中变元x是（ ）
A．自由变元
C．既是自由变元，又是约束变元

B．约束变元
D．既不是自由变元，又不是约束变元
9

7．集合A={1，2， „，10}上的关系R={|x+y=10，x∈A，y∈A}，则R的性质是（ ）
A．自反的
C．传递的、对称的
B．对称的
D．反自反的、传递的
8．若R和S是集合A上的两个关系，则下述结论正确的是（ ）
A．若R和S是自反的，则R∩S是自反的
B．若R和S是对称的，则R

S是对称的
C．若R和S是反对称的，则R

S是反对称的
D．若R和S是传递的，则R∪S是传递的
9．R={<1，4>，<2，3>，<3，1> ，<4，3>}，则下列不是
．．
t（R）中元素的是（ ）
A．<1，1>
C．<1，3>
B．<1，2>
D．<1，4>
10．设A={{1，2，3}，{4，5}，{6，7，8}}，下列选项正确的是（ ）
A．1∈A
C．{{4，5}}

A
B．{1，2，3}

A
D．∈A
11．在自然数集N上，下列运算是可结合的是（ ）
A．a

b=a-2b
C．a

b=-a-b
B．a

b=min{a，b}
D．a

b=|a-b|
12．在代数系统中，整环和域的关系是（ ）
A．整环一定是域
C．域一定是整环
B．域不一定是整环
D．域一定不是整环
14．设G为有n个结点的简单图，则有（ ）
A．Δ(G)＜n
C．Δ(G)＞n
B．Δ(G)≤n
D．Δ(G)≥n
15．具有4个结点的非同构的无向树的数目是（ ）
A．2
C．4

二、填空题（本大题共10小题，每小题2分，共20分）
请在每小题的空格中填上正确答案。错填、不填均无分。
B．3
D．5
16．（

x）（

y）（P（x，y）Q（y，z））∧

xP（ x，y）中

x的辖域为________，

x的辖域为________ 。
17．两个重言式的析取是________式，一个重言式与一个矛盾式的析取是_______ _式。
18．设N是自然数集合，f和g是N到N的函数，且f（n）=2n+1，g（n）=n2
，那么复合函数（f

f）（n）
=________（g

f）（n）=________。
19．设复合函数g

f是从A到C的函 数，如果g

f是满射，那么________必是满射，如果g

f是单射 ，
那么________必是单射。
20．设A={1，2}，B={2，3}，则A-A= ________，A-B=________。

10

21．设 S是非空有限集，代数系统中，其中P（S）为集合S的幂集，则P（S）对∪运算的
单位元是________，零元是________。
+
>中，2的阶是________。 22．在6
,○
24． 在下图中，结点v
2
的度数是________。


0
1
25．设图D=，V={v
1
，v
2
，v
3< br>，v
4
}，若D的邻接矩阵A=


1


1
1
0
1
0
0
1
0
0
1

1

，则deg
-
（v）=________，
1
0

1


从v
2
到v
4长度为2的路有________条。
三、计算题（本大题共5小题，第26、27小题各5分， 第28、29小题各6分，第30小题8分，共30分）
+
B，A的幂集P（A）26．已知 A={{}，{，1}}，B={{，1}，{1}}，计算A∪B，A○。
27．构造命题公式（（P∧Q）→P）∨R的真值表。
28．下图给出了一个有向图。（1 ）求出它的邻接矩阵A；（2）求出A
2
，A
3
，A
4
及可 达矩阵P。

29．求下列公式的主合取范式和主析取范式：P∨（ P→（Q∨（ Q→R）））
30．设A={1，2，3，4，6，8，12，24}，R为A上的整除关系，试画< A，R>的哈斯图，并求A中的最大
元、最小元、极大元、极小元。
四、证明题（本大题共3小题，第31、32小题各6分，第33小题8分，共20分）
31 ．在整数集Z上定义：
abab2,a,bZ
，证明：
>是一个群。
32．R是集合A上自反和传递的关系，试证明：R

R=R。
五、应用题（本大题共2小题，第34小题6分，第35小题9分，共15分）
34．构造下面推理的证明。
如果小张和小王去看电影，则小李也去看电影。小赵不去看电影 或小张去看电影。小王去看电影。所
以，当小赵去看电影时，小李也去。
35．今有n个人，已知他们中任何2人的朋友合起来一定包含其余n-2人。试证明：
（1 ）当n≥3时，这n个人能排成一列，使得中间任何人是其两旁的人的朋友，而两头的人是其左边
（或右 边）的人的朋友。
（2）当n≥4时，这n个人能排成一圆圈，使得每个人是其两旁的人的朋友。

11

12