中国科学院软件所 一九九六年招收硕士学位研究生入学考试试题答案 试题名称：离散数学 主合取范式： 主析取范式： 1） 2）   设 P: 张某杀了厂长； Q: 王某杀了厂长； R: 王某说了真话； S: 厂长家的灯亮着； T: 案发在半夜； 则前提： 1). 2). 3). 4). 5). 反证 .P .T 前提2） .Q 前提1）与假设 .R 前提4） .S 前提3） .T 前提5） . P 2）与6）矛盾 .Q 前提1） 先证：若是双射，则g为满射，为f入射。 任取，是双射，从而存在使，显然，为满射。 任取，若，则，否则由是双射，再由 ， 知，矛盾。从而是f入射。 由于，，由于，是双射，由以上证明h知为满射，h为入射，即h为双射，同理可证f , g也为双射，且，，。 ，其中， .对任意，，对， 即R有自反性。 对任意，如果，即存在使均有，因为G是群，所以，且对存在x使，从而，即，所以R有对称性。 对任意，如果，.即存在使，有，，，。, ，，有传递性。 是F上的等价关系。 3).  x          1 0 0 0 0 1 1 1 1  2 0 0 1 1 0 0 1 1  3 0 1 0 1 0 1 0 1   R的等价类{}{，，}{，，}{} 1)对任意，，即，是自反射，同理。 对任意，如果且，即，，由(2)知a= b，即是反对称的。 对任意，如果，即，那么 ，，是可传递的。 综上知是A上的序关系。 2)任取，由(3)知  即  即 是的上界，若c是的上界，即，则有，则: ， 同样，于是: ，  即，即是的最小上界。 由(3){，}是的下界。 设c是的下界，即，，，，， 即是的最大下界。 。 解答：（反证法）设中T至多有个k-1度为1的结点，不妨设恰有a个，则：  因为，且，矛盾。证毕。 。 解答：（反证法）设D中有两个结点v，u，使得，因为D是竞赛图，所以不妨设，则D中至少存在一结点w，使得，从而，从而构成有向图回路，矛盾，证毕。 。 设是G中最长轨道，。由于P是最长的轨道，故，的邻点均在P上，由于G是简单图，令，，则，，所以，设，于是得G中长为l+1的图，由于，，故C外有一结点，由于G连通，所以有一条C外的轨道与C相连，不失一般性，设y和连通，于是，加上C之长大于l，这与P是的G最长轨道矛盾。证毕。