東北大学离散数学试卷及答案.doc

一、填空 20% （每小题2分） P：你努力，Q：你失败。“除非你努力，否则你将失败”的翻译为 ；“虽然你努力了，但还是失败了”的翻译为 。 2、论域D={1，2}，指定谓词P P (1,1) P (1,2) P (2,1) P (2,2) T T F F 则公式真值为 。 设S={a1 ，a2 ，…，a8}，Bi是S的子集，则由B31所表达的子集是 。 设A={2，3，4，5，6}上的二元关系，则R= （列举法）。 R的关系矩阵MR= 。 5、设A={1，2，3}，则A上既不是对称的又不是反对称的关系R= ；A上既是对称的又是反对称的关系R= 。 * a b c a b c a b c b b c c c b 6、设代数系统A，*，其中A={a，b，c}, 则幺元是 ；是否有幂等 性 ；是否有对称性 。 7、4阶群必是 群或 群。 8、下面偏序格是分配格的是 。 9、n个结点的无向完全图Kn的边数为 ，欧拉图的充要条件是 。 10、公式 的根树表示为 。 二、选择 20% （每小题2分） 1、在下述公式中是重言式为（ ） A．；B．； C．； D． 。 2、命题公式 中极小项的个数为（ ），成真赋值的个数为（ ）。 A．0； B．1； C．2； D．3 。 3、设，则 有（ ）个元素。 A．3； B．6； C．7； D．8 。 设，定义上的等价关系 则由 R产 生的上一个划分共有（ ）个分块。 A．4； B．5； C．6； D．9 。 5、设，S上关系R的关系图为 则R具有（ ）性质。 A．自反性、对称性、传递性； B．反自反性、反对称性； C．反自反性、反对称性、传递性； D．自反性 。 6、设 为普通加法和乘法，则（ ）是域。 A． B． C． D．= N 。 7、下面偏序集（ ）能构成格。 8、在如下的有向图中，从V1到V4长度为3 的道路有（ ）条。 A．1； B．2； C．3； D．4 。 9、在如下各图中（ ）欧拉图。 10、设R是实数集合，“”为普通乘法，则代数系统R ，× 是（ ）。 A．群； B．独异点； C．半群 。 三、证明 46% 设R是A上一个二元关系， 试证明若R是A上一个等价关系，则S也是A上的一个等价关系。（9分） 用逻辑推理证明： 所有的舞蹈者都很有风度，王华是个学生且是个舞蹈者。因此有些学生很有风度。（11分） 若是从A到B的函数，定义一个函数 对任意有，证明：若f是A到B的满射，则g是从B到 的单射。（10分） 若无向图G中只有两个奇数度结点，则这两个结点一定连通。（8分） 设G是具有n个结点的无向简单图，其边数，则G是Hamilton图（8分） 四、计算 14% 设Z6,+6是一个群，这里+6是模6加法，Z6={[0 ]，[1]，[2]，[3]，[4]，[5]}，试求出Z6,+6的所有子群及其相应左陪集。（7分） 权数1，4，9，16，25，36，49，64，81，100构造一棵最优二叉树。（7分） 填空 20%（每小题2分） 1、； 2、T 3、 4、R={2,2,2,