【文章內(nèi)容簡(jiǎn)介】 5 6(D)下午有會(huì)嗎？ 設(shè)I是如下一個(gè)解釋：D＝{a,b}, 則在解釋I下取真值為1的公式是().(A)xyP(x,y)(B)xyP(x,y)(C)xP(x,x)(D)xyP(x,y).，能畫出圖的是().(A)(1,2,2,3,4,5)(B)(1,2,3,4,5,5)(C)(1,1,1,2,3)(D)(2,3,3,4,5,6).、H是一階邏輯公式，P是一個(gè)謂詞，G＝xP(x), H＝xP(x),則一階邏輯公式G249。H是().(A)恒真的(B)恒假的(C)可滿足的(D)＝249。(P249。Q)，H＝P249。(Q249。249。P)，則G與H的關(guān)系是()。(A)G249。H(B)H249。G(C)G＝H(D) 設(shè)A, B為集合，當(dāng)()時(shí)A－B＝B.(A)A＝B(B)A249。B(C)B249。A(D)A＝B＝ = {1,2,3,4}, A上的關(guān)系R＝{(1,1),(2,3),(2,4),(3,4)}, 則R具有()。(A)自反性(B)傳遞性(C)對(duì)稱性(D)以上答案都不對(duì)下列關(guān)于集合的表示中正確的為()。(A){a}249。{a,b,c}(B){a}249。{a,b,c}(C)249。249。{a,b,c}(D){a,b}249。{a,b,c} 12 命題xG(x)取真值1的充分必要條件是().(A)對(duì)任意x，G(x)都取真值1.(B)有一個(gè)x0，使G(x0)取真值1.(C)有某些x，使G(x0)取真值1.(D)，有5個(gè)頂點(diǎn)，6個(gè)面，則G的邊數(shù)是().(A)9條(B)5條(C)6條(D)，則從G中刪去()條邊可以得到樹.(A)6(B)5(C)10(D)，則G的頂點(diǎn)數(shù)與邊數(shù)分別為().(A)4, 5(B)5, 6(C)4, 10(D)5, 、計(jì)算證明題＝{1, 2, 3, 4, 6, 8, 9, 12}，R為整除關(guān)系。(1)畫出半序集(A,R)的哈斯圖；(2)寫出A的子集B = {3,6,9,12}的上界，下界，最小上界，最大下界；(3)寫出A的最大元，最小元，極大元，極小元。＝{1, 2, 3, 4}，A上的關(guān)系R＝{(x,y)| x, y249。A 且 x 249。 y}, 求(1)畫出R的關(guān)系圖；(2)，249。,249。,249。是R上的三個(gè)映射，249。(x)= x+3, 249。(x)= 2x, 249。(x)＝ x/4,試求復(fù)合映射249。?249。，249。?249。, 249。?249。, 249。?249。，249。?249。?：D = {2, 3}, abf(2)f(3)P(2, 2)P(2, 3)P(3, 2)P(3, 3)32320011試求(1)P(a, f(a))∧P(b, f(b))。(2)xy P(y, x).＝{1, 2, 4, 6, 8, 12}，R為A上整除關(guān)系。(1)畫出半序集(A,R)的哈斯圖；(2)寫出A的最大元，最小元，極大元，極小元；(3)寫出A的子集B = {4, 6, 8, 12}的上界，下界，最小上界， = 249。(P→Q)∨(Q∧(249。P→R)), 求G的主析取范式。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)∨(249。P∧Q∧R)(2)H =(P∨(Q∧R))∧(Q∨(249。P∧R))＝{a, b, c, d}上的關(guān)系，其中R＝{(a, a),(a, c),(b, c),(c, d)}, S＝{(a, b),(b, c),(b, d),(d, d)}.(1)試寫出R和S的關(guān)系矩陣；(2)計(jì)算R?S, R∪S, R－1, S－1?R－、證明題：{P→Q, R→S, P∨R}蘊(yùn)涵Q∨S。,B為任意集合，證明：(AB)C = A(B∪C).3.(本題10分)利用形式演繹法證明：{249。A∨B, 249。C→249。B, C→D}蘊(yùn)涵A→D。4.(本題10分)A, B為兩個(gè)任意集合，求證：A－(A∩B)=(A∪B)－一、填空題1.{3}。{{3},{1,3},{2,3},{1,2,3}}.2..= {(a,1),(b,1)}, 249。2= {(a,2),(b,2)},249。3= {(a,1),(b,2)}, 249。4= {(a,2),(b,1)}。249。3, .(P∧249。Q∧R)., .{4}, {1, 2, 3, 4}, {1, 2}.；對(duì)稱性；.(1, 0, 0),(1, 0, 1),(1, 1, 0).9.{(1,3),(2,2),(3,1)}。{(2,4),(3,3),(4,2)}。{(2,2),(3,3)}..{x |1≤x 0, x249。R}。{x | 1 x 2, x249。R}。{x | 0≤x≤1, 。.{(2, 2),(2, 4),(2, 6),(3, 3),(3, 6),(4, 4),(5, 5),(6, 6)}.(249。P(x)∨Q(x))..(R(a)∧R(b))→(S(a)∨S(b)).17.{(1, 3),(2, 2)}。{(1, 1),(1, 2),(1, 3)}.二、選擇題三、計(jì)算證明題1.(1)(2)B無上界，也無最小上界。下界1, 3。最大下界是3.(3)A無最大元，最小元是1，極大元8, 12, 90+。 = {(1,1),(2,1),(2,2),(3,1),(3,2),(3,3),(4,1),(4,2),(4,3),(4,4)}.(1)(2)3.(1)249。?249。＝249。(249。(x))＝249。(x)+3＝2x+3＝2x+3.(2)249。?249。＝249。(249。(x))＝249。(x)+3＝(x+3)+3＝x+6,(3)249。?249。＝249。(249。(x))＝249。(x)+3＝x/4+3,(4)249。?249。＝249。(249。(x))＝249。(x)/4＝2x/4 = x/2，(5)249。?249。?249。＝249。?(249。?249。)＝249。?249。+3＝2x/4+3＝x/2+.(1)P(a, f(a))∧P(b, f(b))= P(3, f(3))∧P(2, f(2))= P(3, 2)∧P(2, 3)= 1∧0 = 0.(2)xy P(y, x)= x(P(2, x)∨P(3, x))R}.6 =(P(2, 2)∨P(3, 2))∧(P(2, 3)∨P(3, 3))=(0∨1)∧(0∨1)= 1∧1 = .(1)(2)無最大元，最小元1，極大元8, 12。極小元是1.(3)B無上界，無最小上界。下界1, 2。 = 249。(P→Q)∨(Q∧(249。P→R))= 249。(249。P∨Q)∨(Q∧(P∨R))=(P∧249。Q)∨(Q∧(P∨R))=(P∧249。Q)∨(Q∧P)∨(Q∧R)=(P∧249。Q∧R)∨(P∧249。Q∧249。R)∨(P∧Q∧R)∨(P∧Q∧249。R)∨(P∧Q∧R)∨(249。=(P∧249。Q∧R)∨(P∧249。Q∧249。R)∨(P∧Q∧R)∨(P∧Q∧249。R)∨(249。P∧Q∧R)= m3∨m4∨m5∨m6∨m7 = 249。(3, 4, 5, 6, 7). =(xP(x)∨yQ(y))→xR(x)= 249。(xP(x)∨yQ(y))∨xR(x)=(249。xP(x)∧249。yQ(y))∨xR(x)=(x249。P(x)∧y249。Q(y))∨zR(z)= xyz((249。P(x)∧249。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∪R－1＝{(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)系圖:＝(P∧Q)∨(249。P∧Q∧R)＝(P∧Q∧249。R)∨(P∧Q∧R)∨(249。P∧Q∧R)＝m6∨m7∨m3 ＝249。(3, 6, 7)H =(P∨(Q∧R))∧(Q∨(249。P∧R))＝(P∧Q)∨(Q∧R))∨(249。P∧Q∧R)＝(P∧Q∧249。R)∨(P∧Q∧R)∨(249。P∧Q∧R)∨(P∧Q∧R)∨(249。P∧Q∧R)＝(P∧Q∧249。R)∨(249。P∧Q∧R)∨(P∧Q∧R)＝m6∨m3∨m7 ＝249。(3, 6, 7)G,H的主析取范式相同，所以G = .(1)P∧Q∧R)7(2)R?S＝{(a, b),(c, d)}，R∪S＝{(a, a),(a, b),(a, c),(b, c),(b, d),(c, d),(d, d)}, R－1＝{(a, a),(c, a),(c, b),(d, c)}, S－1?R－1＝{(b, a),(d, c)}.四 證明題：{P→Q, R→S, P∨R}蘊(yùn)涵Q∨S(1)P∨RP(2)249。R→PQ(1)(3)P→QP(4)249。R→(2)(3)(5)249。Q→RQ(4)(6)R→SP(7)249。Q→SQ(5)(6)(8)Q∨SQ(7)：(AB)C =(A∩~B)∩~C = A∩(~B∩~C)= A∩~(B∪C)= A(B∪C)：{249。A∨B, 249。C→249。B, C→D}蘊(yùn)涵A→D(1)AD(附加)(2)249。A∨BP(3)BQ(1)(2)(4)249。C→249。BP(5)B→CQ(4)(6)CQ(3)(5)(7)C→DP(8)DQ(6)(7)(9)A→DD(1)(8)所以 {249。A∨B, 249。C→249。B, C→D}蘊(yùn)涵A→：A－(A∩B)= A∩~(A∩B)＝A∩(~A∪~B)＝(A∩~A)∪(A∩~B)＝249?！?A∩~B)＝(A∩~B)＝A－B而(A∪B)－B =(A∪B)∩~B=(A∩~B)∪(B∩~B)=(A∩~B)∪249。= A－B所以：A－(A∩B)=(A∪B)－ 離散數(shù)學(xué)試題(本題包括16個(gè)空格，每個(gè)空格3分，共48分。每道小題都可能有一個(gè)以上的正確選項(xiàng)，須選出所有的正確選項(xiàng)，不答不得分，多選、少選或選錯(cuò)都將按比例扣分。)1．命題公式(P∧(P→Q))→Q是_____式。(1)重言(2)矛盾(3)可滿足(4)非永真的可滿足 2．給定解釋I=(D,)=(整數(shù)集，{f(x,y):f(x,y)=xy；g(x,y):g(x,y)=x+y；P(x,y):x(1)100(2)99(3)2048(4)1024(5)512 4．集合Ａ={x|x是整數(shù)，(1)14(2)15(3)16(4)17(5)8(6)49(7)512 7．S={1,2,3,4,5,6,7,8,9,10,11,12}，≤是S上的整除關(guān)系。S的子集Ｂ＝{2,4,6｝，則在(S，≤)中，Ｂ的最大元是_____；Ｂ的最小元是_____；Ｂ的上確界是_____；Ｂ的下確界是_____。(1)不存在的(2)36(3)24(4)12(5)6(6)1(7)2 8．設(shè)有有限布爾代數(shù)(B,+,*,’,0,1)，則 =_____能成立。(1)1(2)2(3)3(4)4(5)5(6)8(7)9 9．G={0,1,2,?,n}，n∈N，定義 為模n加法，即x y=(x+y)mod n，則代數(shù)系統(tǒng)(G，)_____。(1)是半群但不是群(2)是無限群(3)是循環(huán)群(4)是變換群(5)是交換群10．n個(gè)結(jié)點(diǎn)、m條邊的無向連通圖是樹當(dāng)且僅當(dāng)m=_____。(1)n+1(2)n(3)n1(4)2n1 二請(qǐng)給出命題公式 的主析取范式。(10分)三假設(shè)下列陳述都是正確的：(1)學(xué)生會(huì)的每個(gè)成員都是學(xué)生并且是班干部；(2)有些成員是女生。問是否有成員是女班干部？請(qǐng)將上述陳述和你的結(jié)論符號(hào)化，并給出你的結(jié)論的形式證明。(10分)四設(shè)R和S是集合Ｘ上的等價(jià)關(guān)系,則S∩R必是等價(jià)關(guān)系。(10分)參考答案一、3 ；4；2；2 ；7；4；7 、6 、4 二、分析：求給定命題公式的主析取范式與主合取范式，通常有兩種方法——列表法和等值演算法。(1)列表法列出給定公式的真值表，其真值為真的賦值所對(duì)應(yīng)的極小項(xiàng)的析取，即為此公式的主析取范式。(2)等值演算法 在等值演算中，首先將公式中的蘊(yùn)涵聯(lián)結(jié)詞和等價(jià)聯(lián)結(jié)詞化去，使整個(gè)公式化歸為析取范式，然后刪去其中所有的永假合取項(xiàng)，再將析取式中重復(fù)出現(xiàn)的合取項(xiàng)合并和合并合取項(xiàng)中相同的命題變?cè)?，最后?duì)合取項(xiàng)添加沒有出現(xiàn)的命題變?cè)褪呛先?,經(jīng)過化簡(jiǎn)整理，即可得到主析取范式。解：（1）列表法 設(shè)000011111 001010100 010010100 011110100 100001000 101000010 110000010 111100111 根據(jù)真值表中 真值為1的賦值所對(duì)應(yīng)的極小項(xiàng)的析取，即為 的主析取范式。由表可知（2）等值演算三、解：有成員是女班干部。將命題符號(hào)化，個(gè)體域?yàn)槿倐€(gè)體域。：x是學(xué)生會(huì)的成員。：x是學(xué)生 ：x是班干部 ：x是女性 前提：，結(jié)論： 證明： ① P ② ES①，e為額外變?cè)?③ P ④ T③ ⑤ T② ⑥ T② ⑦ T④⑤⑥ ⑧ T② ⑨ T⑤⑦⑧ ⑩ EG⑨離散數(shù)學(xué)試題及答案1離散數(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去工作。則根據(jù)題意應(yīng)有：A249。C249。D，249。(B∧C)，C249。249。D必須同時(shí)成立。因此(A249。C249。D)∧249。(B∧C)∧(C249。249。D)249。(249。A∨(C∧249。 D)∨(249。C∧D))∧(249。B∨249。C)∧(249。C∨249。D)249。(249。A∨(C∧249。 D)∨(249。C∧D))∧((249。B∧249。C)∨(249。B∧249。D)∨249。C∨(249。C