离散数学课后习题答案

习题参考解答

1、(3)P：银行利率降低

Q：股价没有上升

PAQ

(5)P：他今天乘火车去了北京

Q：他随旅行团去了九寨沟

(7)P：不识庐山真面目

Q：身在此山中

Q—P,或〜P一〜Q

(9)P：一个整数能被6整除

Q：一个整数能被3整除

R：一个整数能被2整除

T：一个整数的各位数字之和能被3整除

P-QAR,QT

2、(1)T(2)F(3)F(4)T(5)F

(6)T(7)F(8)悖论

1(3)

(4)

2、不，不，能

主合取范式

-主析取范式

3、解：根据给定的条件有下述命题公式:

（Af（CVD））八〜（BAC）八〜（CAD）

c（〜AV（C八〜D）V（〜CAD））A（〜BV〜C）A（〜CV〜D）

=（（〜A八〜B）V（CA〜D八〜B）V（-CADA-B）V

（〜A八〜C）V（CA〜DA〜C）V（〜CAD八〜C））A（〜CV〜D）

u>（（〜A八〜B）V（CA〜D八〜B）V（〜CAD八〜B）V

（〜A八〜C）V（〜CAD八〜C））A（〜CV〜D）

o（〜A八〜B八〜C）V（C八〜D八〜B八〜C）V（〜CAD八〜B八〜C）V

（〜A八〜C八〜C）V（〜CAD八〜C八〜C）V（〜A八〜BA〜D）V

（C八〜D八〜BA〜D）V（〜CAD八〜B八〜D）V（〜A八〜C/\〜D）V

（〜CAD△〜CA〜D）（由题意和矛盾律）

o（〜CAD八〜B）V（〜A八〜C）V（-CAD）V（C八〜D△〜B）

o（〜CAD八〜B/\A）V（〜C八D八〜B八〜A）V（〜A八〜CAB）V

（〜A八〜C八〜B）V（〜CAD八A）V（〜CAD八〜A）V

（C八〜DA〜B/\A）V（C△〜D八〜B八〜A）

=（〜CAD八〜BAA）V（〜A八〜CAB八D）V（〜A八〜C/\B八〜D）V

（〜A八〜C八〜BAD）V（〜A八〜CA〜B八〜D）V

（-CADAAAB）V（〜CAD八AA〜B）V（〜CAD八〜AAB）V

（〜CADA〜A/\〜B）V（C八〜D八〜BAA）V（C八〜D八〜B八〜A）

o（〜CAD八〜B八A）V（〜A八〜C八BAD）V（〜C/\DAA/\〜B）V

（〜CAD八〜A/\B）V：C八〜D八〜B/\A）

<=>（〜C/\D八〜B/\A）V（〜A八〜C/\B/\D）V（C/\〜D/\〜B/\A）

三种方案：A和D、B和D、A和C

1、（1）需证（PfQ）f（Pf（尸八。））为永真式

（3）需证—S为永真式

3、・.・A=B/.ATB为永真式。即~4丫3永真

~A\/BB\/~AB—A

/.4n3当且仅当~80~4

4、设：P：珍宝藏在东厢房

Q：藏宝的房子靠近池塘

R：房子的前院栽有大柏树

S：珍宝藏在花园正中地下

t：后院栽有香樟树

m：珍宝藏在附近(后院)

命题化后进行推理：

即S为真，珍宝藏在花园正中地下

5、(1)F(P=0,Q=1)(2)F(P=1,Q=R=O)(3)F(P=0,Q=1)

1.(1)~PrQ,R—Q0P—R

证：利用CP规则

①PP(附加前提)

②P

③Q7①②I

④R+QP

⑤〜R7③④I

⑥结论成立CP规则①⑤

(2)(PvQ)->(R/\S),(5VE)fBnPf3

证：①PP(附加)

②PVQT①

③(PvQ)f(R/\S)P

④RAS7②③

⑤ST④

⑥SVET⑤

⑦SVE-BP

⑧Br⑥⑦

⑨PTBCP(①⑧)

2.(2)P：无任何痕迹

Q：失窃时，小花在OK厅

R：失窃时，小英在OK厅

S：失窃时，小胖在附近

T：金刚是偷窃者

M：瘦子是偷窃者

命题可符号化为：

{P,QvR,QTT,-iSf-iR,R->M}

证：①PP

②S+PP

③~sr①②

(4)〜S+RP

⑤〜R7③④

@QvRP

⑦Q7⑤⑥

⑧QTTP

⑨T7⑦⑧

・・・金刚是窃贼。

3.(1)不相容

(2)相容(P=1,R=Q=S=O)

(3)不相容

(4)不相容

4.(1)证：(P.〜°)人(RvS)人(S.〜。)人(P-＞。)人尸

即①={~尸v〜Q,AvS,~Sv~Q,~Pv。，P}

利用消解原理：

①PP

②~Pv~QP

③~Q①②

④~PvQP

⑤~尸③④

⑥~尸人尸==F□①⑤

1.(l)A(x):x是实数B(x):x是有理数

⑵A(x}:工是直线

工与y平行G(x,y):x与y相交

(3)A(x)：x是会员C(x):x有意义

F(x,j)：x参加ya：这个活动

或者F(j,a))->-»C(a)

(4)A(x):x是正整数B(x):x是合数C(x):x是质数

(5)A(x)：x是人B(x)：x存钱a：利息

P：存钱有利息F(x,y):X想有)

2.(1)P(0)AP(l)AP(2)A(/?(0)v/?(1)vQ(2))

(2)[p(o)fG(O)]A[P⑴FG(I)]A[P(2)->e(2)

4.(1)°(y")]v(Vz)双x,y,z)

1.(1)D:数A(x):x=O/(X,J)=XJ

可满足式

⑵A（x）:x是诚实的人8（x）:x讲实话a：小林

可满足式

（3）4（x）:x不便宜夙力/是好货

R（x,y）:x买的ya：衣服b：小王

可满足式

（4）A（x）:x是作家夙x）：x懂得人性本质

C（x）:x是诗人£＞（x）:x是真正的

E（x）：x能刻画人们内心世界

F（x）：x很高明创作了y

a：莎士比亚b：哈姆雷特

2.（1）T

3.（1）F（2）T

4.。：实数P(x,y):y=e”,2(j)：j>0

1.(1)3x3y[P(x)fQ(>,)]

2.不成立

p(o)p(i)p⑵e(o)Q(I)。⑵

D={0,1,2)

o'i'oi'。'i

3•⑴〜((Vx)p(x)f0y)p(),))

o（VxXVy）«）八~尸60）—skolem范式

⑵〜依卜⑴一何胴炖出）

=（WxXVy）（女X4r）A~&y,z））------前束范式

=（Dx）（VyXMX）A~j）））-—skolem范式

1.（l）证：在某个解释下，口电工出）人Q（y）］取值1,必有a力，£）,

P（a）八00）,取值1,因此，3aP（a）取值1。

.♦.（3x）P（x）取值1,由定义，蕴含关系成立。

（2）①~（（*）M%）AQ（a））o~G%）P（x卜~Q（。）

（2）证：在某个解释下，~（（土）网％）人如））取值1

即（3x）P（x）A2（a）取值0,分二种情况：

i）（3x）P（x）=0,则无论2（a）为何值，（h）P（x）f~2（a）取值1。

ii）0（a）=0（3x）p（x）=l,则垓）p（x）f~0（a）取值1

由定义，蕴含关系成立。

1(2)(反证法)

①〜的风)-。^)]P

②(V.T)[P(R)TQ(x)]T①,E

③(~Nx)fvQ(x)]T②，I

④(VxXM%)八~如0)T③,I

⑤P(x)八〜Q(x)US@

⑥p(x)T⑤,I

⑦(Vx)p(x)UG@

⑧(Vx)p(x)f(女)如)P

⑨(Vx)Q(x)T⑧,I

⑩必)T@,I

OG(x)US⑨

口口T⑩CH

2.(1)错误，应换元，即

①(X7x)尸(x)f°(x),

②P(y)fQ(x)

(2)正确

(3)错误，a、b应是同一个常元

(4)错误，因为在尸⑴v(*)[Qa)/\R(x)]中x并不是自由出现

(5)错误，因为在&r)P(x)fQ(x)中，前件是命题，

而后件不是命题

(6)错误，因为a、b并不是同一个常量

(7)错误，①②和③④的顺序不对

应先使用ES,再使用US

3⑴解:设F(x,y):x2y;G(z):z20;f(x,y)=x-y

前提：

①V(x)X/(y)(F(x,y)fG(f(x,y))

②V(x)W(y)JF(x,y)f-iG(f(x,y))

③V(x)V(y)(-iG(f(x,y)fG(f(y,x)))

结论：V(x)V(y)(G(f(x,y))VG(f(y,x)))

证明(反证法)：

©-IV(x)V(y)(G(f(x,y))VG(f(y,x)))

②(3x)(3x)(G(f(x,y))VG(f(y,x)))

③—>G(f(a,b))A—«G(f(b,a))

@V(x)V(y)(F(x,y)fG(f(x,y))

⑤F(a,b)fG(f(a,b))

⑥-iG(f(a,b))f-iF(a,b)

⑦V(x)V(y)(-iG(f(x,y)fG(f(y,x)))

⑧-iG(f(b,a))fG(f(a,b))

(9)V(x)V(y)(-iF(x,y)--«G(f(x,y))

⑩「F(a,b)—G(f(a,b))

(11)G(f(a,b))fF(a,b)

(12)「F(a,b)AF(a,b)

4.(2)

证：首先，将结论否定否作为前提加入到原有前提中

A(~R(卬)v~R(y))]Skoiem范式

子句集为{~P(x)vR(x),~~(2(x)v-P(a\R(b\~~R(y)}

①〜叫丫叫

②尸⑷

③R(x)①,②代换{a/x}

④R(c)③代换{c/x}

⑤〜R(w)v~R()，)

⑥〜R(y)④,⑤代换{c/w}

⑦〜Me)⑥代换{c/y}

⑧口

(l)xG2AU2B=>xe2A或Xe1B

i=>xuA或xuB=>xczAlJB=>Jre24UB

\等

号成立的条件为:A邯B=。RI

关“n"xe24A2“=xe2A^\xe2B

性质、

xuA和x-B=tLAnB->1Vu24nB

自反性“一•济力Xhy=24n3由于y述过程/A2"

反自反性—，RAJ4i1&

XXXXV

对称性XJJVX

反对称性VXXXV

传递性VJJXV

2.(3)“=>"R是对称的，设〈3〉€夫则〈y,x〉eKn〈x,y〉eR7

<j,x>eR~x/.<x,j>€/?=><j,x>€7?,艮f)/?T=R

<="R=R-I由A”的定义，

：.(y,x)eRf即R是对称的。

(5)“n”R是传递的，对V<X,Z>GR2

即M£R

"U”R2±R,,对Vvx,y>GR<y,z>eR,由R”的定义,

有vx,z>wR2qR:.<x,z>eR,即R是可传递的。

4.解：・.R=KIUK2，且/?1门氏2=中

・,.屋=/儿肢=/&，・,・需31nb5|m

=>m=15,gpw=16

故使Rm=Rn的最小正整数机=1,n=16

2^解：

1

3.⑶证：,・"(与)=.号匕t(R2)=UR

i=l1i=lz

由归纳法可证：对VMN+K：UK；£(aUR2)i

JL乙

⑷证：①(R+y=R+*.R+=t(R)=UR1

由归纳法可证：V/eN+«(©)，=f⑻

③=R+,•R*=IAU，(K)

1.证：A=a,Z?eV+}

①自反性由A的定义，ab=baa,bwN

②对称性设((4”(c,d))wR,则ad=bc

即cb=da((c,d),(〃/))eR

③传递性设((%,瓦)(c/J)wK，则〃

((q,&),(c2d2))£R,则Id2=dxc2

3.解：・・・A={1,2,3,4,},So={{1,2,4},{3}}

设A={123,4},4={3}

4.解：・・•每个集合的划分就可以确定一个等价关系

・・・集合有多少个划分就可以确定多少个等价关系

4321a

C+C4-C+C=15种。

4444

5.解：

①《U%不是A上的等价关系

②与cE是A上的等价关系

③r(R「R2)是A上的等价关系

④不是A上的等价关系

3.解：集合A上的空关系中、恒等关系L都是等价关系和偏序关系。

6.解：A=(a,h,c,d)

7.证：i)自反性，对V力伍㈤GR,(R的自反性)

显然伍㈤e3x5:.(b,b)ERQBxB

ii)反对称性，对Va,8cB,(a9b)eRC\BxB^a)eRQBxB

即(a/)eK,伍㈤wR,由R的反对称性，=a=b

iii)传递性,对设(a㈤wRnbxb,(b,c)eBf

则(a,b)wR,(b,c)wRo

由R的传递性，(a,c)eK,显然(a,c)wbxb

4、证：

7、证：f:ArB,g:BfC

3.证明：(扉星新糠A雪商躺箝乐模启启也朝扳理好2)

即g。f&l)=g(/(X))=g(f(*2))=g°/(^2)

与g。/为单射矛盾

②七。加满射

证明：设A=国a2,…，aj

B={bi,b2,bn,…}

令Bi={(a“bi),(ai,b2),…，⑸,bn),•••}(iWn),则

AXB=OH,

r=l

因为B为可数集，所以Bi为可数集。AXB为有限个可数集的

并集。下面用归纳法证明有限个(m个)可数集的并集为可数集。

设—{C1,Cm2,Can,***}

CBB

当m=2时9

构造双射f：N-C】UC2,

N123456•••n-ln•・♦

f(N)CnC21C12C22C13C23…Cl(n/2)C2(n/2)…

所以2个可数集的并集为可数集。

假设ni=kT(k23)时结论成立，即k-l个可数集的并集为可数集，记

为D。

则m=k时，可以构造类似的双射g:N-DUCk,所以为可数集。因而有

限个可数集的并集为可数集。所以AXB是可数集。

1.设G是一个(n,m)简单图。证明：等号成立当且仅当G

是完全图.

证明：由欧拉定理，2m=伏)，d(k)表示第k个结点的度

*=i

因为G是简单图，所以d(k)等号成立当且仅当G是完全图

2m=沙Wtn-1,

*=1

所以2mWn(nT)

即=C：

3、解：(1)不是图的序列，因为奇数度结点的

个数不是偶数。

(2)、(3)、(4)都是图的序列。

4、证：由欧拉定理，2m=Xd(v)

9.若，称G是争舞啰变前留”殖的最低条件；画出一个

V€GV€G

自补图来。KG

二.n=2m<nA

解：设G=(n,m)；G

则m+m'=呜7秒咫，物以=n(n-l)/4

G

1、若U和V是图中仅有的两个奇度数结点，证明U和V必是连通的。

证：(反证法)设V与U不连通

AG={V1,V2},v与u分别属于VLV2二个子图

・・・V与U是G中仅有的二个奇数度结点

・・・v与u即是VI与V2中仅有的一个奇数度结点，与欧拉定理的

推论(9-相矛盾,故v与u必连通

3、设(n,m)简单图G满足m>(n-l)(n-2)/2,证明G必是连通图。构

造一个ni=(n-l)(n-2)/2的非连通简单图。

(书上证明更好)

5、设G=(V,E)是点度均为偶数的连通图。证明：对任何v£V,3(G-v)

Wd(v)/2

证：(反证法)设结论不成立,即存在：vev,o(G-v)>d(v)/2.

因为G是连通的，所以G-v的每个分支都至少有一个点与v相邻接,

而且存在一个分支，其与v相邻接的点只有一条边与v相连(因为如

每个分支中有二个以上的点与v相连，则VPW匕m,

---------------------------2---------

出现矛盾)

・,•存在一个分支，其中只有一条边与v相连；因为G中每个结点的度

数为偶数，所以在这个分支中就会出现一个奇度数结点，其余结点的

度数全为偶数，与欧拉定理的推论相矛盾，故故对任何v£V,s(G-v)

Wd(v)/2

9.证明：恰有两个非割点的简单连通图必是Pn(n22)

证明：归纳法。

n=2时，结论显然成立。

设n=k时结论成立，

当n=k+l时，设0、Vk是Pk上的两个非割点，Vk+i是在Pk上增

加的一个割点，如果结点Vk”不在Pk上的任意两个结点之间，则必与

Pk上某两个结点构成一个回路，Vk“就不是割点，与只有两个非割点

矛盾。故结论成立。

3、解：

X

三个强分图J

-

e8e

5.证明：支数为k,阶数为n的无环图G,其关联矩阵的秩是n-k.

证明：将各支结点和边集中编号后，G的关联矩阵

由分块矩阵子公式及定理，

Y(M)=y(MI)+Y(㈤+…+丫(Mk)

=(n-1)+(n2-l)+-+(nk-l)

=n-k

1、设一个树中度为k的结点数是nk,求它的叶的数目。

解：设L是叶的数目，1n是树的边数，由Euler定理：

由树的定位knk+L=2m

k=2

6、证明正则二叉树必有奇数个结点。

证明：由正则二叉树的定义，其叶结点的个数必为偶数，设叶数

为3分支数为i。

：(m-1)i=t-l

Vm=l/.i=t-l有分支点数是奇数

故结点数4+弋=奇数

3、证：(反证法)

设6=(n,m)和G'=(n,m,)都是平面图

由G的定义m+m'=n(n-l)/2

由定理10^3n-6,m'<3n-6

:.m+m,=n(n-l)/2<6nT2

有n2-13n+24=(n-11)2+9n-97WO

又,:(n-11)220,n211时，9n-9722

:.(n-ll)2+9n-9722

与上式相矛盾，故G与1至少有一个是非平面图

4、证明：具有6个结点，12条边的简单连通平面图，它的面度都是

3。

证：由Euler公式，n-m+f=2

••・6-12+f=2f=8,即面数为8。

•・•对每个面，其度数23

・•・总面度23X8=24

・・•总面度=2Xm=24

・••每个面的度数为3

5、少于30条边的简单平面图至少有一个顶点的度不大于4。

证：(反证法)设所有顶点的度数5

由Euler公式，

由定理10<3n-6

3n—625n/2即n212

则m25n/225X12/2=30与mV30矛盾

因此，至少存在一个顶点的度数不超过4。

2、证明：4k+1阶的所有2k正则简单图都是哈密顿图。

证：VG是2k正则图，

/.对任意的u、v£G,d(u)+d(v)=4k

由定理10-6-2在G中存在一条Hamilton道路，设为：

ViV2,•・・,V4k+1

1)ViV4k”£E,贝(IViV2,-,V4k+iVi构成一个Hamilton圈

2)ViV4k+i史E,则玉与匕邻接

,:G的阶数为4k+l

，M+1必与”1，…,4T中的一个点邻接

(否贝!|d(v4k+i)=4k-l-2k=2k-l与d(v妹+D=2k矛盾)

设HJ4A+1eE，可构造匕，…匕Ll#4A+J4A〃・#i/l

即为G的一个Hamilton圈，故G是一个Hamilton图

5、设G是(n,m)简单图，若〃/N。之！+2，证明G必是哈

密顿图。

证：(反证法)假设G不是哈密尔顿图，则

因为G除结点s,t外的其余n-2结点之间最多可以构成完全

图，所以2m<(n_2)(n-3)+n+n<n2_3n+6=(n-l)(n-2)+4

从而：]

与已知您:宅：妈潘,)蓝鬲隘史

4.设〈S,。是一个含有幺元e的代数系统，a£S.如果存在元b,c£S

使b•a=e(或a•c=e),则称b是a的左逆元(或c是a的右逆元)。证

明：如果一个元既有左逆元b又有右逆元c,则必b=c.

证明：S上的运算•是可结合的。

b=b•e=b•(a•c)=(b•a)•c=e•c=c

4、设半群<A,•>中任何两个不同元素关于运算“•”不可交换，证明:

对任何a^A,a•a=a

证明：(反证法)

设ma£A,使得a•aWa,构造b=a•a,贝(J

a•b=a•a•a=b•a

即a、b可交换，与已知条件相矛盾

：・Va^A,a•a=a

5.设S={00,111,1010}是字符集2={0,1}上的字集合。试构造2*的一

个包含集合S的最小的含幺子半群。

解：令空字符为入.m,n,k为正整数，

T={X,(00)m,(lll)n,(1010)k}U{(00)m(lll)n(1010)k}

U{(00)ra(1010)k(lll)n}U{(lll)n(00)m(1010)k}

u{(m)n(ioio)k(oo)m}u{(ioio)k(oo)mdn)n}

u{(ioio)kdn)n(oo)m)

1、证明：群中只有幺元是嘉等元。

证：（反证法）

设A,。=a，

va'3,’=e

=矛盾

5、写出J的全部子群。

解：〈(1),(12)),〈(1),(13)),〈(1),(23)),

＜(1),(123),(132)〉和二个平凡子群。

6、设部,・＞和"，•＞都是＜G,•＞的子群，令SAT={xlxWSASW

T},ST={s＞tlseSAtei},证明：＜{SAT},•＞$1＜ST,•＞也都

是＜&•＞的子群。

证明：1)・・・S、T是G的子群

・・・eeS,eeT即eeSAT

设a,beSAT.即a,beS和a,beT

b-1GS和b-lwTJ