离散数学期末试卷

北京工业大学经管学院期末试卷

《离散数学》（A）

学号姓名：成绩

一、单项选择题（每题2分，共18分）

1.令P:今天下雪了，Q:路滑，则命题“虽然今天下雪了，但是路不滑”

可符号化为（D）

A.P-QB.PVQ

C.PAQD.PAQ

p-q,蕴涵式，表示假设、条件、“如果，就二

“一”与此题无关

2.关于命题变元P和Q的极大项Ml表示..）.书P1520,此题换作p、q

更容易理解

A.-iPAQB.-|PVQpV-iq011M,

V-iQA-iQ

3.设R（x）:x是实数；S（）:x小于y。用谓词表达下述命题：不存在

最小的实数。其中错误的表达式是：（D）

4.在论域｛｝中与公式（入）A（x）等价的不含存在量词的公式是（B）

A..B.

C.D.

5.下列命题公式为重言式的是（C）

A.Q-（PAQ）B.P->（PAQ）

C.(PAQ)-PD.(PVQ)-Q

牢记一真假条件，作为选择题可直接代入0、1,使选项出现1-0,排除。

熟练的可直接看出C不存在if0的情况

6.设{1,2,3},{),下列二元关系R为A到B的函数的是....)

A.{<1>,<2>,<3>}

B.{<1>,<2>}

C.{<1>,<1>,<2>,<3>}

D.{<1>,<2>,<3>,<1>}

7.偏序关系具有性质(D)背

A.自反、对称、传递

B.自反、反对称

C.反自反、对称、传递

D.自反、反对称、传递

8.设R为实数集合，映射则(是(D).

(A)单射而非满射(B)满射而非单射

(0双射(D)既不是单射也不是满射.

书P96.设函数f:A->B

(1)若，则f是满射的【即值域为B的全集，在本题中为R,该二次函数

有最高点，不满足】

(2)若对于任何的X12WA,xlWx2,都有f(xl)Wf(x2),则称f是单射

的【即真正一一对应，甚至不存在一个y对应多个X。显然，本题为二次函

数，不满足】

(3)若f既是满射的，又是单射的，则称f是双射的【本题中两个都不满

足，既不是单射也不是满射】

二、填空题(每空2分，共22分)

1.设Q为有理数集，笛卡尔集XQ,*是$上的二元运算，<a,b>,<x,y>

£S,

<a,b>*<x,y>=<,>,则*运算的幺元是<a,b>eS,若aWO,

则b〉的逆元是书P123定义

2.在个体域D中，公式的真值为假当且仅当某个G(x)的真值为假，公

式的真值为假，当且仅当所有G(x)的真值都为假。

3.给定个体域为整数域，若F(x)：表示x是偶数，G(x)：表示x是奇数;

那么，是一个永真式；而是一个

永假式__________O

4.设A={a,b,c},A上的二元关系R=«a,b),〈b,c)},则r(R)=

S(R)=_{<>,<>,<>,<>}_o

书P89、P85.

自反闭包：r(R)=RUR0

={<>,<>}U{<>,<>,<>,<>}={<>,<>,<>,<>,<>,<>}

对称闭包:s(R)=RUR-l={<>,<>}U«>,<>}={<>,<>,<>,<>}

传递闭包：t(R)=23U……

5.设{1,2,3}{}，则从X到Y的不同的函数共有8个.

书P96,B上A的概念:

设A、B为集合，所有从A到B的函数构成集合BA,读作“B上A”

如果=m,=n,m、n不全是0,则=

即，若题中给出集合A有1n个元素，B有n个元素，可直接用计算出A到

B的函数个数。本题中为23=8

6.设，则（1）-1=a,（）-1=1*1o

书P139公式

7.设{1,2,3）,f:X-X,g:XT,{<1.2>,<2,3>,<3,1>},

{<1,2>,<2,3>,<3,3»,则{<1,3>,<2,1>,<3,1>},

{<1,3>,<2,3>,<3,2>}。

书P82-83

合成：={OA}

需要说明的是，这里的合成是左复合，即G先作用，然后将F复合到G

±o之前的答案“有误”，因为采用了右复合。这两种合成定义所计算的

合成结果是不相等的，但两个定义都是合理的，只要在体系内部采用同样

的定义就可以了。总之，在咱们的离散里牢记左复合。

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

⑴设集合A={L2,3,4,5},A上的关系1^={<1,2>,<2,2>,<3,

2>,<3,3>,<3,5>,<4,4>,<5,5>}

⑵画出R的关系图；

（3）问R具有关系的哪几种性质（自反、对称、传递、反对称）.

自反性、传递性

⑷书P87表格，根据关系图可直接判断性质……

(5)给出R的传递闭包。

{<1,1>,<1,2>,<2,2>,<3,2>,<3,3>,<3,5>,<4,4>,<5,5>}

R2=o={<1,1>,<1,2>,<2,2>,<3,2>,<3,3>,<3,5>,<4,4>,<5,5>}

R3=R2OR=«1,1>,<1,2>,<2,2>,<3,2>,<3,3>,<3,5>,<4,4>,<5,5>}

所以，t(R)={<1,

1>,<1,2>,<2,2>,<3,2>,<3,3>,<3,5>,<4,4>,<5,5>}

2.集合{}上的二元运算*的运算表如下，求出它的幺元，零元，与逆

71so

*abcde

abaccc

babode

cccccc

dedcba

edecdb

幺元：b

零元：c

逆元：11,11

书P123定义

3.求合式公式一(1P-Q)八］(1QViP))的主析取范式与成真赋值。

A=P-((-1PVQ)A(QAP))

=P-((iPVQ)A(QAP))

=Pf((-1PAQAP)V(QAQAP))

=P->(QAP)

=nPV(QAP)

=(nPA(QV-iQ))V(QAP)

=(AQ)V(nPAnQ)V(PAQ)

=(iPAnQ)VhPAQ)V(PAQ)

=moVmiVmj

成真赋值为00,01,11

4.求在1至IJ1000000之间有多少个整数既不是完全立方数，也不是完全平

方数？

完全平方数的个数：10002=1000000,所以有1000个(即1到1000)

完全立方数的个数：1003=1000000,所以有100个(即1到100)

既是完全平方数又是完全立方数的重复部分：106=1000000,所以有10个

(即16到106)

所以既不是完全立方数，也不是完全平方数的整数有：

1000000-(1000+100-10)=998910

四、证明题(每题8分，共24分)

1.若公司拒绝增加工资，则罢工不会停止，除非罢工超过三个月且公司经

理辞职。公司拒绝增加工资，罢工又刚刚开始。罢工是否能停止？(给出

相应推理的证明过程)

2.给出关系不满足对称性的条件并证明。

3<>eRA<XR

ua<>eRA<XR

Q-Iv(OGRAOER)

3.如果关系R和S为X上的等价关系，证明：RGS也是X上的等价关系。

⑴自反

设Wx£X【推OCRAS】

・・・R和S为X上的等价关系

JR和S均为X上的自反关系

VxeX

AOeR,<>es

AOGRAS

・・・Rns在X上是自反的

⑵对称

设VOERAS【推◊WRCS】

VOeRAS

AOeR,<>es

・・・R和S为X上的等价关系

・・・R和S均为X上的对称关系

・・・<〉£&<>es

AOeRAS

•・•止匕时<>£RAS

•••RAS在X上是对称的【OWRAS时，必有OWRGS】

⑶传递

设OERAS,OERAS【推OWRCS】

VOeRAS

AOeR,oes

VOeRAS

AOeR,oes

YR和S为X上的等价关系

・・・R和S均为X上的传递关系

AOeR,<>es

AOGRAS

:此时<>£Rns,OeRAS

•••RAS在X上是传递的【◊&RGS,<>£RAS时，必有<>£RGS]

综上所述，RGS在X上是自反、对称、传递的

•••RAS为X上的等价