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

《离散数学课后习题答案-(左孝凌版).docx》由会员分享，可在线阅读，更多相关《离散数学课后习题答案-(左孝凌版).docx（64页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1-1，1-2（1） 解：a) 是命题，真值为 T。b) 不是命题。c) 是命题，真值要根据具体情况确定。d) 不是命题。e) 是命题，真值为 T。f) 是命题，真值为 T。g) 是命题，真值为 F。h) 不是命题。i) 不是命题。（2） 解：原子命题：我爱北京天安门。复合命题：如果不是练健美操，我就出外旅游拉。（3） 解：a) (P R)Qb) QRc) Pd) PQ（4） 解：a) 设 Q:我将去参加舞会。R:我有时间。P:天下雨。Q (RP):我将去参加舞会当且仅当我有时间和天不下雨。b) 设 R:我在看电视。Q:我在吃苹果。 RQ:我在看电视边吃苹果。c) 设 Q:一个数是奇数。R:一

2、个数不能被 2 除。（QR）(RQ):一个数是奇数，则它不能被 2 整除并且一个数不能被 2 整除，则它是奇数。(5) 解：a) 设 P：王强身体很好。Q：王强成绩很好。PQb) 设 P：小李看书。Q：小李听音乐。PQc) 设 P：气候很好。Q：气候很热。PQd) 设 P： a 和 b 是偶数。Q：a+b 是偶数。PQe) 设 P：四边形 ABCD 是平行四边形。Q ：四边形 ABCD 的对边平行。PQf) 设 P：语法错误。Q：程序错误。R：停机。（P Q） R(6) 解：a) P:天气炎热。Q:正在下雨。PQb) P:天气炎热。R:湿度较低。PRc) R:天正在下雨。S:湿度很高。 RSd

3、) A:刘英上山。B:李进上山。ABe) M:老王是革新者。N:小李是革新者。 MNf) L:你看电影。M:我看电影。 LMg) P:我不看电视。Q:我不外出。 R:我在睡觉。 PQRh) P:控制台打字机作输入设备。Q:控制台打字机作输出设备。PQ1-3（1） 解：a) 不是合式公式，没有规定运算符次序（若规定运算符次序后亦可作为合式公式）b) 是合式公式c) 不是合式公式（括弧不配对）d) 不是合式公式（R 和 S 之间缺少联结词）e) 是合式公式。（2） 解：a） A 是合式公式，(AB)是合式公式， (A(AB) 是合式公式。这个过程可以简记为：A；(AB)；(A(AB)同理可记b）

4、A；A ；(AB) ；(AB)A)c） A；A ；B；(AB) ；(BA) ； (AB)(BA)d） A；B；(AB) ；(BA) ； (AB)(BA)（3） 解：a） (AC)(BC)A)(BC) A)(AC)b） (BA)(AB)。（4） 解：a) 是由 c) 式进行代换得到，在 c) 中用 Q代换 P, (PP)代换 Q.d) 是由 a) 式进行代换得到，在 a) 中用 P(QP)代换 Q.e) 是由 b) 式进行代换得到，用 R 代换 P, S代换 Q, Q 代换 R, P 代换 S.（5） 解：a) P: 你没有给我写信。 R: 信在途中丢失了。 PQb) P: 张三不去。Q: 李四

5、不去。R: 他就去。 (PQ)Rc) P: 我们能划船。 Q: 我们能跑步。(PQ)d) P: 你来了。Q: 他唱歌。R: 你伴奏。 P(QR)（6） 解：PQRQRP(QR)PQ(PQ)RTTTTTFTFTTFFFTTFTFFFTT F F F T F F FT F F F F F F FT T F F F F F FT F F F F F F FP:它占据空间。Q:它有质量。R:它不断变化。 S:它是物质。这个人起初主张：(PQR) S后来主张：(PQS)(SR)这个人开头主张与后来主张的不同点在于：后来认为有 PQ 必同时有 R，开头时没有这样的主张。（7） 解：a) P: 上午下雨。

6、Q:我去看电影。 R:我在家里读书。 S:我在家里看报。 (PQ)(P(RS)b) P: 我今天进城。Q:天下雨。QPc) P: 你走了。 Q:我留下。QP1-4（4）解：a)FFFFTT FFF TTF TFF FTFF 所以，P(QR) (PQ)Rb)P QRQRP(QR)PQ(PQ)RT TTT TFT F （ ） （）（） 所以，P(QR) (PQ)R ） 所以，P(QR) (PQ)(PR) ）PQPQPQ(PQ)PQ(PQ)TTTFFTFFF F T TF T F TF T T TF T T TF F F TF F F T所 以 ， (PQ) PQ,(PQ)PQ（5） 解：如表，对问

7、好所填的地方，可得公式PQRF1F2F3F4F5F6TTTTFTTFFTTFFFTFFFTFTTFFTTFF1F6，可表达为TFFFTFTTFFTTTFFTTFFTFTFFFTFFFTTFTTTFFFFFTFTTTF1:(QP)RF2:(PQR)(PQR)PQ12345678910111213141516FFFTFTFTFTFTFTFTFTFTFFTTFFTTFFTTFFTTTFFFFFTTTTFFFFTTTTTTFFFFFFFFTTTTTTTT(6)F3:(PQ)(QR)F4:(PQR)(PQR) F5:(PQR)(PQR) F6:(PQR)解：由上表可得有关公式为1.F2.(PQ)3.(Q

8、P)4.P5.(PQ)6.Q7.(PQ)8.(PQ)9.PQ10.PQ11.Q12.PQ13.P14.QP15.PQ16.T(7) 证明：a) A(BA) A(BA) A(AB) A(AB)A(AB)b) (AB) (AB)(AB)(AB)(AB)(AB)(AB)或 (AB) (AB)(BA)(AB)(BA)(AB)(AA)(BB)(BA)(AB)(BA)(AB)(AB)(AB)(AB)c) (AB) (AB)ABd) (AB)(AB)(BA)(AB)(BA)(AB)(AB)e) (ABC)D)(C(ABD)(ABC)D)(C(ABD)(ABC)D)(ABC)D) (ABC)(ABC)D(AB

9、C)(ABC)D (AB)(AB)C)D (C(AB)D)f) A(BC) A(BC) (AB)C(AB)C(AB)Cg) (AD)(BD)(AD)(BD)(AB)D (AB)D (AB)Dh) (AB)C)(B(DC)(AB)C)(B(DC) (AB)(BD)C(AB) (DB)C(AB)(DB)C (AD)B)C (B(DA)C（8） 解：a) (AB) (BA)C (AB) (BA)C (AB) (AB)CTC Cb) A(A(BB) (AA)(B B) TF Tc) (ABC)(ABC) (AA) (BC)T(BC)BC（9） 解：1）设 C 为 T，A 为 T，B 为 F，则满足 A

10、CBC，但 AB 不成立。2） 设 C 为 F，A 为 T，B 为 F，则满足 ACBC，但 AB 不成立。3） 由题意知A 和B 的真值相同，所以 A 和 B 的真值也相同。习题 1-5（1） 证明：a) (P(PQ)Q(P(PQ)Q(PP)(PQ)Q(PQ)Q(PQ)QPQQPTTb) P(PQ)P(PQ) (PP)QTQTc) (PQ)(QR)(PR)因为(PQ)(QR)(PR)所以 (PQ)(QR)为重言式。d) (ab)(bc)(ca)(ab)(bc)(ca)因为(ab)(bc)(ca)(ac)b)(ca)(ac)(ca)(b(ca)(ac)(bc)(ba)所以(ab)(bc)(ca

11、)(ab)(bc)(ca) 为重言式。（2） 证明： a)(PQ)P(PQ)解法 1：设 PQ 为 T（1） 若 P 为 T，则 Q 为 T，所以 PQ 为 T，故 P(PQ)为 T（2） 若 P 为 F，则 Q 为 F，所以 PQ 为 F， P(PQ)为 T命题得证解法 2：设P(PQ)为F ，则P 为T，(PQ)为F，故必有 P 为 T，Q 为 F ，所以 PQ 为 F。 解法 3：(PQ) (P(PQ)(PQ)(P(PQ)(PQ)(PP)(PQ)T所以(PQ)P(PQ) b)(PQ)QPQ设 PQ 为 F，则 P 为 F，且 Q 为 F，故 PQ 为 T，(PQ)Q 为 F，所以(PQ)

12、QPQ。c)(Q(PP)(R(R(PP)RQ设 RQ 为 F，则 R 为 T，且 Q 为 F，又 PP 为 F所以 Q(PP)为 T，R(PP)为 F所以 R(R(PP)为 F，所以(Q(PP)(R(R(PP)为 F即 (Q (P P) (R (R (P P) )RQ 成立。（3） 解：a) PQ 表示命题“如果 8 是偶数，那么糖果是甜的”。b) a)的逆换式 QP 表示命题“如果糖果是甜的，那么 8 是偶数”。c) a)的反换式PQ 表示命题“如果 8 不是偶数，那么糖果不是甜的”。d) a)的逆反式QP 表示命题“如果糖果不是甜的，那么 8 不是偶数”。（4） 解：a) 如果天下雨，我不

13、去。设 P：天下雨。Q：我不去。PQ逆换式 QP 表示命题:如果我不去，则天下雨。逆反式QP 表示命题:如果我去，则天不下雨b) 仅当你走我将留下。设 S：你走了。R：我将留下。RS逆换式 SR 表示命题：如果你走了则我将留下。逆反式SR 表示命题：如果你不走，则我不留下。c) 如果我不能获得更多帮助，我不能完成个任务。设 E：我不能获得更多帮助。H：我不能完成这个任务。EH逆换式 HE 表示命题：我不能完成这个任务，则我不能获得更多帮助。逆反式HE 表示命题：我完成这个任务，则我能获得更多帮助（5） 试证明 PQ，Q 逻辑蕴含 P。证明：解法 1：本题要求证明(PQ) QP,设(PQ) Q

14、为 T，则(PQ)为 T，Q 为 T，故由的定义，必有 P 为 T。所以(PQ) QP解法 2：由体题可知，即证(PQ)Q)P 是永真式。(PQ)Q)P (PQ) (PQ) Q)P (PQ) (PQ) Q) P (PQ) (PQ) Q) P (QPQ) (QPQ) P (QP) T) PQPPQTT（6） 解：P ： 我学习Q： 我数学不及格R：我热衷于玩扑克。如 果 我 学 习 ， 那 么 我 数 学 不 会 不 及格：PQ如果我不 热衷于玩扑克， 那么我 将学习:RP但我数学不及格 :Q因此我热衷于玩扑克。R即本题符号化为：(PQ)(RP)QR证：证法 1：(PQ)(RP)Q)R (PQ)

15、(RP)Q) R (PQ)(RP)QR(QP)(QQ)(RR)(RP) QPRP T所以，论证有效。证法 2：设(PQ)(RP)Q 为 T，则因 Q 为 T，(PQ) 为 T，可得 P 为 F，由(RP)为 T，得到 R 为 T。故本题论证有效。（7） 解：P ： 6 是偶数Q ： 7 被 2 除尽R：5 是素数如 果 6 是 偶 数 ， 则 7 被 2 除 不尽PQ或 5 不 是 素 数 ， 或 7 被 2 除尽RQ5是素数R所以6是奇数P即本题符号化为：（PQ）（RQ）RP证：证法 1：(PQ)(RQ)R)P (PQ) (RQ) R) P (PQ) (RQ) R) P(PP) (PQ) (

16、RR)(RQ) (PQ) (RQ)T所以，论证有效，但实际上他不符合实际意义。证法 2：(PQ)(RQ)R 为 T，则有 R 为 T，且RQ 为 T，故 Q 为 T，再由 PQ 为 T，得到P 为 T。（8） 证明：a) P(PQ)设 P 为 T，则P 为 F，故PQ 为 Tb) ABCC假定ABC 为 T，则 C 为 T。c) CABB因为 ABB 为永真，所以 CABB成立。d) (AB) AB设(AB)为 T，则 AB 为 F。若 A 为 T，B 为 F，则A 为 F，B 为 T，故AB 为 T。若 A 为 F，B 为 T，则A 为 T，B 为 F，故AB 为 T。若 A 为 F，B 为

17、 F，则A 为 T，B 为 T，故AB 为 T。命题得证。e) A(BC)，DE，(DE)ABC设A(BC)，DE，(DE)A 为 T，则 DE 为 T，(DE)A 为 T，所以A 为 T又A(BC)为 T，所以 BC 为 T。命题得证。f) (AB)C，D，CDAB设(AB)C，D，CD 为 T，则D 为 T，CD 为 T，所以 C 为 F又(AB)C 为 T，所以 AB 为 F，所以AB 为 T。命题得证。（9） 解：a) 如果他有勇气，他将得胜。P：他有勇气Q：他将得胜原命题： PQ逆反式： QP 表示：如果他失败了，说明他没勇气。b) 仅当他不累他将得胜。P：他不累Q：他得胜原命题：

18、QP逆反式： PQ 表示：如果他累，他将失败。习题1-6 (1)解：a) (PQ)P(PP)Q(TQ)b) (P(QR) PQ (P(QR)PQ(P PQ)(QPQ)(RPQ)(PQ)(PQ)(PRQ)PQ(PQ)c) PQ(RP)PQ(RP)(PQR)(PQP)(PQR)FPQR(PQR)(2) 解：a) P PPb) PQ(PQ) (PQ)(PQ) c)PQPQ (PP)(QQ)(3) 解：P(PQ)P(PQ)TPP (PP)(PP)P(PP)P(PQ)P(PQ)TPP(PP)PQ(PQ)(PP)(QQ) (PP)(QQ)(PP)(QQ)(5) 证明：(BC)(BC) BC(BC)(BC)

19、BC(6) 解：联结词“”和“”不满足结合律。举例如下：(PP)P)a) 给出一组指派：P 为 T，Q 为F，R 为 F，则(P(PP)P)(PP)P) (4)解：Q)R 为 T，P(QR)为 F故 (PQ)RP(QR).b) 给出一组指派：P 为 T，Q 为F，R 为 F，则(PQ) R 为 T，P(QR)为 F故(PQ)RP(QR). (7)证明：设变元 P，Q，用连结词,作用于 P，Q 得到： P，Q，P，Q，PQ，PP，QQ，QP。 但 PQQP，PPQQ，故实际有：P ， Q ， P ， Q ， PQ ， PP （ T ）（A）用作用于（A）类，得到扩大的公式类（包括原公式类）：P，

20、Q，P，Q，（PQ）， T，F， PQ（B）用作用于（A）类，得到：PQ，PPF，PQ（PQ），P（PQ）Q，P（PP）P，QP（PQ），QQF，Q（PQ）P，QTQ,PQPQ，P（PQ）Q，PTP,Q（PQ）P，QTQ,（PQ）（PQ）PQ.因此，（A）类使用运算后，仍在（B）类中。对（B）类使用运算得：P，Q，P，Q， PQ， F，T，（PQ），仍在（B）类中。对（B）类使用运算得：PQ，PPF，PQ（PQ），P（PQ）Q，PTP，PFP，P（PQ）Q，QP（PQ），QQF，Q（PQ）组P，QTQ, QFQ， Q（PQ） 已证, 不是最小联结词， 又因为 PP，PQPQ，P（PQ）Q，PT

21、P, PFP,P（PQ）Q，Q（PQ）P，QTQ, QTQ,Q（PQ）P，（PQ）T（PQ），（PQ）FPQ，（PQ）（PQ）F TFF，T（PQ） PQ F（PQ） （PQ）（PQ）（PQ）PQ.故由（B）类使用运算后，结果仍在（B）中。由上证明：用,两个连结词，反复作用在两个变元的公式中，结果只能产生（B）类中的公式，总共仅八个不同的公式，故,不是功能完备的，更不能是最小联结词组。Q （PQ），故任何命题公式中的联结词，如仅用 , 表达，则必可用,表达，其逆亦真。故 , 也必不是最小联结词组。(8) 证明，和不是最小联结词组。证明：若，和是最小联结词，则P（PP）P（PP）PP(P(P)对

22、所有命题变元指派 T，则等价式左边为 F，右边为 T，与等价表达式矛盾。所以，c 和不是最小联结词。(9) 证明,和,是最小联结词组。证明：因为,为最小联结词组，且 PQPQ所以 , 是功能完备的联结词组， 又,都不是功能完备的联结词组。(2) 解：a) (PQ)R所以,c是最小c联结词组。c(PQ)R又因为 PQ(PQ)，所以,是功能c完备的 联结词组，又,不是功能完备的联结词组，所以,是最小联结词组。习题1-7(1) 解： P(PQ)P(PQ) (PP)(PQ) P(PQ) (P(QQ)(PQ) (PQ)(PQ)(PQ) PQR(PQ)(PQ) (QR)(QR)(RP)(RP)b) P(Q

23、R)S)P(QR)S)PQRS(PQ)(PQ) (QR)(QR)(RS)(RS)(SP)(SP)c) (PQ)(ST)(PQ)(ST)(PQS)(PQT)d) (PQ)R(PQ)R(PQ)R(PR)(QR)e) (PQ)(PQ)(PQ)(PQ)(PP)(PQ)(QP)(QQ) (PQ)(QP)(3) 解：a) P(PQR)(PP)(PQ)(PR)(PQ)(PR)b) (PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PPQ)(QPQ)c) (PQ)(PQ) PQ(PQ)(PQ)(QP)d) (PQ)R(PQ)R (PQ)R (PR)(QR)e) (PQ)(PQ)(PP)(PQ)(QP)(QQ)

24、(PQ)(QP)(4) 解：a) (PQ)(PQ)(PQ) (PQ) (PQ) (PQ)(PQ)1，2，3PQ=P0b) Q(PQ) (PQ)(QQ) PQ =3P0，1，2(PQ)(PQ) (PQ)c) P(P(Q(QR)P(P(Q(QR)PQR=P01，2，3,4,5,6,7=(PQR) (PQR)(PQR) (PQR)(PQR)(PQR) (PQR)d) (P(QR) )(P(QR) (P(QR) (P(QR) (PP) (P(QR) (QR) P) (QR)(QR) (PQR) (PQR) =0,7P1，2，3,4,5,6 (PQR) (PQR)(PQR) (PQR)(PQR) (PQ

25、R)e) P(P(QP)P(P(QP)(PP)(PQP)T(TQ) T0,1,2,3= (PQ) (PQ)(PQ) (PQ)f) (QP) (PQ)(QP)PQ(QP)(PQ) FP0,1，2，3= (PQ) (PQ) (PQ)(PQ)(5) 证明：a)(AB) (AC) (AB) (AC) A(BC)A(BC) (AB) (AC)b)(AB) (AB)(AB) (AB) (AB) (AB)A(BB)ATA(AB) (BA) (AB) (BA)A(BB)AFAc)AB(AB) (AA)(AB)BABBFAB(AB) (AA)(AB)BABBFd)A(A(AB)AA(AB)TAB(AB)(AB)

26、 (AB)T(6) 解：AR(Q(RP),则 A*R(Q(RP)AR(Q(RP)(R(Q(RP)RQ(RP)(RQ) (RP)A*R(Q(RP)(R(Q(RP)RQ(RP)(RQ) (RP)(7) 解：设 A：A 去出差。B：B 去出差。C：C 去出差。D：D 去出差。若 A 去则 C 和 D 中要去一个。 A(C V D)B 和 C 不能都去。(BC)C 去则D 要留下。CD按题意应有：A(C V D)，(BC)，CD 必须同时成立。因为 C V D (CD) (DC) 故(A(C V D)(BC) (CD) (A(CD) (DC) (BC)(CD) (A(CD) (DC) (BC)(CD)

27、 (A(CD) (DC) (BC)(BD) (CD) C) (ABC) (ABD)(ACD) (AC)(BCD) (CDBD)(CDCD) (CDC) (DCBC)(DCBD)(DCCD) (DCC)在上述的析取范式中，有些（画线的）不符合题意，舍弃，得(AC) (BCD) （CD）(DCB)故分派的方法为：BD ,或 DA,或 CA。(8) 解：设 P：A 是第一。Q：B 是第二。R：C是第二。S：D 是第四。E：A 是第二。由题意得 (P V Q) (R V S) (E V S) (PQ) (PQ) (RS)(RS) (ES) (ES) (PQRS) (PQRS)(PQRS)(PQRS)(

28、ES)(ES)因为(PQRS)与 (PQRS)不合题意，所以原式可化为(PQRS)(PQRS)(ES)(ES) (PQRSES)(PQRSES)(PQRSES)(PQ RSES) (PQRSE)(PQRSE)因R 与E 矛盾，故PQRSE 为真，即 A 不是第一，B 是第二，C 不是第二，D 为第四，A 不是第二。于是得： A 是第三B 是第二C 是第一D 是第四。习题 1-8 (1)证明：a) (PQ)，QR，RP(1)RP(2)QRP(3)Q(1)(2)T,I(4)(PQ)P(5)PQ(4)T,E(6)P(3)(5)T,Ib) J(MN)，(HG)J，HGMN(1) (HG) JP(2)

29、(HG)P(3)J(1)(2)T,I(4) J(MN)P(5) MN(3)(4)T,Ic) BC，(BC)(HG) GH(1) BCP(2) B(1)T,I(3) C(1)T,I(4) BC(2)T,I(5) CB(3)T,I(6) CB(4)T,E(7) BC(5)T,E(8) BC(6)(7)T,E(9) (BC) (HG)P(10) HG(8)(9)T,Id)PQ，(QR)R，(PS) S(2)RQ(1)T,I(3)R(1)T,I(4)Q(2)(3)T,I(5)PQP(6)P(4)(5)T,I(1) (QR) R(7) (PS)P(8)PS(7)T,E(9)S(6)(8)T,I(2) 证明：a)AB，CBAC(1)C)(AP(2) A(3) C(1)T,I(1) T,I(4) ABP(5) B(2)(4)T,I(6)BCP(7