离散数学课后习题答案-(左孝凌版)

(┓PQ(R∧┓P):我将去参加舞会当且仅当我有PabQ：a+bPABCDQ四ABCDPQ（P∨Q）→ R:天正在下雨。S: M:老王是革新者。N:小李是革新者。

L:你看电影。M:我看电影。1-AA∨B)是合式公式，(A→(A∨B以A；┓A；(┓A∧B)A；┓A；B；(┓A→B)；(B→A)；A；B；(A→B)；(B→A)；

ccP(P→P是由a)式进行代换得到，在a)中用P→(Q→PQ.QQRPR∨了。P PQR。P:我们能划船。Q:我们能跑步。P:你来了。Q:他唱歌。R:你伴奏。 R T F T F T F T这个人起初主张：(P∧Q∧RPQ:R:我在家里读书。S:我在家里看报。PQ:PQ:我留下。1- FFTFTFTFTFTFFＦＦRRPQTFTＴＴFＰＱＰＰＱＰＰＴ

Ｆ所以，P∧(Q∨R(P∧Q)∨(P∧R)ＦPQQQTTTFFTFF所以，┓(P∧Q)

PQRPQRTTTTFTTFFTTFFFTFFFTFTTFFTTFTFFFTFTTFFTTTFFTTFFTFTFFFTFFFTTFTTTFFFFFTFTTT

PQPQ12345678910111213141516FFFTFTFTFTFTFTFTFTFTFFTTFFTTFFTTFFTTTFFFFFTTTTFFFFTTTTTTFFFFFFFFTTTTTTTT

A→(B→A)┐(AB)

(AB┐(A→B) A→(B∨C) (┐(A∧B)

((A→B)((┐A∨B)((┐A∨B)T∧CA∨(┐A∨(B∧┐B))(A∨┐A)∨(B∧┐B)T∨FT(A∨┐A)A∨CB∨CABCF，AT，BF，A∧CB∧CAB由题意知┐AB相AB1-（1）

所以(P→Q)∧(Q→R) ∨(c∧a))(a∨b)∧(b∨c)∧(c∨a)为（2）证明：1：P→(P∧Q)TP→(P∧QT2：设P→(P∧Q)为F则P为T(P∧Q)为F 故必有P为T，Q为F，所以P→Q为F。解法3：(P→Q)

P→QT，(P→Q)→QF，QPPRRPP→Q8果a)Q→P甜8a)的反换式┐P→┐Q8a)的逆反式┐Q→┐P果8Q→P

逆反式┐S→┐RE：我不能获得更多帮助。H：我不能完成PQ，QP。1：本题要求证明(PQ)设(PQ)∧QT，则(PQ)T，QT，故由PT。所以(PQ)∧QP2：(((P∧Q)∨(┐P∧┐Q))(┐((P∧Q)∨(┐P∧┐Q))∨┐Q)(((┐P∨┐Q)∧(P∨Q))∨┐Q)((┐Q∨┐P∨┐Q)∧(┐Q∨P∨Q))((┐Q∨┐P)∧T)P：我学 Q：我数学不

如果我不热衷于玩扑克，那么我将学 格:Q ┐((┐P∨┐Q)∧(R∨P)∧Q)2：设(P→┐Q)∧(┐R→P)∧QT，QT，(P→┐QTPF，由(┐R→PTRT。P：6是偶数 Q：7被2除 R：5是素数如果6是偶数，则7被2除不 或5不是素数，或7被2除

R （P→┐Q（┐R∨Q∧R┐((┐P∨┐Q)∧(┐R∨Q)∧R)((P∧Q)∨(R∧┐Q)∨┐R) ((┐P∨P)∧(┐P∨Q))(┐P∨Q)2：(P→┐Q)∧(┐R∨Q)∧RT，RT，且┐R∨QTQT，P→┐QT，得到┐PT。┐(A∧B)

设┐A→(B∨C)，D∨E，(D∨E)→┐AT， 原命题： 逆反式┐Q→┐P 原命题： 逆反式┐P→┐Q (P→(Q∨┐R))

┐PP∨Q┐(P↓Q)(P↓Q)↓(P↓Q)c)P∧Q┐P↓┐Q(P↓P)↓(Q↓Q)

故 ↓Q)↓R为T，P↓(Q↓R)为F PQQP，PPQQ，故实际有：：P，Q，┐P，┐Q，┐（PQ），T，F，

（A）┐P，┐Q，P，Q，PQ，组┐P，QTQ,QF┐Q，Q（PQ）已证{,┐}不是最小联结 ，又因为组 ┐P,TFF，T（PQ）PQF（PQ）┐（PQ）

如仅用{,┐}表达，则必可用{,┐}表达，其逆亦真。故{,┐}也必不是最小联T，与等价表达式矛盾。所以c→

→所以→

→

→

c完备→联结词组又 习 1-(1)解：(P∧┐P)∨(P∧Q)

(P∧Q)∨(P∧┐Q)(┐P∧Q)∨(┐P∧┐Q)

┐(┐P∨┐Q)(P∧Q)P∧Q(P∨Q)∧(P∨┐Q)=(┐P∧┐Q∧R)∨(┐P∧Q∧R)∨(P∧Q∧┐R)d)(P→(Q∧R)

(┐P∨(Q∧R))(P∧┐P)∨(P∧(Q∧R))((┐Q∧┐R)∧┐P)(P∧Q∧R)∨(┐P∧┐Q∧┐R)(P∨Q∨┐R)∧(P∨┐Q∨┐R)∧(┐P∨Q∨┐R)T∨(T∧┐Q)0,1,2,3=(┐P∧┐Q)∨(P∧┐Q)(Q→P)∧┐(P∨┐Q)(A→B)(┐A∨B)∧(┐A∨C)(┐A∨B)(A→B)┐(┐A∨B)(A∧┐B)

(┐A→B)(A∨B)┐(A∧B)┐(R∧Q)

┐(R∨Q)出差。D：DACDA→(CV去 C去则D要留下。 CVD(C∧┐D)∨(D∧┐C)故(A→(CVD))∧┐(B∧CC→┐D)(┐A∨(C∧┐D)∨(D∧┐C))(┐A∨(C∧┐D)∨(D∧┐C))(┐A∨(C∧┐D)∨(D∧┐C))∨(┐B∧┐D)∨(┐C∧┐D)(┐A∧┐B∧┐C)∨(┐A∧┐C∧┐D)∨(┐B∧┐C∧D)∨(┐C∧D∧┐C)∨(┐D∧C∧┐C∧┐D)(┐A∧┐C)∨(┐B∧┐C∧D)故分派的方法为：B∧DD∧AC∧A是第二。S：DE：APVQRVSEV

((P∧┐Q)∨(┐P∧Q))∨(┐R∧S))∧((E∧┐S)((P∧┐Q∧R∧┐S) 因REP∧Q∧┐R∧S∧┐EABCD第四，A于是得：A是第三 B是第二 C是第 D是第四。1-8PPP

(H∨G) B∧C，(BC)→(H∨G) (BC) d)P→Q，(┐Q∨R)∧┐R，┐(┐P∧S)R┐QR┐Q∨┐ ┐QP→QP┐P

(7) ┐→P┐ BC→┐P┐B

┐→B┐FB∧┐B矛b)A→(B→C)(C∧)→E CCB→C ED∧┐D D

E┐E∧┐E矛 A┐F BDD∨→PC∧C∧D

E FC

∧┐E)┐→PBE D

E(A→B) B PB→E E ┐E∨┐FEE→┐F(A→┐

F(C→F(C→DFFC→A→CPA→FBB┐AP∨BAA┐F→┐A→┐A┐A∨┐A┐ABC→P┐┐C(A→┐AP

(C∧D)

CB→CB→(4)PAP C∧DD∨ EEB→FFA→F∧┐E)B→EB(2)

a) ┐ QPP→┐QPQP┐P┐

RPP┐RP（┐SPS→┐┐ (3)（┐P→Q）∧（Q→┐P） ┐

┐RP┐R∧ c)┐(P→Q)→┐(R∨S)，((Q→P)∨┐R)，RP ┐(P→Q) 设P：我跑步。Q：我很疲

┐ ┐ S：他犯了错误。R：他神色慌张。S→RRSS QP QP RP R┐R ┐ ┐

PW（x：x则有¬W（c）（xx（xxC（x：xB（x：x则有C（l）B（l）O（x：x则有O（2m（xx（xxR（x：xQ（x：xR（x：xQ（x：x则有P（x，yG（x，yxy。则有P（A，B）¬G（A，B）

V（x：x（xx¬则（xx（xxC（x：x（xx（xx则 （xx（xxL（x：xW（x：xH（x：x庭妇女。C（x：xW（x：xJ（x：xC（x：xL（x：xJ（y：y则有（x）（L（x）xyS（x：xL（x：x动员。A(x,y)：xy。A(x,y)

a）5b）22xx2x是偶x，xx6（即某6）xyy也是偶数。xxy，y是偶数且x能除尽y（即所有质数能除尽某些解：或∧ ∧┐(u)(┐ ∧L(u)N(x):x是有限个数的乘积。z(y):y0P(x):xF(y):y是乘积中 R(x):x是实数。Q(x,y):yx。故(x)(R(x)→(y)(Q(x,y)∧R(y)))

R(x):x是实数。G(x,y):xy ∧ ∧ （4）解：设 大于y。则(x)(y)(z)(G(y,x)N(x):xS(x,y):yx的或(x)(N(x)→(y)(N(y)∧S(x,y)E(y,z)(x)(N(x)∧┐S(x,2)→ 或(x)(N(x)∧┐S(x,2)→(y)(N(y)∧┐(z)(┐E(y,z)F(x):x是用功的。R(x,y):xyG(y):yK(y):y是厚的。是巨著。a:这本 则有E(b)∧F(b)∧S(b∧R(b,a)∧G(a)∧解设P(x,y):x在y连续。 P(f,a)((ε)(δ)(x)(Q(ε,0)→(Q(δ,0)解：ax是约束变元，yx是约束变元，P(x)∧Q(x)x受全称量词的约束，S(x)x受存在量词的约束。x，y都是约束变元,P(x)x受

x，y是约束变元，z解：aP(1)T，Q(1)F，P(2)F，Q(2)T,所 PT，Q(2)T，Q(3)T，Q(6)F，R(5)F，所以解：a解： ((y)A(u，y)→(x)B(x (x)(y)P(y,x)(x)

(x)( （2）解：a b) (P(f(2))∧Q(2,f(1)) (x)((x)(x)

((x)(P(x)∧Q(a))(x)(P(x)Q(x)),(x)(x)(P(x)Q(x)),(x)(Q(x)(x)(P(x)(x)(P(x)Q(x)),(x)P(x)(x)Q(x)(P(x)Q(x)),(x)P(x)(x)Qa）因为((x)(P(x∧Q(a))(x)P(x故原式为(x)P(x)∨Q(aP（x：xQ（x：x前提x，xa是运xaP（x：x是研究生。Q（x：x

x，xxx不是大学生。x都是研究生。P（x：xQ（x：x学。R（x：x曾读过中学。前提xxx曾读过xxx曾读xxx曾读过（xx（xx。前提xxx是

结论x，xP（x：x（x：x。前提xxx是x，x不是研究生结论x，x证明：(x)(A(x)→B(x))(x)B(x))(x)┐A(x)∨(x) ┐ ∨ (x)A(x)→(x)设论域D={a，b，c}，求证(x)B(x)(D={a，b，c}，所以(x)A(x)∨(x)B(x)(A(a)∧A(b)∧A(c))∨(B(a)∧B(b)(A(a)∨B(a))∧(A(a)∨B(b))∧(A(a)B(c))∧(A(b)∨B(a))∧(A(b)∨B(b))(A(b)∨B(c))∧(A(c)∨B(a))∧(A(c)B(b))∧(A(c) ((求证(x)(y)(P(x)→Q(y))(证明：(x(x)(y)(┐P(x)

(x)┐P(x)∨(┐(x)P(x)∨(( (x)(┐P(x)(x)(y)(┐P(x)b)(x)((y)P(x,y)∨(┐(z)Q(z)(x)((y)P(x,y)∨((z)┐Q(z)(x)(y)(z)(P(x,y)∨┐Q(z) ∧(u)Q(x,u))(x)(y)((x)((x)((x)(y)(z)(u)(v)(┐P(x,y,z)（2）解 ┐((x)P(x)∨(x)Q(x)) → →(x)(┐P(x)∨(y)((x)(y)(┐P(x)∨┐Q(x,y)

(x)(y)((P(x)∧Q(x,y)∨(P(x)∧Q(x,y)∨(P(x)∧┐Q(x,y)∨(┐P(x)∧Q(x,y)∨(┐P(x)∧┐Q(x,y)∨((P(x)∧┐Q(x,y)∨(┐P(x)∧Q(x,y)∧┐R(y,x))) ┐ ∨ ┐ ∨ (x)(┐P(x)(x)(z)(u)(┐P(x)(x)(z)(u)((P(x)∧Q(x,z)∨(P(x)∧Q(x,z)∨(P(x)∧┐Q(x,z)∨(P(x)∧┐Q(x,z)∨(┐P(x)∧Q(x,z)∨(┐P(x)∧┐Q(x,z)∨(┐P(x)∧┐Q(x,z)∧┐R(x,y,u)))┐(x)(┐P(x) ∨Q(x,y))∨((y)P(y)∧ ∨((u)P(u)(x)(u)(z)((P(x)∧┐Q(x,y))

(x)(u)(z)((P(x)∨P(u))∧Q(y,z))∧(┐Q(x,y)∨P(u))∧(┐Q(x,y)∨a)P②┐→③(┐P④┐⑤∨⑥⑦ ┐ ②(┐→③┐→④

⑦⑦→P⑧⑨⑩∧┐ ③P →┐④→┐ →┐d) →C(x)),(x)C(x) ②→┐③(P④

⑤┐⑥∨P⑦∨⑧⑨ ①( ⑤⑥⑦ →b)因为(x)P(x)∨(x)Q(x)┐ (x)P(x)

② ┐③┐ P⑤∨⑥⑦(⑧┐→⑦⑧∧⑦⑧∧I（x：x(x)(Q(x)→R(x))∧(x)(Q(x)(x)(R(x) P∧ P④→⑤P④→⑤⑥

（xx（xxR（x：x(x)(P(x)→┐Q(x)),(x)(Q(x)∨R(x)), (x)①┐P②┐R③∨P④∨⑤⑥→┐P⑦→┐⑧┐P⑨(x)

G（x：x是大学生。L（x：xP（x：x是理工科学生。S（x：x(x)(G(x)→L(x)∨P(x)),(x)(G(x)∧┐P(c),S(c) G(c) ⑤P┐P⑥注意：本题推证过程中未用到前提(x)(G(x)∧S(x))S(c)S（x：x是优秀生，这S（x）与其他前提不矛盾，故本题的推证仍

3-5.1X={a,b,c3-5.2n个元素的集合上，可解因为在X中的任何二元关系都是×XX×X=X20n2个元素，共可组2n个子集，即|XX)|2n。3-5.3表示本地四个电视频道的集合,R1R2ABR1R2R1-R2可分别得出怎样的解R1和R2分别是A×B的两个子集，R1表示音乐节目播出的时间表，R2R1∪R2表示音乐或戏曲节目的播出时间表，R1∩R2表示音乐和戏曲一起播出的时间表，R1R2表示音乐节目表以3-5.4L表示‘整除”关系,LD{1,2,3,6}LD的所有元L∩D.

解3-5.5A上的二元{<x,y>|2≤x,y≤7xy,{<x,y>|x,y是互质的}解ØA×A判断A中的上述关系是否为a自反的，解（1）R是可传递和反对称的。（2）S（3）T3-6.2A={1，2，3,4aAAR，并绘出递的，iv)反对称的吗？解

3-6.3举出A={1，2，3Rc）R解3-6.4RS对任意x∈X，有＜x，x＞∈R和＜x，x＞∈S，所以R∩S在Xy＞∈R∧＜x，y＞∈SRS是对称的，故必有＜y，x＞∈R∧R∩SX＞∈R∩S

3-7.1R1R2Aa）R1R2R1○R2也是R1R2R1○R2也R1R2R1○R2也是R1R2R1○R2也是证明a）a∈AR1R2是自a，b＞}R2={＜b，a＞}c)A={a，b，c}，有R1R2R所以，R1○R2d）假。例如：设A={a，b，c}，有R1={＜ab＞bc＞ac＞b，a＞}则R1，R2都是传递的。但R1○R2={＜，

＜xz＞∈SS反之，设（S○S）S，假定＜SSx，y＞∈IX，x=y。但＜x，x＞∈S，因此＜x，y＞=＜x，x＞∈S，IXSIXS，＞∈IX，故＜x，x＞∈S，SSS∩ScSX所以＜x，y＞＝＜x，x＞∈IXS∩ScIXXX＜y，x＞∈S，x＝y，SRS∈R∧＜x，z＞∈S，即SR∩SX1233-6.5S={1，2，3，4S123 R使得R

所以，R1○R23-7.2SXb）S是自反的，当且仅当IXS；7.3（b（X称的，当且仅当S∩ScIX证明a）S

3-7.3SX吗？证明若S是X3-7.2a）可知SS○S。得到S=S○S.3-8.1根据图3-8.1RRa1 M

3-9.14解44，1+3，1+1+2，2+2，1+1+1+11 0 0

2

C4+1=15（种r（R）=R∪IX={＜a，a＞，＜b，b＞，＜c，c＞，＜a，b＞，＜b，c＞，＜c，b＞＝s（R）=R∪RC={＜a，a＞，＜a，b＞，＜b，a＞，＜b，c＞，＜c，b＞}3-8.2设集合A={a，b，c，d}A用矩阵运算和作图方法求出R010010100100101000010000R

3-9.2设{A1，A2，…，AkA的一个划分，我们定义AR，使＞∈RabR证明a∈AAia∈Aiaa∈RRa,b∈A，若有＜a,b＞∈R，abbab,∈RRa,b,c∈A，iijjiijja,c∴Rdc0100100dc010010001100101001001110 = r（R）=d，d＞}（图abdcabdc

= 3-10.1RR′A：R∪R′不一定是等价关系。证明设A={1，2，3}，S=R∪R′R∪R′={＜1，1＞，＜2，2＞，＜3，3＞，＜3，1＞，＜1，3＞，＜3，2＞，＜2，3＞}因为如＜2，3＞∈S∧＜3，1＞∈S，但＜2，1＞S，R∪R′R∪R′不是A

证明ARx＜＜x,y＞, y3-10.24解因为集合X上的等价关系与X的划分是一一对应的，所以4个元素的有限集上等价关系的数目，与4个元素集合进行划分的数目是相同的，由习题3-9.1可知共有15个不同的等

①对任意＜x,y＞∈A，因为

=y3-10.3S={1，2，3，4，5}，SR，R2}，{3}，{4，5}}，解我们可用如下方法产生一个等价关系：R=

＜＜x,yx,y＞＞∈RR②设＜x,y＞∈A，＜u,v＞∈Ax 3-10.4RS={＜a，b＞∣c，有＜a，c＞∈R∧＜c，b＞∈R}，证明若R是一个等价关系，则S也是一个等价关系。证明R是Ax∈A，因为RAx，x＞∈RS＜x，x＞∈SSx,y∈A，若＜x，y＞∈S，c，使得y，x＞∈S，Sx,y,z∈A，若＜x，y＞∈S，及＜y，z＞∈S，c，使＜xz＞∈SS3-10.5设正整数的序偶集合AAR＜＜x,y＞,＜u,v＞＞∈R当且仅当xv=yu，证明R是一个等价关系。

＜＜x,y＞,＜u,v＞＞∈Ry=vvx=y③＜＜x,y＞, 所以RARAv xv