中国科学院软件所 一九九五年招收硕士学位研究生入学考试试题 试题名称：离散数学 代数结构部分（34分） (10分) 用A集合上的关系R定义一个新关系T:  要使T是等价关系,关系R至少要具备哪些性质?证明你的结论. (12分). 1).在格中,表示a和b的最小上界,定义: a是并不可约元如果,则必有x=a或y=a. 在下面两个哈斯图相应的格中,那些元素是并不可约元?如何刻画并不可约元?给出证明. 2).证明：有限格中，每个元素都可以表示成并不可约元的并。 (12分). H是有限群G的子群，对于，定义  证明： 图论部分（34分） (10分). G称为k色临界图是指，对任意，均有，其中表示G的着色数。 证明：在k色临界图G中，其中，d(v)是结点（顶点）v的度（次数）。 (12分). G是简单连通无向图， G中的最长通路（轨道）为，证明。 证明：G-{}仍为连通图。 (12分). G是n个结点的简单无向图，若对任意，，证明： G是连通图。 G是哈密尔顿图。 数理逻辑部分（32分） (6分). 求的主析取范式和主合取范式。 (8分). 下列蕴涵关系是否成立，若成立，给出证明，否则给出反例： 1） 2） (8分). 求与下面公式等价的前束范式：  (10分). 将下列推理形式化，并对正确的推理给出推理过程，要求指明所设命题或谓词的含义。 没有大于2的偶素数，因而任何偶素数必不大于2。 每个喜欢步行的人都不喜欢坐汽车，每个人或者喜欢坐汽车或者喜欢骑自行车，并非每个人都喜欢骑自行车，因而有人不喜欢步行。