연산자
부정 (Negation)
$\neg P$
부정은 문장의 거짓을 표현하는 기호이다. 부정은 자연어에서 흔히 사용되는 표현이지만, 자연어의 모호함으로 인해 다양한 오류를 범하기도 하는 표현이기도 하다. 그래서 부정을 다룰 때는 특히나 이후 서술할 추론 규칙이 더욱 빛을 발한다. 추론 규칙을 이용해 부정을 사용한 논리를 오류의 여지 없이 다룸으로써 더욱 정교하고 복잡한 논리 전개를 가능케 한다.
진리표 (Truth Table)
마지막 논리연산자인 조건을 살펴보기 전 진리표에 대해 알아보자. 진리표는 명제를 구성하는 각 원자명제의 가능한 참 거짓 조합을 모두 나열하여 그 논리 연산 결과를 각각 작성한 것이다.
두 명제 $P_1$, $P_2$에 대해 명제 $P_1 \land P_2$ 의 진리표는 다음과 같이 표현할 수 있다.
| $P_1$ | $P_2$ | $P_1 \land P_2$ |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
이와 같이 가능한 모든 진리값들을 나열하면 두 명제의 동일성도 증명할 수 있다. 다음 두 명제 $\neg (P_1 \land P_2)$, $\neg P_1 \lor \neg P_2$가 동일함을 진리표를 통해 다음과 같이 증명할 수 있다.
| $P_1$ | $P_2$ | $\neg (P_1 \land P_2)$ | $\neg P_1 \lor \neg P_2$ |
|---|---|---|---|
| T | T | F | F |
| T | F | T | T |
| F | T | T | T |
| F | F | T | T |
가능한 모든 진리값들에 대해 두 명제의 진리값이 동일함을 확인했으므로, 두 명제를 동치(Equivalent)라고 한다. 특히, 이와 같이 연언, 선언, 부정 세 논리연산자만으로 구성되어 있고, 모든 가능한 진리값에 대해 동일한 동치를 Tautological Equivalent 라고 한다.
조건 (Conditional)
$P_1 \rightarrow P_2$
조건은 두 문장 간의 참 거짓 관계를 서술하는 연산자이다. 조건 명제 $P_1 \rightarrow P_2$의 의미는 문장 $P_1$ 이 참이면 $P_2$ 는 참이라는 뜻이다. $P_1$ 이 거짓인 경우 $P_2$ 가 참인지 여부는 명제의 진리값과 관계가 없다. 이는 다음의 예를 통해 설명 가능하다.
한 도시의 시장이 자신이 당선되면 도시에 KTX 노선을 개통하겠다는 공약을 걸었다. 이는 다음과 같은 논리식으로 모델링이 가능하다.
당선(시장) $\rightarrow$ 개통(KTX, 도시)
만약 시장이 당선되고 KTX가 개통되었다면 시장은 참을 말한 것이다. 하지만 만약 시장이 낙선했을 때 KTX가 개통되지 않았다고 해서 시장이 거짓말을 했다고 말할 수는 없다. 현재 우리가 다루고 있는 1차 술어논리(FOL)에서 진리값은 오직 참, 거짓 뿐이다. 시장의 말은 거짓이 아니므로 참을 진리값으로 할당한다. 그리고 시장이 낙선했을 때 KTX가 개통된 것도 같은 과정으로 참을 할당해야 할 것이다. 시장이 거짓말을 하는 유일한 경우는, 시장이 당선되었을 때 KTX가 도시에 개통되지 않은 경우이다. 그러므로 조건이 거짓인 경우는 전건이 거짓이고 후건이 참인 경우 뿐이다.
주의해야할 점은 일상에서 사용하는 조건의 의미와 수리논리학에서의 조건의 의미이 다를 때가 있다는 것이다. 그 대표적인 예가 인과관계로의 혼동과 공허참이다.
인과관계로의 혼용은 자연어에서의 조건의 활용과 수리논리에서 조건의 정의가 다름에서 기인한다. 우리는 일상생활에서 '물을 먹는다 $\rightarrow$ 갈증이 해소된다.'와 같이 인과관계에 조건을 활용한다. 물론 인과관계에 조건이 성립하기도 하지만, 다음과 같이 인과관계가 아닌 경우에도 조건은 성립한다.
$A$ 가 종이책이다. $\rightarrow$ $A$ 는 종이로 이루어졌다.
다른 예는 공허참이다. 공허참은 다음의 예로 쉽게 설명 가능하다.
소크라테스가 에베레스트 산에 오른다. $\rightarrow$ 해는 서쪽에서 뜬다.
위 명제는 참이다. 왜냐면 소크라테스는 에베레스트 산에 오른 적이 없음이 분명하므로, 전건은 거짓이고 그에 따라 조건문은 항상 참이기 때문이다. 하지만 위 명제는 일상 생활 속의 언어적 직관에는 전혀 부합하지 않는다. 따라서 조건을 일상적 언어에서의 조건보다, 조건과 항상 동치인(tautological equivalent) 다음 논리식으로 생각하는 것이 유용한 경우가 있다.
$\neg P_1 \lor P_2$
이를 통해 흔히 일으키는 오류인 전건 부정의 오류가 오류임을 증명할 수 있다. 전건 부정의 오류는 다음과 같은 귀납법으로 증명할 수 있다.
먼저 다음 명제 $G$ 가 가정을 세우자.
$G : \neg (P_1 \rightarrow P_2) \equiv P_2 \rightarrow P_1$
의미)
$G$ : 조건문 $P_1 \rightarrow P_2$ 의 부정이 $P_2 \rightarrow P_1$ 이다.
$P_1 \rightarrow P_2 \equiv \neg P_1 \lor P_2$ 이므로, $\neg (P_1 \rightarrow P_2) \equiv \neg(\neg P_1 \lor P_2)$ 이다. 그리고 드 모르간의 법칙에 의하여 $\neg(\neg P_1 \lor P_2) \equiv P_1 \land \neg P_2$ 이다. 한편, 앞서 설명한 조건문의 동치에 의해 $P_2 \rightarrow P_1 \equiv \neg P_2 \lor P_1$ 이 성립한다. $P_1 \land \neg P_2$ 와 $\neg P_2 \lor P_1$ 동치가 아니므로, 모순이 발생한다. 따라서 주어진 가정 $G$ 는 거짓임을 확인할 수 있다.
한편, 이는 다음의 진리표를 이용해서도 쉽게 증명이 가능하다.
| $P_1$ | $P_2$ | $P_1 \rightarrow P_2$ | $\neg P_1 \lor P_2$ |
|---|---|---|---|
| T | T | T | T |
| T | F | F | F |
| F | T | T | T |
| F | F | T | T |
연산자 우선순위
증명 (Proof)
여러 논리 연산과 추론 규칙은 어떤 주장(Argument)를 증명하기 위한 것이다.따라서 수리논리의 꽃은 논쟁의 여지 없이 증명이라고 단언할 수 있다. 증명은 형식에 따라서 정형 증명과 비정형 증명으로 나눌 수 있다. 비정형 증명은 자연어의 형식을 가진 증명이다. 고등학교 수학 교과서와 논술 시험의 서술 구조는 일반적으로 비정형 증명에 해당한다. 이렇듯 비정형 증명은 우리가 처음 경험한 증명이지만 비정형 증명은 자연어의 형식을 가지고 있는 탓에 암시적 오류의 가능성을 온전히 배제하지 못하고, 서술 구조가 명확하게 파악하기 힘들 수 있다는 단점이 있다.
{##Fitch Format}
Fitch Format
우리는 기호논리를 다루는 만큼 자연어에 가까운 비정형 증명이 아닌 정형증명, 그 중 Fitch Format을 주로 다룰 것이다. 다음은 Fitch Format의 한 예이다. 정형 증명은 기호논리의 강점인 암시적 오류의 배제가능성을 강화해준다.
| 1 | $P\rightarrow Q$ | |||||||
| 2 | $(P\wedge S)\wedge R$ | |||||||
| 3 | $P\wedge S$ | 2 $\ \wedge Elim$ | ||||||
| 4 | $P$ | 3 $\ \wedge Elim$ | ||||||
| 5 | $Q$ | 1,4 $\ \rightarrow Elim$ |
Fitch Format의 구조는 전제(Premises)와 논증(Arguments)들로 나뉜다. 위 예에서 1, 2행은 전제, 나머지 3, 4, 5행은 논증 부분이다. Fitch Format의 한 행은 이전의 행들(전제와 이전 논증)에 있는 문장들에 대해 추론규칙을 적용한 것이다. 그리고 논증 부분 오른쪽에 적용한 추론 규칙을 기입한다. 이제 다음 포스트에서는 본격적으로 각 논리 연산자에 대한 추론 규칙을 설명하겠다.
이전 포스트