Download presentation
Presentation is loading. Please wait.
Published byFanny Hardja Modified 6年之前
1
第三章:命题逻辑的推理理论 主要内容 推理的形式结构 自然推理系统P 本章与其他各章的联系 本章是第五章的特殊情况和先行准备
2
第一节:推理的形式结构
3
3.1 推理形式结构 何为推理?何为证明? 例子: (1)若AB且CD,则ACBD (2)若今天是星期一,则明天是星期二
(3)若ACBD,则AB且CD 推理 —— 从前提出发推出结论的思维过程 上例中,(1),(2)是正确的推理,而(3)是错误的推理 证明 —— 描述推理正确或错误的过程
4
3.1 推理形式结构 逻辑(语义)蕴涵:给定A1,…,Ak和B 讨论 对任意赋值v: 称由前提A1,…,Ak 推出结论B的推理是有效的
如果v(Ai)=T,则v(B)=T 或者存在Aj,使得v(Aj)=F 称由前提A1,…,Ak 推出结论B的推理是有效的 B为有效结论 符号:{A1,…,Ak} ⊨ B 讨论 蕴涵跟蕴涵式的关系? 注意: 推理正确不能保证结论一定正确
5
3.1 推理形式结构 例子 {p, p q} ⊨ q {p, q p} ⊨ q p q p(pq) p(q p) F T
6
3.1 推理形式结构 定理:{A1,…,Ak} ⊨ B 当且仅当
证明 必要性:任意v, 不会出现A1…Ak 为真且 B为假的情况,所以v(A1…Ak B)=T 充分性:任意v, v(A1…Ak B)=T 则或者: A1…Ak 和B同时为T 或者: A1…Ak 为假 所以{A1,…,Ak} ⊨ B
7
3.1 推理形式结构 蕴涵元符号: A1…Ak B 代表 {A1,…,Ak} ⊨ B 推理的形式结构 前提:A1,…,Ak
8
3.1 推理形式结构 判断推理是否正确方法 真值表法 等值演算法 主析取范式法
9
推理实例 例 判断下面推理是否正确 (1) 若今天是1号,则明天是5号. 今天是1号. 所以, 明天是5号.
例 判断下面推理是否正确 (1) 若今天是1号,则明天是5号. 今天是1号. 所以, 明天是5号. (2) 若今天是1号,则明天是5号. 明天是5号. 所以, 今天是1号. 解 设 p:今天是1号,q:明天是5号. (1) 推理的形式结构: (pq)pq 用等值演算法 (pq)pq ((pq)p)q pqq 1 由定理3.1可知推理正确
10
推理实例 (pq)qp (2) 推理的形式结构: 用主析取范式法 (pq)qp (pq)qp
(pq)(pq) (pq)(pq) m0m2m3 结果不含m1, 故01是成假赋值,所以推理不正确
11
3.1 推理形式结构 推理定律 推理定律——重言蕴涵式 重要的推理定律: A (AB) 附加律 (AB) A 化简律 例1:
如果谁骄傲自满,那么他就要落后;小张骄傲自满, 所以,小张必定要落后 (AB)A B 假言推理 例2: 如果谁得了肺炎,他就一定要发烧;小李没发烧, 所以,小李没患肺炎 (AB)B A 拒取式
12
3.1 推理形式结构 例3: 如果降落的物体不受外力的影响,那么,它不 会改变降落的方向;这个物体受到了外力的 影响,
所以,它会改变降落的方向 例4: 如果赵某是走私犯,那么,他应受法律制裁; 经查明,赵某确实受到了法律制裁, 所以,赵某是走私犯
13
3.1 推理形式结构 例5: 我要么选择汤要么选择色拉;我不选择汤。 所以,我选择色拉 (AB)B A 析取三段论 例6:
如果我不能起床,则我不能上班。 如果我不能上班,则我不能得到报酬。 所以,如果我不能起床,则我不能得到报酬 (AB)(BC) (AC) 假言三段论 (AB)(BC) (AC) 等价三段论
14
3.1 推理形式结构 例7: 东方朔偷饮了汉武帝求得的据说饮了能够不死的酒,汉武帝要杀他,他说:“如果这酒真能使人不死,那么你就杀不死我;如果这酒不能使人不死(你能杀得死我),那么它就没有什么用处(不必杀我);这酒或者能使人不死,或者不能使人不死;所以你或者杀不死我,或者不必杀我。” (AB)(CD)(AC) (BD) 构造性二难 (AB)(AB) B 构造性二难 (特殊形式)
15
3.1 推理形式结构 例8: If it rains, we will stay inside.
If it is sunny, we will go for a walk. Either we will not stay inside, or we will not go for a walk. Therefore, either it will not rain, or it will not be sunny. (AB)(CD)( BD) (AC) 破坏性二难
16
3.1 推理形式结构 普罗泰戈拉收了一名学生叫欧提勒士。普氏与他签订了这样一份合同:前者向后者传授辩论技巧,教他帮人打官司;后者入学时交一半学费,另一半学费则在他毕业后帮人打官司赢了之后再交。时光荏苒,欧氏从普氏那里毕业了。但他总不帮人打官司,普氏于是就总得不到那另一半学费。 普氏为了要那另一半学费,他去与欧氏打官司,并打着这样的如意算盘: 如果欧氏打赢了这场官司,按照合同的规定,他应该给我另一半学费。 如果欧氏打输了这场官司,按照法庭的裁决,他应该给我另一半学费。 欧氏或者打赢这场官司,或者打输这场官司。 总之,他应该付给我另一半学费。 但欧氏却对普氏说: 如果这场官司我打赢了,按照法庭的裁决,我不应该给您另一半学费。 如果这场官司我打输了,按照合同的规定,我不应该给您另一半学费。 我或者打赢这场官司,或者打输这场官司。 总之,我不应该付另一半学费 究竟谁的说法对呢?
17
3.1 推理形式结构 推理定律 A (A B) 附加律 (A B) A 化简律 (A B) A B 假言推理
(A B) B A 拒取式 (A B) B A 析取三段论 (A B) (B C) (A C) 假言三段论 (A B) (B C) (A C) 等价三段论 (A B) (C D) (A C) (B D) 构造性二难 (A B) ( A B) B 构造性二难(特殊形式) (A B) (C D) ( B D) ( A C) 破坏性二难
18
3.1 推理形式结构 证明:(A B) (B C) (A C)
((A B) A ) ((B C) C) (B A ) (B C) 1
19
第二节:自然推理系统P
20
3.2 自然推理系统P 自然演绎推理:从一组已知为真的事实出发,直接运用经典逻辑推理规则推出结论的过程
为什么要自然演绎(Natural Deduction)? 给出验证 的推理过程 需要引入证明的概念 一个描述推理过程的命题公式序列,其中的每个公式或者是已知前提,或者是由前面的公式应用到推理规则得到的结论 自然演绎模拟人类的推理 A1…Ak B
21
3.2 自然推理系统P 定义3.2 一个形式系统 I 由下面四个部分组成: (1) 非空的字母表,记作 A(I).
(2) A(I) 中符号构造的合式公式集,记作 E(I). (3) E(I) 中一些特殊的公式组成的公理集,记作 AX(I). (4) 推理规则集,记作 R(I). 记I=<A(I),E(I),AX(I),R(I)>, 其中<A(I),E(I)>是 I 的形式语言系统, <AX(I),R(I)> 是 I 的形式演算系统. 自然推理系统: 无公理, 即AX(I)= 公理推理系统 推出的结论是系统中的重言式, 称作定理
22
自然推理系统P 定义3.3 自然推理系统 P 定义如下: 1. 字母表
(1) 命题变项符号:p, q, r, …, pi, qi, ri, … (2) 联结词符号:, , , , (3) 括号与逗号:(, ), , 2. 合式公式(同定义1.6) 3. 推理规则 (1) 前提引入规则 (2) 结论引入规则 (3) 置换规则
23
3.2 自然推理系统P 假言推理规则 (A B) A B A B A 结论:B All men are mortal
Socrates is a man Therefore Socrates is mortal
24
3.2 自然推理系统P 附加规则 A 结论:A B A (A B)
25
3.2 自然推理系统P 化简规则 A B 结论:A 合取引入规则 A B 结论:A B (A B) A
26
3.2 自然推理系统P 证明: p, q, p q r ⊨ r
27
3.2 自然推理系统P 证明: p, q, p q r ⊨ r p q p q p q r r 推理过程可以写成证明树
28
3.2 自然推理系统P 拒取式规则 (A B) B A 假言三段式规则 A B B 结论:A B C
结论:A C (A B) B A (A B) (B C) (A C)
29
(A B) (C D) (A C) (B D)
3.2 自然推理系统P 析取三段式规则 A B B 结论: A 构造二难推理规则 A B C D A C 结论: B D (A B) B A (A B) (C D) (A C) (B D)
30
(A B) (C D) ( B D) ( A C)
3.2 自然推理系统P 破坏性二难推理规则 A B C D B D 结论:A C (A B) (C D) ( B D) ( A C)
31
3.2 自然推理系统P 形式推演(语法蕴涵):给定A1,…,Ak和B 符号:{A1,…,Ak} ⊢ B
存在公式序列C1, C2,…,Cn,对每个i(i=1,…,n), Ci是某个Aj或者 Ci是由序列中前面的公式应用推理规则得到 Cn=B 称C1,…,Cn是由A1,…,Ak推B的证明
32
3.2 自然推理系统P 例:考虑下述论证 如果这里有球赛,则通行是困难的 如果他们按时到达,则通行是不困难的 他们按时到达了
问:得到什么结论?
33
3.2 自然推理系统P 例:考虑下述论证 设 p:这里有球赛 q:通行是困难的 r:他们按时到达 p q r
如果这里有球赛,则通行是困难的 如果他们按时到达,则通行是不困难的 他们按时到达了 问:得到什么结论? 设 p:这里有球赛 q:通行是困难的 r:他们按时到达 p q r q r p
34
3.2 自然推理系统P 证明 解: 前提: p q, r q,r 结论: p r r q q p q p 前提引入
假言推理 前提引入 拒取式
35
3.2 自然推理系统P 证明 c d, c r, d s ⊢ r s 解: c d c d d s 前提引入
c s c r r c r s r s 前提引入 置换规则 前提引入 假言三段论 前提引入 置换规则 假言三段论 置换规则
36
3.2 自然推理系统P 构造证明的方法 附加前提证明法 归谬法
37
3.2 自然推理系统P 附加前提证明法 对形如 (A1…Ak) (A B)的证明 转化为: A1, …, Ak, A ⊢ B
38
3.2 自然推理系统P 证明 ((p(q s))(¬rp)q) (r s)
39
3.2 自然推理系统P 证明 ((p(q s))(¬rp)q) (r s) 解: r ¬rp r p 前提引入 p
置换规则 假言推理 前提引入 假言推理 前提引入 假言推理
40
3.2 自然推理系统P 归谬法 对形如 (A1…Ak) B的证明 转化为: A1 … Ak B为矛盾式
41
3.2 自然推理系统P 证明 ((r¬q)(r∨s)(sq)(pq)) p
42
3.2 自然推理系统P 证明 ((r¬q)(r∨s)(sq)(pq)) p 解: p p q q s q
43
第三章 习题课 主要内容 推理的形式结构 判断推理是否正确的方法 真值表法 等值演算法 主析取范式法 推理定律 自然推理系统P
构造推理证明的方法 直接证明法 附加前提证明法 归谬法(反证法)
44
基本要求 理解并记住推理形式结构的两种形式: 1. (A1A2…Ak)B 2. 前提:A1, A2, … , Ak 结论:B
熟练掌握判断推理是否正确的不同方法(如真值表法、等值演算法、主析取范式法等) 牢记 P 系统中各条推理规则 熟练掌握构造证明的直接证明法、附加前提证明法和归谬法 会解决实际中的简单推理问题
45
练习1:判断推理是否正确 1. 判断下面推理是否正确: (1) 前提:pq, q 结论:p 解 推理的形式结构:
解 推理的形式结构: (pq)qp 方法一:等值演算法 (pq)qp ((pq)q)p (pq)qp ((pq)(qq))p pq 易知10是成假赋值,不是重言式,所以推理不正确.
46
练习1解答 方法二:主析取范式法, (pq)qp ((pq)q)p pq M2 m0m1m3
47
练习1解答 方法三 真值表法 不是重言式, 推理不正确 1 (pq)qp q p pq (pq)q
方法三 真值表法 不是重言式, 推理不正确 1 (pq)qp q p pq (pq)q 方法四 直接观察出10是成假赋值
48
练习1:判断推理是否正确 (2) 前提:qr, pr 结论:qp
49
练习1解答 (2) 前提:qr, pr 结论:qp 解 推理的形式结构: (qr)(pr)(qp) 用等值演算法
解 推理的形式结构: (qr)(pr)(qp) 用等值演算法 (qr)(pr)(qp) (( qr)(pr) ) (qp) ((qr)(pr))(qp) ((qp)(qr)(rp))(qp) ((qp)(qr)(rp))(qp) 1 推理正确
50
练习2:构造证明 (1) 前提:pq 结论:p(pq) (2)前提:p(qr), sp, q 结论:sr
(3)前提:pq, rq, rs 结论:p
51
练习3:实际问题 3. 在系统P中构造下面推理的证明: 如果今天是周六,我们就到颐和园或圆明园玩. 如果颐和
园游人太多,就不去颐和园. 今天是周六,并且颐和园游 人太多. 所以, 我们去圆明园或动物园玩. 证明: (1) 设 p:今天是周六,q:到颐和园玩, r:到圆明园玩,s:颐和园游人太多 t:到动物园玩 (2) 前提:p(qr), sq, p, s 结论:rt
52
练习3解答 (3) 证明: ① p(qr) 前提引入 ② p 前提引入 ③ qr ①②假言推理 ④ sq 前提引入
⑧ rt ⑦附加
53
作业 14(4),(6) 15(2) 16(2) 17 18(2)
Similar presentations