北京工业大学经管学院期末试卷
《离散数学》（A）
学号姓名：成绩
一、单项选择题（每题2分，共18分）
1．令P：今天下雪了，Q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（ D ） ．
A．P→Q
C．P∧Q B．P∨Q D．P∧Q
p→q，蕴涵式，表示假设、条件、“如果，就”。
“→”与此题无关
2.关于命题变元P和Q的极大项M1表示(C)。 书P15-P20，此题换作p、q更容易理解
A.┐P∧QB.┐P∨Qp∨┐q ---- 01---- 1 ----- M
1C.P∨┐QD.P∧┐Q
3.设R（x）：x是实数；S（x,y）：x小于y。用谓词表达下述命题：不存在最小的实数。其中错误的表达式是：（ D ）
4.在论域D={a,b}中与公式（x）A（x）等价的不含存在量词的公式是（ B ）
A.A(a)A(b)
C.A(a)A(b)
5．下列命题公式为重言式的是（ C ）
A．Q→（P∧Q）
C．（P∧Q）→PB．P→（P∧Q） D．（P∨Q）→QB.A(a)A(b) D.A(b)A(a)
牢记→真假条件，作为选择题可直接代入0、1，使选项出现1→0，排除。熟练的可直接看出C不存在1→0的情况
6.设A=｛1，2，3｝，B=｛a,b｝，下列二元关系R为A到B的函数的是(A)
A.R=｛,,｝
B.R=｛,｝
C.R=｛,,,｝
D.R=｛,,,｝
-第 1页
7.偏序关系具有性质（ D ）背
A.自反、对称、传递
B.自反、反对称
C.反自反、对称、传递
D.自反、反对称、传递
8.设R为实数集合，映射:RR,(x)x22x1,则 是(D).(A) 单射而非满射(C) 双射(B) 满射而非单射(D) 既不是单射也不是满射.
书P96.设函数f：A→B
（1）若ranf=B，则f是满射的【即值域为B的全集，在本题中为R，该二次函数有最高点，不满足】
（2）若对于任何的x1,x2∈A , x1≠x2,都有f(x1)≠f(x2)，则称f是单射的【即x,y真正一一对应，甚至不存在一个y对应多个x。显然，本题为二次函数，不满足】
（3）若f既是满射的，又是单射的，则称f是双射的【本题中两个都不满足，既不是单射也不是满射】
二、填空题（每空2分，共22分）
１.设Q为有理数集，笛卡尔集S=Q×Q，*是S上的二元运算，,∈S,*=, 则*运算的幺元是__________。∈S, 若a≠0， 则的逆元是____________。书P123定义
２.在个体域D中，公式xG(x)的真值为假当且仅当__某个G(x)的真值为假__，公式xG(x)的真值为假，当且仅当__所有G(x)的真值都为假__。
３.给定个体域为整数域，若F（x）：表示x是偶数，G（x）：表示x是奇数；那么，(x)F(x)(x)G(x)是一个(x)(F(x)G(x))是一个
４.设Aa,b,c ,A上的二元关系Ra,b,b,c,则r(R)
{,,,,,} ；
。
书P8
9、P85.自反闭包：r(R) = R U R0
={,} U {,,,} ={,,,,,}对称闭包：s(R) = R U R-1 = {,} U {,} = {,,,}-第 2页
传递闭包：t(R) = RUR2 UR3U……
５.设X={1,2,3},Y={a,b}，则从X到Y的不同的函数共有___8___个.
书P96，B上A的概念：
设Ａ、Ｂ为集合，所有从Ａ到Ｂ的函数构成集合ＢA ，读作“B上A”
如果|A| = m，|B| = n，m、n不全是0，则|BA| = nm
即，若题中给出集合A有m个元素，B有n个元素，可直接用nm 计算出A到B的函数个数。本题中为23 = 8
６.设,,a,bG，则（a-1）-1，（ab）-1b-1 * a-1。
书P139公式
7.设X={1，2，3}，f：X→X，g：X→X，f={,,},
g={,,}，则fg=__{,,}___，gf=__{,,}__。 书P82-8
3合成：FG = {|xGz∧zFy}
需要说明的是，这里的合成FG是左复合，即G先作用，然后将F复合到G上。之前的答案“有误”，因为采用了右复合。这两种合成定义所计算的合成结果是不相等的，但两个定义都是合理的，只要在体系内部采用同样的定义就可以了。总之，在咱们的离散里牢记左复合。
三、计算题（每题9分，共36分）
1.设集合A＝{1, 2, 3,4,5}，A上的关系R＝{,,,,
3>,,,}
(1) 画出R的关系图；
(2)问R具有关系的哪几种性质(自反、对称、传递、反对称).自反性、传递性
书P87表格，根据关系图可直接判断性质……
(3) 给出R的传递闭包。
R={,,,,,,,}
-第 3页
R2 = RR = {,,,,,,,}R3 = R2R = {,,,,,,,}……
所以，t(R) = {,,,,,,,}
2.集合S={a,b,c,d,e}上的二元运算*的运算表如下，求出它的幺元，零元，及逆
元。 *abcde
abaccc
babcde
cccccc
dedcba
edecdb
幺元：b
零元：c
逆元：a-1 =a,b-1 =b, d-1 =d,e-1 =e
书P123定义
3．求合式公式A=P→((P→Q)∧┐(┐Q∨┐P))的主析取范式及成真赋值。
A = P→((┐P∨Q)∧ (Q∧P))
= P→((┐P∨Q)∧ (Q∧P))
= P→((┐P ∧Q∧P)∨(Q∧Q∧P))
= P→(Q∧P)
= ┐P∨(Q∧P)
= (┐P∧(Q∨┐Q))∨(Q∧P)
= (cP∧Q)∨(┐P∧┐Q)∨(P∧Q)
= (┐P∧┐Q)∨(┐P∧Q)∨(P∧Q)
= m0∨m1∨m
3成真赋值为00，01，1
14．求在1到1000000之间有多少个整数既不是完全立方数，也不是完全平方数？-第 4页
完全平方数的个数：1000=1000000，所以有1000个（即1到1000）
完全立方数的个数：1003 =1000000，所以有100个（即1到100）
既是完全平方数又是完全立方数的重复部分：106 =1000000，所以有10个（即16到106） 所以既不是完全立方数，也不是完全平方数的整数有：1000000-(1000+100-10) = 998910
2四、证明题（每题8分，共24分）
1．若公司拒绝增加工资，则罢工不会停止，除非罢工超过三个月且公司经理辞职。公司拒绝增加工资，罢工又刚刚开始。罢工是否能停止？（给出相应推理的证明过程）
2．给出关系不满足对称性的条件并证明。
∃∈R∧∉R
⇔∃∈R∧∉R
⇔┐∀(∈R∧∈R)
3．如果关系R和S为X上的等价关系，证明：R∩S也是X上的等价关系。
(1)自反
设x∈X【推∈R∩S】
∵R和S为X上的等价关系
∴R和S均为X上的自反关系
∵x∈X
∴∈R, ∈S
∴∈R∩S
∴R∩S在X上是自反的
(2)对称
设∈R∩S【推∈R∩S】
∵∈R∩S
∴∈R,∈S
∵R和S为X上的等价关系
∴R和S均为X上的对称关系
∴∈R,∈S
∴∈R∩S
-第 5页
∵此时∈R∩S
∴R∩S在X上是对称的【∈R∩S时，必有∈R∩S】
(3)传递
设∈R∩S，∈R∩S【推∈R∩S】
∵∈R∩S
∴∈R,∈S
∵∈R∩S
∴∈R,∈S
∵R和S为X上的等价关系
∴R和S均为X上的传递关系
∴∈R,∈S
∴∈R∩S
∵此时∈R∩S，∈R∩S
∴R∩S在X上是传递的【∈R∩S，∈R∩S时，必有∈R∩S】
综上所述，R∩S在X上是自反、对称、传递的
∴R∩S为X上的等价关系
书P90
等价关系：自反、对称、传递
偏序关系：自反、反对称、传递
因此要证明某关系在非空集合上是等价关系或偏序关系，一般需分为三个性质分别证明，同时，题目条件中若给出等价关系或偏序关系，也可分为三部分选择使用。这类题条件较多（自己设的、题目推的），一定要思路清晰，否则容易写乱自己绕不出来„„
这道题三部分每个部分所设的条件都是该性质定义里的“若”，想要推出定义里的“则”，即用定义证明。这就是思路很重要的一部分。
-第 6页
