离散数学试题.docx

第一大题：单项选择题（共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．Z7．设f是A到B上的函数，下列式子中错误的是（）。
A． B． C． D．
8．是任意集合上的空关系，则不满足A上的（）。
A．对称 B．反对称 C．自反 D．传递
9．若A-B=A，则（）。
A．BA B． AB= C． AB= D．AB
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(BA(x))BxA(x)
第二大题：判断题(共8小题，每小题1分，共8分)1．“我在说谎话。”是命题。（）
2．x的等价类[x]一定是非空的。（）
3．F(x,y)→(G(x,y)→F(x,y))是永假式。（）
4．在自然数的集合定义下={2}。（）
5.设f:A→B,g:B→C，如果fog:A→C是单射的,则f:A→B,g:B→C也是单射的。（）
6.存在满足既是等价关系又是偏序关系的二元关系。（）
7.A=P(X)，|X|，，则R是等价关系。（）
8.若R是传递的，则s(R)也是传递的。（）
第三大题：计算题和证明题（共6小题，每小题12分，共72分）
求公式(pq)(qr)的主析取范式和主合取范式。

写出公式(pq)r的真值表，并求它们的成真和成假赋值。

在自然推理系统中，构造下面推理的证明：
每个喜欢步行的人都不喜欢骑自行车。每个人或者喜欢骑自行车或者喜欢乘汽车。有的人不喜欢乘汽车。所以，有的人不喜欢步行。（个体域为人类集合）

4.设A={1，2，3，4}，R为QUOTE上的二元关系，，
，
（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，D4个人中要派两个人出差，按下述3个条件有几种派法，如何派？
若A去则C和D中要去一人；
B和C不能都去；
C去则D留下。（要求：必须有逻辑演算的计算过程）