离散数学考试试题(A卷及答案)

离散数学考试试题(A卷及答案)

一、(io分)判断下列公式的类型(永真式、永假式、可满足式)？

1)((P-Q)AQ)-((QVR)AQ)2)「((Q，P)v一P)A(PvR)

3)((PvQ).R).((PAQ)VR)

解：1)永真式；2)永年弑；3)可满足式。

二、(8分)个体域为{1,2},求,x3y(x+y=4)的真值。

解：、x3y(x+y=4)—x((x+l=4)v(x+2=4))

—((1+1=4)V(1+2=4))A((2+1=4)V(2+1=4))

—(OvO)A(0V1)

—1AI—o

三、(8分)已知集合A和B且|A|=n,|B|=m，求A到B的二元关系数是多少？A到B的函勰娓多少?

解：因为|P(AxB)|=2|AxB|=2|A||B|=2mn,所以A到B的二元关系有2mn个。因为|BA|=|B||A|=mn,

所以A到B的函数mn个。

四、(10分)已知人={1,2,3,4,5}和R={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>},求r(R)、s(R)和t(R)。

解:r(R)={<l,2>,<2,l>,<2,3>,<3,4>,<5,4>,<l,l>,<2,2>,<3,3>,<4,4>,<5,5>}

S(R)={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<3,2>,<4,3>,<4,5>}

t(R)={<l,2>,<2,l>,<2,3>,<3,4>,<5,4>,<l,l>,<l,3>,<2,2>,<2,4>,<l,4>}

五、(10分)75个儿童到公园游乐场，他们在那里可以骑旋转木马，坐滑行铁道，乘宇宙飞船，已知其中

20人这三种东西都乘过，其中55人至少乘坐过其中的两种。若每样乘坐一次的费用是0.5元，公园游乐

场总共收入70元，求有多少儿童没有乘坐过其中任何一种。

解设A、B、C分别表示骑旋转木马、坐滑行铁道、乘宇宙飞船的儿童组成的集合，IAnBnCI

=20,|AnB|+|AnC|+|BnC|-2|AnBnC|=55,IA|+|B|+|CI=70/0.5=140o

由容斥原理，得

|AuBuCI=|A|+|B|+|C|-|AnBn|AnCr|BnC|+|AnBnC|

所以

|AnBnC1=75-1AuBuC1=75-(IAI+IBI+|C|)+(|AnB|+|AnC|+|Bn

CI-2|AnBnCI)+|AnBnCI=75-140+55+20=10

没有乘坐过其中任何一种的儿童共10人。

1

六、（12分）已知R和S是非空集合A上的等价关系，试证：DRDS是A上的等价关系；2）对aeA,[a]R

ns二[aLn[a]so

解：…x£A,因为R和S是自反关系，所以<x,x>£R、<x,x>£S,因而<x,x>£RnS,故RCIS是自反

的。

ux、y《A,若<x,y>£RnS,贝[]<x,y>£R、<x,y>eSz因为R和S是对称关系，所以因<y,x>£R、<y,x>

wS,因而<y,x>£RClS,故RAS是对称的。

1

Vx、y、zeA,若<x,y>eRDS且<y,z>eRDS,则<x,y>eR、<x,y>eSH<y,z>eRx<y,z>ES,因为

R和S是传递的，所以因<X,Z>GR、<x,z>eS,因而<x,z>eRCiS,故ROS是传递的。

总之Rns是等价关系。

2)因为xe[a]Rns—<x,a>eRDS—<x,a>eRA<x,a>eS—xe[a]RAXG[a]s—xe[a]RA[a]s

所以同加=同3[a]so

七(10分)设A、B、C、D是集合，f是A到B的双射，g是C到D的双射，令h:AXCTBXD且V<a,c>

GAxC,h(<a,c>)=<f(a),g(c)>o证明h是双射。

证明：1)先证h是满射。

V<b,d>eBxD,则bdB,dGD,因为f是A到B的双1寸，g是C到D的双射，所以存在adA,ceC,

使得f(a)=b,f(c)=d，亦即存在<a,c>GAxC,使得h(<a,c>)=<f(a),g(c)>=<b,d>,所以h是满射。

2)再证h是单射。

V<al,cl>'<a2,c2>GAxC,若h(<al,cl>)=h(<a2,c2>),贝！]<f(al),g(cl)>=<f(a2),g(c2)>,所以

f(al)=f(a2),g(cl)=g(c2),因为f是A到B的双I寸，g是C到D的双射,所以al=a2,cl=c2,所以

<al,cl>=<a2,c2>,所以h是单射。

综合1）和2）,h是双射。

八、（12分）＜G,*＞是个群，ueG,定义G中的运算h"为a\b=a*u-l*b,对任意a,beG,求证：＜G,、＞

也是个群。

证明：1)Va,beG,a\b=a*u-l*beG,运算是封闭的。

2)Va,b,ceG,(a也)\c=(a*u-l*b)*u-l*c=a*u-l*(b*u-l*c)=a\(b、c),运算是可结合的。

3)VaeG，设E为珀勺单位元，贝!]a正=a*u-l*E=a，得E=u,存在单位元。

4)VaeG,a.\x=a*u-l*x=E,x=u*a-l*u,贝!]x\a=u*a-l*u*u-l*a=u=E，每隋

所以<G,、>也是个群。

九、(10分)已知：D=<V,E>,V={1,2,3,4,5},E={<1,2>,<1,4>,<2,3>,<3,4>,<3,5>,<5,1>}求D的邻接

距阵A和可达距阵P。

解：D的令阱妾距阵A和可达距阵P如下：

01十、Q0分）求叶的权分别为

01

00解：最优二叉树为0

A=00100

00

011P二

10

000

2

111

11

11

00

2、4、6、8、10、12、14

的最优二对及其权。

2

权=148

离散数学考试试题(B卷及答案)

一、(10分)求命题公式一(PAQ)一.(.P・R)的主合取范式。

解：.(PAQ)—(P.R)—(_(PAQ)一(_P-R))人JJP・R)…(PAQ))

—((PAQ)V(「PA—R))A((PvR)v(一Pv「Q))

—(PAQ)V(,PA_R)

—(PV「R)A(Qv-P)A(QV-R)

—(PvQvR)A(Pv_Qv,R)A(,PvQvR)A(,PvQvR)

-MiAM3AM4AM5

二、(8分)叙述并证明苏格拉底三段论

解：所有人都是要死的，苏格拉底是人，所以苏格拉底是要死的。

符号化：F(x):x是一个人。G(x):x要死的。A:苏格拉底。

3

命题符号化为Vx(F(x)G(x)),F(a)=G(a)

证明：

(1)Vx(F(xJG(x))P

F(a)->G(a)T(1),US

G(a)T(2)⑶j/

三、（8分）已知A、B、C是三个集曾硼Xn（BiUC）^（AnB）U（ADC）

证明：:x号An（BUC）飞春ANxw（BU#；1<

611

AA(xeByx(C)

4XAAX<B)v(xtAAXI

x-(APIB)vx-APIC

(AnB)u(AnC)

3

..An(Buc)=(AnB)u(Anc)

四、QO分)已知R和s是非空集合A上的等价关系，试证：l)RnS是A上的等价关系；2)对aeA,[a]R

”二⑶RCI[a]so

解：VxwA,因为R和S是自反关系，所以<x,x>£R、<x,x>£S,因而<X,X>£RCIS,故RCIS是自反

的。

Vx、y@A,若<x,y>£RClS,贝(]<x,y>£R、<x,y>eSz因为R和S是对称关系，所以因<y,x>wR、<y,x>

wS,因而<y,x>£RClS,故RAS是对称的。

Vx、y、ZGA,若<x,y>£RnS且<y,z>£RDS,贝eR、<x,y>eSfi<yzz>eRx<y,z>eS,因为

R和S是传递的，所以因<x,z>£R、<x,z>£S,因而<x，z>£RnS,故RClS是传递的。

总之RAS是等价关系。

2)因为xG[a]Rns—<x,a>GRCIS一

<x,a>GRA<x,a>GS—xe[a]RAXE[a]s—xe[a]Rn[a]s

所以所R”=⑶①[a]so

五、(10分)设A={a,b,czd),R是A±fi匚元关系，且R={<a,b>,<b,a>,<b,c>,<c,d>},求

r(R)、s(R)和t(R)o

解r(R)=RUlA={<a,b>,<b,a>,<b,c>,<c,d>,<a,a>,<b,b>,<c,c>,<d；d>}

s(R)=RUR-1={<a,b>,<b,a>,<b,c>,<c,d>,<c,b>,<d,c>}

R2={<a,a>,<a,c>,<b,b>,<b,d>}

R3={<a,b>,<a,d>,<b,a>,<b,c>}

R4={<a,a>,<a,c>,<b,b>,<b,d>}=R2

w

t(R)=UR={<a,b>,<b,a>,<b,c>,<c,d>,<a,a>,<a,c>,<b,b>,<b,d>,<a,d>}

i=i

六、(15分)设A、B、C、D是集合，f是A到B的双射，g是C到D的双|寸，令h:AxC.BxDfiV<a,c>

GAxC,h(<a,c>)=<f(a),g(c)>o证明h是双射。

证明：1)先证h是满射。

V<b,d>eBxD,则beB,deD,因为f是A到B的双I寸，g是C至UD的双1寸，所以存在aeA,ceC,

使得f(a)=b,f(c)=d，亦即存在<a,c>eAxC,使得h(<a,c>)=<f⑶,g(c)>=<b,d>,所以h是满射。

2）再证h是单射。

4

V<al,cl>、<a2,c2>GAxC,若h(<al,cl>)=h(<a2,c2>),贝[]<f(al),g(cl)>=<f(a2),g(c2)>,所

以f(al)=f(a2),g(cl)=g(c2),因为f是A到B的双射，g是C到D的双射，所以al=a2,cl=c2,所

以<al,cl>=<a2,c2>,所以h是单射。

综合1)和2),h是双射。

七、(12分)设<G,*>是群，H是G的非空子集，证明<H,*>是<6,*>的子群的充要条件是若a,b=H,则

有aWH。

证明：Va,beH有b-ieH,所以a*biGH。

VaeH,则e=a*a-1eH

4

a1=e*a1GH

；a,bwH及b-GH,.-.a*b=a*(b1)^eH

•.HcG且H/中，「*在H上满足结合律

.•.<H,*>是<6,*>的子群。

八、(10分)设G=<V,E>是简单的无向平面图，证明G至少有一个结点的度数小于等于5。

解：设G的每个结字的度郭都大寺等于6,则2|E|=xd(v)26|V|,即旧23|V|,与简单无向平面图

的|E|431Vl-6矛盾，噌G号少惠一住吉点的度数小于等于5。

九件Cb,阴勺运臂电即呈