離散數(shù)學(xué)考試試題(A卷及答案)

離散數(shù)學(xué)考試試題(A卷及答案)

一、(io分)判斷下列公式的類型(永真式、永假式、可滿足式)？

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

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

解：1)永真式；2)永年弒；3)可滿足式。

二、(8分)個(gè)體域?yàn)閧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的二元關(guān)系數(shù)是多少？A到B的函勰娓多少?

解：因?yàn)閨P(AxB)|=2|AxB|=2|A||B|=2mn,所以A到B的二元關(guān)系有2mn個(gè)。因?yàn)閨BA|=|B||A|=mn,

所以A到B的函數(shù)mn個(gè)。

四、(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個(gè)兒童到公園游樂場，他們在那里可以騎旋轉(zhuǎn)木馬，坐滑行鐵道，乘宇宙飛船，已知其中

20人這三種東西都乘過，其中55人至少乘坐過其中的兩種。若每樣乘坐一次的費(fèi)用是0.5元，公園游樂

場總共收入70元，求有多少兒童沒有乘坐過其中任何一種。

解設(shè)A、B、C分別表示騎旋轉(zhuǎn)木馬、坐滑行鐵道、乘宇宙飛船的兒童組成的集合，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上的等價(jià)關(guān)系，試證：DRDS是A上的等價(jià)關(guān)系；2）對aeA,[a]R

ns二[aLn[a]so

解：…x￡A,因?yàn)镽和S是自反關(guān)系，所以<x,x>￡R、<x,x>￡S,因而<x,x>￡RnS,故RCIS是自反

的。

ux、y《A,若<x,y>￡RnS,貝[]<x,y>￡R、<x,y>eSz因?yàn)镽和S是對稱關(guān)系，所以因<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,因?yàn)?/p>

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

總之Rns是等價(jià)關(guān)系。

2)因?yàn)閤e[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分)設(shè)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,因?yàn)閒是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),因?yàn)閒是A到B的雙I寸，g是C到D的雙射,所以al=a2,cl=c2,所以

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

綜合1）和2）,h是雙射。

八、（12分）＜G,*＞是個(gè)群，ueG,定義G中的運(yùn)算h"為a\b=a*u-l*b,對任意a,beG,求證：＜G,、＞

也是個(gè)群。

證明：1)Va,beG,a\b=a*u-l*beG,運(yùn)算是封閉的。

2)Va,b,ceG,(a也)\c=(a*u-l*b)*u-l*c=a*u-l*(b*u-l*c)=a\(b、c),運(yùn)算是可結(jié)合的。

3)VaeG，設(shè)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,、>也是個(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和可達(dá)距陣P。

解：D的令阱妾距陣A和可達(dá)距陣P如下：

01十、Q0分）求葉的權(quán)分別為

01

00解：最優(yōu)二叉樹為0

A=00100

00

011P二

10

000

2

111

11

11

00

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

的最優(yōu)二對及其權(quán)。

2

權(quán)=148

離散數(shù)學(xué)考試試題(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è)人。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是三個(gè)集曾硼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上的等價(jià)關(guān)系，試證：l)RnS是A上的等價(jià)關(guān)系；2)對aeA,[a]R

”二⑶RCI[a]so

解：VxwA,因?yàn)镽和S是自反關(guān)系，所以<x,x>￡R、<x,x>￡S,因而<X,X>￡RCIS,故RCIS是自反

的。

Vx、y@A,若<x,y>￡RClS,貝(]<x,y>￡R、<x,y>eSz因?yàn)镽和S是對稱關(guān)系，所以因<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,因?yàn)?/p>

R和S是傳遞的，所以因<x,z>￡R、<x,z>￡S,因而<x，z>￡RnS,故RClS是傳遞的。

總之RAS是等價(jià)關(guān)系。

2)因?yàn)閤G[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分)設(shè)A={a,b,czd),R是A±fi匚元關(guān)系，且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分)設(shè)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,因?yàn)閒是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),因?yàn)閒是A到B的雙射，g是C到D的雙射，所以al=a2,cl=c2,所

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

綜合1)和2),h是雙射。

七、(12分)設(shè)<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上滿足結(jié)合律

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

八、(10分)設(shè)G=<V,E>是簡單的無向平面圖，證明G至少有一個(gè)結(jié)點(diǎn)的度數(shù)小于等于5。

解：設(shè)G的每個(gè)結(jié)字的度郭都大寺等于6,則2|E|=xd(v)26|V|,即舊23|V|,與簡單無向平面圖

的|E|431Vl-6矛盾，噌G號少惠一住吉點(diǎn)的度數(shù)小于等于5。

九件Cb,陰勺運(yùn)臂電即呈