千里之行，始于足下。第2頁/共2頁精品文檔推薦《離散數(shù)學(xué)》試題和答案及解析一、填空題

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.設(shè)有限集合A,|A|=n,則|ρ(A×A)|=2

2n.

3.設(shè)集合A={a,b},B={1,2},則從A到B的所有映射是α1={(a,1),(b,1)},α2={(a,2),(b,2)},α3={(a,1),(b,2)},α4={(a,2),(b,1)},其中雙射的是α3,α4.

4.已知命題公式G＝?(P→Q)∧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},則從A?B＝{4};A?B＝{1,2,3,4};

A－B＝{1,2}.

7.設(shè)R是集合A上的等價關(guān)系，則R所具有的關(guān)系的三個特性是自反性,對稱性傳遞性.

8.設(shè)命題公式G＝?(P→(Q∧R))，則使公式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)},R2={(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,則||ρ(A?B)|=.

11設(shè)A,B,R是三個集合，其中R是實數(shù)集，A={x|-1≤x≤1,x∈R},B={x|0≤x6(D)下午有會嗎？5設(shè)I是如下一具解釋：D＝{a,b},

101b)

P(b,a)P(b,b)P(a,),(aaP

則在解釋I下取真值為1的公式是(D).

(A)?x?yP(x,y)(B)?x?yP(x,y)(C)?xP(x,x)(D)?x?yP(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),則一階邏輯公式G→H是(C).(A)恒確實(B)恒假的(C)可滿腳的(D)前束范式.

8設(shè)命題公式G＝?(P→Q)，H＝P→(Q→?P)，則G與H的關(guān)系是(A)。(A)G?H(B)H?G(C)G＝H(D)以上都別是.9設(shè)A,B為集合，當(dāng)(D)時A－B＝B.(A)A＝B(B)A?B(C)B?A(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的充分必要條件是(A).

(A)對任意x，G(x)都取真值1.(B)有一具x0，使G(x0)取真值1.(C)有某些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.

15.設(shè)圖G的相鄰矩陣為??????

???????

???0110110101110110010111110，則G的頂點數(shù)與邊數(shù)分不為(D).

(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)系。

(1)畫出半序集(A,R)的哈斯圖；

(2)寫出A的子集B={3,6,9,12}的上界，下界，最小上界，最大下界；(3)寫出A的最大元，最小元，極大元，極小元。解：（1）

1

2

4

8

3

6

12

9

（2）B無上界，也無最小上界。下界1,3;最大下界是3（3）A無最大元，最小元是1，極大元8,12,9;極小元是1

2.設(shè)集合A＝{1,2,3,4}，A上的關(guān)系R＝{(x,y)|x,y∈A且x≥y},求

(1)畫出R的關(guān)系圖；(2)寫出R的關(guān)系矩陣.

解：（1）

（2）1

0001

10011101111RM????

?

?=??

??

??

3.設(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)3

2

3

2

1

1

試求(1)P(a,f(a))∧P(b,f(b));

(2)?x?yP(y,x).

解：

(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)?x?yP(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∧1

=1.

5.設(shè)集合A＝{1,2,4,6,8,12}，R為A上整除關(guān)系。

(1)畫出半序集(A,R)的哈斯圖；

(2)寫出A的最大元，最小元，極大元，極小元；

(3)寫出A的子集B={4,6,8,12}的上界，下界，最小上界，最大下界.

解：(1)(2)無最大元，最小元1，極大元8,12;極小元是1.

(3)B無上界，無最小上界。下界1,2;最大下界2.

6.設(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∧?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)

=(?x?P(x)∧?y?Q(y))∨?zR(z)

=?x?y?z((?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)},

(1)求出r(R),s(R),t(R)；

(2)畫出r(R),s(R),t(R)的關(guān)系圖.

解：（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)系圖:

11.經(jīng)過求主析取范式推斷下列命題公式是否等價：

(1)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)

H=(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

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)}.(1)試寫出R和S的關(guān)系矩陣；(2)計算R?S,R∪S,R－

1,S－

1?R－

1.

解：

(1)????

?????

???=000010000100

0101RM?

?

??

?

?

?

??

???=10000000

11000010

SM

(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)}.

四、證明題

1.利用形式演繹法證明：{P→Q,R→S,P∨R}蘊涵Q∨S。解：

(1)P∨RP(2)?R→PQ(1)(3)P→QP(4)?R→Q

Q(2)(3)

(5)?Q→RQ(4)(6)R→SP(7)?Q→SQ(5)(6)(8)Q∨S

Q(7)

2.設(shè)A,B為任意集合，證明：(A-B)-C=A-(B∪C).解：(A-B)-C=CBA)(

)

()()

(CBACBACBA-===

3.(本題10分)利用形式演繹法證明：{?A∨B,?C→?B,C→D}蘊涵A→D。解：

(1)A

D(附加)(2)?A∨BP(3)B

Q(1)(2)(4)?C→?BP(5)B→CQ(4)(6)C

Q(3)(5)(7)C→DP(8)D

Q(6)(7)(9)A→D

D(1)(8)

因此{(lán)?A∨B,?C→?B,C→D}蘊涵A→D.4.(本題10分)A,B為兩個任意集合，求證：

A－(A∩B)=(A∪B)－

B.解：4.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}}.

2n.

2.2

3.α1={(a,1),(b,1)},α2={(a,2),(b,2)},α3={(a,1),(b,2)},α4={(a,2),(b,1)};α3,α

4.

4.(P∧?Q∧R).

5.12,3.

6.{4},{1,2,3,4},{1,2}.

7.自反性；對稱性；傳遞性.

8.(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)}.

10.2m?n.

11.{x|-1≤x<0,x∈R};{x|1<x<2,x∈R};{x|0≤x≤1,x∈R}.12.12;6.

13.{(2,2),(2,4),(2,6),(3,3),(3,6),(4,4),(5,5),(6,6)}.14.?x(?P(x)∨Q(x)).15.21.

16.(R(a)∧R(b))→(S(a)∨S(b)).17.{(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.15.D三、計算證明題1.(1)

(2)B無上界，也無最小上界。下界1,3;最大下界是3.(3)A無最大元，最小元是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)

(2)10001

10011101111RM????

?

?=??

??

??

3.(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.(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)?x?yP(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∧1

=1.

5.(1)

(2)無最大元，最小元1，極大元8,12;極小元是1.

(3)B無上界，無最小上界。下界1,2;最大下界2.6.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)

=m3∨m4∨m5∨m6∨m7=∑(3,4,5,6,7).

7.G=(?xP(x)∨?yQ(y))→?xR(x)

=?(?xP(x)∨?yQ(y))∨?xR(x)

=(??xP(x)∧??yQ(y))∨?xR(x)

=(?x?P(x)∧?y?Q(y))∨?zR(z)

=?x?y?z((?P(x)∧?Q(y))∨R(z))

9.(1)r(R)＝R∪IA＝{(a,b),(b,a),(b,c),(c,d),(a,a),(b,b),(c,c),