大學(xué)必修課程公理法與自然演繹法課件

1、Unit 7 公理法與自然演繹法【本著作除另有注明外，采取創(chuàng)用CC姓名標(biāo)示非商業(yè)性相同方式分享臺(tái)灣3.0版授權(quán)釋出】第1頁(yè)，共41頁(yè)。Unit 7 公理法與自然演繹法截至目前為止，我們已經(jīng)學(xué)習(xí)過(guò)如何以真值樹(shù)法演算。接下來(lái)要介紹的是兩個(gè)常被提到的演算方法：公理法與自然演繹法。第2頁(yè)，共41頁(yè)。Unit 7 公理法與自然演繹法公理法的結(jié)構(gòu)：(1)公理(axioms)：在任何系統(tǒng)中皆真的句式。(2)推論規(guī)則(rule of inference)：在推論過(guò)程中能夠保存真值(truth-preserving)的規(guī)則。第3頁(yè)，共41頁(yè)。Unit 7 公理法與自然演繹法公理：(A1) ( )(A2) ( (

2、 )( ) ( )(A3) ( ) ( )推論規(guī)則：(MP) 從 和( )成立，可以推論出 成立。第4頁(yè)，共41頁(yè)。Unit 7 公理法與自然演繹法公理法的推論：所有公理的取代句式均為真。以(A1) ( )為例 P ( Q P ) (M N) ( K (M N)(S T) W) ( (B C) D) (S T) W) )第5頁(yè)，共41頁(yè)。Unit 7 公理法與自然演繹法公理法的推論：經(jīng)由公理及推論規(guī)則得到的結(jié)論均為定理(theorem)。實(shí)例：(a) P P(b) P (P Q)第6頁(yè)，共41頁(yè)。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頁(yè)，共41頁(yè)。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頁(yè)，共41頁(yè)。Unit 7 公理法與自然演繹法經(jīng)過(guò)證明得到的定理，例如 PP等，就可以在推論過(guò)程作為前提使用。實(shí)例：(c) (P(PQ)(PQ)第9頁(yè)，共41頁(yè)。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頁(yè)，共41頁(yè)。Unit 7 公理法與自然演繹法從公理法的觀點(diǎn)定義論證的有效性：某個(gè)論證是有效的，若且唯若，可以用公理及推論規(guī)則，從前提推論得到結(jié)論。(p.s. 如果前提是空集合，得到的結(jié)論就是上述所說(shuō)的定理。)第11頁(yè)，共41頁(yè)。Unit 7 公理法與自然演繹法實(shí)例：(d) P , Q(PR) QR(e) P , PQ , QR SR第12頁(yè)，共41頁(yè)。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頁(yè)，共41頁(yè)。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頁(yè)，共41頁(yè)。Unit 7 公理法與自然演繹法自然演繹法：僅由適當(dāng)?shù)耐普撘?guī)則形成的演算系統(tǒng)。兩種常見(jiàn)的自然演繹法系統(tǒng)：(1)引進(jìn)規(guī)則(Introduction Rules)與消除規(guī)則(Elimination R

7、ules)(2)等值規(guī)則(Equivalence Rules)與蘊(yùn)涵規(guī)則(Implication Rules)第15頁(yè)，共41頁(yè)。Unit 7 公理法與自然演繹法(1)引進(jìn)規(guī)則與消除規(guī)則：(i) 連言符號(hào)的規(guī)則：第16頁(yè)，共41頁(yè)。Unit 7 公理法與自然演繹法(1)引進(jìn)規(guī)則與消除規(guī)則：(ii) 條件句符號(hào)的規(guī)則：第17頁(yè)，共41頁(yè)。Unit 7 公理法與自然演繹法(1)引進(jìn)規(guī)則與消除規(guī)則：(iii) 等值符號(hào)的規(guī)則：第18頁(yè)，共41頁(yè)。Unit 7 公理法與自然演繹法(1)引進(jìn)規(guī)則與消除規(guī)則：(iv) 否定號(hào)的規(guī)則：第19頁(yè)，共41頁(yè)。Unit 7 公理法與自然演繹法(1)引進(jìn)規(guī)則與消除規(guī)

8、則：(v) 選言符號(hào)的規(guī)則：第20頁(yè)，共41頁(yè)。Unit 7 公理法與自然演繹法實(shí)例練習(xí)：(f) (QR)(PQ)(PR)(g) P(QR) (PQ)R(h) AB, BC AC(i) MN NM(j) PP第21頁(yè)，共41頁(yè)。Unit 7 公理法與自然演繹法(f) (QR)(PQ)(PR)第22頁(yè)，共41頁(yè)。Unit 7 公理法與自然演繹法(g) P(QR) (PQ)R第23頁(yè)，共41頁(yè)。Unit 7 公理法與自然演繹法(h) AB, BC AC第24頁(yè)，共41頁(yè)。Unit 7 公理法與自然演繹法(i) MN NM第25頁(yè)，共41頁(yè)。Unit 7 公理法與自然演繹法(j) PP第26頁(yè)，共4

9、1頁(yè)。Unit 7 公理法與自然演繹法(2) 等值規(guī)則與蘊(yùn)涵規(guī)則(i) 等值規(guī)則笛摩根定律 (DeM): (p q) (p q) (p q) (p q) 交換律 (Comm): (p q) (q p) (p q) (q p)結(jié)合律 (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頁(yè)，共41頁(yè)。Unit 7 公理法與自然演繹法(2) 等值規(guī)則與蘊(yùn)涵規(guī)則(i) 等值規(guī)則 異質(zhì)位換律 (Contra): (p q) (q

10、 p) 蘊(yùn)涵律 (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頁(yè)，共41頁(yè)。Unit 7 公理法與自然演繹法(2) 等值規(guī)則與蘊(yùn)涵規(guī)則(ii) 蘊(yùn)涵規(guī)則 肯定前項(xiàng)律 (MP): p q , p q 否定后項(xiàng)律 (MT): p q , q p 假言三段論 (HS): p q , q r p r 選言三段論 (DS): p q , p q p q , q p第29頁(yè)，共41頁(yè)。Unit 7 公理法與

11、自然演繹法(2) 等值規(guī)則與蘊(yùn)涵規(guī)則(ii) 蘊(yùn)涵規(guī)則 簡(jiǎn)化律 (Simp): p q p p q q 添加律 (Add): p p q 連言律 (Conj): p , q p q建構(gòu)兩難律 (CD): (p q) (r s) , p r q s p q , r s , p r q s第30頁(yè)，共41頁(yè)。Unit 7 公理法與自然演繹法實(shí)例練習(xí)：(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頁(yè)，共41

12、頁(yè)。Unit 7 公理法與自然演繹法(k) (AB)C , (DA)C, (AB)A (DA) 1. (AB)C 2. (DA)C 3. (AB)A 目 標(biāo) (DA) 第32頁(yè)，共41頁(yè)。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頁(yè)，共41頁(yè)。Unit 7 公理法與自然演繹法(l) (PQ)R, R(PQ), RQ RQ 1. (PQ)R 2. R(PQ) 3. RQ 目 標(biāo) R

13、Q 第34頁(yè)，共41頁(yè)。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頁(yè)，共41頁(yè)。Unit 7 公理法與自然演繹法(m) M, NM, KL, (NK)O ON 1. M 2. NM 3. KL 4. (NK)O 目 標(biāo) ON 第36頁(yè)，共41頁(yè)。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頁(yè)，共41頁(yè)。Unit 7 公理法與自然演繹法(n) (GH)F, H FG 1. (GH)F 2. H 目 標(biāo) FG 第38頁(yè)，共41頁(yè)。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頁(yè)，共4