华东理工大学2004离散数学模拟试卷试卷.doc

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