《離散數(shù)學(xué)》大題

三、計算證明題1.設(shè)集合A＝{1,2,3,4,6,8,9,12}，R為整除關(guān)系。畫出半序集(A,R)的哈斯圖；寫出A的子集B={3,6,9,12}的上界，下界，最小上界，最大下界；寫出A的最大元，最小元，極大元，極小元。設(shè)集合A＝{1,2,3,4}，A上的關(guān)系R＝{(x,y)|x,yA且xy},求 畫出R的關(guān)系圖；寫出R的關(guān)系矩陣.設(shè)R是實數(shù)集合，,,是R上的三個映射，(x)=x+3,(x)=2x,(x)＝x/4,試求復(fù)合映射?，?,?,?，??.4.設(shè)I是如下一個解釋：D={2,3},abf(2)f(3)P(2,2)P(2,3)P(3,2)P(3,3)32320011試求(1)P(a,f(a))∧P(b,f(b));(2)xyP(y,x).5.設(shè)集合A＝{1,2,4,6,8,12}，R為A上整除關(guān)系。畫出半序集(A,R)的哈斯圖；寫出A的最大元，最小元，極大元，極小元；寫出A的子集B={4,6,8,12}的上界，下界，最小上界，最大下界.6.設(shè)命題公式G=(P→Q)∨(Q∧(P→R)),求G的主析取范式。7.(9分)設(shè)一階邏輯公式：G=(xP(x)∨yQ(y))→xR(x)，把G化成前束范式.8.對于下面二叉樹的點，求先根遍歷次序、中根遍歷次序、后根遍歷次序。9.設(shè)R是集合A={a,b,c,d}.R是A上的二元關(guān)系,R={(a,b),(b,a),(b,c),(c,d)},求出r(R),s(R),t(R)；畫出r(R),s(R),t(R)的關(guān)系圖.10.試用克魯斯卡爾算法求出如下權(quán)圖的最優(yōu)支撐樹。11.通過求主析取范式判斷下列命題公式是否等價：(1)G=(P∧Q)∨(P∧Q∧R)(2)H=(P∨(Q∧R))∧(Q∨(P∧R))12.用迪克斯特拉算法求下面有限權(quán)圖中從A到B的最短路(要求用圖示給出求解過程)，并計算它們的權(quán)值。13.設(shè)R和S是集合A＝{a,b,c,d}上的關(guān)系，其中R＝{(a,a),(a,c),(b,c),(c,d)}, S＝{(a,b),(b,c),(b,d),(d,d)}.(1)試寫出R和S的關(guān)系矩陣；(2)計算R?S,R∪S,R－1,S－1?R－1.四、證明題1.利用形式演繹法證明：{P→Q,R→S,P∨R}蘊涵Q∨S。2.設(shè)A,B為任意集合，證明：(A-B)-C=A-(B∪C).3.(本題10分)利用形式演繹法證明：{A∨B,C→B,C→D}蘊涵A→D。4.(本題10分)A,B為兩個任意集合，求證：A－(A∩B)=(A∪B)－B.參考答案三、計算證明題1.(1)(2)B無上界，也無最小上界。下界1,3;最大下界是3.(3)A無最大元，最小元是1，極大元8,12,90+;極小元是1.2.R={(1,1),(2,1),(2,2),(3,1),(3,2),(3,3),(4,1),(4,2),(4,3),(4,4)}.(1)(2)3.(1)?＝((x))＝(x)+3＝2x+3＝2x+3.(2)?＝((x))＝(x)+3＝(x+3)+3＝x+6,(3)?＝((x))＝(x)+3＝x/4+3,(4)?＝((x))＝(x)/4＝2x/4=x/2,(5)??＝?(?)＝?+3＝2x/4+3＝x/2+3.4.(1)P(a,f(a))∧P(b,f(b))=P(3,f(3))∧P(2,f(2)) =P(3,2)∧P(2,3) =1∧0 =0.(2)xyP(y,x)=x(P(2,x)∨P(3,x)) =(P(2,2)∨P(3,2))∧(P(2,3)∨P(3,3)) =(0∨1)∧(0∨1) =1∧1 =1.5.(1)(2)無最大元，最小元1，極大元8,12;極小元是1.(3)B無上界，無最小上界。下界1,2;最大下界2.6.G=(P→Q)∨(Q∧(P→R)) =(P∨Q)∨(Q∧(P∨R)) =(P∧Q)∨(Q∧(P∨R)) =(P∧Q)∨(Q∧P)∨(Q∧R) =(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R) =(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R) =m3∨m4∨m5∨m6∨m7=(3,4,5,6,7).7.G=(xP(x)∨yQ(y))→xR(x) =(xP(x)∨yQ(y))∨xR(x) =(xP(x)∧yQ(y))∨xR(x) =(xP(x)∧yQ(y))∨zR(z) =xyz((P(x)∧Q(y))∨R(z))8.先根遍歷次序：ABDFIJGKMCEHL；中根遍歷次序：IFJDGKMBACEHL;后根遍歷次序：IJFMKGDBLHECA.9.(1)r(R)＝R∪IA＝{(a,b),(b,a),(b,c),(c,d),(a,a),(b,b),(c,c),(d,d)},s(R)＝R∪R－1＝{(a,b),(b,a),(b,c),(c,b)(c,d),(d,c)},t(R)＝R∪R2∪R3∪R4＝{(a,a),(a,b),(a,c),(a,d),(b,a),(b,b),(b,c),(b,d),(c,d)}；(2)關(guān)系圖:10、權(quán)為19.11.G＝(P∧Q)∨(P∧Q∧R)＝(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)＝m6∨m7∨m3＝(3,6,7)H=(P∨(Q∧R))∧(Q∨(P∧R))＝(P∧Q)∨(Q∧R))∨(P∧Q∧R)＝(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)＝(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)＝m6∨m3∨m7＝(3,6,7)G,H的主析取范式相同，所以G=H.12.最短路:AGED,最短路的權(quán)值和為7.13.(1)(2)R?S＝{(a,b),(c,d)},R∪S＝{(a,a),(a,b),(a,c),(b,c),(b,d),(c,d),(d,d)},R－1＝{(a,a),(c,a),(c,b),(d,c)},S－1?R－1＝{(b,a),(d,c)}.四證明題1.證明：{P→Q,R→S,P∨R}蘊涵Q∨S(1)P∨R P(2)R→P Q(1)(3)P→Q P(4)R→Q Q(2)(3)(5)Q→R Q(4)(6)R→S P(7)Q→S Q(5)(6)(8)Q∨S Q(7)2.證明：(A-B)-C=(A∩~B)∩~C =A∩(~B∩~C) =A∩~(B∪C) =A-(B∪C)3. 證明：{A∨B,C→B,C→D}蘊涵A→D(1)A D(附加)(2)A∨B P(3)B Q(1)(2)(4)C→B P(5)B→C Q(4)(6)C Q(3)(5)(7)C→D P(8)D Q(6)(7)(9)A→D D(1)(