清华大学本科生考试试题 姓名__________ 班号__________ 学号______________ 考试课程 《离散数学1》 2016年1月8日 （A 卷） （共2页——正反两面） 该页面的所有题目的解答直接写在这张试题纸上，该试题纸一并上交。背面的题目写在答题本上
一、选择题（共13分，每空1分）在下列各小题中选择其中的一种答案，标注在小标题后面的括号中
1. （ ）简而言之，命题逻辑的公理系统是
A. 用来建立公理的系统； B. 由公理产生推理规则的系统； C. 用来完善已有公理的系统；
D. 从精选的几条公理出发，根据规定的演绎规则，推导出一系列定理的形式符号系统。
2. （ ）孔子曰：“己所不欲，勿施于人。
A. 只有己所欲，才能施于人。 B. 除非己所欲，否则不施于人。
C. 若己所欲，则施于人。
3.
4. D. 凡施于人的都应该是己所欲的。 （ ）与连续统假设（CH ）的主要内容最接近的是：满足ℵ0
A. 对所有的x ∈D ，都有P (x ) =F 。 B. 至少存在一个x 0∈D ，使P (x 0) =F 。 C. 根据P(x)来定。
5. （ A. 1,6; B. 1,2,3,5; C. 1,2,3,5,6; D. 1,2,3,6. 其中
6. 1. {¬，⋁，⋀}; 2. {¬，⋀}; 3. {¬，⋁}; 4. {⋁，⋀}; 5. {¬，→}; 6. {↑}. 非空集合A 上的恒等关系IA 是（ ）；全关系EA 是（ ）；空关系∅是（ ）。
A. 偏序关系但不是等价关系 B. 等价关系但不是偏序关系
C. 既是等价关系又是偏序关系 D. 既不是等价关系也不是偏序关系
（ ）对任意集合A ，B 和C ，若A ∪B =A ∪C ，且A ∩B =A ∩C ，则B =C 。 （标出√或×） （ （标出√或×）
（ ）不存在这样的关系：它既不满足对称性，也不满足反对称性。 （标出√或×）
（ （标出√或×）
（ ）若希望所求关系R 的闭包同时具有自反性(r)、对称性(s)和传递性(t)这三种性质，则可先求r(R)，然后求出sr(R)，最后再求tsr(R)。 （标出√或×） 7. 8. 9. 10. 11.
二、填空题（共19分，每空1分）完成下列计算或填空。
1. （2分）设A={∅,b,{2}}，则A +=_____________ P(A) =___________________________
2. （6分）对n 个命题变元，可定义____________个n 元命题联接词。
设A ={1,2,3,4}，B ={a,b, c}，从A 到B 不同的二元关系共有__________个？|A ×B |=_______ 从A 到B 不同的函数共有___________个？在集合A 上，可定义________个不同的等价关系？ 在集合B 上，写出等价类数目最多的那个等价关系R _________________________________
3. （4分）对有限集合A 和B ，|A |=m ，|B |=n ，试给出下列情形m 和n 应满足的条件：、
(1)_______时存在从A 到B 的单射函数；(2)________时存在从A 到B 的满射函数；
(3) _______时存在从A 到B 的双射函数；且有__________个不同的双射函数。
4. （6分）按照无穷公理表示的自然数以及连续统假设，用最简洁的形式写出下列计算结果。 ⋃99=____________， ⋂100=___________， ⋂{96,97}=___________
|NN|=___________ |RR|=__________ |NP|=___________ 注：NP={n|n∈N∧n是素数}
5. （1分）在希尔伯特提出的23个数学问题中连续统假设位列第（ ），故又称希尔伯特第（ ）问题。
（注：本页的题目均须写在答题本上）
三、形式化下列语句，论域均为总论域（共10分，其中1-2小题每题2分，第3-4小题每题3分）
1. 没有最大的素数。
2. 天下乌鸦一般黑（要求写出两种形式，一种仅用全称量词，另一种仅用存在量词）。
3. 斐波那契数列中的每个数有且仅有一个后继。
4. 并非所有人都天赋好，而且天赋不好的人未必就不成功（仅需写出一种形式但全称和存在量词均需
出现）
四、写出计算与构造过程和结果（共15分，第1题2分，第2题5分，第3,4,5题每题4分）
1. 用空集∅构造一个集合序列S 0, S 1, ⋯, S i−1，满足|S i |=i ，且S i ⊆S i+1，试写出序列的前4个集合
S 0, S 1, S 2, S 3。
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. (∃x) (P(x) →Q(x) ) =(∀x) P(x) →(∃x) Q(x)是否正确，如正确试给出证明，如错误需举出反例。
2.
(∀x) (P(x) →Q(x) ) ∧(∀x)(R(x) →¬Q(x) ) ⇒(∀x)(R(x) →¬P(x) )
3. 若R 和S 是A 上的关系，且S ={|(∃c)(aRc ∧cRb ) }。若R 是等价关系，证明S 也是等价关系。
六、设A ={a,b, c, d, e, f, g, h}，R =I A ∪{,,,,,,,,}，
试完成以下4个步骤：
1) 说明R 是A 上的偏序关系；
2) 画出偏序集的哈斯图；
3) 写出
4) 对指出其极大元、极小元、最大元和最小元。
七、证明题第二部分（共12分）
1. 已知A ⊕B =A ⊕C ，证明B =C 。
2. 设A 、B 和C 是任意的集合，证明：(A −B ) −C =(A −C ) −(B−C)
3. 用等势定义证明(0, c ) ≈R ，其中R 为实数域(−∞,+∞)，c 为大于0的具体实数。
八、在会议室安装控制同一电灯L 的3个开关K 1、K 2、K 3，使得改变任一开关的状态，即可改变会议室电
灯的明暗。试分别完成以下3个步骤：
1. 用K 1、K 2、K 3列写出L 的真值表；
2. 写出L
3. 用所学的联结词将L
写出必要的过程或解释说明。
清华大学本科生考试试题 姓名__________ 班号__________ 学号______________ 考试课程 《离散数学1》 2016年1月8日 （A 卷） （共2页——正反两面） 该页面的所有题目的解答直接写在这张试题纸上，该试题纸一并上交。背面的题目写在答题本上
一、选择题（共13分，每空1分）在下列各小题中选择其中的一种答案，标注在小标题后面的括号中
1. （ ）简而言之，命题逻辑的公理系统是
A. 用来建立公理的系统； B. 由公理产生推理规则的系统； C. 用来完善已有公理的系统；
D. 从精选的几条公理出发，根据规定的演绎规则，推导出一系列定理的形式符号系统。
2. （ ）孔子曰：“己所不欲，勿施于人。
A. 只有己所欲，才能施于人。 B. 除非己所欲，否则不施于人。
C. 若己所欲，则施于人。
3.
4. D. 凡施于人的都应该是己所欲的。 （ ）与连续统假设（CH ）的主要内容最接近的是：满足ℵ0
A. 对所有的x ∈D ，都有P (x ) =F 。 B. 至少存在一个x 0∈D ，使P (x 0) =F 。 C. 根据P(x)来定。
5. （ A. 1,6; B. 1,2,3,5; C. 1,2,3,5,6; D. 1,2,3,6. 其中
6. 1. {¬，⋁，⋀}; 2. {¬，⋀}; 3. {¬，⋁}; 4. {⋁，⋀}; 5. {¬，→}; 6. {↑}. 非空集合A 上的恒等关系IA 是（ ）；全关系EA 是（ ）；空关系∅是（ ）。
A. 偏序关系但不是等价关系 B. 等价关系但不是偏序关系
C. 既是等价关系又是偏序关系 D. 既不是等价关系也不是偏序关系
（ ）对任意集合A ，B 和C ，若A ∪B =A ∪C ，且A ∩B =A ∩C ，则B =C 。 （标出√或×） （ （标出√或×）
（ ）不存在这样的关系：它既不满足对称性，也不满足反对称性。 （标出√或×）
（ （标出√或×）
（ ）若希望所求关系R 的闭包同时具有自反性(r)、对称性(s)和传递性(t)这三种性质，则可先求r(R)，然后求出sr(R)，最后再求tsr(R)。 （标出√或×） 7. 8. 9. 10. 11.
二、填空题（共19分，每空1分）完成下列计算或填空。
1. （2分）设A={∅,b,{2}}，则A +=_____________ P(A) =___________________________
2. （6分）对n 个命题变元，可定义____________个n 元命题联接词。
设A ={1,2,3,4}，B ={a,b, c}，从A 到B 不同的二元关系共有__________个？|A ×B |=_______ 从A 到B 不同的函数共有___________个？在集合A 上，可定义________个不同的等价关系？ 在集合B 上，写出等价类数目最多的那个等价关系R _________________________________
3. （4分）对有限集合A 和B ，|A |=m ，|B |=n ，试给出下列情形m 和n 应满足的条件：、
(1)_______时存在从A 到B 的单射函数；(2)________时存在从A 到B 的满射函数；
(3) _______时存在从A 到B 的双射函数；且有__________个不同的双射函数。
4. （6分）按照无穷公理表示的自然数以及连续统假设，用最简洁的形式写出下列计算结果。 ⋃99=____________， ⋂100=___________， ⋂{96,97}=___________
|NN|=___________ |RR|=__________ |NP|=___________ 注：NP={n|n∈N∧n是素数}
5. （1分）在希尔伯特提出的23个数学问题中连续统假设位列第（ ），故又称希尔伯特第（ ）问题。
（注：本页的题目均须写在答题本上）
三、形式化下列语句，论域均为总论域（共10分，其中1-2小题每题2分，第3-4小题每题3分）
1. 没有最大的素数。
2. 天下乌鸦一般黑（要求写出两种形式，一种仅用全称量词，另一种仅用存在量词）。
3. 斐波那契数列中的每个数有且仅有一个后继。
4. 并非所有人都天赋好，而且天赋不好的人未必就不成功（仅需写出一种形式但全称和存在量词均需
出现）
四、写出计算与构造过程和结果（共15分，第1题2分，第2题5分，第3,4,5题每题4分）
1. 用空集∅构造一个集合序列S 0, S 1, ⋯, S i−1，满足|S i |=i ，且S i ⊆S i+1，试写出序列的前4个集合
S 0, S 1, S 2, S 3。
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. (∃x) (P(x) →Q(x) ) =(∀x) P(x) →(∃x) Q(x)是否正确，如正确试给出证明，如错误需举出反例。
2.
(∀x) (P(x) →Q(x) ) ∧(∀x)(R(x) →¬Q(x) ) ⇒(∀x)(R(x) →¬P(x) )
3. 若R 和S 是A 上的关系，且S ={|(∃c)(aRc ∧cRb ) }。若R 是等价关系，证明S 也是等价关系。
六、设A ={a,b, c, d, e, f, g, h}，R =I A ∪{,,,,,,,,}，
试完成以下4个步骤：
1) 说明R 是A 上的偏序关系；
2) 画出偏序集的哈斯图；
3) 写出
4) 对指出其极大元、极小元、最大元和最小元。
七、证明题第二部分（共12分）
1. 已知A ⊕B =A ⊕C ，证明B =C 。
2. 设A 、B 和C 是任意的集合，证明：(A −B ) −C =(A −C ) −(B−C)
3. 用等势定义证明(0, c ) ≈R ，其中R 为实数域(−∞,+∞)，c 为大于0的具体实数。
八、在会议室安装控制同一电灯L 的3个开关K 1、K 2、K 3，使得改变任一开关的状态，即可改变会议室电
灯的明暗。试分别完成以下3个步骤：
1. 用K 1、K 2、K 3列写出L 的真值表；
2. 写出L
3. 用所学的联结词将L
写出必要的过程或解释说明。