感谢恩师的八个字名言-服装厂实习

离散数学试题一（A卷答案）

一、（10分）证明(A∨B)(P∨Q)，P，(BA)∨PA。
二、（10分）甲、乙、丙、丁4个人有且仅有2个人参加围棋优胜比赛。关于谁参加竞赛，下列4种判断都是正确的：
(1)甲和乙只有一人参加；
(2)丙参加，丁必参加；
(3)乙或丁至多参加一人；
(4)丁不参加，甲也不会参加。
请推出哪两个人参加了围棋比赛。
三、（10分）指出下列推理中，在哪些步骤上有错误？为什么？给出正确的推理形式。
(1)x(P(x)Q(x)) P
(2)P(y)Q(y) T(1)，US
(3)xP(x) P
(4)P(y) T(3)，ES
(5)Q(y) T(2)(4)，I
(6)xQ(x) T(5)，EG
四、（10分）设A＝{a，b，c}，试给出A上的一个二元关系R，使其同时不满 足自反性、反自反性、
五、（15分）设函数g：A→B，f：B→C，
(1)若fg是满射，则f是满射。
(2)若fg是单射，则g是单射。
六、 （15分）设R是集合A上的一个具有传递和自反性质的关系，T是A上的关系，使得Tb>R且R，证明T是一个等价关系。
七、（15分）若是群，H是 G的非空子集，则是的子群对任意的a、b∈H
有a*b
1
∈ H。
－
八、（15分）(1)若无向图G中只有两个奇数度结点，则这两个结点一定是连通的。
(2)若有向图G中只有两个奇数度结点，它们一个可达另一个结点或互相可达吗？

uw

v
离散数学试题一（B卷答案）
一、（15分）设计一盏电 灯的开关电路，要求受3个开关A、B、C的控制：当且仅当A和C同时关
闭或B和C同时关闭时灯亮。 设F表示灯亮。
(1)写出F在全功能联结词组{}中的命题公式。
(2)写出F的主析取范式与主合取范式。
二、（10分）判断下列公式是否是永真式？

1

(1)(xA(x)xB(x))x(A(x)B(x))。
(2)(xA(x)xB(x))x(A(x)B(x)))。
三、（15分）设X为集合，A＝P(X)－{}－{X}且A≠，若|X|＝n，问
(1)偏序集是否有最大元？
(2)偏序集是否有最小元？
(3)偏序集中极大元和极小元的一般形式是什么？并说明理由。
四、（10分） 设A＝{1，2，3，4，5}，R是A上的二元关系，且R＝{<2，1>，<2，5>，<2，4>，
<3，4>，<4，4>，<5，2>}，求r(R)、s(R)和t(R)。
六、（10分）有幺元且满足消去律的有限半群一定是群。
证明 设是一个有幺 元且满足消去律的有限半群，要证是群，只需证明G的任一元
素a可逆。
考虑a， a
2
，„，a
k
，„。因为G只有有限个元素，所以存在k＞l，使得ak
＝a
l
。令m＝k－l，有a
l
*e
＝a
l
*a
m
，其中e是幺元。由消去率得a
m
＝e。
于是，当 m＝1时，a＝e，而e是可逆的；当m＞1时，a*a
m-1
＝a
m-1
* a＝e。从而a是可逆的，其逆
元是a
m-1
。总之，a是可逆的。
七、（20分）有向图G如图所示，试求：
(1)求G的邻接矩阵A。
(2)求出 A
2
、A
3
和A
4
，v
1
到v
4
长度为1、2、3和4的路有多少？
(3)求出A
T
A和AA
T< br>，说明A
T
A和AA
T
中的第(2，2)元素和第(2，3)元素的意 义。
(4)求出可达矩阵P。
(5)求出强分图。
离散数学试题二（A卷答案）
一、（10分）判断下列公式的类型（永真式、永假式、可满足式）？
1)((PQ)∧Q)((Q∨R)∧Q) 2)((QP)∨P)∧(P∨R)
3)((P∨Q)R)((P∧Q)∨R)
二、（8分）个体域为{1，2}，求xy（x+y=4）的真值。
三、（8分）已知集 合A和B且|A|=n，|B|=m，求A到B的二元关系数是多少？A到B的函数数是多少？
四、 （10分）已知A={1,2,3,4,5}和R={<1,2>,<2,1>,<2,3>,<3,4>,<5 ,4>}，求r(R)、s(R)和t(R)。
五、(10分) 75个儿童到公园游乐场，他们在那 里可以骑旋转木马，坐滑行铁道，乘宇宙飞船，已知其
中20人这三种东西都乘过，其中55人至少乘坐 过其中的两种。若每样乘坐一次的费用是0.5元，公园
游乐场总共收入70元，求有多少儿童没有乘坐 过其中任何一种。
六、（12分）已知R和S是非空集合A上的等价关系，试证：1）R∩S是A上的 等价关系；2）对a∈A，[a]
R
∩S
=[a]
R
∩[a]
S
。
七（10分）设A、B、C、D是集合，f是A到B的双射，g是C到D的双射，令h ：A×CB×D且

2

∈A×C，h()＝。证明h是双射。
八 、（12分）是个群，u∈G，定义G中的运算“”为ab=a*u-1*b，对任意a,b∈G ，求证：
也是个群。
九、（10分）已知：D=，V={1,2,3 ,4,5}，E={<1,2>,<1,4>,<2,3>,<3,4>,<3,5>,<5,1>}，求D的邻 接
距阵A和可达距阵P。
离散数学试题二（B卷答案）
一、（10分）求命题公式(P∧Q)(PR)的主合取范式。
解：(P∧Q) (PR)（(P∧Q)(PR)）∧（(PR)(P∧Q)）
（(P∧Q)∨(P∧R)）∧（(P∨R)∨(P∨Q)）
(P∧Q)∨(P∧R)
(P∨R)∧（Q∨P）∧（Q∨R）
(P∨Q∨R)∧(P∨Q∨R)∧（P∨Q∨R）∧（P∨Q∨R）
M
1
∧M
3
∧M
4
∧M
5

二、（8分）叙述并证明苏格拉底三段论
三、（8分）已知A、B、C是三个集合，证明A∩(B∪C)=(A∩B)∪(A∩C)
四 、（10分）已知R和S是非空集合A上的等价关系，试证：1）R∩S是A上的等价关系；2）对a∈A，[a ]
R
∩S
=[a]
R
∩[a]
S
。
五、(10分) 设A＝{a，b，c，d}，R是A上的二元关系，且R＝{， ，，}，
求r(R)、s(R)和t(R)。
六、(15分) 设A、 B、C、D是集合，f是A到B的双射，g是C到D的双射，令h：A×CB×D且
∈A ×C，h()＝。证明h是双射。
七、(12分)设是 群，H是G的非空子集，证明是的子群的充要条件是若a，bH，则
有a*b H。
八、（10分）设G=是简单的无向平面图，证明G至少有一个结点的度数小于等于5。
九.G=,A={a,b,c},*的运算表为：(写过程，7分)
-1

（1）G是否为阿贝尔群？

（2）找出G的单位元；（3）找出G的幂等元（4）求b的逆元和c的逆元
离散数学试题三(A卷答案）


3

一、证明题（10分）
1) (P∧Q∧AC)∧(AP∨Q∨C) (A∧(PQ))C。
2) (PQ) PQ。
二、分别用真值表法和公 式法求(P(Q∨R))∧(P∨(QR))的主析取范式与主合取范式，并写出其
相应的成真赋 值和成假赋值（15分）。
三、推理证明题（10分）
1）P∨Q，Q∨R，RSPS。
2) x(P(x)Q(y)∧R(x))，xP(x)Q(y)∧x(P(x)∧R(x))
四 、某班有学生60人，其中有38人学习PASCAL语言，有16人学习C语言，有21人学习COBOL语< br>言；有3个人这三种语言都学习，有2个人这三种语言都不学习，问仅学习两门语言的学生数是多少？(1 0
分)
五、已知A、B、C是三个集合，证明(A∪B)－C＝(A－C)∪(B－C) （10分）
六、已知R、S是N上的关系，其定义如下：R={| x,yN∧y=x}，S={| x,yN∧y=x+1}。求
R、R*S、S*R、R{1,2}、S[{1,2}]（10分）
七、证明：R是传递的R*RR（10分）。
八、证明整数集I上的模m同余关系R={|xy(mod m)}是等价关系。其中，xy(mod m)的含义是x-y
可以被m整除（15分）。
九、若f:A→B和g:B→C是双射，则（gf）=fg（10分）。

-1-1-1
-1
2
离散数学试题三(B卷答案）
一、证明题（10分）
1)((P∨Q)∧(P∧(Q∨R)))∨(P∧Q)∨(P∧R)T
2) xy(P(x)Q(y)) (xP(x)yQ(y))
三、推理证明题（10分）
1)(P(QS))∧(R∨P)∧QRS
2) x(A(x)yB(y))，x(B(x)yC(y))xA(x)yC(y)。
四、只要今天天气不好，就一定有考生不能提前进入考场，当且仅当所有考生提前进入考场，考试才能准
时进行。所以，如果考试准时进行，那么天气就好（15分）。
五、已知A、B、C是三个集合，证明A∩(B∪C)=(A∩B)∪(A∩C) （10分）
六、A={ x
1
,x
2
,x
3
}，B={ y
1
,y
2
}，R={1
, y
1
>,2
, y
2
>,3
, y
2
>}，求其关系矩阵及关系图（10分）。
七、设R={<2,1>,<2,5 >,<2,4>,<3,4>,<4,4>,<5,2>}，求r(R)、s(R)和t(R)，并作出它们及R 的关系图（15
分）。
八、设R
1
是A上的等价关系，R
2
是B上的等价关系，A≠且B≠。关系R满足：<1
，y
1
>，< x
2
，y
2
>>
∈R1
，x
2>∈R
1
且1
，y
2
>∈R
2
， 证明R是A×B上的等价关系（10分）。
九、设f：AB，g：BC，h：CA，证明：如果 hgf＝I
A
，fhg＝I
B
，gfh＝I
C
，则f、g、h均为双
射，并求出f、g和h（10分）。

4
－1－1－1

离散数学试题四（A卷答案）
一、（10分）求(PQ)(P∧(Q∨R))的主析取范式
二、（10分）在某次研讨会的休息时间，3名与会者根据王教授的口音分别作出下述判断：
甲说：王教授不是苏州人，是上海人。
乙说：王教授不是上海人，是苏州人。
丙说：王教授既不是上海人，也不是杭州人。
王教授听后说：你们3人中有一个全说对了，有 一人全说错了，还有一个人对错各一半。试判断王
教授是哪里人？
三、（10分）证明tsr(R)是包含R的且具有自反性、对称性和传递性的最小关系。
四 、（15分）集合A＝{a，b，c，d，e}上的二元关系R为R＝{，，， ，
，，，，，，，，，}，
(1)写出R的关系矩阵。
(2)判断R是不是偏序关系，为什么？
五、（10分）设A、B、C和D为任意集合，证明(A－B)×C＝(A×C)－(B×C)。 七、（15分）设是一代数系统，运算*满足交换律和结合律，且a*x＝a*yx＝y，证明 ：若G
有限，则G是一群。
八、（20分）（1）证明在n个结点的连通图G中，至少有n－1条边。
2
（2） 给定简单无向图G＝，且|V|＝m，|E|＝n。试证：若n≥
C
m1
＋2，则G是哈密尔顿
图
离散数学试题（四B卷答案）
一、（10分）使用将命题 公式化为主范式的方法，证明(PQ)(P∧Q)(QP)∧(P∨Q)。
二、（10分）证明下述推理： 如果A努力工作，那么B或C感到愉快；如果B愉快，那么A不努力工作；如果D愉快那么C不愉快。所以，如果A努力工作，则D不愉快。
三、（10分）证明xy(P(x)Q(y))(xP(x)yQ(y))。
四、（10分）设A＝{，1，{1}}，B＝{0，{0}}，求P(A)、P(B)－{0}、P(B) B。
五、（15分）设X＝{1，2，3，4}，R是X上的二元关系，R＝{<1，1>，<3，1 >，<1，3>，<3，3>，
<3，2>，<4，3>，<4，1>，<4，2>，<1，2>}
(1)画出R的关系图。
(2)写出R的关系矩阵。
(3)说明R是否是自反、反自反、对称、传递的。
六、（15分）设函数f：R×RR×R，f定义为：f()＝。
(1)证明f是单射。
(2)证明f是满射。

5

(3)求逆函数f。
(4)求复合函数f
f和ff。
七、（15分）给定群，若对G中任意元a和b，有a*b＝(a*b)，a*b＝(a*b)，a* b＝(a*b)，
试证是Abel群。
八、（15分）（1）证明在n个结点的连通图G中，至少有n－1条边。
（2）试给出|V |＝n，|E|＝(n－1)(n－2)的简单无向图G＝是不连通的例子。
1
2
333444555
－1
－1
全国2010年7月高等教育自学考试
离散数学试题
课程代码：02324

一、单项选择题（本大题共15小题，每小题1分，共15分）
在每小题列出的四个备选项中 只有一个是符合题目要求的，请将其代码填写在题后的括号内。错
选、多选或未选均无分。
1．下列句子不是命题的是（ ）
．．
A．中华人民共和国的首都是北京
C．雪是黑色的
B．张三是学生
D．太好了！
2．下列式子不是谓词合式公式的是（ ）
．．
A．（x）P(x)→R(y)
B．(x) ┐P（x）(x)(P(x)→Q(x))
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
C．P∨(P∧Q)
B．P∨Q∧R→┐R
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是自由变元
C．(x)的辖域是R(x, y)
B．y是约束变元
D．(x)的辖域是(y)(P(x)∧Q(y))→(x)R(x,y)
6．设论域为{1,2}，与公式(x)A(x)等价的是（ ）
A．A(1)∨A(2)
C．A(1)∧A(2)

B．A(1)→A(2)
D．A(2)→A(1)
6

7 ．设Z
+
是正整数集，R是实数集，f:Z
+
→R, f(n)=log
2
n
,
则f（ ）
A．仅是入射
C．是双射
B．仅是满射
D．不是函数
8．下列关系矩阵所对应的关系具有反对称性的是（ ）

101



011
A．

 


100



001



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

011
B．




101



101



010
D．




1 00


9．设R
1
和R
2
是集合A上的相容关系 ，下列关于复合关系R
1
R
2
的说法正确的是（ ）
A．一定是等价关系
C．一定不是相容关系
10．下列运算不满足交换律的是（ ）
．．．
A．a*b=a+2b
C．a*b=|a-b|
B．a*b=min(a,b)
D．a*b=2ab
B．一定是相容关系
D．可能是也可能不是相容关系
11．设A是偶数集合，下列说法正确的是（ ）
A．是群
C．是群
B．是群
D．, ,都不是群
12．设*是集合A上的二元运算，下列说法正确的是（ ）
A．在A中有关于运算*的左幺元一定有右幺元
B．在A中有关于运算*的左右幺元一定有幺元
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
7

二、填空题（本大题共10小题，每小题2分，共20分）
请在每小题的空格中填上正确答案。错填、不填均无分。
16．请写出表示德摩根律的两个命题公式等 价定理___________，___________。
17．n个命题变元的________ ___称为小项，其中每个变元与它的否定不能同时出现，但两者必须
___________。 18．前提引入规则：在证明的任何步骤上都可以___________，简称___________规 则。
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乘法。
24．设< A,≤>是一个___________，如果A中任意两个元素都有___________，则称为格。
25．若一条___________中，所有的___________均不相同，称为迹。

三、计算题（本大题共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的传递闭包。
29．对题29图所示格，找出它的所有的4元子格。






30．用矩阵的方法求题30图中结点u
i
，u
5
之间长度为2的路径的数目。
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分）

8

35．符合化下列命题，并构造推理证明：三角函数都是周期函数，有些三角函数是连续 函数，所以有些
周期函数是连续函数。
36．两个等价关系的并集不一定是等价关系，试举例说明。
一、单项选择题：（每小题1分，本大题共10分）
1．命题公式
P(QP)
是（ ）。
A、 矛盾式； B、可满足式； C、重言式； D、等价式。
2．下列各式中哪个不成立（ ）。
A、
x(P(x)Q(x))xP(x)xQ(x)
；
B、
x(P(x)Q(x))xP(x)xQ(x)
；
C、
x(P(x)Q(x))xP(x)xQ(x)
；
D、
x(P(x)Q)xP(x)Q
。
3．谓词公式
x(P(x)yR(y))Q(x)
中的 x是（ ）。
A、自由变元； B、约束变元；
C、既是自由变元又是约束变元； D、既不是自由变元又不是约束变元。
4．在0

之间应填入（ ）符号。
A、= ； B、

； C、

； D、

。
5．设< A ，

> 是偏序集，
BA
，下面结论正确的是（ ）。
A、
B
的极大元
bB
且唯一； B、< br>B
的极大元
bA
且不唯一；
C、
B
的上界
bB
且不唯一； D、
B
的上确界
bA
且唯一。
6．在自然数集N上，下列（ ）运算是可结合的。
（对任意
a,bN
）
A、
abab
； B、
abmax(a,b)
；
C、
aba5b
； D、
abab
。
7．Q为有理数集N，Q上定义运算*为a*b = a + b – ab ,则的幺元为（
A、a； B、b； C、1； D、0。
8．给定下列序列，（ ）可以构成无向简单图的结点次数序列。
A、（1，1，2，2，3）； B、（1，1，2，2，2）；
C、（0，1，3，3，3）； D、（1，3，4，4，5）。

9
。


）

9．设G是简单有向图，可达矩阵P(G)刻划下列 （ ）关系。
A、点与边； B、边与点； C、点与点； D、边与边。
10．一颗树有两个2度结点，1个3度结点和3个4度结点，则1度结点数为（ ）。
A、5； B、7； C、9； D、8。
二、填空：（每空1分，本大题共15分）
1．在自然数集中，偶数集为
N
1
、奇数集为
N
2
，则
N
1
N
2
= ；
N
1
N
2
= 。
2．设
X{1,2,3,4},R{1,2,2,4，3,3}
，则
r (R) = ；s (R) = ；t (R) = 。
3．设R为集合A上的等价关系， 对
aA
，集合
[a]
R
= ，
称为元素a形成的R等价类，
[a]
R

，因为 。
4．任意两个不同小项的合取为 ，全体小项的析取式为 。
5．设
Q(x):x为偶数
，
P(x):x为素数
，则下列命题 ：（1）存在唯一偶素数；（2）至多有一个偶素数；
分别形式化：（1） ；
（2） 。
6．设T为根树，若 ，则称T为m元树；
若 则称T为完全m叉树。
7．含5个结点，4条边的无向连通图（不同构）有 个，
它们是 。
三、判断改正题：（每小题2分，本大题共20分）
1．命题公式
(A(AB))B
是一个矛盾式。 （ ）
2．任何循环群必定是阿贝尔群，反之亦真。 （ ）
3．根树中最长路径的端点都是叶子。 （ ）
4．若集合A上的关系R是对称的，则
R
1
也是对称的。 （ ）
5．数集合上的不等关系（≠）可确定A的一个划分。 （ ）
6．设集合A、B、C为任意集合，若A×B = A×C，则B = C。 （ ）
7．函数的复合运算“。”满足结合律。 （ ）
8．若G是欧拉图，则其边数
e
合结点数
v
的奇偶性不能相反。 （ ）

10

9．图G为（n , m）图，G的生成树
T
G
必有n个结点。 （ ）
10．使命题公式
P(QR)
的真值为F的真值指派的P、Q、R值分别是T 、F、F。
（ ）
四、简答题（每小题5分，本大题共25分）
1．设
H, 
和
K,
都是群
G,
的子群，问
HK, 
和
HK,
是否是
G,
的子
并说明理由
2．设
A{2，3，4，9}
，
B{2，4，7，10,12}
，从A到B的关系
R{a,baA,bB,且a整除b}
，试给出R的关系图和关 系矩阵，并说明此关系是否为函
数？为什么？
3．设
S,
是半群，< br>O
L
是左零元，对任
xS,xO
L
是否是左零元？为什么 ？
4．某次会议有20人参加，其中每人至少有10个朋友，这20人拟围一桌入席，用图论知识说明 是否可
能每人邻做的都是朋友？（理由）
5．通过主合取范式，求出使公式
(PQ)R
的值为F的真值指派。

五、证明题：（共30分）
1．设R为集合A上的二元关系，如果R是反自反的和可传递的，则R一定是反对称的。
2． 试证明若
G,
是群，
HG
，且任意的
aH
，对每 一个
xG
，有
axxa
，则
H,
是
G,
的子群。
3．设G是每个面至少由
k
（
k3
）条边围成的连通平面图，试证明
e
为边数。
4．符号化下列各命题，并说明结论 是否有效（用推理规则）。任何人如果他喜欢美术，他就不喜欢体育。
每个人或喜欢体育，或喜欢音乐， 有的人不喜欢音乐，因而有的人不喜欢美术。
离散数学试题<二>

一、选择题（10×2）
1．下述说法错误的是（ ）
A．若
aA
则
aAB
B．若
aA
则
aAB

C．若
aAB
，则
aA
D．若
A⊂B
，则
ABA


11
k(v 2)
，其中
v
为结点数，
e
k2

2．设G 是连通平面图，G中有11个结点，5个面，则G中边的条数是（ ）
A．10 B．12 C．16 D．14
3．以下关系中能构成函数的是（ ）
A．

(1.2),(2.1),(3.4),(4.3)

B．

(1.2),(1.1),(2.2),(3.2)


C．

(1.2),(2.3),(3.4),(4.1)

D．

(1.4),(3.1),(2.3),(4.1),(3.2)


4．图G如下图所示，则G是（ ）
A．欧拉图，非哈密顿图 B．哈密顿图，非欧拉图
C．非欧拉图，非哈密图 D．欧拉图且哈密顿图

5．下列代数系统能够构成群的是（ ）
A．（Q；+） B．（Q，-） C．（R；·） D．（I，+）
6．关于有补格的描述不正确的是（ ）
A．有补格必有界 B．有补格中每个元素的补元一定存在
C．有补格满足德摩根定律 D．有补格的元素不一定有限
7．若图G的所有回路均为偶数长，则G（ ）
A．G是欧拉图 B．G是哈图 C．G是平面图 D．G是二部图
8．下述公式正确的是（ ）
A．
PQQP
B．
PQQP

C．
PQQP
D．
PQPQ

9．设A=｛a,b,c,d｝，A上的关系ρ=｛（a, b),(b,a),(c,a),(c,b),(a,a),(b,b)｝,则
ρ是（ ）
A．自反的 B．对称的 C．反对称的 D．传递的
10．复合语句“他工作很努力；但是思想僵化”中的逻辑联结词为（ ）
A．
∨
B．
∧
C．
→
D．
↔

二、填空（10×2）

12

1、设
U{1, 2,3,4,5,6,7},A{1,3,5,7},B{1,2,6,7}

则A

B
_______________________________ _。

2、已知
A{0,1,2,3},

{(0,1),(1 ,2),(2,1),(0,0)}
，那么

2
=____________ ___
3、已知
f(x)4x2g(x)x
2
5则gf
__________________
4、
R,
为实数及四则运算的乘法， 请写出的幂等元___________________
5、相比于独异点和半群，群的最重要性质是___________________
6、 设
L;,
为代数系统，
,
为二元运算若
,
还满足交换律，结合律和__________律，
则
L;,
为一个格。
7、图G中长度最短的路称为___________________
8、符号化下列语句：他不但学习好，而且身体棒___________________
9、集合代数是一种___________________格
10、半群（A：是B：不是）___________________群
三、简答题（3×10）
1、一棵树有1个结点度数为5，2个结点度数为4，5个结点度数 为2，14个结点度数为1，问度数为3
的结点有几个？
2、判断下面两个图是否为平面图， 若认为是平面图，请画出其相应的平面图解，否则说明它为什么不是
平面图。（10分）

V
2


V
2

V
1
V
6
V
7


V
3

V
1



V
10

V
8

V
5

V
9


V
3
V
4



V
5

V
4

G
１

G
２

111
3、
f:AB,g:BC
，且
f
和
g
都是可逆的，证明函数复合运算满足：
(gf)fg< br>
四、证明题（3×10）
1、试证明群的两个子群的交集也构成的子群。
2、若G是连通平面图，则G中必有一个结点V，使得deg(V)≤5
3、形式证明：如果 他努力学习，则他不会不及格；如果他不爱打麻将，则他会努力学习；结果是他考试
不及格，那么他肯定 爱打麻将。

13

没有标题
一、填空题：（每空1分，本大题共15分）
1．给定命题公式A、B，若 ，则称A和B是逻辑相等的。
2．命题公式
(PQ)
的主析取范式为 ，主合取范式的编码表示
为 。
3．设E为全集， ，称为A的绝对补，记作～A，
且～（～A）= ，～E = ，～

= 。
4．设
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< br>6
{{a},{a,c}}

则A的覆盖有 ，A的划分有 。
5．设S是非空有限集，代数系 统＜

（S），，＞中，

（S）对的幺元为 ，
零元为 。

（S）对的幺元为 ，零元为 。
6．若
GV,E
为汉密尔顿图，则对于结点集V的每个非空子集S，均有
W(G-S)
S
成立，其中W(G-S)是 。

二、单项选择题：（每小题1分，本大题共10分）
1．下面命题公式（ ）不是重言式。
A、
Q(PQ)
； B、
(PQ)P
；
C、
(PQ)(PQ)
； D、
(PQ)(PQ)
。
2．命题“没有不犯错误的人”符号化为（ ）。
x
是人，
P(x)：x
犯错误。 设
M(x)：
A、
x(M(x)P(x))
； B、
(x(M(x)P(x)))
；
C、
(x(M(x)P(x)))
； D、
(x(M(x)P(x)))
。
3．设
A{}
，B =
((A))，
下列各式中哪个是错误的（ ）。

14

A、
B
； B、
{}B
， C、
{{}}B
； D、
{,{}}
(A)。

4．对自然数集合N，哪种运算不是可结合的，运算定义为任
a,bN
（ ）。
A、
abmin(a,b)
； B、
aba2b
；
C、
abab3
； D、
aba,b(mod3)
。
5．设Z为整数集，下面哪个序偶不够成偏序集（ ）。
A、
Z,

(：
小于关系
)
； B、
Z,(：
小于等于关系
)
；
C、
Z,(：等
于关系
)
； D、
Z,(：整除
关系
)
。
6．任意具有多个等幂元的半群，它（ ）。
A、不能构成群； B、不一定能构成群；
C、不能构成交换群； D、能构成交换群。
7．设
A,
是一个有界格，它也是有补格，只要满足（ ）。
A、每个元素都有一个补元； B、每个元素都至少有一个补元；
C、每个元素都无补元； D、每个元素都有多个补元。
8．设
GV,E
为无向图，
V7,E23
，则G一定是（ ）。
A、完全图； B、树； C、简单图； D、多重图。
9．给定无向图
GV,E
，如下图所示，下面哪个边集不是其边割集（ ）。
A、
{v
1
,v
4
,v
3
,v
4
}
；
B、
{v
1
,v< br>5
,v
4
,v
6
}
；
C、
{v
4
,v
7
,v
4
,v
8
}< br>；
D、
{v
1
,v
2
,v
2
,v
3
}
。
10．有n个结点
(n3)
，
m
条边的连通简单图是平面图的必要条件（ ）。
A、
n3m6
； B、
n3m6
； C、
m3n6
； D、
m3n6
。
三、判断改正题：（每小题2分，本大题共20分）
1．设A，B为任意集合，不能
AB且AB
。 （
2．设R是集合A上的关系，若
R
1
,R
2< br>是对称的，则
R
1
R
2
也是对称的。（

15
）



）

3．群中可以有零元（对阶数大于1的群）。 （ ）
4．循环群一定是Abel群。 （ ）
5．每一个链都是分配格。 （ ）
6．不可能有偶数个结点，奇数条边的欧拉图。 （ ）
7．图G中的每条边都是割边，则G必是树。 （ ）
9．公式
x(P(x)Q(x))R(y)
中
x
的辖域为
P(x)
。 （ ）
10．公式
xP(x)yQ(x,y)
的前束范式为

xy(P(x)Q(x,y))
。 （ ）

四、简答题（共20分）
1．用等值演算法求下面公式的主析取范式，并求其成真赋值。
(PQ)R


2．集合
A{1,2,3,4}
上的关系
R{1,1, 1,3,2,2,3,3,3,1,3,4,4,3,4,4}
，写出关
系矩阵
M
R
，画出关系图并讨论R的性质。

3．有n
个药箱，若每两个药箱里有一种相同的药，而每种药恰好在两个药箱中，问共有多少种
药品？

4．一棵树T中，有3个2度结点，一个3度结点，其余结点都是树叶。
（1）T中有几个结点；
（2）画出具有上述度数的所有非同构的无向图。

五、证明题：（35分）
1．符号化下列各题，并说明结论是否有效（用推理规则）。
凡15的倍数都是3的倍数，凡15的倍数都是5的倍数，所以有些5的倍数是3的倍数。
2．用推理规则证明：

16

(AB)(CD), (BE)(DF),(EF),AC
├ A
3．设函数
f：AB
，
g：BC
，若
gf
是满射的，则
g
是满射的 。
4．当且仅当G的一条边
e
不包含在G的闭迹中时，
e
才是G的 割边。
5．设
S,,
是一个分配格，
aS
，令
f(x)xa
，对任意
aS
，证明：
f
是
S,, 
到自身的格同态映射。
2006～2007学年 第1学期
《离散数学》试卷 A
（试卷共6页，答题时间120分钟）
一、选择题（每小题 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}

17

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=,其中“+ ”是普通加法。
xZ
，令

1
(x)=x,

2
(x)=-x,

3
(x)=x+5,

4
(x)=2x，
其中有 个自同构.

1 23456

4、设




231546


是集合A={1，2，3，4,5,6}上的一个置换，则把它表示成不
< br>相交的轮换的积是 。
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


18

得分 阅卷人
三、计算题（每题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
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的子群.

19