中国科学技术大学
一九九二年招收硕士学位研究生入学考试试题答案
试题名称：离散数学
（供计算所用）
代数结构部分解答:
2,6对,
1,3,4,5错.
1. 自反性.e∈G, s∈Sn,
对称性:若sRt 即 .
而
传递性:若 sRt , tRu 即 ,
是 Sn上的等价关系.
2.}, G={}
(123) (132) (12) (13) (23)
(12) (12)
(132) (123) (12) (23) (13)
共有4个分块
如果则 )}
如果则
图论部分解答
a, b ;
a, c ;
b , c;
d;
e;
f;
不是平面图。 因为它有与同胚的子图。
将该边对应的列从关联矩阵中删去，若剩下的矩阵的秩等于原来关联矩阵的秩，则为非割边，否则为割边。
不存在。如果存在这样的图，由于存在两个结点的次数为6,那么这两个结点与其他每个结点均相邻，所以该图中每个结点的次数均。而无一次结点所以这样的图不存在。
设 和 是G的两条最长的通路，并且无公共交点。因为G是连通图， 与 之间有路l, 设 是从 出发沿l前进最后一个和相交的结点，而是路l第一次与相交的结点。当时，构造一条新的路l’,它从出发，沿到，然后沿l从到，最后沿从到，该路长度>k,这与是最长的通路矛盾。故不可。与有公共结点。对 j , p其他情况讨论类似。
数理逻辑部分
一．1，2，对。3 错。
二．命题函数为
论证：
当论域D仅包含两个元素时,D={ a , b },在D上
为T,所以
为T.
当论域D包含多于两个元素时,D={a , b ,………},显然为T,且时,为F,
为F,
(*)不满足.
当论域D包含元素个数<2,D=或D={a}时.
为F,不满足.
1.
B C
1
0
1
0 0
1
1
0
1
1
0
1
0
1
1
1
1
为重言式.
由1知(*)
前提
前提
附加前提
2) 3) MP
1) 4) MP
演绎定理
(*)
或
前提
1)
2)
3)
4)
前提
6)
C 5) 7)
