離散數(shù)學(xué)試題(60學(xué)時(shí))

1、離散數(shù)學(xué)試題A一、解答題(本大題共7小題, 每小題5分, 共35分)1. 用命題邏輯推證語句:“如果你不走, 那么我和她都不留”與“如果我和她有一個(gè)留下, 那么你就得必須走”具有相同的邏輯含義.2. 設(shè)給定解釋I如下: 個(gè)體域DI = 3, 6, 8, 謂詞P(x): x3, G(x): x > 5, R(x): x9, 求下列謂詞公式的真值. (寫出判斷過程, 僅給出結(jié)果而無過程不得分)(1) "x(R(x)®P(x)G(5).(2) $x(P(x)G(x).3. 設(shè)A=a, b, c, A上二元關(guān)系R=áa, añ, áa, c

2、41;, áb, añ, 用關(guān)系矩陣法求最小的自然數(shù)m, n, m < n使得Rm = Rn, 并求其傳遞閉包與對(duì)稱閉包.4. 設(shè)(R*, ×)為代數(shù)系統(tǒng), 其中R*=R-0, × 是數(shù)的乘法, 下述映射f是否為R*到R*的同態(tài).(1) f (x) = x2, (2) f (x) = -x, (3) f (x) = x.5. 設(shè)無向圖G各結(jié)點(diǎn)的度數(shù)都是3, 且結(jié)點(diǎn)數(shù)n與邊數(shù)m之間有下面的關(guān)系:2n3= m.(1) G中結(jié)點(diǎn)數(shù)n與邊數(shù)m各是多少？(2) 在同構(gòu)的意義下能否畫出G的一個(gè)二部圖？若能, 請(qǐng)畫出一個(gè)二部圖.6. 設(shè)函數(shù)f : A®

3、B, g : B®C, h : C®D, 其中A=a, b, c, B=x, y, z, C=1, 2, 3, 4, D=a, b, g, f =áa, yñ, áb, xñ, ác, yñ, g =áx, 2ñ, áy, 1ñ, áz, 4ñ, h =á1, añ, á2, gñ, á3, añ, á4, bñ. 判斷(1) f, g, h各是什么類型的函數(shù)？(2) hgf是

4、什么類型的函數(shù)？它有反函數(shù)嗎？為什么？7. 設(shè)平面圖G有兩個(gè)連通分支, 一個(gè)為K3, 另一個(gè)為K4. 請(qǐng)畫出G的對(duì)偶圖G*, 問G*是歐拉圖嗎？為什么？是哈密頓圖嗎？為什么？(針對(duì)判斷結(jié)果, 給出詳細(xì)的理由)二、計(jì)算題(本大題共5小題, 每小題5分, 共25分)1. 設(shè)集合A=Æ, a, b, B=a, Æ, r (A), r (B)為其冪集, 計(jì)算r (A)r (B).2. 設(shè)G =, G上的運(yùn)算´是矩陣乘法. 已知(G, ´)構(gòu)成群. 在群(G, ´)中, 指出每個(gè)元素的階; 找出每一元素的逆元, 求出G的全部子群.3. 設(shè)R=á

5、1, 1ñ, á1, 3ñ, á2, 1ñ, á2, 2ñ, á3, 3ñ, á4, 3ñ, á4, 4ñ是集合A=1, 2, 3, 4上的二元關(guān)系.(1) 畫出R的關(guān)系圖;(2) 寫成R的關(guān)系矩陣; (3) 說明R是否具有自反、反自反、對(duì)稱、反對(duì)稱、傳遞性質(zhì).4. 求命題公式(P®(QR)(ØP®(ØQ®R)的主合取范式.5. 設(shè)集合A=1, 2, 3, 6, 9, 18, 為整除關(guān)系.(1) 畫出áA,

6、 ñ的哈斯圖;(2) 求子集B = 3, 6, 9的極大元、極小元、最大元、最小元.三、證明題(本大題共2小題, 每小題10分, 共20分)1. 設(shè)(G1,), (G2,)都是群(G,)的子群.(1) 證明: (G1G2,)也是(G1,), (G2,)及(G,)的子群.(2) 若|G1| = 5, |G2| = 6, 問 |G1G2| 是多少？為什么？2. 給定集合A=a, b, c, r (A)是A的冪集, (r (A), )為代數(shù)系統(tǒng), 在r (A)上又定義二元關(guān)系R如下:X R Y 當(dāng)且僅當(dāng) Xb = Yb, X, YÎr (A).、分別為集合的并、交運(yùn)算, 求證:(

7、1) R是r (A)上的等價(jià)關(guān)系;(2) R是r (A)上的關(guān)于的同余關(guān)系;(3) 求商集r (A)/R.四、應(yīng)用題 (本大題共2小題, 每小題10分, 共20分)1. 對(duì)下面推理進(jìn)行符號(hào)化, 并構(gòu)造其證明.會(huì)操作計(jì)算機(jī)的人都認(rèn)識(shí)26個(gè)英文字母; 文盲都不認(rèn)識(shí)26個(gè)英文字母; 有的文盲是很聰明的. 所以有的很聰明的人不會(huì)操作計(jì)算機(jī).(個(gè)體域D: 所有人的集合. 設(shè)F(x): x會(huì)操作計(jì)算機(jī), G(x): x認(rèn)識(shí)26個(gè)英文字母, H(x): x是文盲, R(x): x是很聰明的)2. 設(shè)有n個(gè)人P1, P1, , Pn, 其中某些人在做決策時(shí)能夠互相影響, 而這種影響一般是單方面的, 即如果Pi

8、影響Pj, 那么Pj不一定影響Pi. 并且每個(gè)人不影響他自己. 另外可以考慮二級(jí)影響, 即如果存在一條從Pi到Pj長(zhǎng)度為2的路徑, 則Pi對(duì)Pj有二級(jí)影響. 類似地, 如果存在一條從Pi到Pj長(zhǎng)度為r的路徑, 那么Pi對(duì)Pj有r級(jí)影響.如圖給出了一個(gè)設(shè)計(jì)組中6個(gè)成員之間描述影響關(guān)系的有向圖. 問設(shè)計(jì)組中哪些不同成員之間有二級(jí)影響? 保證設(shè)計(jì)組中成員沒有影響的最小級(jí)數(shù)是多少？···P3P1P5P4···P2P6離散數(shù)學(xué)答案A一、解答題(本大題共7小題, 每小題5分, 共35分)1. 設(shè)P: 你走, Q: 我留, R: 她留. 則兩命題分

9、別符號(hào)化為：Ø P® ØQØR, QR®P.由于 Ø P® ØQØR Û P(ØQØR)Û PØ(QR)Û (QR) ®P.故二者具有相同的邏輯含義.2. (1) "x(R(x)®P(x)G(5) Û (R(3)®P(3)(R(6)®P(6)(R(9)®P(9)G(5)Û (TFF)FÛ F.(2) $x(P(x)G(x) Û (P(3)G(3)(

10、P(6)G(6)(P(9)G(9)Û (TF)(FT)(FT) Û T.3. 由于MR=, , .故當(dāng)m = 2, n = 3時(shí), Rm = Rn. 其傳遞閉包對(duì)應(yīng)的矩陣為：=+=.對(duì)稱閉包對(duì)應(yīng)的矩陣為: Ms =.4. (1) f (x×y) = (xy)2 =x2 ×y2 = f (x)× f (y), 因而是同態(tài).(2) f (x×y) = -xy(-x)(-y)= f (x)× f (y), 不是同態(tài).(3) f (x×y) =x×yx ×y = f (x)× f (y), 不

11、是同態(tài).5. (1) 由握手定理可得, 3n=2m, 與條件2n3 = m聯(lián)立解得n = 6, m = 9.(2) 在同構(gòu)的意義下能畫出G的一個(gè)二部圖K3,3.6. (1) f既不是單射，也不是滿射； g是單射，但不是滿射, h是滿射，但不是單射，f, g, h都不是雙射。···°·°°°···°(2) hgf: A®D, 且hgf (x)= , 既不是單射，也不是滿射, 當(dāng)然不是雙射, 從而無反函數(shù)。7. 畫出G的對(duì)偶圖G*如圖所示。由于G*中有4個(gè)3度結(jié)點(diǎn), 故

12、G*不是歐拉圖.而在G*中, 任意兩個(gè)結(jié)點(diǎn)的度數(shù)之和大于結(jié)點(diǎn)數(shù)5, 由奧爾定理可知, G*是哈密頓圖.二、計(jì)算題(本大題共5小題, 每小題5分, 共25分)1. r (A)=Æ, Æ, a, b, Æ, a, b,r (B)=Æ, a, Æ, a, Æ, r (A)r (B)=Æ.2. 在群(G, ´)中, 元素a為單位元，故其階為1，逆元為a;而b2 = a, 故元素b的階為2, 逆元為b;由于c2 = b, c3 = d, c4= a, 故元素c的階為4, 逆元為c3 = d;由于d2 = b, d3 = c,

13、 d4= a, 故元素d的階為4, 逆元為d3 = c.G的全部子群: a, <b>, <c>=<d>.3. 設(shè)R=á1, 1ñ, á1, 3ñ, á2, 1ñ, á2, 2ñ, á3, 3ñ, á4, 3ñ, á4, 4ñ是集合A=1, 2, 3, 4上的二元關(guān)系.(1) 略;(2) MR=; (3) R具有自反性、反對(duì)稱、不具有反自反、對(duì)稱、傳遞性質(zhì).4. (P®(QR)(ØP®(

14、16;Q®R) Û(ØP(QR)(P(QR)Û(ØPQ)(ØPR)(P(QR)Û(ØPQ)(ØRR)(ØPR)(ØQQ)(P(QR)Û(ØPQR)(ØPQØR)(ØPQR)(ØPØQR)(PQR)·18·····69231ÛÕ(0, 4, 5, 6).5. (1) 畫出áA, ñ的哈斯圖;(2) 子集B = 3, 6,

15、 9的極大元為9, 6、極小元3、無最大元、最小元為3.三、證明題(本大題共2小題, 每小題10分, 共20分)1. (1) "a, bÎ G1G2, 則a, bÎG1, a, bÎG2, 由于(G1,), (G2,)都是群(G,)的子群, 則ab-1ÎG1, G2, 故ab-1ÎG1G2.(G1G2,)也是(G1,), (G2,)及(G,)的子群.(2) 由于(G1G2,)是(G1,), (G2,)的子群, 故有|G1G2| ³ 1, 又|G1G2| | |G1|, |G1G2| | |G2|故|G1G2| = 1.2.

16、(1) R在r (A)上自反性、對(duì)稱性顯然. 其傳遞性為: 若X R Y且Y R Z, 則有Xb = Yb, Yb = Zb, 從而有Xb = Zb, 故X R Z.(2) 由于R是r (A)上的等價(jià)關(guān)系, 若X R Y, 則Xb = Yb. 對(duì)于任意的ZÎr (A), 由集合的分配律, 有(XZ)b = (Xb)(Zb)=(Yb)(Zb) = (YZ)b.故(XZ)R(YZ). 因?yàn)榧蠞M足交換律, 類似地, 有(ZX)R(ZY), 故R是r (A)上的關(guān)于的同余關(guān)系.(3) 由r (A)=Æ, a, b, c, a, b, a, c, b, c, a, b, c, 按等

17、價(jià)關(guān)系R可得其等價(jià)類為: Æ, a, c, a, c，b, a, b, b, c, a, b, c, 故商集r (A)/R=a, b.四、應(yīng)用題(本大題共2小題, 每小題10分, 共20分)1. 符號(hào)化：設(shè)F(x): x會(huì)操作計(jì)算機(jī), G(x): x認(rèn)識(shí)26個(gè)英文字母, H(x): x是文盲, R(x): x是很聰明的。前提："x(F(x)®G(x), "x(H(x)®ØG(x), $x(H(x)R(x),結(jié)論：$x(R(x)ØF(x).證明：序號(hào)斷言依據(jù)1$x(H(x)R(x)P2H(c)R(c)T, 1, ES3H(c)

18、T, 2, 簡(jiǎn)化式4R(c)T, 2, 簡(jiǎn)化式5"x(H(x)®ØG(x)P6H(c)®ØG(c)T, 5, US7ØG(c)T, 3, 6, 假言推理8"x(F(x)®G(x)P9F(c)®G(c)T, 8, US10ØF(c)T, 7, 9, 拒取式11R(c)ØF(c)T, 4, 10, 合取式12$x(R(x)ØF(x)T, 11, EG2. 圖的鄰接矩陣為A, 則A2, A3, A40.故設(shè)計(jì)組中不同成員之間有二級(jí)影響的有序?qū)κ? áP3, P5ñ

19、;, áP4, P5ñ, áP6, P2ñ, áP6, P5ñ. 設(shè)計(jì)組中成員沒有影響的最小級(jí)數(shù)是: r4.離散數(shù)學(xué)試題B一、解答題(本大題共7小題, 每小題5分, 共35分)1. 將下列自然語言按要求進(jìn)行符號(hào)化.(1) 人不犯我, 我不犯人; 人若犯我, 我必犯人. (用命題邏輯)(2) 會(huì)叫的狗未必咬人. (用謂詞邏輯)2. 如果個(gè)體域是集合a, b, c, 試消去公式"x$y (x+y = 0)中的量詞.3. 設(shè)A=a, b, c, A上二元關(guān)系R=áa, añ, áa, cñ,

20、 áb, añ, 求關(guān)系R的自反閉包、對(duì)稱閉包和傳遞閉包.4. 設(shè)Aa, b, S是A上的所有函數(shù)集合, Sf1, f2, f3, f4, 其中f1 : aa, bb; f2: aa, ba; f3 : ab, bb; f4 : ab ba.于是(S, )是一個(gè)代數(shù)系統(tǒng), 是函數(shù)的合成運(yùn)算, 試構(gòu)造出運(yùn)算表, 考察運(yùn)算是否有單位元, 哪些元素有逆元.5. 在有21條邊的無向圖G中, 有3個(gè)4度結(jié)點(diǎn), 其余均為3度結(jié)點(diǎn), 問無向圖共有多少個(gè)結(jié)點(diǎn).6. 在整數(shù)集Z上定義下列運(yùn)算: (1) ab = 2ab; (2) ab = a+b+2; (3) ab = a+2b. 問整數(shù)集

21、Z關(guān)于哪些運(yùn)算構(gòu)成代數(shù)系統(tǒng)？哪些運(yùn)算能構(gòu)成半群？哪些運(yùn)算能構(gòu)成群？(對(duì)每種情況給出具體的理由)7. 分別構(gòu)造滿足下列條件的圖.(1) 畫一個(gè)有一條歐拉回路和一條漢密頓回路的圖.(2) 畫一個(gè)有一條歐拉回路但沒有漢密頓回路的圖.(3) 畫一個(gè)沒有歐拉回路但有一條漢密頓回路的圖. 二、計(jì)算題(本大題共5小題, 每小題5分, 共25分)1. 設(shè)P表示“今天天氣好”，Q表示“我們?nèi)ヂ糜巍? 試用最簡(jiǎn)單明了的漢語描述下面公式所表達(dá)的含義: (¬PQ) (P¬Q)¬ (¬Q¬P).2. 設(shè)S = Q×Q, 其中Q為有理數(shù)集合, 定義S上的二元運(yùn)算

22、*,"áa, bñ, áx, yñS, áa, bñ*áx, yñ = áax, ay+bñ,(1) 求á3, 4ñ*á1, 2ñ.(2) 已知á-1, 3ñ*áa, bñ = á-5,1ñ, 求a, b.(3) *是可交換的嗎？是可結(jié)合的嗎？3. 設(shè)集合A=1, 2, 3, 4, 5, A上的等價(jià)關(guān)系R的等價(jià)類為: M1=1, 2, 3, M2=4, 5. (1) 寫出等價(jià)關(guān)系R;(2

23、) 寫出R的關(guān)系矩陣; (3) 畫出關(guān)系圖.4. 求公式(PQ)®(QR)的主析取范式.5.設(shè)A=a, b, c, d, e, R為A上的關(guān)系, R=áa, dñ, áa, cñ, áa, bñ, áa, eñ, áb, eñ, ác, eñ, ád, eñIA, 試畫(A, R)的哈斯圖, 并求A中的最大元, 最小元, 極大元, 極小元.三、證明題(本大題共2小題, 每小題10分, 共20分)1. 設(shè)G = 2m3n | m, nÎQ

24、(Q是有理數(shù)集合),“*”是數(shù)的乘法.(1) 證明(G, *)是群;(2) 設(shè)映射f : G®G, f (2m3n)= 2m, 證明f是群(G, *)上的自同態(tài)映射.2. (1) 若函數(shù)f : T®U, f是單射; 函數(shù)g, h : S®T, 滿足fg = fh, 證明：g = h.(2) 給出函數(shù)f, g, h的實(shí)例, f : T®U, g, h : S®T, fg = fh, 但gh.四、應(yīng)用題(本大題共2小題, 每小題10分, 共20分)1. 對(duì)下面推理進(jìn)行符號(hào)化, 并構(gòu)造其證明.沒有不守信用的人是可信賴的; 有些可以信賴的人是受過教育的

25、人; 因此有些受過教育的人是守信用的. (個(gè)體域D: 所有人的集合. 設(shè)F(x): x是守信用的人; G(x): x是可信賴的人; H(x): x是受過教育的人.)2. 給定圖D如圖所示.(1) 用矩陣的方法確定D中長(zhǎng)度為4的路徑的數(shù)目, 其中有幾條回路？····v1v2v3v4(2) 寫出D的可達(dá)矩陣.離散數(shù)學(xué)答案B一、解答題(本大題共7小題, 每小題5分, 共35分)1. 將下列自然語言按要求進(jìn)行符號(hào)化.(1) 設(shè)P: 人犯我, Q: 我犯人, 則命題符號(hào)化為：(ØP® ØQ)(P®Q).(2) 設(shè)特性謂詞D(

26、x): x是狗, F(x): x會(huì)叫, G(x): x咬人. 則命題符號(hào)化為$x(D(x)F(x)ØG(x).2. "x$y (x+y = 0) Û (a+a=0)(a+b=0)(a+c=0)(b+a=0)(b+b=0)(b+c=0)(c+a=0)(c+b=0)(c+c=0).3. R的自反閉包為：r(R)=áa, añ, áb, bñ, ác, cñ, áa, cñ, áb, añ.對(duì)稱閉包s(R)=áa, añ, áa, c

27、1;, ác, añ, áb, añ, áa, bñ.傳遞閉包t(R)=áa, añ, áa, cñ, áb, añ, áb, cñ.4.運(yùn)算表為：f1f2f3f4f1f1f2f3f4f2f2f2f3f3f3f3f3f3f3f4f4f3f2f1其中：f1是單位元, f4有逆元，且f4的逆元為f4。5. 由握手定理可得3´4+3(n-3)=2´21解得n=13.6. 整數(shù)集Z關(guān)于這三類運(yùn)算都構(gòu)成代數(shù)系統(tǒng)。能構(gòu)成半群的運(yùn)算為：，*。能構(gòu)成半

28、群的運(yùn)算為：*。7. ················(1) (2) (3)二、計(jì)算題(本大題共5小題, 每小題5分, 共25分)1. 化簡(jiǎn)命題公式(¬PQ) (P¬Q)¬ (¬Q¬P)Û ¬ (¬PQ)(P¬Q)¬ (Q¬P)Û (P¬Q)(P¬Q)(¬QP)Û (P¬

29、;Q)。簡(jiǎn)單漢語描述：今天天氣好, 我們不去旅游。2. á3, 4ñ*á1, 2ñ=á3´1, 3´2+4ñ=á3, 10ñ.(2) 因?yàn)?#225;-1, 3ñ*áa, bñ = á-1´a, -1´b+3ñ=á-5,1ñ, 故a=5, b=2.(3) 易于驗(yàn)證*是不可交換的；但卻是可結(jié)合的。3. (1) 等價(jià)關(guān)系為R = M1´ M1M2 ´M2= á1, 1ñ,

30、 á2, 2ñ, á3, 3ñ, á1, 2ñ, á1, 3ñ, á2, 1ñ, á2, 3ñ, á3, 1ñ, á3, 2ñá4, 4ñ, á5, 5ñ, á4, 5ñ, á5, 4ñ= IAá1, 2ñ, á1, 3ñ, á2, 1ñ, á2, 3ñ, á3, 1ñ, á3, 2ñ, á4, 5ñ, á5, 4ñ(2) R的關(guān)系矩陣為：··5213··4MR=。 (3) 關(guān)系圖：4. (PQ)®(QR) Û Ø (PQ)(QR)Û (Ø PØQ)(QR)Û (Ø PØQ)(RØR)(PØP)(QR)