離散數學試題及答案

百度文庫-讓每個人平等地提升自我百度文庫-讓每個人平等地提升自我一、填空題1設集合A,B,其中A={1,2,3},B={1,2},則A-B=； (A)-(B)=. \.設有限集合A,|A|=n,則|(A>A)|=..設集合A={a,b},B={1,2},則從A至UB的所有映射是1,其中雙射的是.\.已知命題公式G=(PQ)AR,則G的主析取范式是.6設A、B為兩個集合，A={1,2,4},B={3,4},則從AB=；AB=;A-B=. \.設R是集合A上的等價關系，則R所具有的關系的三個特性是,.設命題公式G=(P(QR)),則使公式G為真的解釋有.設集合A={1,2,3,4},A上的關系R1={(1,4),(2,3),(3,2)},R2={(2,1),(3,2),(4,3)},則R1?R2=,R2?R1=,R12=..設有限集A,B,冏=m,|B|=n,則||(AB)|=.設A,B,R是三個集合，其中R是實數集，A={x|-1<x<1,xR},B={x|0<x<2,xR},則A-B=,B-A=,APB=,..設集合A={2,3,4,5,6},R是A上的整除，則R以集合形式(列舉法)記為..設一階邏輯公式G=xP(x)xQ(x),則G的前束范式是.設謂詞的定義域為{a,b},將表達式 xR(x)-xS(x)中量詞消除，寫成與之對應的命題公式是..設集合A={1,2,3,4},A上的二元關系R={(1,1),(1,2),(2,3)},S={(1,3),(2,3),(3,2)}。則RS=,R2=.

、選擇題1設集合A={2,{a},3,4},B={{a},3,4,1},E為全集，則下列命題正確的是( )。(A){2}A(B){a}A(C) {{a}}BE(D){{a},1,3,4}B.2設集合A={1,2,3},A上的關系R={(1,1),(2,2),(2,3),(3,2),(3,3)}，則R不具備( ).(A)自反性 (B)傳遞性/ (C)對稱性\ (D)反對稱性設半序集(A,w)設半序集(A,w)關系w的哈斯圖如下所示，若A的子集B={2,3,4,5},則元素6為B的(D)xyP(x,y).11下列關于集合的表示中正確的為 ((D)xyP(x,y).11下列關于集合的表示中正確的為 ((A){a}{a,b,c} (B){a}{a,b,c}12命題xG(x)取真值1的充分必要條子(A)對任意x,G(x)都取真值1.(C)有某些x,使G(x0)取真值1.13.設G是連通平面圖，有5個頂點，(A)9條(B)5條(C)6條0111一，一…… 101015.設圖G的相鄰矩陣為，，八，110110101011(A)4,5 (B)5,6 (C)4,1三、計算證明題)。{a,b,c} (D){a,b}{a,b,c}是().(B)有一個x。，使G(x0)取真值1.(D)以上答案都不對.6個面，則G的邊數是( ).11條.10,則G的頂點數與邊數分別為(/).1100 (D)5,8.TOC\o"1-5"\h\z( )。(A)下界 (B)上界 (C)最小上界 (D)以上答案都不對4下列語句中，(/)是命題。(A)請把門關上 (B)地球外的星球上也有人 \(C)x+5>6 (D)下午有會嗎？5設I5設I是如下一個解釋:D={a,b},10 10則在解釋I下取真值為1的公式是( ).(A)xyP(x,y)(B)xyP(x,y)(C)xP(x,x).若供選擇答案中的數值表示一個簡單圖中各個頂點的度，能畫出圖的是( ).(A)(1,2,2,3,4,5) (B)(1,2,3,4,5,5) (C)(1,1,1,2,3) (D)(2,3,3,4,5,6)..設G、H是一階邏輯公式，P是一個謂詞，G=xP(x),H=xP(x)，則一階邏輯公式GH是().(A)恒真白(B)恒假的 (C)可滿足的 (D)前束范式.設命題公式G=(PQ),H=P(QP),則G與H的關系是( )。(A)GH(B)HG(C)G=H(D)以上都不是.9設A,B為集合，當( )時人一B=B.(A)A=B(B)AB(C)BA(D)A=B=.10設集合A={1,2,3,4},A上的關系R={(1,1),(2,3),(2,4),(3,4)},則R具有( )。(A)自反性 (B)傳遞性 (C)對稱性 (D)以上答案都不對.設集合A={1,2,3,4,6,8,9,12},R為整除關系。(1)畫出半序集(A,R)的哈斯圖；(2)寫出A的子集B={3,6,9,12}的上界，下界，最小上界，最大下界;

(3)寫出A的最大元，最小元，極大元，極小元。.設集合A={1,2,3,4},A上的關系R={(x,y)|x,yA且xy},求TOC\o"1-5"\h\z(1)畫出R的關系圖； / \(2)寫出R的關系矩陣. / \.設R是實數集合，,,是R上的三個映射， (x)=x+3,(x)=2x,(x)=x/4,試求復合映射？，？，？，？，？？. \.設I是如下一個解釋：D={2,3}, \a bf(2)f(3) P(2,2) P(2,3) P(3,2) P(3,3)3 2 3 2 0 0 1 1試求(1)P(a,f(a))AP(b,f(b)); \xyP(y,x)..設集合人={1,2,4,6,8,12},R為A上整除關系。 \(1)畫出半序集(A,R)的哈斯圖； \(2)寫出A的最大元，最小元，極大元，極小元；(3)寫出A的子集B={4,6,8,12}的上界，下界，最小上界，最大下界 ..設命題公式G=(P-Q)V(QA(P-R)),求G的主析取范式。.(9分)設一階邏輯公式：G=(xP(x)VyQ(y))一xR(x),把G化成前束范式..設R是集合A={a,b,c,d}.R是A上的二元關系,R={(a,b),(b,a),(b,c),(c,d)},(1)求出r(R),s(R),t(R);(2)畫出r(R),s(R),t(R)的關系圖.11.通過求主析取范式判斷下列命題公式是否等價：G=(PAQ)V(PAQAR)H=(PV(QAR))A(QV(PAR))13.設R和S是集合A={a,b,c,d}上的關系,其中R={(a,a),(a,c),(b,c),(c,d)},S={(a,b),(b,c),(b,d),(d,d)}.(1)試寫出R和S的關系矩陣； /(2)計算R?S,RUS,R1,S1?R1.四、證明題\、參考答案 /一、填空題1.{3}; {{3},{1,3},{2,3},{1,2,3}}.2.2n2.2n21={(a,1),(b,1)}, 2={(a,2),(b,2)},3={(a,1),(b,2)}, 4={(a,2),(b,1)}; 3,4.(PAQAR).

12,3.{4},{1,2,3,4},{1,2}.自反性；對稱性；傳遞性.(1,0,0),(1,0,1),(1,1,0).{(1,3),(2,2),(3,1)};{(2,4),(3,3),(4,2)};{(2,2),(3,3)}.10.2mn{x|-1<x<0,xR}；{x|1<x<2,xR}；{x|0<x<1,xR}.12;6.{(2,2),(2,4),(2,6),(3,3),(3,6),(4,4),(5,5),(6,6)}.x(P(x)VQ(x)).21.(R(a)AR(b))一(S(a)VS(b)).{(1,3),(2,2)};{(1,1),(1,2),(1,3)}.二、選擇題1. C. 2. D. 3. B. 4.B.5. D. 6. C. 7. C.8.A.9.D.10.B.11.B.13.A.14.A.15.D三、計算證明題(2)B無上界「也無最小上界。(2)B無上界「也無最小上界。下界1,3;最大下界是3.⑶A無最大兀，最小兀是 1,極大兀8,12,90+;極小兀是1.={(1,1),(2,1),(2,2),(3,1),(3,2),(3,3),(4,1),(4,2),(4,3),(4,4)}.10111011(2)Mr1111001011(1)?=((x))=(x)+3=2x+3=2x+3.?=((x))=(x)+3=(x+3)+3=x+6,?=((x))=(x)+3=x/4+3,?=((x))=(x)/4=2x/4=x/2,??=?(?)=?+3=2x/4+3=x/2+3.(1)P(a,f(a))AP(b,f(b))=P(3,f(3))AP(2,f(2))=P(3,2)AP(2,3)=1A0=0.xyP(y,x)=x(P(2,x)VP(3,x))=(P(2,2)VP(3,2))A(P(2,3)VP(3,3))=(0V1)A(0V1)=1.(1)(2)無最大(3)B無上元，最小元1,極大元,8,12;極小元是1.界，無最小上界。下界1,2;最大下界2.G= (P-Q)V(QA(PfR))=(PVQ)V(QA(PVR))=(PAQ)V(QA(PVR))=(PAQ)V(QAP)V(QAR)

PAQAR)TOC\o"1-5"\h\z=(PA QAR)V(PA QA R)V(PAQAR)V(PAQA R)V(PAQAR)V (PAQAR)=(PA QA R)V(PA QA R)V(PAQAR)V(PAQA R)V(PAQAR)=m3Vm4Vm5Vm6Vm7=(3,4,5,6,7).G=(xP(x)VyQ(y))一xR(x) \=(xP(x)VyQ(y))VxR(x) \=(xP(x)AzyQ(y))VxR(x) 、=(xP(x)AyQ(y))VzR(z) \=八yz((P(x)AQ(y))VR(z)) \9.(1)r(R)=RUlA={(a,b),(b,a),(b,c),(c,d),(a,a),(b,b),(c,c),(d,d)},s(R)=RUR1={(a,b),(b,a),(b,c),(c,b)(c,d),(d,c)},t(R)=RUR2UR3UR4={(a,a),(a,b),(a,c),(a,d),(b,a),(b,b),(b,c),(b,d),(c,d)}(2)關系圖：r(R) s(R) t(R)r(R) s(R) t(R)11.G=(PAQ)V(PAQAR)\=(PAQAR)V(PAQAR)V(PAQAR)=m6Vm7Vm3=(3,6,7)H=(PV(QAR))A(QV(PAR))=(PAQ)V(QAR))V(PAQAR)=(PAQAR)V(PAQAR)V(PAQAR)V(PAQAR)V(PAQAR)=(PAQAR)V(PAQAR)V(PAQAR) /=m6Vm3Vm7=(3,6,7)G,H的主析取范式相同，所以 G=H.1010 0100013.⑴Mr c00 1 0 0 0 1 1Ms0 0 1 0 0 0 00000 0001(2)R?S={(a,b),(c,d)},RUS={(a,a),(a,b),(a,c),(b,c),(b,d),(c,d),(d,d)},R1={(a,a),(c,a),(c,b),(d,c)},S1?R1={(b,a),(d,c)}.四證明題 \.設A,B為任意集合，證明：(A-B)-C=A-(BUC)..(本題10分)利用形式演繹法證明：{AVB