一、填空题（每空3分，共30分）
1．设F(x)：x是人，H(x)：x呼吸，在一阶逻辑中，命题“凡人都呼吸”的符号化形式为_______ _ ________。
2．“我正在说谎”不是命题是 。
3．A={a,b},则A的幂集P(A)＝ 。
4．命题公式(p∧(p→q))→q是__ ___式。(矛盾、永真、非永真的可满足)
5．设*为S上的二元运算，如果对于任意的x,y,zÎS，都有
，则称运算*在S上是可结合的。
6．设连通平面图G有n个顶点，r个面，则G有 条边。
7．设T是非平凡的无向树，则T中至少有 树叶。
8．已知n阶无向简单图G有m条边，则G的补图有__________条边。
9．设 p： 天下大雨；q：他乘公共汽车上班。命题“只有天下大雨，他才乘公共汽车上班”符号化为 。
10．若完全图Kn (n>2)是可一笔画出,则n为 。
二、判断题（每小题1分，共10分）对打√，错打×。
1．若一个图可以一笔画，这个图一定是欧拉图。
2. 只要推理正确，结论就会正确。
3.在偏序集中，最大元一定是极大元，极大元也一定是最大元。
4.空集是一切集合的真子集。
5.集合A上的等价关系与A的划分是一一对应的。
6.有向图D，若D是强连通的，则D一定是单向连通的。
7.若一棵无向树有11个顶点, 则它的所有点的度数和为22。
8.若 AB = AC,则 B = C。
9. 一个关系不是对称的，就必定是反对称的。
10. 通过图G的每条边恰好一次的路是哈密顿路。
三、计算题（每小题5分，共30分）
1.求公式p®q的主析取范式和主合取范式。
2.设A＝{{a,{a}},a}，B={a,{a}},求AÅB。
3．设A＝{a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>},求：R2和R的关系矩阵。
4．设个体域D＝{a,b,c},消去公式"x"y(F(x)∨G(y))中的量词。
5.设n阶无向简单图为3－正则图，且边数m和 n满足2n-3=m,求图的顶点数和边数。
6.一棵树有5片树叶，3个2度顶点，其余的分支点都是3度顶点，求树的顶点数。
四.画图题(每小题4分共20分，画在空白处，标明题号）
1．画出Øp®q的真值表。
2．画出完全图K5。
3．画出集合L＝{1，2，3，6，12}上整除关系的哈斯图。
4．画一颗权为3，4，5，6，7，8，9的最优二叉树。
5．设A＝{a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>}，画出R的关系图。
五、证明题（每小题5分，共10分）
1．在自然推理系统P中构造下面推理的证明：
前提：p∨q，p®┐r，┐s®t，s®r，┐t
结论：r∧q
2．设A＝{1，2，3，4}，R为A´A上的二元关系，任意<a,b>,<c,d>ÎA´A,
<a,b>R<c,d>Ûa+b=c+d,证明：R是等价关系。