《離散數(shù)學(xué)題庫.doc》由會員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué)題庫.doc（20頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、 《離散數(shù)學(xué)》題庫 一、選擇或填空 （數(shù)理邏輯部分） 1、下列哪些公式為永真蘊(yùn)含式？(　　　) (1)Q=>Q→P (2)Q=>P→Q (3)P=>P→Q (4)P(PQ)=>P 2、下列公式中哪些是永真式？( ) (1)(┐PQ)→(Q→R) (2)P→(Q→Q) (3)(PQ)→P (4)P→(PQ) 3、設(shè)有下列公式，請問哪幾個(gè)是永真蘊(yùn)涵式?( ) (1)P=>PQ (2) PQ=>P (3) PQ=>PQ (4)P(P→Q)=>Q (5) (P→Q)=>P (6) P(PQ)=>P 4

2、、公式"x((A(x)B(y，x)) $z C(y，z))D(x)中，自由變元是( )，約束變元是( )。 5、判斷下列語句是不是命題。若是，給出命題的真值。( ) (1) 北京是中華人民共和國的首都。 (2) 陜西師大是一座工廠?！? (3) 你喜歡唱歌嗎？ (4) 若7+8＞18，則三角形有4條邊?！? (5) 前進(jìn)！ (6) 給我一杯水吧！ 6、命題“存在一些人是大學(xué)生”的否定是( )，而命題“所有的人都是要死的”的否定是( )。 7、設(shè)P：我生病，Q：我去學(xué)校，則下列命題可符號化為( )。 (

3、1)　只有在生病時(shí)，我才不去學(xué)校 (2) 若我生病，則我不去學(xué)校 (3)　當(dāng)且僅當(dāng)我生病時(shí)，我才不去學(xué)校(4) 若我不生病，則我一定去學(xué)校 8、設(shè)個(gè)體域?yàn)檎麛?shù)集，則下列公式的意義是( )。 (1) "x$y(x+y=0) (2) $y"x(x+y=0) 9、設(shè)全體域D是正整數(shù)集合，確定下列命題的真值： (1) "x$y (xy=y)　　(　　)　　(2) $x"y(x+y=y)　　(　　) (3) $x"y(x+y=x) 　(　　)　　(4) "x$y(y=2x)　　 (　　) 10、設(shè)謂詞P(x)：x是奇數(shù)，Q(x)：x是偶數(shù)，謂詞公式 $x(P(x)Q(x))在哪

4、個(gè)個(gè)體域中為真?( ) (1) 自然數(shù)　　(2) 實(shí)數(shù)　　 (3) 復(fù)數(shù)　　(4) (1)--(3)均成立 11、命題“2是偶數(shù)或-3是負(fù)數(shù)”的否定是（ ）。 12、永真式的否定是（ ） (1) 永真式　(2) 永假式　(3) 可滿足式　(4) (1)--(3)均有可能 13、公式(PQ)(PQ)化簡為（ ），公式 Q(P(PQ))可化簡為（ ）。 14、謂詞公式"x(P(x) $yR(y))Q(x)中量詞"x的轄域是（ ）。 15、令R(x):x是實(shí)數(shù)，Q(x):x是有理數(shù)。則命題“并非每個(gè)實(shí)數(shù)都是有理數(shù)”的符號化表示為（

5、 ）。 （集合論部分） 16、設(shè)A={a,{a}}，下列命題錯(cuò)誤的是（ ）。 (1) {a}P(A)　(2) {a}P(A)　(3) {{a}}P(A)　(4) {{a}}P(A) 17、在0（ ）之間寫上正確的符號。 (1) =　(2) 　(3) 　(4) 18、若集合S的基數(shù)|S|=5，則S的冪集的基數(shù)|P(S)|=（ ）。 19、設(shè)P={x|(x+1)4且xR},Q={x|5x+16且xR},則下列命題哪個(gè)正確（ ） (1) QP　　(2) QP　(3) PQ　(4) P=Q 20、下列各集合中，哪幾個(gè)分別相等( )

6、。 (1) A1={a,b} (2) A2={b,a} (3) A3={a,b,a} (4) A4={a,b,c} (5) A5={x|(x-a)(x-b)(x-c)=0} (6) A6={x|x2-(a+b)x+ab=0} 21、若A-B=Ф，則下列哪個(gè)結(jié)論不可能正確？( ) (1) A=Ф (2) B=Ф　(3) AB (4) BA 22、判斷下列命題哪個(gè)為真?( ) (1) A-B=B-A => A=B (2) 空集是任何集合的真子集 (3) 空集只是非空集合的子集 (4) 若A的一個(gè)元素屬于B，則A=B 23、判斷下列命

7、題哪幾個(gè)為正確？(　　　)　 (1) {Ф}∈{Ф,{{Ф}}} (2) {Ф}{Ф,{{Ф}}} (3) Ф∈{{Ф}} (4) Ф{Ф} (5) {a,b}∈{a,b,{a},} 24、判斷下列命題哪幾個(gè)正確？(　　　　　) (1) 所有空集都不相等 (2) {Ф}Ф (4) 若A為非空集，則AA成立。 25、設(shè)A∩B=A∩C，∩B=∩C，則B(　)C。 26、判斷下列命題哪幾個(gè)正確？(　　　　　) (1) 若A∪B＝A∪C，則B＝C (2) {a,b}={b,a} (3) P(A∩B)P(A)∩P(B) （P(S)表示S的冪集） (4) 若A為非空

8、集，則AA∪A成立。 27、Ａ，Ｂ，Ｃ是三個(gè)集合，則下列哪幾個(gè)推理正確： (1) AB，BC=> AC (2) AB，BC=> A∈B (3) A∈B，B∈C=> A∈C （二元關(guān)系部分） 28、設(shè)Ａ＝｛1,2,3,4,5,6｝，B={1,2,3}，從Ａ到B的關(guān)系Ｒ＝｛〈x,y〉|x=y2｝，求(1)R (2) R-1 。 29、舉出集合A上的既是等價(jià)關(guān)系又是偏序關(guān)系的一個(gè)例子。(　　　　) 30、集合A上的等價(jià)關(guān)系的三個(gè)性質(zhì)是什么？( ) 31、集合A上的偏序關(guān)系的三個(gè)性質(zhì)是什么？( ) 32、設(shè)A={１,２,３,４}，Ａ上的關(guān)系Ｒ＝｛〈

9、1,2〉，〈2,1〉，〈2,3〉，〈3,4〉｝ 求(1)RR (2) R-1 33、設(shè)Ａ＝｛1，2，3，4，5，6｝，Ｒ是A上的整除關(guān)系，求R= {(　　　　　)}。 34、設(shè)Ａ＝｛1,2,3,4,5,6｝，B={1,2,3}，從Ａ到B的關(guān)系Ｒ＝｛〈x,y〉|x=2y｝，求(1)R (2) R-1 。 35、設(shè)Ａ＝｛1,2,3,4,5,6｝，B={1,2,3}，從Ａ到B的關(guān)系Ｒ＝｛〈x,y〉|x=y2｝，求R和R-1的關(guān)系矩陣。 36、集合A={1,2,…,10}上的關(guān)系R={|x+y=10,x,yA}，則R 的性質(zhì)為（ ）。 (1) 自反的　　(2) 對稱

10、的　　 (3) 傳遞的，對稱的 (4) 傳遞的 （代數(shù)結(jié)構(gòu)部分） 37、設(shè)A={2,4,6}，A上的二元運(yùn)算*定義為：a*b=max{a,b}，則在獨(dú)異點(diǎn)中，單位元是( )，零元是( )。 38、設(shè)A={3,6,9}，A上的二元運(yùn)算*定義為：a*b=min{a,b}，則在獨(dú)異點(diǎn)中，單位元是( )，零元是( )； （半群與群部分） 39、設(shè)〈G,*〉是一個(gè)群，則 (1) 若a,b,x∈G，ax=b，則x=( )； (2) 若a,b,x∈G，ax=ab，則x=( )。 40、設(shè)a是12階群的生成元， 則a2是(

11、 )階元素，a3是( )階元素。 41、代數(shù)系統(tǒng)是一個(gè)群，則G的等冪元是(　　　　)。 42、設(shè)a是10階群的生成元， 則a4是( )階元素，a3是( )階元素。 43、群的等冪元是(　　)，有(　　　)個(gè)。 44、素?cái)?shù)階群一定是( )群, 它的生成元是( )。 45、設(shè)〈G,*〉是一個(gè)群，a,b,c∈G，則 (1) 若ca=b，則c=( )；(2) 若ca=ba，則c=( )。 46、是的子群的充分必要條件是( )。 47、群＜A,*＞的等冪元有(　　　)個(gè)

12、，是(　　　)，零元有(　　　)個(gè)。 48、在一個(gè)群〈G,*〉中，若G中的元素a的階是k，則a-1的階是( )。 49、在自然數(shù)集N上，下列哪種運(yùn)算是可結(jié)合的？（ ） (1) a*b=a-b　　(2) a*b=max{a,b}　(3) a*b=a+2b　(4) a*b=|a-b| 50、任意一個(gè)具有2個(gè)或以上元的半群，它（ ）。 (1) 不可能是群　　(2) 不一定是群　 (3) 一定是群 　(4) 是交換群 51、6階有限群的任何子群一定不是（ ）。 (1) 2階　　(2) 3 階 (3) 4 階 　(4) 6 階 （格與布爾

13、代數(shù)部分） 52、下列哪個(gè)偏序集構(gòu)成有界格（ ） (1) （N,）　(2) （Z,） (3) （{2,3,4,6,12},|（整除關(guān)系）） 　(4) (P(A),) 53、有限布爾代數(shù)的元素的個(gè)數(shù)一定等于（ ）。 (1) 偶數(shù)　(2) 奇數(shù) (3) 4的倍數(shù) 　(4) 2的正整數(shù)次冪 （圖論部分） 54、設(shè)G是一個(gè)哈密爾頓圖，則G一定是( )。 (1) 歐拉圖 (2) 樹 　(3) 平面圖 (4)　連通圖 55、下面給出的集合中，哪一個(gè)是前綴碼？(　　　　　　) (1) {0，10，110，101111}　　　(2)

14、 {01，001，000，1} (3) {b，c，aa，ab，aba}　　　 (4) {1，11，101，001，0011} 56、一個(gè)圖的哈密爾頓路是一條通過圖中( )的路。 57、在有向圖中，結(jié)點(diǎn)v的出度deg+(v)表示( )，入度deg-(v)表示( )。 58、設(shè)G是一棵樹，則G 的生成樹有( )棵。 (1) 0　　(2) 1　　(3) 2　　(4) 不能確定 59、n階無向完全圖Kn 的邊數(shù)是( )，每個(gè)結(jié)點(diǎn)的度數(shù)是( )。 60、一棵無向樹的頂點(diǎn)數(shù)n與邊數(shù)m關(guān)系是(　　　　)。 61、一個(gè)圖的歐拉回路是一條通過圖中(

15、 )的回路。 62、有n個(gè)結(jié)點(diǎn)的樹，其結(jié)點(diǎn)度數(shù)之和是(　　　　)。 63、下面給出的集合中，哪一個(gè)不是前綴碼( )。 (1) {a，ab，110，a1b11} (2) {01，001，000，1} (3) {1，2，00，01，0210} (4) {12，11，101，002，0011} 64、n個(gè)結(jié)點(diǎn)的有向完全圖邊數(shù)是( )，每個(gè)結(jié)點(diǎn)的度數(shù)是( )。 65、一個(gè)無向圖有生成樹的充分必要條件是( )。 66、設(shè)G是一棵樹，n,m分別表示頂點(diǎn)數(shù)和邊數(shù)，則 (1) n=m (2) m=n+1 (3) n=m+1 (4) 不能確定。 67

16、、設(shè)T=〈V,E〉是一棵樹，若|V|>1，則T中至少存在( )片樹葉。 68、任何連通無向圖G至少有( )棵生成樹，當(dāng)且僅當(dāng)G 是( )，G的生成樹只有一棵。 69、設(shè)G是有n個(gè)結(jié)點(diǎn)m條邊的連通平面圖，且有k個(gè)面，則k等于: (1) m-n+2 (2) n-m-2 (3) n+m-2 (4) m+n+2。 70、設(shè)T是一棵樹，則T是一個(gè)連通且( )圖。 71、設(shè)無向圖G有16條邊且每個(gè)頂點(diǎn)的度數(shù)都是2，則圖G有( )個(gè)頂點(diǎn)。 (1) 10 (2) 4 (3) 8 (4) 16 72、設(shè)無向圖G有18條邊且每

17、個(gè)頂點(diǎn)的度數(shù)都是3，則圖G有( )個(gè)頂點(diǎn)。 (1) 10 (2) 4 (3) 8 (4) 12 73、設(shè)圖G=，V={a，b，c，d，e}，E={,,,,},則G是有向圖還是無向圖？ 74、任一有向圖中，度數(shù)為奇數(shù)的結(jié)點(diǎn)有(　　　)個(gè)。 75、具有6 個(gè)頂點(diǎn)，12條邊的連通簡單平面圖中，每個(gè)面都是由(　　)條邊圍成？ (1) 2　　(2) 4　　(3) 3　　(4) 5 76、在有n個(gè)頂點(diǎn)的連通圖中，其邊數(shù)（ ）。 (1) 最多有n-1條　　(2) 至少有n-1 條 (3) 最多有n條

18、 　　(4) 至少有n 條 77、一棵樹有2個(gè)2度頂點(diǎn)，1 個(gè)3度頂點(diǎn)，3個(gè)4度頂點(diǎn)，則其1度頂點(diǎn)為（ ）。 (1) 5　　(2) 7 (3) 8 　(4) 9 78、若一棵完全二元（叉）樹有2n-1個(gè)頂點(diǎn)，則它（ ）片樹葉。 (1) n　　(2) 2n (3) n-1 　(4) 2 79、下列哪一種圖不一定是樹（ ）。 (1) 無簡單回路的連通圖　　(2) 有n個(gè)頂點(diǎn)n-1條邊的連通圖 (3) 每對頂點(diǎn)間都有通路的圖 　(4) 連通但刪去一條邊便不連通的圖 80、連通圖G是一棵樹當(dāng)且僅當(dāng)G中（ ）。 (1) 有些邊是割邊　　

19、(2) 每條邊都是割邊 (3) 所有邊都不是割邊 　(4) 圖中存在一條歐拉路徑 （數(shù)理邏輯部分） 二、求下列各公式的主析取范式和主合取范式： 1、(P→Q)R　 2、(PR)(QR)P 3、(P→Q)(RP) 4、Q→(PR) 5、P→(P(Q→P)) 6、(P→Q)(RP) 7、P(P→Q) 　　　　 8、(R→Q)P 9、P→Q 10、　PQ　 11、PQ 12、（PR）Q 13、（PQ）R 14、(P(QR))(P(QR)) 15、P(P(Q(

20、QR))) 16、(PQ)(PR) 三、證明： 1、P→Q，QR，R，SP=>S 2、A→(B→C)，C→(DE)，F(xiàn)→(DE),A=>B→F 3、PQ， P→R, Q→S => RS 4、(P→Q)(R→S)，(Q→W)(S→X)，(WX)，P→R => P 5、(UV)→(MN), UP, P→(QS)，QS =>M 6、BD，(E→F)→D，E=>B 7、P→(Q→R)，R→(Q→S) => P→(Q→S) 8、P→Q，P→R，R→S =>S→Q 9、P→(Q→R) => (P→Q)→(P→R) 10、P→(Q→R)，Q→P,S→R,P =>S 11、A，

21、A→B， A→C， B→(D→C) => D 12、A→(CB)，B→A，D→C => A→D 13、(PQ)(RQ) （PR）Q 14、P(QP)P(PQ) 15、（PQ）（PR），(QR)，SPS 16、PQ，QR，RS P 17、用真值表法證明ＰＱ (ＰＱ)(ＱＰ) 18、P→QP→(PQ) 19、用先求主范式的方法證明(P→Q)(P→R) (P→（QR） 20、(P→Q)(QR) P 21、為慶祝九七香港回歸祖國，四支足球隊(duì)進(jìn)行比賽，已知情況如下，問結(jié)論是否有效? 前提: (1) 若A隊(duì)得第一，則B隊(duì)或C隊(duì)獲亞軍; (2) 若C隊(duì)獲亞軍，則A隊(duì)不能獲冠軍;

22、 (3) 若D隊(duì)獲亞軍，則B隊(duì)不能獲亞軍; (4) A 隊(duì)獲第一; 結(jié)論: (5) D隊(duì)不是亞軍。 22、用推理規(guī)則證明PQ, (QR),PR不能同時(shí)為真。 (集合論部分) 四、設(shè)Ａ，Ｂ，Ｃ是三個(gè)集合，證明： 1、A (B－C)＝(AB)－(AC) 2、(A－B)(A－C)=A－(BC) 3、AB=AC，B=C，則C=B　　 4、AB=A(B-A) 5、A=B AB= 　　 6、AB = AC，AB=AC，則C=B 7、AB=AC，B=C，則C=B 8、A－(BC)＝(A－B)－C　　 9、(A－B)(A－C)=A－(BC)　 10、A-B=B，

23、則A=B= 11、A=(A-B)(A-C)ABC= 12、(A-B)(A-C)=ABC 13、(A-B)(B-A)=A B= 14、(A-B)-CA-(B-C) 15、P(A)P(B)P(AB) （P(S)表示S的冪集） 16、P(A)P(B)=P(AB) （P(S)表示S的冪集） 17、（A-B）B=（AB）-B當(dāng)且僅當(dāng)B=。 n，則c的階整除m與n的最大公因子(m,n)。 五、證明或解答： （數(shù)理邏輯、集合論與二元關(guān)系部分） 1、設(shè)個(gè)體域是自然數(shù)，將下列各式翻譯成自然語言： (1) xy（xy=1）; (2) xy(xy=1); (3) xy

24、 (xy=0); (4) xy（xy=0）; (5) xy (xy=x); (6) xy（xy=x）; (7) xyz (x-y=z) 2、設(shè)A(x,y,z): x+y=z, M（x,y,z）: xy=z, L(x,y): xy， 個(gè)體域?yàn)樽匀粩?shù)。將下列命題符號化： （1）沒有小于0的自然數(shù); （2）xyz; （4）存在x，對任意y 使得xy=y; （5）對任意x，存在y使x+y=x。 3、列出下列二元關(guān)系的所有元素： （1）A=

25、{0,1,2},B={0,2,4},R={|x,y}; （2）A={1,2,3,4,5},B={1,2},R={|2x+y4且x且yB}; （3）A={1,2,3},B={-3,-2,-1,0,1},R={||x|=|y|且x且yB}; 4、對任意集合A,B，證明：若AA=BB，則B=B。 5、對任意集合A,B，證明：若A，AB=AC，則B=C。 故B=C。 6、設(shè)A={a,b}, B={c}。求下列集合： (1) A{0,1}B； (2) B2A； (3) (AB)2; (4) P(A)A。 7、設(shè)全集U={a,b,c

26、,d,e}, A={a,d}, B={a,b,c}, C={b,d}。求下列各集合： （1）AB； （2）；（3）(A)C; （4）P(A)-P(B); （5）(A-B)(B-C); （6）(AB)C; 8、設(shè)A,B,C是任意集合，證明或否定下列斷言： （1）若AB，且BC，則AC； （2）若AB，且BC，則AC; （3）若AB，且BC，則AC； （4）若AB，且BC，則AC； 9、A上的任一良序關(guān)系一定是A上的全序關(guān)系。 10、若R和S都是非空集A上的等價(jià)關(guān)系，則RS是A上的等價(jià)關(guān)系?！? 11、設(shè)RAA，則R自反 IAR。 12、設(shè)A是集合，RAA，則R是對稱的R

27、＝R－1。 13、設(shè)A，B，C和D均是集合，RAB，SBC，TCD，則 (1)　　R(ST)=(RS)(RT)； (2)　　R(ST)(RS)(RT)； 14、設(shè)〈A,≤〉為偏序集，BA，若B有最大(小)元、上(下)確界，則它們是惟一的。 15、設(shè)A={1,2,3},寫出下列圖示關(guān)系的關(guān)系矩陣，并討論它們的性質(zhì)： 1 1 1 2 3 2 3 2 3 16、設(shè)A={1,2,…,10}

28、。下列哪個(gè)是A的劃分？若是劃分，則它們誘導(dǎo)的等價(jià)關(guān)系是什么？ （1）B={{1,3,6},{2,8,10},{4,5,7}}; （2）C={{1,5,7},{2,4,8,9},{3,5,6,10}}; （3）D={{1,2,7},{3,5,10},{4,6,8},{9}} 17、R是A={1,2,3,4,5,6}上的等價(jià)關(guān)系， R=I{<1,5>,<5,1>,<2,4>,<4,2>,<3,6>,<6,3>} 求R誘導(dǎo)的劃分。 18、A上的偏序關(guān)系的Hasse圖如下。 （1） 下列哪些關(guān)系式成立：ab,ba,ce,ef,df,cf； （2） 分別求出下列集合關(guān)于的極大（?。┰?、

29、最大（?。┰?、上（下）界及上（下）確界（若存在的話）： (a) A; (b) {b,d}; (c) {b,e}; (d) {b,d,e} a e f b d c （半群與群部分） 19、求循環(huán)群C12={e,a,a2,…,a11}中H={e,a4,a8}的所有右陪集。 20、求下列置換的運(yùn)算： 21、試求出8階循環(huán)群的所有生成元和所有子群。 22、

30、I上的二元運(yùn)算*定義為：a,bI，a*b=a+b-2。試問是循環(huán)群嗎？ 23、設(shè)是群，aG。令H={xG|ax=xa}。試證：H 是G 的子群。 24、證明：偶數(shù)階群中階為2 的元素的個(gè)數(shù)一定是奇數(shù)。 25、證明：有限群中階大于2的元素的個(gè)數(shù)一定是偶數(shù)。 26、試求中每個(gè)元素的階。 27、設(shè)是群，a,bG，ae，且a4b=ba5。試證abba。 28、I上的二元運(yùn)算*定義為：a,bI，a*b=a+b-2。試證：為群。 29、設(shè)為半群，aS。令Sa={ai | iI+ }。試證是的子半群。 30、單位元

31、有惟一逆元。 31、設(shè)e和0是關(guān)于A上二元運(yùn)算*的單位元和零元，如果|A|>1，則e0。 32、證明在元素不少于兩個(gè)的群中不存在零元。 33、證明在一個(gè)群中單位元是惟一的。 34、設(shè)a是一個(gè)群〈G,*〉的生成元，則a-1也是它的生成元。 35、在一個(gè)偶數(shù)階群中一定存在一個(gè)2階元素。 36、代數(shù)系統(tǒng)是一個(gè)群，則G除單位元以外無其它等冪元。 37、設(shè)是一個(gè)群，則對于a,b∈G，必有唯一的x∈G，使得ax=b。 38、設(shè)半群中消去律成立，則是可交換半群當(dāng)且僅當(dāng)a,bS，（ab）2=a2b2。 39、設(shè)群除單位元外每個(gè)元素的階均為2，則

32、,＊>是交換群。 40、設(shè)*是集合A上可結(jié)合的二元運(yùn)算，且a,bA,若a*b=b*a，則a=b。試證明： （1）aA,a*a=a，即a是等冪元； （2） a,bA,a*b*a=a; （3） a,b,cA,a*b*c=a*c。 41、設(shè)是群，作f:GG,aa-1。證明：f是G的自同構(gòu)G是交換群。 42、若群的子群滿足|G|＝2|H|，則一定是群的正規(guī)子群。 43、設(shè)H和K都 是G的不變子群。證明：HK也是G 的不變子群。 44、設(shè)群G的中心為C（G）={aG|xG,ax=xa}。證明C（G）是G的不變子群。 45、設(shè)是沒有

33、非平凡子群的有限群。試證：G是平凡群或質(zhì)數(shù)階的循環(huán)群。 46、設(shè)H和K都是G 的有限子群，且|H|與|K|互質(zhì)。試證：HK={e}。 47、素?cái)?shù)階循環(huán)群的每個(gè)非單位元都是生成元。 48、若是可交換獨(dú)異點(diǎn)，T為S中所有等冪元的集合，則是的子獨(dú)異點(diǎn)。 49、設(shè)是群，且a∈G的階為n，k∈I，則|ak|＝，其中(k,n)為k和n的最大公因子。 50、設(shè)是有限群，|G|＝n，則a∈G，|a|n。 51、設(shè)G＝(a)，若G為無限群，則G只有兩個(gè)生成元a和a-1； 52、設(shè)G＝(a)，{e}HG，am是H中a 的最小正冪，則 （1） H＝(am)

34、； （2） 若G為無限群，則H也是無限群； 53、設(shè)G＝(a)，|G|＝n，則對于n 的每一正因子d，有且僅有一個(gè)d階子群。因此n階循環(huán)群的子群的個(gè)數(shù)恰為 n的正因子數(shù)。 54、設(shè)h是從群到的群同態(tài)，G和G2的單位元分別為e1和e2，則 （1） h(e1)=e2； （2） aG1，h(a-1)=h(a)-1； （3） 若HG1，則h(H)G2； （4） 若h為單一同態(tài)，則aG1，|h(a)|=|a|。 55、有限群G的每個(gè)元素的階均能整除G的階。 56、證明：在同構(gòu)意義下，只有兩個(gè)四階群，且都是循環(huán)群。 57、在一個(gè)群〈G,*〉中，若G中的元

35、素a的階是k，即 |a|=k，則a-1的階也是k。 58、在一個(gè)群中，若A和B 都是G的子群。若AB=G，則A=G或B=G。 59、設(shè)e是奇數(shù)階交換群的單位元，則G的所有元素之積為e。 60、設(shè)S=QQ，Q為有理數(shù)集合，*為S上的二元運(yùn)算：對任意(a,b),(c,d)S,有 (a,b)*(c,d)=(ac,ad+b), 求出S關(guān)于二元運(yùn)算*的單位元，以及當(dāng)a0時(shí)，(a,b)關(guān)于*的逆元。 61、設(shè)是一個(gè)群，H、K是其子群。定義G上的關(guān)系R：對任意a,b∈G，aRb 存在 h∈H,k∈K, 使得b=h*a*k，則R是G上的等價(jià)關(guān)系。 62、設(shè)

36、H是G的子群，則下列條件等價(jià)： （1） H是G的不變子群； （2） a∈G，aHa-1H； （3） a∈G，a-1HaH； （4） a∈G，h∈G，aha-1H。 63、在半群中，若對a,bG，方程a*x=b 和y*a=b都有惟一解，則是一個(gè)群。 64、設(shè)是群， H和K都是G的子群，令HK={h*s | s∈K，h∈H}, KH={s*h |s∈K,h∈H},，是G的子群的充分必要條件是HK=KH。 65、設(shè)H和K都 是G的不變子群。證明：HK也是G 的不變子群。 66、設(shè)為群，a,b,cG。若a*b=c

37、*b*a,a*c=c*a,b*c=c*b，且a,b的階分別為m, （格與布爾代數(shù)） 67、當(dāng)n分別是24，36，110時(shí)，是布爾代數(shù)嗎？若是，則求出其原子集。 68、設(shè)L是有界格，且|L|>1。證明：01。 證明： 69、設(shè)是格，若a,b,cL，a≤b≤c，則 ab=b⊙c , (a⊙b)(b⊙c)=(ab)⊙(ac) 70、在布爾代數(shù)中，證明恒等式a(b)=ab 71、設(shè)是格，a1,a2,…,anL。試證：a1a2…an= a1a2…an當(dāng)且僅當(dāng)a1=a2=…=an。 72、在布爾代數(shù)中，證明恒等式(ac)(b)(bc)=(ac)(b)

38、 73、在布爾代數(shù)中，證明恒等式(ab)(c)(c)=(ab)c 74、設(shè)是格，a,b,c,dL。試證：若ab且cd，則 acbd 75、當(dāng)n分別是10,45時(shí)，畫出的哈斯圖。 76、在布爾代數(shù)中，證明恒等式 (a)(b)(c)=(b)(c)(a) 77、設(shè)是格，a,bL，且a≤b，記 I[a,b]={xL|a≤x≤b} 則是的子格。 78、設(shè)A＝{a,b,c}，求的子格（P(A)表示A的冪集）。 79、證明：在同構(gòu)意義下，4階格只有2個(gè)。 80、設(shè)是有界格，是A上的全序

39、關(guān)系。若|A|＞2，則aA-{0,1}，a無補(bǔ)元。 81、格是模格a,b,cL，有 a(b(ac))=(ab)(ac) 82、設(shè)是分配格， a,b,cL。若(ab)＝(ac)且(ab)＝(ac)，則b＝c。 83、證明：在有補(bǔ)分配格中，每個(gè)元素的補(bǔ)元一定惟一。 84、設(shè)是格，則L是分配格當(dāng)且僅當(dāng)a,b,cL，有 (ab)ca(bc) 85、設(shè)是一布爾代數(shù)，則 是一個(gè)交換群，其中＋定義為 a+b=(a⊙b′)(a′⊙b)。 86、設(shè)是一布爾代數(shù)，則 R={ | ab

40、=b}是S上的偏序關(guān)系。 87、設(shè)是一布爾代數(shù)，則關(guān)系={ | a⊙b=a}是S上的偏序關(guān)系?！? （圖論部分） 88、證明在有n個(gè)結(jié)點(diǎn)的樹中，其結(jié)點(diǎn)度數(shù)之和是2n-2。 88、任一圖中度數(shù)為奇數(shù)的結(jié)點(diǎn)是偶數(shù)個(gè)。 89、連通無向圖G的任何邊一定是G的某棵生成樹的弦。這個(gè)斷言對嗎？若是對的請證明之，否則請舉例說明。 90、設(shè)T=是一棵樹，若|V|>1，則T中至少存在兩片樹葉。 91、畫一個(gè)使它分別滿足： (1) 有歐拉回路和哈密爾頓回路； (2) 有歐拉回路，但無條哈密爾頓回路； (3) 無歐拉回路，但有哈密爾頓回路； (4)

41、既無歐拉回路，又無哈密爾頓回路。 92、設(shè)無向圖G=，|E|=12。已知有6個(gè)3度頂點(diǎn)，其他頂點(diǎn)的度數(shù)均小于3。問G中至少有多少個(gè)頂點(diǎn)？ 93、設(shè)圖G=，|V|=n，|E|=m。k度頂點(diǎn)有nk個(gè)，且每個(gè)頂點(diǎn)或是k度頂點(diǎn)或是k+1度頂點(diǎn)。證明：nk=(k+1)-2m。 94、設(shè)G=是一個(gè)連通且|V|=|E|+1的圖，則G中有一個(gè)度為1的結(jié)點(diǎn)。 95、若n階連通圖中恰有n-1 條邊，則圖中至少有一個(gè)結(jié)點(diǎn)度數(shù)為1。 96、若G有n個(gè)結(jié)點(diǎn)，m條邊，f個(gè)面，且每個(gè)面至少由k(k3)條邊圍成，則 mk(ｎ－2)／(ｋ－2)。 97、設(shè)G=是連通的簡單平

42、面圖，|V|=n3，面數(shù)為k,則k2n-4。 98、證明對于連通無向簡單平面圖，當(dāng)邊數(shù)e＜30時(shí)，必存在度數(shù)≤4的頂點(diǎn)。 99、在一個(gè)連通簡單無向平面圖G=〈V，E，F(xiàn)〉中若|V|3，則 |E|3|V|－6。 100、給定連通簡單平面圖G=，且|V|=6, |E|=12, 則對于任意fF, d(f)=3。 101、設(shè)G=是n個(gè)頂點(diǎn)的無向圖(n>2)，若對任意u,vV，有d(u)+d(v)n，則G是連通圖。 102、一次會議有20人參加，其中每個(gè)人都在其中有不下10個(gè)朋友。這20人圍成一圓桌入席，有沒有可能使任意相鄰而坐的兩個(gè)人都是朋友？為什么？ 103、證

43、明在任何兩個(gè)或兩個(gè)以上人的組內(nèi)，存在兩個(gè)人在組內(nèi)有相同個(gè)數(shù)的朋友。 104、設(shè)有如下有向圖G=， （1）求G的鄰接矩陣；（2）G中v1到v4的長度為4 的通路有多少條？（3）G中經(jīng)過v1的長度為3 的回路有多少條？（4）G中長度不超過4 的通路有多少條？其中有多少條通路？ v1 v4 v2 v3 題104圖 105、求下列無向圖中每個(gè)頂點(diǎn)的度數(shù)；求下列有向圖中每個(gè)頂點(diǎn)的出度、入度和度。 a

44、 d e c b f c b a 106、求下列無向圖的子圖、生成子圖、由邊集誘導(dǎo)的子圖和由頂點(diǎn)集誘導(dǎo)的子圖。 a

45、 d e c b f 題106圖 107、求下列賦權(quán)圖頂點(diǎn)間的距離。 d a e 4 3

46、 5 7 1 c b 14 f 108、求下列賦權(quán)圖中v1到其他頂點(diǎn)的距離。 v2 10 v4 3 v1

47、 2 2 6 4 3 4 v6 v3 2 v5 109、求下圖的可達(dá)矩陣。 d a

48、 b e c 110、求下列圖的生成樹。

49、 111、在一個(gè)有n個(gè)頂點(diǎn)的G=中，u,vV。若存在一條從u到v的一條通路，則必有一條從u到v的長度不超過n-1的通路。 112、設(shè)簡單平面圖G中頂點(diǎn)數(shù)n=7，邊數(shù)m=15。證明：G是連通的。 113、已知一棵無向樹中有2個(gè)2度頂點(diǎn)、1個(gè)3度頂點(diǎn)、3個(gè)4度頂點(diǎn)，其余頂點(diǎn)度數(shù)都為1。問它有多少個(gè)1度頂點(diǎn)？ 114、有向圖G是強(qiáng)連通的G中有一回路，它至少通過每個(gè)頂點(diǎn)一次。 115、一個(gè)有向圖是單向連通圖 它有一條經(jīng)過所有結(jié)點(diǎn)的路。 20