2019中央电大历年试题+答案2002—(计算题).doc

PAGE 16 - 四、计算题 解： 14．求谓词公式的前束范式． 15．已知图的结点集V＝{a,b,c,d}以及图G和图D的边集合分别为： E(G)＝{(a,a), (a,b), (b,c), (a,c)} E(G)＝{a，b，a，c，c，a，c，b} 试作图G和图D，写出各结点的度数，回答图G、图D是简单图还是多重图? 图D是简单图 16．设集合A＝{l，2，3}，P(A)是A的幂集合，是集合的对称差运算，求运算在 P(A)上的单位元．x ∈P (A)，求x关于运算的逆元．并解方程{1，2}y＝{1}． 17．化简布尔代数式(a∧b)V(a∧b∧c)V(b∧c)V(aVc)． 理由． 14．列命题公式(P∨Q)→R的真值表，并给出该公式的成假赋值． 做真值表． 公式为假的赋值是(0，l，0)，(1，0，0)，(1，1，0) 16．设图G(如图2所示)是6个结点a,b.c,d,e,f的图，试求图G的最小生成树，并计算 它的权． 16．构造连通无圈的图，即最小生成树，用克鲁斯克尔算 法： 第一步：取db=;第二步：取af=4 第三步：取fe=3；第四步：取ad=9 第五步：取bc＝23 如附图1．权为1+4+3+9+23=40 17．设T是有5片树叶的二元正则树，那末T有多少条边． 解：设T有n个顶点，则有n-1条边，T中有5个1度顶点，1个根为2度顶点，其余n- 5-1个3度顶点 由握手定理 5+2+3(n-5-1)=2(n-1) 解得n=9;于是T有8条边 五．计算题（每小题12分，本题共36分）? ? 15．求（P∨Q）→R的析取范式与合取范式． （P∨Q）∨R?? ?15．（P∨Q）→R ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （4分）Q)∨R? （析取范式）??P∧? (?? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （8分）Q∨R)? （合取范式）? ? ? ? ? ??P∨R)∧(? (?? ? ? ? ? ? ? ? ? ? ? ? （12分）? ? 16．设A={0，1，2，3}，R={x，yA且x+y?A，y?|x0}，S={x，y2}，试求R，S，R?S，S?A且x+y?A，y?|x -1，r(R)． ,??16．R= S={0,0,0,1,0,2,1,0,1,1,2,0}? ? ? ? ? ? ? ? ? ? ? （3分），? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??? ? R?S= ? ? ? ? ? ? ? （6分）S -1= S，? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （9分）r(R)=IA={0,0,1,1,2,2,3,3}．? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （12分）17．画一棵带权为1, 2, 2, 3, 4的最优二叉树,计算它们的权．17．最优二叉树如图三所示 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （10分）? ? ? ? ? ? ? ? ? ? ? ? ? 图三2=27? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??2+4?2+3?3+2?3+2?权为1 （12分）16．试求出 (P∨Q)→R的析取范式，合取范式，主合取范式. 16．(P∨Q)→R ??(P∨Q)∨R?(?P∧?Q)∨R　　　　　析取范式 (3分) ?(?P∨R)∧(?Q∨R) 合取范式 (6分) ?((?P∨R)∨(Q∧?Q))∧((?Q∨R)∨(P∧?P)) ?(?P∨R∨Q)∧(?P∨R∨?Q)∧(?Q∨R∨P)∧(?Q∨R∨?P) ?(?P∨Q∨R)∧(?P∨?Q∨R)∧(P∨?Q∨R) 主合取范式 (12分) 17. 设A={{a, b}, 1, 2}，B={a, b, {1}, 1}，试计算 （1）（A－B）; （2）（A∪B）; （3）( A∪B)－(A∩B). 17．（1）(A－B)={{a, b}, 2} (4分) （2）(A∪B)={{a, b}, 1, 2, a, b, {1}} (8分) （3）( A∪B)－(A∩B)= {{a, b}