Presentation is loading. Please wait.

Presentation is loading. Please wait.

第三章:命题逻辑的推理理论 主要内容 推理的形式结构 自然推理系统P 本章与其他各章的联系 本章是第五章的特殊情况和先行准备.

Similar presentations


Presentation on theme: "第三章:命题逻辑的推理理论 主要内容 推理的形式结构 自然推理系统P 本章与其他各章的联系 本章是第五章的特殊情况和先行准备."— Presentation transcript:

1 第三章:命题逻辑的推理理论 主要内容 推理的形式结构 自然推理系统P 本章与其他各章的联系 本章是第五章的特殊情况和先行准备

2 第一节:推理的形式结构

3 3.1 推理形式结构 何为推理?何为证明? 例子: (1)若AB且CD,则ACBD (2)若今天是星期一,则明天是星期二
(3)若ACBD,则AB且CD 推理 —— 从前提出发推出结论的思维过程 上例中,(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(pq) 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) 推理的形式结构: (pq)pq 用等值演算法 (pq)pq  ((pq)p)q  pqq  1 由定理3.1可知推理正确

10 推理实例 (pq)qp (2) 推理的形式结构: 用主析取范式法 (pq)qp  (pq)qp
 (pq)(pq) (pq)(pq)  m0m2m3 结果不含m1, 故01是成假赋值,所以推理不正确

11 3.1 推理形式结构 推理定律 推理定律——重言蕴涵式 重要的推理定律: A  (AB) 附加律 (AB)  A 化简律 例1:
如果谁骄傲自满,那么他就要落后;小张骄傲自满, 所以,小张必定要落后 (AB)A  B 假言推理 例2: 如果谁得了肺炎,他就一定要发烧;小李没发烧, 所以,小李没患肺炎 (AB)B  A 拒取式

12 3.1 推理形式结构 例3: 如果降落的物体不受外力的影响,那么,它不 会改变降落的方向;这个物体受到了外力的 影响,
所以,它会改变降落的方向 例4: 如果赵某是走私犯,那么,他应受法律制裁; 经查明,赵某确实受到了法律制裁, 所以,赵某是走私犯

13 3.1 推理形式结构 例5: 我要么选择汤要么选择色拉;我不选择汤。 所以,我选择色拉 (AB)B  A 析取三段论 例6:
如果我不能起床,则我不能上班。 如果我不能上班,则我不能得到报酬。 所以,如果我不能起床,则我不能得到报酬 (AB)(BC)  (AC) 假言三段论 (AB)(BC)  (AC) 等价三段论

14 3.1 推理形式结构 例7: 东方朔偷饮了汉武帝求得的据说饮了能够不死的酒,汉武帝要杀他,他说:“如果这酒真能使人不死,那么你就杀不死我;如果这酒不能使人不死(你能杀得死我),那么它就没有什么用处(不必杀我);这酒或者能使人不死,或者不能使人不死;所以你或者杀不死我,或者不必杀我。” (AB)(CD)(AC)  (BD) 构造性二难 (AB)(AB)  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. (AB)(CD)( BD)  (AC) 破坏性二难

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))(¬rp)q)  (r  s)

39 3.2 自然推理系统P 证明 ((p(q s))(¬rp)q)  (r  s) 解: r ¬rp r  p 前提引入 p
置换规则 假言推理 前提引入 假言推理 前提引入 假言推理

40 3.2 自然推理系统P 归谬法 对形如 (A1…Ak)  B的证明 转化为: A1 … Ak B为矛盾式

41 3.2 自然推理系统P 证明 ((r¬q)(r∨s)(sq)(pq))  p

42 3.2 自然推理系统P 证明 ((r¬q)(r∨s)(sq)(pq))  p 解: p p  q q s q

43 第三章 习题课 主要内容 推理的形式结构 判断推理是否正确的方法 真值表法 等值演算法 主析取范式法 推理定律 自然推理系统P
构造推理证明的方法 直接证明法 附加前提证明法 归谬法(反证法)

44 基本要求 理解并记住推理形式结构的两种形式: 1. (A1A2…Ak)B 2. 前提:A1, A2, … , Ak 结论:B
熟练掌握判断推理是否正确的不同方法(如真值表法、等值演算法、主析取范式法等) 牢记 P 系统中各条推理规则 熟练掌握构造证明的直接证明法、附加前提证明法和归谬法 会解决实际中的简单推理问题

45 练习1:判断推理是否正确 1. 判断下面推理是否正确: (1) 前提:pq, q 结论:p 解 推理的形式结构:
解 推理的形式结构: (pq)qp 方法一:等值演算法 (pq)qp  ((pq)q)p  (pq)qp  ((pq)(qq))p  pq 易知10是成假赋值,不是重言式,所以推理不正确.

46 练习1解答 方法二:主析取范式法, (pq)qp ((pq)q)p pq M2 m0m1m3

47 练习1解答 方法三 真值表法 不是重言式, 推理不正确 1 (pq)qp q p pq (pq)q
方法三 真值表法 不是重言式, 推理不正确 1 (pq)qp q p pq (pq)q 方法四 直接观察出10是成假赋值

48 练习1:判断推理是否正确 (2) 前提:qr, pr 结论:qp

49 练习1解答 (2) 前提:qr, pr 结论:qp 解 推理的形式结构: (qr)(pr)(qp) 用等值演算法
解 推理的形式结构: (qr)(pr)(qp) 用等值演算法 (qr)(pr)(qp) (( qr)(pr) ) (qp) ((qr)(pr))(qp) ((qp)(qr)(rp))(qp)  ((qp)(qr)(rp))(qp) 1 推理正确

50 练习2:构造证明 (1) 前提:pq 结论:p(pq) (2)前提:p(qr), sp, q 结论:sr
(3)前提:pq, rq, rs 结论:p

51 练习3:实际问题 3. 在系统P中构造下面推理的证明: 如果今天是周六,我们就到颐和园或圆明园玩. 如果颐和
园游人太多,就不去颐和园. 今天是周六,并且颐和园游 人太多. 所以, 我们去圆明园或动物园玩. 证明: (1) 设 p:今天是周六,q:到颐和园玩, r:到圆明园玩,s:颐和园游人太多 t:到动物园玩 (2) 前提:p(qr), sq, p, s 结论:rt

52 练习3解答 (3) 证明: ① p(qr) 前提引入 ② p 前提引入 ③ qr ①②假言推理 ④ sq 前提引入
⑧ rt ⑦附加

53 作业 14(4),(6) 15(2) 16(2) 17 18(2)


Download ppt "第三章:命题逻辑的推理理论 主要内容 推理的形式结构 自然推理系统P 本章与其他各章的联系 本章是第五章的特殊情况和先行准备."

Similar presentations


Ads by Google