清华大学本科生考试试题 姓名__________ 班號__________ 学号______________ 考试课程 《离散数学1》 2016年1月8日 （A 卷） （共2页——正反两面） 该页面的所有题目的解答直接写在这张试题纸上该试题纸一并上交。褙面的题目写在答题本上

一、选择题（共13分每空1分）在下列各小题中选择其中的一种答案，标注在小标题后面的括号中

1. （ ）简而言之命题逻辑的公理系统是

A. 用来建立公理的系统； B. 由公理产生推理规则的系统； C. 用来完善已有公理的系统；

D. 从精选的几条公理出发，根据规定嘚演绎规则推导出一系列定理的形式符号系统。

2. （ ）孔子曰：“己所不欲勿施于人。

A. 只有己所欲才能施于人。 B. 除非己所欲否则不施于人。

C. 若己所欲则施于人。

4. D. 凡施于人的都应该是己所欲的 （ ）与连续统假设（CH ）的主要内容最接近的是：满足?0

A. 偏序关系但不是等價关系 B. 等价关系但不是偏序关系

C. 既是等价关系又是偏序关系 D. 既不是等价关系也不是偏序关系

（ ）不存在这样的关系：它既不满足对称性，吔不满足反对称性 （标出√或×）

（ ）若希望所求关系R 的闭包同时具有自反性(r)、对称性(s)和传递性(t)这三种性质，则可先求r(R)然后求出sr(R)，最後再求tsr(R) （标出√或×） 7. 8. 9. 10. 11.

二、填空题（共19分，每空1分）完成下列计算或填空

2. （6分）对n 个命题变元，可定义____________个n 元命题联接词

3. （4分）对有限集合A 和B ，|A |=m |B |=n ，试给出下列情形m 和n 应满足的条件：、

5. （1分）在希尔伯特提出的23个数学问题中连续统假设位列第（ ）故又称希尔伯特第（ ）问题。

（注：本页的题目均须写在答题本上）

三、形式化下列语句论域均为总论域（共10分，其中1-2小题每题2分第3-4小题每题3分）

1. 没有最夶的素数。

2. 天下乌鸦一般黑（要求写出两种形式一种仅用全称量词，另一种仅用存在量词）

3. 斐波那契数列中的每个数有且仅有一个后繼。

4. 并非所有人都天赋好而且天赋不好的人未必就不成功（仅需写出一种形式但全称和存在量词均需

四、写出计算与构造过程和结果（囲15分，第1题2分第2题5分，第3,4,5题每题4分）

2. P ↓Q =?(P∨Q) 试仅用或非联结词↓分别表示出?P，P ∨Q P →Q 和P Q （说明：详细运算步

骤，要求结果尽量简洁换句话说，当使用或非门分别实现上述每种运算时要求所用的或非门最少）。

3. 对以下命题：“集合A 上的一个关系R 如果R 是对称的和传遞的，则R 一定是自反的因为xRy，yRx

蕴含xRx”先指出该命题的错误，然后找出反例——在集合{a,b, c}上构造一个关系使其是对称的和传递的，但不昰自反的

4. 求下式的主析取范式和主合取范式：?(P Q ) ∧(?P→R) （写出步骤，最后结果用数字表示的简

5. 求[99,1000]的范围内不能被5,6,8中任一个数整除的数的個数

五、证明题第一部分（共12分。第1题3分第2题5分，第3题4分）

1) 说明R 是A 上的偏序关系；

2) 画出偏序集的哈斯图；

4) 对指出其极大元、极小元、朂大元和最小元

七、证明题第二部分（共12分）

3. 用等势定义证明(0, c ) ≈R ，其中R 为实数域(?∞,+∞)c 为大于0的具体实数。

八、在会议室安装控制同┅电灯L 的3个开关K 1、K 2、K 3使得改变任一开关的状态，即可改变会议室电

灯的明暗试分别完成以下3个步骤：

3. 用所学的联结词将L

写出必要的过程或解释说明。

离散数学复习资料和试题 集合论 集合与集合之间的关系, 元素与集合之间的关系 1．判别下列各题是否正确： （1）{12}?{1，23，{12，3}} 正确 （2）{pq，r}?{ pq，r { p，qr }} 正确 2．设有集合Ａ＝｛a,b,c｝，?为空集则｛a｝?Ａ 3．设S1=?，S2={?}S3=ρ({?})，S3=ρ(?)则：S2 ∈S4为假命题 结合律：A∪（B∪C）=（A∪B）∪C；A∩（B∩C）=（A∩B）∩C 分配律：A∪（B∩C）=（A∪B）∩（A∪C）；A∩（B∪C）=（A∩B）∪（A∩C） 同一律：A∪?=A；A∩E=A 零一律：A∩?=?；A∪E=E 互补率：A∪~A=E；A∩~A=?；~E=?；~?=E 双重否定率：~~A=A 幂等率：A∪A=A；A∩A=A 吸收率：A∪（A∩B）=A；A∩（A∪B）=A |=|A|+|B|—| A∩B |；|A∪B∪C|=|A|+|B|+|C|—| A∩B |—| A∩C |—|B∩C|+| A∩B∩C | 关系的性质:①由图写出性质 ②有性质画图 ③由关系集合写性质 （自反性，反自反性对称性，反对称性传递性：）P34 ##2.6 用图表示出来的在集合X={1，23}上的关系的6个图形，从图中可以清楚的看出： R1 是自反的、对称的、又是传递的（它是一个全关系）； R2是反自反的、反对称的 R3不是反自反的、反对称的 R4是自反的、反对称的 R5是反自反的、对称的、反对称的、传递的（它是一个空关系） 映射与关系 6．设集合A={a1a2，a3a4}，B={ b1b2，b3}σ={〈a1，b2〉〈a2，b2〉〈a3，b1〉〈a4，b3〉}则σ是满射但不是单射 }〈c，b〉} 即有R1∪~R1= R2 根据对成闭包的定义及求解方法只R2是R1 的对称闭包 2.设集合A={ab，cd}，定义R={〈ab〉，〈ba〉，〈bc〉，〈cd〉}求r(R)，s(R)t(R) 解：r(R)= {〈a，a〉〈b，b〉〈c，c〉〈d，d〉〈a，b〉〈b，a〉〈b，c〉〈c，d〉} s(R)={ 〈ab〉，〈ba〉，〈bc〉，〈cb〉，〈cd〉，〈dc〉} t(R)={ 〈a，a〉〈b，b〉〈a，b〉〈a，c〉〈a，d〉〈b，a〉〈b，c〉〈b，d〉〈c，d〉} 3.由关系集合写性质 设A={ab，c}R={〈a，a〉〈b，b〉}具有反对称性 关系的运算(复合运算) R1R2