【一．填空R-11R是集合X上的关系,若,则称R是X上的等价关系.2R是集合X上的二元关系,则关系1/R={|}.3T是一连通图,若T满足,则T构成树.4G是一个图,若G可以,则称G为二部图.5已知谓词公式xF(x,y)y】

　　一．填空R-1

　　1R是集合X上的关系,若,则称R是X上的等价关系.

　　2R是集合X上的二元关系,则关系1/R={|}.

　　3T是一连通图,若T满足,则T构成树.

　　4G是一个图,若G可以,则称G为二部图.

　　5已知谓词公式xF(x,y)yH(x,y),则是自由变元.

　　6已知谓词公式xF(x,y)yG(x,y,z),则是约束变元.

　　7图G存在悬挂顶点,则至少删去条边,图变成两个连通分支.

　　8T是一棵树,则T的树叶最少有片.

　　9G是一个连通图,若G有一个,则G为欧拉图.

　　10图G存在悬挂顶点,则图G的边连通度λ（G）为(.

　　11．设p:小王走路,q:小王听音乐,在命题逻辑中,命题“小王边走路边听音乐”的符号化形式为___________________.

　　12.设F(x)：x是人,H(x,y)：x与y一样高,在一阶逻辑中,命题“人都不一样高”的符号化形式为_________________.

　　13.命题公式r（pq）的成真赋值为_________________,对应的极小项为,成假赋值为对应的极大项为,.

　　14．T是一棵具有n个顶点m条边的树,则n与m的关系是.

　　15．G是一个图,若G含有与的子图,则G一定是非平面图.

　　二．用一阶逻辑公式表示下列命题

　　1集合A属于集合B,

　　2集合A等于集合B

　　3集合X=空集

　　4．集合A上的二元关系R是自反的

　　5．集合A上的二元关系R是反自反的

　　6．集合A上的二元关系R是对称的

　　7．集合A上的二元关系R是反对称的

　　8．集合A上的二元关系R是传递的

　　三．按要求完成下列各题

　　1A={x,y,z},R={,,,},S={,,,},求R◦S、S◦R及S的传递闭包t（R）.

　　2已知集合E={1,2,{1,2}},S={1,{2}},求ES,ES,(E－S)(S－E).求命题公式（pqr）的主析取范式和主合取范式.

　　3A={1,2,{2}},求A×A,P（A）.

　　4画一棵带权为2,2,3,3,4,5,8的最优二元树T,并计算它的权W（T）.

　　5（1）在一棵有2个2度顶点,4个3度顶点,其余顶点都是树叶的无向树中,应该有几片树叶?（2）画出两棵非同构的满足（1）中顶点度数的无向树T1和T2.

　　6一棵树有5片树叶,3个2度顶点,其余的顶点均为3度顶点,问T有几个顶点?

　　7A={1,2,3,5,7,14,15,35},R是A上的整除关系:Rx|y(x整除y),画出R的哈斯图,设B={2,5,7,14,35},求B关于R的极大元、极小元和最大元、最小元.

　　9求出下列图的所有点割集和边割集.

　　10．已知一个有向图G=,其中

　　V={v1,v2,v3},

　　E={,,,,},

　　求D的邻接矩阵A；（2）求顶点v1的入度、出度及次数（3）将G看成无向图,写出关联矩阵.

　　11．用二元树表示下面的表达式

　　((x－2y)*3z－7x)÷(4z-2y)2

　　12．求下列图的最小生成树

　　四．证明下列命题(14分)

　　1A,B,C是任意集合,证明(A-B)-C=(A-C)-(B-C)

　　2A,B,C是任意集合,证明若A⊕B=A⊕C,则B=C

　　3A,B是集合,若P(A)∩P(B)=P(A∩B),其中P(A)表示集合A的幂集.

　　4p,q,r是任意命题,证明p→(q∨r)(p∧┑q)→r

　　5p,q,r是任意命题,证明(p→q)∧(q→r)p→r

　　6前提：(p∧q)→r,┐r∨s,┐s,p,

　　结论：┐q

　　7设A={1,2,3,4},在A×A上定义二元关系R：,A×A,Rx+y=u+v,证明R为A×A上的等价关系.