离散数学(左孝凌)课后习题解答

第1章习题解答

离散数学~

习题1.1

1.下列句子中，哪些是命题？哪些不是命题？如果是命题，指出它的真值。

（1）中国有四大发明。

（2）计算机有空吗？

⑶不存在最大素数。

（4）21+3<5o

（5）老王是ft东人或河北人。

（6）2与3都是偶数。

⑺小李在宿舍里。

⑻这朵玫瑰花多美丽呀！

（9）请勿随地吐痰！

（10）圆的面积等于半径的平方乘以。

（11）只有6是偶数，3才能是2的倍数。

⑫雪是黑色的当且仅当太阳从东方升起。

⑬如果天下大雨，他就乘班车上班。

解：⑴⑶⑷⑸⑹⑺（10）（11）（⑵⑬是命题，其中⑴⑶⑩（1D是真命题，⑷⑹⑫是假命题，（5）⑺

⑬的真值目前无法确定；⑵⑻⑼不是命题。

2.将下列复合命题分成若干原子命题。

⑴李辛与李末是兄弟。

⑵因为天气冷，所以我穿了羽绒服。

⑶天正在下雨或湿度很高。

（4）刘英与李进上ft。

⑸王强与刘威都学过法语。

（6）如果你不看电影，那么我也不看电影。

⑺我既不看电视也不外出，我在睡觉。

（8）除非天下大雨，否则他不乘班车上班。

解：⑴本命题为原子命题；

（2）p：天气冷；q：我穿羽绒服；

（3）p:天在下雨；q:湿度很高；

⑷p：刘英上ft；q：李进上ft;

⑸p：王强学过法语；q：刘威学过法语；

（6）p：你看电影；q：我看电影；

（7）p：我看电视；q：我外出；r：我睡觉；

（3）p:天下大雨：q：他乘班车上班。

1

第1章习题解答

3.将下列命题符号化。

⑴他一面吃饭，一面听音乐。

⑵3是素数或2是素数。

⑶若地球上没有树木，则人类不能生存。

(4)8是偶数的充分必要条件是8能被3整除。

⑸停机的原因在于语法错误或程序错误。

(6)四边形A8CZ)是平行四边形当且仅当它的对边平行。

(7)如果。和是偶数，贝IJ。+〃是偶数。

解：(1)p；他吃饭；q；他听音乐；原命题符号化为；〃

⑵P：3是素数；q：2是素数；原命题符号化为：p\Jq

(3)p：地球上有树木；c/：人类能生存；原命题符号化为：1g

⑷p：8是偶数；q：8能被3整除；原命题符号化为：pig

⑸p：停机：q：语法错误；八程序错误；原命题符号化为：q\/Lp

(6)p：四边形ABCD是平行四边形；g四边形ABCD的对边平行；原命题符号化

为：piq。

⑺p：a是偶数；q：b是偶数；r：a+b是偶数；原命题符号化为：p/\q^r

4.将下列命题符号化，并指出各复合命题的真值。

(1)如果3+3=6,则雪是白的。

(2)如果3+3W6,则雪是白的。

(3)如果3+3=6,则雪不是白的。

⑷如果3+3W6,则雪不是白的。

⑸4是无理数当且仅当加拿大位于亚洲。

⑹2+3=5的充要条件是4是无理数。(假定是10进制)

⑺若两圆O「O的面积相等，则它们的半径相等，反之亦然。

⑻当王小红)情福快时，她就唱歌，反之，当她唱歌时，一定心情愉快。

解：设p：3+3=6。q：雪是白的。

⑴原命题符号化为：pfq；该命题是真命题。

(2)原命题符号化为：仍该命题是真命题。

(3)原命题符号化为：〃f->q；该命题是假命题。

(4)原命题符号化为：该命题是真命题。

⑸P：陋■是无理数；q：加拿大位于亚洲；原命题符号化为：〃1夕；该命题是假命

题。

⑹p：2+3=5；q：y/3是无理数；原命题符号化为：pig;该命题是真命题。

⑺p：两圆O]Qi的面积相等；q：两圆O1,O)的半径相等；原命题符号化为：pig;

该命题是真命题。

(8)p:王小红心情愉快；q：王小红唱歌；原命题符号化为：该命题是其命题。

2

第1章习题解答

习题1.2

1.判断下列公式哪些是合式公式，哪些不是合式公式。

(1)(pAq-r)

⑵

⑶q)一(~s))

⑷(p/\q—rs)

⑸((pf(qfr))-*(付-p)-qVr))。

解：⑴⑶⑸是合式公式；⑵⑷不是合式公式。

2.设p：天下雪。q：

我将进城。r：

我有时间。

将下列命题符号化。

⑴天没有下雪，我也没有进城。

⑵如果我有时间，我将进城。

⑶如果天不下雪而我又有时间的话，我将进城。

解：(1)->pA->q

(2)r—q

(3)-npAr-*Q

3.设p、q、r所表示的命题与上题相同，试把下列公式译成自然语言。

⑴人

(2)」(rVq)

⑶q一(rA-'p)

(4)(q-*r)A(r-*q)

解：⑴我有时间并且我将进城。

⑵我没有时间并且我也没有进城。

⑶我进城，当且仅当我有时间并且天不下雪。

⑷如果我有时间，那么我将进城，反之亦然。

4.试把原子命题表示为p、q、r等，将下列命题符号化。

⑴或者你没有给我写信，或者它在途中丢失了。

⑵如果张三和李四都不去，他就去。

⑶我们不能既划船又跑步。

(4)如果你来了，那末他唱不唱歌将看你是否伴奏而定。

解：(Dp：你给我写信；q：信在途中丢失；原命题符号化为：(「p/\「q)V(pAq)。

⑵p：张三去;q：李四去；r：他去；原命题符号化为：r。

3

_________________________________第1章习题解答

(3)p：我们划船；q：我们跑步；原命题符号化为：「(pAQ)o

(4)p：你来了；q：他唱歌；r：你伴奏；原命题符号化为：pf(qr)。

5.用符号形式写出下列命题。

⑴假如上午不下雨，我去看电影，否则就在家里读书或看报。

⑵我今天进城，除非下雨。

⑶仅当你走，我将留下。

解：(1)p：上午下雨；q：我去看电影；r：我在家读书；s：我在家看报；原命题符号

彳a：Jp-q)A(pfrVs)。

⑵p：我今天进城；q：天下雨；原命题符号化为：［q

(3)p：你走；q：我留、；原命题符号化为：q-*p>

4

第1章习题解答

习题1.3

1.设/、B、。是任意命题公式，证明：

(2)若贝ljBo/

⑶若BoC,贝JA<=>C

证明：⑴由双条件的定义可知是一个永真式，由等价式的定义可知AoA成立。

⑵因为4。以由等价的定义可知A-8是一个永真式，再由双条件的定义可知F-A

也是一个永真式，所以，BoA成立。

(3)对A、B、C的任一赋值，因为AoB,则4-B是永真式，即4与B具有相同的真

值，又因为BoC,则B-C是永真式，即8与C也具有相同的真值，所以4与C也具有

相同的真值：即40c成立。

2.设4、0、。是任意命题公式，

(1席AoB一定成立吗？

(2诺4ACu>8/\C,力。8一定成立吗？

⑶若%<=>r8,4<=>8一定成立吗？

解：⑴不一一定有艮若A为真，B为假，C为真，则AVCoBVC成立，但力

不成立。

⑵不一定有若A为真，B为假，C为假,贝IJAACoBAC成立，但4=8不

成立。

⑶一定有/4u>Bo

3.构造下列命题公式的真值表，并求成真赋值和成假赋值。

⑴q八(pfq)fp

(2)p-*(qVr)

(3)(pVq)(qVp)

⑷(pA-.q)V(rA(?)->r

(5)(「p-(。八方))->r)V(q/\rr)

解：⑴q/\(pTq)Tp的真值表如表1.24所示。

表1.24

PqpTqqnq)q/\(pTq)Tp

00101

01110

10001

11111

5

_______________________________________第1章习题解答

使得公式夕八(pTq)Tp成真的赋值是：00，10,11,使得公式qA(/2Tq)-►〃成假的赋

值是：01O

(2)〃-你\/力的真值表如表1.25所示。

表1.25

Pqrr/VrL(“Vr)

00001

00111

01011

01111

10000

10111

11011

11111

使得公式〃一(qVr)成真的赋值是：000,001,010,011,101,110,111,使得公式

〃-0"厂)成假的赋值是：100。

(3)仍VM-OVp)的真值表如表1.26所示。

表1.26

Pqp\qSV")一("Vp)

00001

01111

10111

11111

所有的赋值均使得公式SVMTqVp)成真，即SVq)一(qVp)是一个永真式。

⑷仍八「切V(/7\q)-r的真值表如表1.27所示。

表1.27

pqrp"qrNq(pA^)V(rA^)(pA-i^)V(rA<7)-*r

00010001

00110001

01000001

01100111

10011010

10111011

6

第1章习题解答

11000001

11100111

使得公式。八F)V("q)f「成真的赋值是:000,001,010,011,101,110,111,

使得公式仍八「"V(r八夕)一〃成假的赋值是：100。

(5)((「〃f力\/(4八「,)的真值表如表1.28所示。

表1.28

Pqrp/\^qfL⑺八f7)八->“))-广q/\f(PA--<?))-*/-)/(</A->r)

00000101

00100101

01000111

01100101

10011000

10111101

11001011

11101101

使得公式八F))f"\Z(夕八f)成真的赋值是:000,001,010,011,101,110,

111,使得公式((「〃-3/\[0)一-)\/(4八「厂)成假的赋值是：100。

4.用真值表证明下列等价式：

(1)—>⑦一q)opA—iq

证明：证明0=〃八-)夕的真值表如表1.29所示。

表1.29

pqL〃「q

001010

011000

100111

111000

由上表可见：—1(/?l/)却〃△―1q的真值表完全相同，所以—1(/7*(/)<->〃△—1夕。

(2)〃-q<=>—)qf

证明：证明pfqeq--1p的真值表如表1.30所示。

表1.30

PqLq7)-167

001111

011101

7

第1章习题解答

100010

111001

由上表可见：〃一夕和的真值表完全相同，所以〃

(3)13-q)<=>〃一一1g

证明：证明「3一0和〃-「4的真值表如表1.31所示。

表1.31

Pqp-qTn)Fpi「q

001010

010101

100111

111000

由上表可见：Tpiq)和〃1-14的真值表完全相同，所以

(4)〃f(qfr)<=>(pA<7)-*/*

证明：证明〃一(qf力和。八"-*r的真值表如表1.32所示。

(5)〃一日一p)o「p—(/L「q)

证明：证明/L你-p)和-1/L(/L-uy)的真值表如表1.33所示。

表1.33

〃一(“f〃)〃一一

Pq“f〃「p「4

00111111

01011011

10110111

11110001

8

第1章习题解答________________________________________

由上表可见：/L(qfp)和-i/L(/LF)的真值表完全相同，且都是永真式，所以pf(q

一p)o「〃一仍一」4)。

(6)「仍一")o(pV4)八-i(pAq)

证明：证明「⑦一功和八力的真值表如表1.34所示。

表1.34

PqpjqTp—q)p\qTp'q)(pV^)A->(pA^)

00100010

01011011

10011011

11101100

由上表可见：Tp一切和(pVq)q)的真值表完全相同，所以-i(p—q)o(p\/4)ATp

A“)

(7)-1s一夕)。(/?A—>^)V{-ipAq)

证明：证明和八夕)的真值表如表1.35所示。

表1.35

pqkqTr-q)n/\—>q「p八q(pA^)VHpA^)

0010000

0101011

1001101

1110000

由上表可见：「3一切和伽八「功\/(「〃/\切的真值表完全相同，所以「3-4)。3人「切

V(―1〃/\cj)a

(8)p-(qV力o(p/\-i(7)fr

证明：证明(9Vr)和。r的真值表如表1.36所示。

表1.36

pqrq\rp-*(t/Vr)-yQ[/)△」4)-*「

00001101

00111101

01011001

01111001

10000110

10111111

11011001

9

第1章习题解答

11111001

由上表可见：pf（gVr）和r的真值表完全相同，所以〃f（qV/*）＜=＞（/?A「夕）-*;*。

5.用等价演算证明习题4中的等价式。

⑴-1s一夕)

=-)(「〃V0（条件等价式）

=〃八-1"（德・摩根律）

⑵-iqf「p

<=>—>—i^rV—>p（条件等价式）

oqV-i〃（双重否定律）

=「pVg（交换律）

（条件等价式）

opfq

⑶」(pig)

（双条件等价式）

=」((pf4)A(4fp))

（条件等价式）

=->((「〃V^)A(pVp\)

（德-摩根律）

o(pAf)V(^A「〃)

o(3A「q)Vq)△(WA->,/)V]〃)（分配律）

o(pVq)八V-ip)（分配律）

（交换律）

o(「pVF)/\(4Vp)

（条件等价式）

O(/L->4)A(「q~p)

op—-iq（双条件等价式）

(4)/L，•)

（条件等价式）

Of7(—i^Vr)

（结合律）

14)Vr

（德•摩根律）

=-!(/?△q)Vr

（条件等价式）

o(P△4)->〃

(5)〃f(q—p)

（条件等价式）

Of7(—i^V/2)

0T

「〃一

（条件等价式）

<=>/?V(-npV-i^)

<=>T

所以pf(qfp)o「pf(pf「q)

(6)-slq)

1（例1.17）

=TS八4)V(fA「功)

（德-摩根律）

<=>(pV^)A(fV「q)

（德-摩根律）

o(pVq)八「3八夕)

所以-i(piq)u>(pVq)A-i(/?Aq)

O)「0)iq)

10

第1章习题解答

<=>T(pf4)A3-*〃))（双条件等价式）

0T(「〃V^)AJqVp))（条件等价式）

（德-摩根律）

(8)〃一*(gVr)

<=>—./?V(^Vr)（条件等价式）

—(「〃▽心厂（结合律）

<=>—«(pA—1^)Vr（德・摩根律）

（条件等价式）

6.试用真值表证明下列命题定律。

⑴结合律：（/?V^）Vr<=>/?VV/*）,（/?A（7）A/­<=>/?AAr）

证明：证明结合律的真值表如表1.37和表1.38所示。

表1.37

Pqro'a(pV^)Vrt/Vr

0000000

0010111

0101111

0111111

1001101

1011111

1101111

1111111

表1.38

pqrp\q(pA^)Arq!\r〃八(9△/•)

0000000

0010000

0100000

0110010

1000000

1010000

1101000

1111111

由真值表可知结合律成立。

(2)分配律：pA(^V/-)<=>(/?A^)V(/?Ar),

〃V(q△/,)<->(/?V<7)A(/^V/•)

11

第1章习题解答

证明：证明合取对析取的分配律的真值表如表1.39所示，析取对合取的的分配律的真值

表如表1.40所示。

表1.39

Pqrt/VrpA(i/Vr)pAr(pAt/)V(/?Ar)

00000000

00110000

01010000

01110000

10000000

10111011

11011101

11111111

表1.40

Pqrq/\r/?V(^Ar)P'qpVr(pV^)A(pVr)

00000000

00100010

01000100

01111111

10001111

10101111

11001111

11111111

由真值表可知分配律成立。

⑶假言易位式：pfq<^qf「p

证明：证明假言易位式的真值表如表1.41所示。

表1.41

Pqpfq

001111

011011

100100

111001

由真值表可知假言易位律成立。

12

第1章习题解答

⑷双条件否定等价式：p-qo-ipiR

证明：证明双条件否定的真值表如表1.42所示。

表1.42

Pqpiq-IPF-ipi-iQ

C01111

C10100

100010

111001

由真值表可知双条件否定等价式成立。

13

第1章习题解答

习题1.4

1.用真值表或等价演算判断下列命题公式的类型。

(l)(pV「q)—q

V-iq)Vq（条件等价式）

<=>Cp八q)\/q（德•摩根律）

oq(可满足式)（吸收律）

(2)」(pfq)八q

=T-1PVq)Aq（条件等价式）

<=>(pA-iq)Aq（德•摩根律）

oF(永假式)（结合律、矛盾律）

⑶(pfq)/\pfq

<=>(-ipVq)/\pfq（条件等价式）

=(「pAp)v(qAp)fq（分配律）

o(qAp)-*q（同一律、矛盾律）

=Tq八P)7q（条件等价式）

=(「qV->p)Vq（德・摩根律）

O7(永真式)（零律、排中律）

(4)(p->q)Aq

oJpVq)八q（条件等价式）

oq(可满足式)（吸收律）

⑸(pfq)f(「q-p)

=(pfq)-*(pfq)（假言易位式）

07(永真式)

(6)((pfq)/\(qfr))f(p-*r)

<=>-i((-ipVq)A(-it?Vr))V(-ipVr)（条件等价式）

o(pA「q)V(qAf)V(—>pVr)（德•摩根律）

<=>(pAiQ)V((.pVe?Vr)A(<pV>rVr))（分配律）

<=>(pA-it?)V(「pVqVr)（同一律、排中律、零律）

<=>(ipVqVrVp)A(-ipVqVrV-1^)（分配律）

oT(永真式)

⑺」p-(pfq)

<=>pVJpVq)（条件等价式）

07(永真式)

(8)pf(pVqVr)

14

第1章习题解答

OipVgVqVr)(条件等价式)

07(永真式)

2.用真值表证明下列命题公式是重言式。

⑴(p/\(p-*q))fq

(P八(p-q))-q的真值表如表1.43所示。由表1.43可以看出(pA(p-q))-q是重言式。

表1.43

pqpfqp八(p-q)(pA(p-(/))-*(?

00101

01101

10001

11111

(2)(「q/\(pfq))--1P

的真值表如表144所示。由表1.44可以看出(->q八(p-q))f-1P是

重言式。

表1.44

Pqpfq「q「q八(p-*q)「p

0011111

0110011

1001001

1110001

⑶(「p△(2▽《))fq

(-1P/\(pVq))fq的真值表如表1.45所示。由表1.45可以看出(-1P/\(pVq))-q是重言

式。

表1.45

PqpVq->pnpA(pVQ)

000101

011111

101001

111001

⑷((p—q)八(q->r))f(p-r)

((p-q)八(qfr))f(P—r)的真值表如表1.46所示c由表1.46可以看出((p-q)八(q-r))

-*(p~r)是重言式。

15

第1章习题解答

表1.46

Pqpfq<7-r(/)-")△(4-*力r((〃f*)A(q-H)f(pf，•)

00011111

00111111

01010011

01111111

10001001

10101011

11010001

11111111

(5)((pV<y)A(/?-*/*)A(^-*r))-*r

力的真值表如表1.47所示。由表1.47可以看出((pVM△⑦

一力八你一切一厂是重言式。

表1.47

Pqrq67-*r((pVf?)A(pfr)A”)fr

00001101

00101101

01011001

01111111

10010101

10111111

11010001

11111111

16

第1章习题解答

(6)((pfq)A(r/s))f((pAr)f(qAs))

((pfs)L((pAr)f(q/\s))的真值表如表1.48所示。由表1.48可以看出((p-q)

A(r-s))-*((p/\r)-*(q/\s))是重言式。

表1.48

PqrsP~qr-*s(p-*Q)A(r-*s)p/\rqf\s(pAr)-*(t?As)原公式

00001110011

00011110011

00101000011

00111110011

01001110011

01011110111

01101000011

01111110111

10000100011

10010100011

10100001001

10110101001

11001110011

11011110111

11101001001

11111111111

(7)((p一q)A(p-r)

((p-q)/\(q-r)L(p-r)的真值表如表1.49所示c由表1.49可以看出((p-q)A(q-r))

—(p—r)是重言式。

表1.49

Pqrp—qq—rp<->r((p—g)A(q-r))f(p-r)

000111.1

00110001

0100001

01101001

10001001

1010001

17

第1章习题解答

11010001

11111111

3.用等价演算证明题2中的命题公式是重言式。

⑴(pA(pfq))fq

<=>Tp△(->pVq))Vq

o(「pV(pA「q))Vq

o((「pVp)A(ipV「q))Vq

o(—ipV—>q)▽q

oT

(2)(TI△(2』))--1P

o(「q△(「P▽q))f「P

<=>->(-.qAJpVq))V-1P

o(qV(pA「q))V「p

<=>{-ipVq)V(pA-