中国科学技术大学
一九九一年招收硕士学位研究生入学考试试题
试题名称：离散数学
数理逻辑部分：（共34分）
（12分）
只允许用以下四个永真式（重言式）T1,T2,T3 以及蕴涵式M:
(T1)
(T2)
(T3)
(T4)
证明：
为真；
为真；
二．（10分）
写出公式的等价式，要求该等价式中只出现联结词┐和.
三．（12分）
下列公式是永真式吗？是划 ‘√’ ，不是划’X’;
图论部分（共30分）
四．（10分）
图G的结点数为v，连通分支个数为w，求G的完全关联矩阵的秩，并给出证明。
五．（10分）
证明5个结点的无向完全图K5不是平面图。
六．（10分）
设D是无回路简单有向图，结点集合,证明存在V中元素的一个排列,使得以为终结点的每条边，其起始点在中，.
代数结构部分（16分）
七．（10分）
R是A 上的二元关系，写出包含R的最小等价关系E的表达式。
八．（13分）
写出正四面体关于4个面的运动群（置换群）。
九．（13分）
G是有限交换群，令,对于
证明：当k 与|G|互素时，f是同构映射。
