【正文】 4。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的每個面的次數(shù)至少為l(l≥3)，則G的邊數(shù)m與結(jié)點數(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。因為S是有限集，所以必存在j＞i，使得bi＝bj。七、（10分）設(shè)是一個半群，如果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是三個集合，則A204。二、（15分）在謂詞邏輯中構(gòu)造下面推理的證明：某學(xué)術(shù)會議的每個成員都是專家并且是工人，有些成員是青年人，所以，有些成員是青年專家。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。)t1=(14253(2)ts=(1425)(25))s1ts=(143(3)ts=(14)(12)(15)奇置換，t1=(14)(12)(15)(13)偶置換s1ts=(14)(13)(25)奇置換第四篇：離散數(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留下。232。 232。54132247。 sts=231。21534247。1=231。230。s1230。232。232。232。45123247。 t=231。43125247。45321247。解：(1)ts=231。247。1230。230。230。(1)計算st,ts,t1,s1,s1ts；(2)將ts,t1,s1ts表成不交的輪換之積。232。232。34512247。t=231。21453247。s=231。230。,t是5元置換，且230。證明：設(shè)G是循環(huán)群,令G=,x,y206。j2是G1到G3的同態(tài)。a,b206。證明：有已知j1是G1到G2的函數(shù)，j2是G2到G3的函數(shù)，則j1N(a)由ax=xa，得x1axx1=x1xax1,x1ae=eax1，即x1a=ax1，所以x1206。fx,y206。證明：ea=ae,e206。（1）全體對稱矩陣 是子群（2）全體對角矩陣 是子群（3）（4）全體上（下）三角矩陣。令b=a2的證。G,a1=a,b1=b,(ab)1=ab,所以ab=a1b1=(ba)1=ba，與G為Abel群矛盾；所以，G含至少含一個3階元，設(shè)為a，則a185。所以，偶數(shù)階群G必含2階元，證明G中存在非單位元a和b,a≠b,且ab=：先證明G含至少含3階元。G，當(dāng)a=e時，a是一階元，當(dāng)a185。(bca)k=e 設(shè)(abc)k=e,則(abc)(abc)(abc)L(abc)=e，即a(bc)(abc)(abc)La(bc)aa1=e 左邊同乘a1，右邊同乘a得(bca)(bca)(bca)L(bca)=(bac)k=a1ea=e反過來，設(shè)(bac)k=e,則(abc)k=，∣abc∣=∣bca∣，同理∣bca∣=∣cab∣：偶數(shù)階群G必含2階元。22證明:設(shè)e0206。所以G關(guān)于矩陣乘法構(gòu)成一個群．，且存在a∈G,使得 G={ak∣k∈Z} 證明：G是交換群。248。247。231。10246。解：(1)x,y∈G, 易知xy∈G,乘法是Z上的代數(shù)運算。248。248。253。01247。,231。01247。231。10246。10246。232。248。,248。01247。,231。01247。231。(2)x,y,z∈Z,(xoy)oz =(x+y2)oz=(x+y2)+z2=x+y+z4 同理(xoy)oz= xo(yoz)，結(jié)合律成立。如下： ” x,y∈Z,xoy= x+y2 問Z關(guān)于o運算能否構(gòu)成群？為什么？ 〉不構(gòu)成群 解：(1)x,y∈Z, xoy= x+y2206。所以，(x(3)x∈S,(xx)=x,，所以1是單位元。r163。S,是S上的代數(shù)運算。(aob)ob沒有單位元, 沒有零元(d)不滿足交換律，滿足結(jié)合律和冪等律沒有單位元, 沒有零元(2)求每個運算的單位元，零元以及每一個可逆元素的逆元。0時，x,y1=1y, xx+10．令S={a，b}，S上有四個運算：*。即無零元。設(shè)是單位元，S，*= *= 則==，解的=，即為單位。Q Q為有理數(shù)集，*為S上的二元運算，,S有 a，b * = （1）*運算在S上是否可交換，可結(jié)合？是否為冪等的？ 不可交換：*= 185。4,(2)* 在Z上是否適合交換律，結(jié)合律，和冪等律？ 滿足交換律，結(jié)合律，和冪等律(3)求*運算的單位元，零元及Z+中所有可逆元素的逆元。見上題7．設(shè) * 為Z+上的二元運算x,y206。加法不封閉，乘法封閉；乘法滿足交換律，結(jié)合律（10）S = ,S關(guān)于普通的加法和乘法運算。封閉，均滿足交換律，結(jié)合律，乘法對加法滿足分配律 加法單位元是0，無零元；乘法無單位元（n1），零元是0；n=1單位元是1（7）A = {a1,a2,L,an} n運算定義如下：封閉 不滿足交換律，滿足結(jié)合律，（8）S = 關(guān)于普通的加法和乘法運算。111=1207。n實可逆矩陣集合關(guān)于矩陣加法及乘法運算，其中n2。（3）全體n180。封閉,不滿足交換律和結(jié)合律，無零元和單位元（2）非零整數(shù)集合普通的除法運算。﹁r ⑤⑦ 合取由于最后一步r217。q 前提引入 ⑤￢r ④化簡律 ⑥r(nóng)217。p 證明：①p 結(jié)論的否定引入 ②p174。216。r218。216。r)前提引入 ⑤q174。p 前提引入 ③p ①②假言推理 ④p174。p,q 結(jié)論：s174。(q174。p 前提引入 ⑩p ⑧⑨假言推理(11)p217。q)⑤ 置換 ⑦（q174。t）217。t 前提引入⑤q171。r 前提引入 ②t ①化簡律 ③q171。q ③④拒取式 ⑥p174。216。216。r)前提引入 ②216。q證明：（2）①216。t,t217。p,q171。r),r 結(jié)論：216。q,216。1 219。r))219。(p218。216。((216。q218。p218。q218。r))218。q218。p217。219。q218。(q217。216。q218。(q217。r219。q)217。(p217。q217。p218。216。q217?！?1)(2)主合取范式為：216。q)219。(p218。216。1217。q218。q218。p))217。(216。(216。q218。q)218。p217。q218。q)218。219。p)219。p→q)→(216。m3219。m0218。(p217。216。q)218。p217。216。q)218。p)218。q217。p)218。(216。216。p)(216。(216。216。p)(216。(216。(p218。219。216。q218。(p→q)∧q∧r(3)(p∨(q∧r))→(p∨q∨r)解：（1）主析取范式(216。p→q)→(216。(p∨q)∧216。1∧(p∨q)∧216。p)∧(216。p)∧(p∨q)∧(216。p∧q)219。p∧q))∧(216。p∧q)219。p→(q∧r)（4）(p∧216。216。p∨q)∧(216。(p∧q)證明（2