《離散數學》試題及答案

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

1設集合A,B，其中A＝{1,2,3},B={1,2},則A-B＝________ρ(A)-ρ(B)＝.

2.設有限集合A,|A|=n,則|ρ(A×A)|=_________

3.設集合A={a,b},B={1,2},則從A到B的所有映射是__________________,其中雙射的是______

4.已知命題公式G＝?(P→Q)∧R，則G的主析取范式是________

6設A、B為兩個集合,A={1,2,4},B={3,4},則從A?B＝______;A?B＝_____;A－B＝

7.設R是集合A上的等價關系，則R所具有的關系的三個特性是______________________,

8.設命題公式G＝?(P→(Q∧R))，則使公式G為確實解釋有____________，_____,_________

9.設集合A＝{1,2,3,4},A上的關系R1={(1,4),(2,3),(3,2)},R2={(2,1),(3,2),(4,3)},則R1?R2=______,R2?R1=_____,R12=_____.

10.設有限集A,B，|A|=m,|B|=n,則||ρ(A?B)|=_______.

11設A,B,R是三個集合，其中R是實數集，A={x|-1≤x≤1,x∈R},B={x|0≤x6(D)下午有會嗎？

5設I是如下一具解釋：D＝{a,b},

1

1b)

P(b,

a)

P(b,

b)

P(a,

)

,

(a

a

P

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

(A)?x?yP(x,y)(B)?x?yP(x,y)(C)?xP(x,x)(D)?x?yP(x,y).

6.若供挑選答案中的數值表示一具簡單圖中各個頂點的度，能畫出圖的是().

(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.設G、H是一階邏輯公式，P是一具謂詞，G＝?xP(x),H＝?xP(x),則一階邏輯公式G→H是().

(A)恒確實(B)恒假的(C)可滿腳的(D)前束范式.

8設命題公式G＝?(P→Q)，H＝P→(Q→?P)，則G與H的關系是()。

(A)G?H(B)H?G(C)G＝H(D)以上都別是.

9設A,B為集合，當()時A－B＝B.

(A)A＝B

(B)A?B

(C)B?A

(D)A＝B＝?.

10設集合A={1,2,3,4},A上的關系R＝{(1,1),(2,3),(2,4),(3,4)},則R具有()。

(A)自反性

(B)傳遞性

(C)對稱性(D)以上答案都別對

11下列對于集合的表示中正確的為()。

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

(C)有某些x，使G(x0)取真值1.(D)以上答案都別對.13.設G是連通平面圖，有5個頂點，6個面，則G的邊數是().

(A)9條(B)5條(C)6條(D)11條.

15.設圖G的相鄰矩陣為???

?

??

?

?

?????

???01101

101011101100101

11110，則G的頂點數與邊數分不為().

(A)4,5(B)5,6

(C)4,10(D)5,8.

三、計算證明題

1.設集合A＝{1,2,3,4,6,8,9,12}，R為整除關系。

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

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

設集合A＝{1,2,3,4}，A上的關系R＝{(x,y)|x,y∈A且x≥y},求(1)畫出R的關系圖；(2)寫出R的關系矩陣.3.

設R是實數集合，σ,τ,?是R上的三個映射，σ(x)=x+3,τ(x)=2x,?(x)＝x/4,試求復合映射σ?τ，σ?σ,σ??,??τ，σ???τ.

4.設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).

5.設集合A＝{1,2,4,6,8,12}，R為A上整除關系。

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

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

(3)寫出A的子集B={4,6,8,12}的上界，下界，最小上界，最大下界.6.設命題公式G=?(P→Q)∨(Q∧(?P→R)),求G的主析取范式。

7.(9分)設一階邏輯公式：G=(?xP(x)∨?yQ(y))→?xR(x)，把G化成前束范式.9.設R是集合A={a,b,c,d}.R是A上的二元關系,R={(a,b),(b,a),(b,c),(c,d)},

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

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

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

(1)G=(P∧Q)∨(?P∧Q∧R)

(2)H=(P∨(Q∧R))∧(Q∨(?P∧R))

13.設R和S是集合A＝{a,b,c,d}上的關系，其中R＝{(a,a),(a,c),(b,c),(c,d)},S＝{(a,b),(b,c),(b,d),(d,d)}.

(1)試寫出R和S的關系矩陣；

(2)計算R?S,R∪S,R－1,S－1?R－1.

四、證明題

參考答案

一、填空題

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

10011101

11

1RM?????

?=??????

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),(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)關系圖:Array

11.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＝∑(3,6,7)

G,H的主析取范式相同，因此G=H.

13.(1)????

?????

???=00

00

10000100

0101RM?????

???????=10

00

00001100001

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

四證明題

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

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

4.(本題10分)A,B為兩個任意集合，求證：

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

B.

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