《離散數(shù)學(xué)》試題及詳解

?失散數(shù)學(xué)?試題及詳解?失散數(shù)學(xué)?試題及詳解PAGEPAGE14?失散數(shù)學(xué)?試題及詳解PAGE一、填空題1設(shè)會合A,B，此中A＝{1,2,3},B={1,2},那么A-B＝________{3}____________;(A)-(B)＝_____{{3},{1,3},{2,3},{1,2,3}}_______.2.2.設(shè)有限會合A,|A|=n,那么|(A×A)|=__2n23.設(shè)會合A={a,b},B={1,2},那么從A到B的全部映照是__1={(a,1),(b,1)},2={(a,2),(b,2)},={(a,1),(b,2)},={(a,2),(b,1)};_,此中雙射的是____,4._3434.命題公式G＝(PQ)∧R，那么G的主析取范式是______(P∧Q∧R)__________________.5.設(shè)G是完整二叉樹，G有7個點，此中4個葉點，那么G的總度數(shù)為___12_______，分枝點數(shù)為_______3_________.6設(shè)A、B為兩個會合,A={1,2,4},B={3,4},那么從AB＝_______{4}__________________;AB＝_____{1,2,3,4}____________;A－B＝____{1,2}_________________.3.7.設(shè)R是會合A上的等價關(guān)系，那么R所擁有的關(guān)系的三個特征是__自反性；對稱性；傳達性_______________________________.8.設(shè)命題公式G＝(P(QR))，那么使公式G為真的解說有____(1,0,0)________，____(1,0,1)_________,____(1,1,0)______________________.9.設(shè)會合A＝{1,2,3,4},A上的關(guān)系R1={(1,4),(2,3),(3,2)},R1={(2,1),(3,2),(4,3)},那么R1?R2=_{(1,3),(2,2),(3,1)}__________,R2?R1=___{(2,4),(3,3),(4,2)}_______,R12=_____{(2,2),(3,3)}__________________.10.設(shè)有限集A,B，|A|=m,|B|=n,那么||(AB)|=___2mn_____.11設(shè)

A,B,R

是三個會合，此中

R是實數(shù)集，A={x|-1

≤x≤1,x

R},B={x|0

≤x<2,x

R},那么A-B=_{x|-1

≤x<0,x

R}_______,B-A=__{x|1<x<2,x

R}_____,A∩B=

___{x|0≤x≤1,x

R}_______________________,.13.設(shè)會合A＝{2,3,4,5,6}，R是A上的整除，那么R以會合形式(列舉法)記為__{(2,2),(2,4),(2,6),(3,3),(3,6),(4,4),(5,5),(6,6)}_____________________________.6.14.設(shè)一階邏輯公式G=xP(x)xQ(x)，那么G的前束范式是__x(P(x)∨Q(x))_.15.設(shè)G是擁有8個極點的樹，那么G中增添__21_______條邊才能把G變?yōu)橥暾麍D。16.設(shè)謂詞的定義域為{a,b},將表達式xR(x)→xS(x)中量詞除去，寫成與之對應(yīng)的命題公式是____(R(a)∧R(b))→(S(a)∨S(b))_______________________.17.設(shè)會合A＝{1,2,3,4}，A上的二元關(guān)系R＝{(1,1),(1,2),(2,3)},S＝{(1,3),(2,3),(3,2)}。那么RS＝_{(1,3),(2,2)}_____________________________,R2＝___{(1,1),(1,2),(1,3)}.______________________.二、選擇題1設(shè)會合A={2,{a},3,4}，B={{a},3,4,1}，E為全集，那么以下命題正確的選項是(C)。(A){2}A(B){a}A(C){{a}}BE(D){{a},1,3,4}B.2設(shè)會合A={1,2,3},A上的關(guān)系R＝{(1,1),(2,2),(2,3),(3,2),(3,3)}，那么R不具備(D).(A)自反性(B)傳達性(C)對稱性(D)反對稱性3設(shè)半序集(A,≤)關(guān)系≤的哈斯圖以下所示，假定A的子集B={2,3,4,5},那么元素(B)。(A)下界(B)上界(C)最小上界(D)以上答案都不對以下語句中，(B)是命題。(A)請把門關(guān)上(B)地球外的星球上也有人3(C)x+5>6(D)下午有會嗎？5設(shè)I是以下一個解說：P(a,a)P(a,b)P(b,a)P(b,b)D＝{a,b},0101那么在解說I下取真值為1的公式是(D).

6為B的65421(A)xyP(x,y)(B)xyP(x,y)(C)xP(x,x)(D)xyP(x,y).6.假定供選擇答案中的數(shù)值表示一個簡單圖中各個極點的度，能畫出圖的是(C).(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).7.設(shè)G、H是一階邏輯公式，P是一個謂詞，G＝xP(x),H＝xP(x),那么一階邏輯公式GH(C).(A)恒真的(B)恒假的(C)可知足的(D)前束范式.8設(shè)命題公式G＝(PQ)，H＝P(QP)，那么G與H的關(guān)系是(A)。(A)GH(B)HG(C)G＝H(D)以上都不是.9設(shè)A,B為會合，當(D)時A－B＝B.(A)A＝B(B)AB(C)BA(D)A＝B＝.10設(shè)會合A={1,2,3,4},A上的關(guān)系R＝{(1,1),(2,3),(2,4),(3,4)},那么R擁有(B)。(A)自反性(B)傳達性(C)對稱性(D)以上答案都不對11以下對于會合的表示中正確的為(B)。(A){a}{a,b,c}(B){a}{a,b,c}(C){a,b,c}(D){a,b}{a,b,c}12命題xG(x)取真值1的充分必需條件是().對隨意x，G(x)都取真值1.(B)有一個x0，使G(x0)取真值1.有某些x，使G(x0)取真值1.(D)以上答案都不對.13.設(shè)G是連通平面圖，有5個極點，6個面，那么G的邊數(shù)是(A).(A)9條(B)5條(C)6條(D)11條.14.設(shè)G是5個極點的完整圖，那么從G中刪去(A)條邊能夠獲得樹.(A)6(B)5(C)10(D)4.0111115.設(shè)圖G的相鄰矩陣為10100，那么G的極點數(shù)與邊數(shù)分別為(D).110111010110110(A)4,5(B)5,6(C)4,10(D)5,8.三、計算證明題1.設(shè)會合A＝{1,2,3,4,6,8,9,12}，R為整除關(guān)系。畫出半序集(A,R)的哈斯圖；寫出A的子集B={3,6,9,12}的上界，下界，最小上界，最大下界；寫出A的最大元，最小元，極大元，極小元。12869423(1)1(2)B無上界，也無最小上界。下界1,3;最大下界是無最大元，最小元是1，極大元8,12,90+;極小元是1.2.設(shè)會合A＝{1,2,3,4}，A上的關(guān)系R＝{(x,y)|x,yA且xy},求畫出R的關(guān)系圖；寫出R的關(guān)系矩陣.R={(1,1),(2,1),(2,2),(3,1),(3,2),(3,3),(4,1),(4,2),(4,3),(4,4)}.(1)142310001100(2)MR110111113.設(shè)R是實數(shù)會合，,,是R上的三個映照，(x)=x+3,(x)=2x,(x)＝x/4,試求復(fù)合映照?，?,?,?，??.(1)?＝((x))＝(x)+3＝2x+3＝2x+3.(2)?＝((x))＝(x)+3＝(x+3)+3＝x+6,(3)?＝((x))＝(x)+3＝x/4+3,(4)?＝((x))＝(x)/4＝2x/4=x/2,(5)??＝?(?)＝?+3＝2x/4+3＝x/2+3.4.設(shè)I是以下一個解說：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));xyP(y,x).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)xyP(y,x)=x(P(2,x)∨P(3,x))(P(2,2)∨P(3,2))∧(P(2,3)∨P(3,3))(0∨1)∧(0∨1)1∧11.設(shè)會合A＝{1,2,4,6,8,12}，R為A上整除關(guān)系。畫出半序集(A,R)的哈斯圖；寫出A的最大元，最小元，極大元，極小元；(3)寫出A的子集B={4,6,8,12}的上界，下界，最小上界，最大下界.1)8124621無最大元，最小元1，極大元8,12;極小元是1.(3)B無上界，無最小上界。下界1,2;最大下界2.6.設(shè)命題公式G=(P→Q)∨(Q∧(P→R)),G=(P→Q)∨(Q∧(P→R))

求G的主析取范式。=(P∨Q)∨(Q∧(P∨R))(P∧Q)∨(Q∧(P∨R))(P∧Q)∨(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)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)=m3∨m4∨m5∨m6∨m7=(3,4,5,6,7).7.(9分)設(shè)一階邏輯公式：G=(xP(x)∨yQ(y))→xR(x)，把

G化成前束范式

.G=(xP(x)∨

yQ(y))→

xR(x)(xP(x)∨yQ(y))∨xR(x)=(xP(x)∧yQ(y))∨xR(x)=(xP(x)∧yQ(y))∨zR(z)=xyz((P(x)∧Q(y))∨R(z))9.設(shè)R是會合A={a,b,c,d}.R是A上的二元關(guān)系,R={(a,b),(b,a),(b,c),(c,d)},求出r(R),s(R),t(R)；畫出r(R),s(R),t(R)的關(guān)系圖.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)}；關(guān)系圖:adadadbcbcbcr(R)s(R)t(R)經(jīng)過求主析取范式判斷以下命題公式能否等價：G=(P∧Q)∨(P∧Q∧R)(2)H=(P∨(Q∧R))∧(Q∨(P∧R))G＝(P∧Q)∨(P∧Q∧R)(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)m6∨m7∨m3(3,6,7)=(P∨(Q∧R))∧(Q∨(P∧R))(P∧Q)∨(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)∨(P∧Q∧R)m6∨m3∨m7(3,6,7)G,H的主析取范式同樣，因此G=H.13.設(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的關(guān)系矩陣；計算R?S,R∪S,R－1,S－1?R－1.1010010000100011(1)MR001MS0000000000001(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)},－－S1?R1＝{(b,a),(d,c)}.四、證明題利用形式演繹法證明：{P→Q,R→S,P∨R}蘊涵Q∨S。證明：{P→Q,R→S,P∨R}蘊涵Q∨S(1)P∨RP(2)R→PQ(1)(3)P→QP(4)R→QQ(2)(3)(5)Q→RQ(4)(6)R→SP(7)Q→SQ(5)(6)(8)Q∨SQ(7)2.設(shè)A,B為隨意會合，證明：(A-B)-C=A-(B∪C).證明：(A-B)-C=(A∩~B)∩~CA∩(~B∩~C)A∩~(B∪C)A-(B∪C)3.(本題10分)利用形式演繹法證明：{A∨B,C→B,C→D}蘊涵A→D。證明：{A∨B,C→B,C→D}蘊涵A→D(1)AD(附帶)(2)A∨BP(3)BQ(1)(2)(4)C→BP(5)B→CQ(4)(6)CQ(3)(5)(7)C→DP(8)DQ(6)(7)(9)A→DD(1)(8)因此{A∨B,C→B,C→D}蘊涵A→D.(本題10分)A,B為兩個隨意會合，求證：A－(A∩B)=(A∪B)－B.證明：A－(A∩B)=A∩~(A∩B)＝A∩(~A∪~B)(A∩~A)∪(A∩~B)∪(A∩~B)(A∩~B)＝A－B(A∪B)－B(A∪B)∩~B(A∩~B)∪(B∩~B)(A∩~B)∪A－B因此：A－(A∩B)=(A∪B)－B.參照答案一、填空題1.{3};{{3},{1,3},{2,3},{1,2,3}}.2n2.7.1={(a,1),(b,1)},={(a,2),(b,2)},={(a,1),(b,2)},4={(a,2),(b,1)};3,.234(P∧Q∧R).12,3.{4},{1,2,3,4},{1,2}.自反性；對稱性；傳達性.(1,0,0),(1,0,1),(1,1,0).{(1,3),(2,2),(3,1)};{(2,4),(3,3),(4,2)};{(2,2),(3,3)}.2mn.15.{x|-1≤x<0,xR};{x|1<x<2,xR};{x|0≤x≤1,xR}.12;6.{(2,2),(2,4),(2,6),(3,3),(3,6),(4,4),(5,5),(6,6)}.18.x(P(x)∨Q(x)).21.(R(a)∧R(b))→(S(a)∨S(b)).{(1,3),(2,2)};{(1,1),(1,2),(1,3)}.二、選擇題1.C.2.D.3.B.4.B.5.D.6.C.7.C.8.A.9.D.10.B.11.B.13.A.14.A.三、計算證明題1.812(1)469231(2)B無上界，也無最小上界。下界1,3;最大下界是無最大元，最小元是1，極大元8,12,90+;極小元是1.2.R={(1,1),(2,1),(2,2),(3,1),(3,2),(3,3),(4,1),(4,2),(4,3),(4,4)}.(1)14231000(2)MR1100111011113.(1)?＝((x))＝(x)+3＝2x+3＝2x+3.(2)?＝((x))＝(x)+3＝(x+3)+3＝x+6,(3)?＝((x))＝(x)+3＝x/4+3,(4)?＝((x))＝(x)/4＝2x/4=x/2,??＝?(?)＝?+3＝2x/4+3＝x/2+3.(1)P(a,f(a))∧P(b,f(b))=P(3,f(3))∧P(2,f(2))P(3,2)∧P(2,3)1∧00.(2)xyP(y,x)=x(P(2,x)∨P(3,x))(P(2,2)∨P(3,2))∧(P(2,3)∨P(3,3))(0∨1)∧(0∨1)1∧11.5.(1)128462(2)無最大元，最小元1，極大元8,12;極小元是1.(3)B無上1界，無最小上界。下界1,2;最大下界2.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∧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)∨(P∧Q∧R)=m∨m∨m∨m∨m=(3,4,5,6,7).345677.G=(xP(x)∨yQ(y))→xR(x)(xP(x)∨yQ(y))∨xR(x)=(xP(x)∧yQ(y))∨xR(x)=(xP(x)∧yQ(y))∨zR(z)=xyz((P(x)∧Q(y))∨R(z))(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)}；關(guān)系圖:adadadbc