Wk07:동어반복적 문장들II.pdf

(1)

기호논리학

(2)

진리표 방법의 한계

I 앞에서 우리는 주어진 문장이 동어반복적인지를 결정하는 절차를 기술했었다. 그것은 연계된 (associated) SC 문장을 찾아내고서, 그 문장을 진리표 검사(truth-table method)에 맡기는 것이었다. I 그러나 연계된 SC 문장이 서너 개 이 상의 문장문자들을 지니고 있을 경우에 진리표 검사는 굉장히 짐스러운 일이 된다. (왜 그런가? 연계된 SC문장에 포함된 문장문자의 갯수가 n이라면 진리표의 행의 수는 몇이 되어야 하나?) I 따라서 (i) 임의의 SC 문장 ψ가 동어반복적이라는 것을 보여주는, 혹은, 결국 같은 일이지만, (ii) SC 문장 φ가 어떤 SC 문장들의 집합 Γ의 동어반복적 귀결이라는 것을 보여주는 더욱 실제적인 방식을 찾을 필요가 대두된다. (왜 (i)과 (ii)가 같은 일이라는 것일까?)

(3)

예: 진리표

예를 들어 문장 ‘ −T ’가 다음 문장집합의 동어반복적 귀결인지의 알고 싶다고 하자: P → −R (S &T ) → R −S → Q −(P → Q) 우리가 그 논변에 상응하는 조건문 (corresponding conditional) (((P → −R)&((S &T ) → R))&((−S → Q)& − (P → Q))) → −T

에 대한 진리표를 그린다면, 우리는 각 32 행을 가진 진리표를 작 성해야 한다. (이것은 어떤 근거에서 나온 숫자인가?)

(4)

추론

덜 번거로운 방법은 상대적으로 간단한 동어반복적 추론의 연쇄 혹은 사슬을 통해, 식 ‘−T ’를 다른 문장들로부터 ‘연역해내는’ 혹은 ‘도출해내는’ 것이다. 예: (1) P → −R (2) (S &T ) → R (3) −S → Q (4) − (P → Q)        전제 (5) P& − Q (4)로부터 (6) P (5)로부터 (7) −R (1)과 (6)으로부터

(5)

추론 (계속)

(앞 슬라이드에서 계속) (8) − (S&T ) (2)와 (7)로부터 (9) S → −T (8)로부터 (10) −Q (5)로부터 (11) S (3)과 (10)로부터 (12) −T (9)와 (11)로부터 각 행의 문장은 오른쪽에 언급된 행의 문장(혹은 문장들)의 동어반복적 귀결이다. 그리고 집합 Γ의 동어반복적 귀결의 동어반복적 귀결은 다시 Γ의 동어반복적 귀결이므로, 결국 ‘−T ’는 원래의 네 전제들의 동어반복적 귀결이다.

(6)

원초적 추론규칙들

SC도출(SC derivation)은 번호 붙여진 행들의 유한한 배열로서, 각 행은 SC 문장과 —‘전제번호’라고 불리는— 수들의 목록으 로 이루어져 있고 그 배열은 다음 규칙들에 따라 구성되어져 있다: P: 어떠한 SC 문장도 임의의 행에 나올 수 있다. 이때 그 행의 전제번호는 단 하나뿐인데 그것들은 바로 그 행의 번호이다. MP: φ 와 (φ → ψ)가 앞 행에 나타났으면 ψ는 그 뒤의 어떤 행에든 나올 수 있다. 그 새로운 행의 전제번호들로서 는 φ와 (φ → ψ)가 나타난 행들의 모든 전제번호들을 취한다. MT: ψ와 (−φ → −ψ)가 앞 행에 나타났으면 φ는 그 뒤의 어떤 행에든 나올 수 있다. 그 새로운 행의 전제번호들 로서는 ψ와 (−φ → −ψ)가 나타난 행들의 모든 전제번호들을 취한다.

(7)

원초적 추론규칙들(계속)

(앞 슬라이드에서 계속) C: ψ 가 앞 행에 나타났으면 (φ → ψ)는 그 뒤의 어떤 행에든 나올 수 있다. 그 새로운 행의 전제번호들로서는 ψ가 나타난 그 행의 모든 전제번호를 취하되, 만일 요구된다면 φ가 나타난 행의 행번호를 제외할 수 있다. D: ψ 가 φ 속의 문장 χ를 χ와 정의상 동치 (아래 참조) 인 문장으로 대치함으로써 φ로부터 얻어질 수 있는 경우에, φ가 앞 행에 나타났으면 ψ는 그 뒤의 어떠한 행에든 나 올 수 있다. 그 새로운 행의 전제번호로서 는 φ가 나타난 행의 모든 전제번호들을 취한다. 정의상 동치: I (φ ∨ ψ) 는 (−φ → ψ)와 정의상 동치이다. 그 역도 성립한다. I (φ&ψ)는 −(φ → −ψ)와 정의상 동치이다. 그 역도 성립한다. I (φ ↔ ψ)는 ((φ → ψ)&(ψ ← φ))와 정의상 동치이다. 그 역도 성립한다.

(8)

SC도출, SC도출가능성, SC정리

I SC 문장 φ가 마지막 행에 나타나고 그 행의 모든 전제들이 SC 문장집합 Γ에 속하는 SC 도출을 Γ로부터 φ의 SC 도출(혹은 증명)이라 부른다. I SC 문장 φ와 SC 문장집합 Γ에 대해, Γ로부터 φ의 SC 도출이 존재할 경우 오직 그 경우에만 φ는 Γ로부터 SC 도출가능 (SC derivable)하다. I SC 문장 φ가 ∧(원소가 없는 문장집합)로부터 SC도출가능할 경우 오직 그 경우에만 φ는 SC정리(SC theorem)이다.

(9)

예 하나

1. (P → Q) → ((Q → R) → (P → R)) (삼단논증의 원리) {1} (1) P → Q P {2} (2) Q → R P {3} (3) P P {1, 3} (4) Q (1) (3) MP {1, 2, 3} (5) R (2) (4) MP {1, 2} (6) P → R (3) (5) C {1} (7) (Q → R) → (P → R) (2) (6) C ∧ (8) (P → Q) → ((Q → R) → (P → R)) (1) (7) C

(10)

또 다른 예

3. P → ((P → Q) → Q) {1} (1) P P {2} (2) P → Q P {1, 2} (3) Q (1) (2) MP {1} (4) (P → Q) → Q (2) (3) C ∧ (5) P → ((P → Q) → Q) (1) (4) C

(11)

예 하나 더

6. P → P (동일률) {1} (1) P P ∧ (2) P → P (1) C 규칙 C는 6을 위한 추론에서 특이하지만 정당하게 적용되었다. 이 점을 보려면 ‘φ’와 ‘ψ’ 양쪽에 ‘P’를 대입시켜 보라: C: ψ 가 앞 행에 나타났으면 (φ → ψ)는 그 뒤의 어떤 행에든 나올 수 있다. 그 새로운 행의 전제번호들로서는 φ가 나타난 행의 행번호를 제외한 ψ가 나타난 행의 모든 전제번호를 취한다.

(12)

재활용은 좋은 것!

공집합으로부터 SC문장 φ의 도출이 존재한다면 φ의 대입예인 SC 문장 ψ에 대해 유사한 도출을 구성하는 것은 쉽다. 우리는 단지 φ 의 주어진 도출을 따라나가면서 φ를 ψ로 변형하기 위해 필요한 대입(substitution)을 수행하면 된다. 그 결과는 ψ의 도출이 될 것이다. 정리 6 (동일률)의 예를 가지고 생각해 보자. 다음 정리 6의 도출을 Q → Q의 도출로 변형한 결과이다: {1} (1) Q P ∧ (2) Q → Q (1) C 다음 예도 마찬가지이다: {1} (1) (R ↔ −S) P ∧ (2) (R ↔ −S ) → (R ↔ −S ) (1) C 일반적으로, 임의의 문장문자 ψ에 대해서, 다음 도출도식 (derivation schema)의 예화는 (ψ → ψ)의 증명이 된다: {1} (1) ψ P ∧ (2) ψ → ψ (1) C

(13)

파생규칙

이렇게 봤을 때, 전에 이미 증명한 문장과 유사한 문장이 나올 때마다 본질적으로 똑같은 도출을 삽입하는 것은 낭비적이다. 따라서 다음의 ‘단축(short-cut)’ 추론규칙을 도입하는 것이 효율적이다: TH: 전에 증명된 SC정리의 대입예인 어떠한 SC문장도 임의의 행에 나올 수 있다. 이때 그 행의 전제번호 집합은 공집합이다. 더욱 일반적으로 말하자면, φ1, φ2, ..., φn이 앞 행들에 나타나고 조건문 (φ1→ (φ2→ . . . → φn→ ψ) . . .))가 이미 증명된 SC 정리의 대입예이면 ψ는 임의의 행에 나올 수 있다. 새로운 행의 전제번호로서는 φ1, φ2, . . . , φn이 나타난 행들의 전제번호 들 모두를 취한다.

(14)

예

정리 10과 아래 있는 그 증명을 살펴보자: 10. − − P → P {1} (1) − − P {2} (2) −P {1} (3) − − − − P → − − P (1) C {1, 2} (4) − − −P (2) (3) MT {1} (5) −P → − − −P {1} (6) P (1) (5) MT ∧ (7) − − P → P

(15)

예 (계속)

다음으로 정리 11을 어떻게 증명할지 생각해 보자: 11. P → − − P 이 정리를 증명하려면 정리 10을 가지고 TH를 적용하면 된다: ∧ (1) − − −P → −P TH 10 {2} (2) P P {2} (3) − − P (1) (2) MT ∧ (4) P → − − P C 여기서 요점은 위와 같이 TH를 이용한 도출이 존재할 때마다, 원초적 추론규칙만을 이용한 도출이 존재한다는 것이다. 왜냐하면 (TH가 사용된) 첫째 행은 정리 10의 증명을 적절히 변형한 것으로 대체될 수 있기 때문이다.

(16)

예 (계속)

여기 그러한 변형과 대체를 통해 얻어진 정리 11의 증명이 있다: {1} (1) − − −P {2} (2) − − P {1} (3) − − − − −P → − − −P {1, 2} (4) − − − − P {1} (5) − − P → − − − − P {1} (6) −P ∧ (7) − − −P → −P {8} (8) P {8} (9) − − P ∧ (10) P → − − P (어떤 추론규칙이 사용되었는지는 생략하였다.) 위 증명의 첫 일곱 행은 단지 정리 10을 위한 증명에서 ‘P’에 ‘−P’을 대입한 것에 불과하다.

(17)

또 다른 예들

15. (P → Q) → (−Q → −P) {1} (1) P → Q P ∧ (2) Q → − − Q TH 11 {1} (3) P → − − Q (1) (2) TH 1 {1} (4) −Q → −P (3) TH 13 ∧ (5) (P → Q) → (−Q → −P) (1) (4) C 집에 가면 위 SC도출에서 TH가 사용된 (2), (3), (4)행들을 정리 11, 1, 13의 SC도출들을 적절히 변형하여 채워넣어보자. 또 다음 정리들의 SC도출들은 지금 칠판에 써 보자: 14. (−P → Q) → (−Q → P) 17. (P → −P) → −P 19. − (P → Q) → P 21. ((P → Q) → ((Q → P) → (P ↔ Q))) 22. (P ↔ Q) → (P → Q)

(18)

매우

중요한 정리들

30. (P ↔ Q) ↔ (Q ↔ P) 31. (P ↔ Q) ↔ (−P ↔ −Q) 32. (P ↔ Q) → ((P&R) ↔ (Q&R)) 33. (P ↔ Q) → ((R&P) ↔ (R&Q)) 34. (P ↔ Q) → ((P ∨ R) ↔ (Q ∨ R)) 35. (P ↔ Q) → ((R ∨ P) ↔ (R ∨ Q)) 36. (P ↔ Q) → ((P → R) ↔ (Q → R)) 37. (P ↔ Q) → ((R → P) ↔ (R → Q)) 38. (P ↔ Q) → ((P ↔ R) ↔ (Q ↔ R)) 39. (P ↔ Q) → ((R ↔ P) ↔ (R ↔ Q))

(19)

동치와 치환

이제 앞에서 배운 위계 (order)의 개념을 다시 떠올려 보자: (i) 원자식은 위계 1이다. (ii) 식 φ가 위계 n 이면, −φ는 위계 n + 1이다. (iii) 식 φ와 ψ의 위계 중 최대치가 n이면, (φ&ψ), (φ ∨ ψ), 그리고 (φ → ψ)는 위계 n + 1이다. 정리 31-39까지가 주어졌을 때, 우리는 ξ의 위계에 수학적 귀납법(이게 무슨 말일까?)을 적용하여 다음 사실을 증명할 수 있다: φ ↔ ψ가 SC정리라고 하자. 만일 χ가 ξ안에서 φ를 ψ를 치환하여 얻어진 식이라면, 그 경우 χ ↔ ξ도 SC정리이다.

(20)

치환규칙

앞의 사실은 다음 규칙을 정당화시켜 준다: R(치환, Replacement) ψ가 앞 행에 나타나고, φ가 ψ에 나타난 모든 θ를 (ψ 안에서)χ로 치환함으로써 얻어지고 , χ ↔ ψ 혹은 θ ↔ χ 가 앞서 증명된 SC 정리의 대입예이면, φ는 임의의 행에 나올 수 있다. 새로운 행의 전제번호로서는 ψ가 나타난 행의 전체번호를 취한다. 24. (P ∨ Q) ↔ (Q ∨ P) (선언의 교환법칙) 40. (P ∨ (Q ∨ R)) ↔ (Q ∨ (P ∨ R)) 41. (P ∨ (Q ∨ R)) ↔ ((P ∨ Q) ∨ R) (선언의 결합법칙) ∧ (1) (P ∨ (Q ∨ R)) ↔ (Q ∨ (P ∨ R)) TH 40 ∧ (2) (P ∨ (Q ∨ R)) ↔ (Q ∨ (R ∨ P)) (1) 24 R ∧ (3) (P ∨ (Q ∨ R)) ↔ (R ∨ (Q ∨ P)) (2) 40 R ∧ (4) (P ∨ (Q ∨ R)) ↔ ((Q ∨ P) ∨ R) (3) 24 R ∧ (5) (P ∨ (Q ∨ R)) ↔ ((P ∨ Q) ∨ R) (4) 24 R

(21)

중요한 규칙과 정리들

42. − (P&Q) ↔ (−P ∨ −Q) 43. − (P ∨ Q) ↔ (−P& − Q) 44. (P&Q) ↔ − (−P ∨ −Q) 45. P ∨ Q ↔ − (−P& − Q)        (드 모르강의 법칙) 46. (P&Q) ↔ (Q&P) (연언의 교환법칙) 47. (P&Q) → P 48. (P&Q) → Q (단순화)

(22)

그밖에

중요한 규칙과 정리들

–I. (P → (Q& − Q)) → −P (부정도입) –E. 10. − −P → P (부정제거) &I. P → (Q → (P&Q)) (연언도입) &E. 47. (P&Q) → P 48. (P&Q) → Q (*연언제거) vI. P → (P ∨ Q) Q → (P ∨ Q) (선언도입) vE. (P ∨ Q) → (−P → Q) (선언제거) 여기에 더해서, 기존의 추론 규칙들 가운데서 I C는 조건문을 증명 속으로 도입하는데 쓰일 수 있고 I MP와 MT는 주어진 전제들로부터 (말하자면) 조건연결사를 제거하는데 쓰일 수 있으며, I D는 쌍조건문을 조건문의 연언으로부터 혹은 그 역으로 치환하는데 쓰일 수 있다는 것을 기억하라. *앞에서는 ‘단순화’라는 이름으로 소개하였다.

(23)

건전성

I 문장 φ가 다섯 규칙 P, MP , MT , C, D에 따라 구성된 도출의 행에 나타난다면, φ는 그 행의 전제들의 동어반복적 귀결이다. 즉, φ가 Γ의 SC도출이라면, φ는 또한 Γ의 동어반복적 도출이다. 이러한 특성을 그 추론규칙들의 ‘건전성 (soundness)’이라고 부른다. I 이것을 증명하려면 주어진 SC도출 안의 행번호에 수학적 귀납법(또!)을 쓰면 된다: (1) 그러한 도출의 첫 행에 나타난 어떠한 문장도 그행의 전제의 동어반복적 귀결이라는 것과 (2) 앞의 (n − k)째 행에 나타난 어떤 문장도 (n − k)째 행의 전제들의 동어반복적 귀결일 경우, 그 뒤의 n째 행에 나타난 어떠한 문장도 n째 행의 전제들의 동어반복적 귀결이라는 것을 입증함으로써 보여줄 것이다.

(24)

건전성 (계속)

I (1)에 관하여 : φ가 첫 행에 나타난다면, φ는 규칙 P에 의해 나왔고 따라서 φ자체가 그 행의 유일한 전제이다. I (2)를 입증하기 위해 우리의 추론규칙들을 하나씩 살펴보자. (i) φ가 규칙 P 에 의해 나왔다변, 그것은 명백히 그 행의 전제의 동어반 복적 귀결이다. (ii) φ가 규칙 MP 에 의해 나왔다변, 그것의 전제들은 문장 ψ와 (ψ → φ)가 나타나는 앞 행들의 전제들 전부이다. φ 는 ψ와 (ψ → φ)의 동어반복적 귀결이다. 그리고 가정에 의해 ψ와 (ψ → φ)는 그것들이 나타난 행들의 전제 들의 동어반복적 귀결이다. 그러므로 φ도 그 전제들의 동어반복적 귀결이다. (161 쪽 9항 참조.) (iii) φ가 규칙 MT 에 의해 나온 경우에, 그 논증은 MP에 대한 경우와 완전히 유사하다.

(25)

건전성 (계속)

(iv) φ가 규칙 C에 의해 나왔다면, χ가 앞 행에 나왔던 것을 조건으로 하 여 φ = (ψ → χ)이다. 가정에 의해 , χ는 그 행의 (ψ 를 포함할 수도 있는) 전제들의 동어반복적 귀결이다. 그러므로 (ψ → χ)는 ψ 를 배제한 그 전제들의 동어반복적 귀결이다. (161쪽 9 항과 10항) (v) 마지막으로, φ가 규칙 D에 의해 나왔다면, 그것으로부터 φ가 정의상 치환(definitional substitution)에 의해 얻어질 수 있는 그러한 어떤 문장이 앞 행에 나타난다. 그런데 그러한 문장들은 항상 서로의 동어반복적 귀결이다. (이 사실을 어떻게 증명할 수 있을까? 힌트: φ의 위계에 수학적 귀납법을 사용하면 된다.)