1、下列命题公式为重言式的是（ ） 单选题 1分

2、下列语句中不是命题的只有（ ） 单选题 1分

3、设p：我很累，q：我去学习，命题：“除非我很累，否则我就去学习”的符号化正确的是（ ） 单选题 1分

4、下列等价式正确的是（      ） 单选题 1分

5、 单选题 1分

6、设A={1，2，3}，A上二元关系S={，，，}，则S是（ ） 单选题 1分

7、设集合X为人的全体，在X上定义关系R、S为R={<a，b|a，b∈X∧a是b的父亲}，S={ 单选题 1分

8、设A是正整数集，R={(x，y)|x，y∈A∧x+3y=12}，则R∩ ({2，3，4，6}×{2，3，4，6})=（ ） 单选题 1分

9、下列式子不正确的是（ ） 单选题 1分

10、下列命题正确的是（      ） 单选题 1分

11、在下列代数系统中，不是环的只有（ ） 单选题 1分

12、下列整数集对于整除关系都构成偏序集，而能构成格的是（ ） 单选题 1分

13、结点数为奇数且所有结点的度数也为奇数的连通图必定是（ ） 单选题 1分

14、无向图G是欧拉图当且仅当G是连通的且（ ） 单选题 1分

15、平面图(如下)的三个面的次数分别是（　　　） 单选题 1分

16、求一个公式的主析取或主合取范式的方法，有（ ）法和（ ）法。 填空题 2分

17、 填空题 2分

18、 填空题 2分

19、集合X={a，b，c，d}上二元关系R={ 填空题 2分

20、 填空题 2分

21、对代数系统，其中*是S上的二元运算，若a，b∈S，且对任意的x∈S，都有a*x=x*a=x，b*x=x*b=b，则称a为运算“*”的（ ），称b为运算“*”的（ ）。 填空题 2分

22、设是群，则满足结合律和（ ）；若｜S｜>l，S中不可能有（ ）。 填空题 2分

23、写出如右有向图的一条初级回路：（ ），其长度是（ ）。 填空题 2分

24、一个（ ）且（ ）的无向图称为树。 填空题 2分

25、在简单无向图G=<V，E>中，如果V中的每个结点都与其余的所有结点邻接，则该图称为（  ），如果V有n个结点，那么它还是（  ）度正则图。 填空题 2分

26、 简答题 5分

27、构造命题公式(p→ (q∧ r))→┐p的真值表。 简答题 5分

28、求图G＝<V，E>的可达矩阵，其中V＝｛v1,v2,v3,v4｝ E＝｛(v_x001f_1,v2), (v_x001f_2,v3), (v2,v4), (v3,v2), (v3,v4), (v3,v1), (v4,v1)｝ 简答题 6分

29、求下列公式的主析取范式和主合取范式：（P∧Q）∨（┐P∧R） 简答题 6分

30、设A＝｛2，3，4，6，8，12，24｝，R为A上整除关系，试画<A，R>的哈斯图，并求A中的最大元，最小元，极大元，极小元。 简答题 8分

31、设M是偶数集，＋和·是数的加、乘运算，证明<M，＋，·>是一个环。 简答题 6分

32、 简答题 6分

33、设G是简单平面图，G有n个顶点m条边，且m<30，证明G中存在一项点v，　　　　　　d（v）≤4。 简答题 8分

34、判断下面推理是否正确，并证明你的结论。 如果小王今天家里有事，则他不会来开会。如果小张今天看到小王，则小王今天来开会了。小张今天看到小王。所以小王今天家里没事。 简答题 6分

35、有6个村庄Vi，i=l，2，…，6欲修建道路使村村可通。现已有修建方案如下带权无向图所示，其中边表示道路，边上的数字表示修建该道路所需费用，问应选择修建哪些道路可使得任二个村庄之间是可通的且总的修建费用最低?要求写出求解过程，画出符合要求的最低费用的道路网络图并计算其费用。 简答题 9分