一、判断题（每题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分） |
