by
Jan 05. 2020
명제 논리 체계에서의 도출
명제 논리 #11
도출은 컴퓨터도 한다
도출derivation은 해석과 대조되는 개념입니다. 해석은 언어적 표현에 의미를 부여하는 일이에요. 보다 구체적으론 지시체를 할당하는 거죠. 그런 점에서 해석은 의미론적semantic 작업에 해당합니다. 어떤 표현이 무엇을 가리키는가를 묻지 않고서는 이 작업을 수행할 수 없어요.
하지만 도출 과정엔 의미가 개입하지 않습니다. 언어적 표현이 어떤 것을 지칭하는지는 따지지 않고도 충분히 가능한 구문론적syntactic 작업이기 때문이죠. 구문론에서 중요한 것은 언어를 사용하는 규칙입니다. "나은 고양이가 괴롭힌다를 싫어한다"와 같은 표현은 구문론적으로 문제가 있죠? 한국어 문법을 어느 정도 아는 사람이라면 어렵지 않게 알고 있습니다. 굳이 "고양이"의 지시체가 어떤 것인지 따지지 않아도요. 그게 호랑이과에 속하는 귀여운 액체형 동물을 가리키는 말인지, 아니면 다른 무언가를 가리키는 말인지가 전혀 중요하지 않다는 거죠.
도출은 단순히 진리표를 그리다가 이런 꼴 날까봐 무서워서 하는 게 아닙니다그래서 도출을 하려면 추론 규칙rules of inference을 익혀야 합니다. 가령 문장 φ&ψ이 주어지면 문장 φ (혹은 ψ)를 쓸 수 있다는 식이에요.
이럴 때 문장 φ (혹은 ψ)가 문장 φ&ψ로부터 도출된다 혹은 따라온다고 말합니다. 이걸 기호로 나타낼 땐 φ&ψ⊢φ (혹은 φ&ψ⊢ψ)라고 써요. 의미론에 바탕을 둔 논리적 귀결 관계를 나타낼 때 ⊨ 기호를 사용하는 것과 대조적이죠.
이 도출 작업은 지시체를 파악하지 못하더라도 충분히 할 수 있기 때문에 컴퓨터가 수행할 수 있습니다. 컴퓨터에 무언가를 입력input하면 미리 정해진 어떤 규칙에 따라 연산을 수행하고 그에 따라 나오는 출력output이 나오죠? 컴퓨터가 입력으로부터 출력을 도출하는 겁니다. 문장 φ&ψ로부터 문장 φ (혹은 ψ)를 도출할 수 있다는 규칙을 학습한 컴퓨터는 p&q를 입력받으면 q를 출력할 수 있습니다. 다만 이 컴퓨터는 φ&ψ가 무슨 의미인지 전혀 알지 못하죠. (존 썰John Searle이라는 철학자는 이런 맥락에서 컴퓨터에겐 의미론이 없고 오직 구문론만 있어서 인간과 본질적으로 다르다고 썰을 풉니다 주장합니다.)
그럼 한 번 컴퓨터의 마음으로(?) 도출해봅시다
(1) p&q
(2) (p∨r)→s
∴ p&s
이 논증은 올바를까요? 진리표를 그린 후 문장 p와 q, r, s에 각각 참과 거짓을 할당하여 파악하는 의미론적 방법도 있습니다. 하지만 지금은 구문론적 방법으로 접근해보죠.
그런데 도출을 하려면 규칙이 필요합니다. 이 규칙은 잠시 후에 알아보기로 해요.
전제 1로부터 우리는 문장 p를 도출할 수 있습니다. 비가 내리고 음악이 흐른다? 그럼 비가 내리겠죠. 그걸 논리학자들은 이렇게 표기합니다.
(1) p&q
(2) (p∨r)→s
{1} (3) p
전제 3이 된 문장 p는 전제 1로부터 도출되었습니다. 그래서 행 번호 (1) 앞에 {1}라고 써줘요. 이 문장이 전제 1에 의존하고 있음을 나타내는 거죠. 이걸 전제 번호라고 부릅니다.
그리고 전제 3으로부터 우리는 다시 문장 p∨r을 도출할 수 있습니다. 비가 내린다? 그럼 비가 내리거나 고양이는 귀엽거나 둘 중에 하나는 맞겠죠.
(1) p&q
(2) (p∨r)→s
{1} (3) p
{1} (4) p∨r
잉? 그런데 (4)는 전제 3으로부터 도출된 것이니 {3}이라고 써야 하지 않나요? 좋은 질문입니다. 전제 3은 처음부터 주어진 게 아니라 전제 1로부터 도출된 것이죠? 그래서 전제 4가 된 문장 p∨r도 궁극적으로는 전제 1에 의존하는 것으로 봅니다. 그래서 {1}이라고 써요.
그다음엔 전제 2와 전제 4로부터 문장 s를 도출할 겁니다. 비가 내리거나 고양이가 귀엽다면 기분이 좋다? 그런데 비가 내리거나 고양이가 귀엽다? 그럼 앙 기모띠 기분이 좋겠죠.
(1) p&q
(2) (p∨r)→s
{1} (3) p
{1} (4) p∨r
{1, 2} (5) s
마지막으로 전제 3과 전제 5로부터 문장 p&s를 도출합니다. 비가 내린다? 근데 기분도 좋다? 그럼 비가 내리고 기분이 좋겠네요.
(1) p&q
(2) (p∨r)→s
{1} (3) p
{1} (4) p∨r
{1, 2} (5) s
{1, 2} ∴ p&s
이 논증은 올바르군요. 결론 p&s는 궁극적으로 전제 1과 전제 2로부터 (그리고 다른 전제에는 의존하지 않고도) 도출할 수 있다는 게 밝혀졌으니까요. 그리고 이건 전제 1과 전제 2가 참인지 혹은 거짓인지를 몰라도 가능한 일이었습니다.
그럼 이 도출을 위해 적용한 규칙들을 포함한 추론 규칙들을 알아볼까요?
추론 규칙
① 전건 긍정modus ponens
조건문과 그 전건이 주어지면 후건을 도출할 수 있어요.
비가 오면 수업을 하지 않는다. 비가 온다. 따라서 수업은 없다! 아싸
(1) φ→ψ
(2) φ
{1,2} ∴ ψ 1,2 MP
② 후건 부정modus tollens
조건문과 그 후건의 부정문이 주어질 땐 전건의 부정문을 도출할 수 있습니다.
미녀는 잠꾸러기다. 난 잠이 없다. 따라서 난 미녀가 아니다.
(1) φ→ψ
(2) ~ψ
{1, 2} ∴ ~φ 1,2 MT
③ 선언적 삼단논증disjunctive syllogism
선언문과 어느 한 선언지의 부정문으로부터는 다른 선언지가 따라옵니다.
이거 아니면 저거다. 그런데 이건 아니다. 그러므로 저거다.
(1) φ∨ψ
(2) ~φ
{1,2} ∴ ψ 1,2 DS
④ 단순화simplification
연언문으로부턴 그 연언지를 도출할 수 있죠.
엄마와 아빠가 거실에 있다. 그렇다면 엄마는 거실에 있다. (물론 아빠도 거실에 있다.)
(1) φ&ψ
{1} ∴ φ 1 Simp.
⑤ 연언화conjunction
두 문장이 주어지면 이들을 연언지로 삼는 연언문을 도출할 수 있죠.
엄마가 거실에 있다. 아빠도 거실에 있다. 그러므로 엄마와 아빠가 거실에 있다.
(1) φ
(2) ψ
{1,2} ∴ φ&ψ 1,2 Conj.
⑥ 부가addition
문장이 하나 주어지면 그게 어느 문장이든 그걸 선언지로 삼는 선언문을 도출할 수 있죠. 어느 선언문이든.
오늘은 춥다. 따라서 오늘 춥거나 내일 오후 1시에 환율은 1,172.35$/￦가 될 것이다. 이런 게 된다는 거죠.
(1) φ
{1} ∴ φ∨ψ 1 Add.
⑦ 동치 치환
논리적으로 동치인 문장들을 상호 치환하는 규칙입니다.
동치 치환 규칙은 문장 전체가 아니라 문장의 일부에 대해서도 적용할 수 있습니다.
i. 드모르간 법칙DeMorgan's Law
~(p&q) ≡ ~p∨~q
~(p∨q) ≡ ~p&~q
ii. 교환 법칙Commutative Law
p&q ≡ q&p
p∨q ≡ q∨p
iii. 결합 법칙Associative Law
(p&q)&r ≡ p&(q&r)
(p∨q)∨r ≡ p∨(q∨r)
iv. 이중 부정Double Negation
~~p ≡ p
v. 정의Definition
p→q ≡ ~(p&~q)
p⇔q ≡(p→q)&(q→p)
⑧-1 전제 도입Presupposition
그냥 아무 문장이나 도출하는 겁니다. 어디로부터? 바로 그 문장 자체로부터.
그 문장을 그저 가정하는 것이죠. 다른 문장으로부터 따라 나온 문장이 아니므로 자기 자신에게 의존하는 문장입니다.
{n} (n) φ P
여기까진 쉽죠? 이제부턴 아닐 거야.
⑧-2 조건문화Conditionalization
문장 ψ로부터는 φ→ψ를 도출할 수 있습니다. 문장 ψ로부터는 부가 규칙에 따라 문장 ~φ∨ψ를 도출할 수 있고, 또 이 문장으로부터는 정의에 의거해 문장 φ→ψ를 도출할 수 있으니까요.
그 어떤 문장으로부터든 그 문장을 후건으로 삼는 조건문을 도출할 수 있다는 거죠. 자연수는 정수다. 그러므로 와인이 맛있다면 자연수는 정수다. 이렇게요.
그런데 이렇게 도출한 조건문 φ→ψ의 전제 번호는 ψ의 전제 번호에서 φ의 행 번호를 제외한 것이 됩니다. 가령 ψ의 전제 번호가 {1,2,3}이고 φ의 행 번호가 (3)일 때 조건문 φ→ψ의 전제 번호는 {1,2}가 돼요.
문장 ψ는 궁극적으로 전제 1과 전제 2, 전제 3(φ)으로부터 도출된 것입니다. 그렇겠죠? 그런데 조건문 φ→ψ는 이미 φ가 참이라면 ψ도 참이라는 의미이므로 구태여 다시 전제 3 φ에 의존할 필요가 없게 되죠. 따라서 φ→ψ는 오직 전제 1과 전제 2로부터만 따라 나온 것이라고 말할 수 있는 겁니다.
…
{n} (n) φ P
…
{1,2,n} (m) ψ
{1,2} ∴ (m+1) φ→ψ n,m C
연습 삼아 전제 도입과 조건문화를 활용해 아래 논증이 올바른지 알아봅시다.
(1) p∨q
(2) p→~(r∨s)
∴ r→q
(1) p∨q
(2) p→~(r∨s)
{3} (3) r P
{3} (4) r∨s 3 Add.
{3} (5) ~~(r∨s) 4 DN
{2,3} (6) ~p 2,5 MT
{1,2,3} (7) q 1,6 DS
{1,2} ∴ r→q 3,7 C
결론이 전제들로부터 도출되니까 올바른 논증 맞네요! 이런 과정을 증명proof이라고 해요.
이런 식으로 그냥 외기만 하던 대우 법칙transposition을 증명해볼 수도 있죠.
(1) p→q
{2} (2) ~q P
{1,2} (3) ~p 1,2 MT
{1} ∴ ~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} ∴ p→q
⑨ 귀류법Reductio ad Absurdu
어떤 문장 φ로부터 그 문장의 부정문 ~φ을 도출할 수 있다면, 그래서 이들을 각각 전건과 후건으로 삼는 조건문 φ→~φ을 도출할 수 있다면? 그럼 ~φ를 도출할 수 있습니다.
참이라고 가정하고 논증을 전개하다가 그 문장과 모순되는 문장이 도출된다면 그 가정이 틀렸다고 보는 거죠.
(1) φ→~φ
{1} ∴ ~φ 1R
귀류법으로도 연습을 한 번 해볼까요? 아래 논증이 올바르다는 걸 증명해봅시다.
(1) p→q
(2) ~p→r
(3) ~q→~r
∴ 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,2,3} ∴ q 10 DN
사실 명제논리 체계에서 도출을 하기 위해 위 규칙들이 모두 필요한 건 아닙니다. 일부는 없어도 된다는 거죠. 가령 선언적 삼단논증 규칙을 도입함으로써 도출할 수 없던 문장이 도출 가능하게 되는 건 아니에요. 선언적 삼단논증을 통해 도출할 수 있는 문장은 다른 규칙을 통해서도 도출할 수 있거든요. 증명 과정이 좀 길어질 뿐.
그래서 논리학자 벤슨 메이츠Benson Mates는 이런 규칙들이 "연역 체계를 편리하게 만드는 것이지 강력하게 만드는 건 아니"라고 말하죠.
공리와 정리
방금 그 타당성을 증명한 위 논증에서 전제 1과 전제 2, 전제 3처럼 주어진 문장은 전제 번호가 없을까요? 아닙니다. 그저 생략되었을 뿐이에요. 이 문장들도 전제 번호가 있습니다. 가령 전제 1의 전제 번호는 {1}이죠. 이 문장은 다른 문장으로부터 도출된 것이 아니라 그냥 처음부터 주어진 거니까요. 스스로에게 의존하는 문장이죠. 이런 문장을 공리axiom라 부릅니다.
한편 그 어떤 문장에도 의존하지 않는 문장이 있습니다. 공집합으로부터 도출되는 문장, 이걸 정리theorem라 불러요. 이들 문장은 전제 번호가 없습니다. 그걸 표시할 땐 { } 이렇게 써요.
가령 항진 문장 p∨~p가 정리에 해당합니다. 확인해볼까요?
{1} (1) ~~p P
{1} (2) p 1 DN
{ } (3) ~~p→p 1,2 C
{ } (4) p→p 3 DN
{ } (5) ~(p&~q) 4 D
{ } (6) ~p∨p 5 DeM
{ } ∴ p∨~p 6 Com.
