离散数学课后习题答案(第一章)

1-11-1，1-21-2 （1） 指出下列哪些语句是命题，那些不是命题，如果是命题，指出它的真值。 a) 离散数学是计算机科学系的一门必修课。是命题，真值为 T。 b) 计算机有空吗？不是命题。 c) 明天我去看电影。是命题，真值要根据具体情况确定。 d) 请勿随地吐痰。不是命题。 e) 不存在最大的质数。是命题，真值为 T。 f) 如果我掌握了英语，法语，那么学习其他欧洲语言就容易多了。是命题，真值为 T。 g) 9+512.是命题，真值为 F。 h) X=3.不是命题。 i) 我们要努力学习。不是命题。 （2） 举例说明原子命题和复合命题。 原子命题：我爱北京天安门。 复合命题：如果不是练健美操，我就出外旅游拉。 （3） 设P表示命题“天下雪。 ” Q表示“我将去镇上。 ” R表示命题“我有时间。 ” 以符号形式写出下列命题 a) 如果天不下雪和我有时间，那么我将去镇上。(P R)Q b) 我将去镇上，仅当我有时间时。QR c) 天不下雪。P d) 天下雪，那么我不去镇上。PQ （4） 用汉语写出一些句子，对应下列每一个命题。 a)()QRP¬ Q:我将去参加舞会。R:我有时间。P:天下雨。 Q (RP):我将去参加舞会当且仅当我有时间和天不下雨。 b)RQ R:我在看电视。Q:我在吃苹果。 RQ:我在看电视边吃苹果。 c) ()()QRRQ Q:一个数是奇数。R:一个数不能被 2 除。 （QR）(RQ):一个数是奇数，则它不能被 2 整除并且一个数不能被 2 整除，则它是奇数。 (5) 将下列命题符号化。 a) 王强身体很好，成绩也很好。 设 P：王强身体很好。Q：王强成绩很好。PQ b) 小李一边看书，一边听音乐。 设 P：小李看书。Q：小李听音乐。PQ c) 气候很好或很热。 设 P：气候很好。Q：气候很热。PQ d) 如果 a 和 b 是偶数，则ab+是偶数。 设 P： a 和 b 是偶数。Q：a+b 是偶数。PQ e) 四边形ABCD是平行四边形，当且仅当它的对边平行。 设 P：四边形 ABCD 是平行四边形。Q ：四边形 ABCD 的对边平行。PQ f) 停机的原因在于语法错误或程序错误。 设 P：语法错误。Q：程序错误。R：停机。 （P Q） R (6) 将下列复合命题分成若干原子命题。 a) 天气炎热且正在下雨。P:天气炎热。Q:正在下雨。PQ b) 天气炎热但湿度较小。P:天气炎热。R:湿度较低。PR c) 天正在下雨或湿度很大。R:天正在下雨。S:湿度很高。 RS d) 刘英与李进上山。A:刘英上山。B:李进上山。AB e) 老王或小李是革新者。M:老王是革新者。N:小李是革新者。MN f) 如果你不看电影，那么我也不看电影。L:你看电影。M:我看电影。LM g) 我既不看电视也不外出，我在睡觉。P:我不看电视。Q:我不外出。 R:我在睡觉。PQR 1-31-3 （1）判别下列公式哪些是合式公式，哪些不是合式公式。 a)().QRS不是合式公式，没有规定运算符次序（若规定运算符次序后亦可作为合式公式） b)().PRS是合式公式 c)()().PQQP¬不是合式公式（括弧不配对） d)().RST不是合式公式（R 和 S 之间缺少联结词） e)()()().PQRPQPR是合式公式。 （2）根据合式公式的定义，说明下列公式是合式公式。 a） ().AAB A 是合式公式，(AB)是合式公式，(A(AB) 是合式公式。这个过程可以简记为：A；(AB)；(A(AB) 同理可记 b） ().ABA¬ A；A ；(AB) ；(AB)A) c） ()()ABBA¬ A；A ；B；(AB) ；(BA) ；(AB)(BA) d） ()().ABBA A；B；(AB) ；(BA) ；(AB)(BA) （3）对下列公式用指定的公式进行代换。 a）(),ABBA用( )AC 代换A，用()BCA代换B (AC)(BC)A)(BC)A)(AC) b） ()()ABBA，用B代换A。 (BA)(AB)。 （5）试把原子命题表示为,P Q R等，然后用符号译出下列各句子。 a) 或者你没有给我写信，或者它在途中丢失了。P: 你没有给我写信。 R: 信在途中丢失了。()PQ¬ b) 如果张三和李四都不去，他就去。P: 张三不去。Q: 李四不去。R: 他就去。(PQ)R c) 我们不能既划船又跑步。P: 我们能划船。 Q: 我们能跑步。 (PQ) d) 如果你来了，那么他唱不唱歌将看你是否伴奏。P: 你来了。Q: 他唱歌。R: 你伴奏。 P(QR) （7）用符号形式写出下列命题。 a) 假如上午不下雨，我去看电影，否则就在家里读书或看报。 P: 上午下雨。 Q:我去看电影。 R:我在家里读书。 S:我在家里看报。(PQ)(P(RS) b) 我今天进城，除非下雨。 P: 我今天进城。Q:天下雨。QP c) 仅当你走我将留下。 P: 你走了。 Q:我留下。QP 1-41-4 (7)证明下列等价式。 a)()()ABAAAB ¬ ¬ 证明： A(BA) A(BA) A(AB) A(AB) A(AB) b)()()()ABABAB¬¬ 证明：(AB) (AB)(AB) (AB)(AB) (AB)(AB) 或 (AB) (AB)(BA) (AB)(BA) (AB)(AA)(BB)(BA) (AB)(BA) (AB)(AB) (AB)(AB) c)()ABAB¬¬ 证明：(AB) (AB)AB d)()()()ABABAB¬¬ ¬ 证明：(AB)(AB)(BA) (AB)(BA) (AB)(AB) e) ()()()ABCDCABDCABD 证明：(ABC)D)(C(ABD) (ABC)D)(C(ABD) (ABC)D)(ABC)D) (ABC)(ABC)D (ABC)(ABC)D (AB)(AB)C)D (C(AB)D) f)()()ABCABC¬ 证明：A(BC) A(BC) (AB)C (AB)C (AB)C g) ()()()ADBDABD 证明：(AD)(BD)(AD)(BD) (AB)D (AB)D (AB)D h) ()()()ABCBDCBDAC 证明：(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) (BA)C (AB) (AB)C TCC B）A(A(BB) 解：A(A(BB)(AA)(BB)TFT C）(ABC)(ABC) 解：(ABC)(ABC) (AA) (BC) T(BC) BC （9）如果ACBC，是否有AB？如果ACBC，是否有AB？如果AB¬ ¬，是否有AB？ 解：1）设 C 为 T，A 为 T，B 为 F，则满足 ACBC，但 AB 不成立。 2）设 C 为 F，A 为 T，B 为 F，则满足 ACBC，但 AB 不成立。 3）由题意知A 和B 的真值相同，所以 A 和 B 的真值也相同。 习题习题 1-51-5 （1） 试证下列各式为重言式。 a) (P(PQ)Q 证明：(P(PQ)Q (P(PQ)Q (PP)(PQ)Q (PQ)Q (PQ)Q PQQ PT T b) P(PQ) 证明：P(PQ) P(PQ) (PP)Q TQ T c) (PQ)(QR)(PR) 证明：(PQ)(QR)(PR) 因为(PQ)(QR)(PR) 所以(PQ)(QR)为重言式。 d) (ab)(bc) (ca)(ab)(bc)(ca) 证明：(ab)(bc) (ca)(ab)(bc)(ca) 因为(ab)(bc)(ca) (ac)b)(ca) (ac)(ca)(b(ca) (ac)(bc)(ba) 所以(ab)(bc) (ca)(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)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(PP)(R(R(PP)RQ 成立。 （3） 设 P 表示命题“8 是偶数” ，Q 表示命题“糖果是甜的” 。试以句子写出： a)PQ 表示命题“如果 8 是偶数，那么糖果是甜的” 。 b) a)的逆换式 QP 表示命题“如果糖果是甜的，那么 8 是偶数” 。 c) a)的反换式PQ 表示命题“如果 8 不是偶数，那么糖果不是甜的” 。 d) a)的逆反式QP 表示命题“如果糖果不是甜的，那么 8 不是偶数” 。 （4） 叙述下列各个命题的逆换式和逆反式，并以符号写出。 a) 如果天下雨，我不去。 设 P：天下雨。Q：我不去。PQ 逆换式 QP 表示命题:如果我不去，则天下雨。 逆反式QP 表示命题:如果我去，则天不下雨 b) 仅当你走我将留下。 设 S：你走了。R：我将留下。RS 逆换式 SR 表示命题：如果你走了