一、判断题(每题2分，共12分)
1.在命运题逻辑中，任何命题公式的主合取范式都是存在的，并且是唯一的。()
2.与是不等值的()
3.设是非连通平面图G的对偶图，设分别为的顶点数，边数和面数，则它们之间满足欧拉公式：。()
4.设无向图G具有割点，则G中一定不存在哈密尔顿通路。()
5.设，A上的恒等关系既是A上的等价关系也是A上的偏序关系。()
6.设A,B,C,D均为非空的集合，已知A*B且C*D，则一定有。()
二、填空题(每小题3分，共30分)
1.设p:小王走路,q:小王听音乐,在命题逻辑中，命题“小王边走路边听音乐”的符号化形式为___________________。
2.设F(x):x是人，H(x,y):x与y一样高，在一阶逻辑中，命题“人都不一样高”的符号化形式为_________________。
3.的成真赋值为________________________。
4.设G是n阶无向带权边通图，各变的权均为a(a>0),设T是G的一棵最小生成树，则T的权W(T)=_______________________。
5.设G1,G2,G3,G4都是4阶3条边的无向简单图，则它们之间至少有___________________个是同构的。
6.设G是n(n2)阶二部图，又是平面图，则命题“G的对偶图是欧拉图”的真值为_______________________。
7.设为整数集，，则f的值域ranf=___________。
8.设则A上共有____________个不同的等价关系。
9.设，恒等关系IA的传递闭包t(IA)=_________________。
10.在实数集合R上定义二元运算如下：____________其中“-”为普通的减法，命题“是代数系统”的真值为___________________。
三、计算题(共43分)
1.求下面公式的主析取范式(写过程，6分)
2.求下面公式的前束范式(6分)
3.画一棵带权为2，2，2，3，3，4，5，8的最优二元树T，并计算它的权W(T)。(6分)
4.(1)在一棵有2个2度顶点，4个3度顶点，其余顶点都是树叶的无向树中，应该有几片树叶?(2)画出两棵非同构的'满足(1)中顶点度数的无向树T1和T2。(6分)
5.设全集E={1,2,3,4,5,6},子集A={1,2},B={2,3,4},C={5,6},求下面集合：(1)(2)(3)(6分)
6.设为一个偏序集，其中，A={1，2，3，4，6，9，24，54}是A上的整除关系。
(1)画出的哈斯图;
(2)求R关于A的极大元;
(3)求B={4,6,9}的最小上界和最大下界。(6分)
7.G=,A={a,b,c},*的运算表为：(7分)
(1)G是否为阿贝尔群?
(2)找出G的单位元;
(3)找出G的幂等元;
(4)求b的逆元和c的逆元。
四、证明题(每小题5分，共15分)
1.在一阶逻辑中，构造下面的证明：前提：，F(a)结论:(5分)
2.无向图G如图所示。(1)证明G是哈密尔图;(2)引证G不是平面图。(5分)
3.设A,B是全集E的子集，已知证明。(5分)
