1、第1页共 2 页三 峡 大 学2012年研究生入学考试试题(A卷)科目代码： 603 科目名称： 离散数学 （考生必须将答案写在答题纸上）1（10分）求 的主析取范式和主合取范式。2（10分）用真值表判断公式 是否为永真式。3 （10分） 给定解释I：定义域D为自然数集， 谓词为“”。在解释I下，求公式的真值。4（10分）构造下面推理的证明：前提：，结论：5（10分）化简下式：6（10分) 设R是A上一个二元关系，。证明若R是A上一个等价关系，则S也是A上的一个等价关系。7（15分），定义上关系为当且仅当 (i) ，或者 (ii) 。（1）证明是集合上的偏序关系；（2）确定偏序集的所有极大元和
2、极小元；（3）若，求出偏序关系。8（15分）设（1）求的关系矩阵和关系图；（2）利用关系矩阵运算求的传递闭包。9（10分）将平面分成两两相邻的m个平面区域，求m的最大值？并证明你的结论。10(10分)设G是具有n个结点的无向简单图，其边数，则G是Hamilton图。11（10分）一次聚会上有7个人a,b,c,d,e,f,g，已知：a会讲汉语；b会讲汉语和法语；c会讲汉语和德语；d会讲法语和英语；e会讲英语；f会讲德语和西班牙语；g会讲英语和西班牙语。请建立图的模型说明如何安排这7个人就坐，使得每个人都能和他身边的人进行交谈。12（10分）在下列赋权图中（边上的数字为该边的权）找一个最小连通子图，并计算它的权。13(10 分)考虑110的正因子集合S关于最大公约数和最小公倍数运算构成的布尔代数，求它的子布尔代数。14(10 分)设是一个布尔代数，如果在A上定义二元运算，为，则是一阿贝尔群。第 2 页
