【正文】 6。B）∧（x206。B∧x207。 A∧x207。五、已知A、B、C是三個(gè)集合，證明A(B∪C)=(AB)∩(AC)（10分）。先求|A∩B|。Q(y)∧R(a)T(3)，US(5)Q(y)∧R(a)T(2)(4)，I(6)Q(y)T(5)，I(7)R(a)T(5)，I(8)P(a)∧R(a)T(2)(7)，I(9)$x(P(x)∧R(x))T(8)，EG(10)Q(y)∧$x(P(x)∧R(x))T(6)(9)，I四、某班有25名學(xué)生，其中14人會(huì)打籃球，12人會(huì)打排球，6人會(huì)打籃球和排球，5人會(huì)打籃球和網(wǎng)球，還有2人會(huì)打這三種球。(R∨S)(6)C∨DT(3)(4)，I P(7)R∨S T(5)，I 2)x(P(x)174。(A∧216。E(2)216。B)174。E，216。R))∨(P∧Q∧R)219。P∧Q∧216。Q∧R)∨(216。P∧216。R)）∨(P∧Q∧R)219。(P∨(Q∧R))∨(P∧Q∧R))219。(P∧Q∧R)的主析取范式和主合取范式（10分）。216。$x(216。B(x))219。(216。(216。Q∧R)∨((Q∨P)∧R)219。Q∧R))∨(Q∧R)∨(P∧R)219。B, C→D}蘊(yùn)涵A→：A－(A∩B)= A∩~(A∩B)＝A∩(~A∪~B)＝(A∩~A)∪(A∩~B)＝198。C→216。A∨B, 216。R→P(3)P→Q(4)216。 0235。234。00235。P∧Q∧R)∨(P∧Q∧R)＝m6∨m3∨m7 ＝229。R)∨(P∧Q∧R)∨(216。P∧Q∧R)＝m6∨m7∨m3 ＝229。P(x)∧216。xP(x)∧216。R)∨(P∧Q∧R)∨(P∧Q∧216。R)∨(P∧Q∧R)∨(216。Q)∨(Q∧P)∨(Q∧R)=(P∧216。P→R))= 216。G(x))前提引入（4）216。216。s218。G(x))217。（3）最小元=1 極小元=1 極大元=5 00100111114234。234。(P(y)217。G(x,s))174。r)=m011218。r)218。216。r)218。(p217。(p217。4.(本題10分)A, B為兩個(gè)任意集合，求證：A－(A∩B)=(A∪B)－：15BADBB 610 BBABB1.{，} ，2 環(huán) 三．=216。,B為任意集合，證明：(AB)C = A(B∪C).3.(本題10分)利用形式演繹法證明：{216。P→R)), 求G的主析取范式。P(x))，$x(M(x)218。q，p174。四、應(yīng)用題(本大題共2小題，每小題5分，共10分)用命題公式將下列命題符號(hào)化： 2和5是偶數(shù)，當(dāng)且僅當(dāng)52。(yP(y)217。(p217。設(shè)D是有向圖，若D的基圖是連通圖，則稱D是_________________圖既不含________________也不含____________________的無向圖稱為簡單圖。設(shè)是一個(gè)代數(shù)系統(tǒng)，o是S上的二元運(yùn)算，若存在q206。在代數(shù)系統(tǒng)（Q是有理數(shù)集，“+”是有理數(shù)加法）中，單位元是______，2的逆元是___________。A、結(jié)合律B、交換律C、分配律D、冪等律設(shè)Z是整數(shù)集，“—”是整數(shù)減法，則下列說法正確的是（）。是群B、是群184。A、f B、{f} C、{a} D、{{a}，f，a}設(shè)關(guān)系F={，}，G={，}則 FoG=（）。A、{，}B、{，} C、{，}D、{，}設(shè)集合H={1，2，3，4}，則H上的關(guān)系R={。 是半群D、是獨(dú)異點(diǎn)下面關(guān)系中，函數(shù)關(guān)系是（）。A、不是代數(shù)系統(tǒng)B、的單位元是0C、是代數(shù)系統(tǒng)D、的單位元是1設(shè)L是無向圖G中的一條通路，L中的頂點(diǎn)各不相同，則L是一條（）。設(shè)集合M={1，2，3，5}，則M的冪集P（M）包含___________個(gè)元素。S，對任意x206。三、計(jì)算題(本大題共3小題，每小題10分，共30分)用等值演算法求公式A=(p218。r)的主析取范式。$zH(y，z))的前束范式。用謂詞公式將下列命題符號(hào)化：每個(gè)計(jì)算機(jī)專業(yè)的學(xué)生都要學(xué)《編譯原理》，但有些計(jì)算機(jī)專業(yè)的學(xué)生不學(xué)《經(jīng)濟(jì)學(xué)》。216。G(x))，x(216。7.(9分)設(shè)一階邏輯公式：G =(xP(x)∨$yQ(y))→xR(x)， = {a, b, c, d}.R是A上的二元關(guān)系, R = {(a,b),(b,a),(b,c),(c,d)},(1)求出r(R), s(R), t(R)；(2)畫出r(R), s(R), t(R)：(1)G =(P∧Q)∨(216。A∨B, 216。(p218。r)=(216。r)1.=(216。(216。r)218。(p217。m010218。yz(P(y)217。H(y,z))3.(1)R={1,1,2,2,3,3,4,4,5,5,1,2,1,3,1,4,1,5,2,4}233。2(2)MR=234。234。00010四；令q表示5是偶數(shù)；r表示52；(p217。$x(S(x)217。q前提引入（3）q218。q前提引入（6）216。G(x)（5）M(x)AI規(guī)則2,4析取三段論（6）x(M(x)174。(216。Q∧R)∨(P∧216。P∧Q∧R)=(P∧216。R)∨(216。$yQ(y))∨xR(x)=($x216。Q(y))∨R(z))9.(1)r(R)＝R∪IA＝{(a,b),(b,a),(b,c),(c,d),(a,a),(b,b),(c,c),(d,d)}, s(R)＝R∪R1＝{(a,b),(b,a),(b,c),(c,b)(c,d),(d,c)}, －t(R)＝R∪R2∪R3∪R4＝{(a,a),(a,b),(a,c),(a,d),(b,a),(b,b),(b,c),(b,d),(c,d)}；(2)關(guān)系圖: abr(R)dcabs(R)dabt(R)dc c＝(P∧Q)∨(216。(3, 6, 7)H =(P∨(Q∧R))∧(Q∨(216。P∧Q∧R)∨(P∧Q∧R)∨(216。(3, 6, 7)G,H的主析取范式相同，所以G = .(1)MR=234。0000011000249。00100001000249。R→Q(5)216。C→216。B(5)B→C(6)CQ(3)(5)P(7)C→D(8)D Q(6)(7)D(1)(8)(9)A→D所以 {216?！?A∩~B)＝(A∩~B)＝A－B 而(A∪B)－B =(A∪B)∩~B =(A∩~B)∪(B∩~B)=(A∩~B)∪198。R 證明: 左端219。((216。(P∨Q)∧R)∨((Q∨P)∧R)219。(P∨Q)∨(P∨Q))∧R 219。 xA(x)174。A(x)∨B(x))219。xA(x)∨$xB(x)219。證明：(P∨(Q∧R))174。（216。(216。R))∨(P∧Q∧R)219。P∧216。R))∨(216。m0∨m1∨m2∨m7 219。E174。(R∨S)222。E174。B)T(1)(2)，I(4)(A∧216。Q(y)∧R(x))，$xP(x)222。而6個(gè)會(huì)打網(wǎng)球的人都會(huì)打另外一種球，求不會(huì)打這三種球的人數(shù)（10分）?！?=|（A∪C）∩B|=|（A∩B）∪（B∩C）|=|（A∩B）|+|（B∩C）||A∩B∩C|=|（A∩B）|+52，∴|（A∩B）|=3。證明：∵x206。（B∪C）219。C）219。 A∧x207。（AC）219。N∧y=x+1}。N∧y=x+1} S*R={| x，y206。y(mod m)}是等價(jià)關(guān)系。x(mod m)，即xRx。3）x，y，z∈I，若xRy，yRz，則（xy）/m=u∈I，（yz）/m=v∈I，于是（xz）/m=（xy+yz）/m=u+v ∈I，因此xRz。因?yàn)椤蔲g219。∈g）219。(216。P∧216。T 證明: 左端219。((P∨Q)∧(P∨R))(分配律)219。Q(y))219。Q(y))219。P(x)∨yQ(y))219。$xP(x)∨yQ(y)219。Q)174。Q)174。(216。216。P∧216。P∨P∨216。(P∨216。(Q174。S 證明：(1)R(2)216。S(6)Q(7)S(8)R174。$yC(y)。$yC(y))P(4)x(B(x)174。C(c)T(5)(6)，I(8)xA(x)174。解 設(shè)P：今天天氣好，Q：考試準(zhǔn)時(shí)進(jìn)行，A(e)：e提前進(jìn)入考場，個(gè)體域：考生 的集合，則命題可符號(hào)化為：216。174。$x216。xA(x)T(1)，E(3)xA(x)174。xA(x))T(4)，E(6)Q174。 x206。 A∧（x206。 A∧x206。 x206。（A∩B）∪（A∩C）∴A∩（B∪C）=（A∩B）∪（A∩C）六、A={ x1,x2,x3 }，B={ y1,y2}，R={,}，求其關(guān)系矩陣及關(guān)系圖（10分）。關(guān)系R滿足：，∈R219。對任意的、∈AB，若R，則∈R1且∈R2。由∈R∈R1及R1的傳遞性得∈R1，由∈R∈R2及R2的傳遞性得∈R1。B，g：B174。從而f、g、h均為雙射。((Q174。R)174。(P∨Q∨R)219。P∧(216。P∧216。(216。1∨((216。m0∨m1∨m2∨m3∨m4∨m5∨m6∨m7 該式為重言式，全部賦值都是成真賦值。(A∧(P171。(P∨Q∨C))219。((216。A∨P∨Q)∨C)219。A)∧(216。P∨216。C 219。Q∨216。C 219。C 219。C 219。C 219。C 219。解：x$y（x+y=4）219。0∧1219。P(B)，有x205。P(A∩B)，由于上述過程可逆，故P(A)∩P(B)=P(A∩B)六、（10分）已知A={1，2，3，4，5}和R={，}，求r(R)、s(R)和t(R)。解：1），∈RR，若f()=f()，即=，則x1+y1=x2+y2且x1y1=x2y2得x1=x2，y1=y2從而f是單射。2）a，b，c∈G，（aDb）Dc=（a*u*b）*u*c=a*u*（b*u*c）=aD（bDc），運(yùn)算是可結(jié)合的。九、（10分）已知：D=，V={1，2，3，4，5}，E={，}，求D的鄰接距陣A和可達(dá)距陣P。P∧(216。Q)∨(216。((P∨Q)∧(P∨(Q∧R)))∨216。((P∨Q)∧(P∨R))∨216。x(P(x)∧Q(x))證明：x(P(x)174。x((216。x(P(x)∧Q(x))二、求命題公式(216。Q)的主析取范式和主合取范式（10分）解：(216。Q)219。Q)∨(P∨216。Q)219。Q)219。Q∨P∨216。M1219。R∨P)∧Q222。(Q174。P(x)222。證明：把邊長為1的正方形分成四個(gè)全等的小正方形，則至少有一個(gè)小正方形內(nèi)有三個(gè)點(diǎn)，它們組成的三角形（可能是退化的）面積不超過小正方形的一半，即1/8。 A∧x206。B∨x206。B）∨（x206。（A∩B）∨x206。證明：a∈A必有i使得a∈Ai，由定義知aRa，故R自反?？傊甊是A上的等價(jià)關(guān)系。對任意的x∈A，若存在y1,y2∈B，使得∈f且∈f,則有∈f且∈f。八、設(shè)是群，和是的子群，證明：若A∪B＝G，則A＝G或B＝G（10分）。B，b207。B，即A∪B＝B，得B＝G，矛盾。A，從而a *(a*b)＝b 206。B，綜合有a*b207。證明 設(shè)無向圖G是不連通的，其k個(gè)連通分支為GG?、Gk。離散數(shù)學(xué)試題（B卷答案5）一、（10分）求命題公式216。P174。216。（216。P174。R)174。P∧216。(P∧Q)∨(216。R)∧（Q∨216。R)∧(P∨216。P∨Q∨216。G（x）：x要死的。G（a）證明：（1）x(F(x)174。 x206。 A∧（x206。 A∧x206。 x206。（A∩B）∪（A∩C）∴A∩（B∪C）=（A∩B）∪（A∩C）四、（10分）已知R和S是非空集合A上的等價(jià)關(guān)系，試證：1）R∩S是A上的等價(jià)關(guān)系；2）對a∈A，[a]R∩S=[a]R∩[a]S。總之R∩S是等價(jià)關(guān)系。 x∈[a]R∧x∈[a]S219。BD且∈AC，h()＝。2）再證h是單射。H，則有a*b206。220。解：設(shè)G的每個(gè)結(jié)點(diǎn)的度數(shù)都大于等于6，則2|E|=Sd(v)≥6|V|，即|E|≥3|V|，與簡單無向平面圖的|E|≤3|V|6矛盾，所以G至少有一個(gè)結(jié)點(diǎn)的度數(shù)小于等于5。Q)174。Q)174。P∨216。Q)219。Q)∨(P∧216。Q)∨(216。P∨216。Q)為可滿足式。(Q∨216。(P∨Q))∨(P∧216。(P∨Q∨P)∧(P∨Q∨216。R))∧(P∨Q∨R)219。m2∨m3∨m4∨m5∨m6∨m7所以，公式(P175。R))為可滿足式。解：論域：所有人的集合。Q(x))P(4)S(a)174。1，{1}}，B＝{0，{0}}，求P(A)、P(B)－{0}、P(B)197。}，{1}，{{1}}，{198。{0}，{{0}}，{0，{0}}－{0}＝{198。{0，{0}}＝{198。(4)若R和S是傳遞的，則R*S也是傳遞的。對任意的a∈A，因?yàn)镽和S是自反的，則∈R，∈S，于是∈R*S，故R*S也是自反的。例如，令A(yù)＝{1，2，3}，R＝{，}，S＝{，}，則R和S是對稱的，但R*S＝{，}不是對稱的。對任意的a∈A，因?yàn)镽和S是自反的，則∈R，∈S，于是∈R∩S，所以R∩S是自反的。由于在Y中任選m個(gè)元素的任一全排列都形成X到mY的不同的單射，故不同的單射有Cnm!＝n(n－1)(n―m―1)個(gè)。七、（10分）若是群，則對于任意的a、b∈G，必有惟一的x∈G使得a*x＝b。－若x162。＝a1*(a*x162。證明：對任意f∈F，d(f)＝3。若存在f∈F，使得d(f)＞3，則3|F|＜2|E|＝24，于是|F|＜8，與|F|＝8矛盾。(1)寫出F在全功能聯(lián)結(jié)詞組{173。在全功能聯(lián)結(jié)詞組{173。(A∧A)219。216。C)219。C)A∨B219。B)219。B))219。B)所以F219。C))∨((B173。(((A173。((A173。(((B173。((B173。(A∧C)∨(B∧C)219。(A∧B∧C)∨(A∧216。M0∧M1∧M2∧M4∧M6主合取范式二、（10分）判斷下列公式是否是永真式？(1)($xA(x)174。(2)(xA(x)174。解(1)($xA(x)174。(216。216。($xA(x)∧216。A(x)∨$xB(x))∧(216。A(x))∨$xB(x)219。B(x))為永真式。B(1)為假，所以x(A(x)174。B(x))為假。若|X|＝n，問(1)偏序集是否有最大元？(2)偏序集是否有最小元？(3)偏序集中極大元和極小元的一般形式是什么？并說明理由。因此的極小元就是X的所有單元集，即{x}，x∈X；而極大元恰好是比X少一個(gè)元素，即X－{x}，x∈X。(2)若fog是單射，則g是單射。因此，f是滿射。證明設(shè)是一個(gè)有幺元且滿足消去律的有限半群，要證是群，只需證明G的任一元素a可逆。由消去率得am＝e。七、（20分）有向圖G如圖所示，試求：(1)求G的鄰接矩陣A。解(1)求G的鄰接矩陣為：230。0231。247。100247。231。0232。247。02111247。02011247。230。231。231。232。 23247。所以v1到v4