中国科学技术大学 一九九六年招收硕士学位研究生入学考试试题 试题名称：离散数学 数理逻辑部分 一.(10分). 试求的主合取范式和主析取范式。 证明: 1).(5分). 2).(7分). 三.(10分). 办案人员得到下列线索: 1).不是张某就是王某杀了厂长,而且两人不会合谋. 2).张某不可能在半夜作案. 3).王某说半夜厂长家灯亮着. 4).王某若没作案,则他不会说谎. 5).若厂长家半夜灯亮着,则案发生在半夜. 请你根据线索找出作案者,形式化证明你的结论. 代数结构部分 四.(10分）. 设,,.记S上的恒同映射为. 证明:如果,,,则f, g ,h均为双射,并求 出. G是{1,2,3}上的置换群，|G|=6. 1). (4分).已知，试G列出的全部元素。 2). (5分).令，在F上定义关系，对任意,存在，使对任何，均有，证明R是F上的等价关系。 3). (3分).求R所确定的等价类。 设是集合A上的二元运算，对任意，满足. 1).， 2).， 3).， 现定义A上关系，证明： 1). (5分).是A上的序关系 2). (7分).对任何，均有一个最小上界和一个最大下界。 图论部分 .(10分).设T是树，且，则T中至少k有个结点的度数（或次数）为1。 (2分).设G是无向完全图，若对G的每条边指定一个方向，所得到的图称为竞赛图，证明：无有向回路（或有向圈）的竞赛图D:<V(D),E(D)>中，对任意,。 (12分).证明：设是简单无向连通图，且，则G中存在一条不小于的通路（或轨道）。