离散数学及其应用(课后习题)

习题1.1

2.指出下列命题是原子命题还是复合命题。

（3）大雁北回，春天来了。

（4）不是东风压倒西风，就是西风压倒东风。

（5）张三和李四在吵架。

解：（3）和（4）是复合命题，（5）是原子命题。

习题1.2

1.指出下列命题的真值：

（1）若2+2>4,则太阳从西方升起。

解：该命题真值为T（因为命题的前件为假）。

（3）胎生动物当且仅当是哺乳动物。

解：该命题真值为F（如鸭嘴兽虽是哺乳动物，但不是胎生动物）。

2.令P：天气好。Q：我去公园。请将下列命题符号化。

（2）只要天气好，我就去公园。

（3）只有天气好，我才去公园。

（6）天气好，我去公园。

解：（2）P―>Q。

（3）Q—»P。

（6）PC。。

习题1.3

2.将下列命题符号化（句中括号内提示的是相应的原子命题的符号表示）:

（1）我去新华书店（P）,仅当我有时间（。）。

（3）只要努力学习（P）,成绩就会好的（。）。

（6）我今天进城（尸），除非下雨（。）。

（10）人不犯我（P）,我不犯人（。）；人若犯我，我必犯人。

解：（1）P-»Q。

（3）PTQ。

（6）—\Q—>Po

（10）（—\P—>―iQ）A（P-■

习题1.4

1.写出下列公式的真值表:

(2)PvfR)。

解：该公式的真值表如下表:

pQRQfRPv(QfR)

00011

00111

01000

01111

10011

10111

11001

11111

2.证明下列等价公式：

(2)(PvQ)人「(PAQ)。一^^―。)。

证明：

」(PC。)=->((PA。)VA[0))

=「(PA。)人一•(-1P人]。))

U>「(PAQ)A(PV。)

=(PV。)人」(PA0)

(4)(PfO)A(PfR)oPf(QAR)。

证明：

(PfQ)A(PfBOJPVSAJPVR)

0->PV(QAR)

=Pf(。人R)

3.甲、乙、丙、丁4人参加考试后，有人问他们谁的成绩最好，甲说，不是我。乙说：是

丁•丙说：是乙。丁说：不是我。已知4个人的回答只有一个人符合实际，问成绩最好的是

谁？

解：设A：甲成绩最好。乙成绩最好。C：丙成绩最好。O：丁成绩最好。

四个人所说的命题分别用尸、Q、RS表示，则

P—iA；Q<=>—iAA―\BA—\CAD；R<=>—\AABA―\CA-\D；S<=>―iD。

则只有一人符合实际的命题K符号化为

K<=>(PA—iQA—i/?A—iS)V(—iPA0A—i/?A—iS)V(—iPA—1。A/?A-iS)V(—iPA—1。A—i/?AS)

PA―\QA—\RA—\S-IAA-i(-IAA-IJBA"—\CAD)A—1(—IAAA-iCA―i£))A£)

<=>-iAA(4vBvCv-i£>)A(Av「BvCVD)AD

今(-iAAZ))A(AvBvCv-J))A(Av-iBvCvD)

0(-v4ABACAZ))V(-V4ABAD)V(-IAA-IBACAD)V(-IAACAD)

oO;

同理，

—IJPA<2A—I/?A-ISAA—I/4A—iBA—iCAA)A—1(—iAABA—iCA—J9)AO0;

—iPA—1。A/?A—iS<=>AA_1(—iAA—iBA—iCA。)A—iAABA—iCA—iDAZ)<=>0；

―\PA―I。A—iRASA,A-1(—iAA—\BA-iCAD)A—1(—iAABA—iCA-iD)A—J)

<=>AA(AvBvCv-J))A(Av-iBVCVZ))A-IZ)

AA-\D,

所以，当K为真时，4人「。为真，即甲的成绩最好。

习题1.5

2.证明下列各蕴含式：

(3)Pf(QfR)=(PfQ)f(PfK)。

证明：

方法一：真值表法(列出命题公式(尸f(Qf/?))->((Pf。)f(Pf/?))的真值表)。

PQRPT。PTR0TKPT(QTR)(PTQ)T(PTR)

000111111

001111111

010110111

011111111

100001111

101011111

110100001

111111111

方法二：等值演算法

(P->(QfR))f((P->?)-»(PfR))

oTP->(QfR))v((P—Q)f(P->R))

Ov(—iQvR))v—1(—iPvQ)v(—iPvR)

=(PA<2A-iZ?)v(PA-I0)V(—>/>v/f)

=(PAQA-17?)v((Pv—iPvZ?)A(—1。v—iPvR))

=(PAQA-1/?)V(-10V-iPVR)

0(Pv—iQv—iPvR)v(Qv—iQv—iPv7?)v(—>Rv-iQv-iPvR)

o1.

方法三：分析法

(1)直接分析法：若前件Pf(QfR)为真，分两种情况：

(I)尸为假，则尸一>。为真，P—R为真，(PfQ)-»(PfR)为真。

(II)尸为真，则QfR为真，此时若。为真，则R为真，则Pf。为真，PTR为

真，(PfQ)f(PfR)演；若。搬，则PfR为假，(PfQ)f(PfR)

为真。

综上，若前件为真，后件必为真，故该蕴含式成立。

(2)间接分析法：若后件(Pf。)-»(PfR)为假，则尸一。为真，PfR为假。由

PfR为假可知，P为真,R为假。再由尸一>。可知，。为真。此时0fR为假，

Pf(QfR)为假，即前件为假。故蕴含式成立。

5.叙述下列各个命题的逆换式和逆反式，并以符号写出。

(1)如果下雨，我不去。

解：设P：天下雨。Q：我去。

逆换式：如果我不去，天就下雨。符号表示为-»p。

逆反式：如果我去，天就不下雨。符号表示为0T「尸。

(2)仅当你走我将留下。

解：设P：我留下。Q：你走。

逆换式：如果你走，我就留下。符号表示为：2f尸。

逆反式：如果你不走，我就不留下。符号表示为：「。一>->尸。

习题1.6

2.将下列命题公式用只含V和「的等价式表达，并要求尽可能简单。

(1)(P/\Q)A-\P•

解：(尸人。)人一!尸=(尸八一1尸)人。=0人。=0.

(2)(P->(Qv-i/?))A-\PAQ,

解：(Pf(Qv-iK))人「尸八2=

。(-|PV(2V—iR)A-1PAQ=(-|PA-|PA0)V(-1PA0A0)V(-iPA0A-i/?)

=(「PA2)V(-IP/\2)V(-IPAQA「K)=(「PA2)V(「P/\2A「K)

=(一|尸A0)V(一1尸A0A—iR)=-1尸AQ

=TPv「O).

(3)―\PA-\QA(―\R―»P).

解：一iPA「2/\(「RfP)=」PA-i0A(/?vP)

。(-|PA-iQA/f)V(-|PA-10八P)。(-|PA-iQA/?)V0

=-tPA-iQ人R=-i(Pv0V

习题1.7

6.求下列命题公式的主析取范式和主合取范式：

(1)((Pv。)-R)f尸,

解：((Pv。)-R)fP=TTPv?)vR)vP

=((PvQ)/\T?)vP=(PvQvP)/\(PvM)=(Pv2)/\(PvT?)

=(PV0V(7?A-iUJ))A(PV(2A-I0)v-J?)

=(PV0V7?)A(PV0V-IJR)A(PV2V-d?)A(PV-10v-d?)

=(尸v。vK)八(Pv。v-uR)A(Pv-i。v—iR)

0Mo人加1人知3(主合取范式)

m2vvm5v/w6vm7.(主析取范式)

习题1.8

1.证明（」Pv「。）人（「尸一＞R）A（Rf-1s）=Sf[0.

证明：(1)sp（附加前提）

(2)R―>—iSp

(3)S—>―JiT(2)E

(4)T(1)(3)I

(5)-uPfRP

(6)PT(5)E

(7)PT(4)(6)I

(8)—iPv—iQP

(9)-'QT(7)(8)I

(10)CP

2.用间接证法证明Pf（[0-»R）,Q--iP，S—>―iR，P=―\S.

证明：(1)sp(附加前提)

(2)Sp

(3)-)/?T(1)(2)I

(4)PP

(5)P—>(-iQ—>R)P

(6)—iQ—>RT(4)((5)I

⑺。T(3)(6)I

(8)QfMP

⑼「pT(7)(8)I

(10)PA-1P(矛盾式)T(4)(9)I

由（10）得出了矛盾，根据归谬法说明原推理正确。

5.“如果下雨，春游就会改期：如果没有球赛，春游就不会改期。结果没有球赛，所以没有

下雨。”证明上述论断正确。

解设P：下雨。0：有球赛。R：春游改期。则上述论断转化为要证明PTR,

—iQ=—iP.

证：⑴一p

(2)P

(3)-iRT(1)(2)I

(4)PTRP

(5)—\PT(3)(4)I

因此，上述推理正确。

7.证明RvS是前提Cv0,CTR,OfS的有效结论。

证明：(1)CvDP

(2)T(1)E

(3)DTSP

(4)-.C-»ST(2)(3)I

(5)CTRP

(6)—\R―>—\CT(5)E

(7)—\R―>ST(4)(6)I

(8)R7sT(7)E

习题2.1

用谓词表达式写出下列命题：

(5)每个有理数是实数。

解：Vx(Q(x)fR(x)),其中Q(x)：x是有理数。R(x)：x是实数。

(6)有的函数连续。

解：3X(F(X)AC(X)),其中尸(x)：x是函数。C(x)：x连续。

习题2.2

2.将下列命题符号化：

(3)没有人登上过木星。

解：设M(x)：x是人。A(x)：x登上过木星。则命题可表示为T3O(M(x)人A(x)).

3.符号化下列命题：

(2)尽管有人聪明，但未必一切人都聪明。

解：设M(x)：x是人。C(x)：x聪明。则命题可表示为

3x(M(x)AC(X))A-nVx(M(x)->C(x)).

习题2.3

2.对下列谓词公式中约束变元进行换名：

(1)Vx3j(P(x,z)->0(j))oS(x,j)

(2)(Vx(P(x)f(R(X)VQ(X)))ANAx))f土S(X,Z)

解(1)Vw3v(P(w,z)0(v))<4-5(x,j)

(2)(Vw(P(w)—>(!?(«)v<2(«)))A3vl?(v))-»3zS(x,z)

3.对下列谓词公式中自由变元进行代入：

(1)Vx^tr,z))A3xVzC(x,y,z)

(2)(VJP(X,J)A3Z0(X,Z))VVXgy)

解(1)(3jA(s,j)->Vxfi(x,w))A3XVZC(X,/,Z)

⑵(VyP(s,y)人士。(s,z))vVxR(x,f)

习题2.4

3.证明下列等价式：

(1)-i3r(P(X)A0(x))=Vx(p(x)f-i(2(x)).

证明:-3X(P(X)AQ(X))

0Vx「(P(x)人。(x))

oVx(「P(x)v[Q(x))

oVx(P(x)f[0(x))

(2)-iVx(P(X)->2(x))O3x(p(x)A-I0(x)).

证明：-1Vx(P(X)TQ(X))

o3x「(P(x)f0(x))

o3x->(-iP(x)vo(x))

o女(P(X)A「Q(X))

习题2.5

求下列谓词公式的前束析取范式和前束合取范式：

(1)(Vx)P(x)->(3x)g(x).

解：(Vx)P(x)f0x)0(x)

O-i(Vr)P(X)V(3x)(2(x)

o(3x)-iP(x)v(3x)(2(x)

00X)(-1P(x)vQ(x))(前束析取范式、前束合取范式)

(2)(Vx)(Vj)((3Z)(P(x,z)AP(j,z))v(3M)e(x,y,u)).

证明：(Vx)Wy)((土)(P(x,z)AP(y,z))v0〃)Q(x,yM)

o(Vx)(Vy)0z)((P(x,z)AP(y,z))v0“)2(x,y,w))(辖域扩张)

="x)(Vy)(女)0w)((P(x,z)AP(y,z))vQ(x,y,“))(辖域扩张)(前束析取范式)

=(Vx)(Vj)(3z)(3w)((P(x,z)vg(x,J,H))A(P(j,z)v0(x,j,«)))(前束合取范式)

习题2.6

1.证明下列各式。

(2)Vx(A(x)vJB(x)),x6(x)VxA(x).

证明：(1)VxC(x)p

(2)C(«)US(1)

(3)Vx(8(x)->-1c(x))p

(4)B(a)―>―\C(a)US(3)

(5)^B(a)T(2)(4)I

(6)Vx(A(x)vB(x))P

(7)A(a)vS(a)US(6)

(8)A(«)T(5)(7)I

(9)VxA(x)UG(8)

2.符号化下列命题并推证其结论。

(3)所有有理数是实数，某些有理数是整数，因此，某些实数是整数。

解：设0(x)：x是有理数。/?(x)：x是实数。Z(x)：x是整数。则命题可符号化为:

Vx(0(x)-»/?(x)),3X(0(X)AZ(X))=>3X(/?(X)AZ(X))Q

证明如下：

(1)3X(0(X)AZ(X))p

(2)2(C)AZ(c)ES(1)

(3)Vx(Q(x)fR(x))P

(4)2(C)fR(c)US(3)

(5)2(c)T(2)I

(6)R(c)T(4)(5)I

(7)Z(c)T(2)I

(8)R(C)AZ(C)T(6)(7)I

(9)3X(7?(X)AZ(X))EG(8)

(4)每个大学生不是文科生就是理科生，有的大学生是优等生，小张不是理科生，但他是

优等生，因此如果小张是大学生，他就是文科生。

解：设S(x)：x是大学生。A(x)：X是文科生。B(x)：x是理科生。C(x)：x是优等

生。，2：小张。该命题可符号化为：

Vx(S(x)A(x)vB(x)),3x(S(x)AC(X)),-JS(a),C(a)=>S(a)—>4(。)。

证明如下：

(1)Vx(S(x)->A(x)vB(x))p

(2)S(a)->A(«)vB(«)US(3)

(3)S(«)附加前提

(6)T(4)(5)I

(7)「B(a)P

(8)A(«)T(6)(7)I

(9)S(«)->A(a)CP

习题3.1

3.确定下列命题是真还是假，并简要说明为什么。

(1)0C0(2)0e0(3)0e{0}(4)0c{0}

解(1)该命题为真，因为0是任何集合的子集。

(2)该命题为假，因为。不包含任何元素。

(3)该命题为真，因为。属于集合{0}。

(4)该命题为真，因为0是任何集合的子集。

6.求下列集合的募集：

⑵{1,0}(3){0,{0}}

解(2)该集合的募集为{0,{1},{0},{1,0}}。

(3)该集合的塞集为{0,{0},{{0}},{0,{0}}}

习题3.2

6.证明下列等式：

(4)A-(B-C)=(A-B)u(AryC).

证明：A-(B-C)=A-(BnC)=An(BnC)

=An(BuC)=(AnB)o(AnC)=(A-B)o(AnC)

因此，A—(B—C)=(A-B)kJ(AoC)o

(5)A-(BnC)=(A-B)u(A-C)o

证明：A-(BnC)^An(BnC)=An(BuC)

=(AnB)u(AnC)=(A-fi)u(A-C)o

因此，A-(BnC)=(A-B)u(A-C)o

(8)(AuB)n(AuC)=(AnC)u(AnB)o

证明：(AuB)c(ZuC)

=((AuB)nA)o((AoB)nC)

=(AnA)u(AnB)u(AnC)o(BnC)

=(AnB)u(AnC)u(BnC)

=(AnC)u(AnB)o[(BnC)n(AoA)]

=(AnC)u(AnB)o(BnCnA)o(BnCr>A)

=[(AnC)o(AnBnC)]u[(AnB)u(AnBnC)]

=(AnC)u(AnB)

因此，(Au3)c(ZuC)=(AcC)u(Zc3)。

习题3.4

3.下列等式能否成立？

(3)(BnC)xA=(BxA)n(CxA)o

解：该等式成立。证明如下：

设<*,9>€(30。)、4<^>xeBnCAyeA

<^>xeB/\xeC/\yeA

<=>(xe^AjeA)A(xeCAjeA)

=<x,y>eBxAA<x,y>eCxA

=<x,y>e(BxA)n(CxA)

因此，(8cC)xA=(3xA)c(CxA)。

(4)(BuC)xA=(BxA)u(CxA)o

解：该等式成立。证明如下：

设<*,9>€(3。。)、4<^>xeBuCAyeA

<^>(xeB\/xeC)/\yeA

<=>(xe^AjeA)v(xeCAjeA)

=<x,y>efixAv<x,y>eCxA

O<x,y>e(BxA)u(CxA)

因此，(8uC)xA=(BxA)u(CxA)。

习题3.5

1.对于下列各种情况，用列举法求出X到¥的关系S、domS、ranS,触S的关系图,

写出S的关系矩阵。

(1)X={0,1,2},♦={0,2,4},S={<x,y>\x,jeXnK).

解：S={<0,0>,<0,2>,<2,0>,<2,2>},

domS={0,2},ranS={0,2}0

关系图如下：

习题3.6

5.设X={a,b,c,d},X上的关系R的关系矩阵如下，试问R是不是自反的、反自反的、

对称的、反对称的和传递的？

’0101、Toil、

00000101

(1)(4)

10011011

、0100,Jill;

解（1）R是反自反的、反对称的、非传递的。因为％=1,。=1,但％=。。

（2）R是自反的、对称的、非传递的。因为勺=1,2=1，但「32=°。

习题3.7

5.(1)设X={a,A,c},X上关系R的关系矩阵是

‘101、

MR=110

J11,

试求出MR°R°R。

习题3.9

4.设X={1,2,3,4,5},试根据以下X的划分求X上相应的等价关系，并画出关系图。

(3){{1},{2},{3,4,5})

解：⑴X{1}={<1,1>}

&={2}x{2}={<2,2>}

R3={3,4,5}x{3,4,5}={<3,3>,<3,4>,<3,5>,<4,3>,<4,4>,<4,5>,

<5,3>,<54,>,<55,>}

R=4uR?D&={<1」>，<2,2>,<3,3>,<3,4>,<3,5>,<4,3>,

<4,4>,<4,5>,<53,>,<54,>,<55,>}

关系图如下：

3

习题3.10

1.对于下列集合上的“整除”关系，画出其哈斯图。

(1){1,2,3,4,6,8,12,24)

解：该整除关系的哈斯图如下：

习题4.1

1.指出下列各关系是否为x到y的函数：

(1)X=Y=N,Z?={<x,j>1(xeX)A(j€¥)A(x+j<100)}.

(3)X={1,2,3,4}'y=XxX,Rx={<1,<2,3»,<2,<3,4»,<3,<1,4»,<4,<2,3»},

R2={<1,<2,3»,<2,<3,4»,<3,<2,3»).

解(1)R不是从x到y的函数；

(2)段是从x到y的函数，&不是从x到丫的函数。

习题4.2

1.设Z+，Z,R,C分别表示正整数集、整数集、实数集、复数集，试指出下列映射中

哪些是单射、满射、双射，并写出定义域和值域。

(1)/:2-2+为/(*)=|2*|+1。

(2)于：RfR为/(x)=cosxo

冗

(4)f:为/(x)=cosxo

2

解(1)为一般映射，定义域为Z,值域为{yly=2A+l,AGN}。

(2)为一般映射，定义域为R,值域为

(4)为单射，定义域为值域为［0,1］。

2

习题4.3

4.设〉={1,2,3,4}。

(3)能否找到另一gH/x的单射g：XfX,有gog=/x?

解:能。例如g={<l,2>,<2,l>,<3,4>,<4,3>}。

(4)试定义一个映射X使/2=/且/。/、。

解：例如/={<1,2>,<22,>,<33,>,<44,>}。

习题7.1

1.设无向图G=<V,E,/>,V={v1,v2,--,v6},E={e1,e2,—,e6},(p(el)=(vl,v2),

(p(e2)=(v2,v2),<P(e3)=(v2,v4),夕(64)=(〃,%),(p(e5)=(v3,v4),夕(0。=(匕，匕)。

(1)画出G的图形。

(2)求G的各节点的度数，并验证握手定理。

(3)G是否是简单图？

(2)deg(v,)=2,deg(v2)=4,deg(v3)=2,deg(v4)=3deg(v5)=l,deg(v6)=0»

6

?deg（匕）=12,2\E\=U,握手定理成立。

i=l

（3）图G中存在环，故G不是简单图。

4.下面各图有几个节点？

（2）21条边，3个度为4的节点，其余都是度为3的节点。

解：设度数为3的节点个数为x,

由握手定理，2x21=3x4+3》

解得x=10

故该图有13个节点。

习题7.2

4.分别指出图7-32中的3个图分别属于哪种类型（强连通，单侧连通，弱连通）。

（a）（b）

解（a）是强连通的，（b）是单侧连通的，（c）是弱连通的。

习题7.3

1.图7-39给出了一个有向图，试求

（1）邻接矩阵。

（2）A4,并找出从！到。长度

为1、2、3、4的路各有几条？

（3）可达性矩阵。

’0111、「0101、'0212、

020100110122

A3=•—

011101010212

、0011,k0100?即20"

’0212、’0101、’0323、

012200110413

A4=•=

021201010323

、0201,100,<0122,

从邻接矩阵及其幕可知，从匕到0长度为1的路有1条，从匕到,长度为2的路有1条，

从%到匕长度为3的路有2条，从匕到0长度为4的路有3条。

(3)令5=4+屋+工+工,

’0747、‘0111、

07470111

则8=,可达性矩阵尸=

07470111

、0434,、0111>

习题7.4

2.确定〃取怎样的值，完全图有一条欧拉回路。

解：完全图K,,有一条欧拉回路的充要条件是每个节点的度数都是偶数。而在爪“中，每个

节点的度数都是〃-1。故当〃为奇数时，完全图叫，有一条欧拉回路。

习题7.6

5.设G是一个连通平面图，它有〃个节点，机条边，且每个面山欠条边围成。试证

k(n-2)

tn-o

k-2

证明：设图G有，个面，由平面图的面的次数的定理，

r

2m=y^deg(7?;)=Arr.(1)

i=l

再由欧拉定理，

〃-m+r=2.