一、填空題1設(shè)集合A,B，其中A＝{1,2,3},B={1,2},則A-; (A)-(B)＝ .2.設(shè)有限集合A,|A|=n,則|(A×A)|= .設(shè)集合A=b},B={1,2},則從A到B的所有映射是 其中雙射的是 .已知命題公式G＝(PQ)∧R，則G的主析取范式是 .設(shè)G是完全二叉樹，G有7個(gè)點(diǎn)，其中4個(gè)葉點(diǎn)，則G的總度數(shù)為 ，分枝點(diǎn)數(shù)為 .6設(shè)A、B為兩個(gè)集合,A={1,2,4},B={3,4},則從AB＝ ; AB＝ ;A－B＝ .設(shè)R是集合A上的等價(jià)關(guān)系，則R所具有的關(guān)系的三個(gè)特性是 , , .設(shè)命題公式G＝(P(QR))，則使公式G為真的解釋有 ， , .9.A＝{1,2,3,4},AR1={(1,4),(2,3),(3,2)},R1={(2,1),(3,2),(4,3)},則R1R2=R1 ,R2R1= , 2R1= .10.設(shè)有限集A,B，|A|=m,|B|=n,則||(AB)|= .11設(shè)A,B,R是三個(gè)集合，其中R是實(shí)數(shù)集，A={x|-1≤x≤1,xR},B={x|0≤x<2,xR},則A-B= ,B-A= A∩B= ,.設(shè)集合A＝{2,3,4,5,6}，R是A上的整除，則R以集合形式(列舉法)記為 .設(shè)一階邏輯公式G=xP(x)xQ(x)，則G的前束范式是 .設(shè)G是具有8個(gè)頂點(diǎn)的樹，則G中增加 條邊才能把G變成完全圖。設(shè)謂詞的定義域?yàn)閧ab},xR(x)→xS(x)中量詞消除，寫成與之對應(yīng)的命題公式是 .17.設(shè)集合A＝{1,2,3,4}，A上的二元關(guān)系R＝{(1,1),(1,2),(2,3)},S＝{(1,3),(2,3),(3,2)}。則RS＝ ,R2＝ .二、選擇題1 設(shè)集合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 設(shè)集合A={1,2,3},A上的關(guān)系R＝{(1,1),(2,2),(2,3),(3,2),(3,3)}，則R不具備( ).

對稱性 (D)反對稱性653421設(shè)半序集(A,≤)關(guān)系≤的哈斯圖如下所示，若A的子集B={2,3,4,5},則元素6為653421下界

上界

最小上界 (D)以上答案都不對下列語句中，( )是命題。請把門關(guān)上 (B)地球外的星球上也有(C)x+5>6 (D)下午有會嗎？P(a,a)P(a,b)P(b,a)P(b,b)設(shè)I是如下一個(gè)解釋：D＝{a,b},

1 0 1 0則在解釋I下取真值為1的公式( ).(A)xyP(x,y) (B)xyP(x,y) (C)xP(x,x) (D)xyP(x,y).若供選擇答案中的數(shù)值表示一個(gè)簡單圖中各個(gè)頂點(diǎn)的度，能畫出圖的是( ).(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).設(shè)、H是一階邏輯公式，P是一個(gè)謂詞，G＝xP(x),H＝xP(x),則一階邏輯公式GH是( ).恒真的 (B)恒假的 (C)可滿足的 (D)前束范.設(shè)命題公式G＝(PQ)，H＝P(QP)，則G與H的關(guān)系是( )(A)GH (B)HG (C)G＝H (D)以上都不是.設(shè)A,B為集合，當(dāng)( )時(shí)A－B＝B.A＝B

AB

BA (D)A＝B＝.10 設(shè)集合A={1,2,3,4},A上的關(guān)系R＝{(1,1),(2,3),(2,4),(3,4)},則R具有( )。

對稱性 (D)以上答案都不對下列關(guān)于集合的表示中正確的( )。(A){a}{a,b,c} (B){a}{a,b,c}(C){a,b,c} (D){a,b}{a,b,c}命題xG(x)取真值1的充分必要條件是( ).對任意x，G(x)都取真值1. (B)有一個(gè)x0，使G(x0)取真值(C)有某些x，使G(x0)取真值1. (D)以上答案都不對.設(shè)G是連通平面圖，有5個(gè)頂點(diǎn)，6個(gè)面，則G的邊數(shù)是( (A)9條 (B)5條 (C)6條 (D)11條.設(shè)G是5個(gè)頂點(diǎn)的完全圖，則從G中刪去( )條邊可以得到(A)6 (B)5 (C)10 (D)4.01G的相鄰矩陣為111(A)4,5 (B)5,6三、計(jì)算證明題

1 1 1 10 1 0 0，則G的頂點(diǎn)數(shù)與邊數(shù)分別為( ).1 0 1 10 1 0 10 1 1 (C)4,10 (D)5,8.1.設(shè)集合A＝{1,2,3,4,6,8,9,12}，R為整除關(guān)系。畫出半序集(A,R)的哈斯圖；AB={3,6,9,12}的上界，下界，最小上界，最大下界；A的最大元，最小元，極大元，極小元。2. A＝{1,2,3,4}，AR＝{(x,y)|x,yA且xy},求R的關(guān)系圖；R的關(guān)系矩陣.3. RR=x+3,(x)=2x,(x)＝x/4,試求復(fù)合映射?,?，??.I是如下一個(gè)解釋：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的最大元，最小元，極大元，極小元；AB={4,6,8,12}的上界，下界，最小上界，最大下界.G(P→Q)∨(Q∧(P→R)),G的主析取范式。(9分)設(shè)一階邏輯公式：G=(xP(x)∨yQ(y))→xR(x)G化成前束范式.9.設(shè)RA={a,b,c,d}.RA上的二元關(guān)系,R={(a,b),(b,a),(b,c),(c,d)},(1) r(R),s(R),t(R)；(2) r(R),s(R),t(R).11.通過求主析取范式判斷下列命題公式是否等價(jià)：(1)G=(P∧Q)∨(P∧Q∧R)(2)H=(P∨(Q∧R))∧(Q∨(P∧R))RSA＝{a,b,d}R＝{(aa),(a,c),(b,c),(cd)},c),(b,d),(d,d)}.RS的關(guān)系矩陣；(2)RS,RSR－1－1R－1.四、證明題利用形式演繹法證明：{P→Q,R→SP∨R}Q∨S。A,B為任意集合，證明：(A-B)-C=(本題10)利用形式演繹法證明：{A∨B, C→B, C→D}蘊(yùn)涵A→D。(10)A,BA－(A∩B)=(A∪B)－B

S＝{(a, b),(b,參考答案一、填空題1. {3}; {{3},{1,3},{2,3},{1,2,3}}.2. 23. 1={(a,1),(b,1)},2={(a,2),(b,2)},3={(a,1),(b,2)},4={(a,2),(b,1)};3,4.4. (P∧Q∧R).5. 12,3.6. {4},{1,2,3,4},{1,2}.7. 自反性；對稱性；傳遞性.8. (1,0,0),(1,0,1),(1,1,0).9. {(1,3),(2,2),(3,1)};{(2,4),(3,3),(4,2)};{(2,2),(3,3)}.10.2mn.11.{x|-1≤x<0,xR};{x|1<x<2,xR};{x|0≤x≤1,xR}.12.12;6.13.{(2,2),(2,4),(2,6),(3,3),(3,6),(4,4),(5,5),(6,6)}.14.x(P(x)∨Q(x)).15.21.16.(R(a)∧R(b))→(S(a)∨S(b)).17.{(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.1281284692311.(1)

15.DB1,3;3.A18,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)}.141423111(2)MR111

0 0 01 0 01 1 01 1 13.(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.81248124621無最大元，B無上界，

18,12;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))9.(1)r(R)＝R∪IA＝{(a,b),(b,a),(b,c),(c,d),(a,a),(b,b),(c,c),(d,d)},s(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)系圖:aadadadbbccbcr(R)s(R)t(R)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.0101000001010000013. (1)M R 0

0 0 M 1 S 0

0 1 10 0 000 00

0 0 1(2)RS＝{(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－1R－1＝{(b,a),d,)}.四證明題證明：{P→QR→S,P∨R}Q∨SP∨RR→PP→QR→SQ→SQ∨S

PQ(1)PQ(2)(3)Q(4)PQ(5)(6)Q(7)2.證明：(A-B)-C=(A∩~B)∩~C=A∩(~B∩~C)=A