离散数学（课件上习题） 第一章

例1-1.1 判定下面这些句子哪些是命题。 ⑴ 2是个素数。 ⑵ 雪是黑色的。

⑶ 2013年人类将到达火星。 ⑷ 如果 a>b且b>c，则a>c 。（其中a,b,c都是 确定的实数） ⑸ x+y<5 ⑹ 请打开书！

⑺ 您去吗？ ⑴⑵⑶⑷是命题

例1-2.1 P：2是素数。

?P：2不是素数 。 例1-2.2 P：小王能唱歌。 Q：小王能跳舞。

P∧Q：小王能歌善舞。 例1-2.3. 灯泡或者 线路有故障。（析取“∨”） 例1-2.4. 第一节课上数学或者上英语。（异或 、排斥或 。即“?”） 注意：P ? Q 与 (P∧?Q)∨(Q∧?P ) 是一样的。 归纳自然语言中的联结词，定义了六个逻辑联结词，分别是：（1）否定 “? ” (2) 合取 “∧ ” (3) 析取 “∨ ” (4) 异或 “? ” (5) 蕴涵 “? ” (6) 等价 “? ”

例1-2.5： P表示：缺少水分。 Q表示：植物会死亡。

P?Q：如果缺少水分，植物就会死亡。

P?Q：也称之为蕴涵式，读成 “P蕴涵Q”， “如果P则Q”。 也说成P是P?Q 的前件，Q是P?Q的后件。

还可以说P是Q的充分条件，Q是P的必要条件。 以下是关于蕴含式的一个例子

P：天气好。 Q：我去公园。 1.如果天气好，我就去公园。 2.只要天气好，我就去公园。 3.天气好，我就去公园。 4.仅当天气好，我才去公园。 5.只有天气好，我才去公园。 6.我去公园，仅当天气好。 命题1.、2.、3.写成： P?Q 命题4.、5.、6.写成： Q?P

例1-2.6： P：△ABC 是等边三角形。 Q ：△ABC是等角三角形。 P?Q ：△ABC 是等边三角形 当且仅当它是等角三角形。

1

课后练习：填空

已知P∧Q为T，则P为( )，Q为( )。 已知P∨Q为F，则P为( )，Q为( )。 已知P为F，则P∧Q为( )。 已知P为T，则P∨Q为( )。

已知P∨Q为T，且P为F ，则Q为( )。 已知P?Q为F，则P为( )，Q为( )。 已知P为F，则P?Q为( )。 已知Q为T，则P?Q为( )。

已知 ?P??Q为F，则P为( )， Q为( )。 已知P为T， P?Q为T，则Q为( )。 已知?Q为T, P?Q为T，则P为( )。 已知P?Q 为T ，P 为T , 则Q 为( ). 已知P?Q 为F ，P 为T , 则Q 为( ). P?P 的真值为( ). P?P 的真值为( )。

1—3节

例1.说离散数学无用且枯燥无味是不对的。 P：离散数学是有用的。

Q：离散数学是枯燥无味的。 该命题可写成： ? (?P∧Q)

例2. 如果小张与小王都不去，则小李去。

P ： 小张去。 Q ： 小王去。 R ： 小李去。 该命题可写成： (?P∧?Q)?R

如果小张与小王不都去，则小李去。 该命题可写成： ?(P∧Q)?R 也可以写成： (?P∨?Q)?R

例3. 仅当天不下雨且我有时间，才上街。 P：天下雨。Q：我有时间。R：我上街。

分析：由于 “仅当 ”是表示 “必要条件 ”的，既 “天不下雨且我有时间 ”，是 “我上街 ”的必要条件。所以

该命题可写成： R?(?P∧Q)

例4. 人不犯我，我不犯人；人若犯我，我必犯人。 P ： 人犯我。Q ： 我犯人。

该命题可写成：(?P??Q)∧(P?Q)或写成： P?Q 例5 .若天不下雨，我就上街；否则在家。 P：天下雨。Q ：我上街。R：我在家。 该命题可写成： (?P?Q)∧(P?R). 注意：中间的联结词一定是“∧”，而不是“∨”，也不是“? ”。

2

1—4节

重言(永真)蕴涵式证明方法 方法1.列真值表。

方法2.假设前件为真，推出后件也为真。 例如求证：

((A∧B)?C)∧?D∧(?C∨D) ? ?A∨?B

证明:设前件((A∧B)?C)∧?D∧(?C∨D) 为真则((A∧B)?C)、?D、(?C∨D)均真， ?D为T，则D为F

?C∨D为T 得C为F

((A∧B)?C )为T 得A∧B为F 如果A为F，则?A为T，所以?A∨?B为T。 如果B为F，则?B为T，所以?A∨?B 为T。 ?((A∧B)?C)∧?D∧(?C∨D) ? ?A∨?B 方法3.假设后件为假，推出前件也为假 。

例如求证： ((A∧B)?C)∧?D∧(?C∨D) ? ?A∨?B 证明: 假设后件?A∨?B 为F, 则A 与B 均为T 。

1. 如C 为F ，则(A∧B)?C为F，所以 前件((A∧B)?C)∧?D∧(?C∨D) 为F 。 2. 如C 为T ，则

⑴ 若D 为T ，则?D 为F ， 所以前件((A∧B)?C)∧?D∧(?C∨D) 为假； ⑵若D为F，则?C∨D 为F ， 所以 前件((A∧B)?C)∧?D∧(?C∨D) 为假。 ?((A∧B)?C)∧?D∧(?C∨D) ? ?A∨?B

重要的重言蕴涵式( 如教材第43 页所示)（课件中出现过多次，可不用记忆） I1. P∧Q?P I2. P∧Q?Q I3. P?P∨Q I4. Q?P∨Q

I5. ?P?P?Q I6. Q?P?Q

I7. ?(P?Q)?P I8. ?(P?Q)??Q I9. P,Q ?P∧Q I10. ?P∧(P∨Q)?Q I11. P∧(P?Q)?Q I12. ?Q∧(P?Q)??P I13. (P?Q)∧(Q?R)?P?R

I14. (P∨Q)∧(P?R)∧(Q?R)?R I15. A?B ?(A∨C)?(B∨C) I16. A?B ?(A∧C)?(B∧C) 1—5节

重要的等价公式（课件中出现多次，可不用记忆）

⑴ 对合律 ??P ?P ⑵ 幂等律 P∨P?P P∧P?P ⑶ 结合律 P∨(Q∨R)?(P∨Q)∨R P∧(Q∧R)?(P∧Q)∧R ⑷ 交换律 P∨Q?Q∨P P∧Q?Q∧P

⑸分配律 P∨(Q∧R)?(P∨Q)∧(P∨R) P∧(Q∨R)?(P∧Q)∨(P∧R) ⑹ 吸收律 P∨(P∧Q)?P P∧(P∨Q)?P

⑺底-摩根定律 ?(P∨Q)??P∧?Q ?(P∧Q)??P∨?Q

⑻ 同一律 P∨F?P P∧T?P ⑼ 零律 P∨T?T P∧F?F ⑽ 互补律 P∨?P?T P∧?P?F ⑾ P?Q ??P∨Q ⑿ P?Q ??Q??P ⒀ P?Q ?(P?Q)∧(Q?P)

⒁ P?Q ?(?P∨Q)∧(P∨?Q) ⒂ P?Q ?(P∧Q)∨(?P∧?Q )

3