原文内容来自免费考研论坛，请点击查看全文
http://bbs.freekaoyan.com/viewthread.php?tid=176048
一九九二年招收硕士学位研究生入学考试试题 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