第一篇：湘潭大學 劉任任版 離散數(shù)學課后習題答案 習題15

習題十五

1、設下面所有謂詞的論域D={a、b、c}。試將下面命題中的量詞消除，寫成與之等值的命題公式。分析：本題主要是考察對全稱量詞、存在量詞的理解，然后通過合取詞、析取詞把全稱量詞和存在量詞消去。（1）?xR?x???S?x?

解：?R(a)?R(b)?R(c)???S(a)?S(b)?S(c)?（2）?x?P?x??Q(x)?

解：?P(a)?Q(a))??P(b)?Q(b)???P(c)?Q(c)?（3）?x7P(x)??xP(x)

解：?7P(a)?7P(b)?7P(c))??P(a)?P(b)?P(c)?

2、指出下列命題的真值：

分析：本題主要是考察合式公式的解釋的定義，已經(jīng)判定給定解釋下合式公式的真值。（1）?x?P?Q(x))?R(e)

其中，P:“3＞2”,Q(x):“x?3”,R(x):“x＞5”,e:5，論域D={-2，3，6} 解：假。

（x為-2時不成立）（2）?x?P(x)?Q(x)?

其中，P(x):“x＞3”,Q(x):“x?4”，論域D={2}。解：真。

3、在一階邏輯中，將下列命題符號化：

分析：本題主要是考察存在量詞、全稱量詞已經(jīng)基本的連接詞的運用。（1）凡有理數(shù)均可表示為分數(shù)。

解：令：P(x)： x是有理數(shù)；Q（x）:x可表示為分數(shù)。

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

（2）有些實數(shù)是有理數(shù)。解：P（x）：:x是實數(shù)，Q(x)：x是有理數(shù)。

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

（3）并非所有實數(shù)都是有理數(shù)。解：P（x）：:x是實數(shù)，Q(x)：x是有理數(shù)。

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

（4）如果明天天氣好，有一些學生將去公園。

解：P（x）: x去公園

S（x）: x是學生

W：明天天氣好

W??x(P(x)?S(x))

（5）對任意的正實數(shù)，都存在大于該實數(shù)的實數(shù)。解：P（x）: x是實數(shù)；

G（x, y）：:x大于y。

?x(P(x)??y(P(y)?G(y,x)))（6）對任意給?＞0，x0??a,b?，都在存在N，使當n＞N時，有

f?x0??fn?x?解：G（x，y）: x＞y, S?x?:x??a,b?

＜?

???x0?G??,0??S?x0???N?n(G?n,N??G(?,f(x0)?fn(x))))

4、指出下列公式中的自由變元和約束變元，并指出各量詞的作用域。

分析：本題主要是考察自由邊緣、約束變元的定義，以及量詞的作用域的概念。（1）?x?P?x??Q?x????xR?x??Q?z?

解；自由變元z, 約束變元x, 第一個?x的作用域是?P?x??Q?x??，第二個是R(x)。

（2）?x(P(x)??y(Q(y))?(?xP(x)?Q(z))

中的P?x? 解：自由變元z，約束為元：x，y。第一個?x的作用域為P?x???yQ?y??

?

第二個?x的作用域為第二個P(x)； ?y的作用域為Q(y)。（3）?x(P(x)?Q(x))??yR(y)?s(z)

解：自由變元：z，約束變元：x和y；

?x的作用域為(P(x)?Q(x))，?y的作用域為R(y)

（4）?x(F(x)??yH(x,y))

解：無自由變元

約束變元x，y；

?x的作用域：(F(x)??yH(x，y))，?y的作用域：H(x,y)

（5）?xF(x)?G(x,y)

解：自由變元：y與G(x，y)中的x，約束變元：F(x)中的x；

?x的作用域：F(x)（6）?x?y(R(x,y)?Q(x,z))??xH(x,y)

解：自由變元：Z與H(x，y)中的y；

約束變元：x,y, ?x和?y的作用范圍：?(R(x,y)?Q(x,z)?，?x的作用范圍：H(x,y)

5．設謂詞公式?x(P(x,y)?Q(x,z))。判定以下改名是否正確 ：

分析：本題主要是考察改名規(guī)則的定義，以及它的適用范圍。有興趣的同學可以順便了解一下代替規(guī)則情形。

（1）?u(P(u,y)?Q(x,z))

解：錯誤（2）?u(P(u,y)?Q(u,z))

解：正確（3）?x(P(u,y)?Q(u,z))

解：錯誤（4）?u(P(x,y)?Q(x,z))

解：錯誤（5）?y(P(y,y)?Q(y,z))

解：錯誤 6．設I是如下一個解釋 ：

D:??a，b?，P(a，a):?1，P(a,b):?0，P(b,a):?0，P(b,b):?1。

試確定下列公式在I下的真值：

分析：本題主要考察合式公式在特定解釋下的真值。（1）?x?yP(x,y)

解：真

（2）?x?yP(x,y)

解：假

（3）?x?y(P(x,y)?P(y,x))解：真（4）?xP(x,x)

解：真

7．判斷下列公式的恒真性和恒假性

分析：本題主要是根據(jù)已知的命題公式、合式公式的基本等值式來進行推導，看該合式公式是與1等值還是與0等值。

（1）?xF(x)??xF(x)

解：恒真（2）?xF(x)?(?x?yG(x,y)??xF(x))

解：恒真（3）?xF(x)?(?x(F(x)??yG(y))

解：恒真（4）?(F(x,y)?F(x,y))

解：恒假

8．設G（x）是恰含自由變元x的謂詞公式，H是不含變元x的謂詞公式，證明：（1）?x(G(x)?H)??xG(x)?H（2）?x(G(x)?H)??xG(x)?H 分析：本題根據(jù)量詞作用域的擴張進行證明。證明（1）

?x(G(x)?H)??x(7G(x)?H)??x7G(x)?H?7(?xG(x))?H??xG(x)?H

證明（2）

?x(G(x)?H)??x(7G(x)?H)??x7G(x)?H?7(?xG(x))?H??xG(x)?H

9．設G（x，y）是任意一個含x，y自由出現(xiàn)的謂詞公式，證明：（1）?x?yG(x，y)??y?xG(x，y)

分析：本題主要是根據(jù)兩個合式公式等值的定義進行證明。證：設D是論域，I是G（x，y）的一個解釋。

（a）若?x?yG(x，y)在I下的為真，則在I下，對任意的x,y?D,G(x,y)即?y?xG(x,y)是真命題，反之亦然。

（b）若?x?yG(x,y)在I下為假，則在I下必存在x0?D或y0?D，使得G（x0, y）或G（x, y0）為假，于是，此xo或yo亦弄假?y?xG(x,y)，反之亦然。

（2）?x?yG(x，y)??y?xG(x，y)

分析：本題主要是根據(jù)兩個合式公式等值的定義進行證明。

證：設D是論域，I是G（x, y）的一個解釋。

（a）若?x?yG(x，y)在I下為真，則在I下存在x0?D與y0?D,使G（x0,y0）為真命題，于是，?y?xG(x,y)也是真命題，反之亦然。

（b）若?x?yG(x，y)在I下為假，則對任意x，y?D，G（x, y）均為假，故?y?xG(x,y)亦為假，反之亦然。

10．將下列公式化成等價的前束范式：

分析：本題主要是根據(jù)已知的基本等值式通過消去蘊含連接詞、等價連接詞，依據(jù)改名規(guī)則、代替規(guī)則進行等值演算化成前束范式。

（1）?xF(x)???xG(x)

解：?xF(x)???xG(x)??xF(x)??x?G(x)??x(F(x)??G(x))（2）?xF(x)??xG(x)解：

?xF(x)??xG(x)???xF(x)??xG(x)??x(7F(x))??xG(x)??x(7F(x)?G(x))

（3）(?xF(x,y)??yG(y))??xH(x,y)

解：

(?xF(x,y)??yG(y))??xH(x,y)?(7(?xF(x,y))??yG(y))??xH(x,y)?(?x(7F(x,y))??zG(z))??xH(x,y)??x?z(7F(x,y)?G(z))??xH(x,y)??x?z(F(x,y)?7G(z))??uH(u,y)??x?z?u((F(x,y)?G(z))?H(u,y))

（4）?x(P(x)??yQ(x,y))

解：?x(P(x)??yQ(x,y))??x(7P(x)??yQ(x,y))??x?y(7P(x)?Q(x,y))

11．給出下面公式的skolem范式：

分析：本題主要是根據(jù)已知的基本等值式通過消去蘊含連接詞、等價連接詞，依據(jù)改名規(guī)則、代替規(guī)則進行等值演算化成前束范式，然后根據(jù)前束范式寫出對應的skolem范式。

（1）7(?xP(x)??y?zQ(y,z))解：

7(?xP(x)??y?zQ(y,z))?(?xP(x)??y?zQ(y,z)??x?y?z(P(x)?Q(y,z))

∴所求為:?x?z(P(x)?Q(f(x),z))

（2）?x(7E(x,o)?(?y(E(y,g(x))??zE(z,g(x))?E(y,z)))))解: 原式??x(7E(x,o)?(?y?z(E(y),g(x)?E(z),g(x)?E(y,z))))

??x(7E(x,o)?7(?y?z(E(y)g(x))?E(y,g(x)?E(y,z))))??x(7E(x,o)?(?u??7(E(y),g(x))?E(?,g(x)?E(y,z))))

??x(7E(x,o)??u??((7(E(u),g(x)))?(7E(?1g(x)))?E(y,z))

??x?u??(E(x,o)?((7E(u,g(x)))?(7E(?,g(x)))?E(y,z))

即為所求

（3）7(?xP(x)??yP(y))

解：7(?xP(x)??yP(y))?7(7?xP(x)??yP(y)?7(?x7P(x)??yP(y)

?7(?x?y(7P(x)?P(y)))??x?y(P(x)?7P(y))即為所求。

12．假設?x?yM(x，y)是公式G的前束范式，其中M（x, y）是僅僅包含變量x，y的母式，設f是不出現(xiàn)在M（x, y）中的函數(shù)符號。證明：G恒真當且僅當?x?yM(x,f(x))恒真。

分析：本題主要是用反證法，根據(jù)解釋的定義來證明結論成立。

證：設G??x?yM(x，y)恒真。若?xM(x,f(x))不真，則存在一個解釋I, 使得對任意的x0?D（論域），M(x0,f(x0))為假。于是，G在I下也為假。此為矛盾。

反之，設?xM(x,f(x))恒真。若?x?yM(x，y)不是恒真，則存在一個解釋I’，使得對任意xi?D，存在yi?D，使M(xi，yi)為假。由于f是不出現(xiàn)在M(x，y)中的函數(shù)符號，故可定義函數(shù)f:使得f(xi)?yi。于是，?xM(x,f(x))在I’下為假。矛盾。

故結論成立。13．證明

D?D，(?x)(P(x)?Q(x))?(?x)(Q(x)?R(x))?(?x)(P(x)?R(x))

分析：本題是根據(jù)基本的等值式、蘊含式、以及US、UG、ES、EG規(guī)則證明結論成立。證：（1）(?x)(P(x)?Q(x))?(?x)(Q(x)?R(x))前提引入

(2)(?x)(P(x)?Q(x))

化簡（1）

（3）P(y)?Q(y)

US規(guī)則，根據(jù)（2）（4）(?x)(Q(x)?R(x))

化簡（1）

（5）Q(y)?R(y)

US規(guī)則，根據(jù)（4）

（6）P(y)?R(y)

假言三段論，根據(jù)（3），（5）（7）(?x)(P(x)?R(x))

ES規(guī)則，根據(jù)（6）

14．構造下面推理的證明：

分析：本題是根據(jù)基本的等值式、蘊含式、以及US、UG、ES、EG規(guī)則證明結論成立。前提：??x(F(x)?H(x)),?x(G(x)?H(x))結論：?xG(x)?7F(x)

證：（1）??x(F(x)?H(x))

前提引入

（2）?x(7F(x)?7H(x))

等價式（1）（3）?x(H(x)?7F(x))

等值式（2）（4）H(y)?7F(y)

US規(guī)則（3）（5）?x(G(x))?H(x)

前提引入（6）G(y)?H(y)

US規(guī)則（5）（7）G(y)??F(y)

假言三段論（4），（6）

（8）?x(G(x)?7F(x))

UG規(guī)則（7）

15．指出下面兩個推理的錯誤。

分析：本題主要是考察US、UG、ES、EG規(guī)則的適用范圍，也就是前提條件。（1）?x(F(x)?G(x))

前提引入

（2）F(y)?G(y)

US規(guī)則，根據(jù)（1）（3）?xF(x)

前提引入

（4）F（y）

ES,(3)（5）G（y）

假言推理，（2），（4）（6）?xG?x?

UG,(5）

解：（4）錯誤。F?y?中的變元y與（2）中的變元重名。

（1）?x?y?x，y?

前提引入（2）?yF(z,y)

US規(guī)則，（1）（3）F(z,c)

ES規(guī)則，（2）（4）?xF?x,c?

UG，（3）（5）?y?xF(x,y)

EG，（4）解：（3）錯誤。在?yF(z,y)中變元并非只有y。

16.每個學術會的成員都是知識分子并且是專家，有些成員是青年人。證明：有的成員是青年專家。分析：本題主要是首先把明天符號化，符號化前提，結論。然后根據(jù)US、UG、ES、EG規(guī)則證明結論成立。

解：P（x）：x是學術會的成員；

E（x）：x是專家；

G（x）：x是知識分子；

Y（x）：x是青年人。

前提：?x(P(x)?G(x)?E(x)),?(x)(P(x)?Y(x))結論：?x(P(x)?Y(x)?E(x))

證明：（1）?x(P(x)?G(x)?E(x)))

前提引入

（2）P(c)?(G(x)?E(c))

US,(1)

（3）?x(P(x)?Y(x))

前提引入（4）P(c)?Y(c)

ES,（3）（5）P（c）

化簡（4）

（6）G(c)?E(c)

假言推理,（2），（5）（7）E（c）

化簡,（6）

（8）Y(c)

化簡,（4）

（9）P(c)?Y(c)?E(c)

合取（5）（7）（8）（10）?x(P(x)?Y(x)?E(x))

EG

第二篇：離散數(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）公式類型為永真式（方法如上例）

第二章部分課后習題參考答案

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)第三章部分課后習題參考答案

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

證明：（2）

①?(q?r)前提引入 ②?q??r ①置換 ③q??r ②蘊含等值式 ④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 結論：s?r 證明

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

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

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

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

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

第三篇：離散數(shù)學課后習題答案第三章

第六章部分課后習題參考答案

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．設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．化簡下列集合表達式：（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個學生，其中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.設集合A＝{{1，2}，{2，3}，{1，3},{?}},計算下列表達式：（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、設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

第七章部分課后習題參考答案

7.列出集合A={2,3,4}上的恒等關系I A,全域關系EA,小于或等于關系LA,整除關系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.設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.設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．設A={a,b,c,d}，R1，R2為A上的關系，其中

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．設A={1，2，3，4}，在A?A上定義二元關系R，?,?A?A，〈u,v> R ?u + y = x + v.(1)證明R 是A?A上的等價關系.(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上的等價關系

(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.設A={1，2，3，4}，R為A?A上的二元關系, ?〈a，b〉，〈c，d〉? A?A ，〈a，b〉R〈c，d〉?a + b = c + d(1)證明R為等價關系.(2)求R導出的劃分.(1)證明：?

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

任意的,∈A×A 設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上的等價關系

(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.對于下列集合與整除關系畫出哈斯圖:(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和偏序關系R?的集合表達式.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)項目(1)(2)極大元: e a,b,d,e 極小元: a a,b,c,e 最大元: e 無 最小元: a 無

第八章部分課后習題參考答案

1．設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.設X={a,b,c,d},Y={1,2,3},f={,,,}判斷以下命題的真假:(1)f是從X到Y的二元關系,但不是從X到Y的函數(shù);

對

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

錯

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

錯

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

第四篇：離散數(shù)學課后習題答案第四章

第十章部分課后習題參考答案

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

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

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

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

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

不封閉

因為 1?1?1?1?1?1??1?R?（6）n關于普通的加法和乘法運算。

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

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

封閉 不滿足交換律，滿足結合律，（8）S = 關于普通的加法和乘法運算。

封閉

均滿足交換律，結合律，乘法對加法滿足分配律（9）S = {0,1},S是關于普通的加法和乘法運算。

加法不封閉，乘法封閉；乘法滿足交換律，結合律（10）S = ,S關于普通的加法和乘法運算。

加法不封閉，乘法封閉，乘法滿足交換律，結合律

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

見上題

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

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

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

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

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

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

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

設是零元，S，*= *= 則==，無解。即無零元。

S，設是它的逆元*= *=<1,0> ==<1,0> a=1/x,b=-y/x 所以當x?0時，?x,y??1?1y,? xx?

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

(a)

(b)

(c)

(d)

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

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

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

沒有單位元, 沒有零元

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

沒有單位元, 沒有零元

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

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

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

（1）S1=（2）S2= 是

不是 加法不封閉

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

第十一章部分課后習題參考答案

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

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

y=(xy)mod 4?S,是S上的代數(shù)運算。解：(1)?x,y∈S, x(2)?x,y,z∈S,設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)，結合律成立。所以，(x(3)?x∈S,(xx)=x,，所以1是單位元。

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

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

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

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

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

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

證明:?x,y∈G，設x?ak,y?al，則

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

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

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

18.設G為群，a,b,c∈G,證明

∣abc∣=∣bca∣=∣cab∣ 證明：先證設(abc)k?e?(bca)k?e 設(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

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

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

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

20.設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階元，設為a，則a?a2，且a2a?aa2。令b?a2的證。

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

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

22.設G為群，a是G中給定元素，a的正規(guī)化子N（a）表示G中與a可交換的元素構成的集合，即 N（a）={x∣x∈G∧xa=ax} 證明N（a）構成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的子群

31.設?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)群，并證明你的結論。

證明：設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)群,因為e是一階元，a,b,c是二階元。36.設?,?是5元置換，且

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

????(1)計算??,??,??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ù)學習題及答案

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

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

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

(2)B和C不能都去；

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

解設A：A去工作；B：B去工作；C：C去工作；D：D去工作。則根據(jù)題意應有：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分）在謂詞邏輯中構造下面推理的證明：某學術會議的每個成員都是專家并且是工人，有些成員是青年人，所以，有些成員是青年專家。

解：論域：所有人的集合。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分）設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分）設A＝{1，2，3，4，5}，R是A上的二元關系，且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上的二元關系，若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是雙射。

證明因為f：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。因為f：A→B是函數(shù)，則y1＝y(tǒng)2。所以f是單射。

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

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

證明因為是一個半群，對任意的b∈S，由*的封閉性可知，b＝b*b∈S，b＝b*b∈S，…，bn∈S，…。

因為S是有限集，所以必存在j＞i，使得bi＝bj。令p＝j－i，則bj＝bp*bj。所以對q≥i，有bq＝bp*bq。

因為p≥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與結點數(shù)n有如下關系：

m≤

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

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

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

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

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

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

證明因為S∨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ù)推理理論證明：每個考生或者勤奮或者聰明，所有勤奮的人都將有所作為，但并非所有考生都將有所作為，所以，一定有些考生是聰明的。

設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名學生，其中14人會打籃球，12人會打排球，6人會打籃球和排球，5人會打籃球和網(wǎng)球，還有2人會打這三種球。而6個會打網(wǎng)球的人都會打另外一種球，求不會打這三種球的人數(shù)。

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

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

因為|(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分）設A1、A2和A3是全集U的子集，則形如?Ai?(Ai?為Ai或Ai)的集合稱為由A1、A2和

i?1

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

證明小項共8個，設有r個非空小項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

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

五、（15分）設R是A上的二元關系，則：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的結點數(shù)、邊數(shù)和面數(shù)。證明對G的邊數(shù)m作歸納法。

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

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

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

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

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

七、（10分）設函數(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，因為g：A→B是函數(shù)，則存在y∈B使∈g。對于y∈B，因f：B→C是函數(shù)，則存在z∈C使∈f。根據(jù)復合關系的定義，由∈g和∈f得∈g*f，即∈f?g。所以Df?g＝A。

對任意的x∈A，若存在y1、y2∈C，使得、∈f?g＝g*f，則存在t1使得∈g且∈f，存在t2使得∈g且∈f。因為g：A→B是函數(shù)，則t1＝t2。又因f：B→C是函數(shù)，則y1＝y(tǒng)2。所以A中的每個元素對應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分）設是的子群，定義R＝{|a、b∈G且a1*b∈H}，則R是G中的－

一個等價關系，且[a]R＝aH。

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

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

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

－1*c∈H，故∈R。

綜上可得，R是G中的一個等價關系。

對于任意的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。