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

1、1-1 ， 1-2P Q（ 1） 解：f)设 P：语法错误。 Q：程序错误。 R：停机。（ P Q） Ra)是命题，真值为 T。(6) 解：b)不是命题。a)P: 天气炎热。 Q:正在下雨。P Qc)是命题，真值要根据具体情况确定。b)P: 天气炎热。 R: 湿度较低。P Rd)不是命题。c)R:天正在下雨。 S: 湿度很高。 RSe)是命题，真值为 T。d)A: 刘英上山。 B: 李进上山。A Bf)是命题，真值为 T。e)M:老王是革新者。 N:小李是革新者。 M Ng)是命题，真值为 F。f)L: 你看电影。 M:我看电影。L Mh)不是命题。g)P: 我不看电视。 Q:我不外出。 R:

2、 我在睡觉。 P QRi)不是命题。h)P: 控制台打字机作输入设备。 Q:控制台打字机作输出设备。 PQ（ 2） 解：原子命题：我爱北京天安门。1-3复合命题：如果不是练健美操，我就出外旅游拉。（ 1）解：（ 3） 解：、 -a)不是合式公式，没有规定运算符次序（若规定运算符次序后亦可a)( P R)Q作为合式公式）b)QRb)是合式公式c)Pc)不是合式公式（d)P Qd)）（ 4） 解：e)不是合式公式（ R 和 S 之间缺少联结词）a) 设 Q:我将去参加舞会。 R: 我有时间。 P: 天下雨。f)是合式公式。Q(R P): 我将去参加舞会当且仅当我有时间和天不下雨。（ 2）解：b)

3、设 R:我在看电视。 Q:我在吃苹果。a） A是合式公式， (AB)是合式公式， (A(AB) 是合式公式。R Q:我在看电视边吃苹果。这个过程可以简记为：c)设 Q:一个数是奇数。 R:一个数不能被 2 除。A；(AB)；(A(AB)（QR） (RQ): 一个数是奇数，则它不能被 2 整除并且一个数不同理可记能被 2 整除，则它是奇数。b） A； A ；( AB) ；( AB)A)(5)解：c） A； A ； B；( AB) ；(BA) ；( AB)(BA)a)设 P：王强身体很好。 Q：王强成绩很好。 PQd） A；B；(AB) ；(BA) ；(A B)(BA)b)设 P：小李看书。 Q：

4、小李听音乐。 P Q（ 3）解：c)设 P：气候很好。 Q：气候很热。 P Qa） (A C)(B C)A) (B C)A) (AC)d)设 P： a 和 b 是偶数。 Q：a+b 是偶数。 P Qb） (B A)(AB) 。e)设 P：四边形 ABCD是平行四边形。 Q ：四边形 ABCD的对边平行。 （ 4）解：a) 是由 c) 式进行代换得到，在 c) 中用 Q代换 P, (P P)代换 Q.d) 是由 a) 式进行代换得到，在 a) 中用 P(QP)代换 Q.e) 是由 b) 式进行代换得到，用 R代换 P, S 代换 Q, Q 代换 R, P 代换 S.（ 5）解：a) P: 你没有

5、给我写信。 R: 信在途中丢失了。 P Qb) P:张三不去。 Q: 李四不去。 R: 他就去。(PQ)Rc) P:我们能划船。 Q: 我们能跑步。 (PQ)d) P:你来了。 Q: 他唱歌。 R: 你伴奏。 P(QR)（ 6）解：P: 它占据空间。 Q: 它有质量。 R: 它不断变化。 S: 它是物质。这个人起初主张： (PQR)S后来主张： (PQ S)(SR)这个人开头主张与后来主张的不同点在于：后来认为有 PQ必同时有 R，开头时没有这样的主张。（ 7）解：a) P: 上午下雨。 Q: 我去看电影。 R: 我在家里读书。 S: 我在家里看报。 ( PQ) (P(RS)b) P: 我今天

6、进城。 Q:天下雨。 QPc) P: 你走了。 Q: 我留下。 QP1-4（ 4）解： a)PQQ RP(QR)PQ(PQ)RRTTTTTTTFFTFTTFFFFFFFFFTFTFFFTFFFFFTTFTFFFTFFF所以， P(QR)(PQ)Rb)PPQR RQ (Q QR)TTTTTFTFTTFFFTTFTFFFTFFF所以， P(QR) (PQ)R ）(PP Q) RTFFFFFFFFFF （） （）（）所以， P(QR)(PQ)(PR)）PQ PQPQ(PQ)PQ(PQ)TTFFFFFFTFFTTTFFFTTFTTFFFFTTTTTT所以， (PQ)P Q,(PQ) PQ（ 5）解：如

7、表，对问好所填的地方，可得公式F1F6，可表达为PQRF1F2F3F4F5F6TTTTFTTFFTTFFFTFFFTFTTFFTTFTFFFTFTTFFTTTFFTTFFTFTFFFTFFFTTFTTTFFF F F T F T T T F1:(Q P)RF2:(P Q R)( P Q R)F3:(P Q)(QR)F4:( P QR)(P QR)F5:( P QR)( P Q R)F6: (PQR)(6)11111111P Q2 3 4 5 6 7 8 9 0 1 2 3 4 5 6FFTFTFTFTTFTFTFTFFFFFTTFFTTFTTFFTTTFTFFFFTTTTFFFTTTTFFTF

8、TTTTTTTTF F F F F F F T解：由上表可得有关公式为1.F2.(P Q)3.(QP)4. P5. (P Q)6. Q7.(PQ)8. (P Q)9.P Q10.PQ11.Q12.P Q13.P14.Q P15.P Q16.T(7) 证明：a) A(BA) A( BA) A ( A B)A (A B)A(A B)b) (AB)(A B) ( A B) (A B) (A B) (A B) (AB)或 (AB)(A B) (B A) ( A B)( BA) ( A B)( A A) (B B) (BA) ( A B)(B A) ( (A B) (AB)(AB) (AB)c) (AB

9、)( A B)A Bd) (A B) (A B) (BA) ( AB)( B A) (A B) ( AB)e) (A BC)D) (C(A BD)( (A B C)D)( C (A BD)( (A B C)D)( ( A BC) D) ( (A BC) ( A B C) D (A BC)( A BC) D (A B)( A B) C)D(C (AB) D)f)A(B C)A(B C)( AB) C (A B) C (A B) Cg) (A D) (BD) ( AD) ( BD) ( A B) D (AB) D (A B) Dh) (A B)C)(B (DC)( (A B) C)( B(D C)

10、( (AB) ( BD) C( (A B) ( DB) C (A B) ( DB) C(A D) B)C(B (D A) C（ 8）解：a) (A B)( B A) C( AB)(B A) C( AB)( A B) CTCCb) A( A (B B) (A A) (B B) TF T c) (A BC)( ABC)(A A) (B C)T(B C)BC（ 9）解： 1）设 C为 T，A 为 T， B 为 F，则满足 A C B C，但 A B 不成立。2 ）设 C为 F，A 为 T，B 为 F，则满足 A C B C，但 A B不成立。3）由题意知 A 和 B 的真值相同，所以A 和 B 的真

11、值也相同。习题 1-5（ 1） 证明：a) (P (P Q) Q(P ( P Q) Q(P P)(P Q) Q(PQ)Q (P Q)Q P QQ PTTb) P(P Q)P ( P Q)(P P) QT QTc)(P Q) (QR) (PR)因为 (PQ)(Q R)(P R)所以(P Q)(QR)为重言式。d) (a b) (b c) (c a)(a b) (b c) (c a)因为 (a b) (b c) (c a)(a c) b) (c a)(a c) (c a) (b (c a)(a c) (b c) (b a)所以 (a b) (b c) (c a)(a b) (b c) (c a)为

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

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

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

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

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

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

18、 为 F，则 A 为 F， B 为 T，故 A B 为 T。若 A 为 F，B 为 T，则 A 为 T， B 为 F，故 A B 为 T。若 A 为 F，B 为 F，则 A 为 T， B 为 T，故 A B 为 T。命题得证。e) A(B C)， D E， (DE) A BC 设 A (B C)，DE，(D E) A 为 T，则 DE 为 T，(DE) A 为 T，所以 A 为 T 又 A (B C)为 T，所以 BC 为 T。命题得证。f) (A B) C， D， CD A B设 (AB) C， D， CD 为 T，则 D 为 T， CD 为 T，所以 C 为 F又(A B) C为 T，所以

19、 AB 为 F，所以 A B 为 T。命题得证。T（ 9）解：P Pa) 如果他有勇气，他将得胜。( P P)(PP)P：他有勇气Q：他将得胜P(P P)原命题： PQ逆反式： Q P 表示：如果他失败了，说明他没勇气。P( PQ)b) 仅当他不累他将得胜。P (PQ)P：他不累Q：他得胜T原命题：QP逆反式： P Q 表示：如果他累，P P他将失败。( P P)(P P) P)习题1-6(P P)P) (P P) P)(1) 解：(4) 解：a) (P Q) P (P P) Q (T Q)PQb) (P (Q R) P Q( P Q)( P (Q R) PQ(P P) (QQ)( P PQ)

20、(Q PQ)( R PQ)(P P) (Q Q) (P P) (Q Q)( PQ)( PQ)( P RQ)(5) 证明：PQ (BC)(P Q)( B C)c) P Q( RP)B CP Q (RP) (BC)( P QR)( P QP)( B C)( P QR)FB CP Q R(6) 解：联结词“”和“”不满足结合律。举例如下：(P Q R)a) 给出一组指派： P 为 T，Q为 F，R 为 F，则 (P Q)R 为 T，P (Q(2)解：R)为 Fa) P P P故 (P Q)R P (QR).b)PQ (P Q)(P Q) (P Q)b) 给出一组指派： P 为 T，Q 为 F，R 为

21、 F，则 (P Q) R 为 T，P(Qc)P Q P Q(P P)(QQ) R)为 F(3) 解：故 (P Q) R P (Q R).P ( P Q)(7) 证明：P(P Q)设变元 P，Q，用连结词 , 作用于 P，Q得到： P， Q， P， Q，PQ，P P，QQ，Q P。备的，更不能是最小联结词组。但 PQ Q P，PPQQ，故实际有：已证 , 不是最小联结词组，又因为 PQ（ PQ），故任何P，Q， P， Q，PQ， PP（T）（ A）命题公式中的联结词，如仅用 , 表达，则必可用 , 表达，用作用于（ A）类，得到扩大的公式类（包括原公式类）：其逆亦真。故 , 也必不是最小联结词组

22、。P，Q， P， Q，（ P Q）， T ，F， PQ（ B）(8) 证明 ， 和 不是最小联结词组。用 作用于（ A）类，得到：证明：若 ， 和 是最小联结词，则P Q，P PF， PQ（ PQ），P（PQ）Q， P （PP）P （ P P）P，P （ P P）Q P （ PQ），Q QF，Q（P Q）P， QT Q,P P(P (P ) PQP Q， P（ PQ） Q， P T P,对所有命题变元指派T，则等价式左边为 F，右边为 T，与等价表达式矛 Q（PQ） P， Q T Q,盾。（ PQ）（PQ）P Q.所以 ， 和 不是最小联结词。因此，（A）类使用运算后，仍在（ B）类中。(9)

23、 证明c , 和 , 是最小联结词组。对（ B）类使用运算得：证明：因为 , 为最小联结词组，且 PQ P Q P， Q，P，Q， PQ， F ，T，所以 , 是功能完备的联结词组， 又 , 都不是功能完备的联结（ P Q），词组。仍在（ B）类中。所以 , 是最小联结词组。对（ B）类使用运算得：又因为cccP Q (PQ) ，所以 , 是功能完备的联结词组，又P Q，P PF，P Q （PQ），P（P Q） Q，P TP， ,不是功能完备的联结词组，P F P， P（PQ）Q，所以 c, 是最小联结词组。Q P （P Q），Q Q F，Q （P Q） P，Q T Q, Q F Q， Q （

24、 P Q） P，习题 1-7 P Q P Q，P（PQ）Q，PTP, P F P, P(1)解：（ P Q） Q，P(PQ) Q （P Q） P， Q T Q, Q T Q,Q （P Q） P，P( PQ)（P Q） T（PQ），（PQ） FPQ，（P Q） （ PQ）(P P)(PQ)FP(PQ)T FF，T （ P Q）PQ(P( QQ) ( PQ)F （ P Q）（ P Q）(P Q)(PQ)( PQ)（ PQ）（PQ）P Q.(2)解：故由（ B）类使用 运算后，结果仍在（ B）中。a) ( PQ)R由上证明：用, 两个连结词，反复作用在两个变元的公式中，结果只( PQ)R能产生（ B

25、）类中的公式，总共仅八个不同的公式，故 , 不是功能完P QR(PQ)(P Q) ( QR) ( Q R) (RP)(R P)b) P(Q R)S)P( (QR)S)P Q RS( PQ)( P Q) ( Q R)( Q R) ( R S) ( R S) (SP)(S P)c)(P Q)(S T)( PQ)( ST)( PQ S)( PQ T)d) (PQ)R ( PQ)R (P Q)R(PR)( QR)e) (PQ)(PQ)( P Q)(PQ)( PP)( PQ)( QP)( QQ)( PQ)( QP)(3) 解：a) P( PQR)(P P)(PQ)(PR)(PQ)(PR)b) (PQ)(

26、PQ) ( PQ)(PQ) (P Q)(PQ)(PPQ)( QPQ)c) (PQ) ( PQ)PQ(PQ)(P Q)( Q P)d) (PQ)R ( PQ)R (P Q)R(PR)( QR)e) ( PQ)(P Q)( PP)( P Q)(QP)(Q Q)( P Q)(QP)(4) 解：a) ( P Q)(P Q) ( P Q) (P Q)(PQ) (P Q)( PQ)1， 2， 3PQ=0b) Q(P Q)(P Q) (Q Q)P Q =30， 1， 2(PQ)(P Q) ( PQ)c) P( P(Q( QR)P(P(Q(QR)PQR=01， 2， 3,4,5,6,7=( P QR) ( P

27、Q R) ( PQR)(P Q R) (P QR) (PQ R)(P QR)d) (P(QR) ) ( P( Q R) ( P(QR) (P( Q R)(P P) (P(QR) ( Q R) P) ( Q R) (QR)(PQR) ( P Q R) =0,71， 2， 3,4,5,6(PQ R) (P QR) (P Q R) ( PQR) ( PQ R) ( P QR) e) P(P(QP)P(P( QP)( PP)( P QP) T(T Q) T0,1,2,3 = ( P Q) ( PQ) (P Q) (PQ)d)f) (QP) ( PQ)A(A(AB)( QP) PQA A(AB)( QP

28、) (P Q)FT0,1 ，2 ，3 = (P Q) (P Q) ( PQ) ( P Q)A B(AB)(5) 证明：(AB) (AB)a)T(AB) (AC)(6) 解： AR(Q (RP), 则 A* R(Q (RP)( AB) ( AC)A R(Q (RP)A(BC)(R(Q(RP)A(BC)R Q (RP)( AB) ( AC)(RQ) (RP)b)A* R(Q (RP)(AB) (AB)(RP)( AB) (AB)R Q (RP)(A B) (AB)(RQ) (RP)A(B B)(7) 解：设 A：A 去出差。 B：B 去出差。 C：C去出差。 D： D去出差。AT若 A 去则 C

29、和 D中要去一个。A (C V D)A( AB) (BA)B 和 C不能都去。(B C)(AB) ( BA)C 去则 D要留下。C DA(B B)按题意应有： A(C V D)， (BC)，CD 必须同时成立。AFA因为 CV D(C D) (D C)c)AB( A B)故(A(C V D) (BC) (C D)(A A)(A B) BAB B( A(C D) (D C) (BC) ( C D)F( A(C D) (D C)( B C) ( C D)A B(AB)( A(CD) (DC)( B C) ( B D)( AA)( AB) B( C D) C)A BB( A BC) ( A BD)

30、( A CD)F( A C)(BCD) ( CD B D) ( CD CD)(5)PQ(4)T,E( CD C) ( DC BC) ( DC BD)(6)P(3)(5)T,I( DC CD) ( DC C)b)J (MN)， (HG) J，HG M N在上述的析取范式中，有些（画线的）不符合题意，舍弃，得(1)(H G) JP( A C) ( B CD) （ CD） ( DC B)(2)(H G)P故分派的方法为： BD , 或 DA, 或 CA。(3)J(1)(2)T,I(8) 解：设 P：A 是第一。 Q：B 是第二。 R：C是第二。 S：D 是第四。 E：(4) J (MN)PA 是第二

31、。(5)M N(3)(4)T,I由题意得 (P V Q) (R V S) (E V S)c)B C，(B C) (HG)GH(1)B CP(P Q) ( PQ)(R S) ( RS) (E S)(2)B(1)T,I( ES)(3)C(1)T,I(P QR S) (P Q RS)( PQR S)(4)B C(2)T,I( PQ RS) (E S)( ES)(5)C B(3)T,I因为(P Q RS)与( PQR S)不合题意，所以原(6)C B(4)T,E式可化为(7)B C(5)T,E(P Q R S)( PQ RS) (E S)(8)BC(6)(7)T,E( ES)(9)(BC) (HG)P

32、(P QR SE S) (P QR S ES)(10) H G(8)(9)T,I( PQ RSE S)( PQ RS ES)d)P Q，( QR) R， ( PS) S(P QR SE) ( PQ RS E)(1)( QR) R因 R与 E 矛盾，故 PQ RSE 为真，(2)QR(1)T,I即 A 不是第一， B 是第二， C 不是第二， D为第四， A 不是第二。(3)R(1)T,I于是得： A 是第三B 是第二C 是第一D(4)Q(2)(3)T,I是第四。(5) P QP(6)P(4)(5)T,I习题 1-8(7)( P S)P(1) 证明：(8)P S(7)T,Ea) (P Q)， QR， R P(9)S(6)(8)T,I(1) RP(2) 证明：(2) Q RPa) A B， C B A C(3) Q(1)(2)T,I(1)(A(4) (P Q)PC)P(6)C D(4)(5)T,I(2)A(1)T,I(7)C(6)T,I(3)C(1)T,I(8)D(6)T,I(4) A BP(9)D E(8)T,I(5)B(2)(4)T,I(10)D EFP(6)C BP(11)(7) B(3)(6)T,IF(9)(10)T,I(8)B B矛盾。