离散数学答案

离散数学答案

评课记录-行气玉佩铭

2023年3月19日发(作者：福尔摩斯密码)

离散数学试题及答案

第2页共18页

离散数学试题及答案

一、填空题

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)|=___2^(n^2)________.

3.设集合A={a,b},B={1,2},则从A到B的所有映射是____A1={(a,1),(b,1)},A2={(a,2),

(b,2)},A3={(a,1),(b,2)},A4={(a,2),(b,1)},______________________,其中双射的是______A3,

A4__________.

4.已知命题公式G＝(PQ)∧R，则G的主析取范式是____P∧Q∧R(m5)____.

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

1

={(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)|=______2^(m*n)___________.

11设A,B,R是三个集合，其中R是实数集，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

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的前束范式是_____yx(P(y)Q(x))________

_____.

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

第3页共18页

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

1

2

3

4

5

6

第4页共18页

(1)

第5页共18页

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

B无上界，也无最小上界。下界1,3;最大下界是3.

(3)写出A的最大元，最小元，极大元，极小元。

A无最大元，最小元是1，极大元8,12,90+;极小元是1.

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

(1)画出R的关系图；

1

2

3

4

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

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

第6页共18页

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

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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

4

1

6

8

12

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

第7页共18页

无最大元，最小元1，极大元8,12;极小元是1.

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

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

6.设命题公式G=(P→Q)∨(Q∧(P→R)),求G的主析取范式。

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

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)画出r(R),s(R),t(R)的关系图.

b

a

c

d

r(R)

b

a

c

d

s(R)

b

a

c

d

t(R)

第8页共18页

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)

＝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.设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的关系矩阵；



























0000

1000

0100

0101

R

M



























1000

0000

1100

0010

S

M

(2)计算R•S,R∪S,R－1,S－1•R－1.

第9页共18页

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。

证明：{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=(A∩~B)∩~C

=A∩(~B∩~C)

=A∩~(B∪C)

=A-(B∪C)

第10页共18页

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.

4.(本题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

第11页共18页

=(A∪B)∩~B

=(A∩~B)∪(B∩~B)

=(A∩~B)∪

=A－B

所以：A－(A∩B)=(A∪B)－B.

离散数学试题（A卷及答案）

一、（10分）某项工作需要派A、B、C和D4个人中的2个人去完成，按下面3个

条件，有几种派法？如何派？

(1)若A去，则C和D中要去1个人；

(2)B和C不能都去；

(3)若C去，则D留下。

解设A：A去工作；B：B去工作；C：C去工作；D：D去工作。则根据题意应有：

ACD，(B∧C)，CD必须同时成立。因此

(ACD)∧(B∧C)∧(CD)

(A∨(C∧D)∨(C∧D))∧(B∨C)∧(C∨D)

(A∨(C∧D)∨(C∧D))∧((B∧C)∨(B∧D)∨C∨(C∧

D))

(A∧B∧C)∨(A∧B∧D)∨(A∧C)∨(A∧C∧D)

第12页共18页

∨(C∧D∧B∧C)∨(C∧D∧B∧D)∨(C∧D∧C)∨(C∧

D∧C∧D)

∨(C∧D∧B∧C)∨(C∧D∧B∧D)∨(C∧D∧C)∨(C∧D

∧C∧D)

F∨F∨(A∧C)∨F∨F∨(C∧D∧B)∨F∨F∨(C∧D∧B)∨F

∨(C∧D)∨F

(A∧C)∨(B∧C∧D)∨(C∧D∧B)∨(C∧D)

(A∧C)∨(B∧C∧D)∨(C∧D)

T

故有三种派法：B∧D，A∧C，A∧D。

二、（15分）在谓词逻辑中构造下面推理的证明：某学术会议的每个成员都是专家并

且是工人，有些成员是青年人，所以，有些成员是青年专家。

解：论域：所有人的集合。S(

x

)：

x

是专家；W(

x

)：

x

是工人；Y(

x

)：

x

是青年人；

则推理化形式为：

x

(S(

x

)∧W(

x

))，

xY(

x

)

x

(S(

x

)∧Y(

x

))

下面给出证明：

(1)

xY(

x

)P

(2)Y(c)T(1)，ES

(3)

x

(S(

x

)∧W(

x

))P

(4)S(c)∧W(c)T(3)，US

(5)S(c)T(4)，I

(6)S(c)∧Y(c)T(2)(5)，I

(7)

x

(S(

x

)∧Y(

x

))T(6)，EG

三、（10分）设A、B和C是三个集合，则AB(BA)。

证明：ABx(x∈A→x∈B)∧x(x∈B∧xA)x(xA∨x∈B)∧x(x∈B∧xA)

x(x∈A∧xB)∧x(xB∨x∈A)x(x∈A∧xB)∨x(x∈A∨

xB)

(x(x∈A∧xB)∧x(x∈A∨xB))(x(x∈A∧xB)∧x(x∈B→x

∈A))

第13页共18页

(BA)。

四、（15分）设A＝{1，2，3，4，5}，R是A上的二元关系，且R＝{，<2，

5>，，，，}，求r(R)、s(R)和t(R)。

解r(R)＝R∪I

A＝{，，，，，，，

，，，}

s(R)＝R∪R－1＝{，，，，，，，<4，

2>，}

R2＝{，，，，，，}

R3＝{，，，，，，}

R4＝{，，，，，，}＝R2

t(R)＝

1i

Ri＝{，，，，，，，<5，

1>，，}。

五、（10分）R是非空集合A上的二元关系，若R是对称的，则r(R)和t(R)是对称

的。

证明对任意的x、y∈A，若xr(R)y，则由r(R)＝R∪I

A得，xRy或xIAy。因R与

IA对称，所以有yRx或yIAx，于是yr(R)x。所以r(R)是对称的。

下证对任意正整数n，Rn对称。

因R对称，则有xR2yz(xRz∧zRy)z(zRx∧yRz)yR2x，所以R2对称。若n

R对

称，则x1n

Ryz(xn

Rz∧zRy)z(zn

Rx∧yRz)y1n

Rx，所以1n

R对称。因此，对任意

正整数n，n

R对称。

对任意的x、y∈A，若xt(R)y，则存在m使得xRmy，于是有yRmx，即有yt(R)x。因此，

t(R)是对称的。

六、（10分）若f：A→B是双射，则f－1：B→A是双射。

证明因为f：A→B是双射，则f－1是B到A的函数。下证f－1是双射。

对任意x∈A，必存在y∈B使f(x)＝y，从而f－1(y)＝x，所以f－1是满射。

对任意的y

1

、y

2

∈B，若f－1(y

1

)＝f－1(y

2

)＝x，则f(x)＝y

1

，f(x)＝y

2

。因为f：A→B是

函数，则y

1

＝y

2

。所以f－1是单射。

综上可得，f－1：B→A是双射。

第14页共18页

七、（10分）设是一个半群，如果S是有限集，则必存在a∈S，使得a*a＝a。

证明因为是一个半群，对任意的b∈S，由*的封闭性可知，b2＝b*b∈S，b3

＝b2*b∈S，…，bn∈S，…。

因为S是有限集，所以必存在j＞i，使得ib＝jb。令p＝j－i，则jb＝pb*jb。所以对

q≥i，有qb＝pb*qb。

因为p≥1，所以总可找到k≥1，使得kp≥i。对于kpb∈S，有kpb＝pb*kpb＝pb*(pb*kpb)

＝…＝kpb*kpb。

令a＝kpb，则a∈S且a*a＝a。

八、（20分）（1）若G是连通的平面图，且G的每个面的次数至少为l(l≥3)，则G

的边数m与结点数n有如下关系：

m≤

2l

l

(n－2)。

证明设G有r个面，则2m＝



r

i

i

fd

1

)(≥lr。由欧拉公式得，n－m＋r＝2。于是，m

≤

2l

l

(n－2)。

（2）设平面图G＝是自对偶图，则|E|＝2(|V|－1)。

证明设G*＝是连通平面图G＝的对偶图，则G*G，于是|F|

＝|V*|＝|V|，将其代入欧拉公式|V|－|E|＋|F|＝2得，|E|＝2(|V|－1)。

第15页共18页

离散数学试题（B卷及答案）

一、（10分）证明(P∨Q)∧(PR)∧(QS)S∨R

证明因为S∨RRS，所以，即要证(P∨Q)∧(PR)∧(QS)RS。

(1)R附加前提

(2)PRP

(3)PT(1)(2)，I

(4)P∨QP

(5)QT(3)(4)，I

(6)QSP

(7)ST(5)(6)，I

(8)RSCP

(9)S∨RT(8)，E

二、（15分）根据推理理论证明：每个考生或者勤奋或者聪明，所有勤奋的人都将有所作为，

但并非所有考生都将有所作为，所以，一定有些考生是聪明的。

设P(e)：e是考生，Q(e)：e将有所作为，A(e)：e是勤奋的，B(e)：e是聪明的，个体域：人

的集合，则命题可符号化为：x(P(x)(A(x)∨B(x)))，x(A(x)Q(x))，x(P(x)Q(x))x(P(x)

∧B(x))。

(1)x(P(x)Q(x))P

第16页共18页

(2)x(P(x)∨Q(x))T(1)，E

(3)x(P(x)∧Q(x))T(2)，E

(4)P(a)∧Q(a)T(3)，ES

(5)P(a)T(4)，I

(6)Q(a)T(4)，I

(7)x(P(x)(A(x)∨B(x))P

(8)P(a)(A(a)∨B(a))T(7)，US

(9)A(a)∨B(a)T(8)(5)，I

(10)x(A(x)Q(x))P

(11)A(a)Q(a)T(10)，US

(12)A(a)T(11)(6)，I

(13)B(a)T(12)(9)，I

(14)P(a)∧B(a)T(5)(13)，I

(15)x(P(x)∧B(x))T(14)，EG

三、（10分）某班有25名学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，

5人会打篮球和网球，还有2人会打这三种球。而6个会打网球的人都会打另外一种球，求不会

打这三种球的人数。

解设A、B、C分别表示会打排球、网球和篮球的学生集合。则：

|A|＝12，|B|＝6，|C|＝14，|A∩C|＝6，|B∩C|＝5，|A∩B∩C|＝2，|(A∪C)∩B|＝6。

因为|(A∪C)∩B|＝(A∩B)∪(B∩C)|＝|(A∩B)|＋|(B∩C)|－|A∩B∩C|＝|(A∩B)|＋5－2＝6，

所以|(A∩B)|＝3。于是|A∪B∪C|＝12＋6＋14－6－5－3＋2＝20，||CBA＝25－20＝5。故，

不会打这三种球的共5人。

四、（10分）设A

1

、A

2

和A

3

是全集U的子集，则形如3

1i

A

i

(A

i

为A

i

或

i

A)的集合称为由A

1

、

A

2

和A

3

产生的小项。试证由A

1

、A

2

和A

3

所产生的所有非空小项的集合构成全集U的一个划分。

证明小项共8个，设有r个非空小项s

1

、s

2

、…、s

r

(r≤8)。

对任意的a∈U，则a∈A

i

或a∈

i

A，两者必有一个成立，取A

i

为包含元素a的A

i

或

i

A，则

a∈3

1i

A

i

，即有a∈r

i1

s

i

，于是Ur

i1

s

i

。又显然有r

i1

s

i

U，所以U＝r

i1

s

i

。

任取两个非空小项s

p

和s

q

，若s

p

≠s

q

，则必存在某个A

i

和

i

A分别出现在s

p

和s

q

中，于是s

p

∩s

q

＝。

综上可知，{s

1

，s

2

，…，s

r

}是U的一个划分。

第17页共18页

五、（15分）设R是A上的二元关系，则：R是传递的R*RR。

证明(5)若R是传递的，则∈R*Rz(xRz∧zSy)xRc∧cSy，由R是传递的得xRy，

即有∈R，所以R*RR。

反之，若R*RR，则对任意的x、y、z∈A，如果xRz且zRy，则∈R*R，于是有

y>∈R，即有xRy，所以R是传递的。

六、（15分）若G为连通平面图，则n－m＋r＝2，其中，n、m、r分别为G的结点数、边

数和面数。

证明对G的边数m作归纳法。

当m＝0时，由于G是连通图，所以G为平凡图，此时n＝1，r＝1，结论自然成立。

假设对边数小于m的连通平面图结论成立。下面考虑连通平面图G的边数为m的情况。

设e是G的一条边，从G中删去e后得到的图记为G，并设其结点数、边数和面数分别为

n、m和r。对e分为下列情况来讨论：

若e为割边，则G有两个连通分支G

1

和G

2

。G

i

的结点数、边数和面数分别为n

i

、m

i

和r

i

。

显然n

1

＋n

2

＝n＝n，m

1

＋m

2

＝m＝m－1，r

1

＋r

2

＝r＋1＝r＋1。由归纳假设有n

1

－m

1

＋r

1

＝2，

n

2

－m

2

＋r

2

＝2，从而(n

1

＋n

2

)－(m

1

＋m

2

)＋(r

1

＋r

2

)＝4，n－(m－1)＋(r＋1)＝4，即n－m＋r＝2。

若e不为割边，则n＝n，m＝m－1，r＝r－1，由归纳假设有n－m＋r＝2，从而n－(m

－1)＋r－1＝2，即n－m＋r＝2。

由数学归纳法知，结论成立。

七、（10分）设函数g：A→B，f：B→C，则：

(1)fg是A到C的函数；

(2)对任意的x∈A，有fg(x)＝f(g(x))。

证明(1)对任意的x∈A，因为g：A→B是函数，则存在y∈B使∈g。对于y∈B，

因f：B→C是函数，则存在z∈C使∈f。根据复合关系的定义，由∈g和∈

f得∈g*f，即∈fg。所以D

f



g

＝A。

对任意的x∈A，若存在y

1

、y

2

∈C，使得

1

>、

2

>∈fg＝g*f，则存在t

1

使得

1

>

∈g且

1

，y

1

>∈f，存在t

2

使得

2

>∈g且

2

，y

2

>∈f。因为g：A→B是函数，则t

1

＝t

2

。又

因f：B→C是函数，则y

1

＝y

2

。所以A中的每个元素对应C中惟一的元素。

综上可知，fg是A到C的函数。

(2)对任意的x∈A，由g：A→B是函数，有∈g且g(x)∈B，又由f：B→C是函数，

第18页共18页

得∈f，于是∈g*f＝fg。又因fg是A到C的函数，则可写为fg(x)

＝f(g(x))。

八、（15分）设是的子群，定义R＝{|a、b∈G且a－1*b∈H}，则R是

G中的一个等价关系，且[a]

R

＝aH。

证明对于任意a∈G，必有a－1∈G使得a－1*a＝e∈H，所以∈R。

若∈R，则a－1*b∈H。因为H是G的子群，故(a－1*b)－1＝b－1*a∈H。所以∈

R。

若∈R，∈R，则a－1*b∈H，b－1*c∈H。因为H是G的子群，所以(a－1*b)*(b

－1*c)＝a－1*c∈H，故∈R。

综上可得，R是G中的一个等价关系。

对于任意的b∈[a]

R

，有∈R，a－1*b∈H，则存在h∈H使得a－1*b＝h，b＝a*h，于

是b∈aH，[a]

R

aH。对任意的b∈aH，存在h∈H使得b＝a*h，a－1*b＝h∈H，∈R，故

aH[a]

R

。所以，[a]

R

＝aH。