離散數(shù)學(xué)(左孝凌)課后習(xí)題解答

第1章習(xí)題解答

離散數(shù)學(xué)~

習(xí)題1.1

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

（1）中國(guó)有四大發(fā)明。

（2）計(jì)算機(jī)有空嗎？

⑶不存在最大素?cái)?shù)。

（4）21+3<5o

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

（6）2與3都是偶數(shù)。

⑺小李在宿舍里。

⑻這朵玫瑰花多美麗呀！

（9）請(qǐng)勿隨地吐痰！

（10）圓的面積等于半徑的平方乘以。

（11）只有6是偶數(shù)，3才能是2的倍數(shù)。

?雪是黑色的當(dāng)且僅當(dāng)太陽(yáng)從東方升起。

?如果天下大雨，他就乘班車上班。

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

?的真值目前無(wú)法確定；⑵⑻⑼不是命題。

2.將下列復(fù)合命題分成若干原子命題。

⑴李辛與李末是兄弟。

⑵因?yàn)樘鞖饫?，所以我穿了羽絨服。

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

（4）劉英與李進(jìn)上ft。

⑸王強(qiáng)與劉威都學(xué)過法語(yǔ)。

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

⑺我既不看電視也不外出，我在睡覺。

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

解：⑴本命題為原子命題；

（2）p：天氣冷；q：我穿羽絨服；

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

⑷p：劉英上ft；q：李進(jìn)上ft;

⑸p：王強(qiáng)學(xué)過法語(yǔ)；q：劉威學(xué)過法語(yǔ)；

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

（7）p：我看電視；q：我外出；r：我睡覺；

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

1

第1章習(xí)題解答

3.將下列命題符號(hào)化。

⑴他一面吃飯，一面聽音樂。

⑵3是素?cái)?shù)或2是素?cái)?shù)。

⑶若地球上沒有樹木，則人類不能生存。

(4)8是偶數(shù)的充分必要條件是8能被3整除。

⑸停機(jī)的原因在于語(yǔ)法錯(cuò)誤或程序錯(cuò)誤。

(6)四邊形A8CZ)是平行四邊形當(dāng)且僅當(dāng)它的對(duì)邊平行。

(7)如果。和是偶數(shù)，貝IJ。+〃是偶數(shù)。

解：(1)p；他吃飯；q；他聽音樂；原命題符號(hào)化為；〃

⑵P：3是素?cái)?shù)；q：2是素?cái)?shù)；原命題符號(hào)化為：p\Jq

(3)p：地球上有樹木；c/：人類能生存；原命題符號(hào)化為：1g

⑷p：8是偶數(shù)；q：8能被3整除；原命題符號(hào)化為：pig

⑸p：停機(jī)：q：語(yǔ)法錯(cuò)誤；八程序錯(cuò)誤；原命題符號(hào)化為：q\/Lp

(6)p：四邊形ABCD是平行四邊形；g四邊形ABCD的對(duì)邊平行；原命題符號(hào)化

為：piq。

⑺p：a是偶數(shù)；q：b是偶數(shù)；r：a+b是偶數(shù)；原命題符號(hào)化為：p/\q^r

4.將下列命題符號(hào)化，并指出各復(fù)合命題的真值。

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

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

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

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

⑸4是無(wú)理數(shù)當(dāng)且僅當(dāng)加拿大位于亞洲。

⑹2+3=5的充要條件是4是無(wú)理數(shù)。(假定是10進(jìn)制)

⑺若兩圓O「O的面積相等，則它們的半徑相等，反之亦然。

⑻當(dāng)王小紅)情?？鞎r(shí)，她就唱歌，反之，當(dāng)她唱歌時(shí)，一定心情愉快。

解：設(shè)p：3+3=6。q：雪是白的。

⑴原命題符號(hào)化為：pfq；該命題是真命題。

(2)原命題符號(hào)化為：仍該命題是真命題。

(3)原命題符號(hào)化為：〃f->q；該命題是假命題。

(4)原命題符號(hào)化為：該命題是真命題。

⑸P：陋■是無(wú)理數(shù)；q：加拿大位于亞洲；原命題符號(hào)化為：〃1夕；該命題是假命

題。

⑹p：2+3=5；q：y/3是無(wú)理數(shù)；原命題符號(hào)化為：pig;該命題是真命題。

⑺p：兩圓O]Qi的面積相等；q：兩圓O1,O)的半徑相等；原命題符號(hào)化為：pig;

該命題是真命題。

(8)p:王小紅心情愉快；q：王小紅唱歌；原命題符號(hào)化為：該命題是其命題。

2

第1章習(xí)題解答

習(xí)題1.2

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

(1)(pAq-r)

⑵

⑶q)一(~s))

⑷(p/\q—rs)

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

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

2.設(shè)p：天下雪。q：

我將進(jìn)城。r：

我有時(shí)間。

將下列命題符號(hào)化。

⑴天沒有下雪，我也沒有進(jìn)城。

⑵如果我有時(shí)間，我將進(jìn)城。

⑶如果天不下雪而我又有時(shí)間的話，我將進(jìn)城。

解：(1)->pA->q

(2)r—q

(3)-npAr-*Q

3.設(shè)p、q、r所表示的命題與上題相同，試把下列公式譯成自然語(yǔ)言。

⑴人

(2)」(rVq)

⑶q一(rA-'p)

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

解：⑴我有時(shí)間并且我將進(jìn)城。

⑵我沒有時(shí)間并且我也沒有進(jìn)城。

⑶我進(jìn)城，當(dāng)且僅當(dāng)我有時(shí)間并且天不下雪。

⑷如果我有時(shí)間，那么我將進(jìn)城，反之亦然。

4.試把原子命題表示為p、q、r等，將下列命題符號(hào)化。

⑴或者你沒有給我寫信，或者它在途中丟失了。

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

⑶我們不能既劃船又跑步。

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

解：(Dp：你給我寫信；q：信在途中丟失；原命題符號(hào)化為：(「p/\「q)V(pAq)。

⑵p：張三去;q：李四去；r：他去；原命題符號(hào)化為：r。

3

_________________________________第1章習(xí)題解答

(3)p：我們劃船；q：我們跑步；原命題符號(hào)化為：「(pAQ)o

(4)p：你來了；q：他唱歌；r：你伴奏；原命題符號(hào)化為：pf(qr)。

5.用符號(hào)形式寫出下列命題。

⑴假如上午不下雨，我去看電影，否則就在家里讀書或看報(bào)。

⑵我今天進(jìn)城，除非下雨。

⑶僅當(dāng)你走，我將留下。

解：(1)p：上午下雨；q：我去看電影；r：我在家讀書；s：我在家看報(bào)；原命題符號(hào)

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

⑵p：我今天進(jìn)城；q：天下雨；原命題符號(hào)化為：［q

(3)p：你走；q：我留、；原命題符號(hào)化為：q-*p>

4

第1章習(xí)題解答

習(xí)題1.3

1.設(shè)/、B、。是任意命題公式，證明：

(2)若貝ljBo/

⑶若BoC,貝JA<=>C

證明：⑴由雙條件的定義可知是一個(gè)永真式，由等價(jià)式的定義可知AoA成立。

⑵因?yàn)?。以由等價(jià)的定義可知A-8是一個(gè)永真式，再由雙條件的定義可知F-A

也是一個(gè)永真式，所以，BoA成立。

(3)對(duì)A、B、C的任一賦值，因?yàn)锳oB,則4-B是永真式，即4與B具有相同的真

值，又因?yàn)锽oC,則B-C是永真式，即8與C也具有相同的真值，所以4與C也具有

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

2.設(shè)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.構(gòu)造下列命題公式的真值表，并求成真賦值和成假賦值。

⑴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章習(xí)題解答

使得公式夕八(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)是一個(gè)永真式。

⑷仍八「切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章習(xí)題解答

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.用真值表證明下列等價(jià)式：

(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章習(xí)題解答

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章習(xí)題解答________________________________________

由上表可見：/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章習(xí)題解答

11111001

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

5.用等價(jià)演算證明習(xí)題4中的等價(jià)式。

⑴-1s一夕)

=-)(「〃V0（條件等價(jià)式）

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

⑵-iqf「p

<=>—>—i^rV—>p（條件等價(jià)式）

oqV-i〃（雙重否定律）

=「pVg（交換律）

（條件等價(jià)式）

opfq

⑶」(pig)

（雙條件等價(jià)式）

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

（條件等價(jià)式）

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

（德-摩根律）

o(pAf)V(^A「〃)

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

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

（交換律）

o(「pVF)/\(4Vp)

（條件等價(jià)式）

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

op—-iq（雙條件等價(jià)式）

(4)/L，?)

（條件等價(jià)式）

Of7(—i^Vr)

（結(jié)合律）

14)Vr

（德?摩根律）

=-!(/?△q)Vr

（條件等價(jià)式）

o(P△4)->〃

(5)〃f(q—p)

（條件等價(jià)式）

Of7(—i^V/2)

0T

「〃一

（條件等價(jià)式）

<=>/?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章習(xí)題解答

<=>T(pf4)A3-*〃))（雙條件等價(jià)式）

0T(「〃V^)AJqVp))（條件等價(jià)式）

（德-摩根律）

(8)〃一*(gVr)

<=>—./?V(^Vr)（條件等價(jià)式）

—(「〃▽心廠（結(jié)合律）

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

（條件等價(jià)式）

6.試用真值表證明下列命題定律。

⑴結(jié)合律：（/?V^）Vr<=>/?VV/*）,（/?A（7）A/-<=>/?AAr）

證明：證明結(jié)合律的真值表如表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

由真值表可知結(jié)合律成立。

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

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

11

第1章習(xí)題解答

證明：證明合取對(duì)析取的分配律的真值表如表1.39所示，析取對(duì)合取的的分配律的真值

表如表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章習(xí)題解答

⑷雙條件否定等價(jià)式：p-qo-ipiR

證明：證明雙條件否定的真值表如表1.42所示。

表1.42

Pqpiq-IPF-ipi-iQ

C01111

C10100

100010

111001

由真值表可知雙條件否定等價(jià)式成立。

13

第1章習(xí)題解答

習(xí)題1.4

1.用真值表或等價(jià)演算判斷下列命題公式的類型。

(l)(pV「q)—q

V-iq)Vq（條件等價(jià)式）

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

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

(2)」(pfq)八q

=T-1PVq)Aq（條件等價(jià)式）

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

oF(永假式)（結(jié)合律、矛盾律）

⑶(pfq)/\pfq

<=>(-ipVq)/\pfq（條件等價(jià)式）

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

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

=Tq八P)7q（條件等價(jià)式）

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

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

(4)(p->q)Aq

oJpVq)八q（條件等價(jià)式）

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

⑸(pfq)f(「q-p)

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

07(永真式)

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

<=>-i((-ipVq)A(-it?Vr))V(-ipVr)（條件等價(jià)式）

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)（條件等價(jià)式）

07(永真式)

(8)pf(pVqVr)

14

第1章習(xí)題解答

OipVgVqVr)(條件等價(jià)式)

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章習(xí)題解答

表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章習(xí)題解答

(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章習(xí)題解答

11010001

11111111

3.用等價(jià)演算證明題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-