《离散数学复习资料全[文摘][整理]》由会员分享，可在线阅读，更多相关《离散数学复习资料全[文摘][整理]（96页珍藏版）》请在金锄头文库上搜索。
1、离散数学习题与解答 第一篇数理逻辑 第一章命题逻辑 1-1（1）指出下列语句哪些是命题，哪些不是命题，如果是命题指出他的真值 a)离散数学是计算机科学系的一门必修棵 b)2 吗？ c)明天我去看电影 d)请勿随地吐痰 e)不存在最大质数 f)如果我掌握了英语，法语，那么学习其他欧洲的语言就容易多了 g)9+512 h)x3 i)月球上有水 j)我正在说假话 解 a)不是命题 b)是命题 , 真值视具体情况而定 c)不是命题 d)是命题 , 真值为 t e)是命题 , 真值为 t f)是命题 , 真值为 f g)不是命题 h)是命题 , 真值视具体情况而定 i)不是命题 1-2(1) 用 P表示
2、命题“天下雪”,( 又表示命题“我将去镇上”,R 表示命题“我有时间”. 以 符号形式写出下列命题: (a) 如果天不下雪和我有时间, 那么我将去镇上. (b) 我将去镇上，仅当我有时间. (c) 天不下雪 (d) 天下雪 , 那么我不去镇上 解 a)( PR)Q b)QR c) P d)P Q 1-2(2) 将下面这段述中所出现的原子命题符号化, 并指出他们的真值, 然后将这段述中的每 一命题符号化2 是有理数是不对的.2 是偶素数 .2 或 4 是素数 . 如果 2 是素数则3 也是素 数.2 是素数当且仅当3 也是素数 . 解: 述中出现5 个原子命题，将他们符号化为: P: 2 是有理
3、数其真值为F Q:2 是素数其真值为T R:2 是偶数其真值为T S:3 是素数其真值为T U:4 是素数其真值为F 述中各命题符号化为: P;QR;QU;QS;Q S 1-2(3) 将下列命题符号化 a)如果 3+3=6, 则雪是白色的. b)如果 3+36, 则雪是白色的 c)如果 3+3=6, 则雪不是白色的. d)如果 3+36, 则雪不是白色的 e)王强身体很好，成绩也很好. f)四边形 ABCD 是平行四边形, 仅当其对边平行 解: 设 P:3+3=6 Q:雪是白色的 R:王强成绩很好S: 王强身体很好 U: 四边形 ABCD是平行四边形V: 四边形 ABCD的对边是平行的 于是
4、: a)可表示为 :PQ b)可表示为 : PQ c)可表示为 : P Q d)可表示为： P Q e)可表示为： SR f)可表示为 :U V 1-3(1) 判别下列公式中哪些是合式公式,那些不是合式公式 a) (QR S) b) (P (R S) c) (P Q)(QP) d) (RS T) e)(P (QR) (P Q)(PR) 解: a)不是合式公式( 若规定运算符优先级后也可以作为合式公式) b)是合式公式 c) 不是合式公式( 括号不配对 ) d)不是合式公式 e)是合式公式 1-3(2) 对下列各式用指定的公式进行代换: a) (AB)B) A), 用（ AC）代换 A，用（ （
5、BC） A代换 B。 b)(A B)(BA), 用 B代换 A,A 代换 B. 解:a)(AC)(B C)A) (B C)A) (AC) b)(B A)(AB) 1-3(3) 用符号形式写出下列命题 a)假如上午不下雨, 我去看电影 ; 否则就在家里读书或看报. b)我今天进城 , 除非下雨 . c)仅当你走 ,我将留下 . 解a) 设 P:上午天下雨 . Q:我去看电影 R:我在家读书S:我在家看报 原命题可译为:( PQ)(P(RS) b) 设:P: 我今天进城Q:天下雨 原命题可译为: Q P c) 设:P: 你走Q:我留下 原命题可译为:QP (4) 称 P Q为条件命题PQ的反换式
6、QP为条件命题PQ的逆换式 Q P为条件命题PQ的逆反式 试写出如下条件命题的反换式，逆换式，逆反式。 （a）如果他有勇气，则他将得胜。 （b）如果天下雨，我不去。 解 （a）设 P：他有勇气，Q ：他将得胜 原条件命题可译为：PQ 反换式： P Q，表示：如果他没有勇气，则他将不能获胜。 逆换式： QP，表示：如果他将得胜，则他有勇气。 逆反式： Q P，表示：如果他不获胜，则他没有勇气。 （b）设 P：天下雨， Q：我去 原条件命题可译为：P Q 反换式： PQ ，表示：如果如果天不下雨，则我去。 逆换式： QP，表示：如果我不去，则天下雨。 逆反式： Q P，表示：如果我去，则天不下雨。
7、 1-4（1）试求下列各命题公式的真值表并解释其结果 （a） （PQ）（ QP） ； （b） （PQ） P； （c）Q （ PQ ） ； （d） （PQ）（ P Q ） ； （e） （ P Q ）（ P Q ） ） ； （f ）（ PQ ） QR 。 解 （a）从真值表1-1 中可看出：（PQ ）（ QP）（ P Q ） (b) 从真值表1-2 中可看出：（PQ ） P是永真式 (c) 从真值表1-3 中可看出： Q （ PQ）是永真式 (d) 从真值表1-4 中可看出：（PQ ）（ PQ）是永真式 (e) 从真值表1-5 中可看出：（ PQ）（ P Q） ） PQ PQ （ P Q ） (f
8、) 从真值表1-6 中可看出：（P Q ） Q R是永真式 表 1-1 P Q PQ QP （PQ ）（ Q P） T T T F F T F F T F T T T T F T T F F T 表1-2 表1-3 表 1-4 表 1-5 表 1-6 1-4（2）用真值表判断下列各组公式是否等价： （a）P(Q R)与（ PQ ） R （b）（PQ ） R与（ PQ） R 解 由表 1-7 可知 P(QR) （ PQ ） R 而（ PQ） R（ PQ） R P Q PQ （PQ） P T T T F F T F F T F F F T T T T P Q PQ Q （ PQ ） T T T F
9、 F T F F T T T F T T T T P Q P PQ PQ （PQ ）（PQ ） T T T F F T F F F F T T T F T T T F T T T T T T P Q P Q PQ （ P Q）（ PQ）（ P Q） ） T T T F F T F F F F T T F T F T T F T T T F T T T F T T P Q R PQ （ PQ ）（ PQ ） Q （ PQ ） Q R T T T T T F T F T T F F F T T F T F F F T F F F F F T T T T T T F F T T F F F F F
10、F F F F F F F F F F F F F F F 表 1-7 1-4 （3）试以真值表证明下列命题： （ a）合取运算的结合律 （ b）德摩根定律 解 （a）如表 1-8， （PQ ） R （b）如表 1-9 ，（ PQ ） P Q （ PQ ） P Q 表 1-8 表 1-9 2-4（4）证明下列等价式： （a）A（ BA） A（ A B） ； (b) （AB） C（ A C）（ BC） ； (c) （ A B）（ A B）（ AB） ； (d) （ （ （A B ） C） D）（ C（ A（ BD） ） ）（ C（ A B） ） D 证 （a）A（ BA） A（ B A） （ B
11、 A） A （ A B ） A A（ B A） A（ A B） A（ A B） P Q R P (QR) （PQ ） R （PQ ） R T T T T T F T F T T F F F T T F T F F F T F F F T F T T T T T T T F T T T T T T T F T T T F T F P Q R PQ （PQ） R Q R P（ Q R） T T T T T F T F T T F F F T T F T F F F T F F F T T F F F F F F T F F F F F F F T F F F T F F F T F F F F F
12、 F F P Q P Q P Q （ PQ ）P Q （ P Q ） T T T F F T F F F F T T F T F T F T T T F T T T F F F T F F F T A（ A B） （b） （AC）（ BC）（ AC）（ BC） （ A B） C （ AB） C （ AB）C （c）（ A B） （AB）（ BA） ） （ AB ）（ BA） ） （AB）（ B A） ） （ A B）（ B A） ） （d） （ （AB） C） D）（ C（ A（ BD） ） ） （ AB C） D）（ C（ ABD） ） ） （ A B CD ） （ CA BD） （ CD）
13、（ （ A B）（ AB） ） （ CD）（ （ A B）（ B A） ） （ CD）（ A B）（ BA） ） （ C（ AB ）（ B A） ） ） D （ C（ AB）（ BA ） ） D （ C（ AB）（ B A） ） D （ C（ A B） ） D （ C（ A B） ） D 1-4（5）判断下列命题公式的类型（永真；永假；非永真，也非永假）： （a） （ P Q ） P） Q ； （b）（ P(P Q)） R； （c）P (P Q) P) Q). 解 （a） （ P Q） P） Q （ PQ） P） Q （ P Q） P） Q （PQ） P） Q （P Q） P） Q （P P）
14、（ Q P） ） Q （ Q P） Q T P T （ a）为永真式 （ b）（ P(P Q)） R （P P Q ） R （ P P Q） R FR F （ b ）为永假式 （ c）P (P Q) P) Q) P ( (P Q) P) Q) P ( (P P ) (Q P) Q) P ( (F(Q P) Q) P ( Q P Q) PT P （ c ）为非永真式，也非永假式 1-4.(6)化简如下语句： “情况并非如此：若他不来，则我不去”。 解 ：首先符号化上述语句。 设 P：他来。 Q：我去 则原句：（P Q ） 然后化简上述命题公式 （ P Q ） （Q P） （ QP） （QP） Q
15、 P 即：我去了，但他未来。 14（7） （a）如果 AC BC，是否有A B？ 如果 A C BC，是否有A B？ 如果 A B，是否有 A B？ 解 （a）不能说必有A B，因为当AC BC时，有可能某种指派使C为 T， 但 A、B的值并不相同 （b）不能说必有A B，因为当 AC B C时，有可能某种指派使C 为 F，但 A 、 B的值并不相同 （c）结论正确。因为（AB）（ B A） ，所以 B A 为永真式 时， AB也是永真式。即B A时，必有 A B。同理 A B时，B A。所以 B A时，必有A B 15（1）试证下列各式为永真式： （a） （P （ P Q） ） Q ； （b） P（ P Q） ； （c） （ PQ）（ QR ） ）（ PR） ； （d） （ PQ）（ QR ）（ RP） ）（PQ ）（ Q R）（ RP） ） 解 （a） （P （ P Q ） ） Q （ P （ PQ） ） Q （ P P）（ PQ） ） Q （ P Q ） Q （ P Q） Q P QQ
