《离散数学 ch1.》由会员分享，可在线阅读，更多相关《离散数学 ch1.（39页珍藏版）》请在金锄头文库上搜索。
1、东北石油大学 离散数学 Discrete Mathematics (第1章) School of Software, Northeast Petroleum University 2 计算机学院 School of computer q: 雪是白色的; r: a能被4整除; s: a能被2整除. 将下列命题符号化，并指出真值。 (1) 如果3+36，则雪是白的。 (2) 如果3+36，则雪是白的。 (3) 如果3+36，则雪不是白的。 (4) 如果3+36，则雪不是白的。 (5) 只要a能被4整除，则a一定能被2整除。 (6) a能被4整除，仅当a能被2整除。 (7) 除非a能被2整除，a才能
2、被4整除。 (8) 除非a能被2整除，否则a不能被4整除。 (9) 只有a能被2整除，a才能被4整除。 (10) 只有a能被4整除，a才能被2整除。 1.1 命题与联结词 pq pq p q p q rs rs rs rs rs sr 真值:1 真值:1 真值:0 真值:1 真值:1 真值:1 真值:1 真值:1 真值:1 与a有关 17 计算机学院 School of computer q:3+3=6; r:3是偶数; s:日出东方; t:驼鸟会飞; u: f (x) 在 x0 可导; v: f (x) 在 x0连续. 将下列复合命题符号化，并指出真值。 (1) 2 + 2 4 当且仅当 3
3、 + 3 6. (2) 2 + 2 4 当且仅当 3 是偶数. (3) 2 + 2 4 当且仅当日出东方. (4) 2 + 2 4 当且仅当驼鸟会飞. (5) f (x) 在 x0可导当且仅当它在 x0 连续. p q 1 p r 0 u v 0 p s 1 p t 0 联结词运算顺序: , , , , , 同级按出现顺序运算. 18 计算机学院 School of computer 若使A为0, 则称 这组值为A的成假赋值. 21 计算机学院 School of computer 成假赋值赋值 :011,101,111 p q rpq r (pq)r 0 0 0 0 0 1 0 1 0 0
4、1 1 1 0 0 1 0 1 1 1 0 1 1 1 0 0 1 1 1 1 1 1 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1.2 命题公式及其赋值 24 计算机学院 School of computer 无成假赋值 p q qp(qp)q(qp)qp 0 0 0 1 1 0 1 1 1 0 1 1 0 0 0 1 1 1 1 1 1.2 命题公式及其赋值 25 计算机学院 School of computer 无成真赋值 p q ppq (pq) (pq)q 0 0 0 1 1 0 1 1 1 1 0 0 1 1 0 1 0 0 1 0 0 0 0 0 1.2 命
5、题公式及其赋值 26 计算机学院 School of computer (2) 若A在它的任何赋值下均为假, 则称A为矛盾式或永假式; (3) 若A不是矛盾式, 则称A是可满足式. 由上例可知, (pq) r, (qp) qp, (pq) q 分别为非重言式的可满足式, 重言式, 矛盾式. 注意：重言式是可满足式，但反之不真. 27 计算机学院 School of computer & information technology (1) 求出公式的全部成真赋值与成假赋值 (2) 判断公式的类型: 末列全1(重言)全0(矛盾)其他可满足 7 真值表的用途 例1.10:下列公式哪些真值表相同？
6、(1) pq；(2) qr；(3) (pq)(pr)p)； (4) (qr)(pp) 例1.9: 下列公式哪些真值表相同？ (1) pq；(2) pq；(3) (pq)；(4) (pq)(qp)； (5) qp 1.2 命题公式及其赋值 28 计算机学院 School of computer & information technology 第一章 小结 l 命题、真值 l 简单命题及符号化 l 联结词, , , , l 复合命题及符号化 l 命题公式及层次 l 公式的类型 l 真值表及应用 29 计算机学院 School of computer & information technolog
7、y 1. 将下列命题符号化 (1) 豆沙包是由面粉和红小豆做成的. (2) 苹果树和梨树都是落叶乔木. (3) 王小红或李大明是物理组成员. (4) 王小红或李大明中的一人是物理组成员. (5) 由于交通阻塞，他迟到了. (6) 如果交通不阻塞，他就不会迟到. (7) 他没迟到，所以交通没阻塞. (8) 除非交通阻塞，否则他不会迟到. (9) 他迟到当且仅当交通阻塞. 巩固练习1 30 计算机学院 School of computer & information technology 提示：分清复合命题与简单命题 分清相容或与排斥或 分清充分与必要条件及充分必要条件 巩固练习1 (续) 解答：
8、(1) 是简单命题p 设 p: 苹果树是落叶乔木，q:梨树是落叶乔木 (2) pq 设 p: 王小红是物理组成员，q:李大明是物理组成员 (3) pq (4) (pq)(pq) 设 p: 交通阻塞，q: 他迟到 (5) pq (6) pq (7) qp (8) qp (9) qp 31 计算机学院 School of computer & information technology 巩固练习2 2. 设 p : 2是素数 q : 北京比天津人口多 r : 美国的首都是旧金山 求下面命题的真值 (1) (pq)r (2) (qr)(pr) (3) (qr)(pr) (4) (qp)(pr)(r
9、q) 0 1 0 0 32 计算机学院 School of computer & information technology 巩固练习3 3. 用真值表判断下面公式的类型 (1) pr(qp) (2) (pq) (qp) r (3) (pq) (pr) 33 计算机学院 School of computer & information technology 巩固练习3 (续) (1) pr(qp) 矛盾式 p q rpr (qp ) pr(q p) 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 0 0 0 0 0 1 0 1 0 0 1 1
10、0 0 0 0 0 0 0 0 0 0 0 0 34 计算机学院 School of computer & information technology 巩固练习3 (续) (2) (pq) (qp) r 重言式 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 0 1 1 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 (pq) (qp) r qp pq p q r 35 计算机学院 School of computer & information technology 巩固练习3 (续) (3) (pq) (
11、pr) 非永真式的可满满足式 p q rpq pr (pq) (pr) 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 0 0 1 36 计算机学院 School of computer & information technology 习题一(部分习题解答) pq (p q)(pq)或pq pq pq pq pq qp qp (pq)r (pq) 14. 将下列命题符号化 (1) 刘晓月跑得快 ，跳得高 。 (2) 老王是山东人 或河北人 。 (3) 因为天气冷
12、 ，所以我穿了羽绒服 。 (4) 王强 与刘威 都学过法语。 (5) 他一面吃面包 ，一面听音乐 。 (6) 如果天下大雨 ，他就乘车上班 。 (7) 只有天下大雨 ，他才乘车上班 。 (8) 除非天下大雨 ，否则他不乘车上班 。 (9) 下雪 路滑 ，他迟到了 。 (10) 2 与4 都是素数，这是不对的。 要点：分清复合命题与简单命题, , , , 分清相容或与排斥或 分清必要与充分条件及充分必要条件 (p)(q) (p)(q) (p)(q) (p)(q) (p)(q) (p)(q) (p)(q) (p)(q) (p)(q)(r) (p)(q) 37 计算机学院 School of com
13、puter & information technology 19. 用真值表判断下列公式类型 (4) (pq)(q p) (5) (pr)( p q) (6) (pq)(qr)(pr) 习题一(部分习题解答) 重言式 非重言的可满足式 重言式 20. 求下列公式的成真赋值 (3) (pq) p (4) (pq) q 00 01 10 01 10 11 21. 求下列公式的成假赋值 (3) (pq)(pr)p) 100 101 38 计算机学院 School of computer & information technology 习题一(部分习题解答) 22. 已知公式(qp)p是矛盾式，求公式(qp)pr 的成真赋值和成假赋值。 无成真赋值 23. 已知公式(pq)p是重言式，求公式(pq)p)r 的成真赋值和成假赋值。 无成假赋值 39 计算机学院 School of computer & information technology Hello! This chapter ends, thank you!
