(完整word版)離散數(shù)學(xué)期末考試試題(有幾套帶答案)

1、離散試卷及答案 第 1頁共 12頁 、證明題(10分) 1) ( -PA ( -QA R) V (QA R) V (P A R)=R 證明：左端-PA-QARVgVPjARj -PA-Q)AR) V(QVP)AR) ：=(-(PVQ)AR)V(QVP)ARi (PVQ)V(QVP)AR ：=(-CPVQ)V(PVQ)AZAR(W)：=R 2) x(A(x) _；B(x) = -xA(x) xB(x) 證明：x(A(x) B(x) x(F(x)VB(x)= xf(x)V xB(x)二-xA(x)V xB(x 建-xA(x) xB(x) 、求命題公式(P V (QA R)_.(P A QA R)的

2、主析取范式和主合取范式(10分) 證明： (P V (Q A R) r (P A QA R)h (P V (QA R) V(P AQA R) (-PA (-QV-R) )V (P A QA R) ：=(-PA P)V ( -PA -R) V (P A QA R) U( -PA PA R) V ( -PA PA -R) V ( PA QA -R) V ( PA QA R) V (P A QA R) :二 mOV mV mV m7 二 M3V M4V MV M6 三、推理證明題(10分) 1) CV D, (C V D) -E, -E (A A -B), (A A-B)=.(R V S)= RV

3、S 證明：(1) (C VD) -E (2) -E 乂 A A -B) (3) (C V D) (A A -B) (4) (A A -B) (R V S) (5) (C V D).(R V S) (6) C V D (7) R V S 2) x(P(x) ；Q(y) A R(x) , xP(x) =Q(y) A x(P(x) A R(x) 四、 設(shè)m是一個(gè)取定的正整數(shù)，證明：在任取 m 1個(gè)整數(shù)中，至少有兩個(gè)整數(shù)，它們的差是 m的整數(shù)倍 證明 設(shè)a1 , a2，am1為任取的 冊(cè) 1個(gè)整數(shù)，用m去除它們所得余數(shù)只能是 o, 1，m-1,由抽屜原理可知， a1，a2，am 1這阿 1個(gè)整數(shù)中至少

4、存在兩個(gè)數(shù) as和at，它們被m除所得余數(shù)相同，因此 as和at的差是m的整 數(shù)倍。 五、 已知 A B、C是三個(gè)集合，證明 A-(B U C)=(A-B) n (A-C) (15分) 證明 /x 三 A- (BU C)：二 x 三 AA x ( BU C) = AA( xBA x ：= (AAxB)A( AA x】C) ：= (A-B) A (A-C) ：= x - (A-B)n( A-C). A- (BU C) = (A-B)n( A-C) 六、已知 R、S 是 N 上的關(guān)系，其定義如下： R=| x,y :二 NA y=x2，S=| x,y 二 NA y=x+1。 求 R1、 R*S、S

5、*R、 R 1,2、S1,2 (10 分) 解：R-1=| x,y 三 NA y=x2，R*S=| x,y 三 NA y=x2+1，S*R=| x,y 三 NA y= (x+1) 2， 七、若 f:A -B 和 g:B TC是雙射，則(gf) 1=f1g1 (10 分)離散數(shù)學(xué)試題(A卷及答案) 證明(1) xP(x) P(a) -x(P(x) Q(y) A R(x) (4) P(a) .Q(y) AR(a) (5) Q(y) A R(a) (6) Q(y) (7) R(a) (8) P(a) (9) P(a) A R(a) (10) x(P(x) A R(x) (11)Q(y) A x(P(

6、x) A R(x) 離散試卷及答案 第 2頁共 12頁 證明：因?yàn)?f、g是雙射，所以 gf : A-C是雙射，所以 gf 有逆函數(shù)(gf) -1 : C-A。同理可推 f-1g-1： C-A是雙射。 因?yàn)?f-1g-1： ：存在 z ( g-1 f-1)；二存在 z ( f g) = vy,x gf：= G(gf) -1, 所以(gf) -1=f-1g-1。 R 1,2=v1,1, , S1,2=1,4。 八、 (15分)設(shè)是半群，對(duì)A中任意元a和b,如ab必有a*b b*a,證明： (1) 對(duì)A中每個(gè)元a,有a*a= a。 (2) 對(duì)A中任意元a和b,有a* b*a= a。 (3) 對(duì)A中

7、任意元a、b和c,有a*b*c = a*c。 證明 由題意可知，若a*b= b*a,則必有a= b。 (1) 由(a* a)* a=a*( a* a)，所以 a*a=a。 (2) 由 a*( a*b*a) = (a*a)*( b*a) = a*b*( a*a) = (a*b*a)*a,所以有 a*b*a= a。 (3) 由(a* c)*( a* b* c) = (a*c*a)*( b*c) = a*( b*c) = (a*b)*c = (a*b)*( c*a*c) = ( a* b* c)*( a*c)，所以有 a*b*c= a*c。 九、 給定簡單無向圖 G= ,且| V| = m | E|

8、 = n。試證：若n醉+ 2,則G是哈密爾頓圖 證明 若n訐+ 2，則 2n卅3m+ 6 (1 )。 若存在兩個(gè)不相鄰結(jié)點(diǎn) u、v使得 d( u ) + d( v ) m則有 2n= d(w) Q(x) A xP(x)二- x(P(x) Q(x) A P(x) x( P(x) V Q(x) A P(x)二- x(P(x) A Q(x)：二- xP(x) A xQ(x) h x(P(x) A Q(x) 二、求命題公式(-PQ)r(P V -Q)的主析取范式和主合取范式(10分) 解：(-P Q) (P VP)u(-PQ)V (P V-Q)=(P V Q)V (P V-Q)=(-PAP)V (P

9、V Q) ：=(PV PVQ)A ( PV PV P)=(P V P)=M匕 mOV m2V m3 四、例 5在邊長為 1的正方形內(nèi)任意放置九個(gè)點(diǎn)，證明其中必存在三個(gè)點(diǎn)，使得由它們組成的三角形(可能是退化的)面積不超三、推理證明題(10分) 1)(P (Q S) A ( -RV P) A Q ：R S 證明：(1) R 附加前提 (2) -RV P P (3) P T(1) (2),I (4) P ；(Q；S) P (5) Q；S T(3),1 (6) Q P (7) S T(5)(6),1 (8) R S CP 2) -x(P(x) V Q(x)，-x-P(x)= x Q(x) 證明：(1)

10、 x-P(x) P (2) -P(c) T(1),US (3) -x(P(x) V Q(x) P (4) P(c) V Q(c) T(3),US (5) Q(c) T(2X 4),1 (6) x Q(x) T(5),EG 離散試卷及答案 第 3頁共 12頁 過 1/8 ( 10 分)。 證明：把邊長為 1的正方形分成四個(gè)全等的小正方形，則至少有一個(gè)小正方形內(nèi)有三個(gè)點(diǎn)，它們組成的三角形(可能是退化的) 面積不超過小正方形的一半，即 1/8。 五、 已知 A B、C是三個(gè)集合，證明 An (B U C)=(A n B) U (A n C) ( 10分) 證明：T x 三 A n( BU C)：二

11、x 三 A A x 三(BU C)：二 x 三 A A( x 三 B V x 三 C)：二(x 三 A A x 三 B)V( x 三 A A x 三 C)：二 x 三(An B) V XE A QC= x e (An B)U( An C)二 An( BUC) = (An B)U( An C) 六、 7=A1，A,，An是集合 A的一個(gè)劃分，定義 R=a，b|a、b A，1=1，2，n，則 R是 A上的等價(jià)關(guān)系(15分)。 證明：-a A必有 i使得 a A，由定義知 aRa,故 R自反。 a,b A，若 aRb，_則 a,b A，即 b,a A，所以 bRa,故 R對(duì)稱。 -a,b,c A，若

12、 aRb 且 bRc，則 a,b A及 b,c A。因?yàn)?i 工 j 時(shí) A n A=.：，故 i=j，即 a,b,c A，所以 aRc，故 R傳遞。 總之 R是 A上的等價(jià)關(guān)系。 七、 若 f:A -B是雙射，則 f-1:B -A是雙射(15分)。 證明：對(duì)任意的 x A，因?yàn)?f 是從 A到 B的函數(shù)，故存在 y B,使x,y f，y,x f-1。所以,f -1是滿射。 對(duì)任意的 x A若存在 y1,y2 B，使得y1,x f-1且y2,x f-1,則有x,y1 f 且x,y 2 f。因?yàn)?f 是函數(shù)，_則 y】=y2。所 以，f 是單射。 因此 f 是雙射。 八、 設(shè)G *是群，A, *

13、和B, *是G *的子群，證明：若 AU B= G,則A= G或B= G( 10 分)。 證明 假設(shè)G且G 則存在aA, aB,且存在 b=B, b-A (否則對(duì)任意的 aA, a二B從而 A B 即 AU B=B,得B= G 矛盾。) 對(duì)于元素a*bG,若a*bA,因A是子群，a-1.叭，從而a-1 * ( a*b) = b A,所以矛盾，故a*bA。同理可證a*bB,綜合 有 a*b -AU B= G 綜上所述，假設(shè)不成立，得證 A= G或 B= G 九、 若無向圖 G是不連通的，證明 G的補(bǔ)圖 G是連通的(10分)。 證明 設(shè)無向圖G是不連通的，其k個(gè)連通分支為 G1、G2、Gk。任取結(jié)

14、點(diǎn) u、v G若 u和 v不在圖G的同一個(gè)連通分 支中，則u , v不是圖G的邊，因而u , v是圖 G的邊；若 u和 v在圖G的同一個(gè)連通分支中，不妨設(shè)其在連通分支 G (1 w i w k )中，在不同于 Gi的另一連通分支上取一結(jié)點(diǎn) w，U u , w 和w , v都不是圖G的邊，因而u , w 和w , v 都是 G的邊。綜上可知，不管那種情況， u和 v都是可達(dá)的。由 u和 v的任意性可知，G是連通的。 一、 選擇題.(每小題 2分，總計(jì) 30) 1. 給定語句如下： (1) 15 是素?cái)?shù)(質(zhì)數(shù)) (2) 10 能被 2整除，3是偶數(shù)。 (3) 你下午有會(huì)嗎？若無會(huì)，請(qǐng)到我這兒來！

15、(4) 2x+30. (5) 只有 4是偶數(shù)，3才能被 2整除。 (6) 明年 5月 1日是晴天。 以上 6個(gè)語句中，是簡單命題的為(A),是復(fù)合命題的為(B),是真命題的為(C),是假命題的是(D),真值待定的命題是(E) A：(3)(6) (1)(4)(6) (1) ( 6) B: (6) (5) C:(1)(2)(5)(6) 無真命題 3( 5) D: (1)(2) 無假命題 (1)(2)(5) E:(6) 購(6) 無真值待定的命題 離散試卷及答案 第 4頁共 12頁 2. 將下列語句符號(hào)化： (1) 4是偶數(shù)或是奇數(shù)。(A)設(shè) p： 4是偶數(shù)，q： 4是奇數(shù)離散試卷及答案 第 5頁共

16、 12頁 (2) 只有王榮努力學(xué)習(xí)，她才能取得好成績。 (B)設(shè) p：王榮努力學(xué)習(xí)，q：王榮取得好成績 (3) 每列火車都比某些汽車快。 (C)設(shè) F(x):x 是火車，G(y):y是汽車，H(x,y):x 比 y快。 A: p V q p A q p Tq B: p T q q T p p A q C:-x y (F(x) A G(y) 3. 設(shè) S=1,2,3,下圖給出了 1、設(shè)P x, y 為 x 整除 y, Qx 為 x : 2,個(gè)體域?yàn)?1,2/，求公式: _x y P x,y Q x 的真值。 2、設(shè)集合A1,2,3,4；A上的關(guān)系 R -1,1 , 1,2 , 2,1 / 2,3

17、 Q 2 =P 1,1 Q 1 上 P 2,1 Q 2 山 ii：P 1,2 Q 1 上 P 2,2 Q 2 P 1,2 i；=1,P 2,1i=0,P 2,2 i； = 1,Q 1=1,Q 2 =0 .=11上00i ii11上1 0 =1 該公式的真值是 1，真命題。 x y P x, y Q x = x P x,1 Q x P x,2 Q x P 1,1 Q 1 P1,2 Q1 P 2,1 Q 2 P 2,2 Q 2 或者 T T T T F F T F u T T T F u T T = T 2、r(R)1,1., 1,2, 2,1 , 2,3, 3,4 ,2,2 , 3,3 , 4,

18、4* s(R) 1,1 ,1,2, 2,1, 2,3, 3,4, 3,2, 43? t(R)1,1., 1,2 , 2,1, 2,3, 3,4, 1,3 , 2,2 , 2,4 , 1,4? （2）極小元、最小元是 1,極大元、 最大元是 24 四、3、（ 1） R是A上的偏序關(guān)系 離散試卷及答案 7 ) 第 8頁共 12頁 pqp = 一一 p q p 二 p q p 二 p =p q q =p q p q i 2, .主合取范式| . o , 安徽大學(xué) 2004-2005學(xué)年第二學(xué)期離散數(shù)學(xué)期末考試試卷（ A卷）參考答案 一、單項(xiàng)選擇 在自然數(shù)集 N上，下列哪種運(yùn)算是可結(jié)合的？（ A. a

19、* B. a * b = max a, b C. a* D. a* b = a b(mod 3) 下列代數(shù)系統(tǒng)S，*中，哪個(gè)是群? 離散試卷及答案 7 ) 第 9頁共 12頁 A. S =0,1,3,5，*是模 7 加法 B. S=Q （有理數(shù)集合），*是一般乘法 c. S二Z （整數(shù)集合），*是一般減法 D. S =1,3,4,5,9，*是模 11 乘法 若H，A. n整除m C. n整除m且 m整除n D. B. 下面哪個(gè)集合關(guān)于指定的運(yùn)算構(gòu)成環(huán)？（ =n， G = m整除n n不整除m且 m不整除n A. a b3 2 |a, b Z，關(guān)于數(shù)的加法和乘法 B. n階實(shí)數(shù)矩陣，關(guān)于矩陣的加

20、法和乘法 C. a b 2 |a,b Z，關(guān)于數(shù)的加法和乘法 D. a,bZ 關(guān)于矩陣的加法和乘法 J 在代數(shù)系統(tǒng)中，整環(huán)和域的關(guān)系為（ ） A.域一定是整環(huán) B. 域不一定是整環(huán) C.整環(huán)一定是域 D. 域一定不是整環(huán) D. N是自然數(shù)集，空是小于等于關(guān)系，則（N,乞）是（ A.有界格 B.有補(bǔ)格 C.分配格 D. 有補(bǔ)分配格 圖 1-1給岀的哈斯圖表示的格中哪個(gè)元素?zé)o補(bǔ)元？（ A. a B. c C. e D. 圖 1-1 d g 離散試卷及答案 7 ) 第 10頁共 12頁 A. (1，1，2，2, 3) B. (1，3, 4, 4, 5) 給定下列序列，可構(gòu)成無向簡單圖的結(jié)點(diǎn)度數(shù)序列的

21、是（ 離散試卷及答案 第 11頁共 12頁 9 歐拉回路是（ ）。 2 證明：（1）證明在格中成立：（a * b）二（c* d） _ （a 二 c） * （b 二 d）。 （5分） （2）證明布爾恒等式：（a * c）二（a * b）二（b* c） = （a * c）二（a * b）。 （5分）C. (0, 1, 3, 3, 3) D. (1 , 1, 2, 2, 2) A.路徑 B. 簡單回路 C.既是基本回路也是簡單回路 10 哈密爾頓回路是（ ）。 D.既非基本回路也非簡單回路 簡單回路 D.既非基本回路也非簡單回路 、填空題（以下每個(gè)下劃線為一空，請(qǐng)按要求填入合適的內(nèi)容。每空 2 分，

22、共 30分） 1設(shè)S是非空有限集，代數(shù)系統(tǒng)（p（s）,u,n）中，p（s）對(duì)u運(yùn)算的單位元是 ，零元是 ， p（s）對(duì)a運(yùn)算 的單位元是 。 2 在運(yùn)算表 2-1中空白處填入適當(dāng)符號(hào)，使 （a,b,c,）成為群。 ， ， ， 。 3 設(shè) H 二0,4,8 , :：: H , 12 是群：:：N12, 12 的子群，其中 N12 二0,1,2,11 , 12 是模 12 加法，則:：:N12, 12 有 個(gè)真子群，H的左陪集3H = , 4H二 。 4 設(shè)：:：A,，乜是一個(gè)布爾代數(shù)，如果在 A上定義二元運(yùn)算 二為： a b c a a b a b c c c a 二 b = （a b） （a

23、b），則：A,三：是一個(gè) 。 表 2-1 5 任何一個(gè)具有2n個(gè)元素的有限布爾代數(shù)都是 _ _。 6 若連通平面圖G有 4個(gè)結(jié)點(diǎn)，3個(gè)面，則G有 條邊。 7 一棵樹有兩個(gè)結(jié)點(diǎn)度數(shù)為 2，一個(gè)結(jié)點(diǎn)度數(shù)為 3,三個(gè)結(jié)點(diǎn)度數(shù)為 4,它有 個(gè)度數(shù)為 1的結(jié)點(diǎn) 8 無向圖G是由k（ k _2）棵數(shù)組成的森林，至少要添加 條邊才能使 G成為一棵樹。 三、求解題（20分） 1 試寫出：:：N6, 6 中每個(gè)子群及其相應(yīng)的左陪集。 （6 分） 2 若一個(gè)有向圖 G是歐拉圖，它是否一定是強(qiáng)連通的？若一個(gè)有向圖 3有向圖G如圖 3-1所示。 （1） 求G的鄰接矩陣A ； （2分） （2） G中V1到V4長度為 4

24、的路徑有幾條？ （2分） （3） G中V1到自身長度為 3的回路有幾條？ （2分） （4） G是哪類連通圖？ （2分） 四、證明題（30分） 1 設(shè)：:G,* 是一群，x G。定義：a b = a* x G是強(qiáng)連通的，它是否一定是歐拉圖？說明理由。 （6分） 圖 3-1 b , - a,bG。證明 G/也是一群 離散試卷及答案 第 12頁共 12頁 3 證明：（1）在 6個(gè)結(jié)點(diǎn) 12條邊的連通平面簡單圖中，每個(gè)面由 3 條邊圍成。 （5分） （2）證明當(dāng)每個(gè)結(jié)點(diǎn)的度數(shù)大于等于 3 時(shí)，不存在有 7條邊的簡單連通平面圖。 安徽大學(xué) 2004-2005學(xué)年第二學(xué)期離散數(shù)學(xué)期末考試試卷（ A卷）參考

25、答案 一、 單項(xiàng)選擇 1. B; 2.D; 3.A; 4.C; 5.A; 6.C; 7.B; 8.D; 9.B; 10.C. 二、 填空題 1 ：,S , S ； 2 c, b , b , a ； 3 5 , 3,7,11 , 4,8,0 ； 4 交換群； 5 同構(gòu)； 6 5 ; 7 9 ; 8 k -1。 三、 求解題 1 解：子群有：:0, 6 ,譏0,3, 6 , ： 0,2,4, 6 。 :0, 6 的左陪集為：0 , 1 , 2 , 3 , 4 , 5 0,3, 6 的左陪集為：0,3 , 1,4 , 2,5 離散試卷及答案 第 13頁共 12頁 中, 離散試卷及答案 第 16頁共

26、12頁 S關(guān)于max運(yùn)算的么兀是 _ ，零兀是 _ 2.設(shè)10為模10加法，則在 :0,1川 1,9, 10 a 中，元素5的階為 _ ， 6的階為 3.設(shè)S|10 =1,2,5,10,11,22,55,110 , gcd和Icm分別為求最大公約數(shù)和最小公倍數(shù)運(yùn)算, 則在布爾代數(shù):：:SnQ,gcd,lcm 中，原子的個(gè)數(shù)為= 一，元素22的補(bǔ)元為一 4.在格：:：5. 一個(gè)具有n個(gè)結(jié)點(diǎn)的簡單連通無向圖的邊數(shù)至少為 _ ，至多為= 三、解答題（第 1小題 12分，第 2小題 8分，共 20分） 1.設(shè)圖G如圖 1所示， V4 離散試卷及答案 第 17頁共 12頁 G，使得對(duì)于-x G有f（x）

27、 = 證明：f是：:G, 安徽大離散、單項(xiàng)選擇題（每小題 2分，共 20分） 1.A ； 2.C ； 3.D ； 4.D ； 5.C ； 6.B ； 7.B ； 8.B ； 9.A ； 10.A 、填空題（每小空 2分，共 20分） 0， 1 ； 2. 2， 5 ； 3. 3， 5 ； 4. a ， b ； 5. n-1 ， n(n -1)/2 0 0 1 0 1 1 r 0 1. （1） G的鄰接矩陣 A = 0 1 0 1 0 1 2 1 0 2 2 2、 0 2 4 2、 A(2)= 0 1 0 1 ； A= 0 0 2 0 ；A(4)= 0 2 0 2 0 0 2 0 0 2 0 2 0 0 4 0 0 1 0 1丿 0 0 2 0 0 2 0 2 從v1到v4的長為2,3, 4的路徑的條數(shù)分別為1,2,2 ； 0 1 1 r 0 111 G的可達(dá)矩陣為P = 0 111 10 0 0 故G的強(qiáng)連通分圖的結(jié)點(diǎn)集為 w，V2, V3N4。 12 分 三、解答題（第 1小題 12分，第 2小題 8分，共 20 分） 離散試卷及答案 第 18頁共 12頁 2. : N8, 8 的子群為：:0, 8 ， :： 0, 2,