【正文】 (3)顯然當|m|＝|n|時，才存在雙射。(2)顯然當|m|≤|n|時，存在單射。五、（15分）令X＝{x1，x2，…，xm}，Y＝{y1，y2，…，yn}。(5)成立。(4)不成立。(3)不成立。(2)不成立。解(1)成立。(5)若R和S是自反的，則R∩S是自反的。(3)若R和S是對稱的，則R*S也是對稱的。0，{{0}}，{0，{0}}四、（15分）設(shè)R和S是集合A上的任意關(guān)系，判斷下列命題是否成立？(1)若R和S是自反的，則R*S也是自反的。{0}，{{0}}，{0，{0}}197。{0}，{{0}}，{0，{0}} P(B)197。1，{1}}} P(B)－{0}＝{198。1}，{198。{198。B。C(a)T(9)，Us(11)C(a)T(8)(10)，I(12)$xC(x)T(11)，EG(13)$x(C(x)∨F(x))T(12)，I三、（10分）設(shè)A＝{198。Q(a)T(1)，US(5)S(a)T(2)，I(6)Q(a)T(4)(5)，I(7)H(a)T(2)，I(8)Q(a)∧H(a)T(6)(7)，I(9)x(Q(x)∧H(x)174。C(x))，$x(S(x)∧H(x))$x(C(x)∨F(x))下面給出證明：(1)$x(S(x)∧H(x))P(2)S(a)∧H(a)T(1)，ES(3)x(S(x)174。H(x)：x是身體健康的；S(x)：x是事業(yè)獲得成功的人；F(x)：x是事業(yè)半途而廢的人；則推理化形式為：x(S(x)174。所以，存在著事業(yè)獲得成功的人或事業(yè)半途而廢的人。二、（15分）在謂詞邏輯中構(gòu)造下面推理的證明：每個科學家都是勤奮的，每個勤奮又身體健康的人在事業(yè)中都會獲得成功。(Q∨216。Q)174。M0∧M1219。(P∨Q∨R)∧(P∨Q∨216。(P∨Q∨(R∧216。Q)∧(P∨Q∨R)219。Q∧R))219。Q∧R))219。(216。R))219。(P∧216。（2）因為(P175。216。Q)174。M0所以，公式(216。P∧Q)219。(P∧Q)∨(P∧216。Q)∨(216。P∨216。216。216。Q)174。R))解：（1）因為(216。(P∧216。Q)(2)(P175。(P171。P∨216。mm1m1，所以n≤m2/4。因為(m2m1)2179。九、（10分）給定二部圖G＝，且|V1∪V2|＝m，|E|＝n，證明n≤m/4。又因為H是G非空子集，所以*在H上滿足結(jié)合律。任取a∈H，由e、a∈H得a－1＝e*a－1∈H。充分性：由H非空，必存在a∈H。對任意的a、b∈H有a*b－1∈H。248。0247。=M(R)，所以R是傳遞的。247。1232。1231。231。(3)對于R的關(guān)系矩陣，由于對角線上不全為1，R不是自反的；由于對角線上存在非0元，R不是反自反的；由于矩陣不對稱，R不是對稱的；經(jīng)過計算可得 230。0247。 0247。247。1232。1231。231。解(1)R的關(guān)系圖如圖所示：(2)R的關(guān)系矩陣為：230。(2)寫出R的關(guān)系矩陣。x+y+xy2x+y(xy)2(4)fof()＝f(f())＝f()＝＝ fof()＝f(f())＝f()＝＝。(2)對任意的∈RR，令x＝uw2u+w2－1，y＝uw2，則f()＝u+w2＋uw2，u+w2－＝，所以f是滿射。(4)求復合函數(shù)f－1of和fof。(2)證明f是滿射。RR，f定義為：f()＝。由數(shù)學歸納法知，對任意的正整數(shù)n，Rn＝R。R*R。R。下面由R是自反和傳遞的推導出R*R＝R即可。設(shè)n＝k時，Rk＝R。五、（10分）若R是集合A上的自反和傳遞關(guān)系，則對任意的正整數(shù)n，R＝R。B＝A197。B。C。C，但x207。B222。A∩B，而x∈B222。C；當x207。x∈A∩C222。A197。B222。x207。B＝A197。(3)成立。(2)不一定。解(1)不一定。B＝A197。(2)若A∩B＝A∩C，則B＝C。A(c)T(6)(8)，I(10)$x216。216。216。C(x)T(1)，E(3)216。A(x)下面給出證明：(1)216。B(x))，x(B(x)∨C(x))，216。A(x)：x喜歡步行；B(x)：x喜歡坐汽車；C(x)：x喜歡騎自行車；則推理化形式為：x(A(x)174。有的人不喜歡騎自行車，因而有的人不喜歡步行。T)219。(T174。((T∧T)∨(T∧T)))∧(T174。((Q(1)∧R(2，1))∨(Q(2)∧R(2，2))))219。(P(1)174。x(P(x)174。F 若P(1)＝P(2)＝T，Q(1)＝Q(2)＝T，R(1，1)＝R(1，2)＝R(2，1)＝R(2，2)＝T，則 x(P(x)174。F)∧(T174。((F∧F)∨(F∧F)))219。(T174。((Q(1)∧R(1，1))∨(Q(2)∧R(1，2))))∧(P(2)174。((Q(1)∧R(x，1))∨(Q(2)∧R(x，2))))219。$y(Q(y)∧R(x，y)))219。解：設(shè)論域為{1，2}。二、（10分）分別找出使公式x(P(x)174。M2∧M4∧M6 219。P∨216。Q∨R)∧(P∨216。P∨Q∨R)∧(216。Q∨R)219。Q)∨R)∧((P∧216。(216。P∧216。(P∨Q)∨R219。R219。R)。R)222。T 所以，(P174。Q∨Q∨216。(P∨Q∨216。Q)∨(Q∨216。P∨R))219。P∨R)∧(216。(P∧216。R)∨216。(P∧216。Q∨R))∨(216。((216。R)219。R))174。解：（1）因為((P174。R)（2）求(P∨Q)174。R)222。第二篇：離散數(shù)學離散數(shù)學試題（A卷答案）一、（10分）（1）證明(P174。g是A到C的函數(shù)，則可寫為 f。g。g是A到C的函數(shù)。所以A中的每個元素對應C中惟一的元素。因為g：A→B是函數(shù)，則t1＝t2。g＝A。根據(jù)復合關(guān)系的定義，由∈g和∈f得∈g*f，即∈。證明(1)對任意的x∈A，因為g：A→B是函數(shù)，則存在y∈B使∈g。七、設(shè)函數(shù)g：A→B，f：B→C，則：(1)f。所以f－1 是單射。對任意的yy2∈B，若f－1(y1)＝f－1(y2)＝x，則f(x)＝y(tǒng)1，f(x)＝y(tǒng)2。下證f－1是雙射。五、設(shè)R和S是集合A＝{a, b, c, d}上的關(guān)系，其中R＝{(a, a),(a, c),(b, c),(c, d)}，S＝{(a, b),(b, c),(b, d),(d, d)}.計算R?S, R∪S, R－ 1, S－ 1?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)}.六、若f：A→B是雙射，則f－1 ：B→A是雙射。2)若x≤y，則f(x)≤f(y)且g(x)≤ g（y），f○g（x）＝f(g(x))≤f(g(y))＝f○g(y)所以f○g是單凋遞增。設(shè)f和g是在R上單調(diào)遞增，證明1)若(f十g)(x)=f(x)+g(x)，則f+g是單調(diào)遞增； 2)復合函數(shù)f○g是單調(diào)遞增：3)f和g的乘積不一定是單調(diào)遞增。證明f∩g＝{| x∈dom f∧x∈dom g∧y=f（x）∧y=g（x）} ＝{| x∈dom f∩dom g∧y=f（x）=g（x）} 令h=f∩g，則dom h={ x | x∈dom f∩dom g，f（x）=g（x）}若y1 =y2，因為f是函數(shù)，故必有y1 ＝／f（x1），y2 ＝／f（x2），且x1 ≠x2，所以h=f∩g是一個函數(shù)。第一篇：離散數(shù)學例題離散數(shù)學例題一、證明對任意集合A，B，C，有 a）AB）C=A（B∪C）； b）（AB）C=（AC）B；c）（AB）C=（AC）（BC）。證明a）（AB）C=（A∩～B）∩～C =A∩（～B∩～C）=A∩～（B∩C）=AB∪C）b）（AB）C= A∩～B∩～C = A∩～C∩～B =（AC）Bc）（AC）（BC）=（A∩～C）∩～（B∩～C）=（A∩～C）∩（～B∪C）=（A∩～C∩～B）∪（A∩～C∩C）= A∩～B∩～C =（AB）C二、設(shè)命題公式G =(P→Q)∨(Q∧(P→R)), 求G的主析取范式 G =(P→Q)∨(Q∧(P→R))=(P∨Q)∨(Q∧(P∨R))=(P∧Q)∨(Q∧(P∨R))=(P∧Q)∨(Q∧P)∨(Q∧R)=(P∧Q∧R)∨(P∧Q∧∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧ R)=(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)= m3∨m4∨m5∨m6∨m7 =(3, 4, 5, 6, 7).三、假設(shè)f和g是函數(shù)，證明f∩g也是函數(shù)。因為dom h存在且y1 ≠y2 時x1 ≠x2，即 h＝{| x∈ Dom h，y=h（x）=f（x）=g（x）}四、設(shè)函數(shù)f：R→R，若x≤y＝＞f（x）≤f（y），則稱函數(shù)f是單調(diào)遞增的。證明1)因為f和g是單調(diào)遞增，若x≤y，則有f（x）≤f(y)，g(x)≤g(y)，(f+g)(x)=f(x)十g(x)≤f(y)+g（y）=(f十g)(y)所以f+g是單調(diào)遞增。3）令f(x)=g（x）=x，則f和g是單調(diào)遞增，但其積函數(shù)g*g(x)=f（x）*g（x）=x2 在R上不是單凋遞增。證明因為f：A→B是雙射，則f－1 是B到A的函數(shù)。對任意x∈A，必存在y∈B使f(x)＝y(tǒng)，從而f－1(y)＝x，所以f－1 是滿射。因為f：A→B 是函數(shù)，則y1＝y(tǒng)2。綜上可得，f－1 ：B→A是雙射。g是A到C的函數(shù)；(2)對任意的x∈A，有fg(x)＝f(g(x))。對于y∈B，因f：B→C是函數(shù)，則存在z∈C使∈f。所以Df。對任意的x∈A，若存在yy2∈C，使得、∈fg＝g*f，則存在t1使得∈g且∈f，存在t2使得∈g且∈f。又因f：B→C是函數(shù)，則y1＝y(tǒng)2。綜上可知，f。(2)對任意的x∈A，由g：A→B是函數(shù)，有∈g且g(x)∈B，又由f：B→C是函數(shù)，得∈f，于是∈g*f＝f。又因f。g(x)＝f(g(x))。Q)∧(Q174。(P174。R的主析取范式與主合取范式，并寫出其相應的成真賦值和成假賦值。Q)∧(Q174。(P174。216。P∨Q)∧(216。P∨R)219。Q)∨(Q∧216。P∨R 219。Q)∨((Q∨216。R∨216。(P∧216。P∨R)219。P∨R)∧(216。P∨R)219。Q)∧(Q174。(P174。（2）(P∨Q)174。216。(216。Q)∨R 219。P∨(Q∧216。P)∨216。(216。P∨216。Q∨R)∧(216。Q∨R)219。m0∨m1∨m3∨m5所以，其相應的成真賦值為000、000110111：成假賦值為：0100、110。$y(Q(y)∧R(x，y)))為真的解釋和為假的解釋。若P(1)＝P(2)＝T，Q(1)＝Q(2)＝F，R(1，1)＝R(1，2)＝R(2，1)＝R(2，2)＝F，則 x(P(x)174。x(P(x)174。(P(1)174。((Q(1)∧R(2，1))∨(Q(2)∧R(2，2))))219。((F∧F)∨(F∧F)))∧(T174。(T174。F)219。$y(Q(y)∧R(x，y)))219。((Q(1)∧R(x，1))∨(Q(2)∧R(x，2))))219。((Q(1)∧R(1，1))∨(Q(2)∧R(1，2))))∧(P(2)174。(T174。((T∧T)∨(T∧T)))219。T)∧(T174。T三、（10分）在謂詞邏輯中構(gòu)造下面推理的證明：每個喜歡步行的人都不喜歡做汽車，每個人或者喜歡坐汽車或者喜歡騎自行車。解論域：所有人的集合。216。xC(x)$x216。xC(x)P(2)$x216。C(c)T(2)，ES(4)x(B(x)∨C(x))P(5)B(c)∨C(c)T(4)，US(6)B(c)T(3)(5)，I(7)x(A(x)174。B(x))P(8)A(c)174。B(c)T(7)，US(9)216。A(x)T(9)，EG四、（10分）下列論斷是否正確？為什么？(1)若A∪B＝A∪C，則B＝C。(3)若A197。C，則B＝C。例如，令A＝{1}，B＝{1，2}，C＝{2}，則A∪B＝A∪C，但B＝C不成立。例如，令A＝{1}，B＝{1，2}，C＝{1，3}，則A∩B＝A∩C，但B＝C不成立。因為若A197。C，對任意的x∈B，當x∈A時，有x∈A∩B222。A197。x207。C＝(A∪C)－(A∩C)222。x∈C，所以B205。A時，有x207。x∈A∪B，所以x∈A∪B－A∩B＝A197。x∈A197。 A，于是x∈C，所以B205。同理可證，C 205。因此，當A197。C時，必有B＝C。證明 當n＝1時，結(jié)論顯然成立。當n＝k＋1時，Rk+1＝Rk*R＝R*R。由傳遞性得R*R205。另一方面，對任意的∈R，由R自反得∈R，再由關(guān)系的復合得∈R*R，從而R205。因此，R＝R*R。n六、（15分）設(shè)函數(shù)f：RR174。(1)證明f是單射。(3)求逆函數(shù)f。證明(1)對任意的x，y，x1，y1∈R，若f()＝f()，則＝，x＋y＝x1＋y1，x－y＝x1－y1，從而x＝x1，y＝y(tǒng)1，故f是單射。u+w2－1(3)f()＝。七、（15分）設(shè)X＝{1，2，3，4}，R是X上的二元關(guān)系，R＝{，}(1)畫出R的關(guān)系圖。(3)說明R是否是自反、反自反、對稱、傳遞的。1231