中国科学技术大学
一九九二年招收硕士学位研究生入学考试试题
试题名称：离散数学
（供计算所用）
代数结构部分（共32分）
判断对错（18分）
1．A，B是集合，命题和不可能同时成立。
2．若R 是集合A上的传递关系，则也是集合A 上的传递关系。
3．四阶群中必有四阶元。
4．非循环群的每一个子群必是非循环群。
5．f 是G1 到G2的群同态映射，若G1是交换群，则G2 也是交换群。
6．分配格必是模格。
（14分）
是D={1,2,……n}上所有置换（双射）组成的集合。对置换乘法（函数复合）运算构成群，G是的子群。
在上定义关系R,,存在
证明：R是上的等价关系。
取n=3，列出的所有元素，找出的一个二元阶子群G，求上述等价关系所确定的一个划分。
图论部分（共33分）
(8分)
下面列出了一些关于简单图的结论,它们的哪些组合可以作为树的定义,写出所有可能,但不允许在组合中有多余的结论:
无圈.
连通.
边数=结点数-1;
每队结点间有且仅有一条通路(轨);
连通图的每一条边均为割边;
在原图中增加任一条边恰好得到一个圈;
(15分)
右图是否是平面图,为什么?
如何从一连通图的关联距阵中判断一边是否割边?
一个简单图的七个结点的次数分别为6,6,5,4,3,3,1,问这样的图是否存在?若存在,请画出相应的图 ,否则,说明理由.
(10分)
证明:连通图的任意两条最长的通路(轨)有公共结点.
数理逻辑部分(共29分)
判断对错(9分)
为重言式.
联结词的定义是.{}是最小的联结词组.
的前束范式为.
(10分)
利用谓词E(x, y)(表示x与y 相同”)来构造命题函数(谓词演算的合式公式),使得该命题函数具有性质:”在个体域 D中可满足:当且仅当D只含有两个个体.”论述你构造的正确性.
(10分)
用真值表证明: 为重言式
用推理规则证明:.
(不准使用规则).
