【正文】 ，B(e)：e是聰明的，個(gè)體域：人的集合，則命題可符號化為：x(P(x)174。R174。PT(1)(2)，I(4)P∨QP(5)QT(3)(4)，I(6)Q174。R附加前提(2)P174。S。S)216。S，所以，即要證(P∨Q)∧(P174。216。R)∧(Q174。證明設(shè)G＝是連通平面圖G＝的對偶圖，則G G，于是|F|＝|V*|＝|V|，將其代入歐拉公式|V|－|E|＋|F|＝2得，|E|＝2(|V|－1)。由歐拉公式得，n－m＋r＝2。229。八、（20分）（1）若G是連通的平面圖，且G的每個(gè)面的次數(shù)至少為l(l≥3)，則G的邊數(shù)m與結(jié)點(diǎn)數(shù)n有如下關(guān)系：m≤rl(n－2)。對于bkp∈S，有bkp＝bp*bkp＝bp*(bp*bkp)＝…＝232－1－1－1－1－1－1－1－1－1mm222nbkp*bkp。所以對q≥i，有bq＝bp*bq。因?yàn)镾是有限集，所以必存在j＞i，使得bi＝bj。七、（10分）設(shè)是一個(gè)半群，如果S是有限集，則必存在a∈S，使得a*a＝a。所以f是單射。對任意的yy2∈B，若f(y1)＝f(y2)＝x，則f(x)＝y(tǒng)1，f(x)＝y(tǒng)2。下證f是雙射。六、（10分）若f：A→B是雙射，則f：B→A是雙射。對任意的x、y∈A，若xt(R)y，則存在m使得xRy，于是有yRx，即有yt(R)x。yRn+1x，所以Rn+1對稱。$z(xRnz∧zRy)219。yRx，所以R對稱。$z(xRz∧zRy)219。下證對任意正整數(shù)n，R對稱。因R與IA對稱，所以有yRx或yIAx，于是yr(R)x。五、（10分）R是非空集合A上的二元關(guān)系，若R是對稱的，則r(R)和t(R)是對稱的。四、（15分）設(shè)A＝{1，2，3，4，5}，R是A上的二元關(guān)系，且R＝{，}，求r(R)、s(R)和t(R)。(B204。B)∧x(x∈B→x∈A))219。216。B)∧x(x∈A∨x207。216。x(x∈A∨x207。$x(x∈A∧x207。B∨x∈A)222。B)∧216。216。A∨x∈B)∧$x(x∈B∧x207。A)219。B219。A)。216。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。二、（15分）在謂詞邏輯中構(gòu)造下面推理的證明：某學(xué)術(shù)會(huì)議的每個(gè)成員都是專家并且是工人，有些成員是青年人，所以，有些成員是青年專家。C∧D)219。B∧C∧216。A∧216。C∧D)219。C∧D∧216。B∧C∧216。A∧216。C∧D)∨F 219。C∧D∧216。 D∧216。A∧216。D)219。C∧D∧216。C∧D∧216。B∧216。C)∨(216。C∧D∧216。C∧216。C)∨(C∧216。D)∨(C∧216。 D∧216。B∧216。D)∨(C∧216。A∧216。A∧216。B∧216。C)∨(216。A∧216。D))219。C∨(216。B∧216。B∧216。 D)∨(216。(216。C∨216。B∨216。 D)∨(216。(216。216。D)∧216。因此(A174。216。D，216。則根據(jù)題意應(yīng)有：A174。第一篇：離散數(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去工作。C197。(B∧C)，C174。D必須同時(shí)成立。C197。(B∧C)∧(C174。D)219。A∨(C∧216。C∧D))∧(216。C)∧(216。D)219。A∨(C∧216。C∧D))∧((216。C)∨(216。D)∨216。C∧216。(216。B∧216。A∧216。D)∨(216。C)∨(216。C∧216。 D∧216。C)∨(C∧216。B∧216。 D∧216。 D∧216。D)∨(216。B∧216。C∧D∧216。D)∨(216。C)∨(216。C∧216。F∨F∨(216。C)∨F∨F∨(C∧216。B)∨F∨F∨(216。B)∨F∨(216。(216。C)∨(216。 D)∨(216。B)∨(216。(216。C)∨(216。 D)∨(216。T故有三種派法：B∧D，A∧C，A∧D。解：論域：所有人的集合。B222。(B204。證明：A204。x(x∈A→x∈B)∧$x(x∈B∧x207。x(x207。A)219。$x(x∈A∧x207。x(x207。216。B)∨216。B)219。($x(x∈A∧x207。B))219。($x(x∈A∧x207。216。A)。解r(R)＝R∪IA＝{，，}s(R)＝R∪R＝{，} R＝{，}R＝{，}R＝{，}＝Rt(R)＝URi＝{，，15}。證明對任意的x、y∈A，若xr(R)y，則由r(R)＝R∪IA得，xRy或xIAy。所以r(R)是對稱的。因R對稱，則有xRy219。$z(zRx∧yRz)219。若Rn對稱，則xRn+1y219。$z(zRnx∧yRz)219。因此，對任意正整數(shù)n，Rn對稱。因此，t(R)是對稱的。證明因?yàn)閒：A→B是雙射，則f是B到A的函數(shù)。對任意x∈A，必存在y∈B使f(x)＝y(tǒng)，從而f(y)＝x，所以f是滿射。因?yàn)閒：A→B是函數(shù)，則y1＝y(tǒng)2。綜上可得，f：B→A是雙射。證明因?yàn)槭且粋€(gè)半群，對任意的b∈S，由*的封閉性可知，b＝b*b∈S，b＝b*b∈S，…，bn∈S，…。令p＝j(luò)－i，則bj＝bp*bj。因?yàn)閜≥1，所以總可找到k≥1，使得kp≥i。令a＝bkp，則a∈S且a*a＝a。l2l證明設(shè)G有r個(gè)面，則2m＝2)。d(f)≥lr。于是，m≤l2(n－ii=1（2）設(shè)平面圖G＝是自對偶圖，則| E|＝2(|V|－1)。**離散數(shù)學(xué)考試試題（B卷及答案）一、（10分）證明(P∨Q)∧(P174。S)S∨R證明因?yàn)镾∨R219。R174。R)∧(Q174。R174。(1)216。RP(3)216。SP(7)ST(5)(6)，I(8)216。SCP(9)S∨RT(8)，E二、（15分）根據(jù)推理理論證明：每個(gè)考生或者勤奮或者聰明，所有勤奮的人都將有所作為，但并非所有考生都將有所作為，所以，一定有些考生是聰明的。(A(x)∨B(x)))，x(A(x)174。x(P(x)174。(1)216。Q(x))P(2)216。P(x)∨Q(x))T(1)，E(3)$x(P(x)∧216。Q(a)T(3)，ES(5)P(a)T(4)，I(6)216。(A(x)∨B(x))P(8)P(a)174。Q(x))P(11)A(a)174。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ì)打這三種球。解設(shè)A、B、C分別表示會(huì)打排球、網(wǎng)球和籃球的學(xué)生集合。因?yàn)閨(A∪C)∩B|＝(A∩B)∪(B∩C)|＝|(A∩B)|＋|(B∩C)|－|A∩B∩C|＝|(A∩B)|＋5－2＝6，所以|(A∩B)|＝3。故，不會(huì)打這三種球的共5人。(Ai162。試證由AA2和A3所產(chǎn)生的所有非空小項(xiàng)的集合構(gòu)成全集U的一個(gè)劃分。對任意的a∈U，則a∈Ai或a∈Ai，兩者必有一個(gè)成立，取Ai162。i=13即有a∈Usi，于是U205。又顯然有Usi205。i=1i=1i=1i=1rrrr任取兩個(gè)非空小項(xiàng)sp和sq，若sp≠sq，則必存在某個(gè)Ai和Ai分別出現(xiàn)在sp和sq中，于是sp∩sq＝198。五、（15分）設(shè)R是A上的二元關(guān)系，則：R是傳遞的219。R。$z(xRz∧zSy)222。R。R，則對任意的x、y、z∈A，如果xRz且zRy，則∈R*R，于是有∈R，即有xRy，所以R是傳遞的。證明對G的邊數(shù)m作歸納法。假設(shè)對邊數(shù)小于m的連通平面圖結(jié)論成立。設(shè)e是G的一條邊，從G中刪去e后得到的圖記為G162。、m162。對e分為下列情況來討論：若e為割邊，則G162。Gi的結(jié)點(diǎn)數(shù)、邊數(shù)和面數(shù)分別