×B.2.设A={1,2,3,4,5},R={<x,y>|xÎA,yÎA且x+y£4},S={<x,y>|xÎA,yÎA且x+y<0},试求R,S,R·S,S·R,R-1,S-1,r(S),s(R).3.设A={1,2,3,4,5,6,7,8},R是A上的整除关系,B={2,4,6}.(1)写出关系R的表示式;(2)画出关系R的哈斯图;(3)求出集合B的最大元、最小元.4.设G=<V,E>,V={v1,v2,v3,v4,v5},E={(v1,v3),(v2,v3),(v2,v4),(v3,v4),(v3,v5),(v4,v5)},试(1)给出G的图形表示;(2)写出其邻接矩阵;(3)求出每个结点的度数;(4)画出其补图的图形.5.图G=<V,E>,其中V={a,b,c,d,e},E={(a,b),(a,c),(a,e),(b,d),(b,e),(c,e),(c,d),(d,e)},对应边的权值依次为2、1、2、3、6、1、4及5,试(1)画出G的图形;(2)写出G的邻接矩阵;(3)求出G权最小的生成树及其权值.6.设有一组权为2,3,5,7,17,31,试画出相应的最优二叉树,计算该最优二叉树的权.7.求P®QÚR的析取范式,合取范式、主析取范式,主合取范式.8.设谓词公式.(1)试写出量词的辖域;(2)指出该公式的自由变元和约束变元.9.设个体域为D={a1,a2},求谓词公式("y)($x)P(x,y)消去量词后的等值式;三、证明题1.对任意三个集合A,B和C,试证明:若A´B=A´C,且A¹,则B=C.2.试证明:若R与S是集合A上的自反关系,则R∩S也是集合A上的自反关系.3.设连通图G有k个奇数度的结点,证明在图G中至少要添加条边才能使其成为欧拉图.4.试证明(P®(QÚØR))ÙØPÙQ与Ø(PÚØQ)等价.5.试证明:Ø(A∧ØB)∧(ØB∨C)∧ØCÞØA.
全文预览
