[블로그 이사 예정] 철학, 끄적끄적

기호논리학 XV: 명제논리 8 [형식적 도출] 본문

교과서·강의 노트/기호논리학

기호논리학 XV: 명제논리 8 [형식적 도출]

형이상학적 찐따 2015.03.17 08:38

이 글은 연세대학교 철학과의 선우환 교수님께서 강의하신 논리학 수업 필기를 바탕으로 쓴 것입니다. 작성자 본인의 이해에 따라 소폭 수정하거나 추가한 부분이 있습니다. 실제 강의 내용과 다를 수 있습니다.


어떤 논증이 타당한지를 확인하려면 전제들을 원소로 삼는 문장 집합 Γ로부터 결론이 귀결되는지를 확인하면 된다. 딱히 어려운 작업은 아니지만 번거롭기 짝이 없다. 해석을 하기 위해 진리표를 그려본 사람이라면 알 것이다. 원자 문장이 한두 개일 때는 좀 낫다. 금방 해석 작업을 끝낼 수 있으니까 말이다. 하지만 원자 문장의 갯수가 늘어나면 해석 작업은 기하급수적으로 길어진다. (원자 문장의 갯수가 n일 때 진리표의 행의 갯수는 이 된다.) 잘못했다가는

[이미지 출처]

이런 꼴 난다. 이 지점에서 형식적 도출formal derivation이 도움을 줄 수 있다. 일련의 규칙에 따라서 주어진 문장으로부터 다른 문장을 이끌어내는 작업이다. 형식적 도출이 해석과 다른 점은 뭘까? 단순히 진리표를 그리지 않아도 된다는 걸까? 그렇지 않다. 더 중요한 차이는 해석이 의미론적semantic 작업인 반면에 도출은 통사론적syntatic 작업이라는 것이다. 해석을 하려면 문장의 의미(=진리값)을 할당해야 한다. 논증을 이루는 표현들에 의미론적 값을 할당하지 않으면 불가능한 것. 하지만 도출은 표현들의 의미를 몰라도 할 수 있다. 그냥 규칙만 따라가면 되니까.


I 형식적 도출

p&q

(p∨r)s

∴ p&s

이 논증은 타당한가? 진리표를 그려서 알아봐도 된다. 그런데 행을 16개나 그려야 된다. 귀찮다. 게다가 진리표가 커질수록 실수를 할 확률도 높아질 것 같다. 형식적 도출을 배운 사람이라면 얘기가 다르다. 배운 사람의 시범을 보도록 한다.

      (1) p&q

      (2) (p∨r)→s

  {1} (3) p [← 전제1]

  {1} (4) p∨r [← 전제3 ← 전제1]

{1,2} (5) s [← 전제2와 전제4 ← 전제1과 전제2]

{1,2} (6) p&s [← 전제3과 전제5 ← 전제1과 전제2]

소괄호 () 안에 들어있는 번호를 '행 번호'라고 부른다. 말 그대로 문장이 몇 번째 행에 있는지를 말해주는 것이다. 그냥 순서대로 쓰면 된다. 중요한 것은 중괄호 {} 안에 들어있는 '전제 번호'들이다. 해당 문장이 스스로의 참을 보증하기 위해 의존하고 있는 전제들의 행 번호를 말한다. 가령 세 번째 행의 p는 첫 번째 행의 p&q로부터 도출해낼 수 있다는 말이다. (엄밀히 말하면 첫 번째와 두 번째 행의 문장들도 전제 번호를 갖고 있다. 다만 최초에 주어진 문장들에 대해서는 편의상 전제 번호를 생략할 뿐이다. 아마도 이 문장들의 전제 번호가 자신의 행 번호와 같기 때문일 것이다. 물론 전제 번호와 행 번호가 같은 것은 이 문장들이 스스로가 참임을 내세우기 위해 자기 자신에게 의존하고 있는 탓이다.)

그런데 네 번째 행의 p∨r은 전제3으로부터 도출됨에도 불구하고 전제 번호가 3이 아니다. 전제3이 다시 전제1로부터 도출되기 때문이다. 이런 이유로 p∨r의 전제 번호는 {3}이 아니라 {1}이 된다. 3대신에 전제3의 전제 번호인 1 - 혹은 전제3이 의존하고 있는 문장의 행 번호 - 을 넣는 것이다. 다시 말해 전제 번호는 그 문장이 가장 근본적인 수준에서 의존하고 있는 문장의 행번호가 된다. (참고로 전제 번호가 없으면 그 문장은 항진 문장이다. 그 어떤 문장에 의존하지 않고도 스스로가 참임을 보증할 수 있다는 것.)

그렇다면 세 번째 행의 p가 첫 번째 행의 p&q로부터 도출될 수 있는 까닭은 무엇일까? 물론 그것은 p가 p&q의 귀결이기 때문이다. 후자가 참이면서 전자가 거짓일 수 없다는 말이다. 진리표를 통해 우리는 이 작업을 할 수 있게 되었다. 하지만 형식적 도출에서는 매번 진리표를 그리는 번거로움을 피하기 위해 몇 가지 규칙들을 사용한다. 'φ&ψ이면 필연적으로 φ가 따라 나온다' 같은 식의 규칙 말이다.


II 형식적 도출 규칙

도출된 문장의 오른쪽에는 반드시 어떤 문장으로부터 어떤 규칙을 사용해서 도출되었는지를 적어 두어야 한다.

① 전건 긍정modus ponens (MP): 조건문과 그 조건문의 전건이 참이면 후건도 반드시 참이다. 비가 오면 수업을 하지 않는다. 실제로 비가 온다! 따라서 수업은 없다! 아싸

          (1) φψ

          (2) φ

∴ {1,2} (3) ψ     1,2 MP

② 후건 부정modus tollens (MT): 조건문은 참인데 그 조건문의 후건이 거짓이면 전건도 반드시 거짓이다. 미녀는 잠이 많다. 그런데 나는 잠이 없다. 그러므로 나는 미녀가 아니다. 이젠 논리적으로도 증명이 됐다…

          (1) φψ

          (2) ~ψ

∴ {1,2} (3) ~φ     1,2 MT[각주:1]

③ 선언적 삼단논증disjunctive syllogism (DS): 선언문이 참일 때 하나의 선언지가 거짓이라면 다른 선언지는 반드시 참이다. 이쪽 아니면 저쪽이다. 그런데 이쪽은 아니다. 그러므로 저쪽이다. 농담이 아니고 선언적 삼단논증은 개도 한다. 사냥감을 쫓아가는 개를 생각해보도록…

          (1) φ∨ψ

          (2) ~φ

∴ {1,2} (3) ψ     1,2 DS

④ 단순화simplification (Simp.): 연언문이 참이라면 연언지도 모두 참이다. 철수와 영희가 도서관에 있다. 그렇다면 철수는 도서관에 있다. 물론 영희도 도서관에 있다.

        (1) φ&ψ

∴ {1} (2) φ     1 Simp.

⑤ 연언화conjunction (Conj.): 두 문장이 참이라면 그 문장을 연언문 연결사로 묶어 만든 연언문도 참이다. 철수가 도서관에 있다. 영희도 도서관에 있다. 그러므로 철수와 영희는 도서관에 있다.

          (1) φ

          (2) ψ

∴ {1,2} (3) φ&ψ     1,2 Conj.

⑥ 부가addition (Add.): 어떤 문장이 참이라면 그 문장과 임의의 문장을 선언문 연결사로 묶어 만든 선언문도 참이다. 나는 천재다. 따라서 '나는 천재이거나 내일은 비가 온다'는 문장은 참이 된다. (좀 어색하게 들릴지도 모른다. 물론 우리는 실생활에서 언어를 이런 식으로 사용하지 않는다. 다만 명제논리 체계에서 문장들의 진리값은 진리함수적으로 결정된다. 분자 문장의 진리값은 오로지 그 문장을 구성하고 있는 원자 문장들의 진리값에 의해서만 결정된다는 말이다.)

       (1) φ

∴{1} (2) φ∨ψ    1 Add.

⑦ 귀류법reductio ad absurdum (R): 어떤 문장을 참이라고 가정하고 논증을 전개하다가 그 문장과 모순되는 문장이 도출된다면 애초의 가정이 틀렸다고 볼 수 있다. ('reductio ad absurdum'은 라틴어로 '모순으로의 회귀'라는 뜻을 갖는다.)

        (1) φ

∴ {1} (2) ~φ          1 R

⑨ 동치 치환: 논리적으로 동치인 문장들의 쌍을 치환할 수 있다. 문장 전체는 물론이고 문장을 구성하는 일부분만 치환하는 것도 가능하다.

i 드모르간 법칙DeMorgan's Law (DeM)

~(p&q) ⇔ ~p∨~q

~(p∨q) ⇔ ~p&~q

ii 교환 법칙commutative law (Com.)

p&q ⇔ q&p

p∨q ⇔ q∨p

iii 결합 법칙associative law (Assoc.)

p&(q&r) ⇔ (p&q)&r

p∨(q&r) ⇔ (p∨q)∨r

iv 이중부정double negation (DN)

~~p ⇔ p

v 정의definition (D)

pq ⇔ ~p∨q

~(pq) ⇔ p&~q

p↔q ⇔ (pq)&(qp)

⑩ 전제 도입 (P)과 조건문화conditionalization (C)

임의의 문장을 임의의 행에 도입하는 것을 전제도입이라고 한다. 이 문장은 가정된 것이므로 자기 자신 외에 다른 문장에 의존하지 않는다. 따라서 이 문장의 유일한 전제번호는 자기 자신의 행번호가 된다. (I에서 살펴본 예에서 첫 번째와 두 번째 행의 문장도 사실 이런 식으로 도입된 것이라고 보면 된다.) 여기까진 쉽다.

보통 대학교 논리학 수업에서 학생들이 안드로메다로 가기 시작하는 지점이 바로 여기다. 논증에서 앞 행에 ψ가 나왔다면 φ→ψ가 어떤 행에든 나올 수 있다. 후건이 참이라면 전건의 진리값이 무엇이든 그 조건문은 참이 되기 때문이다. 그런데 새로 도입된 문장 φψ의 전제 번호는 ψ의 전제 번호들 중에서 φ의 행번호를 제외한 것이다. 예를 들어 ψ의 전제 번호가 {1,2,3}이고 φ의 행번호가 (3)일 때, φψ의 전제 번호는 {1,2}가 된다는 말이다. 곰곰히 생각해보면 그리 어렵지 않다. 과연 그럴까… ψ는 전제1과 전제2와 전제3인 φ에 의존한다. 전제1과 전제2와 전제3인 φ가 모두 참이라면 ψ도 참이라는 말이다. 그런데 φψ는 이미 φ가 참이라면 ψ도 참이라는 내용을 담고 있으므로 굳이 다시 전제3인 φ에 의존할 필요가 없게 되는 것이다.

이 두 가지 규칙을 함께 설명하는 데에는 이유가 있다. 먼저 임의의 문장 φ을 가정하고 논증을 전개하여 ψ를 얻어낸 다음에 φ→ψ를 도출한다. 이때 φ→ψ의 전제 번호에서 φ의 행 번호가 빠질 것이다. 따라서 우리는 φ→ψ를 내세우기 위해 임의로 내세운 가정에 의존하고 있지 않느냐는 비판으로부터 벗어날 수 있게 된다. φ→ψ는 임의로 도입된 φ에 논리적으로 의존하고 있지 않기 때문이다. 이런 전략을 '조건증명법'이라고 부른다.

        (1) p∨q

        (2) p~(r∨s)

   {3} (3) r                 P

    {3} (4) r∨s             3 Add.

    {3} (5) ~~(r∨s)       4DN

  {2,3} (6) ~p             2,5 MT

{1,2,3} (7) q               1,6 DS

  {1,2} (8) rq            3,7 C

대부분의 규칙들은 재빨리 이해가 될 것이다. 그렇지 않다면 진리표를 그려서 확인해보기 바란다.

사실 이들 도출 규칙 중 일부는 없어도 되는 것이다. 예를 들어 선언적 삼단 논증 규칙을 도입함으로써 도출할 수 없던 것을 도출할 수 있게 되는 것은 아니다. 선언적 삼단 논증으로 도출할 수 있는 것은 다른 규칙들을 이용해 충분히 도출할 수 있기 때문이다. 다만 조금 귀찮을 뿐이다. 이 같은 규칙들이 "우리의 연역 체계를 편리하게 만들 수 있을지는 모르겠지만 강화시키지는 않는다"는 벤슨 메이츠Benson Mates의 언급은 이런 맥락에서 이해할 수 있다.[각주:2]


III 응용

참고로 이 규칙들이 전부는 아니다. 그렇지만 이 규칙들을 활용해서 모든 가능한 규칙들을 고안해낼 수 있다. 실제로 논리학 교과서들을 보면 모두가 조금씩 다른 규칙들을 제시한다는 것을 알 수 있다. 하지만 친구 책에는 있는 규칙이 내 책에 없다고 걱정할 필요는 없다. 내 책에 있는 규칙들로 친구 책에 있는 규칙들도 얻어낼 수 있기 때문이다. 반대로 친구 책에는 없는 규칙이 내 책에 있다고 내가 더 좋은 논리 체계를 익힌 것은 아니다. 친구 역시 내 책에 있는 규칙들을 자기 책에 있는 규칙들을 통해 얻어낼 수 있으니 말이다.

다만 여러 규칙들을 알고 있으면 형식적 도출을 할 때 편리한 것은 사실이다. 시간도 절약하고 샤프심도 아낄 수 있다는 얘기다. 논리학을 계속해서 공부하다보면 계속해서 새로운 규칙들을 스스로 만들어낼 수 있을 것이다. 여기서 가장 널리 애용되는 규칙들 몇 가지만 알아보기로 한다. 그냥 알려주지는 않는다. 우리가 배운 규칙들을 활용해서 스스로 얻어낼 것이다.

① 대우transposition 법칙

pq ⇔ ~q~p

고등학교에서 그냥 외우라고 가르치는 대우 법칙을 직접 증명해본다.

      (1) pq

  {2} (2) ~q           P

{1,2} (3) ~p           1,2 MT

  {1} (4) ~q~p     2,3 C


      (1) ~q~p

  {2} (2) p         P

  {2} (3) ~~p     2 DN

{1,2} (4) ~~q     1,2 MT

{1,2} (5) q         4 DN

  {1} (6) pq

② 딜레마 논증Dilemma Argument

p∨q

pr

qs

∴ r∨s

엄마가 좋다고 말하거나 아빠가 좋다고 말해야 한다. 엄마가 좋다고 말하면 아빠가 용돈 안 준다. 아빠가 좋다고 말하면 엄마가 용돈 안 준다. 아빠 혹은 엄마가 용돈을 주지 않을 것이다. 사용 빈도가 꽤 높은 규칙이다.

           (1) p∨q

           (2) p→r

           (3) q→s

      {4} (4) ~r        P

    {2,4} (5) ~p       2,4 MT

  {1,2,4} (6) q         1,5 DS

{1,2,3,4} (7) s         3,6 MP

  {1,2,3} (8) ~r→s    4,7 C

  {1,2,3} (9) r∨s      8D 


IV 항진 문장 도출

어떤 문장이 항진 문장인지의 여부도 형식적 도출을 활용해서 파악할 수 있다. 그 문장의 전제 번호의 집합이 공집합인 경우 - 전제 번호가 없는 경우 - 그 문장은 항진 문장이다. 가령 (p→q)((qr)(pr)) 이라는 문장은 어떤가?

    {1} (1) pq                          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) pr                           3,5 C

    {1} (7) (q→r)(pr)                 2,6 C

     { } (8) (pq)((qr)(pr))     1,7 C


V 전략

"그런데 언제 어느 규칙을 써야하는 거야?" 형식적 도출에 익숙지 않은 사람은 이런 생각을 할 수 있다. 하지만 안타깝게도 이 질문에 대해서 명확한 대답을 주기는 어렵다. 그냥 연습하면서 감을 잡는 수밖에……. 그래도 어느 정도 참고할 만한 전략은 있다.

① 도출하고자 하는 결론이 조건문인 경우: 그 조건문의 전건을 새로운 전제로 도입하고 이로부터 후건을 도출해낸다. 그런 다음 조건문화를 통해 두 문장을 묶어서 조건문으로 만든다. 앞서 전제 도입과 조건문화를 설명하면서 제시했던 예를 다시 살펴보면 도움이 될 것 같다.

        (1) p∨q

        (2) p~(r∨s)

   {3} (3) r                 P

    {3} (4) r∨s             3 Add.

    {3} (5) ~~(r∨s)       4DN

  {2,3} (6) ~p             2,5 MT

{1,2,3} (7) q               1,6 DS

  {1,2} (8) rq            3,7 C

② 도출하고자 하는 결론이 하나의 원자 문장으로 이루어진 경우: 그 문장의 부정문을 새로운 전제로 도입하고 이로부터 이 부정문의 부정문, 그러니까 결론이 될 문장(의 이중부정문)을 도출해낸다. 이어서 귀류법을 통해 결론을 이끌어낸다. 예를 들어

pq

~pr

~q~r

∴ q

와 같은 논증의 타당성을 형식적 도출로 증명하기 위해 ~q를 새로운 전제로 도입하는 것이다.

          (1) p→q

          (2) ~p→r

          (3) ~q→~r

     {4} (4) ~q     P

    {3,4} (5) ~r    3,4 MP

  {2,3,4} (6) ~~p     2,5 MT

  {2,3,4} (7) p     6 DN

{1,2,3,4} (8) q     1,7 MP

  {1,2,3} (9) ~q→q     4,8 C

  {1,2,3} (10) q     9 R


  1. 후건 부정 규칙은 'φ⊃~ψ and ψ, therefore, ~φ' 등 다른 방식으로도 정형화formulate되기도 한다. 그러나 그 핵심은 다르지 않다. [본문으로]
  2. 『Elementary Logic』, 2nd ed. (New York: Oxford University Press, 1972), p. 102 [본문으로]
10 Comments
댓글쓰기 폼