离散数学形成性考核作业4

离散数学形成性考核作业4R={(x,y)|x,y∈A且x|y}(2)哈斯图见附图(3)B的最大元为6，最小元为2。离散数学综合练习书面作业本次作业要求学生提交作业的方式有三种：手工书写、在线提交Word文档或手写并拍照上传。要求手写答案字迹工整，解答题要有解答过程。一、公式翻译题1.小王去上课，小李也去上课。翻译成命题公式为P^Q，其中P表示小王去上课，Q表示小李去上课。2.他去旅游，仅当他有时间。翻译成命题公式为P→Q，其中P表示他去旅游，Q表示他有时间。3.有人不去工作。翻译成谓词公式为∃x(A(x)^¬B(x))，其中A(x)表示x是人，B(x)表示x去工作。4.所有人都努力学习。翻译成谓词公式为∀x(A(x)→B(x))，其中A(x)表示x是人，B(x)表示x努力学习。二、计算题1.设A={{1},{2},1,2}，B={1,2,{1,2}}，求(1)AB；(2)A∩B；(3)A×B。解：(1)AB={{1},{2}}；(2)A∩B={1,2}；(3)A×B包含12个元素。2.设A={1,2,3,4,5}，R={<x,y>|xA，yA且x+y4}，S={<x,y>|xA，yA且x+y<0}，求R，S，RS，SR，R-1，S-1，r(S)，s(R)。解：(1)R={<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<3,1>}；(2)S=Φ；(3)RS=Φ，SR=Φ；(4)R-1={<1,1>,<2,1>,<3,1>,<1,2>,<2,2>,<1,3>}；(5)S-1=Φ；(6)r(S)={<1,1>,<2,2>,<3,3>,<4,4>,<5,5>}；(7)s(R)={<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<3,1>}。3.设A={1,2,3,4,5,6,7,8}，R是A上的整除关系，B={2,4,6}，求：(1)关系R的表示式；(2)关系R的哈斯图；(3)集合B的最大元、最小元。解：(1)R={(x,y)|x,y∈A且x|y}；(2)关系R的哈斯图见附图；(3)B的最大元为6，最小元为2。2.给定关系R={<1,1>,<1,2>,<1,3>,<1,4>,<1,5>,<1,6>,<1,7>,<1,8>,<2,2>,<2,4>,<2,6>,<2,8>,<3,3>,<3,6>,<4,4>,<4,8>,<5,5>,<6,6>,<7,7>,<8,8>}，画出其哈斯图。3.给定集合B，没有最大元，最小元是2。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.求PQR的析取范式、合取范式、主析取范式和主合取范式。答案：P(Q∨R)的否定形式为┐P(Q∨R)=┐P∨┐(Q∨R)=┐P∨┐Q∧┐R，因此析取范式为P∨Q∨R，合取范式为┐PQ∨R，主析取范式为PQR，主合取范式为┐PQ∨R。8.设谓词公式(∃x)(P(x,y)→(∀z)Q(y,x,z))∧(∀y)R(y,z)。（1）写出量词的辖域；（2）指出该公式的自由变元和约束变元。答案：（1）量词x的辖域为P(x,y)→(∀z)Q(y,x,z)，量词z的辖域为Q(y,x,z)，量词y的辖域为R(y,z)。（2）P(x,y)中的x是约束变元，y是自由变元；Q(y,x,z)中的x和z是约束变元，y是自由变元；R(y,z)中的x是自由变元，y是约束变元。9.设个体域为D={a1,a2}，求谓词公式(y)(x)P(x,y)消去量词后的等值式。答案：(y)(x)P(x,y)可以消去量词得到P(a1,a1)∧P(a2,a1)∧P(a1,a2)∧P(a2,a2)，即xP(x,a1)∧xP(x,a2)的合取式。证明题：1.对任意三个集合A、B和C，若AB=AC且A≠∅，则B=C。证明：设x∈A，y∈B，则(x,y)∈AB=AC，因此y∈C。同理，设z∈C，则(x,z)∈AC=AB，因此z∈B。因此，B=C，证毕。2.若R与S是集合A上的自反关系，则R∩S也是集合A上的自反关系。证明：由自反关系的定义可知，对于任意x∈A，都有(x,x)∈R和(x,x)∈S。因此，对于任意x∈A，都有(x,x)∈R∩S，即R∩S是自反的，证毕。3.设连通图G有k个奇数度的结点，证明在图G中至少要添加k/2条边才能使其变为欧拉图。证明：由定理推论可知，度数为奇数的结点必为偶数个，因此k为偶数。对于每对奇数度结点，都需要添加一条边才能使它们的度数变为偶数。因此，至少需要添加k/2条边才能使所有结点的度数变为偶数，从而使图G成为欧拉图，证毕。4.证明(P(QR))PQ与(PQ)等价。证明：(P(QR))PQ=((P∧(Q∨R))∧P∧Q)=((P∧Q)∨(P∧R))∧P∧Q//分配律=(P∧Q)∨(P∧R)∧P∧Q//吸收律=(P∧Q)∧(P∧Q∨R)//分配律=(P∧Q)//同一律因此，(P(QR))PQ与(PQ)等价，证毕。试证明(PQ)（摩根律）：(A∧B)∧(B∨C)∧C证明过程如下：1.前提引入：假设(A∧B)∧(B∨C)∧C成立。2.前提引入：假设~P，即P的否定成立。3.由前提1可知，A∧B成立，因此A和B都成立。4.由前提1可知，B∨C成立，因此B或C至少有一个成立。5.由前提1可知，C成立。6.由前提2可知，~P成立，因此P不成立。7.根据摩根律，可得到~(A∧~B)，即~A∨B成立。8.根据前提3和前提7，可得到B成立。9.由前提4和前提8可得到~B不成立