大学必修课程公理法与自然演绎法课件

1、Unit 7 公理法与自然演绎法【本着作除另有注明外，采取创用CC姓名标示非商业性相同方式分享台湾3.0版授权释出】第1页，共41页。Unit 7 公理法与自然演绎法截至目前为止，我们已经学习过如何以真值树法演算。接下来要介绍的是两个常被提到的演算方法：公理法与自然演绎法。第2页，共41页。Unit 7 公理法与自然演绎法公理法的结构：(1)公理(axioms)：在任何系统中皆真的句式。(2)推论规则(rule of inference)：在推论过程中能够保存真值(truth-preserving)的规则。第3页，共41页。Unit 7 公理法与自然演绎法公理：(A1) ( )(A2) ( (

2、 )( ) ( )(A3) ( ) ( )推论规则：(MP) 从 和( )成立，可以推论出 成立。第4页，共41页。Unit 7 公理法与自然演绎法公理法的推论：所有公理的取代句式均为真。以(A1) ( )为例 P ( Q P ) (M N) ( K (M N)(S T) W) ( (B C) D) (S T) W) )第5页，共41页。Unit 7 公理法与自然演绎法公理法的推论：经由公理及推论规则得到的结论均为定理(theorem)。实例：(a) P P(b) P (P Q)第6页，共41页。Unit 7 公理法与自然演绎法(a) P P1. (p (pp) p) ( p ( p p) (

3、 p p) (A2) ( ( ) ( ) ( )2. p (pp) p) (A1) ( )3. (p (p p) ( p p) 1,2 (MP) : p (p p) p) : (p (p p) ( p p)4. p (p p) (A1) ( )5. p p 3,4 (MP)第7页，共41页。Unit 7 公理法与自然演绎法(b) P (P Q)1. (QP)(PQ) (A3)2. (QP)(PQ)(P (QP)(PQ) (A1)3. P (QP)(PQ) 1,2 (MP)4. (P (QP)(PQ) (P (QP) (P (PQ) (A2)5. (P (QP) (P (PQ) 3,4 (MP)

4、6. P (QP) (A1)7. P (PQ) 5,6 (MP)第8页，共41页。Unit 7 公理法与自然演绎法经过证明得到的定理，例如 PP等，就可以在推论过程作为前提使用。实例：(c) (P(PQ)(PQ)第9页，共41页。Unit 7 公理法与自然演绎法(c) (P(PQ)(PQ)(1) (P(PQ) (PP) (PQ) (A2)(2) (P(PQ) (PP) (PQ) (P(PQ) (PP) (P(PQ) (PQ) (A2)(3) (P(PQ) (PP) (P(PQ) (PQ) 1,2 (MP)(4) (PP) (P(PQ) (PP) (A1)(5) (PP) (Pr)(6) (P(

5、PQ) (PP) 4,5 (MP)(7) (P(PQ) (PQ) 3,6 (MP)第10页，共41页。Unit 7 公理法与自然演绎法从公理法的观点定义论证的有效性：某个论证是有效的，若且唯若，可以用公理及推论规则，从前提推论得到结论。(p.s. 如果前提是空集合，得到的结论就是上述所说的定理。)第11页，共41页。Unit 7 公理法与自然演绎法实例：(d) P , Q(PR) QR(e) P , PQ , QR SR第12页，共41页。Unit 7 公理法与自然演绎法(d) P , Q(PR) QR1. P (Pr)2. Q(PR) (Pr)3. P(QP) (A1)4. QP 1,3 (

6、MP)5. (Q(PR) (QP) (QR) (A2)6. (QP) (QR) 2,5 (MP)7. (QR) 4,6 (MP)第13页，共41页。Unit 7 公理法与自然演绎法(e) P , PQ , QR SR1. P (Pr)2. PQ (Pr) 3. QR (Pr)4. Q 1,2 (MP)5. R 3,4 (MP)6. R(SR) (A1) 7. SR 5,6 (MP)第14页，共41页。Unit 7 公理法与自然演绎法自然演绎法：仅由适当的推论规则形成的演算系统。两种常见的自然演绎法系统：(1)引进规则(Introduction Rules)与消除规则(Elimination R

7、ules)(2)等值规则(Equivalence Rules)与蕴涵规则(Implication Rules)第15页，共41页。Unit 7 公理法与自然演绎法(1)引进规则与消除规则：(i) 连言符号的规则：第16页，共41页。Unit 7 公理法与自然演绎法(1)引进规则与消除规则：(ii) 条件句符号的规则：第17页，共41页。Unit 7 公理法与自然演绎法(1)引进规则与消除规则：(iii) 等值符号的规则：第18页，共41页。Unit 7 公理法与自然演绎法(1)引进规则与消除规则：(iv) 否定号的规则：第19页，共41页。Unit 7 公理法与自然演绎法(1)引进规则与消除规

8、则：(v) 选言符号的规则：第20页，共41页。Unit 7 公理法与自然演绎法实例练习：(f) (QR)(PQ)(PR)(g) P(QR) (PQ)R(h) AB, BC AC(i) MN NM(j) PP第21页，共41页。Unit 7 公理法与自然演绎法(f) (QR)(PQ)(PR)第22页，共41页。Unit 7 公理法与自然演绎法(g) P(QR) (PQ)R第23页，共41页。Unit 7 公理法与自然演绎法(h) AB, BC AC第24页，共41页。Unit 7 公理法与自然演绎法(i) MN NM第25页，共41页。Unit 7 公理法与自然演绎法(j) PP第26页，共4

9、1页。Unit 7 公理法与自然演绎法(2) 等值规则与蕴涵规则(i) 等值规则笛摩根定律 (DeM): (p q) (p q) (p q) (p q) 交换律 (Comm): (p q) (q p) (p q) (q p)结合律 (Assoc): (p (q r) (p q) r) (p (q r) (p q) r)分配律 (Dist): (p (q r) (p q) (p r) (p (q r) (p q) (p r)双重否定律 (DN): p p第27页，共41页。Unit 7 公理法与自然演绎法(2) 等值规则与蕴涵规则(i) 等值规则 异质位换律 (Contra): (p q) (q

10、 p) 蕴涵律 (Impl): (p q) (p q) 等值律 (Equiv): (p q) (p q) (q p) (p q) (p q) (p q) 移出律 (Exp): (p q) r) (p (q r) 重言律 (Taut): p p p p p p第28页，共41页。Unit 7 公理法与自然演绎法(2) 等值规则与蕴涵规则(ii) 蕴涵规则 肯定前项律 (MP): p q , p q 否定后项律 (MT): p q , q p 假言三段论 (HS): p q , q r p r 选言三段论 (DS): p q , p q p q , q p第29页，共41页。Unit 7 公理法与

11、自然演绎法(2) 等值规则与蕴涵规则(ii) 蕴涵规则 简化律 (Simp): p q p p q q 添加律 (Add): p p q 连言律 (Conj): p , q p q建构两难律 (CD): (p q) (r s) , p r q s p q , r s , p r q s第30页，共41页。Unit 7 公理法与自然演绎法实例练习：(k) (AB)C , (DA)C, (AB)A (DA) (l) (PQ)R, R(PQ), RQ RQ(m) M , NM , KL , (NK)O ON(n) (GH)F, H FG (o) (WS)(SW) , WS, S WS第31页，共41

12、页。Unit 7 公理法与自然演绎法(k) (AB)C , (DA)C, (AB)A (DA) 1. (AB)C 2. (DA)C 3. (AB)A 目 标 (DA) 第32页，共41页。Unit 7 公理法与自然演绎法(k) (AB)C , (DA)C, (AB)A (DA) 1. (AB)C Pr 2. (DA)C Pr 3. (AB)A Pr 4. (AB) 3, Simp 5. C 1,4, MP 6. (DA) 2, 5, MT第33页，共41页。Unit 7 公理法与自然演绎法(l) (PQ)R, R(PQ), RQ RQ 1. (PQ)R 2. R(PQ) 3. RQ 目 标 R

13、Q 第34页，共41页。Unit 7 公理法与自然演绎法(l) (PQ)R, R(PQ), RQ RQ 1. (PQ)R Pr 2. R(PQ) Pr 3. RQ Pr 4. (PQ) 1, Simp 5. R 2, 4, MT 6. Q 3, 5, MP 7. RQ 5, 6, Conj第35页，共41页。Unit 7 公理法与自然演绎法(m) M, NM, KL, (NK)O ON 1. M 2. NM 3. KL 4. (NK)O 目 标 ON 第36页，共41页。Unit 7 公理法与自然演绎法(m) M, NM, KL, (NK)O ON 1. M Pr 2. NM Pr 3. KL Pr 4. (NK)O Pr 5. N 1, 2, MT 6. K 3, Simp 7. NK 5, 6, Conj 8. O 4, 7, MP 9. ON 8, Add第37页，共41页。Unit 7 公理法与自然演绎法(n) (GH)F, H FG 1. (GH)F 2. H 目 标 FG 第38页，共41页。Unit 7 公理法与自然演绎法(n) (GH)F, H FG 1. (GH)F Pr 2. H Pr 3. H 2, DN 4. HG 3, Add 5. GH 4, Comm 6. (GH) 5, DeM 7. F 1, 6, DS 8. FG 7, Add第39页，共4