第一篇：離散數(shù)學(xué)課后習(xí)題答案

第一章部分課后習(xí)題參考答案 設(shè)p、q的真值為0；r、s的真值為1，求下列各命題公式的真值。

（1）p∨(q∧r)? 0∨(0∧1)?0（2）（p?r）∧(﹁q∨s)?（0?1）∧(1∨1)?0∧1?0.（3）（?p∧?q∧r）?(p∧q∧﹁r)?（1∧1∧1）?(0∧0∧0)?0(4)（?r∧s）→(p∧?q)?（0∧1）→(1∧0)?0→0?1 17．判斷下面一段論述是否為真：“?是無理數(shù)。并且，如果3是無理數(shù)，則2也是無理數(shù)。另外，只有6能被2整除，6才能被4整除。”

答：p: ?是無理數(shù)

q: 3是無理數(shù)

0

r: 2是無理數(shù)

s: 6能被2整除t: 6能被4整除

0

命題符號化為： p∧(q→r)∧(t→s)的真值為1，所以這一段的論述為真。19．用真值表判斷下列公式的類型：（4）(p→q)→(?q→?p)（5）(p∧r)?(?p∧?q)（6）((p→q)∧(q→r))→(p→r)答：

（4）

p

q

p→q

?q

?p

?q→?p

(p→q)→(?q→?p)

0

0

0

0

0

0

0

0

0

0

所以公式類型為永真式

（5）公式類型為可滿足式（方法如上例）（6）公式類型為永真式（方法如上例）

第二章部分課后習(xí)題參考答案

3.用等值演算法判斷下列公式的類型，對不是重言式的可滿足式，再用真值表法求出成真賦值.1(1)?(p∧q→q)(2)(p→(p∨q))∨(p→r)(3)(p∨q)→(p∧r)答：(2)（p→(p∨q)）∨(p→r)?(?p∨(p∨q))∨(?p∨r)??p∨p∨q∨r?1

所以公式類型為永真式

(3)P

q

r

p∨q

p∧r

（p∨q）→(p∧r)0

0

0

0

0

0

0

0

0

0

0

0

0 0

0

0 1

0

0

0

0 1

0

1

0

0

0 1

所以公式類型為可滿足式

4.用等值演算法證明下面等值式：(2)(p→q)∧(p→r)?(p→(q∧r))(4)(p∧?q)∨(?p∧q)?(p∨q)∧?(p∧q)證明（2）(p→q)∧(p→r)?(?p∨q)∧(?p∨r)??p∨(q∧r))?p→(q∧r)（4）(p∧?q)∨(?p∧q)?(p∨(?p∧q))∧(?q∨(?p∧q)?(p∨?p)∧(p∨q)∧(?q∨?p)∧(?q∨q)?1∧(p∨q)∧?(p∧q)∧1 ?(p∨q)∧?(p∧q)5.求下列公式的主析取范式與主合取范式，并求成真賦值

(1)(?p→q)→(?q∨p)(2)?(p→q)∧q∧r(3)(p∨(q∧r))→(p∨q∨r)解：

（1）主析取范式

(?p→q)→(?q?p)?????(p?q)?(?q?p)(?p??q)?(?q?p)(?p??q)?(?q?p)?(?q??p)?(p?q)?(p??q)(?p??q)?(p??q)?(p?q)?m0?m2?m3

?∑(0,2,3)主合取范式：

(?p→q)→(?q?p)???(p?q)?(?q?p)(?p??q)?(?q?p)?(?p?(?q?p))?(?q?(?q?p))?1?(p??q)?(p??q)? M1

?∏(1)(2)主合取范式為：

?(p→q)?q?r??(?p?q)?q?r ?(p??q)?q?r?0 所以該式為矛盾式.主合取范式為∏(0,1,2,3,4,5,6,7)矛盾式的主析取范式為 0(3)主合取范式為：

(p?(q?r))→(p?q?r)??(p?(q?r))→(p?q?r)??(?p?(?q??r))?(p?q?r)(?p?(p?q?r))?((?q??r))?(p?q?r))?1?1 ?1 所以該式為永真式.永真式的主合取范式為 1 主析取范式為∑(0,1,2,3,4,5,6,7)第三章部分課后習(xí)題參考答案

14.在自然推理系統(tǒng)P中構(gòu)造下面推理的證明：(2)前提：p?q,?(q?r),r 結(jié)論：?p(4)前提：q?p,q?s,s?t,t?r 結(jié)論：p?q

證明：（2）

①?(q?r)前提引入 ②?q??r ①置換 ③q??r ②蘊(yùn)含等值式 ④r 前提引入 ⑤?q ③④拒取式 ⑥p?q 前提引入 ⑦￢p（3）⑤⑥拒取式

證明（4）：

①t?r 前提引入 ②t ①化簡律 ③q?s 前提引入 ④s?t 前提引入

⑤q?t ③④等價三段論 ⑥（q?t）?(t?q)⑤ 置換 ⑦（q?t）⑥化簡 ⑧q ②⑥ 假言推理 ⑨q?p 前提引入 ⑩p ⑧⑨假言推理(11)p?q ⑧⑩合取

15在自然推理系統(tǒng)P中用附加前提法證明下面各推理：

4(1)前提：p?(q?r),s?p,q 結(jié)論：s?r 證明

①s 附加前提引入 ②s?p 前提引入 ③p ①②假言推理 ④p?(q?r)前提引入 ⑤q?r ③④假言推理 ⑥q 前提引入 ⑦r ⑤⑥假言推理

16在自然推理系統(tǒng)P中用歸謬法證明下面各推理：

(1)前提：p??q,?r?q,r??s 結(jié)論：?p 證明：

①p 結(jié)論的否定引入 ②p?﹁q 前提引入 ③﹁q ①②假言推理 ④￢r?q 前提引入 ⑤￢r ④化簡律 ⑥r(nóng)?￢s 前提引入 ⑦r ⑥化簡律 ⑧r?﹁r ⑤⑦ 合取

由于最后一步r?﹁r 是矛盾式,所以推理正確.

第二篇：離散數(shù)學(xué)課后習(xí)題答案第三章

第六章部分課后習(xí)題參考答案

5.確定下列命題是否為真：

（1）???

真

（2）???

假（3）??{?}

真

（4）??{?}

真（5）｛a,b｝?｛a,b,c,｛a,b,c｝｝

真（6）｛a,b｝?｛a,b,c,｛a,b｝｝

真（7）｛a,b｝?｛a,b,｛｛a,b｝｝｝

真（8）｛a,b｝?｛a,b,｛｛a,b｝｝｝

假

6．設(shè)a,b,c各不相同，判斷下述等式中哪個等式為真:（1）｛｛a,b｝，c,?｝ =｛｛a,b｝,c｝

假（2）｛a ,b,a｝=｛a,b｝

真（3）｛｛a｝，｝=｛｛a,b｝｝

假（4）｛?，｛?｝，a,b｝=｛｛?,｛?｝｝,a,b｝

假 8．求下列集合的冪集：

（1）｛a,b,c｝ P(A)={ ?,{a},,{c},{a,b},{a,c},{b,c},{a,b,c}}（2）｛1，｛2，3｝｝ P(A)={ ?, {1}, {{2,3}}, {1，{2，3}} }（3）｛?｝ P(A)={ ?, ｛?｝ }

（4）｛?，｛?｝｝ P(A)={ ?, {1}, {{2,3}}, {1，{2，3}} } 14．化簡下列集合表達(dá)式：（1）（A?B）?B）-（A?B）（2）（（A?B?C）-（B?C））?A 解:(1)（A?B）?B）-（A?B）=（A?B）?B）?～（A?B）

=（A?B）?～（A?B）)?B=??B=?

（2）（（A?B?C）-（B?C））?A=（（A?B?C）?～（B?C））?A =（A?～（B?C））?（（B?C）?～（B?C））?A =（A?～（B?C））???A=（A?～（B?C））?A=A 18．某班有25個學(xué)生，其中14人會打籃球，12人會打排球，6人會打籃球和排球，5人會打籃球和網(wǎng) 球，還有2人會打這三種球。已知6個會打網(wǎng)球的人都會打籃球或排球。求不會打球的人數(shù)。解: 阿A={會打籃球的人}，B={會打排球的人}，C={會打 |A|=14, |B|=12, |A?B|=6,|A?C|=5,| A?B?C|=2, 如圖所示。

25-(5+4+2+3)-5-1=25-14-5-1=5 不會打球的人共5人

21.設(shè)集合A＝{{1，2}，{2，3}，{1，3},{?}},計(jì)算下列表達(dá)式：（1）?A（2）?A（3）??A（4）??A 解:（1）?A={1，2}?{2，3}?{1，3}?{?}={1，2，3,?}

（2）?A={1，2}?{2，3}?{1，3}?{?}=?

（3）??A=1?2?3??=?

（4）??A=?

27、設(shè)A,B,C是任意集合，證明(1)(A-B)-C=A-B?C(2)(A-B)-C=(A-C)-(B-C)證明

(1)(A-B)-C=(A?～B)?～C= A?(～B?～C)= A?～(B?C)=A-B?C(2)(A-C)-(B-C)=(A?～C)?～(B ?～C)=(A?～C)?(～B?C)=(A?～C?～B)?(A?～C?C)=(A?～C?～B)?? = A?～(B?C)=A-B?C 由（1）得證。

網(wǎng)球的人} |C|=6,C?A?B

第七章部分課后習(xí)題參考答案

7.列出集合A={2,3,4}上的恒等關(guān)系I A,全域關(guān)系EA,小于或等于關(guān)系LA,整除關(guān)系DA.解：IA ={<2，2>,<3,3>,<4,4>} EA={<2,2>,<2,3>,<2,4>,<3,4>,<4,4>,<3,2>,<3,3>,<4,2>,<4,3>} LA={<2,2>,<2,3>,<2,4>,<3,3>,<3,4>,<4,4>} DA={<2,4>} 13.設(shè)A={<1,2>,<2,4>,<3,3>}

B={<1,3>,<2,4>,<4,2>} 求A?B,A?B, domA, domB, dom(A?B), ranA, ranB, ran(A?B), fld(A-B).解：A?B={<1,2>,<2,4>,<3,3>,<1,3>,<4,2>} A?B={<2,4>} domA={1,2,3} domB={1,2,4} dom(A∨B)={1,2,3,4} ranA={2,3,4} ranB={2,3,4} ran(A?B)={4} A-B={<1,2>,<3,3>}，fld(A-B)={1,2,3} 14.設(shè)R={<0,1><0,2>,<0,3>,<1,2>,<1,3>,<2,3>} 求R?R, R-1, R?{0,1,}, R[{1,2}] 解：R?R={<0,2>,<0,3>,<1,3>} R-1,={<1,0>,<2,0>,<3,0>,<2,1>,<3,1>,<3,2>} R?{0,1}={<0,1>,<0,2>,<0,3>,<1,2>,<1,3>} R[{1,2}]=ran(R|{1,2})={2,3}

16．設(shè)A={a,b,c,d}，R1，R2為A上的關(guān)系，其中

R1=?a,a,a,b,b,d?

R2??a,d,b,c,b,d,c,b23求R1?R2,R2?R1,R1,R2。?

解: R1?R2={,,} R2?R1={} R12=R1?R1={,,} R22=R2?R2={,,} R23=R2?R22={,,}

36．設(shè)A={1，2，3，4}，在A?A上定義二元關(guān)系R，?,?A?A，〈u,v> R ?u + y = x + v.(1)證明R 是A?A上的等價關(guān)系.(2)確定由R 引起的對A?A的劃分.（1）證明：∵R ?u+y=x-y ∴R?u-v=x-y ??A?A ∵u-v=u-v ∴R ∴R是自反的

任意的,∈A×A 如果R，那么u-v=x-y ∴x-y=u-v ∴R ∴R是對稱的

任意的,,∈A×A 若R,R 則u-v=x-y,x-y=a-b ∴u-v=a-b ∴R ∴R是傳遞的

∴R是A×A上的等價關(guān)系

(2)∏={{<1,1>,<2,2>,<3,3>,<4,4>}, {<2,1>,<3,2>,<4,3>}, {<3,1>,<4,2>}, {<4,1>}, {<1,2>,<2,3>,<3,4>}, {<1,3>,<2,4>}, {<1,4>} }

41.設(shè)A={1，2，3，4}，R為A?A上的二元關(guān)系, ?〈a，b〉，〈c，d〉? A?A ，〈a，b〉R〈c，d〉?a + b = c + d(1)證明R為等價關(guān)系.(2)求R導(dǎo)出的劃分.(1)證明：?

a+b=a+b ∴R ∴R是自反的

任意的,∈A×A 設(shè)R，則a+b=c+d ∴c+d=a+b ∴R ∴R是對稱的 任意的,,∈A×A 若R,R 則a+b=c+d,c+d=x+y ∴a+b=x+y ∴R ∴R是傳遞的

∴R是 A×A上的等價關(guān)系

(2)∏={{<1,1>}, {<1,2>,<2,1>}，{<1,3>,<2,2>,<3,1>}，{<1,4>,<4,1>,<2,3>,<3,2>}, {<2,4>,<4,2>,<3,3>}, {<3,4>,<4,3>}, {<4,4>}}

43.對于下列集合與整除關(guān)系畫出哈斯圖:(1){1,2,3,4,6,8,12,24}(2){1,2,3,4,5,6,7,8,9,10,11,12} 解: ***19511

42(1)(2)45.下圖是兩個偏序集的哈斯圖.分別寫出集合A和偏序關(guān)系R?的集合表達(dá)式.debafc

gbcfdeag

(a)(b)解:(a)A={a,b,c,d,e,f,g} R?={,,,,,,,,,}?IA

(b)A={a,b,c,d,e,f,g} R?={,,,,,,}?IA 46.分別畫出下列各偏序集的哈斯圖,并找出A的極大元`極小元`最大元和最小元.(1)A={a,b,c,d,e} R?={,,,,,,}?IA.(2)A={a,b,c,d,e}, R?={}?IA.解:

edbcadeabc

(1)

(2)項(xiàng)目(1)(2)極大元: e a,b,d,e 極小元: a a,b,c,e 最大元: e 無 最小元: a 無

第八章部分課后習(xí)題參考答案

1．設(shè)f :N?N,且

?1，若x為奇數(shù)?

f(x)=?x

若x為偶數(shù)?2，?求f(0), f({0}), f(1), f({1}), f({0,2,4,6,…})，f({4,6,8}), f-1({3,5,7}).解：f(0)=0, f({0})={0}, f(1)=1, f({1})={1}, f({0,2,4,6,…})=N，f({4,6,8})={2,3,4}, f-1({3,5,7})={6,10,14}.4.判斷下列函數(shù)中哪些是滿射的?哪些是單射的?哪些是雙射的?(1)f:N?N, f(x)=x2+2

不是滿射，不是單射

(2)f:N?N,f(x)=(x)mod 3,x除以3的余數(shù)

不是滿射，不是單射

?1，若x為奇數(shù)(3)f:N?N,f(x)=?

不是滿射，不是單射

?0，若x為偶數(shù)

?0，若x為奇數(shù)(4)f:N?{0,1},f(x)=?

是滿射，不是單射

?1，若x為偶數(shù)(5)f:N-{0}?R,f(x)=lgx

不是滿射，是單射

(6)f:R?R,f(x)=x2-2x-15

不是滿射，不是單射

5.設(shè)X={a,b,c,d},Y={1,2,3},f={,,,}判斷以下命題的真假:(1)f是從X到Y(jié)的二元關(guān)系,但不是從X到Y(jié)的函數(shù);

對

(2)f是從X到Y(jié)的函數(shù),但不是滿射,也不是單射的;

錯

(3)f是從X到Y(jié)的滿射,但不是單射;

錯

(4)f是從X到Y(jié)的雙射.錯

第三篇：離散數(shù)學(xué)課后習(xí)題答案第四章

第十章部分課后習(xí)題參考答案

4．判斷下列集合對所給的二元運(yùn)算是否封閉：（1）整數(shù)集合Z和普通的減法運(yùn)算。

封閉,不滿足交換律和結(jié)合律，無零元和單位元（2）非零整數(shù)集合普通的除法運(yùn)算。不封閉

（R）和矩陣加法及乘法運(yùn)算，其中n2。（3）全體n?n實(shí)矩陣集合封閉 均滿足交換律，結(jié)合律，乘法對加法滿足分配律； 加法單位元是零矩陣，無零元；

乘法單位元是單位矩陣，零元是零矩陣；

（4）全體n?n實(shí)可逆矩陣集合關(guān)于矩陣加法及乘法運(yùn)算，其中n2。不封閉（5）正實(shí)數(shù)集合和運(yùn)算，其中運(yùn)算定義為：

不封閉

因?yàn)?1?1?1?1?1?1??1?R?（6）n關(guān)于普通的加法和乘法運(yùn)算。

封閉，均滿足交換律，結(jié)合律，乘法對加法滿足分配律 加法單位元是0，無零元；

乘法無單位元（n?1），零元是0；n?1單位元是1（7）A = {a1,a2,?,an} n運(yùn)算定義如下：

封閉 不滿足交換律，滿足結(jié)合律，（8）S = 關(guān)于普通的加法和乘法運(yùn)算。

封閉

均滿足交換律，結(jié)合律，乘法對加法滿足分配律（9）S = {0,1},S是關(guān)于普通的加法和乘法運(yùn)算。

加法不封閉，乘法封閉；乘法滿足交換律，結(jié)合律（10）S = ,S關(guān)于普通的加法和乘法運(yùn)算。

加法不封閉，乘法封閉，乘法滿足交換律，結(jié)合律

5．對于上題中封閉的二元運(yùn)算判斷是否適合交換律，結(jié)合律，分配律。

見上題

7．設(shè) * 為Z?上的二元運(yùn)算?x,y?Z?，X * Y = min(x，y),即x和y之中較小的數(shù).(1)求4 * 6，7 * 3。

4,(2)* 在Z上是否適合交換律，結(jié)合律，和冪等律？ 滿足交換律，結(jié)合律，和冪等律

(3)求*運(yùn)算的單位元，零元及Z?中所有可逆元素的逆元。單位元無，零元1, 所有元素?zé)o逆元

8．S?Q?Q Q為有理數(shù)集，*為S上的二元運(yùn)算，,S有

< a，b >* = （1）*運(yùn)算在S上是否可交換，可結(jié)合？是否為冪等的？ 不可交換：*= ?< a，b >* 可結(jié)合：(*)*=*= *(*)=*=(*)*=*(*)不是冪等的

（2）*運(yùn)算是否有單位元，零元？ 如果有請指出，并求S中所有可逆元素的逆元。

設(shè)是單位元，S，*= *= 則==，解的=<1,0>，即為單位。

設(shè)是零元，S，*= *= 則==，無解。即無零元。

S，設(shè)是它的逆元*= *=<1,0> ==<1,0> a=1/x,b=-y/x 所以當(dāng)x?0時，?x,y??1?1y,? xx?

10．令S={a，b}，S上有四個運(yùn)算：*，分別有表10.8確定。

(a)

(b)

(c)

(d)

(1)這4個運(yùn)算中哪些運(yùn)算滿足交換律，結(jié)合律，冪等律？(a)交換律，結(jié)合律，冪等律都滿足，零元為a,沒有單位元；(b)滿足交換律和結(jié)合律，不滿足冪等律，單位元為a,沒有零元

a?1?a,b?1?b(c)滿足交換律,不滿足冪等律,不滿足結(jié)合律

a?(b?b)?a?a?b, a?(b?b)?(a?b)?b

沒有單位元, 沒有零元

(d)不滿足交換律，滿足結(jié)合律和冪等律

沒有單位元, 沒有零元

(2)求每個運(yùn)算的單位元，零元以及每一個可逆元素的逆元。見上

(a?b)?b?a?b?a

16．設(shè)V=〈 N，+，〉，其中+，分別代表普通加法與乘法，對下面給定的每個集合確定它是否構(gòu)成V的子代數(shù)，為什么？

（1）S1=（2）S2= 是

不是 加法不封閉

（3）S3 = {-1，0，1} 不是，加法不封閉

第十一章部分課后習(xí)題參考答案

8.設(shè)S={0，1，2，3}，為模4乘法，即

y=(xy)mod 4 “?x,y∈S, x問〈S，〉是否構(gòu)成群？為什么？

y=(xy)mod 4?S,是S上的代數(shù)運(yùn)算。解：(1)?x,y∈S, x(2)?x,y,z∈S,設(shè)xy=4k+r 0?r?3

(xy)z =((xy)mod 4)

z=r

z=(rz)mod 4 =(4kz+rz)mod 4=((4k+r)z)mod 4 =(xyz)mod 4 同理x(yz)=(xyz)mod 4 y)z = x1)=(1(y

z)，結(jié)合律成立。所以，(x(3)?x∈S,(xx)=x,，所以1是單位元。

(4)1?1?1,3?1?3, 0和2沒有逆元 所以，〈S，9.設(shè)Z為整數(shù)集合，在Z上定義二元運(yùn)算。如下： ” ?x,y∈Z,xoy= x+y-2 問Z關(guān)于o運(yùn)算能否構(gòu)成群？為什么？ 〉不構(gòu)成群 解：(1)?x,y∈Z, xoy= x+y-2?Z,o是Z上的代數(shù)運(yùn)算。(2)?x,y,z∈Z,(xoy)oz =(x+y-2)oz=(x+y-2)+z-2=x+y+z-4 同理(xoy)oz= xo(yoz)，結(jié)合律成立。

(3)設(shè)e是單位元，?x∈Z, xoe= eox=x,即x+e-2= e+x-2=x, e=2(4)?x∈Z , 設(shè)x的逆元是y, xoy= yox=e, 即x+y-2=y+x-2=2, 所以，x?1?y?4?x 所以〈Z，o〉構(gòu)成群

??10??10?11.設(shè)G=???01??,??0?1??,???????10???10????01??,??0?1???，證明G關(guān)于矩陣乘法構(gòu)成一個群． ?????解：(1)?x,y∈G, 易知xy∈G,乘法是Z上的代數(shù)運(yùn)算。

(2)矩陣乘法滿足結(jié)合律

?10?(3)設(shè)??01??是單位元，??(4)每個矩陣的逆元都是自己。所以G關(guān)于矩陣乘法構(gòu)成一個群．

14.設(shè)G為群，且存在a∈G,使得 G={ak∣k∈Z} 證明：G是交換群。

證明:?x,y∈G，設(shè)x?ak,y?al，則

xy?akal?ak?l??al?k?alak?yx 所以，G是交換群

17.設(shè)G為群，證明e為G中唯一的冪等元。

22證明:設(shè)e0?G也是冪等元，則e0?e0，即e0?e0e，由消去律知e0?e

18.設(shè)G為群，a,b,c∈G,證明

∣abc∣=∣bca∣=∣cab∣ 證明：先證設(shè)(abc)k?e?(bca)k?e 設(shè)(abc)k?e,則(abc)(abc)(abc)?(abc)?e，即

a(bc)(abc)(abc)?a(bc)aa?1?e 左邊同乘a?1，右邊同乘a得

(bca)(bca)(bca)?(bca)?(bac)k?a?1ea?e

反過來，設(shè)(bac)k?e,則(abc)k?e.由元素階的定義知，∣abc∣=∣bca∣，同理∣bca∣=∣cab∣

19.證明：偶數(shù)階群G必含2階元。

證明：設(shè)群G不含2階元，?a?G，當(dāng)a?e時，a是一階元，當(dāng)a?e時，a至少是3階元,因?yàn)槿篏時有限階的，所以a是有限階的，設(shè)a是k階的,則a?1也是k階的，所以高于3階的元成對出現(xiàn)的，G不含2階元，G含唯一的1階元e,這與群G是偶數(shù)階的矛盾。所以，偶數(shù)階群G必含2階元

20.設(shè)G為非Abel群，證明G中存在非單位元a和b,a≠b,且ab=ba.證明：先證明G含至少含3階元。

若G只含1階元,則G={e},G為Abel群矛盾；

若G除了1階元e外,其余元a均為2階元，則a2?e，a?1?a

?a,b?G,a?1?a,b?1?b,(ab)?1?ab,所以ab?a?1b?1?(ba)?1?ba，與G為Abel群矛盾；

所以，G含至少含一個3階元，設(shè)為a，則a?a2，且a2a?aa2。令b?a2的證。

21.設(shè)G是Mn(R)上的加法群，n≥2，判斷下述子集是否構(gòu)成子群。（1）全體對稱矩陣 是子群（2）全體對角矩陣 是子群

（3）全體行列式大于等于0的矩陣.不是子群（4）全體上（下）三角矩陣。是子群

22.設(shè)G為群，a是G中給定元素，a的正規(guī)化子N（a）表示G中與a可交換的元素構(gòu)成的集合，即 N（a）={x∣x∈G∧xa=ax} 證明N（a）構(gòu)成G的子群。證明：ea=ae,e?N(a)??

?x,y?N(a),則ax?xa,ay?ya

a(xy)?(ax)y?(xa)y?x(ay)?x(ya)?(xy)a,所以xy?N(a)

由ax?xa，得x?1axx?1?x?1xax?1,x?1ae?eax?1，即x?1a?ax?1，所以x?1?N(a)所以N（a）構(gòu)成G的子群

31.設(shè)?1是群G1到G2的同態(tài)，?2是G2到G3的同態(tài)，證明?1??2是G1到G3的同態(tài)。證明：有已知?1是G1到G2的函數(shù)，?2是G2到G3的函數(shù)，則?1·?2是G1到G3的函數(shù)。

?a,b?G1,(?1??2)(ab)??2(?1(ab))??2(?1(a)?1(b))

?(?2(?1(a)))(?2(?1(b)))?(?1??2)(a)(?1??2)(b)所以:?1·?2是G1到G3的同態(tài)。

33.證明循環(huán)群一定是阿貝爾群，說明阿貝爾群是否一定為循環(huán)群，并證明你的結(jié)論。

證明：設(shè)G是循環(huán)群,令G=,?x,y?G,令x?ak,y?al,那么

xy?akal?ak?l?al?k?alak?yx,G是阿貝爾群

克萊因四元群,G?{e,a,b,c}

?eeabceabcaaecb bbceaccbae是交換群,但不是循環(huán)群,因?yàn)閑是一階元，a,b,c是二階元。36.設(shè)?,?是5元置換，且

?12345??12345?????21453??，????34512??

????(1)計(jì)算??,??,??1,??1,??1??；(2)將??,??1,??1??表成不交的輪換之積。

(3)將（2）中的置換表示成對換之積，并說明哪些為奇置換，哪些為偶置換。

?12345??12345??1?12345???解：(1)???? ????45321??43125?? ????45123??

????????1?12345??12345??1???21534?? ??????54132?? ????)??1?(14253(2)???(1425)(25))??1???(143(3)???(14)(12)(15)奇置換，??1?(14)(12)(15)(13)偶置換

??1???(14)(13)(25)奇置換

第四篇：離散數(shù)學(xué)習(xí)題及答案

離散數(shù)學(xué)考試試題（A卷及答案）

一、（10分）某項(xiàng)工作需要派A、B、C和D 4個人中的2個人去完成，按下面3個條件，有幾種派法？如何派？

(1)若A去，則C和D中要去1個人；

(2)B和C不能都去；

(3)若C去，則D留下。

解設(shè)A：A去工作；B：B去工作；C：C去工作；D：D去工作。則根據(jù)題意應(yīng)有：A?C?D，?(B∧C)，C??D必須同時成立。因此

(A?C?D)∧?(B∧C)∧(C??D)

?(?A∨(C∧? D)∨(?C∧D))∧(?B∨?C)∧(?C∨?D)

?(?A∨(C∧? D)∨(?C∧D))∧((?B∧?C)∨(?B∧?D)∨?C∨(?C∧?D))

?(?A∧?B∧?C)∨(?A∧?B∧?D)∨(?A∧?C)∨(?A∧?C∧?D)

∨(C∧? D∧?B∧?C)∨(C∧? D∧?B∧?D)∨(C∧? D∧?C)∨(C∧? D∧?C∧?D)∨(?C∧D∧?B∧?C)∨(?C∧D∧?B∧?D)∨(?C∧D∧?C)∨(?C∧D∧?C∧?D)

?F∨F∨(?A∧?C)∨F∨F∨(C∧? D∧?B)∨F∨F∨(?C∧D∧?B)∨F∨(?C∧D)∨F ?(?A∧?C)∨(?B∧C∧? D)∨(?C∧D∧?B)∨(?C∧D)

?(?A∧?C)∨(?B∧C∧? D)∨(?C∧D)

?T

故有三種派法：B∧D，A∧C，A∧D。

二、（15分）在謂詞邏輯中構(gòu)造下面推理的證明：某學(xué)術(shù)會議的每個成員都是專家并且是工人，有些成員是青年人，所以，有些成員是青年專家。

解：論域：所有人的集合。S(x)：x是專家；W(x)：x是工人；Y(x)：x是青年人；則推理化形式為：

?x(S(x)∧W(x))，?xY(x)?x(S(x)∧Y(x))

下面給出證明：

(1)?xY(x)P

(2)Y(c)T(1)，ES

(3)?x(S(x)∧W(x))P

(4)S(c)∧W(c)T(3)，US

(5)S(c)T(4)，I

(6)S(c)∧Y(c)T(2)(5)，I

(7)?x(S(x)∧Y(x))T(6)，EG

三、（10分）設(shè)A、B和C是三個集合，則A?B??(B?A)。

證明：A?B??x(x∈A→x∈B)∧?x(x∈B∧x?A)??x(x?A∨x∈B)∧?x(x∈B∧x?A)

???x(x∈A∧x?B)∧??x(x?B∨x∈A)???x(x∈A∧x?B)∨??x(x∈A∨x?B)

??(?x(x∈A∧x?B)∧?x(x∈A∨x?B))??(?x(x∈A∧x?B)∧?x(x∈B→x∈A))

??(B?A)。

四、（15分）設(shè)A＝{1，2，3，4，5}，R是A上的二元關(guān)系，且R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>}，求r(R)、s(R)和t(R)。

解r(R)＝R∪IA＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，1>，<2，2>，<3，3>，<4，4>，<5，5>}

s(R)＝R∪R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，2>，<4，2>，<4，3>} R＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}

R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<5，4>}

R＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}＝R

t(R)＝?Ri＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<2，2>，<5，1>，<5，4>，<5，i?1?4232－

15>}。

五、（10分）R是非空集合A上的二元關(guān)系，若R是對稱的，則r(R)和t(R)是對稱的。

證明對任意的x、y∈A，若xr(R)y，則由r(R)＝R∪IA得，xRy或xIAy。因R與IA對稱，所以有yRx或yIAx，于是yr(R)x。所以r(R)是對稱的。

下證對任意正整數(shù)n，R對稱。

因R對稱，則有xRy??z(xRz∧zRy)??z(zRx∧yRz)?yRx，所以R對稱。若Rn對稱，則xRn?1y??z(xRnz∧zRy)??z(zRnx∧yRz)?yRn?1x，所以Rn?1對稱。因此，對任意正整數(shù)n，Rn對稱。對任意的x、y∈A，若xt(R)y，則存在m使得xRy，于是有yRx，即有yt(R)x。因此，t(R)是對稱的。

六、（10分）若f：A→B是雙射，則f：B→A是雙射。

證明因?yàn)閒：A→B是雙射，則f是B到A的函數(shù)。下證f是雙射。

對任意x∈A，必存在y∈B使f(x)＝y(tǒng)，從而f(y)＝x，所以f是滿射。

對任意的y1、y2∈B，若f(y1)＝f(y2)＝x，則f(x)＝y(tǒng)1，f(x)＝y(tǒng)2。因?yàn)閒：A→B是函數(shù)，則y1＝y(tǒng)2。所以f是單射。

綜上可得，f：B→A是雙射。

七、（10分）設(shè)是一個半群，如果S是有限集，則必存在a∈S，使得a*a＝a。

證明因?yàn)?S，*>是一個半群，對任意的b∈S，由*的封閉性可知，b＝b*b∈S，b＝b*b∈S，…，bn∈S，…。

因?yàn)镾是有限集，所以必存在j＞i，使得bi＝bj。令p＝j(luò)－i，則bj＝bp*bj。所以對q≥i，有bq＝bp*bq。

因?yàn)閜≥1，所以總可找到k≥1，使得kp≥i。對于bkp∈S，有bkp＝bp*bkp＝bp*(bp*bkp)＝…＝232－1－1－1－1－1－1－1－1－1mm222nbkp*bkp。

令a＝bkp，則a∈S且a*a＝a。

八、（20分）（1）若G是連通的平面圖，且G的每個面的次數(shù)至少為l(l≥3)，則G的邊數(shù)m與結(jié)點(diǎn)數(shù)n有如下關(guān)系：

m≤

rl(n－2)。l?2l證明設(shè)G有r個面，則2m＝

2)。?d(f)≥lr。由歐拉公式得，n－m＋r＝2。于是，m≤l?2(n－ii?

1（2）設(shè)平面圖G＝是自對偶圖，則| E|＝2(|V|－1)。

證明設(shè)G＝是連通平面圖G＝的對偶圖，則G? G，于是|F|＝|V*|＝|V|，將其代入歐拉公式|V|－|E|＋|F|＝2得，|E|＝2(|V|－1)。**

離散數(shù)學(xué)考試試題（B卷及答案）

一、（10分）證明(P∨Q)∧(P?R)∧(Q?S)S∨R

證明因?yàn)镾∨R??R?S，所以，即要證(P∨Q)∧(P?R)∧(Q?S)?R?S。

(1)?R附加前提

(2)P?RP

(3)?PT(1)(2)，I

(4)P∨QP

(5)QT(3)(4)，I

(6)Q?SP

(7)ST(5)(6)，I

(8)?R?SCP

(9)S∨RT(8)，E

二、（15分）根據(jù)推理理論證明：每個考生或者勤奮或者聰明，所有勤奮的人都將有所作為，但并非所有考生都將有所作為，所以，一定有些考生是聰明的。

設(shè)P(e)：e是考生，Q(e)：e將有所作為，A(e)：e是勤奮的，B(e)：e是聰明的，個體域：人的集合，則命題可符號化為：?x(P(x)?(A(x)∨B(x)))，?x(A(x)?Q(x))，??x(P(x)?Q(x))?x(P(x)∧B(x))。

(1)??x(P(x)?Q(x))P

(2)??x(?P(x)∨Q(x))T(1)，E

(3)?x(P(x)∧?Q(x))T(2)，E

(4)P(a)∧?Q(a)T(3)，ES

(5)P(a)T(4)，I

(6)?Q(a)T(4)，I

(7)?x(P(x)?(A(x)∨B(x))P

(8)P(a)?(A(a)∨B(a))T(7)，US

(9)A(a)∨B(a)T(8)(5)，I

(10)?x(A(x)?Q(x))P

(11)A(a)?Q(a)T(10)，US

(12)?A(a)T(11)(6)，I

(13)B(a)T(12)(9)，I

(14)P(a)∧B(a)T(5)(13)，I

(15)?x(P(x)∧B(x))T(14)，EG

三、（10分）某班有25名學(xué)生，其中14人會打籃球，12人會打排球，6人會打籃球和排球，5人會打籃球和網(wǎng)球，還有2人會打這三種球。而6個會打網(wǎng)球的人都會打另外一種球，求不會打這三種球的人數(shù)。

解設(shè)A、B、C分別表示會打排球、網(wǎng)球和籃球的學(xué)生集合。則：

|A|＝12，|B|＝6，|C|＝14，|A∩C|＝6，|B∩C|＝5，|A∩B∩C|＝2，|(A∪C)∩B|＝6。

因?yàn)閨(A∪C)∩B|＝(A∩B)∪(B∩C)|＝|(A∩B)|＋|(B∩C)|－|A∩B∩C|＝|(A∩B)|＋5－2＝6，所以|(A∩

B)|＝3。于是|A∪B∪C|＝12＋6＋14－6－5－3＋2＝20，|A?B?C|＝25－20＝5。故，不會打這三種球的共5人。

四、（10分）設(shè)A1、A2和A3是全集U的子集，則形如?Ai?(Ai?為Ai或Ai)的集合稱為由A1、A2和

i?1

3A3產(chǎn)生的小項(xiàng)。試證由A1、A2和A3所產(chǎn)生的所有非空小項(xiàng)的集合構(gòu)成全集U的一個劃分。

證明小項(xiàng)共8個，設(shè)有r個非空小項(xiàng)s1、s2、…、sr(r≤8)。

對任意的a∈U，則a∈Ai或a∈Ai，兩者必有一個成立，取Ai?為包含元素a的Ai或Ai，則a∈?Ai?，i?13即有a∈?si，于是U??si。又顯然有?si?U，所以U＝?si。

i?1i?1i?1i?1rrrr

任取兩個非空小項(xiàng)sp和sq，若sp≠sq，則必存在某個Ai和Ai分別出現(xiàn)在sp和sq中，于是sp∩sq＝?。綜上可知，{s1，s2，…，sr}是U的一個劃分。

五、（15分）設(shè)R是A上的二元關(guān)系，則：R是傳遞的?R*R?R。

證明(5)若R是傳遞的，則∈R*R??z(xRz∧zSy)?xRc∧cSy，由R是傳遞的得xRy，即有∈R，所以R*R?R。

反之，若R*R?R，則對任意的x、y、z∈A，如果xRz且zRy，則∈R*R，于是有∈R，即有xRy，所以R是傳遞的。

六、（15分）若G為連通平面圖，則n－m＋r＝2，其中，n、m、r分別為G的結(jié)點(diǎn)數(shù)、邊數(shù)和面數(shù)。證明對G的邊數(shù)m作歸納法。

當(dāng)m＝0時，由于G是連通圖，所以G為平凡圖，此時n＝1，r＝1，結(jié)論自然成立。

假設(shè)對邊數(shù)小于m的連通平面圖結(jié)論成立。下面考慮連通平面圖G的邊數(shù)為m的情況。

設(shè)e是G的一條邊，從G中刪去e后得到的圖記為G?，并設(shè)其結(jié)點(diǎn)數(shù)、邊數(shù)和面數(shù)分別為n?、m?和r?。對e分為下列情況來討論：

若e為割邊，則G?有兩個連通分支G1和G2。Gi的結(jié)點(diǎn)數(shù)、邊數(shù)和面數(shù)分別為ni、mi和ri。顯然n1＋n2＝n?＝n，m1＋m2＝m?＝m－1，r1＋r2＝r?＋1＝r＋1。由歸納假設(shè)有n1－m1＋r1＝2，n2－m2＋r2＝2，從而(n1＋n2)－(m1＋m2)＋(r1＋r2)＝4，n－(m－1)＋(r＋1)＝4，即n－m＋r＝2。

若e不為割邊，則n?＝n，m?＝m－1，r?＝r－1，由歸納假設(shè)有n?－m?＋r?＝2，從而n－(m－1)＋r－1＝2，即n－m＋r＝2。

由數(shù)學(xué)歸納法知，結(jié)論成立。

七、（10分）設(shè)函數(shù)g：A→B，f：B→C，則：

(1)f?g是A到C的函數(shù)；

(2)對任意的x∈A，有f?g(x)＝f(g(x))。

證明(1)對任意的x∈A，因?yàn)間：A→B是函數(shù)，則存在y∈B使∈g。對于y∈B，因f：B→C是函數(shù)，則存在z∈C使∈f。根據(jù)復(fù)合關(guān)系的定義，由∈g和∈f得∈g*f，即∈f?g。所以Df?g＝A。

對任意的x∈A，若存在y1、y2∈C，使得、∈f?g＝g*f，則存在t1使得∈g且∈f，存在t2使得∈g且∈f。因?yàn)間：A→B是函數(shù)，則t1＝t2。又因f：B→C是函數(shù)，則y1＝y(tǒng)2。所以A中的每個元素對應(yīng)C中惟一的元素。

綜上可知，f?g是A到C的函數(shù)。

(2)對任意的x∈A，由g：A→B是函數(shù)，有∈g且g(x)∈B，又由f：B→C是函數(shù)，得∈f，于是∈g*f＝f?g。又因f?g是A到C的函數(shù)，則可寫為f?g(x)＝f(g(x))。

八、（15分）設(shè)是的子群，定義R＝{|a、b∈G且a1*b∈H}，則R是G中的－

一個等價關(guān)系，且[a]R＝aH。

證明對于任意a∈G，必有a1∈G使得a1*a＝e∈H，所以∈R。－－

若∈R，則a1*b∈H。因?yàn)镠是G的子群，故(a1*b)1＝b1*a∈H。所以∈R。－－－－

若∈R，∈R，則a1*b∈H，b1*c∈H。因?yàn)镠是G的子群，所以(a1*b)*(b1*c)＝a－－－－

－1*c∈H，故∈R。

綜上可得，R是G中的一個等價關(guān)系。

對于任意的b∈[a]R，有∈R，a1*b∈H，則存在h∈H使得a1*b＝h，b＝a*h，于是b∈aH，－－

[a]R?aH。對任意的b∈aH，存在h∈H使得b＝a*h，a1*b＝h∈H，∈R，故aH?[a]R。所以，[a]R－

＝aH。

第五篇：離散數(shù)學(xué)及其應(yīng)用集合論部分課后習(xí)題答案

作業(yè)答案：集合論部分

P90:習(xí)題六

5、確定下列命題是否為真。（2）???（4）??{?}

（6）{a,b}?{a,b,c,{a,b}} 解答：（2）假（4）真（6）真

8、求下列集合的冪集。（5）{{1,2},{2,1,1},{2,1,1,2}}（6）{{?,2},{2}} 解答：

（5）集合的元素彼此互不相同，所以{2,1,1,2}?{1,2}，所以該題的結(jié)論應(yīng)該為

{?,{{1,2}},{{2,1,1}},{{1,2},{2,1,1}}}

（6）{?,{{?,2}},{{2}},{{?,2},{2}}}

9、設(shè)E?{1,2,3,4,5,6}，A?{1,4}，B?{1,2,5},C?{2,4},求下列集合。（1）A（2）解答：（1）A（2）

31、設(shè)A,B,C為任意集合，證明 B

(AB)

B?{1,4}{3,4,6}?{4}

(AB)?{1}?{2,3,4,5,6}

(A?B)證明：

(B?A)?(AB)?(AB)

(A?B)(B?A)?{x|x?A?B?x?B?A}?{x|(x?A?x?B)?(x?B?x?A)}?{x|(x?A?x?B)?(x?B?x?B)?(x?A?x?A)?(x?B?x?A)} ?{x|(x?A?x?B)?(x?B?x?A)}?{x|(x?A?{x|(x?A?A

B)?(x?A?x?B)}?{x|(x?AB)?(x?ABB)}?{x|(x?AB)?(x?A?x?B)}B)}B)?(x?AB?A34、設(shè)A,B為集合，證明：如果(A?B)證明：（反證法）

設(shè)a?A(B?A)?AB，則AB??。

B，則a?A,a?B，所以a?A?B,a?B?A； 所以a?(A?B)但是a?A與(A?B)

37、設(shè)A,B,C為任意集合，證明：C?A?C?B?C?(A證明：

對任意x?C，由于C?A,C?B，所以x?A且x?B所以x?A因此，C?(A

(B?A)

B矛盾。

B)。

B B。

(B?A)?AB)。

P121:習(xí)題七

5、設(shè)A,B為任意集合，證明

若A?A?B?B，則A?B。

證明：

x?A??x,x??A?A

??x,x??B?B?x?B所以有A?B

9、設(shè)A?{1,2,4,6}，列出下列關(guān)系R（2）R?{?x,y?|x,y?A?|x?y|?1}（3）R?{?x,y?|x,y?A?y為素?cái)?shù)} 解答：

11、Ri是X上的二元關(guān)系，對于x?X定義集合（2）R?{?1,2?,?2,1?}

（3）R?{?1,2?,?2,2?,?4,2?,?6,2?}

Ri(x)?{y|xRy}

顯然Ri(x)?X。如果X?{?4,?3,?2,?1,0,1,2,3,4},且令

R1?{?x,y?|x,y?X?x?y}

R2?{?x,y?|x,y?X?y?1?x?y?2} R3?{?x,y?|x,y?X?x2?y}

求R1(0),R1(1),R2(0),R2(?1),R3(3)。解答：

R1(0)?{1,2,3,4}R1(1)?{2,3,4}R2(0)?{?1,0}R2(?1)?{?2,?1}R3(3)??，B?{?1,3?,?2,4?,?4,2?}。求A13、設(shè)A?{?1,2??,2,4,??3,3}?

B，AB，domA,domB,dom(A解答：

B),ranA,ranB,ran(AB),fld(A?B).AAB?{?1,2?,?2,4?,?3,3?,?1,3?,?4,2?} B?{?2,4?}

domA?{1,2,3} domB?{1,2,4} dom(AB)?{1,2,3,4}

ranA?{2,3,4} ranB?{2,3,4} ran(A B)?{4}

fld(A?B)?{1,2,3}

16、設(shè)A?{a,b,c,d}，R1,R2為A上的關(guān)系，其中

R1?{?a,a?,?a,b?,?b,d?}，R2?{?a,d?,?b,c?,?b,d?,?c,b?}。求R1R2，R2R1，R12，R23。

解答：

R1R2?{?a,d?,?a,c?,?a,d?} R2R1?{?c,d?}

R12?{?a,a?,?a,b?,?a,d?} R22?{?b,b?,?c,c?,?c,d?} R23?{?b,c?,?b,d?,?c,b?}

20、給定A?{1,2,3,4}，A上的關(guān)系R?{?1,3?,?1,4?,?2,3?,?2,4?,?3,4?}（1）畫出R的關(guān)系圖。（2）說明R的性質(zhì)。解答：

（1）

（2）R具有反自反性，反對稱性，傳遞性

21、設(shè)A?{1,2,3}，圖7.11給出12種A上的關(guān)系，對于每種關(guān)系寫出相應(yīng)的關(guān)系矩陣，并說明它所具有的性質(zhì)。

解答：

?110???（a）111,具有自反性。????101???110???（b）001,具有反對稱性和傳遞性。????100???111???（c）111,具有自反性，對稱性和傳遞性。????111??

23、設(shè)R的關(guān)系圖如圖7.12所示，試給出r(R)，s(R)和t(R)的關(guān)系圖。

25、設(shè)A?{1,2,3,4}，R是A上的等價關(guān)系，且R是A上所構(gòu)成的等價類為{1},{2,3,4}。（1）求R。（2）求RR（3）求R傳遞閉包。解答：

（1）R?{?1,1?,?2,2?,?3,3?,?4,4?,?2,3?,?3,2?,?2,4?,?4,2?,?3,4?, ?1?4,3?}

（2）由于等價關(guān)系滿足對稱性，所以R所以RR?1?1?R

?R

（3）由于等價關(guān)系滿足傳遞性，所以傳遞閉包為其自身，即t(R)?R

26、對于給定的A和R，判斷R是否為A上的等價關(guān)系。（1）A為實(shí)數(shù)集，?x,y?A,xRy?x?y?2。（2）A?{1,2,3}，?x,y?A,xRy?x?y?3。（3）A?Z，?x,y?A,xRy?xy為奇數(shù)。

（5）A?P(X),C?X，?x,y?A,xRy?x?y?C 解答：

（1）不是，不滿足自反性、對稱性、傳遞性。（2）不是，由于A?{1,2,3}集合較小，①自反性：?x?A,x?x?3??x,x??R

②對稱性，??x,y??R,x?y?3?y?x?3??y,x??R 但是傳遞性不滿足，?1,3?,?3,2??R，但是?1,2??R。?（3）不是，滿足對稱性、傳遞性，但是不滿足自反性 取x?2，但是2?2?4不為奇數(shù)，所以?2,2??R。

（5）滿足

①自反性：?x?A?x?X?x?x???C??x,x??R ②對稱性：??x,y??R?y?x?x?y?C??y,x??R ③傳遞性：??x,y?,?y,z??R

?x?y?C,y?z?C ?(x?y)?(y?x)?C,(y?z)?(z?y)?C?(x?y)?C,(y?x)?C,(y?z)?C,(z?y)?C下面證明(x?z)?C

?a?(x?z)?a?x,a?z

若a?y，則a?y?z，所以a?C 若a?y，則a?x?y，所以a?C

所以(x?z)?C，同理可證，(z?x)?C 所以x?z?(x?z)?(z?x)?C 所以?x,z??R。因此滿足傳遞性。

27、設(shè)A?{a,b,c,d},A上的等價關(guān)系

R?{?a,b?,?b,a?,?c,d?,?d,c?}?IA

畫出R的關(guān)系圖，并求出A中各元素的等價類。解答：關(guān)系圖為

等價類[a]?[b]?{a,b}；[c]?[d]?{c,d}

30、設(shè)A?{1,2,3,4},，在A?A上定義二元關(guān)系R，??u,v?,?x,y??A?A,?u,v?R?x,y??u?y?x?v。

（1）證明R為A?A上的等價關(guān)系。（2）確定由R引起的對A?A的劃分。解答：（1）證明：

①自反性：??x,y??A?A，由于x?y?x?y，所以??x,y?,?x,y???R； ②對稱性：???x,y?,?u,v???R

有x?v?u?y，所以u?y?x?v 因此??u,v?,?x,y???R

③傳遞性：???x,y?,?u,v??,??u,v?,?s,t???R

有x?v?u?y，u?t?s?v，所以x?s?t?y 因此??x,y?,?s,t???R。

（2）等價類有

[?1,1?]?{?1,1?,?2,2?,?3,3?,?4,4?} [?1,2?]?{?1,2?,?2,3?,?3,4?} [?1,3?]?{?1,3?,?2,4?} [?1,4?]?{?1,4?} [?2,1?]?{?2,1?,?3,2?,?4,3?} [?3,1?]?{?3,1?,?4,2?} [?4,1?]?{?4,1?}

37、對于下列集合與整除關(guān)系畫出哈斯圖。（1）{1,2,3,4,6,8,12,24}（2）{1,2,3,4,5,6,7,8,9,10,11,12} 解答：（1）

（2）

38、針對圖7.14中的每個哈斯圖，寫出集合以及偏序關(guān)系的表達(dá)式。

解答：

（a）集合為A?{1,2,3,4,5}，偏序關(guān)系為{?1,3?,?1,5?,?2,4?,?2,5?,?3,5?,?4,5?}?IA（b）集合為B?{a,b,c,d,e,f}，偏序關(guān)系為{?a,b?,?c,d?,?e,f?}?IB（c）集合為C?{1,2,3,4,5}，偏序關(guān)系{?1,2?,?1,3?,?1,4?,?1,5?,?2,4?,?2,5?,?3,4?,?3,5?,?4,5?}?IC

40、分別畫出下列偏序集?A,R??的哈斯圖，并找出A的極大元、極小元、最大元和最小元。

（1）A?{a,b,c,d,e,f}，R??{?a,d?,?a,c?,?a,b?,?a,e?,?b,e?,?c,e?,?d,e?}?IA

R??{?c,d?}?IA（2）A?{a,b,c,d,e}

解答：

（1）哈斯圖為

極小元為a,f,極大元為e,f，無最大元、最小元（2）哈斯圖為

極小元為a,b,c,e，極大元為a,b,d,e，無最大元、最小元

41、A?{1,2,3....,12}，R為整除關(guān)系，B?{x|2?x?4}，在偏序集?A,R?中求B的上界、下界、最小上界和最大下界。

解：下界即為公約數(shù)，2，3，4的公約數(shù)只有1，所以下界為1，最大下界也為1；

下界即為公倍數(shù)，2，3，4的公倍數(shù)只有12，所以上界為1，最大上界也為12；

P141:習(xí)題八

4、判斷下列函數(shù)中哪些是滿射？哪些是單射？哪些是雙射？（2）f:N?N,f(x)?x2?2（4）f:N?{0,1},f(x)???0?1xisodd

xiseven（6）f:R?R,f(x)?x2?2x?15

解答：（2）單射；（3）滿射；（4）既不為單射也不為滿射。

{1,2,3}

5、設(shè)X?{a,b,c,d},Y?，f?{?a,1?,?b,2?,?c,3?}，判斷下列命題的真假。

（1）f是從X到Y(jié)的二元關(guān)系，但不是X到Y(jié)的函數(shù)。（3）f是從X到Y(jié)的滿射，但不是單射。解答：（1）真；（3）假

15、設(shè)A?{a,b,c}，R為A上的等價關(guān)系，且R?{?a,b?,?b,a?}?IA，求自然映射g:A?A/R。

解答： A/R?{{a,b},{c}}

?{a,b}g(x)???cx?a,b x?c19、設(shè)f,g是從N到N的函數(shù)，且

?x?1?f(x)??0?x?（1）求f（2）說明f解答： x?0,1,2,3x?4x?5g

?x?

g(x)??2??3xiseven

xisoddg是否為單射、滿射、雙射？

（1）f?3?x?1??g?g(f(x))??2?0?x??2x?0,2,5,7,9......x?1,3x?4x?6,8,10,12.....（2）為滿射，但是不為單射。

20、設(shè)f:N?N?N，f(x)??x,x?1?（1）說明f是否為單射和滿射，說明理由。

（2）f的反函數(shù)是否存在，如果存在，求出f的反函數(shù)；（3）求ranf。解答：

（1）x?y時，?x,x?1???y,y?1?，所以為單射； 而對?1,3??N?N，不存在x?N，使得f(x)??x,x?1?，所以不為滿射。

（2）不存在反函數(shù)，因?yàn)椴皇请p射函數(shù)；（3）ranf?{?x,x?1?|x?N}

22、對于以下集合A和B，構(gòu)造從A到B的雙射函數(shù)。（1）A?{1,2,3},B?{a,b,c}（2）A?(0,1),B?(0,2)

（3）A?{x|x?Z?x?0},B?N（4）A?R,B?R 解答： ??a?（1）f(x)??b?c?（2）f(x)?2xx?1x?2 x?3x?(0,1)（3）f(x)??x?1

（4）f(x)?ax(a?0,a?1)