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

習(xí)題六格與布爾代數(shù)

一、填空題

1、設(shè)是偏序集,如果_________, 則稱是(偏序)格.2、設(shè)〈B,∧,∨,′，0，1〉是布爾代數(shù)，對(duì)任意的a∈B,有a∨a′=____,a∧a′=______.3、一個(gè)格稱為布爾代數(shù)，如果它是______格和______格.4、設(shè)<>是有界格，a,bL,若ab=0,則a=b=_____；若ab=1,則a=b=____.二、證明題

1、設(shè)是格，a,b,c,d?L。試證：若a?b且c?d，則

a∧c?b∧d2、證明：在有補(bǔ)分配格中，每個(gè)元素的補(bǔ)元一定唯一。

3、設(shè)是一布爾代數(shù)，則

R={ | a?b=b}是S上的偏序關(guān)系

4、若是一個(gè)格，則對(duì)任意a、b、c?A，有若a≤c且b≤c，則a∨b≤c。

5、若是一個(gè)格，則對(duì)于任意a，b?A，證明以下兩個(gè)公式等價(jià)；

（1）a≤b

（2）a∨b =b6、證明：如果格中交對(duì)并是分配的，那么并對(duì)交也是分配的，反之亦然。

7、如果是有界格，全上界和全下界分別是1和0，則對(duì)任意元素a?A，證明：

a?1=1?a=1，a?0=0?a=a

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

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

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

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

(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必須同時(shí)成立。因此

(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ù)會(huì)議的每個(gè)成員都是專家并且是工人，有些成員是青年人，所以，有些成員是青年專家。

解：論域：所有人的集合。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是三個(gè)集合，則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是對(duì)稱的，則r(R)和t(R)是對(duì)稱的。

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

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

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

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

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

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

對(duì)任意的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è)是一個(gè)半群，如果S是有限集，則必存在a∈S，使得a*a＝a。

證明因?yàn)?S，*>是一個(gè)半群，對(duì)任意的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。所以對(duì)q≥i，有bq＝bp*bq。

因?yàn)閜≥1，所以總可找到k≥1，使得kp≥i。對(duì)于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的每個(gè)面的次數(shù)至少為l(l≥3)，則G的邊數(shù)m與結(jié)點(diǎn)數(shù)n有如下關(guān)系：

m≤

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

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

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

證明設(shè)G＝是連通平面圖G＝的對(duì)偶圖，則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ù)推理理論證明：每個(gè)考生或者勤奮或者聰明，所有勤奮的人都將有所作為，但并非所有考生都將有所作為，所以，一定有些考生是聰明的。

設(shè)P(e)：e是考生，Q(e)：e將有所作為，A(e)：e是勤奮的，B(e)：e是聰明的，個(gè)體域：人的集合，則命題可符號(hào)化為：?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人會(huì)打籃球，12人會(huì)打排球，6人會(huì)打籃球和排球，5人會(huì)打籃球和網(wǎng)球，還有2人會(huì)打這三種球。而6個(gè)會(huì)打網(wǎng)球的人都會(huì)打另外一種球，求不會(huì)打這三種球的人數(shù)。

解設(shè)A、B、C分別表示會(huì)打排球、網(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。故，不會(huì)打這三種球的共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的一個(gè)劃分。

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

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

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

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

五、（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，則對(duì)任意的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ù)。證明對(duì)G的邊數(shù)m作歸納法。

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

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

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

若e為割邊，則G?有兩個(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)對(duì)任意的x∈A，有f?g(x)＝f(g(x))。

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

對(duì)任意的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中的每個(gè)元素對(duì)應(yīng)C中惟一的元素。

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

(2)對(duì)任意的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中的－

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

證明對(duì)于任意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中的一個(gè)等價(jià)關(guān)系。

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

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

＝aH。

第三篇：離散數(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

命題符號(hào)化為： 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.用等值演算法判斷下列公式的類型，對(duì)不是重言式的可滿足式，再用真值表法求出成真賦值.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 ①化簡(jiǎn)律 ③q?s 前提引入 ④s?t 前提引入

⑤q?t ③④等價(jià)三段論 ⑥（q?t）?(t?q)⑤ 置換 ⑦（q?t）⑥化簡(jiǎn) ⑧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 ④化簡(jiǎn)律 ⑥r(nóng)?￢s 前提引入 ⑦r ⑥化簡(jiǎn)律 ⑧r?﹁r ⑤⑦ 合取

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

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

集合論

1.A={?,1}，B={{a}}求A的冪集、A×B、A∪B、A+B。2.A={1,2,3,4,5}, R={(x,y)|x

4.A={a,b,c},R= IA ∪{(a,b),(b,a)}，求a和b關(guān)于R的等價(jià)類。

5.R是A上的等價(jià)關(guān)系，A/R={{1,2}，{3}},求A，R。6.請(qǐng)分別判斷以下結(jié)論是否一定成立，如果一定成立請(qǐng)證明，否則請(qǐng)舉出反例。

①如果A∪B?C，則A?C或者B?C。②如果A×B=A×C且A??，則B=C。

27.如果R是A上的等價(jià)關(guān)系，R,r(R)是否一定是A上的等價(jià)關(guān)系？證明或舉例。

8.已知A∩C?B∩C,A-C?B-C,證明：A?B。9.證明：AX(B∩C)=(AXB)∩(AXC)10.證明：P(A)∪P(B)?P(A∪B)-111.證明：R[sym] iff R=R

-1212.證明：r(R)=R∪IA,S(R)=R∪R,t(R)=R∪R∪...13.證明：s(R∪S)=s(R)∪s(S)14.R是A上的關(guān)系，證明：如果R是對(duì)稱的，則r(R)也是對(duì)稱的。

15.I是整數(shù)集，R={(x,y)|x-y是3的倍數(shù)}，證明：R是I上的等價(jià)關(guān)系。

16.如果R是A上的等價(jià)關(guān)系，則A/R一定是A的劃分。17.R是集合A上的自反關(guān)系，S是A上的自反和對(duì)稱關(guān)系，證明t(R∪S)是A上的等價(jià)關(guān)系。18.I是正整數(shù)集合，R是I×I上的二元關(guān)系，R={<,>|xv=yu},證明：R是等價(jià)關(guān)系。

19.f:A?B，R是B上的等價(jià)關(guān)系，令S={|x?A且y?A且?R}，證明：S是A上的等價(jià)關(guān)系。

20.R是集合A上的自反關(guān)系，S是A上的自反和對(duì)稱關(guān)系，證明t(R∪S)是A上的等價(jià)關(guān)系。

21.P和Q都是集合A上的劃分，請(qǐng)問P∪Q，P-Q是否是A上的劃分，22.R?AXA,R[irref]且R[tra],證明：r(R)是A上的偏序關(guān)系。

23.畫出{1,2,3,4,6}上整除關(guān)系的哈斯圖，求{2,3,6}的4種元素。

24.A={a,b,c,d,e,f,g},R={(a,c),(a,e),(b,d),(b,f),(d,e),(d,f)},S=tr(R),畫出S的哈斯圖并求{b,c,d,f}的極大元等8種元素。

25.f:A→B,g:B→C都是單（滿）射，證明：復(fù)合映射gof一定是單（滿）射。

26.f:A→B,g:B→C，gof是單射，請(qǐng)問f和g是否一定是單射？請(qǐng)證明或舉出反例。27.R是實(shí)數(shù)集，f:R×R?R×R,f()=,請(qǐng)問f是否為單射？是否為滿射？分別證明或舉反例。28.已知B∩C=?,令f：P(B∪C)?P(B)×P(C)，對(duì)X?P(B∪C),令f(X)=(B∩X,C∩X),證明：f是雙射。

代數(shù)系統(tǒng)

1.是模8加群，Z8={0,1,2,3,4,5,6,7},+8是模8加法，求出的單位元、每個(gè)元素的逆元、所有的生成元和所有的子群。

2.求的單位元，零元，每個(gè)元素的逆元，每個(gè)元素的階，它是循環(huán)群?jiǎn)?？求出它所有的子群?/p>

3.R是實(shí)數(shù)集，在R上定義運(yùn)算*為x*y=x+y+xy,問：是代數(shù)系統(tǒng)嗎？有單位元嗎？每個(gè)元素都有逆元嗎？ ***4.R是非零實(shí)數(shù)集合，是代數(shù)系統(tǒng)，對(duì)于R中元素*x,y，令xoy=2x+2y-2。請(qǐng)問中是否存在單位元、零元、哪些元素有逆元？運(yùn)算o是否滿足交換律和結(jié)合律。分別說明理由。

5.R是實(shí)數(shù)集，R上的6運(yùn)算定義如下：對(duì)R中元素x,y，f1()=x+y；f2()=x-y；f3()=xy；f4()=x/y；f5()=max{x,y}；f6()=|x-y|。問：哪些滿足交換律、結(jié)合律、有單位元、有零元？說明理由。

6.是一個(gè)群，證明：G是交換群當(dāng)且僅當(dāng)對(duì)任意G中222元素x,y,都有等式(xy)=xy成立。

7.證明：如果群G中每個(gè)元素的逆元素都是它自已，則G是交換群。

8.循環(huán)群一定是交換群。

9.證明：階為素?cái)?shù)的群一定是循環(huán)群。

-110.是一個(gè)群，u?G,定義運(yùn)算*：x*y=xouoy, 證明：是一個(gè)群。

11.整數(shù)集Z上定義運(yùn)算*：對(duì)任意整數(shù)x和y,x*y=x+y-4,其中+，-為普通加減法。證明：是一個(gè)群。

12.證明：如果群G中至少有兩個(gè)元素，則群中沒有零元。13.S是G的子群，證明：{x|x是S的左陪集}是G的一個(gè)劃分

14.是一個(gè)群,a?G,n是a的階(周期)，證明：k<{a|k=0,2,…,n-1},o>是的一個(gè)子群。

15.H，K都是群G的子群，請(qǐng)問H∩K,H∪K,H-K是否一定是G的子群？ 16.H，K是G的兩個(gè)子群，a?G, 試證：aH?aK當(dāng)且僅當(dāng)H?K。17.G={1,3,4,5,9},*是模11的乘法(即x*y=xy mod 11)，請(qǐng)問(G,*)是否構(gòu)成群？

n18.是群，e是單位元，a?G,a的階為k,證明：a=e當(dāng)且僅當(dāng) n是k的倍數(shù)。

19.S是G的子群，證明：{x|x是S的左陪集}是G的一個(gè)劃分

20.G是群，證明：S={a?G|?x?G(ax=xa)},則S是G的子群。21.是偶數(shù)階群，則G中必存在2階元素。22.證明：6個(gè)元素的群在同構(gòu)意義下只有兩個(gè)。

++23.R為實(shí)數(shù)集，R為正實(shí)數(shù)集，與是否同構(gòu)？ 24.是有限群，證明：G不可能表示成兩個(gè)真子群的并。25.圖論

1.如何判斷二部圖？完全圖、完全二部圖的邊數(shù)。2.如何求E回路？

3.Petersen圖是否為E圖或H圖。

4.哪些完全圖是H圖？哪些完全圖是E圖？ 5.n為何值時(shí)輪圖為H圖？ 6.如何求最小生成樹。

7.證明：奇數(shù)個(gè)頂點(diǎn)的二部圖（兩步圖）不是哈密爾頓圖。8.證明：如果G是歐拉圖，則其邊圖L(G)也是歐拉圖。9.證明：奇數(shù)個(gè)頂點(diǎn)的二部圖（兩步圖）不是哈密爾頓圖。10.G是平面圖，G有m條邊，n個(gè)頂點(diǎn)，證明：m?3n-6。并由此證明K5不是平面圖。

11.證明：有6個(gè)頂點(diǎn)的簡(jiǎn)單無向圖G和它的補(bǔ)圖中至少有一個(gè)三角形。

12.證明：在至少有兩個(gè)頂點(diǎn)的無向樹中，至少有2個(gè)一度頂點(diǎn)。

13.G是無向簡(jiǎn)單連通圖，G有n個(gè)頂點(diǎn)，則G最少有幾條邊，最多有幾條邊？

14.證明：簡(jiǎn)單無向圖G和它的補(bǔ)圖中至少有一個(gè)是連通圖。15.證明：無向圖中奇度點(diǎn)（度數(shù)為奇數(shù)的點(diǎn)）有偶數(shù)個(gè)。16.證明：n個(gè)頂點(diǎn)的無向連通圖至少有n-1條邊。17.G是H圖，V是G的頂點(diǎn)集，證明：對(duì)任意頂點(diǎn)集S，??S?V，都有ω（G-S）≤|S|。其中ω（G-S）表示G-S的分圖數(shù)目。18.一棵無向樹有3個(gè)3次點(diǎn)，1個(gè)頂點(diǎn)次數(shù)為2，其余頂點(diǎn)次數(shù)為1，問它有幾個(gè)次數(shù)為1的頂點(diǎn)？寫出求解過程。19.證明：每個(gè)簡(jiǎn)單平面圖都包含一個(gè)次至多為5的頂點(diǎn)。20.連通平面圖G有n個(gè)頂點(diǎn)，m條邊和f個(gè)面，證明：n-m+f=2。21.如果圖G的最大頂點(diǎn)次數(shù)≤ρ，證明：G是ρ+1可點(diǎn)著色的。

22.G是無向簡(jiǎn)單連通圖，G有n個(gè)頂點(diǎn)，則G最少有幾條邊，最多有幾條邊？

23.如果一個(gè)簡(jiǎn)單圖G和它的補(bǔ)圖同構(gòu)，則稱G是自補(bǔ)圖，求所有4個(gè)頂點(diǎn)自補(bǔ)圖。

24.G是平面圖，G有m條邊，n個(gè)頂點(diǎn)，證明：m?3n-6。如果G中無三角形，則m?2n-4。數(shù)理邏輯

1.如果今天是星期一，則要進(jìn)行英語(yǔ)或數(shù)理邏輯考試。

沒有不犯錯(cuò)誤的人。整數(shù)都是有理數(shù)。有的有理數(shù)不是整數(shù)。

不存在最大的整數(shù)。有且只有一個(gè)偶數(shù)是素?cái)?shù)。2.求真值表及范式：P?(┓Q?R)、(┓Q?R)?(P?R)3.推理：

p?(q?r)，┓s∨p，q ├ s?r p?r，q?s，p∨q ├ r∨s p∨q，p?┓r，s?t，┓s?r，┓t ├ q p?(┓(r∧s)?┓q),p,┓s ├ ┓q 4.如果小王是理科學(xué)生，他一定會(huì)學(xué)好數(shù)學(xué)。如果小王不是文科學(xué)生，他一定是理科學(xué)生。小王沒學(xué)好數(shù)學(xué)。所以小王是文科學(xué)生。

5.判斷各公式在給定解釋時(shí)的真假值，并且改變論域使該公式在新的解釋下取值相反。論域：D={-2,3,6}, F(x):x≤3, G(x):x>5, R(x,y):x+y<4 ①?x(F(x)∨G(x))②?y?yR(x,y)

第五篇：離散數(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各不相同，判斷下述等式中哪個(gè)等式為真:（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．化簡(jiǎn)下列集合表達(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個(gè)學(xué)生，其中14人會(huì)打籃球，12人會(huì)打排球，6人會(huì)打籃球和排球，5人會(huì)打籃球和網(wǎng) 球，還有2人會(huì)打這三種球。已知6個(gè)會(huì)打網(wǎng)球的人都會(huì)打籃球或排球。求不會(huì)打球的人數(shù)。解: 阿A={會(huì)打籃球的人}，B={會(huì)打排球的人}，C={會(huì)打 |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 不會(huì)打球的人共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上的等價(jià)關(guān)系.(2)確定由R 引起的對(duì)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是對(duì)稱的

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

∴R是A×A上的等價(jià)關(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為等價(jià)關(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是對(duì)稱的 任意的,,∈A×A 若R,R 則a+b=c+d,c+d=x+y ∴a+b=x+y ∴R ∴R是傳遞的

∴R是 A×A上的等價(jià)關(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.對(duì)于下列集合與整除關(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.下圖是兩個(gè)偏序集的哈斯圖.分別寫出集合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ù);

對(duì)

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

錯(cuò)

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

錯(cuò)

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