期末練習題學期_第1頁
期末練習題學期_第2頁
期末練習題學期_第3頁
期末練習題學期_第4頁
期末練習題學期_第5頁
已閱讀5頁,還剩6頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權,請進行舉報或認領

文檔簡介

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)

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經(jīng)權益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論