华东理工大学2004离散数学模拟试卷试卷
姓名 学号 班级 成绩 .
一．填空题（共20分） 1． （2分）给出下列语句：
（1）32不能被4整除. （2）19是素数当且仅当太阳从西边升起. （3）x?5?y?z. （4）哈佛大学在上海市. 其中 是命题； 是复合命题. 2． （2分）给出以下命题：
（1）2?3?5?3?7?10. （2）2?3?5?3?7?10. （3）2?3?5?3?7?10 （4）2?3?5?3?7?10.
其中真值是F的命题是 . 3．（2分）给出下列命题： （1）(p?q)?(?q??p) （2）(p?(p?q))?q
（3）?(q?p)?p （4）((p?q)?(q?r))?(p?r) 其中 是重言式， 是矛盾式. 4．（2分）在以下4个推理或结论中 是正确的推理或结论. （1） A?(B?C)?(A?B)?(A?C). （2） (?x)F(x),(?x)G(x)?(?y)(F(y)?G(y)). （3） (?x)(?y)A(x,y)?(?y)(?x)A(x,y). （4） ?(?x)(A(x)??B(x))?(?x)(A(x)?B(x)).
5．（2分）判断下列命题的真假（其中A,B,C,S,T均为集合, ?为空集）：
（ ）（1）??? （ ）（2）??? （ ）（3）(S?T??)?S?T （ ）（4）(A?B)?(B?C)?A?C
6．(2分)(?x)(?((?y)P(x,y))?((?z)Q(z)?R(t)))的前束范式是
.
?,???,??????，则?(A)?A中有 个元素. 7．(1分)设A??8．(2分)设集合A??a,b,c?，则A上的二元关系共有 个；其中同时满足反自反 性以及对称性的关系有 个.
1 / 4
9．(3分)给定集合A??1,2,3?上的3个关系如下：
R1???2,2?,?2,3?,?2,1?,?1,1??，R2???2,2?,?2,3?,?3,2?,?3,3?,?1,1??，
R3???2,3?,?3,3?,?3,1??，
则其中满足对称性的关系是 ；满足传递性的关系是 ； 满足反自反性的关系是 ；满足反对称性的关系是 ； 为等价关系的是 ；Ran(R1?R2)?{ } . 10．(1分)设R1,R2是集合A上的等价关系，做出下列几个关系：
（1）(A?A)?R1 （2）R2?R1 （3）R1?R1 （4）R1?R2， 其中关系 一般不再是A上的等价关
系. 11．(1分)集合A??1,2,3,4?上包含序偶?1,4?和?3,2?的全序关系是
R?{ }. 二．选择题（每小题2分，共10分） 1．下列命题中正确的结论是（ ）：
(A)集合A上的关系R如果不是对称的，就一定是反对称的； (B)若关系R,S都是反自反的，那么R?S必也为反自反的； (C)若关系R,S都是传递的，那么R?S必也为传递的； (D)每一个良序集必为全序集.
2．下列结论中不正确的结论是（ ）：
(A)三个命题变元的布尔小项?P?Q??R的编码是m010； (B) 三个命题变元的布尔大项?P?Q??R的编码是M101； (C)任意两个不同的布尔小项的合取式必为永假式； (D)任意两个不同的布尔大项的合取式必为永假式. 3．以下命题中不正确的结论是（ ）： (A)集合的交运算满足结合律与交换律； (B)集合的并运算满足结合律与交换律；
(C)对任意三个集合A,B和C有A?(B?C)?(A?B)?(A?C)成立； (D) 对任意三个集合A,B和C，由A?B?A?C必可推出有B?C. 4．以下命题中不正确的结论是（ ）： (A)素数阶群必为循环群； (B)循环群必为Abel群；
2 / 4
(C)当n?2时，n阶对称群Sn必为Abel群； (D)4阶群必为Abel群.
5．以下命题中正确的结论是（ ）：
(A)n个结点的完全图Kn的着色数?(Kn)?4；
(B)如果一个连通图的奇结点的个数大于2，那么它必不是一个Euler图； (C)一棵树必是连通图，但其中可能有回路； (D)图的邻接矩阵必为对称阵. 三．解答题(共70分) 1．（8分）证明下列蕴含式： ((A?B)?C)?(?D)?(?C?D)??A??B. 2．（8分）证明：对任意集合A,B,C有
A?(B?C)?(A?B)?(A?C). 3．（10分）将下述命题化为主析取范式和主合取范式： (p?(q?r))?(?p?(?q??r).
4．（10分）给出集合A=?a,b,c,d,e?上的一个关系
R???a,b?,?b,c?,?c,d?,?d,c?,?b,e?,?e,e??.
（1）（2分）写出它的关系矩阵A ； （2）（2分）求出它的自反闭包r(R). （3）（2分）求出它的对称闭包S(R).
（4）（4分）求出它的传递闭包t(R)（限用矩阵算法）.
注：后面三小题的所有结果最后都要用序偶的形式来表达。 5．(12分)在整数集合Z上定义如下的乘法运算“?”：a?b?a?b?3，那么 ?Z,??构成一个什么样的代数结构？试证明你的结论。
3 / 4