中國(guó)石油大學(xué)大學(xué)離散數(shù)學(xué)期末復(fù)習(xí)題及答案

1、離散數(shù)學(xué)期末復(fù)習(xí)題一、填空題（每空2分，共20分）1、集合A上的偏序關(guān)系的三個(gè)性質(zhì)是、和。2、一個(gè)集合的備集是指。3、集合A=b,c,B=a,b,c,d,e,則A?B=。4、集合A=1,2,3,4,B=1,3,5,7,9,則A?B=。5、若A是2元集合，則2A有個(gè)元素。6、集合A=1,2,3,A上的二元運(yùn)算定義為：a*b=a和b兩者的最大值，則2*3=。7、設(shè)A=a,b,c,d,則IAI=。8、對(duì)實(shí)數(shù)的普通加法和乘法，是加法的哥等元，是乘法的哥等兀。9、設(shè)a,b,c是阿貝爾群<G,+>的元素，貝U-（a+b+c尸。10、一個(gè)圖的哈密爾頓路是。11、不能再分解的命題稱為,至少包含一個(gè)

2、聯(lián)結(jié)詞的命題稱為。12、命題是o13、如果p表示王強(qiáng)是名大學(xué)生，貝Unp表示。14、與一個(gè)個(gè)體相關(guān)聯(lián)的謂詞叫做。15、量詞分兩種：和o16、設(shè)A、B為集合，如果集合A的元素都是集合B的元素，則稱A是B的。17、集合上的三種特殊元是、及。18、設(shè)A=a,b,則，A）的四個(gè)元素分別是：,。19、代數(shù)系統(tǒng)是指由及其上的或組成的系統(tǒng)。20、設(shè)<L,*1,*2>是代數(shù)系統(tǒng)，其中是*1,*2二元運(yùn)算符，如果*1,*2都滿足、,并且*1和*2滿足,則稱<L,*1,*2>是格。21、集合A=a,b,c,d,B=b,則AB=。22、設(shè)A=1,2,貝卜AI=。23、在有向圖中，結(jié)點(diǎn)v的出度

3、deg+(v)表示,入度deg-(v)表示以。24、一個(gè)圖的歐拉回路是。25、不含回路的連通圖是。26、不與任何結(jié)點(diǎn)相鄰接的結(jié)點(diǎn)稱為。27、推理理論中的四個(gè)推理規(guī)則二、判斷題(每題2分，共20分)1、空集是唯一的。2、對(duì)任意的集合A,A包含A。3、恒等關(guān)系不是對(duì)稱的，也不是反對(duì)稱的。4、集合1,2,3,3和1,2,2,3是同一集合。5、圖G中，與頂點(diǎn)v關(guān)聯(lián)的邊數(shù)稱為點(diǎn)v的度數(shù)，記作deg(v)。6、在實(shí)數(shù)集上，普通加法和普通乘法不是可結(jié)合運(yùn)算。7、對(duì)于任何一命題公式，都存在與其等價(jià)的析取范式和合取范式。8、設(shè)(A,*)是代數(shù)系統(tǒng)，aCA,如果a*a=a,則稱a為(A,*)的等哥元。9、設(shè)f:A

4、-B,g:B-C。若f,g都是雙射，則gf不是雙射。10、無(wú)向圖的鄰接矩陣是對(duì)稱陣。11、一個(gè)集合不可以是另一個(gè)集合的元素。12、映射也可以稱為函數(shù)，是一種特殊的二元關(guān)系。13、群中每個(gè)元素的逆元都不是惟一的。14、<0,1,2,3,4,MAX,MIN>是格。15、樹(shù)一定是連通圖。16、單位元不是可逆的。17、一個(gè)命題可賦予一個(gè)值，稱為真值。18、復(fù)合命題是由連結(jié)詞、標(biāo)點(diǎn)符號(hào)和原子命題復(fù)合構(gòu)成的命題。19、任何兩個(gè)重言式的合取或析取不是一個(gè)重言式。20、設(shè)f:A-B,g:BfC。若f,g都是滿射，則g?f不是滿射。21、集合1,2,3,3和1,2,3是同一集合。22、零元是不可逆的

5、。23、一般的，把與n個(gè)個(gè)體相關(guān)聯(lián)的謂詞叫做一元謂詞。24、“我正在說(shuō)謊?！辈皇敲}。25、用A表示“是個(gè)大學(xué)生”，c表示“張三”，則A(c):張三是個(gè)大學(xué)生。26、設(shè)F=<3,3>,<6,2>,貝UF-1=<6,3>,<2,6>。27、歐拉圖是有歐拉回路的圖。28、設(shè)f:A-B,g:BCo若f,g都是單射，則g?f也是單射。三、計(jì)算題(每題10分，共40分)1、設(shè)A=c,d,B=0,1,2,則計(jì)算AXB,BXA。2、A=a,b,c,B=1,2,計(jì)算AXB。3、A=a,b,c,計(jì)算AXA。4、符號(hào)化命題“如果2大于3，則2大于4?！?。5、符號(hào)化命

6、題“并不是所有的兔子都比所有的烏龜跑得快”。6、符號(hào)化命題“2是素?cái)?shù)且是偶數(shù)”。7、 設(shè)A=a,b,c,d，R是A的二元關(guān)系，定義為：R=<a,a>,<a,b>,<b,a>,<c,b>,<c,a>,<d,c>,<d,b>,<d,a>,寫(xiě)出A上二元關(guān)系R的關(guān)系矩陣。8、設(shè)人=1,2,3,4木是A的二元關(guān)系，定義為：R=<1,1>,<1,2>,<2,1>,<3,2>,<3,1>,<4,3>,<4,2>,<4,1&g

7、t;，寫(xiě)出A上二元關(guān)系R的關(guān)系矩陣。9、設(shè)有向圖G如下所示，求各個(gè)結(jié)點(diǎn)的出度、入度和度數(shù)。V412、求命題公式r(pAnq)的真值表。13、設(shè)<2x+y,5>=<10,x3y>,求x,y。14、R1、R2是從1,2,3,4,5至U2,4,6的關(guān)系，若R1=<1,2>,<3,4>,<5,6>,R2=<1,4>,<2,6>,計(jì)算domR1,ranR1,fldR1,domR2,ranR2,fldR2。15、例：設(shè)A=1,2,3,4,5,B=3,4,5,C=1,2,3,A至UB的關(guān)系R=<x,y>|x+y=

8、6,B到C的關(guān)系S=<y,z>|yz=2,求R?S。16、集合A=a,b,c,B=1,2,3,4,5,R是A上的關(guān)系，S是A到B的關(guān)系。R=<a,a>,<a,c>,<b,b>,<c,b>,<c,c>,S=<a,1>,<a,4>,<b,2>,<c,4>,<c,5>,求R?S,S1?R117、A=1,2,3,4,5,6,D是整除關(guān)系，畫(huà)出哈斯圖并求出最小元、最大元、極小元和極大元。18、設(shè)集合A=a,b,c,A上的關(guān)系R=<a,a>,<a,b>

9、,<b,c>,求R的自反、對(duì)稱、傳遞閉包。19、求下圖中頂點(diǎn)v0與v5之間的最短路徑。20、分別用三種不同的遍歷方式寫(xiě)出對(duì)下圖中二叉樹(shù)點(diǎn)的訪問(wèn)次序。四、證明題(每題10分，共20分)1、若R和S都是非空集A上的等價(jià)關(guān)系，證明RS是A上的等價(jià)關(guān)系。2、證明蘇格拉底論證：凡人要死。蘇格拉底是人，蘇格拉底要死。3、P-Q,nQR,nR,nSPnS4、在群G,*中，除單位元e外，不可能有別的哥等元。5、設(shè)R和S是二元關(guān)系，證明：(RS)-1=R-1S-16、證明：(QAS)一R)A(S一(PVR)=(SA(P-Q)一R.7、設(shè)I是整數(shù)集合，k是正整數(shù)，I上的關(guān)系R=x,y|x,y£

10、;I,且x-證明R是等價(jià)關(guān)系。8、證明(p-q)r)(nqAp)Vr)9、證明(PVQ)A(P-R)A(Q-S)SVR10、證明P一nQ,QVnR,RAnSnP11、證(？x)(P(x)VQ(x)n(?x)P(x)一(x)Q(x),在群內(nèi)有唯一12、證明定理：設(shè)G,?此群，對(duì)于任意a,bCG,則方程a?x=b與y?a=b解。離散數(shù)學(xué)復(fù)習(xí)題參考答案一、填空題(每空1分，共20分)1、集合A上的偏序關(guān)系的三個(gè)性質(zhì)是自反性、反對(duì)稱性和傳遞性。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,

11、5,7,9,則A?B=1,3。5、若A是2元集合，則2A有工一個(gè)元素。6、集合A=1,2,3,A上的二元運(yùn)算定義為：a*b=a和b兩者的最大值，則2*3=3。7、設(shè)A=a,b,c,d,則IAI=4。8、對(duì)實(shí)數(shù)的普通加法和乘法，0_是加法的哥等元，L是乘法的哥等元。9、設(shè)a,b,c是阿貝爾群G,+的元素，則-(a+b+c)=(-a)+(-b)+(-c)。10、一個(gè)圖的哈密爾頓路是一條通過(guò)圖中所有結(jié)點(diǎn)一次且恰好一次的路。11、不能再分解的命題稱為原子命題，至少包含一個(gè)聯(lián)結(jié)詞的命題稱為復(fù)合命題。12、命題是能夠表達(dá)判斷(分辯其真假)的陳述語(yǔ)句。13、如果p表示王強(qiáng)是一名大學(xué)生，則p表示王強(qiáng)不是一名大

12、學(xué)生。14、與一個(gè)個(gè)體相關(guān)聯(lián)的謂詞叫做一元謂詞。15、量詞分兩種：全稱量詞和存在量詞。16、設(shè)A、B為集合，如果集合A的元素都是集合B的元素，則稱A是B的子集。17、集合上的三種特殊元是單位元、零元及可逆元。18、設(shè)A=a,b,則p(A)的四個(gè)元素分別是：空集一,叫，a,b。19、代數(shù)系統(tǒng)是指由集合及其上的一元或二元運(yùn)算符組成的系統(tǒng)。20、設(shè)L,*1,*2是代數(shù)系統(tǒng)，其中是*1,*2二元運(yùn)算符，如果*1,*2都滿足交換律、結(jié)合律，并且*1和*2滿足吸收律：則稱L,*1,*2是格。21、集合A=a,b,c,d,B=b,則AB=a,c,d。22、設(shè)A=1,2,貝卜AI=2_o23、在有向圖中，結(jié)點(diǎn)

13、v的出度deg+(v)表示以v為起點(diǎn)的邊的條數(shù).入度deg-(v)表示以v為終點(diǎn)的邊的條數(shù)。24、一個(gè)圖的歐技回路杲一條通對(duì)圖中所有邊一次且恰好一次的回路。25、不含回路的連通圖是樹(shù)。26、不與任何結(jié)點(diǎn)相鄰接的結(jié)點(diǎn)稱為孤立結(jié)點(diǎn)。27、推理理論中的四個(gè)推理規(guī)則是全稱指定規(guī)則（US規(guī)則）、全稱推廣規(guī)則（UG規(guī)則）、在在指定規(guī)則（ES規(guī)則）、存在推廣規(guī)則（EG規(guī)則）。二、判斷題（每題2分，共20分）1、12、13、X。4、Vo5、Vo6、X。7、18、19、X。10、11、X。12、Vo13、X。14、Vo15、Vo16、X。17、Vo18、19、X。20、X。21、Vo22、123、X。24、25

14、、126、X。27、28、1、空集是唯一的。2、對(duì)任意的集合A,A包含A。3、恒等關(guān)系不是對(duì)稱的，也不是反對(duì)稱的。4、集合1,2,3,3和1,2,2,3是同一集合。5、圖G中，與頂點(diǎn)v關(guān)聯(lián)的邊數(shù)稱為點(diǎn)v的度數(shù)，記作deg（v）。6、在實(shí)數(shù)集上，普通加法和普通乘法不是可結(jié)合運(yùn)算。7、對(duì)于任何一命題公式，都存在與其等價(jià)的析取范式和合取范式。8、設(shè)（A,*）是代數(shù)系統(tǒng)，aCA,如果a*a=a,則稱a為（A,*）的等哥元。9、設(shè)f:A-B,g:B-C。若f,g都是雙射，則gf不是雙射。10、無(wú)向圖的鄰接矩陣是對(duì)稱陣。11、一個(gè)集合不可以是另一個(gè)集合的元素。12、映射也可以稱為函數(shù)，是一種特殊的二元關(guān)系

15、。13、群中每個(gè)元素的逆元都不是惟一的。14、<0,1,2,3,4,MAX,MIN>是格。15、樹(shù)一定是連通圖。16、單位元不是可逆的。17、一個(gè)命題可賦予一個(gè)值，稱為真值。18、復(fù)合命題是由連結(jié)詞、標(biāo)點(diǎn)符號(hào)和原子命題復(fù)合構(gòu)成的命題。19、任何兩個(gè)重言式的合取或析取不是一個(gè)重言式。20、設(shè)f:A-B,g:B-C。若f,g都是滿射，則g?f不是滿射。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

16、=<3,3>,<6,2>,貝UF-1=<6,3>,<2,6>。27、歐拉圖是有歐拉回路的圖。28、設(shè)f:A-B,g:B-C。若f,g都是單射，則g?f也是單射。三、計(jì)算題(每題10分，共40分)1、設(shè)A=c,d,B=0,1,2,則AXB=<c,0>,<c,1>,<c,2>,<d,0>,<d,1>,<d,2>,BXA=<0,c>,<0,d>,<1,c>,<1,d>,<2,c>,<2,d>。2、A=a,b,c

17、,B=1,2,AXB=a,b,cx1,2=<a,1>,<b,1>,<c,1>,<a,2>,<b,2>,<c,2>。3、A=a,b,c,AXA=a,b,cxa,b,c=<a,a>,<a,b>,<a,c>,<b,a>,<b,b>,<b,c>,<c,a,>,<c,b>,<c,c>。4、符號(hào)化命題“如果2大于3，則2大于4?！?。設(shè)L(x,y):x大于y,a：2,b：3,c：4,則命題符號(hào)化為L(zhǎng)(a,b)-L(a,c)。5、符號(hào)化命題“并不是所有的兔子都比所有的烏龜跑得快”。設(shè)F(x)：x是兔子。G(x)：x是烏龜