By relieving the brain of all unnecessary work, a good notation sets it free to concentrate on more advanced problems, and in effect increases the mental power of the race.
- Alfred North Whitehead
훌륭한 표기법은 불필요한 작업에 신경 쓰지 않게 함으로써 더 어려운 문제에 집중하게 해주고, 결과적으로 정신력을 강화해준다.
- 알프레드 노스 화이트헤드
1차 술어 논리(FOL: First Order Logic)
논리학은 인간의 모든 추론의 원리에 대해 탐구하고 기술하는 학문이다. 논리학을 이용하면 추론을 오류 가능성이 높은 직관에만 의존하지 않고, 명시적이고 단순한 추론규칙들의 적용을 통해서 전개해 나갈 수 있다. 또 주어진 논증과 추론을 논리학적으로 모델링하여 추론이 타당한지 객관적으로 판별하고 발견하지 못했던 오류를 발견할 수도 있다. 이렇듯 논리학은 매우 강력한 도구이다. 그래서 수학 뿐만 아니라 철학, 자연과학과 사회과학, 심지어 신학에서까지, 논리체계를 가지고 있는 학문에서 광범위하게 사용된다.
1차 술어 논리 혹은 명제 논리(Propositional Logic)는 가장 기초적인 수리 논리학 중 하나로 가능세계의 개념을 끌어들인 양상논리와 고차논리들을 이해하는 기반이 된다. 다음은 1차 술어 논리의 개념과 연산, 정형 증명(특히 Fitch Format 을 이용한)에 대해 간단하게 다룬다.
명제 (Proposition)
고전적인 수리논리학에서 명제는 참, 거짓 둘 중 하나의 진리값만을 가지는 문장을 의미한다. 여기서 문장이란 단순한 자연어 문장(예: 철수는 남자이다.)와 같은 문장 뿐만 아니라 수학적인 식(예: $1 + 1 = 2$)또한 문장이라고 한다. 한 명제의 진리값은 항상 참 혹은 거짓이다.
항진명제는 항상 참인 명제이다. 가령 배중률이라 하는 "P이거나 P가 아니다."와 같은 명제는 항진명제다. 왜냐하면 P가 참이라면 말 그대로 P가 참이므로 해당 명제는 참이되고, P가 거짓이라면 'P가 아니다.'라는 명제가 참이 되기 때문이다. 결과적으로 주어진 명제는 P의 참/거짓 여부에 관계 없이 항상 참이 된다.
원자 명제 (Atomic Sentence)
원자 명제는 명제의 최소단위이다. 1차 술어 논리에서 원자 명제는 하나의 술어 기호(Predicate Symbol)와 개별 기호(Identity Symbol)들로 구성된다. 다음 표는 자연어와 그에 대응하여 표현된 술어 논리 기호이다.
| 자연어 | 원자 명제 |
|---|---|
| "A가 B보다 키가 크다." | $Taller(A, B)$ |
| "A는 B의 왼쪽에 있다." | $Left(A, B)$ |
| "A는 정육면체이다." | $Cube(A)$ |
여기서 $Taller$, $Left$, $Cube$와 같이 술어의 역할을 하는 기호를 술어 기호, 인자로 작용하는 개별자 $A$, $B$를 개별 기호라고 한다. 술어 기호는 서술에 요구되는 개별 기호의 갯수에 따라, 그리고 기호의 위치에 따라 분류된다. 술어 기호가 하나의 인자만을 받는다면 unary 라고 하고, 두 개의 인자를 받으면 binary 라고 한다. 그리고 $n$개 ($3 \leq n$) 인자를 받는 술어 기호는 n-ary 라고 부른다.
술어 기호는 술어 기호의 위치에 따라 분류되기도 한다. 앞서 예를 든 술어기호와 같이 술어기호가 여러 인자들 앞에 위치하는 것을 전위 기호/전위 연산자(prefix)라고 하고, $A = B$와 같이 술어기호 $=$가 두 인자들 가운데 오는 것을 중위 기호/중위 연산자라고 한다. 참고로 이러한 전위 연산과 중위 연산은 프로그래밍 언어를 설계할 때도 사용되는 개념이다.
연산자 (Boolean Connectivity)
1차 술어 논리에는 다양한 연산자가 있다. 이들 모두는 개별자들, 그리고 명제들 사이의 관계를 기술하는 데에 사용된다. 연산자들을 통해 복잡하게 구성된 명제들을 정형적으로 기술할 수 있고, 이는 복잡한 명제의 분석을 가능케 한다.
등호 (Identity)
$A = B$
우리에게 가장 익숙한 기호인 등호는 두 개별자 혹은 명제들이 동일함을 의미한다. 동일함의 판별 기준은 라이프니츠의 동일자 식별 불가능성(identity of indiscernibles)이다. 동일자 실별 불가능성이란 동일함의 정의가 식별 불가능임을 말한다. 두 대상이 동일하다는 것은 두 대상 사이에 구별 가능한 속성이 존재하지 않는다는 것이다. 가령 똑같은 두 물체가 서로 다른 위치에 존재한다고 해보자. 각 물체가 가지고 있는 특징(가령 생김새, 크기 등)은 같다고 하더라도 두 물체의 '위치'라는 속성으로 인해 구별이 가능하게 된다. 그러므로 두 물체는 동일한 물체가 아님을 증명할 수 있다. 동일자 식별불가능성 원리는 대상들 사이의 '같음'을 명시적으로 정의한다. 이는 두 대상이 서로 다른 특징을 가짐을 통해 두 대상이 동일하지 않음을 보일 수 있게 하고, 두 대상이 가지는 모든 속성이 같음을 통해 두 대상이 동일함을 보일 수 있게 한다.
연언 (Conjunction)
$P_1 \land P_2$
연언(Conjunction)은 자연어에서 '그리고', 'and'의 의미를 가진다. $P_1 \land P_2$의 의미는 $P_1$, $P_2$가 동시에 참이라는 뜻이다. 혹자들은 이를 집합에 대한 연산인 교집합과 햇갈릴 것이다. 하지만 연언과 교집합($A \cap B$)은 명백히 다른 연산이다. 연언은 문장(명제 혹은 조건)에 적용되는 연산이고, 교집합은 집합에 적용되는 연산이다. 이 둘이 유사성을 보이는 이유는 이 두 연산 모두 '동시에 만족한다'라는 개념을 표현하기 위해 고안되었기 때문이다.
그렇다고 교집합과 연언이 아무런 관계를 맺지 않는 것은 아니다. 고등학교 1학년 수학 교육과정을 거친 독자들은 '명제'와 '집합'의 관계에 대해 이해하고 있을 것이다. 연언과 교집합도 이와 유사한 관계를 가진다. 비록 연언은 문장에, 교집합은 집합에 적용되는 연산이지만 이 두 연산은 모두 한 개념을 표현하기 위해 고안된 것이기 때문이다. 그렇기에 연언으로 연결된 두 명제의 진리집합은 교집합을 통해 기술될 수 있다. 다음 예를 살펴보자.
문장 $p$의 진리집합 $P$, 문장 $q$의 진리집합 $Q$에 대해, 문장 $p \land q$의 진리집합은 다음과 같다.
$P \cap Q$
이와 같이 연언과 교집합은 밀접한 관계를 맺지만 적용되는 연산이 다름을 유의해야 한다.
선언 (Disjunction)
$P_1 \lor P_2$
선언(Disjunction)은 자연어에서 '혹은', 'or'의 의미를 가진다. 연언과 의미가 다를 뿐 쓰임은 거의 동일하다고 생각하면 된다. 연언과 교집합과의 관계에서 유추할 수 있듯이 선언은 합집합과 밀접한 관계를 맺는다. 선언과 합집합은 '적어도 둘 중 하나는 만족한다'라는 개념을 표현하기 위해 고안된 연산이다. 그렇기에 선언으로 연결된 문장의 진리집합은 각 문장의 진리집합의 합집합과 같다. 다음과 같이 기술할 수 있는 것이다.
문장 $p$의 진리집합 $P$, 문장 $q$의 진리집합 $Q$에 대해, 문장 $p \lor q$의 진리집합은 다음과 같다.
$P \cup Q$
추후 포스팅에서는 남은 연산들인 부정, 조건과 이 연산들을 활용한 정형적 연역 증명에 대해 다루고, 더 나아가 현대대수와 범주론적 관점에서 논리 연산들을 조망하는 것에 대해 다룰 것이다.
출처)
- Barker-Plumer, Barwise, Etchemeny, Language, Proof and Logic 2nd Edition, CSLI Publications, Stanford Univ., 2011