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

《離散數(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有6、集合A={1,2,3｝，A上的二元運(yùn)算定義為：a*b=a和b兩者的最大值，則2*3=。7、設(shè)A={a,b,c,d},則∣A∣=。8、對實(shí)數(shù)的普通加法和乘法，是加法的冪等元，是乘法的冪等元。9、設(shè)a,b,c是阿貝爾群<G,+>的元素，則-(a+b+c)=。10、一個(gè)圖的哈密爾頓路是。11、不能再分解的命題稱為，至少包含一個(gè)聯(lián)結(jié)詞的命題稱為。12、命題是。13、如果p表示王強(qiáng)是一名大學(xué)生，則┐p表示。14、與一個(gè)個(gè)體相關(guān)聯(lián)的謂詞叫做。15、量詞分兩種：和。16、設(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=，則A\B=。22、設(shè)A={1,2},則∣A∣=。23、在有向圖中，結(jié)點(diǎn)v的出度deg+(v)表示，入度deg-(v)表示以。24、一個(gè)圖的歐拉回路是。25、不含回路的連通圖是。26、不與任何結(jié)點(diǎn)相鄰接的結(jié)點(diǎn)稱為。27、推理理論中的四個(gè)推理規(guī)則是、、、。二、判斷題（每題2分，共20分）1、空集是唯一的。2、對任意的集合A，A包含A。3、恒等關(guān)系不是對稱的，也不是反對稱的。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、對于任何一命題公式，都存在與其等價(jià)的析取范式和合取范式。8、設(shè)（A,*）是代數(shù)系統(tǒng)，a∈A，如果a*a＝a，則稱a為（A，*）的等冪元。9、設(shè)f：A→B，g：B→C。若f，g都是雙射，則gf不是雙射。10、無向圖的鄰接矩陣是對稱陣。11、一個(gè)集合不可以是另一個(gè)集合的元素。12、映射也可以稱為函數(shù)，是一種特殊的二元關(guān)系。13、群中每個(gè)元素的逆元都不是惟一的。14、<{0,1,2,3,4},MAX,MIN>是格。15、樹一定是連通圖。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、“我正在說謊?！辈皇敲}。25、用A表示“是個(gè)大學(xué)生”，c表示“張三”，則A(c)：張三是個(gè)大學(xué)生。26、設(shè)F＝{<3,3>,<6,2>}，則F-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}，則計(jì)算A×B，B×A。2、A={a,b,c}，B={1,2}，計(jì)算A×B。3、A={a,b,c}，計(jì)算A×A。4、符號(hào)化命題“如果2大于3，則2大于4。”。5、符號(hào)化命題“并不是所有的兔子都比所有的烏龜跑得快”。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>}，寫出A上二元關(guān)系R的關(guān)系矩陣。8、設(shè)A={1,2,3,4}，R是A的二元關(guān)系，定義為：R={<1,1>,<1,2>,<2,1>,<3,2>,<3,1>,<4,3>,<4,2>,<4,1>}，寫出A上二元關(guān)系R的關(guān)系矩陣。9、設(shè)有向圖G如下所示，求各個(gè)結(jié)點(diǎn)的出度、入度和度數(shù)。10、設(shè)有向圖G如下所示，求各個(gè)結(jié)點(diǎn)的出度、入度和度數(shù)。11、設(shè)無向圖G如下所示，求它的鄰接矩陣。12、求命題公式┐(p∧┐q)的真值表。13、設(shè)<2x+y,5>=<10,x－3y>，求x，y。14、R1、R2是從{1,2,3,4,5}到{2,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到B的關(guān)系R={<x,y>|x+y=6}，B到C的關(guān)系S={<y,z>|y－z=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，S–1?R–117、A＝{1,2,3,4,5,6}，D是整除關(guān)系，畫出哈斯圖并求出最小元、最大元、極小元和極大元。18、設(shè)集合A={a,b,c}，A上的關(guān)系R={<a,a>,<a,b>,<b,c>}，求R的自反、對稱、傳遞閉包。19、求下圖中頂點(diǎn)v0與v5之間的最短路徑。20、分別用三種不同的遍歷方式寫出對下圖中二叉樹點(diǎn)的訪問次序。四、證明題（每題10分，共20分）1、若R和S都是非空集A上的等價(jià)關(guān)系，證明RS是A上的等價(jià)關(guān)系。2、證明蘇格拉底論證：凡人要死。蘇格拉底是人，蘇格拉底要死。3、P→Q，┐QR，┐R，┐SP┐S4、在群<G,*>中，除單位元e外，不可能有別的冪等元。5、設(shè)R和S是二元關(guān)系，證明：(RS)-1=R-1S-16、證明：((Q∧S)→R)∧(S→(P∨R))=(S∧(P→Q))→R.7、設(shè)I是整數(shù)集合，k是正整數(shù)，I上的關(guān)系R＝{<x,y>|x,y∈I，且x－y可被k整除}，證明R是等價(jià)關(guān)系。8、證明((p→q)→r)((┐q∧p)∨r)9、證明(P∨Q)∧(P→R)∧(Q→S)S∨R10、證明P→┐Q，Q∨┐R，R∧┐S┐P11、證(?x)(P(x)∨Q(x))┐(?x)P(x)→(x)Q(x)12、證明定理：設(shè)<G,?>是群，對于任意a,b∈G，則方程a?x=b與y?a=b，在群內(nèi)有唯一解?！峨x散數(shù)學(xué)》復(fù)習(xí)題參考答案一、填空題（每空1分，共20分）1、集合A上的偏序關(guān)系的三個(gè)性質(zhì)是自反性、反對稱性和傳遞性。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有46、集合A={1,2,3｝，A上的二元運(yùn)算定義為：a*b=a和b兩者的最大值，則2*3=3。7、設(shè)A={a,b,c,d},則∣A∣=4。8、對實(shí)數(shù)的普通加法和乘法，0是加法的冪等元，1是乘法的冪等元。9、設(shè)a,b,c是阿貝爾群<G,+>的元素，則-(a+b+c)=(-a)+(-b)+(-c)。10、一個(gè)圖的哈密爾頓路是一條通過圖中所有結(jié)點(diǎn)一次且恰好一次的路。11、不能再分解的命題稱為原子命題，至少包含一個(gè)聯(lián)結(jié)詞的命題稱為復(fù)合命題。12、命題是能夠表達(dá)判斷（分辯其真假）的陳述語句。13、如果p表示王強(qiáng)是一名大學(xué)生，則┐p表示王強(qiáng)不是一名大學(xué)生。14、與一個(gè)個(gè)體相關(guān)聯(lián)的謂詞叫做一元謂詞。15、量詞分兩種：全稱量詞和存在量詞。16、設(shè)A、B為集合，如果集合A的元素都是集合B的元素，則稱A是B的子集。17、集合上的三種特殊元是單位元、零元及可逆元。18、設(shè)A={a,b}，則ρ(A)的四個(gè)元素分別是：空集，{a}，，{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=，則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è)圖的歐拉回路是一條通過圖中所有邊一次且恰好一次的回路。25、不含回路的連通圖是樹。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、√。2、√。3、×。4、√。5、√。6、×。7、√。8、√。9、×。10、√。11、×。12、√。13、×。14、√。15、√。16、×。17、√。18、√。19、×。20、×。21、√。22、√。23、×。24、√。25、√。26、×。27、√。28、√。1、空集是唯一的。2、對任意的集合A，A包含A。3、恒等關(guān)系不是對稱的，也不是反對稱的。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、對于任何一命題公式，都存在與其等價(jià)的析取范式和合取范式。8、設(shè)（A,*）是代數(shù)系統(tǒng)，a∈A，如果a*a＝a，則稱a為（A，*）的等冪元。9、設(shè)f：A→B，g：B→C。若f，g都是雙射，則gf不是雙射。10、無向圖的鄰接矩陣是對稱陣。11、一個(gè)集合不可以是另一個(gè)集合的元素。12、映射也可以稱為函數(shù)，是一種特殊的二元關(guān)系。13、群中每個(gè)元素的逆元都不是惟一的。14、<{0,1,2,3,4},MAX,MIN>是格。15、樹一定是連通圖。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、“我正在說謊?！辈皇敲}。25、用A表示“是個(gè)大學(xué)生”，c表示“張三”，則A(c)：張三是個(gè)大學(xué)生。26、設(shè)F＝{<3,3>,<6,2>}，則F-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}，則A×B={<c,0>,<c,1>,<c,2>,<d,0>,<d,1>,<d,2>}，B×A={<0,c>,<0,d>,<1,c>,<1,d>,<2,c>,<2,d>}。2、A={a,b,c}，B={1,2}，A×B={a,b,c}×{1,2}={<a,1>,<b,1>,<c,1>,<a,2>,<b,2>,<c,2>}。3、A={a,b,c}，A×A={a,b,c}×{a,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?！薄ＴO(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)：x是偶數(shù)。a：2，則命題符號(hào)化為F(a)∧G(a)。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>}，寫出A上二元關(guān)系R的關(guān)系矩陣。解：R的關(guān)系矩陣為：8、設(shè)A={1,2,3,4}，R是A的二元關(guān)系，定義為：R={<1,1>,<1,2>,<2,1>,<3,2>,<3,1>,<4,3>,<4,2>,<4,1>}，寫出A上二元關(guān)系R的關(guān)系矩陣。解：R的關(guān)系矩陣為：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+(v3)＝2，deg-(v3)＝1；deg(v4)＝2，deg+(v4)＝1，deg-(v4)＝1；10、設(shè)有向圖G如下所示，求各個(gè)結(jié)點(diǎn)的出度、入度和度數(shù)。答：deg(v1)＝3，deg+(v1)＝2，deg-(v1)＝1；deg(v2)＝3，deg+(v2)＝2，deg-(v2)＝1；deg(v3)＝5，deg+(v3)＝2，deg-(v3)＝3；deg(v4)＝deg+(v4)＝deg-(v4)＝0；deg(v5)＝1，deg+(v5)＝0，deg-(v5)＝1；11、設(shè)無向圖G如下所示，求它的鄰接矩陣。12、求命題公式┐(p∧┐q)的真值表。pq┐qp∧┐q┐(p∧┐q)0010101001101101100113、設(shè)<2x+y,5>=<10,x－3y>，求x，y。解：由定理列出如下方程組：求解得x=5，y=0。14、R1、R2是從{1,2,3,4,5}到{2,4,6}的關(guān)系，若R1＝{<1,2>,<3,4>,<5,6>}，R2={<1,4>,<2,6>}，計(jì)算domR1，ranR1，fldR1，domR2，ranR2，fldR2。解：domR1={1,3,5}，ranR1={2,4,6}，fldR1=domR1∪ranR1={1,2,3,4,5,6}；domR2={1,2}，ranR2={4,6}，fldR2=domR2∪ranR2={1,2,4,6}。15、例：設(shè)A={1,2,3,4,5}，B={3,4,5},C={1,2,3}，A到B的關(guān)系R={<x,y>|x+y=6}，B到C的關(guān)系S={<y,z>|y－z=2}，求R?S。解：R={<1,5>,<2,4>,<3,3>},S={<3,1>,<4,2>,<5,3>}，從而R?S={<1,3>,<2,2>,<3,1>}或者因<1,5>∈R，<5,3>∈S，所以<1,3>∈R?S；因<2,4>∈R，<4,2>∈S，所以<2,2>∈R?S；因<3,3>∈R，<3,1>∈S，所以<3,1>∈R?S；從而R?S={<1,3>,<2,2>,<3,1>}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，S–1?R–1R?S={<a,1>,<a,4>,<a,5>,<b,2>,<c,2>,<c,4>,<c,5>}(R?S)-1={<1,a>,<4,a>,<5,a>,<2,b>,<2,c>,<4,c>,<5,c>}R–1={<a,a>,<c,a>,<b,b>,<b,c>,<c,c>}，S–1={<1,a>,<4,a>,<2,b>,<4,c>,<5,c>}S–1?R–1={<1,a>,<2,b>,<2,c>,<4,a>,<4,c>,<5,a>,<5,c>}。17、A＝{1,2,3,4,5,6}，D是整除關(guān)系，畫出哈斯圖并求出最小元、最大元、極小元和極大元。解：1是A的最小元，沒有最大元，1是極小元，4、5、6都是A的極大元。18、設(shè)集合A={a,b,c}，A上的關(guān)系R={<a,a>,<a,b>,<b,c>}，求R的自反、對稱、傳遞閉包。r(R)={<a,a>,<a,b>,<b,c>,<b,b>,<c,c>}s(R)={<a,a>,<a,b>,<b,a>,<b,c>,<c,b>}t(R)={<a,a>,<a,b>,<b,c>,<a,c>}19、求下圖中頂點(diǎn)v0與v5之間的最短路徑。解：如下圖所示v0與v5之間的最短路徑為：v0,v1,v2,v4,v3,v5最短路徑值為1+2+1+3+2=920、分別用三種不同的遍歷方式寫出對下圖中二叉樹點(diǎn)的訪問次序。先根遍歷：ABDEHCFIJGK中根遍歷：DBHEAIFJCGK后根遍歷：DHEBIJFKGCA四、證明題（每題10分，共20分）1、若R和S都是非空集A上的等價(jià)關(guān)系，證明RS是A上的等價(jià)關(guān)系。證明：a∈A，因?yàn)镽和S都是A上的等價(jià)關(guān)系，所以xRx且xSx。故xRSx。從而RS是自反的。a,b∈A，aRSb，即aRb且aSb。因?yàn)镽和S都是A上的等價(jià)關(guān)系，所以bRa且bSa。故bRSa。從而RS是對稱的。a,b,c∈A，aRSb且bRSc，即aRb，aSb，bRc且bSc。因?yàn)镽和S都是A上的等價(jià)關(guān)系，所以aRc且aSc。故aRSc。從而RS是傳遞的。故RS是A上的等價(jià)關(guān)系。2、證明蘇格拉底論證：凡人要死。蘇格拉底是人，蘇格拉底要死。設(shè)：H(x)：x是人。M(x)：x是要死的。s：蘇格拉底。本題要證明：(x)(H(x)→M(x))∧H(s)M(s)證明：⑴(x)(H(x)→M(x)) P ⑵H(s)→M(s) US⑴ ⑶H(s) P ⑷M(s) ⑵、⑶3、P→Q，┐QR，┐R，┐SP┐S證明：(1)┐R前提(2)┐QR前提(3)┐Q（1），（2）(4)P→Q前提(5)┐P（3），（4）(6)┐SP前提(7)┐S（5），（6）4、在群<G,*>中，除單位元e外，不可能有別的冪等元。因?yàn)閑?e=e，所以e是冪等元。設(shè)aG且a?a=a，則有a=e?a=(a–1?a)?a=a–1?(a?a)=a–1?a=e，即a=e。5、設(shè)R和S是二元關(guān)系，證明：(RS)-1=R-1S-1證明：.所以.6、證明：((Q∧S)→R)∧(S→(P∨R))=(S∧(P→Q))→R.證明：左邊：((Q∧S)→R)∧(S→(P∨R))=(┐(Q∧S)∨R)∧(┐S∨(P∨R))=(┐Q∨┐S∨R)∧(┐S∨P∨R)=(┐Q∨┐S∨R)∧(┐S∨P∨R)右邊：(S∧(P→Q))→R=┐(S∧(┐P∨Q))∨R=(┐S∨(P∧┐Q))∨R=(┐Q∨┐S∨R)∧(┐S∨P∨R)所以((Q∧S)→R)∧(S→(P∨R))=(S∧(P→Q))→R.7、設(shè)I是整數(shù)集合，k是正整數(shù)，I上的關(guān)系R＝{<x,y>|x,y∈I，且x－y可被k整除}，證明R是等價(jià)關(guān)系。證明：(1)對任意的x∈A，有x－x=0可被k整除。所以<x,x>∈R，即R具有自反性。(2)對任意的x，y∈A，<x,y>∈R，即x－y可被k整除，設(shè)x－y=km，則y－x=－km，顯然y－x可被k整除。所以<y,x>∈R，即R具有對稱性。(3)設(shè)x，y，z∈A，若<x,y>∈R，<y,z>∈R，即x－y可被k整除，y－z可被k整除，設(shè)x－y=km，y－z=kn，則x－z=k(m+n)，即x－z可被k整除。所以<x,z>∈R，即R具有傳遞性。綜上所述，R具有自反性、對稱性和傳遞性，故R是等價(jià)關(guān)系。8、證明：⑴((p→q)→r