期末練習(xí)題12年1學(xué)期

習(xí)題一. 多重選擇填空題(本題包括16個(gè)空格，每個(gè)空格3分，共48分。每道小題都可能有一個(gè)以上的正確選項(xiàng)，須選出所有的正確選項(xiàng)，不答不得分，多選、少選或選錯(cuò)都將按比例扣分。)1 命題公式(P(PQ)Q是_式。(1) 重言 (2) 矛盾 (3) 可滿足 (4) 非永真的可滿足2給定解釋I=(D,)=(整數(shù)集，f(x,y):f(x,y)=x-y；g(x,y):g(x,y)=x+y；P(x,y):xy)，下列公式中_在解釋I下為真。(1) P(f(x,y),g(x,y) (2) xy P(f(x,y),g(x,y) (3) xy(P(x,y) P(f(x,y),x) (4) xy P(f(x,y),g(x,y)3 是集合， =10，則=_。(1) 100 (2) 99 (3) 2048 (4) 1024 (5) 5124 集合=x|x是整數(shù)，30，=x|x是質(zhì)數(shù)，x20，C=1,3,5，則=_;=_;=_;=_。(1) 1,2,3,5 (2) (3) 0(4) 1,3,5,7,11,13,17,19 (5) 1,3,5,7 (6) 7,11,13,17,195設(shè)A、B、C是集合，下列四個(gè)命題中，_在任何情況下都是正確的。(1) 若AB且BC，則AC (2) 若AB且BC，則AC(3) 若AB且BC，則AC (4) 若AB且BC，則AC5127S=1,2,3,4,5,6,7,8,9,10,11,12，是S上的整除關(guān)系。S的子集2,4,6，則在(S，)中，的最大元是_；的最小元是_；的上確界是_；的下確界是_。(1) 不存在的 (2) 36 (3) 24 (4) 12 (5) 6 (6) 1 (7) 28設(shè)有有限布爾代數(shù)(B,+,*,0,1)，則=_能成立。(1) 1 (2) 2 (3) 3 (4) 4 (5) 5 (6) 8 (7) 99 n個(gè)結(jié)點(diǎn)、m條邊的無向連通圖是樹當(dāng)且僅當(dāng)m=_。(1) n+1 (2) n (3) n-1 (4)2n-1 二. 請(qǐng)給出命題公式的主析取范式。(10分)三. 假設(shè)下列陳述都是正確的：(1)學(xué)生會(huì)的每個(gè)成員都是學(xué)生并且是班干部；(2)有些成員是女生。問是否有成員是女班干部？請(qǐng)將上述陳述和你的結(jié)論符號(hào)化，并給出你的結(jié)論的形式證明。(10分)四. 設(shè)R和S是集合上的等價(jià)關(guān)系,則SR必是等價(jià)關(guān)系。(10分)六。假設(shè)在圖G(有向圖或無向圖)中，有10條邊，4個(gè)3度的結(jié)點(diǎn)，其余結(jié)點(diǎn)的度數(shù)不大于2。問G中至少有幾個(gè)結(jié)點(diǎn)？(10分)一、選擇題1令P：今天下雪了，Q：路滑，則命題“雖然今天下雪了，但是路不滑”可符號(hào)化為（）APQBPQCPQDPQ2下列命題公式為重言式的是（）AQ（PQ）BP（PQ）C（PQ）PD（PQ）Q4謂詞公式x(P(x)yR(y)Q(x)中量詞的轄域是（）ABP（x）C(P(x)yR(y)DP(x), Q(x)5設(shè)個(gè)體域A=a,b，公式xP(x)xS(x)在A中消去量詞后應(yīng)為（）AP(x)S(x)BP(a)P(b)(S(a)S(b)CP(a)S(b)DP(a)P(b)S(a)S(b)6下列選項(xiàng)中錯(cuò)誤的是（）ABCD7設(shè)A=a,b,c,d，A上的等價(jià)關(guān)系R=, , , IA，則對(duì)應(yīng)于R的A的劃分是（）Aa,b, c,dBa, b,c, dCa,b,c,dDa, b, c,d8設(shè)R為實(shí)數(shù)集，函數(shù)f：RR，f(x)=2x，則f是（）A滿射函數(shù)B入射函數(shù)C雙射函數(shù)D非入射非滿射10下列運(yùn)算中關(guān)于整數(shù)集不能構(gòu)成半群的是（）Aab=maxa, bBab=bCab=2abDab=|a-b|12設(shè)A=a, b, c，R是A上的二元關(guān)系，R=, , , ，那么R是（）A反自反的B反對(duì)稱的C可傳遞的D不可傳遞的13設(shè)D=為有向圖，V=a, b, c, d, e, f, E=, , , , 是（）A強(qiáng)連通圖B單向連通圖C弱連通圖D不連通圖14在有n個(gè)結(jié)點(diǎn)的連通圖中，其邊數(shù)（）A最多有n-1條B至少有n-1條C最多有n條D至少有n條15連通圖G是一棵樹，當(dāng)且僅當(dāng)G中（）A有些邊不是割邊B每條邊都是割邊C無割邊集D每條邊都不是割邊16下列命題公式中不是重言式的是（）Ap(qr)Bp(qp)Cp(pp)D(p(qr)(q(pr)17下列語(yǔ)句中為命題的是（）A這朵花是誰(shuí)的？B這朵花真美麗?。這朵花是你的嗎？D這朵花是他的。18設(shè)個(gè)體域是整數(shù)集，則下列命題的真值為真的是（）Ayx(xy=1)Bxy (xy0)Cxy (xy=y2)Dyx(xy=x2)19關(guān)于謂詞公式（x）(y)(P(x,y)Q(y,z)(x)p(x,y),下面的描述中錯(cuò)誤的是（）A（x）的轄域是（y）（P（x,y）Q(y,z)）Bz是該謂詞公式的約束變?cè)狢（x）的轄域是P（x,y）Dx是該謂詞公式的約束變?cè)?0設(shè)論域D=a,b，與公式xA（x）等價(jià)的命題公式是（）AA（a）A（b）BA（a）A（b）CA（a）A（b）DA（b）A（a）21集合A=1，2，3上的下列關(guān)系矩陣中符合等價(jià)關(guān)系條件的是（）ABCD22設(shè)A=，B=P（P（A），以下不正確的式子是（）A ， ， ， 包含于BB 包含于BC ， 包括于BD ， ， 包含于B23設(shè)Z是整數(shù)集，E=，-4，-2，0，2，4，f：ZE，f（x）=2x，則f（）A僅是滿射B僅是入射C是雙射D無逆函數(shù)24設(shè)A=1，2，3，4，5，A上二元關(guān)系R=1，2，3，4，2，2，S=2，4，3，1，4，2，則S-1R-1的運(yùn)算結(jié)果是（）A4，1，2，3，4，2B2，4，2，3，4，2C4，1，2，3，2，4D2，2，3，1，4，426在實(shí)數(shù)集合R上，下列定義的運(yùn)算中不可結(jié)合的是（）Aa*b=a+b+2abBa*b=a+bCa*b=a+b+abDa*b=a-b27下列集合關(guān)于所給定的運(yùn)算成為群的是（）A已給實(shí)數(shù)a的正整數(shù)次冪的全體，且a0，1，-1，關(guān)于數(shù)的乘法B所有非負(fù)整數(shù)的集合，關(guān)于數(shù)的加法C所有正有理數(shù)的集合，關(guān)于數(shù)的乘法D實(shí)數(shù)集，關(guān)于數(shù)的除法28設(shè)無向圖中有6條邊，有一個(gè)3度頂點(diǎn)和一個(gè)5度頂點(diǎn)，其余頂點(diǎn)度為2，則該圖的頂點(diǎn)數(shù)是（）A3B4C5D629下列各圖中既是歐拉圖，又是漢密爾頓圖的是（）A B C D30設(shè)無向圖G的邊數(shù)為m，結(jié)點(diǎn)數(shù)為n，則G是樹等價(jià)于（）AG連通且m=n+1BG連通且n=m+1CG連通且m=2nD每對(duì)結(jié)點(diǎn)之間至少有一條通路31下列為兩個(gè)命題變?cè)狿，Q的小項(xiàng)是（）APQ PB PQC PQD PPQ32下列語(yǔ)句中是真命題的是（）A我正在說謊B嚴(yán)禁吸煙C如果1+2=3，那么雪是黑的D如果1+2=5，那么雪是黑的33設(shè)P：我們劃船，Q：我們跑步。命題“我們不能既劃船又跑步”符號(hào)化為（）A P QB P QC（PQ）D（ P Q）34命題公式（P（PQ）Q是（）A矛盾式B蘊(yùn)含式C重言式D等價(jià)式35命題公式（PQ）R的成真指派是（）A000，001，110，B001，011，101，110，111C全體指派D無36在公式（）F（x，y）（ y）G（x，y）中變?cè)獂是（）A自由變?cè)狟約束變?cè)狢既是自由變?cè)?，又是約束變?cè)狣既不是自由變?cè)植皇羌s束變?cè)?7集合A=1，2，10上的關(guān)系R=|x+y=10，xA，yA，則R的性質(zhì)是（）A自反的B對(duì)稱的C傳遞的、對(duì)稱的D反自反的、傳遞的38若R和S是集合A上的兩個(gè)關(guān)系，則下述結(jié)論正確的是（）A若R和S是自反的，則RS是自反的B若R和S是對(duì)稱的，則RS是對(duì)稱的C若R和S是反對(duì)稱的，則RS是反對(duì)稱的D若R和S是傳遞的，則RS是傳遞的39R=，則下列不是t（R）中元素的是（）ABCD40設(shè)A=1，2，3，4，5，6，7，8，下列選項(xiàng)正確的是（）A1AB1，2，3AC4，5ADA41在自然數(shù)集N上，下列運(yùn)算是可結(jié)合的是（）Aab=a-2bBab=mina，bCab=-a-bDab=|a-b|45具有4個(gè)結(jié)點(diǎn)的非同構(gòu)的無向樹的數(shù)目是（）A2B3C4D547設(shè)A-B=，則有（）AB=BBCABDAB48A，B是集合，P（A），P（B）為其冪集，且AB=，則P(A)P(B)為（）ABCD，49設(shè)集合A=1，2，3，10，下列定義的運(yùn)算關(guān)于集合A是不封閉的是（）Ax*y=maxx,yBx*y=minx,yCx*y=GCDx,y,即x,y的最大公約數(shù)Dx*y=LCMx,y,即x,y的最小公倍數(shù)51設(shè)A=1，2，3，4，5，B=6，7，8，9，10，以下關(guān)系是從A到B的入射函數(shù)的是（）Af =,Bf =,Cf =,Df =,52設(shè)簡(jiǎn)單圖G所有結(jié)點(diǎn)的度數(shù)之和為12，則G一定有（）A3條邊B4條邊C5條邊D6條邊53下列不一定是樹的是（）A無回路的連通圖B有n個(gè)結(jié)點(diǎn)，n-1條邊的連通圖C每對(duì)結(jié)點(diǎn)之間都有通路的圖D連通但刪去一條邊則不連通的圖54下面關(guān)于關(guān)系R的傳遞閉包t(R)的描述最確切的是（）At(R)是包含R的二元關(guān)系Bt(R)是包含R的最小傳遞關(guān)系Ct(R)是包含R的一個(gè)傳遞關(guān)系Dt(R)是任何包含R的傳遞關(guān)系55歐拉回路是（）A路徑B跡C既是初級(jí)回路也是跡D既非初級(jí)回路也非跡56.在公式中變?cè)獃是（ ）A自由變?cè)狟約束變?cè)狢既是自由變?cè)质羌s束變?cè)狣既不是自由變?cè)?，又不是約束變?cè)?7設(shè)A=1，2，3，A上二元關(guān)系S=，則S是（ ）A自反關(guān)系B反自反關(guān)系C對(duì)稱關(guān)系D傳遞關(guān)系59設(shè)A是正整數(shù)集，R=(x，y)|x，yAx+3y=12，則R (2，3，4，62，3，4，6)=（ ）A O/BC，D，61結(jié)點(diǎn)數(shù)為奇數(shù)且所有結(jié)點(diǎn)的度數(shù)也為奇數(shù)的連通圖必定是（ ）A歐拉圖B漢密爾頓圖C非平面圖D不存在的62無向圖G是歐拉圖當(dāng)且僅當(dāng)G是連通的且（ ）AG中各頂點(diǎn)的度數(shù)均相等BG中各頂點(diǎn)的度數(shù)之和為偶數(shù)CG中各頂點(diǎn)的度數(shù)均為偶數(shù)DG中各頂點(diǎn)的度數(shù)均為奇數(shù)63平面圖(如下)的三個(gè)面的次數(shù)分別是（）A11，3，4B11，3，5C12，3，6D10，4，65.設(shè)A=a,b,c,則AA中的元素有( )。 A.3個(gè) B.6個(gè) C.8個(gè) D.9個(gè)66.設(shè)(G,+,*)是一個(gè)除環(huán),則它不滿足的運(yùn)算律是( )。 A.加法交換律 B.乘法交換律 C.乘法消去律 D.加法消去律67.對(duì)于一個(gè)代數(shù)系統(tǒng),以下命題成立的是( )。 A.每個(gè)元素必有左逆元 B.一個(gè)元素有左逆元,則它也是右逆元 C.一個(gè)元素的左右逆元不一定相等 D.一個(gè)元素的左逆元存在時(shí)必唯一68.若一個(gè)代數(shù)系統(tǒng)(A,*)滿足運(yùn)算封閉性及結(jié)合律,且有幺元,則它是( )。 A.獨(dú)異點(diǎn) B.群 C.格 D.布爾代數(shù)69.在有3個(gè)結(jié)點(diǎn)的圖中,奇結(jié)點(diǎn)的個(gè)數(shù)為( )。 A.0 B.1 C.1或3 D.0或2 71.若圖G有一條路經(jīng)過圖中每個(gè)結(jié)點(diǎn)恰好一次,則G( )。 A.有一條歐拉路 B.是歐拉圖 C.有一條漢密爾頓路 D.是漢密爾頓圖二、填空題（本大題共10小題，每小題2分，共20分）1任意兩個(gè)不同的小項(xiàng)的合取為_式，全體小項(xiàng)的析取式必為_式。2公式x(P(x)Q(x,y)zR(y, z)S(x)中的自由變?cè)獮開，約束變?cè)獮開。3設(shè)集合M=x|1x12,x被2整除，xZ,N=x|1x12,x被3整除，xZ，則 MN=_，MN=_。4設(shè)X=1，2，3，f：XX，g：XX，f=,g=,，則fg=_，gf=_。5設(shè)A=a,b,c，R是A上的二元關(guān)系，且給定R=,，則R的自反閉包r(R)= _，對(duì)稱閉包s(R)= _。6設(shè)*是集合S上的二元運(yùn)算，若運(yùn)算*滿足_且存在_，則稱為獨(dú)異點(diǎn)。7如下無向圖割點(diǎn)是_，割邊是_。8無向圖G具有生成樹，當(dāng)且僅當(dāng)_。G的所有生成樹中_的生成樹稱為最小生成樹。9、命題公式P7P有_組為T的真值指派，_為F的真值指派。10.一棵有6個(gè)葉結(jié)點(diǎn)的完全二叉樹，有_個(gè)內(nèi)點(diǎn)；而若一棵樹有2個(gè)結(jié)點(diǎn)度數(shù)為2，一個(gè)結(jié)點(diǎn)度數(shù)為3，3個(gè)結(jié)點(diǎn)度數(shù)為4，其余是葉結(jié)點(diǎn)，則該樹有_個(gè)葉結(jié)點(diǎn)。11.在一棵根樹中，有且只有一個(gè)結(jié)點(diǎn)的入度為_，其余所有結(jié)點(diǎn)的入度均為_。12.當(dāng)f:XY是_函數(shù)時(shí)，f有逆函數(shù)，且f -1。f=_。13.設(shè)E=1,2,3,4,5,6,A=1,4,B=1,2,3,C=2,4,則(AB)C=_,冪集P(AB)C)=_。14.由命題變?cè)捌浞穸ㄋM成的有限個(gè)析取式的合取式稱為_，由命題變?cè)捌浞穸ㄋM成的有限個(gè)合取式的析取式稱為_。15（x）（y）（P（x，y）Q（y，z）xP（x，y）中x的轄域?yàn)開，x的轄域?yàn)開。16兩個(gè)重言式的析取是_式，一個(gè)重言式與一個(gè)矛盾式的析取是_式。17設(shè)N是自然數(shù)集合，f和g是N到N的函數(shù)，且f（n）=2n+1，g（n）=n2，那么復(fù)合函數(shù)（ff）（n）=_（gf）（n）=_。18、設(shè)是群，則滿足結(jié)合律和_；20設(shè)A=1，2，B=2，3，則A-A=_，A-B=_。21設(shè)S是非空有限集，代數(shù)系統(tǒng)中，其中P（S）為集合S的冪集，則P（S）對(duì)運(yùn)算的單位元是_，零元是_。24在下圖中，結(jié)點(diǎn)v2的度數(shù)是_。25設(shè)圖D=，V=v1，v2，v3，v4，若D的鄰接矩陣A=，則deg-（v1）=_，從v2到v4長(zhǎng)度為2的路有_條。26不能再分解的命題稱為_，至少包含一個(gè)聯(lián)結(jié)詞的命題稱為_。27在命題演算中，五個(gè)聯(lián)結(jié)詞的含義是由其_表唯一確定的。28使公式（x）（y）（A（x）B（y）（x）A（x）（y）B（y）成立的條件是_不含有y，_不含有x。29設(shè)A為任意集合，請(qǐng)?zhí)钊脒m當(dāng)?shù)倪\(yùn)算符，使式子A_A=；A_A=成立。30設(shè)A=0，1，2，3，6，R=x,y|xy(x,yA)yx(mod 3)，則domR=_，ranR=_。31稱集合S是給定非空集合A的覆蓋：若S=S1，S2，Sn，其中SiA，Si，i=1，2，n，且_；進(jìn)一步若_，則S是集合A的劃分。32對(duì)實(shí)數(shù)的普通加法和乘法，_是加法的冪等元，_是乘法的零元。33若一條路中，所有邊均不相同，則此路稱作_；若一條路中所有的結(jié)點(diǎn)均不相同，則稱此路為_。35設(shè)A=0，1，2，3，R=x,y|x,yA(y=x+1y=)，S=x,y|x,yA（x=y+2）。試求RSR。36在簡(jiǎn)單無向圖G=中，如果V中的每個(gè)結(jié)點(diǎn)都與其余的所有結(jié)點(diǎn)鄰接，則該圖稱為_。37、AB的對(duì)偶式為_。39(1)畫出一個(gè)有歐拉回路的圖; (2)畫出一個(gè)有哈密爾頓回路的圖; (3)畫出一個(gè)有歐拉回路和哈密爾頓回路的圖.38設(shè)A=1，2，B=2，3，則AA=_，AB=_。39設(shè)A=1，2，3，4上關(guān)系R=,，則R的自反閉包r(R)= _，對(duì)稱閉包S（R）=_。40命題公式（PQ） P的成真指派為_，成假指派為_。41公式（）（F（x）G(y)）()(H(x)中的自由變?cè)獮開，約束變?cè)獮開。42設(shè)f :RR,f (x)=x2-2,g :RR,g(x)=x-1,那么復(fù)合函數(shù)=_，=_。46在根樹中，若每一個(gè)結(jié)點(diǎn)的出度_m,則稱這棵樹為m叉樹。如果每一個(gè)結(jié)點(diǎn)的出度_m或0，則稱這棵樹為完全m叉樹。47是一個(gè)群，其中Zn=0,1,2,n-1,xy=(x+y)mod n，則在中，1的階是_，4的階是_。48、對(duì)代數(shù)系統(tǒng)，其中*是S上的二元運(yùn)算，若a，bS，且對(duì)任意的xS，都有a*x=x*a=x，b*x=x*b=b，則稱a為運(yùn)算“*”的_，稱b為運(yùn)算“*”的_。49一個(gè)_且_的無向圖稱為樹。50在簡(jiǎn)單無向圖G=中，如果V中的每個(gè)結(jié)點(diǎn)都與其余的所有結(jié)點(diǎn)鄰接，則該圖稱為_，如果V有n個(gè)結(jié)點(diǎn)，那么它還是_度正則圖。.公式A(x)B(x)的前束范式為_。51.設(shè)論域?yàn)榧蟖,b,c，則(x)P(x)(x)Q(x)_。52.集合A上的關(guān)系“”稱為偏序關(guān)系，如果滿足_。53.設(shè)A=a,b,c，B=a,b,c,d,則AB=_。54.集合A=a,b,c上的關(guān)系R=,的對(duì)稱閉包為_。55.設(shè)A=1,2，A上的二元運(yùn)算定義為x*y=minx,y，則*的運(yùn)算表為_。56.設(shè)A=2,3,6,12，A上的序關(guān)系“”定義為：xy當(dāng)且僅當(dāng)x整除y.令B=2,3,6，則B的最小上界是_，B的極小元是_。60.的單位元是_。61.設(shè)圖G的鄰接矩陣為，則從結(jié)點(diǎn)v1到v3的長(zhǎng)度為2的路徑數(shù)為_，v2的數(shù)_的度數(shù)為_。62. 一顆完全二叉樹的高為3，則它至少有_片樹葉.三、計(jì)算題：1集合A=a, b, c, d, e上的二元關(guān)系R為R=, , , , , , , , , , , , ,（1）寫出R的關(guān)系矩陣,關(guān)系圖；（2）判斷R是否是等價(jià)關(guān)系,求出所有元素的等價(jià)類； （3）求出R所對(duì)應(yīng)的劃分（4）任意給劃分a,c,b,de,求出對(duì)應(yīng)的等價(jià)關(guān)系。2、求出下圖的最小生成樹3已知A=，1，B=，1，1，計(jì)算AB，AB，A的冪集P（A）。4構(gòu)造命題公式（PQ）P）R的真值表。5下圖給出了一個(gè)有向圖。