離散數(shù)學(xué)復(fù)習(xí)題全

1、離散數(shù)學(xué)復(fù)習(xí)資料一、填空.命題“對(duì)于任意給定的正實(shí)數(shù)，都存在比它大的實(shí)數(shù)”令F(x)： X為實(shí)數(shù)，L(x，y)：x y則命題的邏輯謂詞公式為 。.設(shè)p：王大力是100米冠軍，q：王大力是500米冠軍，在命題邏輯中，命題“王大力不 但是100米冠軍，而且是 500米冠軍”的符號(hào)化形式為 。命題“存在一個(gè)人不但是 100米冠軍，而且是 500米冠軍”的符號(hào)化形式為 。.選擇合適的論域和謂詞表達(dá)集合A= 直角坐標(biāo)系中，單位元(不包括單位圓周)的點(diǎn)集”則A= o.設(shè)P (x)： x是素?cái)?shù)，E(x)： x是偶數(shù)，O(x)： x是奇數(shù)N (x,y)： x可以整數(shù)y。則謂詞x(P(x) y(O(y) N(y

2、, x)的自然語(yǔ)言是對(duì)于任意一個(gè)素?cái)?shù)都存在一個(gè)奇數(shù)使該素?cái)?shù)都能被整除。.設(shè)個(gè)體域是a, b,謂詞公式(x) P(x) ( x)P(x)寫成不含量詞的形式是 。.謂詞 x y( z(P(x,z) P(y,z) uQ(x, y,u)的前束范式為 。.命題公式A P ( P (Q ( Q R)的主合取范式為,其編碼表示為。. 設(shè)E為全集，稱為A的絕對(duì)補(bǔ)，記作A,且(A) =，E =,.=。.設(shè) A=2,5,6,B 2,3,4,C1 ,3,4,則 A-B=, AB= ,AxC =。.設(shè) A a,b,c考慮下列子集 Si a,b,b,c , S2 a, a,b,a,c,. S3a,b,c, S4 a,b

3、,c, S5 a,b,c , S6 a,a,c.則A的覆蓋有 , A的劃分有 。.設(shè) M x1 x 12,x被2整除，x Z , N x1 x 12,x被3整除，x Z,則M N , M N o.設(shè)人=, , B=,惻 A B=, A B=。. A=1, 2, 3, 4, 5, 6, A上二元關(guān)系T x, y | x y是素?cái)?shù)，則用列舉法 T= ;T的關(guān)系圖為, T具有 性質(zhì)。17.偏序集 A, R的哈斯圖為17.偏序集 A, R的哈斯圖為d.設(shè)A x|x 2n , n N,定義A上的二元運(yùn)算為普通乘法、除法和加法，則代數(shù)系統(tǒng)A,*中運(yùn)算*關(guān)于 運(yùn)算具有封閉性。. A, B, C表示三個(gè)集合，

4、文圖中陰影部分的集合表達(dá)式為 。20.0 10 1設(shè)圖 G = V, 20.0 10 1設(shè)圖 G = , V Vi,V2,V3,V4的鄰接矩陣1,則V1的入度0110 0 0deg (Vi)=, V4的出度deg (V4) =,從V2到V4的長(zhǎng)度為2的路徑有 條。.結(jié)點(diǎn)數(shù)n ( n 3)的簡(jiǎn)單連通平面圖的邊數(shù)為m,則m與n的關(guān)系為 m=3n-6。.設(shè)f, g是自然數(shù)集N上的函數(shù)x N, f (x) x 1 , g(x) 2x,則f g(x) Z3上定義+3如下:.設(shè)I是整數(shù)集合，Z3上定義+3如下:3 j (i j)mod 3,則+3的運(yùn)算表為 ； 是否構(gòu)成群 24.集合 24.集合 S=”

5、,3, 丫，8 上的二元運(yùn)算*為*a3丫8a8a3丫3a3丫8丫3丫Y丫8a8Y8那么，代數(shù)系統(tǒng)S, *中的幺元是 , “的逆元是 25.設(shè) a,b,c, * 為代數(shù)系統(tǒng)，*運(yùn)算如下:*abcaabcbbaccccc則它的幺元為設(shè) A=a, b, c, A 上設(shè) A=a, b, c, A 上.兀關(guān)系 R= , ，則 s (R)=27 .28.設(shè)集合X=1,2,3,27 .28.設(shè)集合X=1,2,3,下列關(guān)系中不是等價(jià)的。設(shè) A=, , B=,則 A B =29.30.設(shè)G是n階完全圖，則G的邊數(shù)m=31.設(shè)A=a, b,c,d,其上偏序關(guān)系 R的哈斯圖如右圖所示：則29.30.設(shè)G是n階完全圖

6、，則G的邊數(shù)m=31.設(shè)A=a, b,c,d,其上偏序關(guān)系 R的哈斯圖如右圖所示：則R=。32.n階完全圖Kn的邊數(shù)為33.結(jié)點(diǎn)數(shù)n ( n 3)的簡(jiǎn)單連通平面圖的邊數(shù)為m,則m與n的關(guān)系為34.O的補(bǔ)圖為,oA= ,B= ,C= ,D= ,設(shè) X 1,2,3,4, R 1,2，2,4，3,3 ，則(R尸；s (R)= ;t(R) =.有向圖 I中從vi到V2長(zhǎng)度為2的通路有 條。.設(shè)G為9階無(wú)向圖，每個(gè)結(jié)點(diǎn)度數(shù)不是5就是6,則G中至少有 個(gè)5度結(jié)點(diǎn)。. n階完全圖結(jié)點(diǎn) v的度數(shù)d(v) =n-1。二、證明.不構(gòu)造真值表證明蘊(yùn)涵式.(Q (PP) (R(R(P P)R Q.證明ABC D ,

7、DEFA F.證明(PA Q)V(PAQ) P.證明(P QR)(P Q)R.證明 x(P(x) Q(x) xP(x) xQ(x).證明 x(P(x)Q(x) xP(x)xQ(x).用推理規(guī)則證明下式：.前提：(x)P(x) x(P(x) Q(x)R(x) ,( x)P(x),( x)Q(x).結(jié)論：(x)( y)(P(x) R(y).設(shè)論域 D=a , b , c,求證：xA(x) xB(x) x(A(x) B(x)。.設(shè)g f是復(fù)合函數(shù)，如果 g f滿射，則g也是滿射。.假定f : AB,g : B C,且gf是一個(gè)滿射，g是個(gè)入射，則f是滿射。.用反證法證明(P Q)(P R)(Q S)

8、 S Ro.設(shè) I , + 一個(gè)群，設(shè) Ie= x|x=2n , nCI ,證明 Ie, + 是 I , + 的一個(gè)子群。三、按要求解答.將謂詞公式( x)P(x) ( y)Q(y)( y)R(y)化為前束析取范式與前束合取范式。.用推理規(guī)則論證：如果今天是星期六，我們就要到頤和園或圓明園玩，如果頤和園游人太 多，我們就不去頤和園玩。今天是星期六，頤和園游人太多，所以，我們?nèi)A明園玩。.符號(hào)化語(yǔ)句：“有些人喜歡所有的花，但是人們不喜歡雜草，那么花不是雜草”。并推證其結(jié)論。.用推理規(guī)則論證：或者邏輯難學(xué)，或者有少數(shù)學(xué)生不喜歡它；如果數(shù)學(xué)容易學(xué)，那么邏輯 并不難學(xué)。因此，如果許多學(xué)生喜歡邏輯，那么

9、數(shù)學(xué)并不難學(xué)。.設(shè)有下列情況，用推理規(guī)則論證結(jié)論是否有效(a)或者天晴，或者下雨。(b)如果天晴,我去看電影。(c)如果我去看電影，我就不看書。結(jié)論：如果我在看書則天在下雨。.符號(hào)化語(yǔ)句：“有些病人相信所有的醫(yī)生，但是病人都不相信騙子，所以醫(yī)生都不是騙子” 并推證其結(jié)論。.給定3個(gè)命題：P:北京比天津人口多； Q: 2大于1; R: 15是素?cái)?shù)。求復(fù)合命題：(Q R) (P R)的真值。.將x( ( yP(x, y)( zQ(z) R(x)化為與其等價(jià)的前束范式。.把公式 x P x x Q x轉(zhuǎn)化為前束范式.求(Q P) ( P Q)的主合取范式。.求(ABC) (A(BC)的主析取范式與主

10、合取范式。.求(PVQ)R的主析取范式與主合取范式。.設(shè)命題Ai, A2的真值為1, A3, A4真值為0,求命題. (Ai (A2(A3A)(A2A4)的真值。. 一 1. 一一 .求集合Anx 0 x (n 1,2,3,)的并與父。n.設(shè)*=1,2,3,4,5, X上的關(guān)系 R= , , , , ,求 R 的傳遞閉 包 t (R)。.設(shè)集合X a, b, c, d上的關(guān)系R a,b , b,a , b,c , c,c 。求R的傳遞閉包t(R)。.在實(shí)數(shù)平面上，畫出關(guān)系 R x,y xy20 xy20,并判定關(guān)系的特 殊性質(zhì)。.設(shè) X= a, b, c, d , R是 X上的二元關(guān)系,R=,

11、 , , , 設(shè)$=1 , 2,3,4, 6,8 , 12,24“ ”為S上整除關(guān)系，問(wèn)：（1）偏序集 S , 的哈斯圖如何（2）偏序集（1）畫出R的關(guān)系圖。（2）寫出R的關(guān)系矩陣。（3）說(shuō)明R的性質(zhì). A=a,b,c,d, R=,為A上的關(guān)系，利用矩陣乘法求R的傳遞閉包，并畫出t （R）的關(guān)系圖。. S, 的極小元、最小元、極大元、最大元是什么.集合 A 2,3,6,12,24,36上的偏序關(guān)系為整除關(guān)系。設(shè)B 6,12,C 2,3,6,試畫出哈斯圖，并求 A, B, C的最大元素、極大元素、下界、上確界。.對(duì)于實(shí)數(shù)集合R,在下表所列的二元遠(yuǎn)算是否具有左邊一列中的性質(zhì)，請(qǐng)?jiān)谙鄳?yīng)位上填寫“Y”

12、或 “N”。MaxMin+可結(jié)合性可交換性存在幺兀存在零兀.設(shè) B4=e , a , b , ab ,運(yùn)算 *如下表,*eababeeababaaeabbbbabeaababbae則是一個(gè)群（稱作 Klein四元群）。.設(shè) S = R - -1 （R 為實(shí)數(shù)集），a b a b ab。(1)說(shuō)明S，是否構(gòu)成群；(2)在S中解方程2 x 3 7 o.設(shè)X =1,2,3,4, R是X上的二元關(guān)系，. R= 1,1 , 3,1 , 1 ,3 , 3 ,3 , 3,2 , 4,3 , 4,1 , 4 2 , 1 ,2 (1)畫出R的關(guān)系圖。寫出 R的關(guān)系矩陣。說(shuō)明 R是否是自反、反自反、對(duì)稱、傳遞的。

13、.設(shè)I是負(fù)整數(shù)集合，定義二個(gè)雙射函數(shù)f、g ,f :I I f x x 1,1 ,2,2 ,g: I N g x x 1 1,0 , 2,1 , ,求g o f ,并說(shuō)明其是否是雙射函數(shù)。.設(shè)M= 0o,60o,120o,240o,300o,180o表示平面上幾何圖形順時(shí)針旋轉(zhuǎn)的六種位置，定義一個(gè)二元運(yùn)算對(duì)M中任一元素a,b有2*=圖形旋轉(zhuǎn)(a+b)的角度，并規(guī)定當(dāng)旋轉(zhuǎn)到360o時(shí)即為0o。是否是群。*0o60o120o180o240o300o0o0o60o120o180o240o300o60o60o120o180o240o300o0o120o120o180o240o300o0o60o180o

14、180o240o300o0o60o120o240o240o300o0o60o120o180o300o300o0o60o120o180o240o.求圖中的一棵最小生成樹。v731.已知某有向圖的鄰接矩陣如下:路徑的條數(shù)。32.33.V2V3V40 試求：V3到V1的長(zhǎng)度為4的有向F31.已知某有向圖的鄰接矩陣如下:路徑的條數(shù)。32.33.V2V3V40 試求：V3到V1的長(zhǎng)度為4的有向F圖所示帶權(quán)圖中最優(yōu)投遞路線并求出投遞路線長(zhǎng)度（郵局在D點(diǎn)）。30G201CB4。123D的可達(dá)矩陣，并判斷圖的連通性。34.有向圖G如圖所示，試求：（1）求G的鄰接矩陣Ao （2）求出A2、A3和A4 （3） v1到V4長(zhǎng)度為1、2、3和4的路徑有多少（4）求出可達(dá)矩陣 P。35.35.畫一個(gè)有一條