离散1 课后习题答案VIP专享VIP免费

离散1一、选择题（每题2分，共20分）CABBBDACDA二、填空题（每题2分，共20分）1.2.a∨b=1，a∧b=03.x*(xΔy)=xxΔ(x*y)=x4.无回路5.大项的合取所组成6.($x)ØP(x)("x)ØP(x)7.68.对任意的a,b,有(a*b)*(a*b)=(a*a)*(b*b)9.βγ10.{<1，2>，<3，3>,<1，3>，<4，2>}，{<1,4>,<2,2>}三、判断题（每题1分，共10分）×√√×××××√√四、解答题（5小题，共30分）1.(5分）给定无孤立点图G，若存在一条路，经过图中每边一次且仅一次，该条路称为欧拉路；如果一个图有欧拉路，则这个图能一笔画出。2.（8分）各4分，步骤对，结果错，适当扣分，如果求出其一个，另一个直接写出，也不扣分。只有结果，且结果对，给一半分，只有结果，且结果错，不给分。解：主析取范式:(┐P∧┐Q∧R)∨(┐P∧┐Q∧┐R)∨(P∧Q∧R)∨(P∧┐Q∧R)∨(┐P∧Q∧R)主合取范式:（┐P∨Q∨R）∧（┐P∨┐Q∨R）∧（P∨┐Q∨R）3.（5分）由无向树的性质可知，无向树的顶点数是边数加1，又知无向图所有顶点的度之和为边数的2倍。（1分）令1度顶点个数为x,则顶点数为2+1+3+x，所有顶点的度之和为x+2*2+3+3*4，（2分）从而有x+2*2+3+3*4=2*(2+1+3+x-1)，解之得x=9,即有9个1度的点。（2分）4.（7分）解：5.（5分）（2分）,（2分）,具有自反，对称性质（1分）五、证明（3小题，共20分）1.（10分）每步约1分，没有P,T标识扣3分,没有序号扣3分。证明过程：（1）P→RP（2）R→PT（1）E（3）PQP（4）P→QT（3）E（5）Q→SP（6）P→ST（4）（5）I（7）R→ST（2）（6）I（8）RST（8）E2.（5分）。证明：(A－B)(A－C)=(A~B)(A~C)=A(~B~C)=A~(BC)=A－(BC)3.（5分）证明过程：明显，H是G的子集。任取xH,则有a*x=x*a，对等式左乘和右乘x-1,有x-1*a=a*x-1.再任取yH,则(y*x-1)*a=y*(x-1*a)=y*(a*x-1)=(y*a*)x-1=(a*y)*x-1=a*(y*x-1)由定理可得，H是G的子群。或由群的定义来证明。离散2一、选择题（每题2分，共20分）BCCADAABDC二、填空题（每题2分，共20分）1.(1)PQ(2)(┐P∨Q)∧(P∨┐Q)或（(┐P∧┐Q)∨(P∧Q)等）2.自反，反对称，传递3.（）4.经过图中每边一次且仅一次5.上确界6.MaxMin+可结合性YYY可交换性YYY存在幺元NNN存在零元NNY7.至少有两个元素的有补分配格8.小项的析取所组成9.x|(xÎA)Ù(xÎB)10.简单图中若每一对结点间都有边相连三、判断题（每题1分，共10分）××√√×√√××√四、解答题（3小题，共20分）1.（5分）在根树中，若每一个结点的出度小于或等于2，则这棵树称为2叉树。任何一棵有序树都可以改写为对应的二叉树，方法是：⑴除了最左边的分枝点外，删去所有从每一结点长出的分枝。在同一层次中，兄弟结点间用从左到右的有向边连接。⑵选定二叉树的左儿子和右儿子如下：直接处于给定结点下面的结点，作为左儿子，对于同一水平线上给定结点右邻结点，作为右儿子，以此类推。2．（8分）各4分，步骤对，结果错，适当扣分，如果求出其一个，另一个直接写出，也不扣分。只有结果，且结果对，给一半分，只有结果，且结果错，不给分。解：主析取范式:（┐PQR）∨（┐P┐QR）∨（PQR）主合取范式:（┐P∨Q∨R）（┐P∨Q∨┐R）（P∨Q∨R）（P∨┐Q∨R）（┐P∨┐Q∨R）3.（7分）这是一个求最小生成树的问题，可用多种方法，但必须有思路和过程。解：按该图的生成树建立通讯线路能使城市间直接通讯，按最小生成树建立通讯线路能使城市间直接通讯且总造价最小。（1分）通讯方案（最小生成树）：（5分）最小总造价为：57（1分）五、证明（3小题，共30分）4.（10分）每步约1分，没有P,T标识扣3分,没有序号扣3分。证明过程：（1）P→QP（2）QRP（3）Q→RT(2)E（4）P→RT(1)（3）I（5）RP（6）PT（4）（5）I（7）SPP（8）ST(6)（7）I5.（10分）证明过程：证明：因为R和S都是非空集A上的等价关系，所以R和S都有自反性，对称性和传递性。（1分）（1）,则,所以,所以RS是自反的。（2分）（2），则，因为R和S是对称的，所以（3分），从而,所以RS是对称的。（3），则，因为R和S是传递的，所以，从而,所以RS是传递的。（3分）由上面的三点可得RS是A上的等价关系。（1分）6.（6分）证明过程：如果图G(V,E)不连通的话，它的顶点可...