北 京 交 通 大 学
2005-2006学年第一学期《离散数学》期末考试试卷（B）
学院_____________ 专业___________________ 班级____________ 学号_______________ 姓名_____________
题号 得分 阅卷人
姓名：
一 16
二 16 三 40 四 28
总分 学号： 班级： □选修 □必修
一、填空题（共16分，每空2分）
1. 命题公式G=（P?Q）?R，则G共有 个不同的解释；把G在其所有解释下所取
真值列成一个表，称为G的 。
2. 设A={a，{b}}，则A的幂集是?(A)? ； 3. 设R 是集合A上的二元关系，如果关系R同时具有 性、对称性和 性，则称R是等价关系。
4. 设R 是集合A上的二元关系，如果R是反自反的，则它的关系矩阵的主对角线元
素 。 5. 在推理理论中，推导过程中如果一个或多个公式重言蕴涵某个公式，则这个公式就可以
引入推导过程中，这一推理规则叫做 。 6. 设R 是集合A上的二元关系，如果关系R同时具有自反性、 和传递性，
则称R是A上的一个偏序关系。 二、选择一个正确答案的代号，填入括号中。（共16分，每小题2分）
1. 命题公式(P?Q) ? (P?R)的主析取范式中包含极小项（ ）
A．P?Q?R； B．P?Q??R； C．P??Q?R； D．P??Q??R 2. 下列谓词公式中（ ）不是命题。
A．(?x)P(x)； B．(?x)P(x)； C．(?x)(P(x)?P(y))； D．(?x)(?y)(P(x) ?R(y)) 3. 下列谓词公式中（ ）不正确。
A．(?x)(A(x) ?B) ? (?x) A(x) ?B； B．(?x)(B ?A(x)) ? B ?(?x) A(x)； C．(?x)(B ?A(x)) ? B ?(?x) A(x)； D．(?x)(A(x)?B) ?(?x)A(x)?B； 4. 下列命题中正确的是（ ）。
A．a?{{a}}； B．{a}?{{a}}； C．{a}?{{a}}； D．??{{a}}。
5. 由集合运算定义，下列各式正确的有（ ）。
北京交通大学2003-2004学年第2学期 离散数学期末考试题&参考答案 第 1 页 共 4 页
A． X?X?Y B.X?X?Y C.X?X?Y D.Y?X?Y 6. 设A,B,C为任意三个集合，下列各命题中正确的是（ ）。
A．若A?B且B?C，则A?C； B．若A?B且B?C，则A?C； C．若A?B且B?C，则A?C； D．若A?B且B?C，则A?C。 7. 设R1，R2是集合A={a，b，c，d}上的两个关系，其中R1={（a，a），（b，b），（b，c），
（d，d）}，R2={（a，a），（b，b），（b，c），（c，b），（d，d）}，则R2是R1的（ ）闭包。
A．自反 B．对称 C．传递 D．以上都不是
8. 设偏序关系R是集合A={1，2，3，4，5，6}中数的“整除”关系，则A的极大元、极
小元的个数分别是（ ）。
A．2，1 B．2，2 C．3，1 D．3，2 三、计算题（共40分，每小题10分）
1. 求命题公式（P?Q）?（?P?R）的主合取范式。
2. 在一个班级的50个学生中，有26人在第一次考试中得到A，21人在第二次考试中得
到A。假如有17人两次考试都没有得到A，问有多少学生两次考试中都得到了A？
3. 设为一个偏序集，其中，A={1，2，3，4，6，9，24，54}是A上的整除关系。
（1）画出的哈斯图；
北京交通大学2003-2004学年第2学期 离散数学期末考试题&参考答案 第 2 页 共 4 页
（2）求R关于A的极大元；
（3）求B={4,6,9}的最小上界和最大下界。
4. 设已知集合A={1,2,3,4,5,6}上的等价关系
R={(1,1),(1,5),(2,2),(2,3),(2,6),(3,2),(3,3),(3,6),(4,4),(5,1),(5,5),(6,2),(6,3)(6,6)} 求A的由R诱导出的划分和A关于R的商集。
四、证明题（共28分）
1. 证明集合等式（A-B）∪（B-A）=（A∪B）-（A∩B）.
北京交通大学2003-2004学年第2学期 离散数学期末考试题&参考答案 第 3 页 共 4 页
2. 用逻辑推理方法证明：{P?Q， R?S，P?R }蕴涵Q?S。
3. 考虑整数集合Z，对于某个正整数r，定义Z上的一个关系R：aRb当且仅当b=ar。证
明R是Z上的一个偏序。
北京交通大学2003-2004学年第2学期 离散数学期末考试题&参考答案 第 4 页 共 4 页