離散數(shù)學(xué)形成性考核作業(yè)4

離散數(shù)學(xué)形成性考核作業(yè)4R={(x,y)|x,y∈A且x|y}(2)哈斯圖見附圖(3)B的最大元為6，最小元為2。離散數(shù)學(xué)綜合練習(xí)書面作業(yè)本次作業(yè)要求學(xué)生提交作業(yè)的方式有三種：手工書寫、在線提交Word文檔或手寫并拍照上傳。要求手寫答案字跡工整，解答題要有解答過(guò)程。一、公式翻譯題1.小王去上課，小李也去上課。翻譯成命題公式為P^Q，其中P表示小王去上課，Q表示小李去上課。2.他去旅游，僅當(dāng)他有時(shí)間。翻譯成命題公式為P→Q，其中P表示他去旅游，Q表示他有時(shí)間。3.有人不去工作。翻譯成謂詞公式為?x(A(x)^?B(x))，其中A(x)表示x是人，B(x)表示x去工作。4.所有人都努力學(xué)習(xí)。翻譯成謂詞公式為?x(A(x)→B(x))，其中A(x)表示x是人，B(x)表示x努力學(xué)習(xí)。二、計(jì)算題1.設(shè)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個(gè)元素。2.設(shè)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.設(shè)A={1,2,3,4,5,6,7,8}，R是A上的整除關(guān)系，B={2,4,6}，求：(1)關(guān)系R的表示式；(2)關(guān)系R的哈斯圖；(3)集合B的最大元、最小元。解：(1)R={(x,y)|x,y∈A且x|y}；(2)關(guān)系R的哈斯圖見附圖；(3)B的最大元為6，最小元為2。2.給定關(guān)系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.設(shè)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）求出每個(gè)結(jié)點(diǎn)的度數(shù)；（4）畫出其補(bǔ)圖的圖形。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)}，對(duì)應(yīng)邊的權(quán)值依次為2、1、2、3、6、1、4及5，試：（1）畫出G的圖形；（2）寫出G的鄰接矩陣；（3）求出G權(quán)最小的生成樹及其權(quán)值。6.給定一組權(quán)為2,3,5,7,17,31的節(jié)點(diǎn)，畫出相應(yīng)的最優(yōu)二叉樹，并計(jì)算其權(quán)。7.求PQR的析取范式、合取范式、主析取范式和主合取范式。答案：P(Q∨R)的否定形式為┐P(Q∨R)=┐P∨┐(Q∨R)=┐P∨┐Q∧┐R，因此析取范式為P∨Q∨R，合取范式為┐PQ∨R，主析取范式為PQR，主合取范式為┐PQ∨R。8.設(shè)謂詞公式(?x)(P(x,y)→(?z)Q(y,x,z))∧(?y)R(y,z)。（1）寫出量詞的轄域；（2）指出該公式的自由變?cè)图s束變?cè)?。答案：?）量詞x的轄域?yàn)镻(x,y)→(?z)Q(y,x,z)，量詞z的轄域?yàn)镼(y,x,z)，量詞y的轄域?yàn)镽(y,z)。（2）P(x,y)中的x是約束變?cè)?，y是自由變?cè)籕(y,x,z)中的x和z是約束變?cè)?，y是自由變?cè)?；R(y,z)中的x是自由變?cè)瑈是約束變?cè)?.設(shè)個(gè)體域?yàn)镈={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.對(duì)任意三個(gè)集合A、B和C，若AB=AC且A≠?，則B=C。證明：設(shè)x∈A，y∈B，則(x,y)∈AB=AC，因此y∈C。同理，設(shè)z∈C，則(x,z)∈AC=AB，因此z∈B。因此，B=C，證畢。2.若R與S是集合A上的自反關(guān)系，則R∩S也是集合A上的自反關(guān)系。證明：由自反關(guān)系的定義可知，對(duì)于任意x∈A，都有(x,x)∈R和(x,x)∈S。因此，對(duì)于任意x∈A，都有(x,x)∈R∩S，即R∩S是自反的，證畢。3.設(shè)連通圖G有k個(gè)奇數(shù)度的結(jié)點(diǎn)，證明在圖G中至少要添加k/2條邊才能使其變?yōu)闅W拉圖。證明：由定理推論可知，度數(shù)為奇數(shù)的結(jié)點(diǎn)必為偶數(shù)個(gè)，因此k為偶數(shù)。對(duì)于每對(duì)奇數(shù)度結(jié)點(diǎn)，都需要添加一條邊才能使它們的度數(shù)變?yōu)榕紨?shù)。因此，至少需要添加k/2條邊才能使所有結(jié)點(diǎn)的度數(shù)變?yōu)榕紨?shù)，從而使圖G成為歐拉圖，證畢。4.證明(P(QR))PQ與(PQ)等價(jià)。證明：(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)等價(jià)，證畢。試證明(PQ)（摩根律）：(A∧B)∧(B∨C)∧C證明過(guò)程如下：1.前提引入：假設(shè)(A∧B)∧(B∨C)∧C成立。2.前提引入：假設(shè)~P，即P的否定成立。3.由前提1可知，A∧B成立，因此A和B都成立。4.由前提1可知，B∨C成立，因此B或C至少有一個(gè)成立。5.由前提1可知，C成立。6.由前提2可知，~P成立，因此P不成立。7.根據(jù)摩根律，可得到~(A∧~B)，即~A∨B成立。8.根據(jù)前提3和前提7，可得到B成立。9.由前提4和前提8可得到~B不成立