一、 不定项选择题（3×5分，每题可能有1至4个正确答案，多选或错选不得分）
1. 对于以下前提：S→┓Q，S∨R，┓R，┓P?Q其有效结论是（
）。
（A） S （B） P （C） Q （D） ┓Q
2．集合A＝{ a , b , c , d ,
e , f , g } , A上的一个划分π＝{{ a , b } , { c , d , e } , { f , g}},那么π所对应的等价关系应有（
）个序偶。
（A） 15 (B) 16 (C) 17
(D) 18
3. 以下关系属于偏序关系的是（
）。
（A）实数集上两实数间的“等于”关系 （B） 同余关系
（C）整数集上两实数间的“大于”关系 （D）良序关系
4．以下哈斯图构成分配格的是（
）。
（A）
（B）
（C） （D）
5．循环群＜｛[1]，[2]，[3]，[4]，[5]，[6]｝，×7＞的生成元是（
）。
（A）[2] (B) [3] (C) [4] (D) [5]
二、证明 (P∧ (P→Q))→Q为永真式。
（6分）
三、证明：?x (Q(x)→R(x)) , ?x (Q(x)∧ I (x)) ? ?x (R(x)∧ I (x)) （6分）
四、某班有学生60人，其中有38人学习PASCAL语言，有16人学习C语言，有21人学习COBOL语言；有3 个人这3种语言都学习，有2个人这3种语言都不学习，问仅学习两门语言的学生数是多少？
（8分）
五、关系R如图所示，试写出关系矩阵并求出R的自反闭包，对称闭包和传递闭包。
（12分）
六、证明若关系R是对称的，则R的传递闭包t(R)也是对称的。 （10分）
提示：首先证明对任意自然数k , 若R对称，则Rk对称。
七、对于代数系统＜R+,×＞和＜R,+＞，其中R+为正实数（不含0）集，R为实数集，×为普通乘法，＋为普通加法：
（1）说明＜R+,×＞和＜R,+＞都是群。
（2）证明自然对数函数Ln(x)是＜R+,×＞到＜R,+＞的同构。
（3）若A＝｛x | Ln(x)∈H且＜H,+＞为＜R，＋＞的子群｝，证明＜A，×＞为＜R+,×＞的子群。
（15分）
八、代数系统＜H，＊＞是群＜G，＊＞的一个子群，证明以下结论：
（1）当a∈H时,H关于a的左右陪集为aH=Ha=H
（2）关系R＝｛＜a , b＞｜a∈G,b∈G且a－1＊b∈H ｝是等价关系且对任意a∈G,有aH=[a]R。
（3）当a∈G－H时，＜aH，＊＞一定不是＜G,＊＞的子群。
(15分)
九、写出以下无向图的邻接矩阵并画出其补图。
（7分）
十、证明n阶（n>1）简单无向连通图中，至少有两个顶点的度数相同。
（6分）