:(2)写出G的邻接矩阵53)G权最小的生成树及其权值6.设有一组权为2,3,5,7,17,31,试画出相应的最优二叉树,计算该最优二叉树的权.663?311?171?75?52?3权为?2*5+3*5+5*4+7*3+17*2+31=1317.求P?QR的析取范式,合取范式、主析取范式,主合取范式.8.设谓词公式(x)(P(x,y)?(?z)Q(y,x,z))?(?y)R(y,z).(1)试写出量词的辖域;7(2)指出该公式的自由变元和约束变元.9.设个体域为D={a1,a2},求谓词公式(?y)(x)P(x,y)消去量词后的等值式;三、证明题1.对任意三个集合A,B和C,试证明:若AB=AC,且A,则B=C.证明:(1)对于任意〈a,b〉∈,其中a∈A,b∈,因为AB=AC,ABB必有〈a,b〉∈AC,其中b∈C,因此BC。(2)同理,对于任意〈a,c〉∈AC,其中a∈A,c∈C,因为AB=AC,必有〈a,c〉∈AB,其中c∈,因此C。BB由(1)、(2)得:B=C.2.试证明:若R与S是集合A上的自反关系,则R∩S也是集合A上的自反关系.证明:若R与S是集合A上的自反关系,则任意?x∈A,<x,x>∈R,<x,x>∈S,8从而<x,x>∈R∩S,注意x是A的任意元素,所以?R∩S也是集合A上的自反关系。k3.设连通图G有k个奇数度的结点,证明在图G中至少要添加?条边才能使其成为欧拉图.证明:由定理3.1.2,任何图中度数为奇数的结点必是偶数,可知k是偶数.又根据定理4.1.1的推论,图G是欧拉图的充分必要条件是图G不含奇数度结点.因此只要在每对奇数度结点之间各加一条边,使图G的所有结点的度数变为偶数,成为欧拉图.故最少要加k条边到图G才能使其成为欧拉图.24.试证明?(P?(Q?R))?PQ与?(P?Q)等价.5.试证明:?(A∧?B)∧(?B∨C)∧?C?A.910
全文预览
