版權(quán)說(shuō)明:本文檔由用戶(hù)提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、離散數(shù)學(xué)期末復(fù)習(xí)題參考答案一、填空題(每空 1 分,共 20分)1、集合 A 上的偏序關(guān)系的三個(gè)性質(zhì)是自反性、反對(duì)稱(chēng)性和傳遞性。2、一個(gè)集合的冪集是指該集合所有子集的集合。3、集合 A=b,c , B=a,b,c,d,e ,則 A ?B=a,b,c,d,e 。4、集合 A=1,2,3,4 , B=1,3,5,7,9 ,則 A?B=1,3 。5、若 A 是 2 元集合 , 則 2A 有 4 個(gè)元素。6、集合 A=1,2,3 ,A 上的二元運(yùn)算定義為: a* b = a 和b兩者的最大值,則 2*3= 3 。7、設(shè) A=a, b,c,d, 則A= 4 。8、對(duì)實(shí)數(shù)的普通加法和乘法,0 是加法的冪等
2、元, 1 是乘法的冪等元。9、設(shè) a,b,c 是阿貝爾群 的元素,則 -(a+b+c)=(-a)+( -b)+( -c) 。10、一個(gè)圖的哈密爾頓路是一條通過(guò)圖中所有結(jié)點(diǎn)一次且恰好一次的路。11、不能再分解的命題稱(chēng)為原子命題,至少包含一個(gè)聯(lián)結(jié)詞的命題稱(chēng)為復(fù)合命題。12、命題是能夠表達(dá)判斷(分辯其真假)的陳述語(yǔ)句。13、如果 p 表示王強(qiáng)是一名大學(xué)生,則 p表示王強(qiáng)不是一名大學(xué)生。14、與一個(gè)個(gè)體相關(guān)聯(lián)的謂詞叫做一元謂詞。15、量詞分兩種:全稱(chēng)量詞和存在量詞。16、設(shè) A 、 B 為集合,如果集合 A 的元素都是集合 B 的元素,則稱(chēng) A 是 B 的子集。17、集合上的三種特殊元是單位元、零元及
3、可逆元。18、設(shè) A=a, b ,則 (A) 的四個(gè)元素分別是:空集, a ,b ,a, b 。19、代數(shù)系統(tǒng)是指由集合及其上的一元或二元運(yùn)算符組成的系統(tǒng)。20、設(shè) 是代數(shù)系統(tǒng),其中是 *1,*2 二元運(yùn)算符,如果 * 1,* 2都滿(mǎn)足交換律、結(jié)合律, 并且* 1和*2滿(mǎn)足吸收律,則稱(chēng) 是格。21、集合 A=a,b,c,d ,B=b ,則 A B= a, c,d 。22、設(shè) A=1, 2, 則A= 2 。23、在有向圖中,結(jié)點(diǎn) v 的出度 deg+(v) 表示以 v 為起點(diǎn)的邊的條數(shù),入度 deg-(v)表示以 v 為終點(diǎn)的邊的條數(shù)。24、一個(gè)圖的歐拉回路定義為一條通過(guò)圖中所有邊一次且恰好一次
4、的回路。25、不含回路的連通圖是樹(shù)。26、不與任何結(jié)點(diǎn)相鄰接的結(jié)點(diǎn)稱(chēng)為孤立結(jié)點(diǎn)。27、推理理論中的四個(gè)推理規(guī)則是全稱(chēng)指定規(guī)則(US 規(guī)則)、全稱(chēng)推廣規(guī)則 (UG 規(guī)則 )、存在指定規(guī)則 (ES 規(guī)則) 、存在推廣規(guī)則 (EG 規(guī)則 )。二、判斷題(每題 2 分,共 20分)1、空集是唯一的。 2、對(duì)任意的集合 A, A 包含 A。 3、恒等關(guān)系不是對(duì)稱(chēng)的,也不是反對(duì)稱(chēng)的。4、集合 1,2,3,3 和 1,2,2,3 是同一集合。 5、圖 G 中,與頂點(diǎn) v 關(guān)聯(lián)的邊數(shù)稱(chēng)為點(diǎn) v 的度數(shù),記作 deg(v)。 6、在實(shí)數(shù)集上,普通加法和普通乘法不是可結(jié)合運(yùn)算。7、對(duì)于任何一命題公式,都存在與其等
5、價(jià)的析取范式和合取范式。8、設(shè)( A,* )是代數(shù)系統(tǒng), a A,如果 a*a a,則稱(chēng) a為( A , * )的等冪元。 9、設(shè) f: A B, g: BC。若 f,g 都是雙射,則 gf 不是雙射。 10、無(wú)向圖的鄰接矩陣是對(duì)稱(chēng)陣。 11、一個(gè)集合不可以是另一個(gè)集合的元素。12、映射也可以稱(chēng)為函數(shù),是一種特殊的二元關(guān)系。13、群中每個(gè)元素的逆元都不是惟一的。14、 是格。 15、樹(shù)一定是連通圖。 16、單位元不是可逆的。 17、一個(gè)命題可賦予一個(gè)值,稱(chēng)為真值 。18、復(fù)合命題是由連結(jié)詞、標(biāo)點(diǎn)符號(hào)和原子命題復(fù)合構(gòu)成的命題。19、任何兩個(gè)重言式的合取或析取不是一個(gè)重言式。20、設(shè) f:AB,
6、g:BC。若 f, g都是滿(mǎn)射,則 g?f 不是滿(mǎn)射。 21、集合 1,2,3,3 和 1,2,3 是同一集合。 22、零元是不可逆的 。23、一般的,把與 n 個(gè)個(gè)體相關(guān)聯(lián)的謂詞叫做一元謂詞 。24、“我正在說(shuō)謊?!辈皇敲}。 25、用 A 表示“是個(gè)大學(xué)生”, c 表示“張三”,則 A(c) :張三是個(gè)大學(xué)生。 26、設(shè) F , ,則 F-1 , 。27、歐拉圖是有歐拉回路的圖。 28、設(shè) f:AB, g:BC。若 f, g都是單射,則 g?f 也是單射。 三、計(jì)算題(每題 10 分,共 40 分)1、設(shè) A=c,d, B=0,1,2 ,則 A B=, ,B A= , 。2、A = a,b
7、,c ,B = 1,2 ,AB = a,b,c 1,2 = , 。3、A = a,b,c ,AA = a,b,c a,b,c = , 。4、符號(hào)化命題“如果 2 大于 3,則 2 大于 4?!?。設(shè) L(x,y) :x 大于 y, a:2, b: 3, c: 4,則命題符號(hào)化為 L(a,b) L(a,c) 。5、符號(hào)化命題“并不是所有的兔子都比所有的烏龜跑得快”。設(shè) F(x) :x 是兔子。 G(x) :x 是烏龜。 H(x,y) :x比 y 跑得快。該命題符號(hào)化為: ? x? y(F(x) G(y) H(x,y) 。6、符號(hào)化命題“ 2 是素?cái)?shù)且是偶數(shù)”。設(shè) F(x) :x 是素?cái)?shù)。 G(x)
8、:x 是偶數(shù)。 a: 2,則命題符號(hào)化為 F(a)G(a)。7、設(shè) A=a,b,c,d ,R 是 A 的二元關(guān)系, 定義為:R=, , ,寫(xiě)出 A 上二元關(guān)系 R 的關(guān)系矩陣。解:R 的關(guān)系矩陣為:11001000110011108、設(shè) A=1,2,3,4 ,R是A的二元關(guān)系,定義為:R=, ,9、設(shè)有向圖G 如下所示,求各個(gè)結(jié)點(diǎn)的出度、入度和度數(shù)。deg(v1) 3, deg+(v1) 1, deg-(v1) 2; deg(v2) deg+(v4) deg-(v2) 0; deg(v3)3, deg(v4)2,deg+(v3) 2,deg+(v4) 1,deg-(v3)1;deg-(v4)
9、1;求它的鄰接矩陣。入度和度數(shù)。答:deg+(v1) 2, deg+(v2) 2, deg+(v3) 2,deg(v1)3,deg(v2)3,deg(v3)5,deg(v4) deg+(v4) deg-(v4) 0; deg(v5) 1, deg+(v5) 0, deg-(v5) 1;deg-(v1)1;deg-(v2)1;deg-(v3)3;01011010A(G)0101101012、求命題公式 (p q)的真值表。qpq (p q) ,寫(xiě)出A 上二元關(guān)系 R 的關(guān)系矩陣。解:R 的關(guān)系矩陣為:11001000110011100010101001101101100113、設(shè) = ,求 x,
10、y。 解:由定理列出如下方程組:2x y 10x 3y 5求解得 x=5 , y=0 。14、R1、R2是從1, 2, 3, 4, 5 到2, 4, 6 的關(guān)系,若R1, , ,R2=, ,計(jì)算 domR1,ranR1,fldR1 ,domR2,ranR2,fldR2 。解: domR1=1, 3, 5 , ranR1=2, 4, 6 ,fldR1=dom R1 ran R1=1, 2, 3, 4, 5, 6 ; domR2=1, 2 , ranR2=4, 6 ,fldR2=dom R2 ran R2=1, 2, 4, 6 。15、設(shè) A=1, 2, 3, 4, 5 ,B=3, 4, 5, C
11、=1, 2, 3 ,A到 B的關(guān)系 R=|x+y=6 ,B到C 的關(guān)系 S=|y z=2 ,求 R?S。解:R=, , , S=, , ,從而 R?S=, , 或者因 R , S,所以 R?S;因R, S,所以 R?S;因 R, S,所以 R?S;從而 R?S=, , 16、集合 A=a, b, c ,B=1, 2, 3, 4, 5 ,R是A上的關(guān)系,S是 A到B 的關(guān)系。R=, , , , , S=, , , , ,求 R?S, S1?R1 R?S=, , , , , , (R?S)-1=, , , , , , 1R 1=, , , , ,1S1=, , , , S1?R 1=, , , ,
12、 , , 。17、A1, 2, 3, 4, 5, 6 ,D 是整除關(guān)系,畫(huà)出哈斯圖并求出最小元、最大元、極小元和極 大元。解:1 是 A 的最小元,沒(méi)有最大元, 1 是極小元, 4、 5、 6 都是 A 的極大元。18、設(shè)集合 A=a,b,c ,A 上的關(guān)系 R=, , ,求 R 的自反、 對(duì)稱(chēng)、 傳遞閉包。 r(R)=,s(R)=, t(R)=,19、求下圖中頂點(diǎn) v0 與 v5 之間的最短路徑。v5v0, v1, v2, v4 , v3, v520、分別用三種不同的遍歷方式寫(xiě)出對(duì)下圖中二叉樹(shù)點(diǎn)的訪問(wèn)次序。中根遍歷:DBHEAIFJCGK后根遍歷: DHEBIJFKGCA四、證明題(每題 1
13、0 分,共 20 分)1、若 R和 S都是非空集 A 上的等價(jià)關(guān)系,證明 R S是 A 上的等價(jià)關(guān)系。證明: aA,因?yàn)?R和S都是A上的等價(jià)關(guān)系,所以 xRx且xSx。故 x R S x。從而 R S 是自反的。a,b A ,aR Sb,即 aRb且aSb。因?yàn)?R和S都是 A上的等價(jià)關(guān)系,所以 bRa且bSa。 故 b R S a。從而 R S 是對(duì)稱(chēng)的。a,b,cA,a R S b且b R S c,即aRb,aSb,bRc且bSc。因?yàn)?R和S都是 A上的等 價(jià)關(guān)系,所以 aRc 且 aSc。故 a R S c。從而 R S 是傳遞的。故 R S 是 A 上的等價(jià)關(guān)系。 2、證明蘇格拉底
14、論證:凡人要死。蘇格拉底是人,蘇格拉底要死。設(shè): H(x) :x是人。M(x) :x是要死的。s:蘇格拉底。本題要證明: ( x)(H(x) M(x) H(s) M(s) 證明:US( x)(H(x) M(x) P H(s) M(s) H(s)P M(s)、3、P Q, QR, R, S PS證明:(1)R前提(2)Q R前提(3)Q(1),(2)(4)PQ前提(5)P(3),(4)(6)S P前提(7)S(5),(6)4、在群 中,除單位元e 外,不可能有別的冪等元。因?yàn)?e?e=e,所以e 是冪等元。設(shè)aG且a?a=a,則有a=e?a=(a 1 ?a)?a=a 1?(a?a)=a1 ?a=
15、e,即 a=e。6、證明: (Q S) R)(S (P R) = (S(PQ) R.證明:左邊: (QS)R) (S(P R)=( (QS)R)( S(PR)=( QSR)( SPR)=( QSR)( SPR)右邊: (S(PQ) R= (S( PQ) R= ( S(P Q)R= ( QSR)( SPR)所以 (Q S) R)(S (P R) = (S (PQ) R.7、設(shè) I 是整數(shù)集合, k 是正整數(shù), I 上的關(guān)系 R |x, y I,且 xy 可被 k 整除 , 證明 R 是等價(jià)關(guān)系。證明: (1) 對(duì)任意的 x A,有 x x=0 可被 k 整除。所以 R,即 R 具有自反性。(2)
16、 對(duì)任意的 x,y A, R,即 xy可被 k 整除,設(shè) x y=km ,則 y x= km, 顯然 yx可被 k整除。所以 R,即 R具有對(duì)稱(chēng)性。(3)設(shè)x,y,z A ,若 R, R,即xy可被 k整除, y z可被 k整除, 設(shè)x y=km , y z=kn ,則 x z=k(m+n) ,即 xz可被 k整除。所以 R,即 R具 有傳遞性。綜上所述, R 具有自反性、對(duì)稱(chēng)性和傳遞性,故 R 是等價(jià)關(guān)系。8、證明:(p q)r) (qp)r)p (q r)? r(q p)證明: (pq) r)( p q) r)/蘊(yùn)涵等值式(pq) r/蘊(yùn)涵等值式(p ( q) r/德摩根律( q p) r
17、)/交換律p(qr)? r(q p)(1)(P)反證法附加前提(2)P由(1)(3)PQ已知前提(4)Q由(2)和(3)(5)QR已知前提(6)R由(4)和(5)(7)RS已知前提(8)R由 (7)(9)RR由(6)和(8),矛盾(1) (? x)P(x)前提引入(2) ( x) P(x)由(1)(3) P(c)由(2) ES(4) ( ? x)(P(x) Q(x)前提引入(5) P(c) Q(c)由(4) US(6) Q(c)由(3)和(5)(7) ( x)Q(x)由(6) EG (? x)P(x) ( x)Q(x)CP 規(guī)則:要證 S RC ,也就是證明 (S R) C? p (qr)? p (qr)? r( q p)? r(q p)? r (q p)9、證明 (PQ) (P R)/蘊(yùn)涵等值式/蘊(yùn)涵等值式/結(jié)合律與交換律/蘊(yùn)涵等值式/蘊(yùn)涵等值式 (Q S) SR(1)PQ已知前提(2)PQ由(1)(3)QS已知前提(4)PS由(2) 和 (3)(5)SP由(4)(6)PR已知前提(7)SR由(5) 和 (6)(8)SR由(
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 淺談后進(jìn)生學(xué)習(xí)興趣與學(xué)習(xí)習(xí)慣的培養(yǎng)
- 船舶配套業(yè)相關(guān)項(xiàng)目投資計(jì)劃書(shū)
- 【二年級(jí)】上冊(cè)道德與法治-第11課 大家排好隊(duì) 課件 人教版道德與法治 二年級(jí)上冊(cè)
- 蘇教版五年級(jí)數(shù)學(xué)上冊(cè)教學(xué)工作總結(jié)
- 振沖置換法軟基處理方案
- 2019-2020年海外直播平臺(tái)行業(yè)分析報(bào)告
- 幼兒園食堂人員健康管理制度
- 日常安全培訓(xùn)試題及答案標(biāo)準(zhǔn)卷
- 費(fèi)用歸集與分配4生產(chǎn)費(fèi)用在完工產(chǎn)品與在產(chǎn)品之間的歸集和分配
- 2024-2030年中國(guó)起重設(shè)備行業(yè)市場(chǎng)發(fā)展分析及競(jìng)爭(zhēng)格局與投資機(jī)會(huì)研究報(bào)告
- 河南省鹽及鹽化工產(chǎn)業(yè)發(fā)展研究
- 實(shí)驗(yàn)性臨床醫(yī)療風(fēng)險(xiǎn)處置預(yù)案
- 卡特320320GC323故障代碼參數(shù)
- PDM系統(tǒng)電子檔案“四性”檢測(cè)方案
- 手球?qū)m?xiàng)課課程教案
- 可逆反擊錘式破碎機(jī)施工方案
- 融資項(xiàng)目調(diào)查表(共6頁(yè))
- 六年級(jí)上冊(cè)數(shù)學(xué)試題-圓-單元檢測(cè)題(含答案)西師大
- 跨境電商公司運(yùn)營(yíng)人員晉升及淘汰制度方案
- 【原創(chuàng)】張靜:《基層政權(quán)》浙江人民出版社2000年版
- 小(微)工貿(mào)企業(yè)安全生產(chǎn)基礎(chǔ)臺(tái)賬
評(píng)論
0/150
提交評(píng)論