离散数学期末考试试题及答案

.

..

一、填空题

1设集合A,B，其中A＝{1,2,3},B={1,2},则A-B＝{3};(A)-(B)＝

{3},{1,3},{2,3},{1,2,3}}.

2.设有限集合A,|A|=n,则|(A×A)|=22n.

3.设集合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.设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为12，分枝点数为3.

6设A、B为两个集合,A={1,2,4},B={3,4},则从AB＝{4};AB＝{1,2,3,4};

A－B＝{1,2}.

7.设R是集合A上的等价关系，则R所具有的关系的三个特性是自反性,对称性

传递性.

8.设命题公式G＝(P(QR))，则使公式G为真的解释有(1,0,0),(1,0,1),(1,1,0)

9.设集合A＝{1,2,3,4},A上的关系R

1

={(1,4),(2,3),(3,2)},R

2

={(2,1),(3,2),(4,3)},则R

1

•R

2

={(1,3),(2,2),(3,1)},R

2

•R

1

={(2,4),(3,3),(4,2)}_R

1

2={(2,2),(3,3).

10.设有限集A,B，|A|=m,|B|=n,则||(AB)|=nm2.

11设A,B,R是三个集合，其中R是实数集，A={x|-1≤x≤1,xR},B={x|0≤x<2,xR},

则A-B=-1<=x<0,B-A={x|1

A∩B={x|0≤x≤1,xR},.

13.设集合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)}.

14.设一阶逻辑公式G=xP(x)xQ(x)，则G的前束范式是x(P(x)∨Q(x)).

15.设G是具有8个顶点的树，则G中增加21条边才能把G变成完全图。(完全图的边

数

2

)1(nn

，树的边数为n-1)

16.设谓词的定义域为{a,b},将表达式xR(x)→xS(x)中量词消除，写成与之对应的命题公式

是_(R(a)∧R(b))→(S(a)∨S(b))_.

17.设集合A＝{1,2,3,4}，A上的二元关系R＝{(1,1),(1,2),(2,3)},S＝{(1,3),(2,3),(3,2)}。则

RS＝{(1,3),(2,2)},

R2＝{(1,1),(1,2),(1,3)}.

.

..

二、选择题

1设集合A={2,{a},3,4}，B={{a},3,4,1}，E为全集，则下列命题正确的是(C)。

(A){2}A(B){a}A(C){{a}}BE(D){{a},1,3,4}B.

2设集合A={1,2,3},A上的关系R＝{(1,1),(2,2),(2,3),(3,2),(3,3)}，则R不具备(D).

(A)自反性(B)传递性(C)对称性(D)反对称性

3设半序集(A,≤)关系≤的哈斯图如下所示，若A的子集B={2,3,4,5},则元素6为B的

(B)。

(A)下界(B)上界(C)最小上界(D)以上答案都不对

4下列语句中，(B)是命题。

(A)请把门关上(B)地球外的星球上也有人

(C)x+5>6(D)下午有会吗？

5设I是如下一个解释：D＝{a,b},

0101

b)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.若供选择答案中的数值表示一个简单图中各个顶点的度，能画出图的是(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.设G、H是一阶逻辑公式，P是一个谓词，G＝xP(x),H＝xP(x),则一阶逻辑公式GH

是(C).

(A)恒真的(B)恒假的(C)可满足的(D)前束范式.

8设命题公式G＝(PQ)，H＝P(QP)，则G与H的关系是(A)。

(A)GH(B)HG(C)G＝H(D)以上都不是.

9设A,B为集合，当(D)时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具有(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)有一个x

0

，使G(x

0

)取真值1.

(C)有某些x，使G(x

0

)取真值1.(D)以上答案都不对.

13.设G是连通平面图，有5个顶点，6个面，则G的边数是(A).

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

14.设G是5个顶点的完全图，则从G中删去(A)条边可以得到树.

(A)6(B)5(C)10(D)4.

15.设图G的相邻矩阵为

































01101

10101

11011

00101

11110

，则G的顶点数与边数分别为(D).

(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)的哈斯图；

1

2

3

4

5

6

.

..

(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.设集合A＝{1,2,3,4}，A上的关系R＝{(x,y)|x,yA且xy},求

(1)画出R的关系图；

(2)写出R的关系矩阵.

解：（1）

1

2

3

4

（2）

1000

1100

1110

1111

R

M















3.设R是实数集合，,,是R上的三个映射，(x)=x+3,(x)=2x,(x)＝x/4,试求复合

映射•，•,•,•，••.

解：

(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.设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));

(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.设集合A＝{1,2,4,6,8,12}，R为A上整除关系。

(1)画出半序集(A,R)的哈斯图；

(2)写出A的最大元，最小元，极大元，极小元；

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

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

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

6.设命题公式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)

=m

3

∨m

4

∨m

5

∨m

6

∨m

7

=(3,4,5,6,7).

.

..

7.(9分)设一阶逻辑公式：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.设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)的关系图.

解：（1）

r(R)＝R∪I

A

＝{(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)关系图:

11.通过求主析取范式判断下列命题公式是否等价：

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

＝m

6

∨m

7

∨m

3

＝(3,6,7)

b

a

c

d

r(R)

b

a

c

d

s(R)

b

a

c

d

t(R)

.

..

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)

＝m

6

∨m

3

∨m

7

G,H的主析取范式相同，所以G=H.

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)



























0000

1000

0100

0101

R

M



























1000

0000

1100

0010

S

M

(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→QQ(2)(3)

(5)Q→RQ(4)

(6)R→SP

(7)Q→SQ(5)(6)

.

..

(8)Q∨SQ(7)

2.设A,B为任意集合，证明：(A-B)-C=A-(B∪C).

解：(A-B)-C=

CBA)(

)(

)(

)(

CBA

CBA

CBA













3.(本题10分)利用形式演绎法证明：{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.

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

2.22n.

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

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)

1000

1100

1110

1111

R

M















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

2

4

8

3

6

12

9

1

2

3

4

.

..

=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)

=m

3

∨m

4

∨m

5

∨m

6

∨m

7

=(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∪I

A

＝{(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)关系图:

2

4

1

6

8

12

.

..

11.G＝(P∧Q)∨(P∧Q∧R)

＝(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)

＝m

6

∨m

7

∨m

3

＝(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)

＝m

6

∨m

3

∨m

7

＝(3,6,7)

G,H的主析取范式相同，所以G=H.

13.(1)



























0000

1000

0100

0101

R

M



























1000

0000

1100

0010

S

M

(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→QQ(2)(3)

b

a

c

d

r(R)

b

a

c

d

s(R)

b

a

c

d

t(R)

.

..

(5)Q→RQ(4)

(6)R→SP

(7)Q→SQ(5)(6)

(8)Q∨SQ(7)

2.证明：(A-B)-C=(A∩~B)∩~C

=A∩(~B∩~C)

=A∩~(B∪C)

=A-(B∪C)

3.证明：{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.

5.证明：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.