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

一九九二年招收硕士学位研究生入学考试试题 o@-%fh;2@  
试题名称：离散数学 F)?RcF*  
（供计算所用）  Kx 1  
代数结构部分（共32分）  ls|9e  
一．     判断对错（18分）
fvT`^=5  
1．A，B是集合，命题 和 不可能同时成立。 ;^cwy7_t  
2．若R 是集合A上的传递关系，则 也是集合A 上的传递关系。 N#KJ|f  
3．四阶群中必有四阶元。 m.cA=%  
4．非循环群的每一个子群必是非循环群。 p)JxY$+  
5．f 是G1 到G2的群同态映射，若G1是交换群，则G2 也是交换群。 2X{
AjB  
6．分配格必是模格。 n"w#:7O v  
二．     （14分） @Y&!dF;W9  
是D={1,2,……n}上所有置换（双射）组成的集合。 对置换乘法（函数复合）运算构成群，G是 的子群。 [/EzUUlG  
1.     在 上定义关系R, , 存在
2W<p5K  
证明：R是 上的等价关系。 {][wn1Fu  
2.     取n=3，列出 的所有元素，找出 的一个二元阶子群G，求上述等价关系所确定的 一个划分。 GqX-e; 4  
$PxBUQT  
图论部分（共33分） kMy,AqRX  
一.     (8分) 1]$r?2/  
下面列出了一些关于简单图的结论,它们的哪些组合可以作为树的定义,写出所有可能,但不允许在组合中有多余的结论: EL#?VX  
a.     无圈.  o#MSX1n  
b.     连通. SL$`,hGK  
c.     边数=结点数-1; 4k"Y|.3j?  
d.     每队结点间有且仅有一条通路(轨); tqRtGG#im  
e.     连通图的每一条边均为割边; \O|s$Ok   
f.       在原图中增加任一条边恰好得到一个圈; 1&7W7r' h  
二.     (15分) = 0o3=1:^  
1.     右图是否是平面图,为什么? D6$AsH2  
2.     如何从一连通图的关联距阵中判断一边是否割边? U-(tR"  
3.     一个简单图的七个结点的次数分别为6,6,5,4,3,3,1,问这样的图是否存在?若存在,请画出相应的图 ,否则,说明理由. dd=/M^\$h  
三.     (10分) (2)7ERZ  
证明:连通图的任意两条最长的通路(轨)有公共结点. e51J;m  
qu5OA~,  
数理逻辑部分(共29分) v\F0zT  
一.     判断对错(9分) y#,6s:9>  
1.       为重言式. t}gR{WJ  
2.     联结词 的定义是 .{ }是最小的联结词组. $Js8GL6  
3.       的前束范式为 . fC"<>/;  
二.     (10分) jn$umvM  
利用谓词E(x, y)(表示x与y 相同”)来构造命题函数(谓词演算的合式公式),使得该命题函数具有性质:”在个体域 D中可满足:当且仅当D只含有两个个体.”论述你构造的正确性. ;b sMfT