中国科学院计算所 一九九三年招收硕士学位研究生入学考试试题 试题名称：离散数学 数理逻辑部分(共34分) 一.(12分)下列推理是否成立?证明你的结论. 前提: 结论: 前提: 结论: 二.(10分) 是否最小联结词组?即能否仅用联结词组和表示所有的命题公式?证明你的结论. 三.(12分) 三个前提为:    两个结论为:   写出推导过程. 代数结构部分(共34分) 一.(10分) 和是集合S中的等价关系,和是它们产生的划分.证明: 当且仅当的每一个划分都包含在的每一个分块中. 五.(10分) 设是n阶有限群,e为单位元,是G 的任意几个元素,不一定两两不同.试证:存在整数p和q, ,使得. 六.(14分) 设是环,其乘法单位元记为1,加法单位元记为0,对于任意,定义,.求证:也是环,并且与环同构 图论部分(共32分) 七.(11分) 设连通单图G有n个结点(或称作顶点), ,m条边,定义矩阵,,分别如下: 1)  2)  3)  证明: (其中为结点的次数(或称为度数),为矩阵B 的转置). 八.(11分) 设G是连通单图,但不是完全图,则存在三个结点u,v,w,使uv,vwE(G),但uwE(G). 九(10分) 连通图G 的树图是一个图,它的结点为G的生成树,与相连的充要条件是它们恰好有v-2条公共边(其中v为G的结点数).证明:连通图的树图是连通图.