【正文】 （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è)集合，則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是對(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ì)稱，則有xRy219。$z(xRz∧zRy)219。$z(zRx∧yRz)219。yRx，所以R對(duì)稱。若Rn對(duì)稱，則xRn+1y219。$z(xRnz∧zRy)219。$z(zRnx∧yRz)219。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ì)任意的yy2∈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)槭且粋€(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)。l2l證明設(shè)G有r個(gè)面，則2m＝2)。229。d(f)≥lr。由歐拉公式得，n－m＋r＝2。于是，m≤l2(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)∧(P174。R)∧(Q174。S)S∨R證明因?yàn)镾∨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ù)推理理論證明：每個(gè)考生或者勤奮或者聰明，所有勤奮的人都將有所作為，但并非所有考生都將有所作為，所以，一定有些考生是聰明的。設(shè)P(e)：e是考生，Q(e)：e將有所作為，A(e)：e是勤奮的，B(e)：e是聰明的，個(gè)體域：人的集合，則命題可符號(hào)化為：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人會(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，|AUBUC|＝25－20＝5。故，不會(huì)打這三種球的共5人。四、（10分）設(shè)AA2和A3是全集U的子集，則形如IAi162。(Ai162。為Ai或Ai)的集合稱為由AA2和i=13A3產(chǎn)生的小項(xiàng)。試證由AA2和A3所產(chǎn)生的所有非空小項(xiàng)的集合構(gòu)成全集U的一個(gè)劃分。證明小項(xiàng)共8個(gè)，設(shè)有r個(gè)非空小項(xiàng)ss…、sr(r≤8)。對(duì)任意的a∈U，則a∈Ai或a∈Ai，兩者必有一個(gè)成立，取Ai162。為包含元素a的Ai或Ai，則a∈IAi162。，i=13即有a∈Usi，于是U205。Usi。又顯然有Usi205。U，所以U＝Usi。i=1i=1i=1i=1rrrr任取兩個(gè)非空小項(xiàng)sp和sq，若sp≠sq，則必存在某個(gè)Ai和Ai分別出現(xiàn)在sp和sq中，于是sp∩sq＝198。綜上可知，{s1，s2，…，sr}是U的一個(gè)劃分。五、（15分）設(shè)R是A上的二元關(guān)系，則：R是傳遞的219。R*R205。R。證明(5)若R是傳遞的，則∈R*R222。$z(xRz∧zSy)222。xRc∧cSy，由R是傳遞的得xRy，即有∈R，所以R*R205。R。反之，若R*R205。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后得到的圖記為G162。，并設(shè)其結(jié)點(diǎn)數(shù)、邊數(shù)和面數(shù)分別為n162。、m162。和r162。對(duì)e分為下列情況來討論：若e為割邊，則G162。有兩個(gè)連通分支G1和G2。Gi的結(jié)點(diǎn)數(shù)、邊數(shù)和面數(shù)分別為ni、mi和ri。顯然n1＋n2＝n162。＝n，m1＋m2＝m162。＝m－1，r1＋r2＝r162。＋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不為割邊，則n162。＝n，m162。＝m－1，r162。＝r－1，由歸納假設(shè)有n162。－m162。＋r162。＝2，從而n－(m－1)＋r－1＝2，即n－m＋r＝2。由數(shù)學(xué)歸納法知，結(jié)論成立。七、（10分）設(shè)函數(shù)g：A→B，f：B→C，則：(1)fog是A到C的函數(shù)；(2)對(duì)任意的x∈A，有fog(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，即∈fog。所以Dfog＝A。對(duì)任意的x∈A，若存在yy2∈C，使得、∈fog＝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中惟一的元素。綜上可知，fog是A到C的函數(shù)。(2)對(duì)任意的x∈A，由g：A→B是函數(shù)，有∈g且g(x)∈B，又由f：B→C是函數(shù)，得∈f，于是∈g*f＝fog。又因fog是A到C的函數(shù)，則可寫為fog(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]R205。aH。對(duì)任意的b∈aH，存在h∈H使得b＝a*h，a1*b＝h∈H，∈R，故aH205。[a]R。所以，[a]R－＝aH。