离散数学期末试卷

1、北京工业大学经管学院期末试卷离散数学（A）学号 姓名： 成绩一、单项选择题（每题2分，共18分）1令P：今天下雪了，Q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（D）APQBPQCPQDPQpq，蕴涵式，表示假设、条件、“如果，就”。“”与此题无关2. 关于命题变元P和Q的极大项M1表示( C )。 书P15-P20，此题换作p、q更容易理解A.PQB.PQ pq - 01- 1 - M1C.PQD.PQ3.设R（x）：x是实数；S（x,y）：x小于y。用谓词表达下述命题：不存在最小的实数。其中错误的表达式是：（D）4.在论域D=a,b中与公式（）A（x）等价的不含存在量词的公式是

2、（B）A. B. C. D. 5下列命题公式为重言式的是（C）AQ（PQ）BP（PQ）C（PQ）P D（PQ）Q牢记真假条件，作为选择题可直接代入0、1，使选项出现10，排除。熟练的可直接看出C不存在10的情况6. 设A=1，2，3，B=a,b，下列二元关系R为A到B的函数的是( A )A. R=,B. R=,C. R=,D. R=,7.偏序关系具有性质（D） 背A.自反、对称、传递B.自反、反对称C.反自反、对称、传递D.自反、反对称、传递8.设R为实数集合，映射则s 是( D ).(A) 单射而非满射(B) 满射而非单射 (C) 双射(D) 既不是单射也不是满射.书P96.设函数f：AB（

3、1）若ranf=B，则f是满射的【即值域为B的全集，在本题中为R，该二次函数有最高点，不满足】（2）若对于任何的x1,x2A , x1x2,都有f(x1)f(x2)，则称f是单射的【即x,y真正一一对应，甚至不存在一个y对应多个x。显然，本题为二次函数，不满足】（3）若f既是满射的，又是单射的，则称f是双射的【本题中两个都不满足，既不是单射也不是满射】二、填空题（每空2分，共22分）.设Q为有理数集，笛卡尔集S=QQ，*是S上的二元运算，,S, *=, 则*运算的幺元是_。S, 若a0，则的逆元是_。书P123定义.在个体域D中，公式的真值为假当且仅当_某个G(x)的真值为假_，公式的真值为假

4、，当且仅当_所有G(x)的真值都为假_。.给定个体域为整数域，若F（x）：表示x是偶数，G（x）：表示x是奇数；那么，是一个 永真式 ；而是一个 永假式 。.设, ；s(R)= , 。书P89、P85.自反闭包：r(R) = R U R0 =, U , =, 对称闭包：s(R) = R U R-1 = , U , = ,传递闭包：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即，若题中给出

5、集合A有m个元素，B有n个元素，可直接用nm 计算出A到B的函数个数。本题中为23 = 8.设a,bG，则（a-1）-1= a ，（ab）-1= b-1 * a-1 。书P139公式7. 设X=1，2，3，f：XX，g：XX，f=,g=,，则fg=_,_，gf=_,_。书P82-83合成：FG = |xGzzFy需要说明的是，这里的合成FG是左复合，即G先作用，然后将F复合到G上。之前的答案“有误”，因为采用了右复合。这两种合成定义所计算的合成结果是不相等的，但两个定义都是合理的，只要在体系内部采用同样的定义就可以了。总之，在咱们的离散里牢记左复合。三、计算题（每题9分，共36分）1. 设集合

6、A1, 2, 3,4,5，A上的关系R, (1) 画出R的关系图；(2) 问R具有关系的哪几种性质(自反、对称、传递、反对称).自反性、传递性书P87表格，根据关系图可直接判断性质(3) 给出R的传递闭包。R=, R2 = RR = , R3 = R2R = , 所以，t(R) = ,2. 集合S=a,b,c,d,e上的二元运算*的运算表如下，求出它的幺元，零元，及逆元。* a b c d ea b a c c cb a b c d ec c c c c cd e d c b ae d e c d b幺元：b零元：c逆元：a-1 =a,b-1 =b, d-1 =d,e-1 =e书P123定义3

7、求合式公式A=P(PQ)(QP)的主析取范式及成真赋值。A = P(PQ) (QP)= P(PQ) (QP) = P(P QP)(QQP) = P(QP) = P(QP) = (P(QQ)(QP) = (cPQ)(PQ)(PQ) = (PQ)(PQ)(PQ) = m0m1m3成真赋值为00，01，114求在1到1000000之间有多少个整数既不是完全立方数，也不是完全平方数？完全平方数的个数：10002 =1000000，所以有1000个（即1到1000）完全立方数的个数：1003 =1000000，所以有100个（即1到100）既是完全平方数又是完全立方数的重复部分：106 =1000000

8、，所以有10个（即16到106）所以既不是完全立方数，也不是完全平方数的整数有：1000000-(1000+100-10) = 998910四、证明题（每题8分，共24分）1若公司拒绝增加工资，则罢工不会停止，除非罢工超过三个月且公司经理辞职。公司拒绝增加工资，罢工又刚刚开始。罢工是否能停止？（给出相应推理的证明过程）2给出关系不满足对称性的条件并证明。RRRR(RR)3如果关系R和S为X上的等价关系，证明：RS也是X上的等价关系。 (1)自反设xX【推RS】R和S为X上的等价关系R和S均为X上的自反关系xXR, SRSRS在X上是自反的(2)对称设RS【推RS】RSR,SR和S为X上的等价关系R和S均为X上的对称关系R,SRS此时RSRS在X上是对称的【RS时，必有RS】(3)传递设RS，RS【推RS】RSR,SRSR,SR和S为X上的等价关系R和S均为X上的传递关系R,SRS此时RS，RSRS在X上是传递的【RS，RS时，必有RS】综上所述，RS在X上是自反、对称、传递的RS为X上的等价关系书P90等价关系：自反、对称、传递偏序关系：自反、反对称、传递因此要证明某关系在非空集合上是等价关系或偏序关系，一般需分为三个性质