中国科学院软件所 一九九七年招收硕士学位研究生入学考试试题 试题名称：离散数学 （8分） 设为交换群，n为正整数，证明： （12分） 设是偏序集。 叙述链（线性序或全序）的定义。 证明：链是格。 证明：链是分配格。 （15分） 设R是集合A上的二元关系。 求A上包含R的最小等价关系E的表达式。 证明E的最小性。 以，为例验证你的结果。 (10分) 证明下列蕴涵式。   （12分） 证明或反驳下列公式： （4分） （8分） （10分） 求公式的主析取范式。 求公式的前束范式。 （10分） 设G是严格有向图，则G中有长度大于或等于的有向轨，其中 。 （11分） 设G是无向单图，则存在G的二分子图B，使得。 （12分） 设G是(k-1)边连通的k正则图，V(G)且是偶数，则G有完备匹配。