離散數(shù)學(xué)試題與答案

1、離散數(shù)學(xué)試題與答案【篇一：離散數(shù)學(xué)試題及答案】一、填空題1 設(shè)集合 a,b ,其中 a= 1,2,3, b= 1,2, 則 a- b =; = .3. 設(shè)集合 a = a, b, b = 1, 2, 則從 a 到 b 的所有映射是, 其中雙射的是4. 已知命題公式g = ?(p?q) Ar,則g的主析取范式是5. 設(shè) g 是完全二叉樹(shù)，g 有 7 個(gè)點(diǎn)，其中4 個(gè)葉點(diǎn)，則g 的總度數(shù)為 ，分枝點(diǎn)數(shù)為.7 . 設(shè) r 是集合 a 上的等價(jià)關(guān)系，則r 所具有的關(guān)系的三個(gè)特性是8 .設(shè)命題公式g = ?(p?(q?r),則使公式g為真的解釋有9 .設(shè)集合 a = 1,2,3,4, a 上的關(guān)系 ri

2、 = (1,4),(2,3),(3,2), ri =(2,1),(3,2),(4,3), 則 r1?r2 = ,r2?r110 . 設(shè)有限集a, b ， |a| = m, |b| = n, 則 | |?(a?b)| =11設(shè)a,b,r是三個(gè)集合，其中r是實(shí)數(shù)集，a = x | - 1<x< 1, x?r, b =x | 0< x 2, x?則 a-b =, b-a =, aA b =,.13 .設(shè)集合a = 2, 3, 4, 5, 6，是a上的整除，則r以集合形式(列舉法)記為 14 . 設(shè)一階邏輯公式g = ?xp(x)?xq(x) ，則 g 的前束范式是15 .設(shè) g 是

3、具有 8 個(gè)頂點(diǎn)的樹(shù)，則g 中增加 條邊才能把g變成完全圖。?(a) - ?(b) r1216 .設(shè)謂詞的定義域?yàn)閍, b,將表達(dá)式？xr(x) -?xs(x)中量詞消除， 寫(xiě)成與之對(duì)應(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)。則 r?s = r2 =二、選擇題1設(shè)集合a=2,a,3,4 , b = a,3,4,1 , e為全集，則下列命題正確的是 ( )。(a)2?a(b)a?a(c)?a?b?e (d)a,1,3,4?b.2 設(shè)集合 a=1,2,3,a 上的關(guān)系 r

4、= (1,1),(2,2),(2,3),(3,2),(3,3),則 r 不具備 ( ).(a)自反性(b)傳遞性(c)對(duì)稱性(d)反對(duì)稱性則元3設(shè)半序集(a, w菠系 啪哈斯圖如下所示，若 a的子集素6為b的()。(a)下界(b)上界(c)最小上界(d)以上答案都不對(duì)4下列語(yǔ)句中，()是命題。(a)請(qǐng)把門關(guān)上(b)地球外的星球上也有人(c)x + 5 6 (d) 下午有會(huì)嗎？5 設(shè) i 是如下一個(gè)解釋：d = a,b, p(a,a) p(a,b) p(b,a) p(b,b) 1 01 0則在解釋i 下取真值為1 的公式是( ).(a)?x?yp(x,y)(b)?x?yp(x,y)(c)?xp(

5、x,x) (d)?x?yp(x,y).6 . 若供選擇答案中的數(shù)值表示一個(gè)簡(jiǎn)單圖中各個(gè)頂點(diǎn)的度，能畫(huà)出圖的是 ( ).(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).7 .設(shè)g、h是一階邏輯公式，p是一個(gè)謂詞，g = ?xp(x), h =?xp(x), 則一階邏輯公式g?h 是 ( ).(a)恒真的(b)恒假的可滿足的(d)前束范式.8設(shè)命題公式g = ?(p?q) , h = p?(q?p)，則g與h的關(guān)系是()。(a)g?h(b)h?g(c)g = h (d)以上都不是.9設(shè)a, b為集合,當(dāng)()時(shí)a b =

6、 b.(a)a = b (b)a?b (c)b?a (d)a = b = ?.10 設(shè)集合 a = 1,2,3,4, a 上的關(guān)系 r=(1,1),(2,3),(2,4),(3,4), 則 r 具有 ( )。(a)自反性(b)傳遞性 對(duì)稱性(d)以上答案都不對(duì)11 下列關(guān)于集合的表示中正確的為( )。(a)a?a,b,c (b)a?a,b,c (c)?a,b,c (d)a,b?a,b,c12 命題 ?xg(x) 取真值 1 的充分必要條件是( ).(a)對(duì)任意x, g(x)都取真值1.(b)有一個(gè)x0,使g(x0)取真值1.有某些x,使g(x0)取真值1.(d)以上答案都不對(duì).13 . 設(shè) g

7、 是連通平面圖，有5 個(gè)頂點(diǎn)，6 個(gè)面，則g 的邊數(shù)是( ).(a) 9 條 (b) 5 條 (c) 6 條 (d) 11 條 .14 . 設(shè) g 是 5 個(gè)頂點(diǎn)的完全圖，則從g 中刪去 ( )條邊可以得到樹(shù).(a)6(b)5(c)10 (d)4.1111?0100? ，則 1011?0101?0110?0?1 的相鄰矩陣為 ?1?1?115. 設(shè)圖 gg 的頂點(diǎn)數(shù)與邊數(shù)分別為( ).(a)4, 5 (b)5, 6 (c)4, 10 (d)5, 8.三、計(jì)算證明題(1) 集合 a = 1, 2, 3, 4, 6, 8, 9, 12 , r 為整除關(guān)系。(1)畫(huà)出半序集(a,r)的哈斯圖；(2)

8、 寫(xiě)出 a 的子集 b = 3,6,9,12 的上界，下界，最小上界，最大下界；(3) 寫(xiě)出 a 的最大元，最小元，極大元，極小元。2.設(shè)集合 a = 1, 2, 3, 4 , a 上的關(guān)系 r = (x,y) | x, y?a 且 x ? y,求1) ) 畫(huà)出 r 的關(guān)系圖；2) ) 寫(xiě)出 r 的關(guān)系矩陣.3) 設(shè) r 是實(shí)數(shù)集合，?,?,? 是 r 上的三個(gè)映射，?(x) = x+3, ?(x) =2x, ?(x) = x/4,試求復(fù)合映射 ? ， ?, ?, ? ， ?.4) 設(shè) i 是如下一個(gè)解釋：d = 2, 3,a3 b 2 f (2) 3 f (3) 2 p(2, 2) p(2,

9、 3) p(3, 2) p(3, 3) 0 0 1 1試求(1) p(a, f (a) A p(b, f (b);(2) ?x?y p (y, x).5.設(shè)集合a = 1, 2,4, 6, 8,12，為a上整除關(guān)系。(1)畫(huà)出半序集(a,r)的哈斯圖；(2) 寫(xiě)出 a 的最大元，最小元，極大元，極小元；(3) 寫(xiě)出 a 的子集 b = 4, 6, 8, 12 的上界，下界，最小上界，最大下界 .6 .設(shè)命題公式g = ?(p f q)V (q A (?p f r),求g的主析取范式。7 . (9 分)設(shè)一階邏輯公式：g = (?xp(x) V ?yq(y) f ?xr(x)，把 g 化成前束范

10、式.9. 設(shè) r 是集合 a = a, b, c, d. r 是 a 上的二元關(guān)系, r = (a,b), (b,a),(b,c), (c,d),(1) 求出r(r), s(r), t(r) ；(2) 畫(huà)出r(r), s(r), t(r) 的關(guān)系圖.11. 通過(guò)求主析取范式判斷下列命題公式是否等價(jià)：(1) g = (p A q) V (?p A q A r)(2) h = (p V (q A r) A (q V (?p A r)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

11、, d),(d, d).(1) 試寫(xiě)出 r 和 s 的關(guān)系矩陣；(2)計(jì)算 r?s, r Us, r1, s1?r1.四、證明題1 .利用形式演繹法證明：pfq, r s, pV r蘊(yùn)涵qVs。2 .設(shè)a,b為任意集合，證明：(a-b)-c = a-(b U c).3 .(本題10分)利用形式演繹法證明：?a V b, ?c ?b, c d1涵 a d o4 . ( 本題 10 分 )a, b 為兩個(gè)任意集合，求證：a (a Ab) = (aU b) b .參考答案一、填空題1. 3; 3,1,3,2,3,1,2,3.2. 2.n23. ?1= (a,1), (b,1), ?2= (a,2),

12、 (b,2),?3= (a,1), (b,2), ?4=(a,2), (b,1); ?3, ?4.4. (p A ?q A r).5. 12, 3.6. 4, 1, 2, 3, 4, 1, 2. 7. 自反性；對(duì)稱性；傳遞性.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. 2m?n.11. x | - 1<x 0, x?r; x | 1 x 2, x?r; x | 0<x< 1, x?r.12. 12; 6.13. (2, 2),(2, 4),

13、(2, 6),(3, 3),(3, 6),(4, 4),(5, 5),(6,6).14. ?x(?p(x) Vq(x).15. 21.【篇二：離散數(shù)學(xué)練習(xí)題及答案】的表示方法有兩種：法。請(qǐng)把“奇整數(shù)集合”表示出， k?z 來(lái) 。 1、列舉；描述；x|x?2k?12 、無(wú)向連通圖g 含有歐拉回路的充分必要條件是2*、連通有向圖d 含有歐拉回路的充分必要條件是d 中每個(gè)結(jié)點(diǎn)的入度=出度.3 、設(shè) r 是集合 a 上的等價(jià)關(guān)系，則r 所具有的關(guān)系的三個(gè)特性是自反性、對(duì)稱性、傳遞性.4 、有限圖g 是樹(shù)的一個(gè)等價(jià)定義是：.5、設(shè)n(x) ： x 是自然數(shù)，z(y)； y 是整數(shù)，則命題“自然數(shù)都是整數(shù)

14、，而有的整數(shù)不是自然數(shù) ”符號(hào)化為?x(n(x)?z(x)?x(z(x)?n(x)6 、在有向圖的鄰接矩陣中，第i 行元素之和,第 j 列元素之和分別為結(jié)點(diǎn) v 的出度和結(jié)點(diǎn)v 的入度7 、設(shè) a， b 為任意命題公式，c 為重言式，若a?c?b?c ，那么命題a?b 是重言式的真值是1 8 、命題公式?(p?q) 的主析取范式為9、設(shè)圖g =v, e和g? = v?,e?,若g?是g的真子圖，若，貝U g?是g的生成子圖.v?v或e?e;v?v,e?e10、在平面圖g?v,e? 中 ,則11、設(shè) a?a,b,?deg(r)=淇中 r(i=1,2,rig 的面 iiri?1b?1,2 ，則從

15、a 到 b 的所有映射是11 、 ?1= ( a， 1)，( b， 1) ； ?2= ( a， 2)，(b， 2) ； ?3=( a， 1)，( b，2) ； ?4= ( a，2 )，( b ， 1 ) 12、表達(dá)式？x?yl (x, y)中謂詞的定義域是a, b, c,將其中的 量詞消除，寫(xiě)成與之等價(jià)的命題公式為12、(l(a，a)?l (a，b)?l (a，c)?( l( b， a) ?l (b，b) ?l(b，c)?(l(c，a)?l(c，b)?l( c， c)12*、設(shè)個(gè)體域d = a,b,公式？x(g(x)?yh(x,y)消去量詞化為13、含有三個(gè)命題變項(xiàng)p， q， r 的命題公式p

16、?q 的主析取范式是14、設(shè)r， s 都是集合a 上的等價(jià)關(guān)系，則對(duì)稱閉包s(r?s)=15 、設(shè)g 是連通平面圖，v,e,r 分別表示g 的結(jié)點(diǎn)數(shù)，邊數(shù)和面數(shù)，則v,e和 r 滿足的關(guān)系式是 v?r?e?16、設(shè)g是n個(gè)結(jié)點(diǎn)的簡(jiǎn)單圖，若g,則g 一定是哈密頓圖.17、一個(gè)有向樹(shù)t 稱為根樹(shù)，若稱為樹(shù)葉. 若有向圖t 恰有一個(gè)結(jié)點(diǎn)的入度為0，其余結(jié)點(diǎn)入度為1 ；入度為 0 的結(jié)點(diǎn)；出度為0 的結(jié)點(diǎn) .18 、圖的通路中邊的數(shù)目稱為結(jié)點(diǎn)不重復(fù)的通路是通路. 邊不重復(fù)的通路是 通路 . 通路長(zhǎng)度；初級(jí)；簡(jiǎn)單.19、設(shè) a 和 b 為有限集，|a|=m ， |b|=n ，則有個(gè)從 a 到 b 的關(guān)系

17、，有 個(gè)從 a 到 b 的函數(shù)，其中當(dāng)m?n 時(shí)有 個(gè)入射，當(dāng)m=n 時(shí)，有個(gè)雙射。19、 2m*nm,nm,cn?m!,m!2a?n|n?n (是/不是)可數(shù)的。是20、集合21 、設(shè) l?1,2,3,4,12? 上的整除關(guān)系?a1,a2a1,a2?l,a1 整除 a2 ?在 l 上定義兩個(gè)二元運(yùn)算? 和 ? ：對(duì)任意a,b?l ， a?b?glb(a,b) ，a?b?lub(a,b)。請(qǐng)?zhí)羁?在橫線上填是或不是)：是 是 是不是代數(shù)系統(tǒng)?l,?,? 格。 代數(shù)系統(tǒng)?l,?,? 有界格。代數(shù)系統(tǒng) ?l,?,? 有補(bǔ)格。代數(shù)系統(tǒng)?l,?,? 分配格。二、單項(xiàng)選擇題(選擇一個(gè)正確答案的代號(hào)，填入

18、括號(hào)中)1 、設(shè)命題公式g= ?( p?q )， h=p? ( q? ?p )，則 g 與 h 的關(guān)系是( a )。a g?hb h?g c g=h d 以上都不是2 、下列命題公式等值的是( c )(a)?p?q,p?q(c)q?(p?q),?q?p?q(b)a?(a?b),?a?(a?b)(d)?a?(a?b),b3、設(shè)v = a,b,c,d,與v能構(gòu)成強(qiáng)連通圖的邊集e = ( a )(a) a,b,a,c,d,a,b,d,c,d (b) a,d,b,a,b,c,b,d,d,c(c) a,c,b,a,b,c,d,a,d,c (d) a,d,b,a,b,d,c,d,d,c4、設(shè) l(x) ：

19、 x 是演員， j(x) ： x 是老師，a(x,y) ： x 佩服 y. 那么命題“所有演員都佩服某些老師 ”符號(hào)化為( b )(a) ?xl(x)?a(x,y)(b) ?x(l(x)?y(j(y)?a(x,y)(c) ?x?y(l(x)?j(y)?a(x,y)(d) ?x?y(l(x)?j(y)?a(x,y)5 、在由 3 個(gè)元素組成的集合上，可以有(d ) 種不同的關(guān)系。(a)3 (b)8(c) 9 (d) 5126、設(shè) s1=?,s2=?,s3=p(?),s4=p(?) 則命題為假的是( a ) (a)s2?s4(b) s1?s3 (c) s2?s4 (d) s4?s37 、設(shè) g 是

20、連通平面圖，有v 個(gè)結(jié)點(diǎn)，e 條邊， r 個(gè)面，則r= ( a )(a) e v 2(b)v e 2(c)e v 2(d) e v 28 、下列命題正確的是(a )。a ?=? b ?=?c a?a ， b， c d ?a ， b， c9、設(shè)a, b, c都是集合，如果 a?c =b?c ,則有(c )(a) a = b (b) a?b (c) 當(dāng) a c = b c 時(shí)，有 a=b (d)當(dāng) c=u 時(shí)，有a?b10、設(shè) (b,?,?,0,1) 是布爾代數(shù)，?a,b?b,a?b ，則下式不成立的是(d ) (a)ab?0(b)a?b?1(c)a?b?a(d)a?b?111 、下面給出的一階邏

21、輯等價(jià)式中，(a )是錯(cuò)的。a?x ( a(x)?b (x)=?xa(x)?xb(x)b a?xb(x)=?x(a?b ( x)c ?x ( a(x)?b (x)=?xa(x)?xb(x)d ?xa ( x) =?x ( ?a( x)三、多重選擇題(每道小題都可能有一個(gè)以上的正確選項(xiàng)，須選出所有的正確選項(xiàng)，不答不得分，多選、少選或選錯(cuò)都將按比例扣分。)1、命題公式(pA(pfq)fq是 式。(1) 重言 (2) 矛盾 (3) 可滿足 (4) 非永真的可滿足2、給定解釋i=(d,ic)=( 整數(shù)集，f(x,y):f(x,y)=x-y ；g(x,y):g(x,y)=x+y ；p(x,y):xy)

22、，下列公式中在解釋 i 下為真。(1) p(f(x,y),g(x,y) (2) ?x?y p(f(x,y),g(x,y)？x?y(p(x,y)- p(f(x,y),x) (4) ?x?y p(f(x,y),g(x,y)3、A 是集合，a =10,則 p(a)= 。(1) 100(2) 99 (3) 2048 (4) 1024(5) 5124、集合A =x|x 是整數(shù)，x230 , B =x|x 是質(zhì)數(shù)，x20 , c=1,3,5, 則 (a?b)?c=; (b?a)?c=; (c?a)?(b?a)=; (b?c)?a= 。(1) 1,2,3,5(2) ? (3) 0 (4) 1,3,5,7,1

23、1,13,17,19(5) 1,3,5,7 (6) 7,11,13,17,195、設(shè)a、 b、 c 是集合，下列四個(gè)命題中，在任何情況下都是正確的。(1)若 a?b 且 b G c,貝fj a G c (2)若 a?b 且 b G c,貝fj a?c(3)若 a G b 且 b?c ,則 a?c (4)若 a G b 且 b?c，則 a G c6、設(shè)集合A =a,b,c,d,e,f,g , A 的一個(gè)劃分？=a,b,c,d,e,f,g, 則?所對(duì)應(yīng)的等價(jià)關(guān)系有個(gè)二元組。(1) 14 (2) 15(3) 16 (4) 17 (5) 8 (6) 49 (7) 5127、s =1,2,3,4,5,6

24、,7,8,9,10,11,12, 逗 s 上的整除關(guān)系。s 的子集B =2,4,6 ,則在 s, w中，B的最大元是 ; B的最小元是 ;B的上確界是 ; B的下確界是 。(1) 不存在的(2) 36(3) 24 (4) 12 (5) 6 (6) 1 (7) 28、設(shè)有有限布爾代數(shù)(b,+,*, ,0,1，則 )b= 能成立。(1) 1 (2) 2 (3) 3 (4) 4 (5) 5(6) 8(7) 99、g =0,1,2,?,n , n Gn,定義？為模 n 加法，即 x?y =(x+y) modn ，則代數(shù)系統(tǒng)(g， ?) 。(1) 是半群但不是群(2) 是無(wú)限群(3) 是循環(huán)群(4) 是

25、變換群(5)是交換群10、僅有一個(gè)結(jié)點(diǎn)的圖稱為()，當(dāng)然也是( )(1) 零圖 (2) 平凡圖 (3) 補(bǔ)圖 (4) 子圖1. 1 、3。2.4。3. 4。4.1 ；4； 2；2。5. 4。7. 1 ；7；4；7。8. 2、4、6。9. 3、5。10. 2； 1。四、化簡(jiǎn)解答題1、(1)設(shè)圖g(如第1題圖)，作圖g的嵌入圖，說(shuō)明圖g是平面圖.第 1 題圖 1 、 (1)圖 g 的嵌入圖，如第12 題答案圖.故圖g 為平面圖(4 分 )第 12 題答案圖(2)在具有 n 個(gè)頂點(diǎn)的完全圖kn 中刪去多少條邊才能得到樹(shù)？解： n 個(gè)頂點(diǎn)的完全圖kn 中共有 6. 4。 n?(n?1) 條邊， n 個(gè)

26、頂點(diǎn)的樹(shù)應(yīng)有 n?1 條邊，于是，刪2n?(n?1)(n?1)?(n?2)?(n?1)? 去的邊有：。222、判別謂詞公式?x?yf(x,y)?y?xf(x,y) 的類型 .2 、設(shè) i 為任意一個(gè)解釋，d 為 i 的個(gè)體域. 若在解釋i 下，該公式的前件為0，無(wú)論?y?xf(x,y) 如何取值，?x?yf(x,y)?y?xf(x,y) 為 1 ；若在解釋i 下，該公式的前件為1 ，則 ?x0?d, 使得 ?yf(x,y) 為 1，它蘊(yùn)含著？y?d,f(x0,y?)為1?xf(x,y?)為1,由y?的任意性，必有 ?y?xf(x,y) 為 1 ，于是 ?x?yf(x,y)?y?xf(x,y)

27、為 1.所以， ?x?yf(x,y)?y?xf(x,y) 是永真式3、化簡(jiǎn)集合表達(dá)式：(a?b?c)?(a?c) (c?(c b) a)3、(a?b?c)?(a?c) (c?(c b)?a)= (a?c) (c?a)(兩次用吸收律)=(a?c)?(c?a)=(a?c)?(c?c)?a?(a?c)=(a?c)?a=a4 、判斷下列哪些運(yùn)算結(jié)果是對(duì)的？哪些是錯(cuò)的？請(qǐng)將錯(cuò)誤的運(yùn)算結(jié)果更正過(guò)來(lái)(1) ? (2) ?(3) ?,? (4) ?,?,?( 5) (a?b)?b?a ( 6) (a?b)?b?a( 7) a?a?a ( 8) (a?b)?a?4、 (1) 對(duì) (2) 錯(cuò)應(yīng)為? (3) 對(duì) (

28、4) 錯(cuò)應(yīng)為?( 5)錯(cuò)應(yīng)為a?b ( 6)錯(cuò)應(yīng)為a?b( 或 a?b 或a ab)( 7)錯(cuò)應(yīng)為?，即 a?a?a?a?a?a?( 8)對(duì)5、將命題公式?p?q?(?r?p) 化為只含?和 ?的盡可能簡(jiǎn)單的等值式 5、 ?p?q?(?r?p)?(p?q)?(r?p) (優(yōu)先級(jí)有誤)?(p?q)?(?p?r) 不惟一 .(1) v1e5 v5e7 v2e2 v3 (2) v5e6 v2e2 v3e3 v4e8 v2e7 v5 v254 (3) v2e7 v5e6 v2 (4) v1e1 v2e2 v3e3 v4e8 v2e6 v5ev46、 (1) 初級(jí)通路；(2) 簡(jiǎn)單回路；(3) 初級(jí)回路

29、；(4) 簡(jiǎn)單通路.e3v ev 7 、試問(wèn) n 取何值時(shí)，無(wú)向完全圖kn ，存在一條歐拉回路？6 、設(shè)圖 g 如右圖 . 已知通路7 、由于 kn 有 n 個(gè)結(jié)點(diǎn)，并且每個(gè)結(jié)點(diǎn)的度數(shù)均為n 1，于是，當(dāng) n 為奇數(shù)時(shí)，kn 的每個(gè)結(jié)點(diǎn)的度數(shù)都是偶數(shù)，所以存在一條歐拉回路8、已知 (l ， *， ?)是格，且二元運(yùn)算*和 ?滿足分配律，?a,b,c?l ，化簡(jiǎn)表達(dá)式(a*b)?(a*c)* (a*b)?(b*c)解答： (a*b)?(a*c)*(a*b)?(b*c)=(a*b)? ( (a*c)* (b*c)( 分配律)=(a*b) ?(a*b)*c) ( 冪等律 )=a*b( 吸收律 )9

30、、化簡(jiǎn) (?p?(?q?r)?(q?r)?(p?r)。9、 (?p?(?q?r)?(q?r)?(p?r)=(?p?q?q?p)?r=(?p?q?p)?r=r10、試將一階邏輯公式?x?yp?x,y?yq?y?r?x? 化成前束范式。 解：【篇三：離散數(shù)學(xué)試卷及答案】t> 一、填空20% (每小題2分)1.設(shè) a?x|(x?n)且(x?5),b?x|x?e 且 x?7 (n：自然數(shù)集，e+ 正 偶數(shù)) 則 a?b? 。 2 a， b， c 表示三個(gè)集合，文圖中陰影部分的集合表達(dá)式為。3設(shè)p ， q 的真值為0， r， s 的真值為1 ，則?(p?(q?(r?p)?(r?s) 的真值 = 。

31、4 公式 (p?r)?(s?r)?p 的主合取范式為。5 若解釋i 的論域 d 僅包含一個(gè)元素，則?xp(x)?xp(x) 在 i 下真值為 。6 設(shè) a=1 ， 2， 3， 4， a 上關(guān)系圖為則 r2 = 。7 .設(shè)a=a , b, c, d,其上偏序關(guān)系r的哈斯圖為則 r= 。8 圖的補(bǔ)圖為。9設(shè) a=a ， b， c， d ， a 上二元運(yùn)算如下：那么代數(shù)系統(tǒng)a， *的幺元是，它們的逆元分別為。10下圖所示的偏序集中，是格的為。二、選擇20% （每小題2 分）1 、下列是真命題的有（）aa?a ；b ?,? ；c?,? ； d ? 。 2、下列集合中相等的有（）a 4， 3? ； b?

32、，3，4； c 4， ?， 3，3；d3， 4。3、設(shè) a=1 ， 2， 3，則 a 上的二元關(guān)系有（）個(gè)。 a 23 ； b 32 ； c 23?3； d 3 2?2。4、設(shè)r, s是集合a上的關(guān)系，則下列說(shuō)法正確的是（）a.若r, s是自反的，則r?s是自反的；b .若r, s是反自反的， 則r?s是 反自反的；c.若r, s是對(duì)稱的，則r?s是對(duì)稱的；d .若r, s是 傳遞的，則 r?s 是傳遞的。5、設(shè)a=1 , 2, 3, 4, p （a）（ a的窯集）上規(guī)定二元系如下r?s,t?|s,t?p（a）?（|s|?|t| 則 p（ a） / r=（）a a ； b p（a） ； c1

33、，1 ，2， 1， 2，3， 1 ， 2，3，4； d ? ， 2，2， 3，2，3， 4，a6、設(shè)a=? , 1, 1 , 3, 1 , 2, 3則a上包含關(guān)系“？的哈斯圖為（ ）7 、下列函數(shù)是雙射的為（）a f : i?e , f （x） = 2x ； b f : n?n?n, f （n） = n , n+1；c f :r?i , f （x） = x； d f :i?n, f （x） = | x |。 （注： i 整數(shù)集，e偶數(shù)集，n 自然數(shù)集，r 實(shí)數(shù)集）8、圖 中 從 v1 到 v3 長(zhǎng)度為 3的通路有（）條。a 0；b1；c2；d3。9 、下圖中既不是eular 圖，也不是hamilton 圖的圖是（）10、在一棵樹(shù)中有7 片樹(shù)葉，3 個(gè) 3 度結(jié)點(diǎn)，其余都是4 度結(jié)點(diǎn)則該樹(shù)有（）個(gè) 4度結(jié)點(diǎn)。a 1； b 2；c 3； d 4 。三、證明26%1、r是集合x(chóng)上的一個(gè)自反關(guān)系，求證：r是對(duì)稱和傳遞的，當(dāng)且僅當(dāng)a, b 和 a , c 在 r 中有 .b , c 在 r 中。(