一九九三年招收硕士学位研究生入学考试试题

一九九三年招收硕士学位研究生入学考试试题 H+S$nt  
试题名称：离散数学 . 6IS c  
数理逻辑部分(共34分) 4N`*!w8;#  
一.(12分)下列推理是否成立?证明你的结论. Yr^XgH 9(  
a)     前提: Bkh,@d|Z  
结论: G5z,% "3  
b)     前提: k|E7`Fz,  
结论:
G':l.F  
二.(10分) Q9mn|PW~d  
      是否最小联结词组?即能否仅用联结词组 和 表示所有的命题公式?证明你的结论. *S8
G"}Z{  
三.(12分) p(/c_H t  
      三个前提为: O%AhaI  
          IMVK]_Y/*0  
          Sc3JK=Pt>  
          4 =;J*  
      两个结论为: A7eH6 u6  
          #jsL%Z<?  
          S
T4N" :  
写出推导过程. R<P?&s!  
p]~j?ae=$x  
代数结构部分(共34分) rI P&6y3n  
一.(10分) ;UT14h
  
      和 是集合S中的等价关系, 和 是它们产生的划分.证明: lc {`ay,  
当且仅当 的每一个划分都包含在 的每一个分块中. #\??GbRUf  
五.(10分) >-\J)mP  
    设 是n阶有限群,e为单位元, 是G 的任意几个元素,不一定两两不同.试证:存在整数p和q, ,使得 . 3KCYxtIQ  
六.(14分) LUBtxAi  
    设 是环,其乘法单位元记为1,加法单位元记为0,对于任意 ,定义 , .求证: 也是环,并且与环 同构 *D3(01u  
XdrTxN  
图论部分(共32分) WawNmYP  
七.(11分) H|odOo[  
    设连通单图G有n个结点(或称作顶点), ,m条边 ,定义矩阵 , ,分别如下: TTt-dh  
    1) 0J:@!I!K  
    2) zPco '  
    3) ( uK.n8G`  
证明: Uc
g D  
    (其中 为结点 的次数(或称为度数), 为矩阵B 的转置). W0TjKI@  
八.(11分) Wm^kf~*X  
    设G是连通单图,但不是完全图,则存在三个结点u,v,w,使uv,vw E(G),但uw E(G). $W^_V&g  
Bq! 3{T  
Yjl:v(,\  
九(10分) _Ba2+?D   
    连通图G 的树图是一个图,它的结点 为G的生成树, 与 相连的充要条件是它们恰好有v-2条公共边(其中v为G的结点数).证明:连通图的树图是连通图.

看不懂,什么东西呀