当前位置:首页 >> 理学 >>

离散数学习题课


3.

命题逻辑-习题课 离散数学 Discrete Mathematics
主讲:李 春光 模式识别与智能系统实验室 lichunguang@bupt.edu.cn

离散数学- Discrete Mathematics 模式识别实验室 www.pris.edu.cn

1

3.
命题与联结词

第一章 简要回顾
主要内容: – 简单命题、复合命题、5种基本联结词及复合命题的符号化 基本要求: – 分清简单命题与复合命题,掌握联结词的定义,能够准确 地把基本复合命题和复合命题符号化,并能够迅速求出复 合命题的真值

命题公式及其赋值
主要内容: – 命题公式的定义、命题公式的层次、命题公式的赋值、真 值表以及公式的类型 基本要求:深刻理解命题公式的赋值,掌握命题公式的类型(重言式 、矛盾式、可满足式),能够熟练写出给定命题公式的真值表,从而 准确判断公式的类型 离散数学- Discrete Mathematics 模式识别实验室 www.pris.edu.cn
2

3.
等值式

第二章 简要回顾
主要内容:等值式的概念,16组(24个)基本等值式,等值演算,置 换规则 重点:16组基本等值式,借助基本等值式和置换规则进行等值演算 进而判断公式的类型

析取范式与合取范式
主要内容:基本概念(文字,极小项、极大项、析取范式、合取范式 、主析取范式、主合取范式)、主析取范式和主合取范式存在和唯 一性定理 重点:求取主析取范式和主合取范式,以及借此确定公式的成真赋 值或成假赋值、判断公式的类型、判断公式是否等值 难点:求取主析取范式和主合取范式

真值函数与联结词完备集
主要内容:真值函数的定义、联结词完备集 离散数学- Discrete Mathematics 模式识别实验室 www.pris.edu.cn
3

3.

第三章 简要回顾
主要内容:判断推理是否正确的方法、推理定律 重点:理解推理的形式结构,掌握判断推理正确的方法 难点:

推理的形式结构

自然推理系统P
主要内容:自然推理系统P中的证明 重点:牢记各条推理规则的内容和名称,熟练地掌握在 自然推理系统中构造证明的方法(直接法、附加前提法、 归谬法) 难点:将日常生活中某些推理形式化,并判断正确性以 及在自然推理系统P中证明
离散数学- Discrete Mathematics 模式识别实验室 www.pris.edu.cn
4

3. 联结词

联结词
自然语言里的联结词具有二义性
张三与李四都是大二的 张三与李四是同学

联结词可将命题联结起来构成复杂的命题, 相 当于初等数学里的实数集上定义的+、-、×、 ÷等运算符

5个常用的逻辑联结词:
“非”,“并且”,“或”,“如果,那么”,“当且仅 当” ┐ 、∧、∨、→、 ?
离散数学- Discrete Mathematics 模式识别实验室 www.pris.edu.cn
5

3. 双重否定 等幂律 结合律

16组等值式模式
┐ ┐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
6

交换律

离散数学- Discrete Mathematics 模式识别实验室 www.pris.edu.cn

3.

16组等值式模式

分配律 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
离散数学- Discrete Mathematics 模式识别实验室 www.pris.edu.cn
7

3. 同一律

16组等值式模式
P∨0?P P ∧1 ?P

零律 P∨1?1 P ∧0 ?0 排中律 P ∨ ┐P ? 1 矛盾律 P ∧ ┐P ? 0 蕴含等值式 P→Q?┐P∨Q 等价等值式 P?Q ?(P→Q)∧(Q→P)
离散数学- Discrete Mathematics 模式识别实验室 www.pris.edu.cn
8

3. 假言易位

16组等值式模式

P→Q ? ┐Q→ ┐P 等价否定等值式 P?Q ? ┐P ? ┐Q 归谬论 (P→Q ) ∧ (P→ ┐Q ) ? ┐P

离散数学- Discrete Mathematics 模式识别实验室 www.pris.edu.cn

9

3. 重要的推理定律
A?A∨B (A∧B) ?A ((A→B )∧A) ?B

推理定律
(附加式) (化简式) (假言推理) (拒取式) (析取三段论) (假言三段论) (等价三段论)

((A→B )∧ ┐B) ? ┐A ((A ∨ B) ∧┐A) ? B ((A→B) ∧( B→C)) ? (A→C) ((A?B) ∧( B?C)) ? (A?C)

((A→B) ∧( C→D) ∧(A ∨C)) ? (B ∨D) (构造性二难推论) ((A→B) ∧( C→D) ∧(┐B ∨ ┐D)) ? (┐A ∨┐C) (破坏性二难推论)

离散数学- Discrete Mathematics 模式识别实验室 www.pris.edu.cn

10

3.

自然推理系统
1、字母表:
命题变项符号:p, q, r,… 联结词符号: ┐,∧,∨ ,→ ,? 括号与逗号: (,) , ,

自然推理系统P:

2、合式公式 3、推理规则
– 前提引入规则:在证明的任何步骤上都可以引入前提 – 结论引入规则:在证明任何步骤上得到的结论都可以作为 后续证明的前提 – 置换规则:在证明的任何步骤上,命题公式的子公式都可 以用与之等值的公式替换,得到公式序列中的又一个公式 11 离散数学- Discrete Mathematics 模式识别实验室 www.pris.edu.cn

3.

推理规则
推理规则还有: –假言推理规则: – 附加规则: –化简规则:

A→ B A ∴B

A ∴ A∨ B
A→ B ?B ∴?A

A∧ B ∴A

– 拒取式规则:

A→ B

B→C –假言三段论规则: ∴ A → C 12 离散数学- Discrete Mathematics 模式识别实验室 www.pris.edu.cn

3.

推理规则
A∨ B ?B ∴A
A→ B C→D A∨ C ∴B ∨ D A B ∴A∧ B

推理规则还有:
–析取三段论规则:

–构造性二难推理规则:

A→ B C→D –破坏性二难推理规则: ?B ∨ ?D ∴?A ∨ ?C
–合取引入规则:
离散数学- Discrete Mathematics 模式识别实验室 www.pris.edu.cn

13

3.

基本考察点
复合命题的符号化
利用真值表判断公式的类型

等值演算
求主析取范式和主合取范式

推理理论
推理的形式结构、正确性判断 在自然推理系统中构造证明
离散数学- Discrete Mathematics 模式识别实验室 www.pris.edu.cn
14

3.

第一章作业 6. 仔细看看例1.4

7. 可以符号化为 (┐p∧q)∨(p∧┐q) ,也可以符号化为:p∨q;但并不意味 着(┐p∧q)∨(p∧┐q)等值于p∨q
?错误情况:“通过真值表检验,两者等 值”

离散数学- Discrete Mathematics 模式识别实验室 www.pris.edu.cn

15

3.

第一章作业
p: 今天星期一,q: 明天星期二,r:明天星期三 (1) p→q; (2) q→p; (3) p ? q; (4) p→r

13. 首先符号化,然后观察其真值表

p q 0 0 0 0 1 1

r 0 1 0

p→q
1 1 1

q→p
1 1 1

p→r
1 1 0
16

离散数学- Discrete Mathematics 模式识别实验室 www.pris.edu.cn

3. 14、符号化:

第一章作业
(4) (5) “与”不是命题联结词的“析取”,是“简单 命题”[50%]:p (9) 只有天下大雨,才乘车上班 [60%]
P:天下大雨, Q:他乘车上班 Q→P,或者┐P → ┐Q

(10) 除非天下大雨,否则他不乘车上班 [60%]
P:天下大雨, Q:他乘车上班 Q→P,或者┐P → ┐Q

(11) “下雪路滑,他迟到了”
有几个原子命题?[95%] P:下雪,Q:路滑,R:他迟到了 (P∧Q) →R
离散数学- Discrete Mathematics 模式识别实验室 www.pris.edu.cn
17

3. 14. 符号化

第一章作业
(12) “2与4 都是素数,这是不对的”。[60%]
两种错误:
– (1)p: 2是素数,q:4是素数, r:这是不对的 – (2)p: 2与4 都是素数; q:这是不对的

正解:p: 2是素数,q:4是素数 ┐(p∧q)

(13)“2与4 都是素数,这是不对的”的判断是 不对的。
p: 2是素数,q:4是素数 ┐(┐(p∧q) )
离散数学- Discrete Mathematics 模式识别实验室 www.pris.edu.cn
18

3.

第一章作业
新接触的基本符号7个:
5个联结词符号: ┐,∨,∧,→, ? 1个等值符号:? 1个推理正确符号:?

符号用法的错误:

这些符号有何关系呢?

等值符号? :
A?B ,即A ? B为重言式;

推理正确符号? :
A ? B,即A→B为重言式;
离散数学- Discrete Mathematics 模式识别实验室 www.pris.edu.cn
19

3.

复合命题的符号化
1) 找出各个简单命题,并逐个符号化 2) 找出自然语言中的联结词,并准确符号 成相应基本联结词 3) 用基本联结词把简单命题逐个联结起来

复合命题的符号化基本步骤

离散数学- Discrete Mathematics 模式识别实验室 www.pris.edu.cn

20

3.

复合命题的符号化
今夜你若敢去公墓,那么我就咬掉我的鼻 子或咬掉我的耳朵 P:今夜你敢去公墓 Q:我咬掉我的鼻子 R: 我咬掉我的耳朵

例 将下列命题符号化

P →(Q∨R)
离散数学- Discrete Mathematics 模式识别实验室 www.pris.edu.cn
21

3.

复合命题的符号化
例 将下列命题符号化
王乐是计算机系的学生,生于1980年或 1981年, 是三好学生。 P:王乐是计算机系的学生 Q:王乐生于1980年 R: 王乐生于1981年 S: 王乐是三好学生

P∧(Q∨R)∧S
离散数学- Discrete Mathematics 模式识别实验室 www.pris.edu.cn
22

3.

复合命题的符号化
张三和李四是兄弟。 P:张三是兄弟 Q:李四是兄弟

例 将下列命题符号化

P∧Q

Error!

P :张三和李四是兄弟

P(原子命题)
离散数学- Discrete Mathematics 模式识别实验室 www.pris.edu.cn
23

3.

复合命题的符号化
张三或李四都能做这件事 P:张三能做这件事 Q:李四能做这件事

例 将下列命题符号化

P∨Q
P∧Q

Wrong!
24

离散数学- Discrete Mathematics 模式识别实验室 www.pris.edu.cn

3.

复合命题的符号化
如果我上街,我就去书店看看,除非我 很累。 P:我上街 Q:我去书店看看 R:我很累
表示1 表示2

例 将下列命题符号化

┐R → (P→Q) (┐R∧P) →Q
25

离散数学- Discrete Mathematics 模式识别实验室 www.pris.edu.cn

3.

蕴涵联结词
与日常语言的区别,
下列表达均用p→q符号化:
“如果p,那么q” “只要p ,就q” “p 仅当q” “只有 q,才p” “除非q,才p” “除非q ,否则非p”

p、q是无关的命题时, 逻辑上允许讨论p→q 规定p为F时,则p →q为T, 这在自然用语中是 不常使用的
离散数学- Discrete Mathematics 模式识别实验室 www.pris.edu.cn
26

3. 例:
(1) (2) (3) (4)

蕴涵联结词
只要今天不下雨,我就骑自行车上班 除非今天下雨,否则我就骑自行车上班 只有今天不下雨,我才骑自行车上班 如果今天下雨,我就不骑自行车上班

令p: 今天下雨, q: 我骑车上班 (1) ┐p→q (2) ┐p→q (3) q→┐p (4) p→┐q
离散数学- Discrete Mathematics 模式识别实验室 www.pris.edu.cn
27

3.

第二章 习题

27、
列出成真赋值,构造主析取范式

28、
根据题意,列出真值表,针对成真赋值写 出主析取范式 难点在于正确列出真值表

离散数学- Discrete Mathematics 模式识别实验室 www.pris.edu.cn

28

3.

第二章 习题
29、[用等值演算求解]
设p: 王小红为班长,q:丁金生为班长,r: 李强 为班长,s:李强为生活委员,t:王小红为生活 委员 ,u:王小红为学习委员 甲乙丙都对了一半:
甲对了一半:(┐p∧s)∨(p∧┐s) 乙对了一半:(┐q∧t)∨(q∧┐t) 丙对了一半: (┐r∧u)∨(r∧┐u)

F =((┐p∧s)∨(p∧┐s)) ∧((┐q∧t)∨(q∧ ┐t)) ∧((┐r∧u)∨(r∧┐u)) 等值演算:
离散数学- Discrete Mathematics 模式识别实验室 www.pris.edu.cn
29

3.
等值演算得到:

第二章 习题
F?(┐p∧q∧┐r∧s∧┐t∧u)∨ (┐p∧ ┐q∧┐r∧s∧t∧u) ∨ (p∧┐q∧┐r∧┐s∧t∧u) ∨ (p∧q∧┐r∧┐s∧┐t∧u) ∨(┐p∧┐q∧r∧s∧t∧┐u) ∨(┐p∧q∧r∧s∧┐t∧┐u) ∨(p∧┐q∧r∧┐s∧t∧┐u) ∨(p∧q∧r∧┐s∧┐t∧┐u) 含有8个极小项,但是能得到合理解释的只有1个极小项 注意:每人只能任一职,每职只能任一人 p: 王小红为班长,q:丁金生为班长,r: 李强为班长,s: 李强为生活委员,t:王小红为生活委员 ,u:王小红为 学习委员 所以:q、s、u为真,即丁金生为班长,李强为生活委员 ,王小红为学习委员

离散数学- Discrete Mathematics 模式识别实验室 www.pris.edu.cn

30

3.

第二章 习题
符号化
A:赵去,B:钱去,C:孙去,D:李去,E:周去 A→B, D∨E, (┐B∧C)∨(B∧┐C), C ? D, E→(A∧B)

30、[用等值演算求解]

F= (A→B)∧(D∨E) ∧((┐B∧C)∨(B∧┐C)) ∧(C ? D) ∧ (E→(A∧B)) 可以有三种方式解决这种问题:
(1) 真值表法,2^5=32种可能情况,一一检验 (2) 等值演算法,处理含有5个命题变项的公式 (3) 推理规则法 [提出假设,构造推理]
离散数学- Discrete Mathematics 模式识别实验室 www.pris.edu.cn
31

3.

第二章 习题 (2) 等值演算法
F?(┐A∧┐B ∧ C ∧ D ∧┐E) ∨ (A ∧ B ∧┐C∧┐D ∧ E)

(3) 推理规则法 [提出假设,构造推理]
前提:A→B, D∨E, (┐B∧C)∨(B∧┐C), C ? D, E→(A∧B) 结论?
离散数学- Discrete Mathematics 模式识别实验室 www.pris.edu.cn
32

3.

第三章 习题 推理的形式结构和推理正确性判断 6.
(1)(3)(6)推理正确,其余均错误

8.
写出推理的形式结构,利用推理规则,构 造有效结论

离散数学- Discrete Mathematics 模式识别实验室 www.pris.edu.cn

33

3.

解决生活中的判断问题

例:小李或小张是先进工作者; 如果小李是先进 工作者,你是会知道的; 如果小张是先进工作者 ,小赵也是; 你不知道小李是先进工作者。 问: 谁是先进工作者? 解: (1) 首先找出原子命题, 完成符号化 p: 小李是先进工作者 q: 小张是先进工作者 r: 我知道小李是先进工作者 s: 小赵是先进工作者 (2)把复合命题符号化为: (p ∨ q) ∧ → r) ∧ ∧(p ∧(q → s) ∧ ┐r (3) 用等值演算化简,求成真赋值:
离散数学- Discrete Mathematics 模式识别实验室 www.pris.edu.cn
34

3.

解决生活中的判断问题

(p∨q)∧(p→r)∧(q→s)∧┐r ? (p ∨ q) ∧ (q → s) ∧((┐ p ∨ r) ∧ ┐r) ? (p ∨ q) ∧ (┐ q ∨ s) ∧(┐ p ∧ ┐ r) ? ((p ∧ ┐ q )∨ (q ∧ ┐q) ∨ (p ∧ s) ∨ (q ∧ s)) ∧(┐ p ∧ ┐ r) ?((p ∧ ┐ q ∧ ┐ p ∧ ┐ r )∨ (p ∧ s ∧ ┐ p ∧ ┐ r ) ∨ (q ∧ s ∧ ┐ p ∧ ┐ r )) ?0 ∨ 0 ∨ (q ∧ s ∧ ┐ p ∧ ┐ r ) ? (q ∧ s ∧ ┐ p ∧ ┐ r ) ? (┐ p ∧ q ∧ ┐ r ∧ s) 0101 ?m5
解释:q与s为真,也就是说,小张和小赵是先进工作者

离散数学- Discrete Mathematics 模式识别实验室 www.pris.edu.cn

35

3.

求解实际应用问题

例9:张先生手中有代号为A、B、C、D、E的五种 股票,根据当前股市情况及张先生的经济需求,需 要将若干股票抛出,但又须满足如下要求:
(1)若A抛出,则B也抛出; (2)B和C要留一种股票且只能留一种; (3)C和D要么全抛,要么都不抛; (4)D和E两种股票中必然有一种或两种要抛出; (5)若E抛出,则A、B也抛出。

上述五种条件全部满足, 问有几种合理的方案供张先生选择
离散数学- Discrete Mathematics 模式识别实验室 www.pris.edu.cn
36

3.

求解实际应用问题
找出原子命题,进行符号化:
A:A抛出;B:B抛出;C:C抛出;D:D抛出;E:E 抛出 5个条件依次可以符号化为:(A → B),(B∧ ┐ C)∨(┐ B∧C),(C?D),(D∨ E), E→ (A∧B)

对整个复合命题的符号化:
(A → B) ∧((B∧ ┐ C)∨(┐ B∧C)) ∧ (C?D) ∧(D∨ E) ∧(E→ (A∧B))

通过等值演算,得出:
(略)
离散数学- Discrete Mathematics 模式识别实验室 www.pris.edu.cn
37

3.

综合例题
例8 如果a是奇数,则a不能被2整除; 如果a是偶数,则a 能被2整除; 因此, 如果a是偶数,则a不是奇数。
试用不同方法证明

解:符号化
P: a是奇数 Q: a是偶数 R: a能被2整除

前提: P→ ┐R,Q →R 结论: Q → ┐P 验证: (P→ ┐R)∧(Q →R)→(Q→┐P)为重言式: 1. 真值表法 2. 等值演算法 3. 主范式法 4. 证明的方法 离散数学- Discrete Mathematics 模式识别实验室 www.pris.edu.cn

38

3.

求解实际应用问题
(1) 甲或乙盗窃了录音机 (2) 若甲盗窃了录音机,则作案时间不能发生在 午夜之前 (3) 若乙的证词正确,则午夜时屋里灯光未灭 (4) 若乙的证词不正确,则作案时间发生在午夜 之前 (5) 午夜时屋里灯光灭了

例10:公安人员审盗窃案,已知事实如下:

请问:盗窃录音机的是 甲, 还是乙?
离散数学- Discrete Mathematics 模式识别实验室 www.pris.edu.cn
39

3.
符号化:

求解实际应用问题
P: 甲盗窃了录音机 Q:乙盗窃了录音机 C: 作案时间发生在午夜之前 D: 乙的证词正确 E: 午夜时屋里灯光熄灭 前提:P∨Q, P→ ┐C, D → ┐E, ┐D → C, E ① E 前提引入 ② D → ┐E 前提引入
③ ④ ⑤ ⑥ ⑦ ⑧ ⑨

┐D ┐D → C C P→ ┐C ┐P P∨Q Q

①②拒取式
前提引入

③④假言推理
前提引入

⑤⑥拒取式
前提引入

⑦⑧析取三段论
40

离散数学- Discrete Mathematics 模式识别实验室 www.pris.edu.cn

3.

求解实际应用问题

例11:甲、乙、丙、丁四人参加拳击比赛
、如果甲获胜,则乙失败;如果丙获胜,则 乙也获胜,如果甲不获胜,则丁不失败。所 以如果丙获胜,则丁不失败。 请用推理方法,证明有效结论。

离散数学- Discrete Mathematics 模式识别实验室 www.pris.edu.cn

41

3.

求解实际应用问题

符号化: A: 甲获胜,B:乙获胜,C:丙获胜,D:丁获胜 前提:A→ ┐B, C→B, ┐A→D 结论:C→D 采用附加前提证明法 ① C 附加前提引入 ② C→B 前提引入 ③ B ①②假言推理 ④ A→ ┐B 前提引入 ⑤ ┐A ③④拒取式 ⑥ ┐A→D 前提引入 ⑦ D ⑤⑥假言推理
离散数学- Discrete Mathematics 模式识别实验室 www.pris.edu.cn
42


赞助商链接
相关文章:
离散数学例题
离散数学例题 - 离散数学例题 一、证明对任意集合 A,B,C,有 a)A-B)-C=A-(B∪C); b)(A-B)-C=(A-C)-B; c)(A-B)-C=(A-C)-(B-C)。 ...
离散数学习题课7
离散数学习题课7_理学_高等教育_教育专区。第七章 图论 1、 设无向图中有 6 条边,3 度和 5 度的顶点各一个,其余的都是 2 度顶点,问该图有几 个顶点...
离散数学习题课2
离散数学习题课2_理学_高等教育_教育专区。第二章 谓词逻辑 1、 在一元谓词逻辑中,分别在(a) (b) (c)时将下面命题符号化并讨论命题的真值: 1) 凡是整数...
离散数学课后习题答案(左孝凌版)
离散数学课后习题答案(左孝凌版)_理学_高等教育_教育专区。离散数学课后习题答案 (左孝凌版) 1-1,1-2 解: a) 是命题,真值为 T。 b) 不是命题。 c) 是...
《离散数学》典型例题
离散数学》典型例题_理学_高等教育_教育专区。《离散数学》典型例题 一、选择题 1. 图 1 哈斯图所示的偏序集为格的是( )。 2. 设有无向图如图 2,则( ...
离散数学例题
离散数学习题 4页 1财富值 离散数学习题及答案 5页 1财富值 离散数学习题解答 44页 免费 离散数学习题课 29页 2财富值 离散数学习题答案 33页 2财富值喜欢...
离散数学课后习题答案_(邱学绍) (1)
离散数学最全最新答案 ... 18页 1下载券离​散​数​学​课​后​...6 习题 1.3 1.解表 2-12 p 0 0 1 1 q 0 1 0 1 ?p ?q ?p ?...
【离散数学】知识点及典型例题整理
屈婉玲《离散数学》1-3章... 14页 4下载券 武大国软离散数学_习题整... ...离散数学期末复习要点与... 6页 1下载券【​离​散​数​学​】​...
第一章离散数学习题课
第一章离散数学习题课_理学_高等教育_教育专区。经典的离散数学讲解 第一章习题课第一章学习指南 、命题的真值 、命题联结词 1)掌握和理解命题(简单命题和复合...
离散数学屈婉玲版课后习题
离散数学屈婉玲版课后习题 - 第一章部分课后习题参考答案 1 2 3 4 5 16 设 p、q 的真值为 0;r、s 的真值为 1,求下列各命题公式的真值。 (1)p∨(...
更多相关标签: