中国科学院软件所 一九九五年招收硕士学位研究生入学考试试题答案 试题名称：离散数学 一．，是对称的。 若R是自反的，为真，而，为真， 是自反的。 若R是传递的，,  ,是传递的。 综上知，要使T为等价关系，R至少要有自反性和传递性。 二．1）e,f,g,h为并不可约元，F,C,E,G,H为并不可约元。 在哈斯图中反映的是中元素的置位关系，如果一个元素至多有一个置位元素，则该元素为并不可约元。 若a是非“并不可约元”，即存在使，在哈斯图中从x,y分别有条路通向a并在a处首次会合，到达a之前的两个元素即是的a置位元素，从而a至少有两个置位元素。由此得出a是“并不可约元”，必定a至多有一个置位元素，反过来，若a至少有两个置位元素，显然，且,不是并不可约元。 2）任取A中元素，如果a至多有一个置位元素，则a本身为并不可约元，且 ，如果a至少有两个置位元素，则，若都是并不可约元，这时已结束，如果至少其中一个不是并不可约元，则对文法继续重复2）。由于是有限格，故这一过程在有限步之内会停止，最后。其中均为并不可约元，这里如果出现，则用代替，另用代替，证毕。 3）证明：令 是映射，即对每一个元素均有效，若，则，H是子群。于是，即 任取，使，是满射。 若，知，即， ，为单射。 综上知是到的双射。是有限群，均为有限集合。  四．证明：用反证法。若在图G中存在，由于G是k 色临界图，对可作正常k-1着色，在 G中与邻接的结点个数。在中对这些结点至多用k-2种颜色，即至少还有k-1种颜色中的一种未使用，这样就得到G的正常k-1着色，与已知矛盾。故不可， 。 五．1）是G中的最长路，L的长度为l-1，结点的邻点为 ，，若不在L上，则L可以延长至，这L与是最长通路矛盾，均L在上,。 2）用反证法。设不连通，是一条通路，它在一个连通片中，令C是不在的那个连通片。在C中有长为m的最长通路。由1）知，在图G中，令，通路是G中长为。由于L是最长路，即。由此看出中至多有个结点与相邻。所以：  与矛盾，是连通图。 六．1）用反证法。若G不连通，它至少有两个连通片，取，与已知条件矛盾，是连通的。 2）设是G的最长通路，显然。由于L是G的最长通路，和的邻点L都在上，令的邻点为，如果都不与相邻，那，与已知条件矛盾。于是存在一个i，使与相邻，与相邻，构造长为l+1的回路。如果，G中必有不在L上的结点w，由于G连通，w与L上的一个结点相邻，. 当时，是G中长l+1为的通路。 当时，是G中长l+1为的通路。 与L是G的最大通路矛盾，故不可。上面的回路C既是的G哈密尔顿回路，是哈密尔顿图。 七．    八．1） 2）反例：论域为自然数，。 对任何x都能找到y=x+1，显然x<y。为T， 对任何y存在x=y+1，使x不小于y，为F. 从而蕴涵关系不成立。 九．    十．1) 论域：自然数集合， 是偶数，是素数，。 推理形式化为：  因为它们是等价的两个谓词公式，显然蕴涵关系成立，即推理是正确的。 论域：全体人。 喜欢步行，喜欢坐汽车，喜欢起自行车。 推理形式化为：  1). 前提 2). 1), E 3). 2), ES 4). 前提 5). 4) US 6). 3) 5) I 7). 前提 8). 7) US 9). 6) 8) I 10). 9) EG