【正文】 第一篇：離散數(shù)學(xué)習(xí)題及答案離散數(shù)學(xué)考試試題（A卷及答案）一、（10分）某項工作需要派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)有：A174。C197。D，216。(B∧C)，C174。216。D必須同時成立。因此(A174。C197。D)∧216。(B∧C)∧(C174。216。D)219。(216。A∨(C∧216。 D)∨(216。C∧D))∧(216。B∨216。C)∧(216。C∨216。D)219。(216。A∨(C∧216。 D)∨(216。C∧D))∧((216。B∧216。C)∨(216。B∧216。D)∨216。C∨(216。C∧216。D))219。(216。A∧216。B∧216。C)∨(216。A∧216。B∧216。D)∨(216。A∧216。C)∨(216。A∧216。C∧216。D)∨(C∧216。 D∧216。B∧216。C)∨(C∧216。 D∧216。B∧216。D)∨(C∧216。 D∧216。C)∨(C∧216。 D∧216。C∧216。D)∨(216。C∧D∧216。B∧216。C)∨(216。C∧D∧216。B∧216。D)∨(216。C∧D∧216。C)∨(216。C∧D∧216。C∧216。D)219。F∨F∨(216。A∧216。C)∨F∨F∨(C∧216。 D∧216。B)∨F∨F∨(216。C∧D∧216。B)∨F∨(216。C∧D)∨F 219。(216。A∧216。C)∨(216。B∧C∧216。 D)∨(216。C∧D∧216。B)∨(216。C∧D)219。(216。A∧216。C)∨(216。B∧C∧216。 D)∨(216。C∧D)219。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是三個集合，則A204。B222。216。(B204。A)。證明：A204。B219。x(x∈A→x∈B)∧$x(x∈B∧x207。A)219。x(x207。A∨x∈B)∧$x(x∈B∧x207。A)219。216。$x(x∈A∧x207。B)∧216。x(x207。B∨x∈A)222。216。$x(x∈A∧x207。B)∨216。x(x∈A∨x207。B)219。216。($x(x∈A∧x207。B)∧x(x∈A∨x207。B))219。216。($x(x∈A∧x207。B)∧x(x∈B→x∈A))219。216。(B204。A)。四、（15分）設(shè)A＝{1，2，3，4，5}，R是A上的二元關(guān)系，且R＝{，，，}，求r(R)、s(R)和t(R)。解r(R)＝R∪IA＝{，，，，，}s(R)＝R∪R＝{，，，，} R＝{，，，}R＝{，，，}R＝{，，，}＝Rt(R)＝URi＝{，，，，，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對稱，則有xRy219。$z(xRz∧zRy)219。$z(zRx∧yRz)219。yRx，所以R對稱。若Rn對稱，則xRn+1y219。$z(xRnz∧zRy)219。$z(zRnx∧yRz)219。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是滿射。對任意的yy2∈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分）設(shè)是一個半群，如果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(luò)－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與結(jié)點數(shù)n有如下關(guān)系：m≤rl(n－2)。l2l證明設(shè)G有r個面，則2m＝2)。229。d(f)≥lr。由歐拉公式得，n－m＋r＝2。于是，m≤l2(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)∧(P174。R)∧(Q174。S)S∨R證明因為S∨R219。216。R174。S，所以，即要證(P∨Q)∧(P174。R)∧(Q174。S)216。R174。S。(1)216。R附加前提(2)P174。RP(3)216。PT(1)(2)，I(4)P∨QP(5)QT(3)(4)，I(6)Q174。SP(7)ST(5)(6)，I(8)216。R174。SCP(9)S∨RT(8)，E二、（15分）根據(jù)推理理論證明：每個考生或者勤奮或者聰明，所有勤奮的人都將有所作為，但并非所有考生都將有所作為，所以，一定有些考生是聰明的。設(shè)P(e)：e是考生，Q(e)：e將有所作為，A(e)：e是勤奮的，B(e)：e是聰明的，個體域：人的集合，則命題可符號化為：x(P(x)174。(A(x)∨B(x)))，x(A(x)174。Q(x))，216。x(P(x)174。Q(x))$x(P(x)∧B(x))。(1)216。x(P(x)174。Q(x))P(2)216。x(216。P(x)∨Q(x))T(1)，E(3)$x(P(x)∧216。Q(x))T(2)，E(4)P(a)∧216。Q(a)T(3)，ES(5)P(a)T(4)，I(6)216。Q(a)T(4)，I(7)x(P(x)174。(A(x)∨B(x))P(8)P(a)174。(A(a)∨B(a))T(7)，US(9)A(a)∨B(a)T(8)(5)，I(10)x(A(x)174。Q(x))P(11)A(a)174。Q(a)T(10)，US(12)216。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。因為|(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，|AUBUC|＝25－20＝5。故，不會打這三種球的共5人。四、（10分）設(shè)AA2和A3是全集U的子集，則形如IAi162。(