安徽大学计算机学院离散数学期末考试试卷.doc

院/系 年级 专业 姓名 学号
答 题 勿 超 装 订 线
------------------------------装---------------------------------------------订----------------------------------------线----------------------------------------

安徽大学20 09 —20 10 学年第 1 学期
《 离散数学（上） 》考试试卷（A卷）
（闭卷 时间120分钟）

题 号
一
二
三
四
五
六
七
总分
得 分

阅卷人

得分

一、单项选择题（每小题2分，共20分）
1.设明天下雪，我去镇上，则命题"只有明天不下雪，我才去镇上”可符号化为（ ）
A.； B.； C.； D.。
2.下列命题是重言式的是（ ）
A.； B.；
C.； D.。
3.设解释如下：论述域为整数集，，，，则下列公式在下为真的是（ ）
A. ；B. ；
C. ； D. 。
4.对任意集合，下列结论不正确的是（ ）
A. ； B. ；
C. ； D. 。
5.关于到的函数，下列结论错误的是（ ）
A. ； B. ； C. ； D. 。
6.整数集合上的二元关系具有（ ）
A.自反性和对称性； B.反自反性和对称性； C.自反性和传递性； D.反对称性和传递性。
7.设，为非空集合上的二元关系，则下列结论不成立的是（ ）
A. ； B. ；

C. ； D. 。
8.设和是非空集合的划分，则下列集合一定是的划分的是（ ）
A. ； B. ； C.； D. 。
9.设是集合上的恒等关系，要使为上的等价关系，可取（ ）
A.； B.；
C.； D.。
10.设和分别为自然数和实数集合，则下列集合中与其他集合的基数不同的集合是（ ）
A.； B.； C.； D. 。
得分

二、判断题（每小题2分，共10分）
1.联结词集合为全功能的。（ ）
2.对任意集合，若及，则。（ ）
3.一定是良序集合。（ ）
4.如果合成函数是双射的，则函数必是单射的而是满射的。（ ）
5.有理系数的所有多项式集合是可数的。（ ）

得分

三、填空题（每小空2分，共20分）
1.设：是偶数，：是质数，：是整数，：是负数，则在全总个体域下
“有某个质数其平方是偶数”符号化为： ；
“对任何两个整数和，或是非负的”符号化 。
2.设，，则= ；= 。
3.设为整数集合，则集合上的二元关系
的关系矩阵为= ；传递闭包的关系矩阵为 。
4.设，，，则特征函数 ， 。
5.设为自然数集，为整数集，为实数集，则 ， （填=，>，<）。

得分

四、解答题（每小题10分，共20分）
1. 设集合，定义上的偏序关系为整除关系，
（1）给出偏序集合的哈斯图；
（2）求出的最大元、最小元、极大元和极小元，并填入下表；
（3）求出的上界、下界、上确界和下确界，并填入下表。
集合
最大元
最小元
极大元
极小元

集合
上界
下界
上确界
下确界

2. 求的主析取范式和主合取范式。

答 题 勿 超 装 订 线
------------------------------装---------------------------------------------订----------------------------------------线----------------------------------------

得分

五、证明题（每小题10分，共30分）
1.用推理规则证明：

2. 设R是A上一个二元关系，

试证明若R是A上一个等价关系，则S也是A上的一个等价关系。

3. 设为整数集合，函数定义为：，
证明：不是单射也不是满射。

安徽大学20 10 —20 11 学年第 1 学期
《离散数学（上）》A卷）考试试题参考答案及评分标准
一、单项选择题（每小题2分，共20分）
1、B，2、 C，3、D，4、 D，5、D，6、 C，7、C，8、D，9、D，10、D
二、判断题（每空2分，共10分）
1、×，2、√，3、×，4、×，5、√
三、填空题（每小空2分，共20分）
1、，；
2、，；
3、，；
4、，；
5、=，>；
四、解答题（每小题10分，共20分）
1、（1）哈斯图如右图（2分）
（2）-（3），下表每空2分
集合
最大元
最小元
极大元
极小元

不存在
不存在
3，10
2，3
集合
上界
下界
上确界
下确界

30
1
30
1

2、
（2分）

（4分）
，
于是，主合取范式为：， （7分）
主析取范式为：

（10分）
五、证明题（每小题10分，共30分）
1、 ① P
② P（附加前提）， （2分）
③ ，①，② （4分）
④ ，③ （6分）
⑤ ，④ （8分）
⑥ ，⑤

⑦ CP （10分）

2、要证明S为A上的等价关系，只需要证明S具有自反性、对称性和传递性。
① 自反性
只需证明对，有。
由于R为等价关系，故对，有。
于是，对，都，使，
由S的定义，可得。自反性得证。 （3分）
② 对称性
只需证明对，必有 。
由S的定义，必存在，使且，
因为R为等价关系，故具有对称性，从而有且，
由S的定义，必有。 对称性得证。 （3分）
③ 传递性
只需证明对，，必有。
对于，由S的定义，必存在，使且，由R为等价关系，从而R具有传递性，于是；
对于，由S的定义，必存在，使且，由R为等价关系，从而R具有传递性，于是。
从而，存在，使且，由S的定义，必有。传递性得证。 （4分）

3、① 证明不是单射的，
，有，
，有，
，有，从而不是单射。 （5分）
② 证明不是满射的，
对，不存在，使。
反之，有下列式子成立：，对，此方程无解。
从而不是满射的。 （5分）

第 6 页 共 6 页