中国科学院计算所 一九九三年招收硕士学位研究生入学考试试题答案 试题名称：离散数学 一.(a)将A,B,C,D全部赋值为假,可得所有前提取值为真,而结论为假,所以推理不 成立. 1) A 前提 2)  前提 3) 1), 2) , T 4) 前提 5) 4) T 6) 5) E 7) 3) 6) T 所以推理成立. 二.对公式中的联结词个数n做归纳证明: 当公式中仅含有联结词和时.则当公式的所有命题变元赋值为真时,公式也取值为真. 当时,公式为命题变元,成立. 假设时成立: 时，设公式为A，则存在公式B，C，使：，或且B，C中的联结词个数均。由假设，当所有变元赋值真时，B，C为真。 ；A取值为真。 所以不能表示永假公式。不是最小联结词组。 三．（a） . 前提 . 1）两次US . 前提 . 3）两次US . 4）T . 2）5）T . UG ( b ) .  前提 .  1）两次US . 前提 . 3）两次US . 4) T . 附加前提 . 5）6）T . 2) 7) T . 3)换名 . 9）两次US . 8） 10）T . 6) 11) CP . 12) UG 代数结构部分 四．令划分.若,对 为中任一划分块。。在中取代表元。是S的划分。使。 有，又 即 由 的任意性知：的每一划分块都包含在的某一划分块中。 若的每一划分块都包含在的划分块中。则即a, b在的同一划分块中,必有a, b 在的同一划分块中. . 五．令，考虑集合  若使，不妨设，则  。即使  若不使，则S中元素两两不同，。 又，又。 而G中有唯一的单位元e,。 即：使。 六．f保持运算        是同构映射。与同构。 七．设   则 为B的第i行与的第i列相乘. B的第i行有个1，而的第i列的相应分量也为1。  而为B的第i行与的第j列相乘.若同时是某边的两端点，则恰有k，使B的第i行与的第j列的第k个分量同时为1, 否则B的第i行与的第j列无同一分量同时为1，   八．证：连通，不是完全图，存在结点使，连 通，之间有通路。若长为2，则，使，但 ，设长k为时成立。则长k+1为时，设P上与u相 邻顶为，则若，则满足题设条件，若，则长为k，由假设，满足条件。结论成立。 九．对任意两株生成树，设已有k 条公共边，而有条不同边。这时存在边，但，从而有唯一的圈，圈中存在，使，且仍是G的生成树。否则中有圈，这与是树矛盾。 易知与恰好有条公共边，在树图上它们相邻。且与的公共边比与的公共边多一条。再对如法炮制，增加与的公共边树，总可以找到与只有一条不同边的树。相应地在树图上找到了从到的路。故树图连通。