考试时间：2009年7月16日
北京化工大学2008——2009学年第二学期
《 离散数学（I） 》期末考试试卷
课程代码 M A T 2 1 3 2 T 班级： 姓名： 学号： 分数：
题号 得分
一、填空题（共20分，每小题2分）
1. 设P，Q 的真值为0，R，S的真值为1，则
?(P?(Q?(R??P)))?(R??S)的真值= 。
?2.设 A?{x|(x?N)且(x?5)},B?{x|x?E且x?7}（N：自然数集，E+ 正偶
一 二 三 四 总分 数），则A∩B= 。
3. A={1, 2, 3, 4}，则A上有____个不同的双射函数。 4. 谓词公式?xP(x)??xQ(x)的前束范式为 。 5. 所有极小项的析取式为 。
6. 若集合S有n个元素，则其幂集P(S)有 个元素。
7. 设P：它占据空间，Q：它有质量，R：它不断运动，S：它叫做物质。命题 “占据空间的，有质量的而且不断运动的叫做物质”的符号化 为 。
8. 公式 P??(Q??S) 的对偶式为 。
?101???MR??110??111?X?{a,b,c}??，则 9. 设，X上的关系R的关系矩阵是
MR?R?
。
10. 设有关系R={<1,2>, <2,4>, <3,3>}，则D(R) = 。
二、判断题（共20分，每小题2分，正确的在题号前打?，错误的在题号前打×） 1.设R是集合S上的一个二元关系，若R是自反的，则R也是自反的。 2.空集是任何集合的真子集S。
3.设A,B,C是集合，若A?B、B?C、C?A，则A=B=C。 4.只有双射函数才有反函数。
5.同一个谓词公式，指定的论域不同，其真值也可能不同。 6.若R不是A上的对称关系，则R一定是A上的反对称关系 7.若A??，则{A}是A的一个划分。
8. 三个命题变元的极小项~P∧Q∧~R的编码是m=010。 9. 对任意集合A、B、C，若B∩A=C∩A，则B=C。 10.P是命题变元，P与P互为对偶式。
三、选择题（共20分，每小题2分） 1.下列各式中， 是错的。
A Φ?Φ B Φ?Φ C Φ?{Φ} D Φ?{Φ} 2. 设S={1,2,3}，S上关系R={<1,1>,<2,2>,<3,3>,<1,2>,<2,1>,<3,1>,<2,3>} 则R具有 性质。
A．自反、对称、传递； B．反自反、反对称； C．反自反、反对称、传递； D．自反 。
-1
3.下列命题公式为永真式的是 。
A：P→(P∨Q) B：(P∨﹁Q)→Q C：Q∧﹁Q D：P→﹁Q 4. 设S?{?,{1},{1,2}}，则有 ?S。
A、{{1,2}} ；B、{1,2 } ； C、{1} ； D、{2} 。
5. 下列等价关系正确的是 。
A、?x(P(x)?Q(x))??xP(x)??xQ(x)； B、?x(P(x)?Q(x))??xP(x)??xQ(x)； C、?x(P(x)?Q)??xP(x)?Q；
D、?x(P(x)?Q)??xP(x)?Q。
S与?S?6. 设C={{a},{b},{a,b}}，则分别为 。
S?CS?CA、C和{a,b}；B、{a,b}与?；C、{a,b}与{a,b}；D、C与C
7. N是自然数集，定义f:N?N, f(x)?(x) mod3（即x除以3的余数），
则f 。
A、是满射不是单射； B、是单射不是满射； C、是双射； D、不是单射也不是满射。
8.若论域为整数域，则下列公式中 是真的。
A ?x?y(x+y=0) B ?x?y(x+y=0) C ?x?y(x+y=0) D ?y?x(x+y=0)
9. 6.在谓词演算中，P(a)是?xP(x)的有效结论，其理论根据是 。 A US规则 B UG规则 C ES规则 D EG规则
10. 命题逻辑演绎的CP规则为 。
A、 在推演过程中可随便使用前提；
B、在推演过程中可随便使用前面演绎出的某些公式的逻辑结果；
C、如果要演绎出的公式为B?C形式，那么将B作为前提，设法演绎出C； D、设?(A)是含公式A的命题公式，B?A，则可用B替换?(A)中的A。
四、计算与证明题
1．(10分)通过构造主范式（主析取范式或主合取范式均可）的方法证明如下等价式：
(A→B)∧(A→C)? A→(B∧C)
2.（共10分） 前提: ?x (F(x)?(G(x)∧H(x))), ?x F(x),
证明结论: ?x (F(x)∧H(x))。
3. （共10分）设A={a,b,c,d}，A上的二元关系
R={
（2）求A中每一个元素的等价类； （3）求A对R的商集A/R； （4）求由R诱导的A的划分AR。
4、（本题共10分，每题5分）
(1).令Ai={1，2，3，···，i}，求A1∪A2∪A3∪···∪An 。
(2) 令f(x)=ax+b和g(x)=cx+d，其中a,b,c,d为常数，试问当a,b,c,d满足什么
条件时f ?g= g ? f 。
相关推荐：
loading