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

1、第一章習(xí)題1. 1判斷下列語句是否為命題，若是命題請(qǐng)指出是簡(jiǎn)單命題還是復(fù)合命題。（1）是無理數(shù)。（2）5能被2整除。（3）現(xiàn)在開會(huì)嗎？（4）x+50（5）這朵花真是好看?。?）2是素?cái)?shù)當(dāng)且僅當(dāng)三角形有三條邊。（7）雪是黑色的當(dāng)且僅當(dāng)太陽是從東方升起。（8）2000年10月1日天氣晴好。（9）太陽系以外的星球上有生物。（10）小李在宿舍里。（11）全體起立。（12）4是2的倍數(shù)或是3的倍數(shù)。（13）4是偶數(shù)且是奇數(shù)。（14）李明和王華是同學(xué)。（15）藍(lán)色和黃色可以調(diào)配成綠色。1.2 將上題中的命題符號(hào)化，并討論他們的真值。1. 3判斷下列各命題的真值。（1） 若2+2=4，則3+3=6；（2）

2、若2+2=4，則3+36；（3） 若2+2=4，則3+3=6；（4） 若2+2=4，則3+3=6；（5） 2+2=4，當(dāng)且僅當(dāng)3+3=6；（6） 2+2=4，當(dāng)且僅當(dāng)3+36；（7） 2+24，當(dāng)且僅當(dāng)3+3=6；（8） 2+24，當(dāng)且僅當(dāng)3+36；1. 4將下列命題符號(hào)化，并討論其真值。（1） 如果今天是1號(hào)，則明天是2號(hào)；（2） 如果今天是1號(hào)，則明天是3號(hào)；1. 5將下列命題符號(hào)化。（1） 2是偶數(shù)不是素?cái)?shù)；（2） 小王不但聰明而且用功；（3） 雖然天氣冷。老王還是來了；（4） 他一邊吃飯，一邊看電視；（5） 如果天下大雨，他就乘公交汽車來；（6） 只有天下大雨，他才乘公交汽車來；（7）

3、 除非天下大雨，否則他不乘公交汽車來；（8） 不經(jīng)一事，不長(zhǎng)一智；1. 5設(shè)p,q的真值為0 ，r,s的真值為1，求下列命題公式的真值。（1） p(qr);（2） (pr)(ps); （3）（p(qr)(pq)(rs);(4)(p(qrp)(rs);1.6設(shè)p：2+3=5。 q：大熊貓產(chǎn)在中國(guó)。 r：復(fù)旦大學(xué)在廣州。求下列復(fù)合命題的真值：（1）(pq)r（2）(r(pq)p（3）r(pqr)（4）(pqr)(pq)r)1.7用真值表判斷下列公式的類型：方法不限。（1）p(pqr)（2）(pq)q（3）(qr)r（4）(pq)(qp)（5）(pr)(pq)（6）(pq)(qr)(pr)（7）(p

4、q)(rs)1. 8用等值演算法證明下列等值式。(1) (pq)(pq)p;(2) (pq)(pr)(p(qr);(3) (pq)(qp)(pq)1. 9設(shè) A,B,C 為任意的命題公式。(1) 已知ACBC,問AB嗎？(2) 已知ACBC,問AB嗎？(3) 已知AB, 問AB嗎？1.10求下列命題公式的主析取范式，主合取范式，成真賦值，成假賦值。1.11通過求主析取范式判斷下列各組命題公式是不是等值。1.12有一探測(cè)隊(duì)有3名隊(duì)員，有一天取得一塊礦樣，3人的判斷如下：甲說：這不是鐵，也不是銅；已說：這不是鐵，是錫；丙說：這不是錫，是鐵；經(jīng)實(shí)驗(yàn)鑒定后發(fā)現(xiàn)，其中一人兩個(gè)判斷是正確的，一個(gè)人判斷對(duì)一

5、半，一個(gè)人的判斷全錯(cuò)了，根據(jù)以上的情況判斷礦樣的種類。1.13判斷下列的推理是不是正確，先將命題符號(hào)化，在寫出前提和結(jié)論，然后在進(jìn)行判斷。（1）如果今天是1號(hào)，則明天是5號(hào)，今天是1號(hào)，所以明天是5號(hào)。（1）如果今天是1號(hào)，則明天是5號(hào)，明天是5號(hào)，所以今天是1號(hào)。（1）如果今天是1號(hào)，則明天是5號(hào)，明天不是5號(hào)，所以今天不是1號(hào)。（1）如果今天是1號(hào)，則明天是5號(hào)，今天不是1號(hào)，所以明天不是5號(hào)。1.14構(gòu)造下面的推理的證明。1.15如果他是理科學(xué)生，他必學(xué)好數(shù)學(xué)，如果他不是文科學(xué)生，他必是理科學(xué)生，他沒有學(xué)好數(shù)學(xué)，所以他不是文科學(xué)生。判斷上面的推理是不是正確，并且證明你的結(jié)論。1.16給定

6、命題公式如下；上述公式的成真賦值A(chǔ)，成假賦值為B，公式的類型為C。供選擇的答案: 無 全體賦值 010，100，101，111 010，100，101，110，111B: 無 全體賦值 000，001，011， 000，010，110C: 重言式 矛盾式 可滿足式1.17給定命題公式如下；上述公式的主析取范式中含的極小項(xiàng)的個(gè)數(shù)為A，主合取范式含的極大項(xiàng)的個(gè)數(shù)為B，成真值的賦值為C供選擇的答案A 2 3 5 0 8B 0 8 5 3 C 000,001,110; 001,011,101,110,111; 全體賦值 無1.18給定下列三組前提。上述前提中，（1）的邏輯結(jié)論（有效結(jié)論）為A，（2）的

7、邏輯結(jié)論為B，（3）的邏輯結(jié)論C。供選擇的答案A,B,C: r q s 1.19設(shè)計(jì)一個(gè)符合下列要求的室類照明控制的線路，在房間的門外、門類及其床頭分別裝一個(gè)可以控制同一個(gè)電燈F的3個(gè)開關(guān)A,B,C, 當(dāng)且僅當(dāng)一個(gè)開關(guān)的搬鍵向上或3 個(gè)開關(guān)的搬鍵都向上時(shí)候電燈亮，則F的邏輯關(guān)系式可以化簡(jiǎn)為A供選擇的答案A: 1.20某電路中有一個(gè)燈泡和三個(gè)開關(guān)A,B,C。已知在且僅在下述四種情況下燈亮：（1）C的扳鍵向上，A,B的扳鍵向下。（2）A的扳鍵向上，B,C的扳鍵向下。（3）B,C的扳鍵向上，A的扳鍵向下。（4）A,B的扳鍵向上，C的扳鍵向下。設(shè)F為1表示燈亮，p,q,r分別表示A,B,C的扳鍵向上。

8、（a）求F的主析取范式。（b）在聯(lián)結(jié)詞完備集,上構(gòu)造F.（c）在聯(lián)結(jié)詞完備集,上構(gòu)造F.1.21一個(gè)排隊(duì)線路，輸入為A,B,C，其輸出分別為FA,FB,FC。本線路中，在同一時(shí)間內(nèi)只能有一個(gè)信號(hào)通過，若同時(shí)有兩個(gè)和兩個(gè)以上信號(hào)申請(qǐng)輸出時(shí)，則按A,B,C的順序輸出。寫出FA,FB,FC在聯(lián)結(jié)詞完備集,中的表達(dá)式。第二章習(xí)題2.1在一階邏輯中將下列命題符號(hào)化. （1）鳥都會(huì)飛翔. （2）并不是所有人都愛吃糖. （3）有人愛看小說. （4）沒有不愛看電影的人. 2.2 在一階邏輯中將下列命題符號(hào)化，并指出個(gè)命題的真值.個(gè)體域分別為 （a）自然數(shù)集合N（N中含O）. （b）整數(shù)集合Z. （c）實(shí)數(shù)集合

9、R. （1）對(duì)于任意的x，均由 (2 )存在x，使得x+2=0. (3 ) 存在x，使得5x=1. 2.3 在一階邏輯中將下列命題符號(hào)化. （1）每個(gè)大學(xué)生不是文科生就是理科生.（2）有些人喜歡所有的花.（3）沒有不犯錯(cuò)誤的人.（4）在北京工作的人未必就是北京人.（5）任何金屬都可以溶解在某種液體中.（6）凡對(duì)頂角都相等.2.4在一階邏輯中將下面命題符號(hào)化，并分別討論個(gè)體域限制為(a),(b)時(shí)命題的真值：（1）對(duì)于任意的x，均有x2-2=(x+)(x-)。（2）存在x，使得x+5=9。其中(a)個(gè)體域?yàn)樽匀粩?shù)集合，(b)個(gè)體域?yàn)閷?shí)數(shù)集合。2.5將下列各式翻譯成自然語言，然后再不同領(lǐng)域中卻定它

10、們的真值.個(gè)體域分別為（a）實(shí)數(shù)集合(b)整數(shù)集合(c)正整數(shù)集合(d)（非0 實(shí)數(shù)集合）2.6設(shè)個(gè)體域D=a,b,c，消去下列各式的量詞：(1) xy(F(x)G(y)(2) xy(F(x)G(y)(3) xF(x)yG(y)(4) x(F(x,y)yG(y)2.7設(shè)個(gè)體域D=1,2，請(qǐng)給出兩種不同的解釋I1和I2，使得下面公式在I1下都是真命題，而在I2下都是假命題。(1) x(F(x)G(x)(2) x(F(x)G(x)2.8給定解釋I如下：(a) 個(gè)體域D=3,4。(b) (x)為(3)=4，(4)=3。(c) (x,y)為(3,3)=(4,4)=0，(3,4)=(4,3)=1。 試求

11、下列公式在I下的真值：(1) xyF(x,y)(2) xyF(x,y)(3) xy(F(x,y)F(f(x),f(y)2.9在自然推理系統(tǒng)F中構(gòu)造下面推理的證明：(1) 前提：x(F(x)(G(a)R(x)，xF(x)結(jié)論：x(F(x)R(x)(2) 前提：x(F(x)G(x)，xG(x)結(jié)論：xF(x)(3) 前提：x(F(x)G(x)，x(G(x)R(x)，xR(x)結(jié)論：xF(x)2.10在自然推理系統(tǒng)F中，證明下面推理：(1) 每個(gè)有理數(shù)都是實(shí)數(shù)，有的有理數(shù)是整數(shù)，因此有的實(shí)數(shù)是整數(shù)。(2) 有理數(shù)、無理數(shù)都是實(shí)數(shù)，虛數(shù)不是實(shí)數(shù)，因此虛數(shù)既不是有理數(shù)、也不是無理數(shù)。(3) 不存在能表示

12、成分?jǐn)?shù)的無理數(shù)，有理數(shù)都能表示成分?jǐn)?shù)，因此有理數(shù)都不是無理數(shù)。2.11(1) 試給出解釋，使得在下具有不同的真值（2）試給出解釋，使得在下具有不同的真值2.12給出解釋，使下面的兩個(gè)公式在解釋下面為假，從而說明這兩個(gè)公式都不是邏輯有效式（用真式）2.13設(shè)個(gè)體域，在D=a,b,c 下D驗(yàn)證量詞否定等值式2.15設(shè)個(gè)體域，在D=a,b,c,消去下列公式中的量詞。2.16求下列各式的前束范式，要求使用自由變換換名規(guī)則。2.17 構(gòu)造下面推理的證明（1）前提； 結(jié)論：（3） 前提：）結(jié)論：2.18取個(gè)體域?yàn)檎麛?shù)集，給定下列各公式在上面的公式中，真命題為A, 假命題為B供選擇的答案A: (1),(3)

13、,(4),(6) (3),(4),(5) (1),(3),(4),(5)(3),(4),(6),(7)B: (2),(3),(6) (2),(6),(8)(1),(2),(6),(7)(2),(6),(8),(7)2.19在一階邏輯中給出下面4個(gè)推理2.20在一階邏輯中構(gòu)造下面的推理證明每個(gè)喜歡步行的人都不喜歡坐汽車， 每個(gè)人或者喜歡坐汽車或自行車，有的人不喜歡自行車，所以有的人不喜歡步行。命題符號(hào)化： F(x): x 喜歡步行,G(x):x 喜歡坐汽車,H(x):x 喜歡自行車.在上述推理中，（2）后用的推理規(guī)則為A，（4）后面用的推理規(guī)則為B，（5）用的推理規(guī)則是（2）（4）所得到的推理規(guī)

14、則C,（8）用的推理規(guī)則是（5）和（7）得到的推理規(guī)則D供選擇的答案A,B,C,D UI, EI, UG, EG,拒取式假言推理析取三段論第三章習(xí)題集合與二元關(guān)系3.1.選擇適當(dāng)?shù)闹^詞表示下列集合：(1)小于5的非負(fù)整數(shù)(2)奇整數(shù)集合(3)10的整倍數(shù)的集合2.用列元素法表示下列集合：(1)S1x|x是十進(jìn)制的數(shù)字(2)S2x|x2x5(3)S3x|xxZ3x3(5)S5|x，yZ0x2-1y03.2.設(shè)F表示一年級(jí)大學(xué)生的集合，S表示二年級(jí)大學(xué)生的集合，M表示數(shù)學(xué)專業(yè)學(xué)生的集合，R表示計(jì)算機(jī)專業(yè)學(xué)生的集合，T表示聽離散數(shù)學(xué)課學(xué)生的集合，G表示星期一晚上參加音樂會(huì)的學(xué)生的集合，H表示星期一晚

15、上很遲才睡覺的學(xué)生的集合。問下列各句子所對(duì)應(yīng)的集合表達(dá)式分別是什么？請(qǐng)從備選的答案中挑出來。 (1)所有計(jì)算機(jī)專業(yè)二年級(jí)的學(xué)生在學(xué)離散數(shù)學(xué)課。(2)這些且只有這些學(xué)離散數(shù)學(xué)課的學(xué)生或者星期一晚上去聽音樂會(huì)的學(xué)生在星期一晚上很遲才睡覺。(3)聽離散數(shù)學(xué)課的學(xué)生都沒參加星期一晚上的音樂會(huì)。(4)這個(gè)音樂會(huì)只有大學(xué)一、二年級(jí)的學(xué)生參加。(5)除去數(shù)學(xué)專業(yè)和計(jì)算機(jī)專業(yè)以外的二年級(jí)學(xué)生都去參加了音樂會(huì)。備選答案：TGH GHT SRTHGT TG FSGGFS S-(RM)G GS-(RM)3.3.確定下列命題是否為真：(1)(2)(3)(4)(5)a，ba，b，c，a，b，c(6)a，ba，b，c，a

16、，b (7)a，ba，b，a，b(8)a，ba，b，a，b3.4已知A=,求AP(A)。3.5對(duì)于任意集合A,B,C，若ABAC,是否一定有BC成立？為什么？ 3.6設(shè)A,B,C,D是任意集合，(1) 求證(AB)(CD)=(AC)(BD)。(2) 下列等式中哪個(gè)成立？那些不成立?對(duì)于成立的給出證明，對(duì)于不成立的舉一反例。(AB)(CD)=(AC)(BD)(A-B)(C-D)=(AC)-(BD) 3.7設(shè)A,B為任意集合，證明若AA=BB，則 A=B。3.8列出從集合A=1，2到B=1的所有的二元關(guān)系。3.9列出集合A=2，3，4上的恒等關(guān)系IA，全域關(guān)系EA，小于或等于關(guān)系LA，整除關(guān)系DA

17、。3.10.列出集合A=，上的包含關(guān)系。3.11.設(shè)A=1，2，4，6，列出下列關(guān)系R: (1) R=|x，yAx+y2(2) R=|x，yA|x-y|=1(3) R=|x，yAx/yA(4) R=|x，yAy為素?cái)?shù)3.12.Ri是X上的二元關(guān)系，對(duì)于xX定義集合Ri(x)=y|xRiy。顯然Ri(x)X。如果X=-4，-3，-2，-1，0，1，2，3，4，且令R1=|x，yXxyR2=|x，yXy-1xy+2R3=|x，yXx2y求R1(0)，R1(1)，R2(0)，R2(-1)，R3(3)。3.13.設(shè)A=0，1，2，3，R是A上的關(guān)系，且R=，給出R的關(guān)系矩陣和關(guān)系圖。3.14設(shè)=,=,

18、求AB,AB,domA,dom(AB),ranA,ranB,ran(AB),fld(A-B) 3.15設(shè)R=,求RR,R-1 ,R0,1,R1,2。3.16 設(shè)A=,求A-1,A2,A3,A,A,A,A,A。3.17 設(shè)A=a,b,c,d，R1,R2為A上的關(guān)系，其中R1=,R2=,求R1R2, R2R1,R12,R23。3.18設(shè)A=a,b,c，試給出A上兩個(gè)不同的關(guān)系R1和R2,使得 R12=R1, R23=R2 3.19證明定理7.4的(1)，(2)，(4)。3.20證明定理7.5的(2)，(3)。3.21設(shè)R1和R2為A上的關(guān)系，證明： （1）(R1R2)-1=R1-1R2-1 （2）

19、(R1R2)-1=R1-1R2-1第四章習(xí)題代數(shù)系統(tǒng)4.1、列出以下運(yùn)算的運(yùn)算表：(1) A=1,2,，xA，x是x的倒數(shù)，即x=.(2) A=1,2,3,4,x,yA有xy=max(x,y),max(x,y)是x和y之中較大的數(shù)。4.2、判斷下列集合對(duì)所給的二元運(yùn)算是否封閉：(1) 整數(shù)集合Z和普通的減法運(yùn)算(2) 非零整數(shù)集合Z*和普通的除法運(yùn)算(3) 全體nn實(shí)矩陣集合Mn(R)和矩陣加法及乘法運(yùn)算，其中n2(4) 全體nn實(shí)可逆矩陣集合關(guān)于矩陣加法和乘法運(yùn)算，其中n2(5) 正實(shí)數(shù)集合R+和運(yùn)算，其中運(yùn)算定義為：,R+,ab=ab-a-b(6) nZ+,nZ=nz|zZ.nZ關(guān)于普通的

20、加法和乘法運(yùn)算。(7) A=a1,a2,.,an,n2.運(yùn)算定義如下：ai,ajA,aiaj=ai.(8) S=2x-1|xZ+關(guān)于普通的加法和乘法運(yùn)算。(9) S=0,1,S關(guān)于普通的加法和乘法運(yùn)算。 (10)S=x|x=2n,nZ+，S關(guān)于普通的加法和乘法運(yùn)算4.3、對(duì)于上題中封閉的二元運(yùn)算判斷是否適合交換律、結(jié)合律和分配律。4.4、對(duì)習(xí)題2中封閉的二元運(yùn)算找出它的單位元，零元和所有可逆元素的逆元。4.5、S=QQ,Q為有理數(shù)集，*為S上的二元運(yùn)算，,S有*=(1) *運(yùn)算在S上是否可交換，可結(jié)合？是否為冪等的？(2) *運(yùn)算是否有單位元，零元？如果有，請(qǐng)指出，并求S中所有可逆元素的逆元。

21、4.6、R為實(shí)數(shù)集，定義以下六個(gè)函數(shù)f1,.,f6.x,yR有f1()=x+y,f2()=x-y,f3()=xy, f4()=max(x,y),f5()=min(x,y), f6()=|x-y|(1) 指出哪些函數(shù)是R上的二元運(yùn)算。(2) 對(duì)所有R上的二元運(yùn)算說明是否為可交換、可結(jié)合、冪等的。(3) 求所有R上二元運(yùn)算的單位元、零元以及每一個(gè)可逆元素的逆元。4.7、令S=a,b,上有四個(gè)二元運(yùn)算：*,和,分別由表10.8確定。表10.8(1) 這四個(gè)運(yùn)算中哪些運(yùn)算滿足交換律、結(jié)合律、冪等律(2) 求每個(gè)運(yùn)算的單位元、零元及所有可逆元素的逆元。4.8、設(shè)S=1,2,.,10,問下面定義的運(yùn)算能否

22、與S構(gòu)成代數(shù)系統(tǒng)?如果能構(gòu)成代數(shù)系統(tǒng)則說明*運(yùn)算是否滿足交換律、結(jié)合律，并求*運(yùn)算的單位元和零元。(1) x*y=gcd(x,y),gcd(x,y)是x與y的最大公約數(shù)。(2) x*y=lcm(x,y),lcm(x,y)是x與y的最小公倍數(shù)。(3) x*y=大于等于x和y的最小整數(shù)。(4) x*y=質(zhì)數(shù)p的個(gè)數(shù)，其中xpy. 4.9、下面各集合都是N的子集，它們能否構(gòu)成代數(shù)系統(tǒng)V=的子代數(shù)：(1) x|xNx可以被16整除(2) x|xNx與8互質(zhì)(3) x|xNx是40的因子(4) x|xNx是30的倍數(shù) 4.10、設(shè)V=，其中+和分別代表普通加法和乘法，對(duì)下面給定的每個(gè)集合確定它是否構(gòu)成V

23、的子代數(shù)，為什么？(1) S1=2n|nZ(2) S2=2n1|nZ(3) S3=1，0，1 4.11、設(shè)V1=,其中xy表示取x和y之中較大的數(shù)。V2=,其中x*y表示取x和y之中較小的數(shù)。求出V1和V2的所有子代數(shù)。指出哪些是平凡子代數(shù)，哪些是真子代數(shù)。 第五章幾個(gè)典型的代數(shù)系統(tǒng)5.1.設(shè)A=0,1,試給出半群的運(yùn)算表,其中為函數(shù)的復(fù)合運(yùn)算。5.2.設(shè)G=a+bi|a,bZ,i為虛數(shù)單位,即i2=-1.驗(yàn)證G關(guān)于復(fù)數(shù)加法構(gòu)成群。5.3.設(shè)Z為整數(shù)集合,在Z上定義二元運(yùn)算如下：x,yZ,xy=x+y-2 問Z關(guān)于運(yùn)算能否構(gòu)成群？為什么？ 5.4.設(shè)A=x|xRx0,1.在A上定義六個(gè)函數(shù)如下

24、：f1(x)=x, f2(x)=x-1, f3(x)=1-x,f4(x)=(1-x)-1, f5(x)=(x-1)x-1, f6(x)=x(x-1)-1 令F為這六個(gè)函數(shù)構(gòu)成的集合,運(yùn)算為函數(shù)的復(fù)合運(yùn)算。(1) 給出運(yùn)算的運(yùn)算表。(2) 驗(yàn)證是一個(gè)群。5.5.設(shè)G為群,且存在aG,使得 G=ak|kZ, 證明G是交換群。5.6.證明群中運(yùn)算滿足消去律. 5.7.設(shè)G為群,若xG有x2=e,證明G為交換群。5.8.設(shè)G為群,證明e為G中唯一的冪等元。5.9.證明4階群必含2階元。5.10設(shè)A=a+bi|a,bZ,i2=-1,證明A關(guān)于復(fù)數(shù)的加法和乘法構(gòu)成環(huán),稱為高斯整數(shù)環(huán)。5.12.(1) 設(shè)R

25、1,R2是環(huán),證明R1與R2的直積R1R2也是環(huán)。(2) 若R1和R2為交換環(huán)和含幺環(huán),證明R1R2也是交換環(huán)和含幺環(huán)。5.13. 判斷下列集合和給定運(yùn)算是否構(gòu)成環(huán)、整環(huán)和域,如果不能構(gòu)成,說明理由。(1) A=a+bi|a,bZ,其中i2=-1,運(yùn)算為復(fù)數(shù)的加法和乘法。(2) A=-1,0,1,運(yùn)算為普通加法和乘法。(3) A=M2(Z),2階整數(shù)矩陣的集合，運(yùn)算為矩陣加法和乘法。(4) A是非零有理數(shù)集合Q*,運(yùn)算為普通加法和乘法。5.14.設(shè)G是非阿貝爾群,證明G中存在元素a和b,ab,且ab=ba. 5.15.設(shè)H是群G的子群,xG,令xHx-1=xhx-1|hH, 證明xHx-1是G

26、的子群,稱為H的共軛子群。5.16.設(shè) (1) G上的二元運(yùn)算為矩陣乘法,給出G的運(yùn)算表(2) 試找出G的所有子群(3) 證明G的所有子群都是正規(guī)子群。5.17.設(shè)G是有限群，K是G的子群，H是K的子群,證明G:H=G:KK:H. 5.18.令G=Z,+是整數(shù)加群。求商群Z/4Z,Z/12Z和4Z/12Z. 5.19.對(duì)以下各小題給定的群G1和G2以及f:G1G2,說明f是否為群G1到G2的同態(tài)。如果是,說明G是否為單同態(tài),滿同態(tài)和同構(gòu),并求同態(tài)像f(G1)和同態(tài)核kerf.(1) G1=,G2=,其中R*為非零實(shí)數(shù)的集合,+和分別表示數(shù)的加法和乘法。f:ZR*,f(x)=(2) G1=,G2

27、=,其中+和分別表示數(shù)的加法和乘法A=x|xC|x|=1,其中C為復(fù)數(shù)集合。f:ZA,f(x)=cosx+i sinx(3) G1=,G2=,+和以及A的定義同(2).f:RA,f(x)=cosx+i sinx 5.20.設(shè)f是群G1到G2的同構(gòu),證明f-1是G2到G1的同構(gòu)。5.21.圖中給出六個(gè)偏序集的哈斯圖。判斷其中哪些是格。如果不是格,說明理由。5.22.下列各集合對(duì)于整除關(guān)系都構(gòu)成偏序集,判斷哪些偏序集是格。(1) L=1,2,3,4,5(2) L=1,2,3,6,12(3) L=1,2,3,4,6,9,12,18,36(4) L=1,2,22,.,2n,nZ+ 5.23.(1)畫出

28、Klein四元群的子群格。(2)畫出模12的整數(shù)群Z12的子群格。(3)畫出3元對(duì)稱群S3的子群格。 5.24.設(shè)L是格,求以下公式的對(duì)偶式:(1) a(ab)a(2) a(bc)(ab)(ac)(3) b(ca)(bc)a 5.25.設(shè)L是格,a,b,cL,且abc,證明 ab=bc5.26.針對(duì)圖13.10中的格L1,L2和L3,求出他們的所有子格。 圖13.105.27.針對(duì)圖13.9中的每個(gè)格,如果格中的元素存在補(bǔ)元,則求出這些補(bǔ)元。5.28.說明圖13.9中的每個(gè)格是否為分配格、有補(bǔ)格和布爾格,并說明理由。5.29.對(duì)以下各小題給定的集合和運(yùn)算判斷它們是哪一類代數(shù)系統(tǒng)(半群,獨(dú)異點(diǎn),

29、群,環(huán),域,格,布爾代數(shù)),并說明理由。(1) S1=0，1,-1，運(yùn)算為普通加法和乘法。(2) S2=a1,a2,.,an,ai,ajS2,ai*aj=ai.這里的n是給定的正整數(shù),且n2.(3) S3=0,1,*為普通乘法。(4) S4=1,2,5,7,10,14,35,70,和*分別表示求最小公倍數(shù)和最大公約數(shù)運(yùn)算。(5) S5=0,1,2,*為模3加法,為模3乘法。5.30.設(shè)B是布爾代數(shù),B中的表達(dá)式f是 (ab)(abc)(bc) (1)化簡(jiǎn)f.(2)求f的對(duì)偶式f* 。5.31.設(shè)是布爾代數(shù)，在B中化簡(jiǎn)以下表達(dá)式：上定義二元運(yùn)算*，a,bB, （1）(ab)(ab)(ab) （2

30、）(ab)(a（bc)c 5.32.對(duì)于n=1,.,5,給出所有不同構(gòu)的n元格,并說明哪些是分配格、有補(bǔ)格和布爾格。5.33.設(shè)是布爾代數(shù),在B上定義二元運(yùn)算,x,yB有xy=(xy)(xy)問能否構(gòu)成代數(shù)系統(tǒng)？如果能,指出是哪一種代數(shù)系統(tǒng)。為什么？ 5.34.設(shè)G1為循環(huán)群,f是群G1到G2的同態(tài),證明f(G1)也是循環(huán)群。5.35.設(shè)G=是15階循環(huán)群。(1) 求出G的所有的生成元。(2) 求出G的所有子群。5.36.設(shè),是5元置換,且 (1) 計(jì)算,-1,-1,-1(2) 將,-1,-1表成不交的輪換之積。(3) 將(2)中的置換表示成對(duì)換之積,并說明哪些為奇置換,哪些為偶置換。5.37

31、設(shè)A=1,2,5,10,11,22,55,110是110的正因子集，A, 構(gòu)成的偏序集，其中 為整除關(guān)系。（1）畫出偏序集A, 的哈斯圖。（2）說明該偏序集是不是構(gòu)成布爾代數(shù)，為什么？第六章習(xí)題 圖論基礎(chǔ)6.1下列各組數(shù)中，那些能構(gòu)成無向圖的度數(shù)列？那些能構(gòu)成無向簡(jiǎn)單圖的度數(shù)列？（1）1，1，1，2.3 (2)2,2,2,2,2 (3)1,2,3,4,5 (4)1,3,3,36.2設(shè)有向簡(jiǎn)單圖D的度數(shù)為2，2，3，3，入度列0，0，2，3，試求D的除度列。6.3設(shè)是4階有向簡(jiǎn)單圖，度數(shù)列為3，3，3，3.它的入度列9或出度列）能為1，1，1，1嗎？6.4設(shè)( )為一正整數(shù)序列， 互不相同，問此

32、序列能構(gòu)成n階無向圖的度數(shù)列嗎？為什么？6.5下面無向圖中有幾個(gè)頂點(diǎn)？（1）16條邊，每個(gè)頂點(diǎn)都是2度頂點(diǎn).（2）21條邊，3個(gè)4度頂點(diǎn)，其余的都是3度頂點(diǎn).（3）24條邊，各頂點(diǎn)的度數(shù)是相同的.6.6 35條邊 ，每個(gè)頂點(diǎn)的度數(shù)至少為3的圖最多有幾個(gè)頂點(diǎn)?6.7設(shè)n階無向簡(jiǎn)單圖中，（G）=n-1，問 （G）應(yīng)為多少？6.8一個(gè)n（n）階無向簡(jiǎn)單圖中，為奇數(shù)，已知中有各奇度頂點(diǎn)，問的補(bǔ)圖中有幾個(gè)奇度頂點(diǎn)？6.9設(shè)是階有向簡(jiǎn)單圖，是的子圖，已知的邊數(shù)（），問的邊數(shù)為多少？6.10畫出的所有非同構(gòu)的子圖，其中有幾個(gè)是子圖？生成子圖中有幾個(gè)是連通圖？6.11設(shè)為階簡(jiǎn)單圖（無向圖或有向圖），為的補(bǔ)圖，

33、若，則稱為自補(bǔ)圖，的生成子圖中有幾個(gè)非同構(gòu)的自補(bǔ)圖？6.12設(shè)無向圖G有10條邊，3度與4度頂點(diǎn)各2個(gè)，其余頂點(diǎn)的度數(shù)均小于3，問G中至少有幾個(gè)頂點(diǎn)？在最少頂點(diǎn)的情況下，寫出G的度數(shù)列、(G)、(G). 6.13設(shè)n階圖G中有m條邊，證明：(G)2m/n(G). 6.14設(shè)無向圖中有6條邊，3度與5度頂點(diǎn)各一個(gè)，其余的都是2度頂點(diǎn)，問該圖有幾個(gè)頂點(diǎn)？ 6.15證明空間中不可能存在有奇數(shù)個(gè)面且每個(gè)面都有奇數(shù)條棱的多面體。 6.16階2-正則圖有幾種非同構(gòu)的情況？ 6.17設(shè)n階無向圖為3-正則圖，且邊數(shù)m與n滿足2n-3=m，問這樣的無向圖有幾種非同構(gòu)的情況？6.18畫出階有完全圖所有非同構(gòu)的子

34、圖，問其中有幾個(gè)是生成子圖？生成子圖中有幾個(gè)是自補(bǔ)圖？6.19設(shè)均為階無向簡(jiǎn)單圖，他們均由兩條邊，他們能彼此均非同構(gòu)嗎？為什莫？6.20已知階無向圖中有條邊，各頂點(diǎn)的度數(shù)均為，又已知，問在同構(gòu)的意義下，是唯一的嗎？又若為簡(jiǎn)單時(shí)，是否唯一？6.22在的邊上涂上紅色或藍(lán)色，證明對(duì)于任意一種隨意的涂法，總存在紅色或藍(lán)色？6.23試尋找個(gè)階有向簡(jiǎn)單圖，使得強(qiáng)連通圖；為單向連通圖，但不是強(qiáng)連通圖；而是弱連通圖，但不是單向連通圖，當(dāng)然，更不是強(qiáng)連通圖6.24設(shè)-和-分別為無向連通圖G的點(diǎn)割集.G-的連通圖分支個(gè)數(shù)k一定為幾？G-l連通分支數(shù)也是定數(shù)嗎？6.25有向圖D如圖7.19所示.求D中長(zhǎng)度為4的通路

35、總數(shù)，并指出其中有多少條是回路？又有幾條是-到-的通路？6.26現(xiàn)有3個(gè)4階4條邊的無向簡(jiǎn)單圖G1,G2,G3,證明它們中至少有兩個(gè)是同構(gòu)的。 6.27設(shè)G是n階自補(bǔ)圖，證明n=4k或n=4k+1，其中k為正整數(shù)。 6.28設(shè)G是n階無向簡(jiǎn)單圖，n3且為奇數(shù)，證明G與中奇度頂點(diǎn)的個(gè)數(shù)相等。 6.29已知在完全二部圖Kr,s中，rs.(1)Kr,s中含有多少種非同構(gòu)的圈？(2)Kr,s中至多有多少個(gè)頂點(diǎn)彼此不相鄰？(3)Kr,s中至多有多少條邊彼此不相鄰？(4)Kr,s的點(diǎn)連通度為幾？邊連通度為幾？ 第七章習(xí)題歐拉圖7.1畫出完全2部圖-.7.2設(shè)G為n（n-1），至少用幾種顏色給G的頂點(diǎn)染色，使相鄰的頂點(diǎn)顏色不同？7.3完全二部圖-中，邊數(shù)m為多少？7.4完全二部圖-的匹配數(shù)為多少？7.5今有工人甲.乙.丙去完成三項(xiàng)任務(wù)a，b，c.已知工人甲能勝任a，b，c三項(xiàng)任務(wù)