第一篇：離散數(shù)學(xué)復(fù)習(xí)題

離散數(shù)學(xué)復(fù)習(xí)題

一、填空

1、命題中的否定聯(lián)接詞；蘊含聯(lián)接詞

2、一個命題公式，若在所有賦值下取值為真，則稱此公式為式；若……假，則……..為 永假 式；若至少存在一組賦值，其命題為真，則…….為可滿足式。

3、有限布爾代數(shù)只能有n4、R是定義在集合上的二元關(guān)系，若R滿足性、性，則稱R是A上的等價關(guān)系。

5、全序集（A，≤）必是，且是

6、n階m條邊無向圖G是樹，當(dāng)且僅當(dāng)G是連通點，且m=

7、若有向樹G中，有一個頂點的入度為，則稱G為根樹。

8、有序?qū)?x,y>具有以下性質(zhì)

（1）當(dāng)x不等于y時，≠

（2）=的充要條件是x=u且y=r。

9、關(guān)系的性質(zhì)五。

10、圖中頂點作為邊的端點的稱為此頂點的度數(shù)。

11、設(shè)X是格，并對交運算時可分配的，則且 格中的交運算對并運算是可分配的。

12、有向圖按連通圖分為三類連通圖、連通圖、連通圖。

13、T 為一顆根樹，若T的每個分支點則稱T為r元正則樹。

14、設(shè)A、B是集合，求A與B之間關(guān)系（屬于、不屬于、包含…）如果A={1}，B={1,{1,2}}，則A不屬于B、A不包含B15、若R是定義在集合A上的一個二元關(guān)系，若R滿足、性、可傳遞性則稱R是偏序關(guān)系。

16、設(shè)集合A={1,2,3,4}，A上二元關(guān)系R={<1,1><1,3><2,1><3,3><3,4><4,3>}，則逆序關(guān)系R?1。

17、在有補分配格中，每個元素（的補元）都是的。

18、在無向圖中，度數(shù)為奇數(shù)的頂點個數(shù)必為數(shù)。

19、若圖中通路P中所有邊互不相同，則稱P為通路，若通路中所有頂點互不相同，則稱P為 基本 通路。

二、簡述題

1、偏序關(guān)系與格

2、設(shè)R是A愛上的二元關(guān)系，如果R是自反的，反對稱的，傳遞的二元關(guān)系，則稱R是A上的偏序關(guān)系或者半序關(guān)系；

2、等價關(guān)系與集合的劃分

3、握手定理

4、對偶式與對偶原理

5、正規(guī)子群

6、什么是域，有限整環(huán)是不是域，為什么？

7、集合的基本運算公式（集代數(shù)公式）有哪些？

8、群論中的拉格朗日定理

9、主析取范式與主合取范式

10、鴿巢原理與計數(shù)原理

三、判斷題

1、設(shè)A,B是集合，則A?=

2、偶數(shù)階循環(huán)群有且只有一個2階元素

3、設(shè)（G,?）是n階群，且有k階子群，則k丨n4、有限格必是有界格

5、偶數(shù)階群中比存在非幺元a，使得a?a=e6、不存在含有奇數(shù)個面且每個面上有奇數(shù)條棱的多面體

7、設(shè)（A，?）是獨異點，B是A的子集，且（B，?）是獨異點，則（B，?）一定是（A，?）的子獨異點8、3階群同構(gòu)意義下唯一

9、（N=（0），?）是一個群

10、素數(shù)階群一定沒有非平凡子群

四、計算題

1、求命題公式P∧（Q→R）主析取范式。

2、寫出3次對稱群（S3,?）的運算表及所有正規(guī)子群。

3、在1,2,3…….100這100個自然數(shù)中，可以被2或3整除但不能被5整除的數(shù)有多少個？

4、設(shè), A =3，P B=64，P A?B=256，求 B , A?B , A?B , A⊕B。

5、設(shè)A={a,b,c,d}，R={（a,c）,（c,b）,（b,a）,（a,d）}，求R，r R ,s R ,t(R)的關(guān)系矩陣或關(guān)系圖

6、命題公式 P∧Q ∨ ?P ∧(?Q)的真值表

7、寫出群(N13? 0,?13)各元素之階數(shù)

8、集合A={1,2,3,6,8,12}，求A 上的整除關(guān)系R并畫出Hasse圖

9、寫出（（a?4b）c?（7b+d））+（c+8a）的前綴式和后綴式

10、求（N6,?6）群的自同態(tài)

五、證明題

1、證明（N13? 0，?13）是循環(huán)群

2、證明不存在含有奇數(shù)個面且每個面上有奇數(shù)個棱的多面體

3、設(shè)（A,?）是代數(shù)系統(tǒng)，R是（A,?）上的同余關(guān)系，(A R,?)是其商代數(shù)，設(shè)f是A到A/R的函數(shù)，對于A中任意元素a，都有f a = a R

證明：f是（A,?）到(A R,?)的同態(tài)映射

4、設(shè)T是完全k元樹，若分枝點為i，樹葉數(shù)為t，證明：i=(t?1)/(k?1)

5、證明偶數(shù)階群必有二階子群，且必有奇數(shù)個二階子群

6、R是集合A上的等價關(guān)系，證明：對任意x，y屬于A在此處鍵入公式。

（1）若xRy，則 x R= y R

（2）若(x,y)?R，則 x R∩ x R=?

7、證明下列說法是等價的（1）A≤B（2）A?B=?（3）A∩B=A（4）A∪B=B8、證明邏輯等價式P?Q? P?Q ?(?P??Q)

9、證明10階群必有5階子群

第二篇：離散數(shù)學(xué)復(fù)習(xí)題

離散數(shù)學(xué)復(fù)習(xí)題

? 設(shè)命題p，r的真值為1，命題q，s的真值為0，則（p→q）(﹁r→s)的真值

為。

? 只要4不是素數(shù)，3就是素數(shù)，用謂語表達式符號化為。

? D=｛｝，則冪集ρ(D)=

? A={a,}，B=｛｝，則A×B=

? 若集合A，B的元素個數(shù)分別為|A|=m,|B|=n,則A到B有種不同二元關(guān)系。? 設(shè)A=｛1,2,3,4｝，B=｛4,5，6,7｝，R=｛<1,4>，<1,6><2,4>，<3,5>，<3,6>｝是由A

到B的二元關(guān)系，則domR=，ranR=

? I A是集合A上的恒等關(guān)系，A上的關(guān)系R具有性當(dāng)且僅當(dāng)IAR。? 二元關(guān)系R是等價關(guān)系，當(dāng)且僅當(dāng)?shù)腞是。

9.設(shè)K4是有4個點的無向完全圖，則K4有條邊。

10.無向圖G是歐拉圖當(dāng)且僅當(dāng)。

11.在任何無向圖這，所有頂點的度數(shù)之和等于邊數(shù)的倍。

12.設(shè)K5是有5個點的無向完全圖，則K5有條邊。

13.無向圖G是歐拉圖當(dāng)且僅當(dāng)。

計算題

? 求公式（PQ）→（QR）的主析取范式

? 集合A=｛a,b,c｝,R={,,,}是集合A上的二元關(guān)系，求R的自反

閉包r(R),對稱閉包s(R)和傳遞閉包t(R)(用矩陣運算)，并畫出各閉包的關(guān)系圖。? 設(shè)圖G

? 寫出G的鄰接矩陣

? 求各結(jié)點的初度，入度

? 求V3到V2長度是3的路的數(shù)目

? 設(shè)集合A=｛1,2，3,4,6,8，12｝，R是A上的整除關(guān)系，? 畫出偏序圖的哈斯圖；

證明題

? 在自然推理系統(tǒng)p中構(gòu)造下面推理的證明

前提：﹁r，﹁pr，（q）→p

結(jié)論：q→﹁

? 在自然系統(tǒng)p中構(gòu)造下面推理的證明

前提：pq,p→r,q→s

結(jié)論：sr

第三篇：離散數(shù)學(xué)復(fù)習(xí)題1

邏輯

1、給出的真值表

2、證明為永真式 謂詞量詞和推理

1、使用量詞和謂詞表達不存在這一事實

2、證明前提“在這個班上的某個學(xué)生沒有讀過書”和班上的每個學(xué)生都通過了第一門考試蘊含結(jié)論“通過考試的某個人沒有讀過書” 集合、函數(shù)、數(shù)列與求和

1、全集為，求集合A=的位串？它的補集的位串是什么？寫出集合A=的所有子集，寫出集合

2、從集合到集合能定義多少個函數(shù)？下面給出的函數(shù)其定義為：該函數(shù)是雙射嗎？是滿射嗎？該函數(shù)是否存在逆函數(shù)？如果存在請給出其逆函數(shù)。計數(shù)

1、計算機系統(tǒng)的美國用戶有一個6～8個字符構(gòu)成的密碼，其中每個字符是一個大寫字母或數(shù)字，且每個密碼必須至少包含一個數(shù)字，問總共有多少個合適的密碼？

2、在30天的一個月里，某棒球隊一天至少打一場比賽，但最多打45場。證明一定有連續(xù)的若干天內(nèi)這個球隊恰好打了14場比賽

3、證明n個元素的集合中允許重復(fù)的r組合數(shù)等于

4、按照字典順序生成整數(shù)1，2，3的所有排列（不允許重復(fù)），在362541后面按照字典順序的下一個最大排列是什么？找出在1000100111后面的下一個最大的二進制串。關(guān)系

1、求下面給出關(guān)系R的自反閉包、對稱閉包和傳遞閉包的0-1關(guān)系矩陣，其中

2、S是所有比特串的集合，關(guān)系定義為當(dāng)s=t或者s和t的長度至少是3，且前3個比特相同時具有關(guān)系，例如0101，0011100101，但01010，0101101110。證明是S上的等價關(guān)系，由產(chǎn)生的S的等價類是那些集合？

3、偏序集（{2,4,5,10,12,20,25},|）的那些元素是極大的，那些元素是極小的？ 圖與樹

1、在下圖所示的圖中，從a 到d的長度為4的通路有幾條？該圖是否是Euler圖，是否是Hamilton圖，該圖的度序列是什么？該圖是否可平面，如果是請給出平面畫圖，該圖的點色數(shù)和邊色數(shù)等于多少？給出該圖的一個生成樹，2、求下面賦權(quán)圖從a到z的最短距離是多少？最短路徑是什么？（畫圖給出標(biāo)號過程）

3、用哈夫曼編碼方法來編碼下列符號，這些符號具有下列頻率：A:0.08，B:0.10，C:0.12，D:0.15，E:0.20，F(xiàn):0.35,該編碼方法編碼一個字符的平均位數(shù)是多少？

4、下面樹的高度是多少？那些節(jié)點是內(nèi)部節(jié)點，那些節(jié)點是葉子節(jié)點，該樹是否是3元正則樹？分別給出該樹節(jié)點的前序、中序、后序遍歷的節(jié)點訪問次序

第四篇：本科離散數(shù)學(xué)復(fù)習(xí)題

離散數(shù)學(xué)復(fù)習(xí)題

一、填空題

1.集合A={?,1}，B={1,2}，則2A?2B=_________，2A?2B=_________.A與B的笛卡爾積A?B=_________.2.1000以內(nèi)的所有正整數(shù)中，能被4和5同時整除的共有_____個，不能被6整除的共有_____個

3.設(shè)集合A={1,2,3}，B={a,b,c}，則A?B共有_____個元素。A到B 的關(guān)系

(包括空關(guān)系)共有_____個，其中又有_____個是A?B的函數(shù), 有_____ 個是A? B的內(nèi)射, 有_____ 個是A? B的雙射。

4.設(shè)A={1,2,3,4,5,6,7,8}.則由B15 表示的A的子集是____________.A的一個子集{2,3,5,7}可表示為____________ 5.集合A={1,2,3,4}，上的兩個關(guān)系 ?1={(1,2),(1,3),(2,1)(2,2),(4,1)}，?2={(1,3),(3,1)}，則?1??2=____________.?1??2=____________.?=_________.?6=_________ ?1?2=____________.?2?1=____________.?116.集合 A={1,2,3} 上的關(guān)系 ?={(1,1),(1,2),(1,3),(3,3)} 具有的性質(zhì)是 _____.7.集合 A={1,2,3,4} 上具有自反性的關(guān)系有_____個，具有對稱性的關(guān)系有_____個，8.設(shè)集合A={a,b,c,d}，則A共有_____中不同的分劃，A上共有_____個不同的等價關(guān)系。若其中的一個分劃則與之對應(yīng)的等價關(guān)系是________________.?A={{a},{b,c},vx3zi2e}，若A上的等價關(guān)系：??{(a,a),(b,b),(c,c),(d,d),(a,c),(c,a),(b,d),(d,b}.則由?導(dǎo)出的A的分劃是____________.9.設(shè)?是集合A={1,2,3,4,5,6,7,8,9,10}上的關(guān)于模3同余關(guān)系，則[2]?=______________________.10.A={1,2,3,4,5,6,7,8,9,10,11,12,24}, ?是集合A上的整除關(guān)系, B?A且 B={2,4,6},則B的最大元是______.最小元是______.上界是______.下界是 ______.最小上界是______.最大下界是______.A的最大元是______.最小元是 ______.A11.在格?2,??中，集合 A={1,2,3,4,5,6},2A的兩元素{1,2}?{2,3,5}______.{1,2}與{2,3,5}上界有 ______個.{1,2}?{2,3,5}是______.{2,3,4}與{2,4,5}共有______個不同的下界.{1,2,4,6}的補元是________.13.設(shè)為任意的格,a,b,c,d?L, 若a?b且b?c,則a?c=______________.b?c=______________.a?c=______________.a?b=______________.14.自然數(shù)集上的整除關(guān)系是一個格, 則在格 ?N,?.中

8?12=______________8?12=______________.9?11=______________9?11=______________.15.Z是整數(shù)集,函數(shù) ?定義為:Z?Z,且 ?(X)=|X|-2X,則函數(shù)?的類型是_____(內(nèi)射,滿射,雙射).16.設(shè)A={1,2,3,4,5},函數(shù)?: A?A, ?(x)=6-x, 則函數(shù)?是一個_________射, 17.設(shè)函數(shù)?: R?R，則

f(x)?x2?2，函數(shù)g: R?R, g(x)?x?4

f?g?____,g?f?____.f?1(x)?_________.18.設(shè)集合A={1,2,3,4,5,6,7,8,9,10},B={2,4,6,8,10,12,14,16,18,20}，函數(shù)f:A?B,f(i)?18?2i,i?A，設(shè)H??1,2,5,6,??A,則f(H)?______，設(shè)G??4,8,10,16??B,則f?1(G)?_____.19.含10條邊的圖的總度數(shù)是____________.20.含有8個頂點的完全圖共有______條邊.21.含6個結(jié)點,9條邊的無向連通圖,要得到此圖的一棵生成樹,必須刪去__條邊.22.不同構(gòu)且有6個結(jié)點的樹共有______個.23.簡單圖G=共有10個結(jié)點,其中6個結(jié)點的度數(shù)為3，其余4個結(jié)點的 度數(shù)都為2, 則該圖共有____條邊.該圖的補圖共有____條邊.24.簡單圖G共有9個結(jié)點,且圖G與它的補圖同構(gòu)，則該圖共有____條邊.25.一棵樹有2個2度分支點, 1個3度分支點, 3個4度分支點, 則此樹共有____片樹葉.26.若完全圖Kn既是歐拉圖又是哈密爾頓，則n滿足的條件是__________ 2 27.命題P:“小王學(xué)過高等數(shù)學(xué)”.Q:“小王學(xué)過離散數(shù)學(xué)”.則符合命題“小王學(xué)過 高等數(shù)學(xué)但沒有學(xué)過離散數(shù)學(xué)”可表示為___________.命題?(P?Q)表示的 復(fù)合命題含義是:__________________________________________________.28.公式((?P?Q)?(?Q??P))?P可化簡為___________________________.29.將公式P?(Q?P)化成與之等價的且只含?和?的公式，則此公式為: __________________.30.令P,Q的賦值分別為1,0.則公式

（(?P?Q)?(?Q??P)）?（P??Q的真值為__________________.31.公式A含兩個命題變元P,Q，其主析取范式為：

(?P?Q)?(?Q??P)），則它的主合取范式是______________.二、選擇題

1.設(shè)集合A={a，{a}}，則下列錯誤的是().A){a}?2A;B){a}?2A;C){{a}}?2A； D){{a}}?2A;

2.集合A={1,2,3,4,5,6,7,8,9,10}, A上的關(guān)系?={(x,y)|x+y=10，x,y?A},則關(guān) 系 ?具有的性質(zhì)是().A)自反的;B)對稱的;C)傳遞的,對稱的;D)反自反的,對稱的;

3.設(shè)集合X={-1,1,2,3}與Y={1,2,3,4,5,9}, ?(x)=x2,是X?Y的一個函數(shù),則下列 正確的是().A)?是內(nèi)射但不是滿射;

B)?是滿射但不是內(nèi)射;C)?是雙射;

D)?既不是入射也不是滿射;

4.設(shè)I為整數(shù)集合.A={x | x2<30，x?I}, B={x | x為質(zhì)數(shù)，x<20}, C={1,3,5}, 則(C-A)?(B-A)=().A){1,2,3,5};B)?;

C){1,3,5,7};

D){1,2,3,5,7};5.在下面的三個命題公式

1)(P?Q)?(P?Q);2)(P?Q)?(P?Q);3)(P?Q)?(Q?P);中是永真式的公式有()個.A)0;B)1;C)2;D)3;

6.下面論斷正確的是().A)有補格一定是分配格;B)有補格一定是有界格;C)任何一個格必有最大元;D)偏序集就是格;

7.下列命題中錯誤的是().A)若L為有限集,則格必定是有限格;

B)在格中,?a,b?L,必有a?(a?b)=a;C)格是有補格當(dāng)且僅當(dāng)有元素存在補元;

D)在有補分配格中,?a,b?L, 必有a?b=a?b;

8.一個含n個結(jié)點,連通且有圈的簡單圖,至少有()條邊.A)

n;B)n+1;C)n+2;D)2n-1;

三、判斷題

1.設(shè)A={?}, B=22, 則: {?}?B且{?}?B.A

()

()2.集合A={a,b,c}上的關(guān)系?={(a,b),(a,c)}是不可傳遞的.3.平面上直線間的“平行關(guān)系”是等價關(guān)系.()4.人群中的“朋友關(guān)系”是偏序

()5.若?g是滿射,則?必是滿射.()6.若?, g都是入射,則g??也是入射.()7.在有限分配格中,一個元素若有補元,則補元一定是唯一的.()8.K4有10個生成子圖.()9.三個(4,2)無向簡單圖中,至少有兩個同構(gòu).()10.凡陳述句都是命題.()11.命題公式(P?(P?Q))?Q是矛盾式.()12.命題“如果1+2=3，那么雪是黑的”是真命題.。

13.判定偏序集是否為格.（教材P150頁圖7-

3、P174頁圖7-12）

四、解答題

1.設(shè)集合A={1,2,4,5},B={1,2,3,5,16,25}，A到B的關(guān)系?={(x,y)|x?A,y?B且y=x2}, 1)寫出?的所有元素;

2)求出關(guān)系?的定義域及值域;3)寫出關(guān)系?的關(guān)系矩陣M?;4)判斷關(guān)系?是否為A?B的一個函數(shù)? 2.設(shè)集合A={1,2,3,4},?是A上的一個關(guān)系,?的關(guān)系矩陣如下:

求:?的自反閉包r(?),對稱閉包s(?),傳

遞閉包t(?).4.設(shè)集合A={1,2,3,6,12,24,36,72},A上的整除關(guān)系?={(a,b)|a,b?A且a|b}.1)畫出偏序集的次序圖;2)A的子集B={6,24,36},求集合{x|x?A,且x能整除B中的每一個整數(shù)}，并求集合{x|x?A,且x能被B中的每一個整數(shù)整除}.3)判定偏序集是否為格?說明理由.5.偏序集的次序圖 如下:

1)求B1={b,c,e}的最小元,最大元.2)求B2={b,c,d,e}的上界,最小上界,下界,最大下界.3)求A的最小元,最大元.4)偏序集是否為格?為什么?

6.格的次序圖如下:

1)求出A中所有元素的補元.2)判定格是否為有補格?為什么? 3)判定格是否為分配格?為什么?

7.無向簡單圖G的鄰接矩陣如下：

?0??1?1??0?0??0? 11000??01000?10110??01001?01000??00100??

求圖G的所有割點、割邊.8.有向圖G=如下:

1)

2)3)4)5)

求G的鄰接矩陣;求deg(V1);

從結(jié)點V2到V4長度為3的路有幾條? 圖中長度為2的回路有幾條? 求d(V1 , V4)

9.求下面有權(quán)圖的一棵最小生成樹.并求出最小權(quán)數(shù).10.求公式(P?(Q?R))?(R?(Q?P))的主析取范式和主合取范式.11.掌握歐拉圖、哈密頓圖的判定.(教材P227頁第16、17、18題)

五、證明題

1.證明： P?(Q?R)?Q?(P?R)2.證明：（Q?(P??P)?(R?(P??P))?R? 3.用推理規(guī)則證明: 1)(P?Q)?R, ?S?U, ?R?S, U?W, ?W??P??Q.2)證明:Q?S是前提,?P??Q?R, Q?(R?S), P的有效結(jié)論.4.試給出以下推理證明: 若這里舉行足球賽，則交通就會很擁堵.若他們按時到了球場，則說明交通是暢通的.他們按時到達了.所以這里沒有舉行足球賽.5.設(shè)是一個格,a,b,c,d?L, 若a?b且c?d.求證:a?c?b?d.6.設(shè)是一個格,a,b,c, ?L.證明：（a?b）?(b?c)?(a?c)?(a?b)?(b?c)?(a?c).7.設(shè)N是自然數(shù)集,定義N上的二元關(guān)系?={(x,y)|x?N,y?N,x+y是偶數(shù)} 證明?是一個等價關(guān)系.8.證明：自然數(shù)集N上的“整除關(guān)系”是一個偏序

9.證明：在（n,m）的樹中，m = n-1 6

第五篇：離散數(shù)學(xué)復(fù)習(xí)題(期末測試卷)

復(fù)習(xí)題

一、填空題（請將每空的正確答案寫在答題紙相應(yīng)位置處，答在試卷上不得分。每小題2分，共16分。）

1．謂詞公式?x?y(P(x,y)?Q(y,z))??xR(x,y)中?x的轄域是。

2．命題公式(p??q)的成真賦值為。

3．在1和1000之間（包括1和1000在內(nèi)）不能被4和5整除的數(shù)有個。

4．設(shè)R是定義在集合A?{1,2,3,4}上的二元關(guān)系R?{?1,1?,?1,2?,?2,3?,?1,4?}，則R的對稱閉包s(R)?。

5．A?{1,2,3,4},x?y?min{x,y},則代數(shù)系統(tǒng)?A,??中的零元是。

6．具有10個結(jié)點的無向完全圖的邊數(shù)=。

7．一次同余方程3x??1(mod5)的最小正整數(shù)解是。

8．84與198的最大公約數(shù)是。

二、單項選擇題（從下列各題四個備選答案中選出一個正確答案，并將其代號寫在答題紙相應(yīng)位置處。答案錯選或未選者，該題不得分。每小題2分，共16分。）

1.設(shè)F(x): x是有理數(shù)，G(x)：x能表示成分數(shù)。在一階邏輯中，命題“沒有不能表示成分數(shù)的有理數(shù)”可符號化為()。

A.??x(F(x)??G(x))B.??x(F(x)??G(x))

C.??x(F(x)??G(x))D.??x(F(x)??G(x))

2.設(shè)個體域是整數(shù)集，則下列命題的真值為真的是()。

A．?y?x(x?y?1)B．?x?y(x?y?0)

C．?x?y(x?y?y2)D．?y?x(x?y?x2)

3.集合A?{1,2,?,10}上的關(guān)系R?{?x,y?|x?y?10,?x,y?A}，則R的性質(zhì)為()。

A、自反的B、傳遞的、對稱的C、對稱的D、反自反的、傳遞的4．對自然數(shù)集合N，下列定義的運算中()是不可結(jié)合的。

A.a?b?a?b?3B.a?b?a?2b

C.a?b?a?b(mod 3)D.a?b?min{a,b}

5．下列各圖中既是歐拉圖，又是漢密爾頓圖的是()。

A．B．C．D．

6．對于下列度數(shù)序列，可畫成簡單無向圖的是()。

A．(1，1，1，2，3)B．(1，2，2，3，4，5)

C．(1，2，3，4，5，5)D．(2，3，3，4，5，6)

7.含有5個結(jié)點、3條邊的不同構(gòu)的簡單圖有()個。A.2B.3C.4D.5【】

8．5的模6逆等于()。

A．1B．

3C．4D．5

三、計算題（第1、2、3、4小題各7分，第5、6小題各8分共44分。）1．求命題公式(p?q)?(p?r)的主析取范式和主合取范式。

2．設(shè)?A,R?為偏序集，其中A?{1,2,3,4,6,9,24,54}，R是A上的整除關(guān)系。（1）畫出?A,R?的哈斯圖；（2）求A中的極大元；（3）令B?{4,6,9}，求B的上確界和下確界。3．求下圖1中帶權(quán)無向圖的最小生成樹，并求出該最小生成樹的權(quán)值。4．求解遞推方程：an?7an?1?12an?2?0,a0?4,a1?6。5．有向圖D如圖2所示，求：（1）D中v1到v3長度為3的通路有幾條？（2）D中v1到v1長度為3的回路有幾條？（3）D是哪類連通圖？

v

4圖1圖

2v

36．在通訊中要傳輸字母a,b,c,d,e,f,g，它們出現(xiàn)的頻率為：

a:30%,b:20%,c:15%,d:10%,e:10%,f:9%,g:6%，設(shè)計傳輸上述字母的最佳二元前綴碼，畫出最優(yōu)樹，并求傳輸100個按上述頻率出現(xiàn)的字母所需二進制字個數(shù)。

四、證明題（每小題8分，共16分。）1．設(shè)R為自然數(shù)集N上的關(guān)系，定義N上的關(guān)系R如下：?x,y??R?x?y是偶數(shù)。（1）證明R為等價關(guān)系；（2）求商集N/R。2．設(shè)Z為整數(shù)集合，在Z上定義二元運算?如下：證明：?x,y?Z,x?y?x?y?2，?Z,??是群。

五、符號化下列命題，并在自然推理系統(tǒng)P中論證結(jié)論的有效性（8分。）

若小張喜歡數(shù)學(xué)，則小李或小趙也喜歡數(shù)學(xué)。若小李喜歡數(shù)學(xué)，則他也喜歡物理。小張確實喜歡數(shù)學(xué)，可小李不喜歡物理。所以，小趙喜歡數(shù)學(xué)。

參考答案

一、填空題（請將每空的正確答案寫在答題紙相應(yīng)位置處，答在試卷上不得分。每小題2分，共16分。）

1．P(x,y)?Q(y,z)2．10，11，003．600

4．{?1,1?,?1,2?,?2,3?,?1,4?,?2,1?,?3,2?,?4,1?}5．1 6．457．38．6

二、單項選擇題（從下列各題四個備選答案中選出一個正確答案，并將其代號寫在答題紙相應(yīng)位置處。答案錯選或未選者，該題不得分。每小題2分，共16分。）

1．C2．C3．C4．B5．C6．A7．C8．D

三、計算題（第1、2、3、4小題各7分，第5、6小題各8分共44分。）

1．解：主合取范式為：（5分）

(p?q)?(p?r)?(?p?q)?(?p?r)

?((?p?q)?(r??r))?((?p?r)?(q??q))?(?p?q?r)?(?p?q?r)?(?p?q?r)?(?p??q?r)?(?p?q?r)?(?p?q?r)?(?p??q?r)?M4?M5?M6

主析取范式為：（2分）

(p?q)?(p?r)?m0?m1?m2?m3?m7

?(?p??q??r)?(?p??q?r)?(?p?q??r)?(?p?q?r)?(p?q?r)2．解：（1）?A,R?的哈斯圖如下圖所示。（3分）

429（2）A中的極大元是：24，54；(2分)

（3）B的上確界：無；B的下確界：1。(2分)3．解：所求該圖的最小生成樹如下圖所示。（5分）

該最小生成樹的權(quán)值之和

W（t）=2+1+1+2+3+4=13（2分）

4．解：其特征方程為：x2?7x?12?0，其特征根是：x1?3,x2?4（2分）

通解為：an?c13n?c24n（2分）

代入初值得到：c1?c2?4,3c1?4c2?6

解得：c1?10,c2??6（2分）

所以，原方程的解為：

an?10?3n?6?4n。（1分）

5．解：先求圖D的鄰接矩陣A及A2、A3。

?1?1A??

?0??

1110??

2?2011?2?，（1分）A???1001?

??

000??1

122??

5?4111?3?,（2分）A???1000?

??110??2

233?

232??（2分）110?

?

122?

(1)D中v1到v3長度為3的通路有3條。（1分）(2)D中v1到v1長度為3的回路有5條。（1分）(3)D是強連通圖。（1分）

6．解：按字母順序，令pi為傳輸?shù)趇個字母的頻率，i?1,2,?,7，則傳輸100個字母，各字母出現(xiàn)的頻數(shù)為wi?100pi，得

w1?30,w2?20,w3?15,w4?10,w5?10,w6?9,w7?6。將它們按照從小到大順序排列，得6?9?10?10?15?20?30。（2分）以wi為權(quán)求最優(yōu)2叉樹如下圖所示。

6（4分）

傳輸?shù)那熬Y碼分別為：a?01,b?11,c?001,d?100,e?101,f?0001,g?0000。傳100個所需二進制數(shù)字個數(shù)為：

W(t)=15+30+60+100+40+20=265。（2分）

四、證明題（每小題8分，共16分。）1．（1）證明：

?x?N,因為x?x?2x，2x?N且是偶數(shù)，于是?x,x??R,因此R在N上是自反的；（1分）

?x,y?N,若?x,y??R,則x?y是偶數(shù)，即y?x是偶數(shù)，于是?y,x??R, 因此R在N上是對稱的；（1分）

?x,y,z?N,若?x,y??R且?y,z??R,則x?y?2k1?y?z?2k2,k1,k2?Z，于是x?z?(x?y)?(y?z)?2y?2(k1?k2?y)，進而?x,z??R,因此R在N上是傳遞的；（2分）

綜上所述，R是N上的等價關(guān)系。（1分）

（2）N關(guān)于等價關(guān)系R的所有等價類為[0]R?{0,2,4,6,???}和[1]R?{1,3,5,7,???}，則N/R?{[0]R,[1]R}。（3分）

2．證明：顯然，Z關(guān)于?是封閉的。（1分）

對于任意x,y,z?Z，由于

(x?y)?z?(x?y?2)?z?(x?y?2)?z?2?x?y?z?4，而 x?(y?z)?x?(y?z?2)?x?(y?z?2)?2?x?y?z?4，于是

(x?y)?z?x?(y?z)，即?滿足結(jié)合律。（2分）

（2分）?x?Z，因為x?2?x?2?2?x?2?x，因此2是Z關(guān)于?的單位元。

?x?Z，由于4?x?Z且x?(4?x)?x?(4?x)?2?2?(4?x)?x，于是

x關(guān)于?存在逆元4?x。（2分）所以，?Z,??是群。（1分）

五、符號化下列命題，并在自然推理系統(tǒng)P中論證結(jié)論的有效性（8分。）解：設(shè)簡單命題

p：小張喜歡數(shù)學(xué)。q：小李喜歡數(shù)學(xué)。

r：小趙喜歡數(shù)學(xué)。s：小李喜歡物理。（2分）前提：p?(q?r),q?s,p,?s 結(jié)論：r

（或?qū)憺椋和评硇问綖閜?(q?r),q?s,p,?s?r）（1分）證明：

(1)q?s前提引入(2)?s前提引入

（2）拒取式（2分）(3)?q（1）

(4)p?(q?r)前提引入(5)p前提引入

（5）假言推理（2分）(6)q?r（4）

（6）析取三段論（1分）(7)r（3）