期末練習題學期

1、習題一. 多重選擇填空題(本題包括16個空格，每個空格3分，共48分。每道小題都可能有一個以上的正確選項，須選出所有的正確選項，不答不得分，多選、少選或選錯都將按比例扣分。)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):x<y)，下列公式中_在解釋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

2、,y),g(x,y)3 是集合， =10，則=_。(1) 100 (2) 99 (3) 2048 (4) 1024 (5) 5124 集合=x|x是整數(shù)，<30，=x|x是質(zhì)數(shù)，x<20，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設A、B、C是集合，下列四個命題中，_在任何情況下都是正確的。(1) 若AB且BC，則AC (2) 若AB且BC，則AC(3) 若AB且BC，則AC (4) 若AB且BC，則AC5127S=1,2,3,4,5

3、,6,7,8,9,10,11,12，是S上的整除關系。S的子集2,4,6，則在(S，)中，的最大元是_；的最小元是_；的上確界是_；的下確界是_。(1) 不存在的 (2) 36 (3) 24 (4) 12 (5) 6 (6) 1 (7) 28設有有限布爾代數(shù)(B,+,*,0,1)，則=_能成立。(1) 1 (2) 2 (3) 3 (4) 4 (5) 5 (6) 8 (7) 99 n個結點、m條邊的無向連通圖是樹當且僅當m=_。(1) n+1 (2) n (3) n-1 (4)2n-1 二. 請給出命題公式的主析取范式。(10分)三. 假設下列陳述都是正確的：(1)學生會的每個成員都是學生并且是

4、班干部；(2)有些成員是女生。問是否有成員是女班干部？請將上述陳述和你的結論符號化，并給出你的結論的形式證明。(10分)四. 設R和S是集合上的等價關系,則SR必是等價關系。(10分)六。假設在圖G(有向圖或無向圖)中，有10條邊，4個3度的結點，其余結點的度數(shù)不大于2。問G中至少有幾個結點？(10分)一、選擇題1令P：今天下雪了，Q：路滑，則命題“雖然今天下雪了，但是路不滑”可符號化為（）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),

5、 Q(x)5設個體域A=a,b，公式xP(x)xS(x)在A中消去量詞后應為（）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下列選項中錯誤的是（）AØØBØØCØØDØØ7設A=a,b,c,d，A上的等價關系R=<a, b>, <b, a>, <c, d>, <d, c>IA，則對應于R的A的劃分是（）Aa,b, c,dBa, b,c, dCa,b,c,dDa, b, c,d8設R為實數(shù)集，函數(shù)f：RR，

6、f(x)=2x，則f是（）A滿射函數(shù)B入射函數(shù)C雙射函數(shù)D非入射非滿射10下列運算中關于整數(shù)集不能構成半群的是（）Aab=maxa, bBab=bCab=2abDab=|a-b|12設A=a, b, c，R是A上的二元關系，R=<a, a>, <a, b>, <a, c>, <c, a>，那么R是（）A反自反的B反對稱的C可傳遞的D不可傳遞的13設D=<V, E>為有向圖，V=a, b, c, d, e, f, E=<a, b>, <b, c>, <a, d>, <d, e>, <

7、f, e>是（）A強連通圖B單向連通圖C弱連通圖D不連通圖14在有n個結點的連通圖中，其邊數(shù)（）A最多有n-1條B至少有n-1條C最多有n條D至少有n條15連通圖G是一棵樹，當且僅當G中（）A有些邊不是割邊B每條邊都是割邊C無割邊集D每條邊都不是割邊16下列命題公式中不是重言式的是（）Ap(qr)Bp(qp)Cp(pp)D(p(qr)(q(pr)17下列語句中為命題的是（）A這朵花是誰的？B這朵花真美麗啊！C這朵花是你的嗎？D這朵花是他的。18設個體域是整數(shù)集，則下列命題的真值為真的是（）Ayx(x·y=1)Bxy (x·y0)Cxy (x·y=y2)Dyx

8、(x·y=x2)19關于謂詞公式（x）(y)(P(x,y)Q(y,z)(x)p(x,y),下面的描述中錯誤的是（）A（x）的轄域是（y）（P（x,y）Q(y,z)）Bz是該謂詞公式的約束變元C（x）的轄域是P（x,y）Dx是該謂詞公式的約束變元20設論域D=a,b，與公式xA（x）等價的命題公式是（）AA（a）A（b）BA（a）A（b）CA（a）A（b）DA（b）A（a）21集合A=1，2，3上的下列關系矩陣中符合等價關系條件的是（）ABCD22設A=Ø，B=P（P（A），以下不正確的式子是（）AØ ，Ø ，Ø ，Ø 包含于BB

9、16; 包含于BCØ ，Ø 包括于BDØ ，Ø ，Ø 包含于B23設Z是整數(shù)集，E=，-4，-2，0，2，4，f：ZE，f（x）=2x，則f（）A僅是滿射B僅是入射C是雙射D無逆函數(shù)24設A=1，2，3，4，5，A上二元關系R=1，2，3，4，2，2，S=2，4，3，1，4，2，則S-1R-1的運算結果是（）A4，1，2，3，4，2B2，4，2，3，4，2C4，1，2，3，2，4D2，2，3，1，4，426在實數(shù)集合R上，下列定義的運算中不可結合的是（）Aa*b=a+b+2abBa*b=a+bCa*b=a+b+abDa*b=a-b27下列集合關

10、于所給定的運算成為群的是（）A已給實數(shù)a的正整數(shù)次冪的全體，且a0，1，-1，關于數(shù)的乘法B所有非負整數(shù)的集合，關于數(shù)的加法C所有正有理數(shù)的集合，關于數(shù)的乘法D實數(shù)集，關于數(shù)的除法28設無向圖中有6條邊，有一個3度頂點和一個5度頂點，其余頂點度為2，則該圖的頂點數(shù)是（）A3B4C5D629下列各圖中既是歐拉圖，又是漢密爾頓圖的是（）A B C D30設無向圖G的邊數(shù)為m，結點數(shù)為n，則G是樹等價于（）AG連通且m=n+1BG連通且n=m+1CG連通且m=2nD每對結點之間至少有一條通路31下列為兩個命題變元P，Q的小項是（）APQù PBù PQCù PQD

11、49; PPQ32下列語句中是真命題的是（）A我正在說謊B嚴禁吸煙C如果1+2=3，那么雪是黑的D如果1+2=5，那么雪是黑的33設P：我們劃船，Q：我們跑步。命題“我們不能既劃船又跑步”符號化為（）Aù Pù QBù Pù QCù（P«Q）Dù（ù Pù Q）34命題公式（P（PQ）Q是（）A矛盾式B蘊含式C重言式D等價式35命題公式ù（PQ）R的成真指派是（）A000，001，110，B001，011，101，110，111C全體指派D無36在公式（）F（x，y）（ y）G（x，y）中變元x

12、是（）A自由變元B約束變元C既是自由變元，又是約束變元D既不是自由變元，又不是約束變元37集合A=1，2，10上的關系R=<x，y>|x+y=10，xA，yA，則R的性質(zhì)是（）A自反的B對稱的C傳遞的、對稱的D反自反的、傳遞的38若R和S是集合A上的兩個關系，則下述結論正確的是（）A若R和S是自反的，則RS是自反的B若R和S是對稱的，則RS是對稱的C若R和S是反對稱的，則RS是反對稱的D若R和S是傳遞的，則RS是傳遞的39R=<1，4>，<2，3>，<3，1>，<4，3>，則下列不是t（R）中元素的是（）A<1，1>B&l

13、t;1，2>C<1，3>D<1，4>40設A=1，2，3，4，5，6，7，8，下列選項正確的是（）A1AB1，2，3AC4，5ADÆA41在自然數(shù)集N上，下列運算是可結合的是（）Aab=a-2bBab=mina，bCab=-a-bDab=|a-b|45具有4個結點的非同構的無向樹的數(shù)目是（）A2B3C4D547設A-B=Æ，則有（）AB=ÆBBÆCABDAB48A，B是集合，P（A），P（B）為其冪集，且AB=Æ，則P(A)P(B)為（）AÆBÆCÆDÆ，Æ49設集

14、合A=1，2，3，10，下列定義的運算關于集合A是不封閉的是（）Ax*y=maxx,yBx*y=minx,yCx*y=GCDx,y,即x,y的最大公約數(shù)Dx*y=LCMx,y,即x,y的最小公倍數(shù)51設A=1，2，3，4，5，B=6，7，8，9，10，以下關系是從A到B的入射函數(shù)的是（）Af =<1,8>,<3,9>,<4,10>,<2,6>,<5,7>Bf =<1,7>,<2,6>,<4,8>,<1,9>,<5,10>Cf =<1,6>,<2,7>,

15、<4,9>,<3,8>Df =<1,10>,<5,9>,<3,6>,<4,6>,<2,8>52設簡單圖G所有結點的度數(shù)之和為12，則G一定有（）A3條邊B4條邊C5條邊D6條邊53下列不一定是樹的是（）A無回路的連通圖B有n個結點，n-1條邊的連通圖C每對結點之間都有通路的圖D連通但刪去一條邊則不連通的圖54下面關于關系R的傳遞閉包t(R)的描述最確切的是（）At(R)是包含R的二元關系Bt(R)是包含R的最小傳遞關系Ct(R)是包含R的一個傳遞關系Dt(R)是任何包含R的傳遞關系55歐拉回路是（）A路徑B跡C

16、既是初級回路也是跡D既非初級回路也非跡56.在公式中變元y是（ ）A自由變元B約束變元C既是自由變元，又是約束變元D既不是自由變元，又不是約束變元57設A=1，2，3，A上二元關系S=<1，1>，<1，2>，<3，2>，<3，3>，則S是（ ）A自反關系B反自反關系C對稱關系D傳遞關系59設A是正整數(shù)集，R=(x，y)|x，yAx+3y=12，則R (2，3，4，6×2，3，4，6)=（ ）A O/B<3，3>C<3，3>，<6，2>D<3，3>，<6，2>，<9，1&g

17、t;61結點數(shù)為奇數(shù)且所有結點的度數(shù)也為奇數(shù)的連通圖必定是（ ）A歐拉圖B漢密爾頓圖C非平面圖D不存在的62無向圖G是歐拉圖當且僅當G是連通的且（ ）AG中各頂點的度數(shù)均相等BG中各頂點的度數(shù)之和為偶數(shù)CG中各頂點的度數(shù)均為偶數(shù)DG中各頂點的度數(shù)均為奇數(shù)63平面圖(如下)的三個面的次數(shù)分別是（）A11，3，4B11，3，5C12，3，6D10，4，65.設A=a,b,c,則A×A中的元素有( )。 A.3個 B.6個 C.8個 D.9個66.設(G,+,*)是一個除環(huán),則它不滿足的運算律是( )。 A.加法交換律 B.乘法交換律 C.乘法消去律 D.加法消去律67.對于一個代數(shù)系統(tǒng),

18、以下命題成立的是( )。 A.每個元素必有左逆元 B.一個元素有左逆元,則它也是右逆元 C.一個元素的左右逆元不一定相等 D.一個元素的左逆元存在時必唯一68.若一個代數(shù)系統(tǒng)(A,*)滿足運算封閉性及結合律,且有幺元,則它是( )。 A.獨異點 B.群 C.格 D.布爾代數(shù)69.在有3個結點的圖中,奇結點的個數(shù)為( )。 A.0 B.1 C.1或3 D.0或2 71.若圖G有一條路經(jīng)過圖中每個結點恰好一次,則G( )。 A.有一條歐拉路 B.是歐拉圖 C.有一條漢密爾頓路 D.是漢密爾頓圖二、填空題（本大題共10小題，每小題2分，共20分）1任意兩個不同的小項的合取為_式，全體小項的析取式必為

19、_式。2公式x(P(x)Q(x,y)zR(y, z)S(x)中的自由變元為_，約束變元為_。3設集合M=x|1x12,x被2整除，xZ,N=x|1x12,x被3整除，xZ，則 MN=_，MN=_。4設X=1，2，3，f：XX，g：XX，f=<1, 2>,<2,3>,<3,1>,g=<1,2>,<2,3>,<3,3>，則fg=_，gf=_。5設A=a,b,c，R是A上的二元關系，且給定R=<a,b>,<b,c>,<c,a>，則R的自反閉包r(R)= _，對稱閉包s(R)= _。6設*是集合

20、S上的二元運算，若運算*滿足_且存在_，則稱<S，*>為獨異點。7如下無向圖割點是_，割邊是_。8無向圖G具有生成樹，當且僅當_。G的所有生成樹中_的生成樹稱為最小生成樹。9、命題公式P7P有_組為T的真值指派，_為F的真值指派。10.一棵有6個葉結點的完全二叉樹，有_個內(nèi)點；而若一棵樹有2個結點度數(shù)為2，一個結點度數(shù)為3，3個結點度數(shù)為4，其余是葉結點，則該樹有_個葉結點。11.在一棵根樹中，有且只有一個結點的入度為_，其余所有結點的入度均為_。12.當f:XY是_函數(shù)時，f有逆函數(shù)，且f -1。f=_。13.設E=1,2,3,4,5,6,A=1,4,B=1,2,3,C=2,4,

21、則(AB)C=_,冪集P(AB)C)=_。14.由命題變元及其否定所組成的有限個析取式的合取式稱為_，由命題變元及其否定所組成的有限個合取式的析取式稱為_。15（x）（y）（P（x，y）Q（y，z）xP（x，y）中x的轄域為_，x的轄域為_。16兩個重言式的析取是_式，一個重言式與一個矛盾式的析取是_式。17設N是自然數(shù)集合，f和g是N到N的函數(shù)，且f（n）=2n+1，g（n）=n2，那么復合函數(shù)（ff）（n）=_（gf）（n）=_。18、設<S，*>是群，則<S，*>滿足結合律和_；20設A=1，2，B=2，3，則A-A=_，A-B=_。21設S是非空有限集，代數(shù)系統(tǒng)

22、<P（S），>中，其中P（S）為集合S的冪集，則P（S）對運算的單位元是_，零元是_。24在下圖中，結點v2的度數(shù)是_。25設圖D=<V，E>，V=v1，v2，v3，v4，若D的鄰接矩陣A=，則deg-（v1）=_，從v2到v4長度為2的路有_條。26不能再分解的命題稱為_，至少包含一個聯(lián)結詞的命題稱為_。27在命題演算中，五個聯(lián)結詞的含義是由其_表唯一確定的。28使公式（x）（y）（A（x）B（y）（x）A（x）（y）B（y）成立的條件是_不含有y，_不含有x。29設A為任意集合，請?zhí)钊脒m當?shù)倪\算符，使式子A_A=Ø；A_A=Ø成立。30設A=0，

23、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，且_；進一步若_，則S是集合A的劃分。32對實數(shù)的普通加法和乘法，_是加法的冪等元，_是乘法的零元。33若一條路中，所有邊均不相同，則此路稱作_；若一條路中所有的結點均不相同，則稱此路為_。35設A=0，1，2，3，R=x,y|x,yA(y=x+1y=)，S=x,y|x,yA（x=y+2）。試求RSR。36在簡單無向圖G=<V，E>中，如果V 中的每個結點都與其余的所有結點鄰

24、接，則該圖稱為_。37、AB的對偶式為_。39(1)畫出一個有歐拉回路的圖; (2)畫出一個有哈密爾頓回路的圖; (3)畫出一個有歐拉回路和哈密爾頓回路的圖.38設A=1，2，B=2，3，則AA=_，AB=_。39設A=1，2，3，4上關系R=<1,2>,<2,4>,<3,3>,<1,3>，則R的自反閉包r(R)= _，對稱閉包S（R）=_。40命題公式（PQ）ù P的成真指派為_，成假指派為_。41公式（）（F（x）G(y)）()(H(x)中的自由變元為_，約束變元為_。42設f :RR,f (x)=x2-2,g :RR,g(x)=x

25、-1,那么復合函數(shù)=_，=_。46在根樹中，若每一個結點的出度_m,則稱這棵樹為m叉樹。如果每一個結點的出度_m或0，則稱這棵樹為完全m叉樹。47<Zn,>是一個群，其中Zn=0,1,2,n-1,xy=(x+y)mod n，則在<Z6,>中，1的階是_，4的階是_。48、對代數(shù)系統(tǒng)<S，*>，其中*是S上的二元運算，若a，bS，且對任意的xS，都有a*x=x*a=x，b*x=x*b=b，則稱a為運算“*”的_，稱b為運算“*”的_。49一個_且_的無向圖稱為樹。50在簡單無向圖G=<V，E>中，如果V中的每個結點都與其余的所有結點鄰接，則該圖稱為

26、_，如果V有n個結點，那么它還是_度正則圖。.公式A(x)B(x)的前束范式為_。51.設論域為集合a,b,c，則(x)P(x)(x)Q(x)_。52.集合A上的關系“”稱為偏序關系，如果滿足_。53.設A=a,b,c，B=a,b,c,d,則AB=_。54.集合A=a,b,c上的關系R=<a,b>,<c,c>,<b,c>的對稱閉包為_。55.設A=1,2，A上的二元運算定義為x*y=minx,y，則*的運算表為_。56.設A=2,3,6,12，A上的序關系“”定義為：xy當且僅當x整除y.令B=2,3,6，則B的最小上界是_，B的極小元是_。60.<整

27、數(shù)集,加>的單位元是_。61.設圖G的鄰接矩陣為，則從結點v1到v3的長度為2的路徑數(shù)為_，v2的數(shù)_的度數(shù)為_。62. 一顆完全二叉樹的高為3，則它至少有_片樹葉.三、計算題：1集合A=a, b, c, d, e上的二元關系R為R=<a,a>, <a,b>, <a,c>, , <b,b>, <b,a>, <b,c>, <c,c>, <c,a>, <c,b>, <d,d>, <d,e>, <e,e>,<e,d>（1）寫出R的關系矩陣,關系圖；（2）判斷R是否是等價關系,求出所有元素的等價類； （3）求出R所對應的劃分（4）任意給劃分a,c,b,de,求出對應的等價關系。2、求出下圖的最小生成樹3已知A=Æ，Æ，1，B=Æ，1，1，計算AB，AB，A的冪集P（A）