离散数学试题

第一大题:单项选择题（共10小题，每小题2分,共20分）

1．下列不成立的式子是（ ）。 A．

B．

C．

D．

2．设A与B为含n个命题变项的公式,哪一个是真命题?（ )。 A．若A为重言式，则A的主合取范式为0 B．AB当且仅当A与B有相同的主合取范式 C． 若A为矛盾式，则A的主析取范式为1 D．任何公式都能等值地化成{, ｝中的公式 3．下面命题中不是真命题的是（ ）. A．海水是咸的当且仅当雪是白的。

B．如果南昌是直辖市,那么北京是中国首都。

C．若太阳从西边落下,则2是奇数. D．南昌的夏天冷当且仅当南昌的冬天热。 4．个体变项的取值范围（ )。 A．定义域

B．辖域

C．值域

D． 个体域

5．1到999中,与1000互素的数的个数为( ）. A．240

B．360

C．400

D．480

6．下列集合中与幂集P（N)等势的是（ )。 A． R

B． N

C．Q

D．Z

7．设f是A到B上的函数,下列式子中错误的是（ ）. A．IAff B． fIAf C． fIBf D．IAffIB

8．是任意集合上的空关系，则不满足A上的( ）。 A．对称

B．反对称

C．自反

D．传递

9．若A-B=A，则（ ）。

A．BA

B． AB=

C． AB=

D．AB

10．下列公式中错误的是（ )。

A．x(A（x）B)xA（x)B

B．x（A(x)B）xA(x)B C．x（A(x）B）xA(x)B

D．x(BA(x))BxA(x)

第二大题：判断题（共8小题,每小题1分,共8分)

1．“我在说谎话。”是命题.（ ） 2．x的等价类［x］一定是非空的。( )

3．F（x，y)→(G(x,y）→F(x,y))是永假式。（ ） 4．在自然数的集合定义下32={2｝。( ）

5. 设f:A→B, g:B→C ,如果fg:A→C是单射的， 则 f：A→B, g：B→C也是单射的。 ( ) 6. 存在满足既是等价关系又是偏序关系的二元关系。（ ）

7. A=P（X)，|X｜2,x,yA,xRyxyyx，则R是等价关系.( ） 8. 若R是传递的,则s(R)也是传递的。（ ）

第三大题：计算题和证明题（共6小题，每小题12分，共72分）

1. 求公式(pq）(qr)的主析取范式和主合取范式。

2. 写出公式(pq）r的真值表,并求它们的成真和成假赋值.

3．在自然推理系统中，构造下面推理的证明:

每个喜欢步行的人都不喜欢骑自行车。每个人或者喜欢骑自行车或者喜欢乘汽车.有的人不喜欢乘汽车。所以，有的人不喜欢步行。（个体域为人类集合）

4。 设A=｛1,2，3,4｝，R为AA上的二元关系，a,b,c,dAA，

a,bRc,dabcd，

（1）证明R是等价关系； （2)求商集A×A/R。

5。 画出集合{1，2，3，4,5,6,7,8，9，10，11,12｝与整除关系的哈斯图，设B={2,4,6｝，求B的极大元，极小元，最大元，最小元，上界，下界，上确界和下确界。

6. A，B,C，D 4个人中要派两个人出差，按下述3个条件有几种派法，如何派? （1）若A去则C和D中要去一人; （2）B和C不能都去；

（3）C去则D留下.(要求：必须有逻辑演算的计算过程）