[계산논리] 명제논리의 증명 1. 공리를 이용한 증명

공리 $($배우$)$

 

 

 

지금까지 우리는 어떤 명제식의 참/거짓을 판단하기 위해 진리표를 이용했다.

즉, 명제변수가 갖는 진리값에 따라 명제식이 어떤 값을 갖는지를 확인했던 것이다. 

 

그리고, 명제변수가 어떤 값을 갖든 상관없이 참이 되는 명제식을 항진명제라고 했다. 

 

 

이번 글에서는, 어떠한 명제식이 참임을 보이는 다른 방법을 알아볼 것이다. 

 

 

 

명제논리의 공리

 

공리$($axiom$)$란, 증명할 필요 없이 자명하게 참이 되는 명제를 말한다.

명제논리에서 사용되는 몇가지 공리를 소개하겠다. 

 

Axiom 1. Commutativity	Axiom 7. Contradiction
$p \wedge q = q \wedge p$ $p \vee q = q \vee p$	$p \wedge \neg p = F$
Axiom 2. Associativity	Axiom 8. Implication
$p \wedge (q \wedge r) = (p \wedge q) \wedge r$ $p \vee (q \vee r) = (p \vee q) \vee r$	$p \rightarrow q = \neg p \vee q$
Axiom 3. Distributivity	Axiom 9. Equality
$p \vee (q \wedge r) = (p \vee q) \wedge (p \vee r)$ $p \wedge (q \vee r) = (p \wedge q) \vee (p \wedge r)$	$(p \leftrightarrow q) = (p \rightarrow q) \wedge (q \rightarrow p)$
Axiom 4. De Morgan	Axiom 10. OR - Simplification
$\neg(p \wedge q) = \neg p \vee \neg q$ $\neg(p \vee q) = \neg p \wedge \neg q$	$p \vee p = p$  $p \vee T = T, p \vee F = p$ $p \vee (p \wedge q) = p$
Axiom 5. Double Negation	Axiom 11. AND - Simplification
$\neg \neg p = p$	$p \wedge p = p$ $p \wedge T = p, p \wedge F = F$ $p \wedge (p \vee q) = p$
Axiom 6. Excluded Middle	Axiom 12. Identity
$p \vee \neg p = T$	$p = p$

 

 

여기에서, $=$ 기호는 좌변과 우변의 명제식이 동일하므로 서로 치환이 가능하다는 의미이다.

또한, $T, F$는 당연히 참/거짓을 뜻하는 명제상수이다. 1/0으로 이해해도 좋다.

 

 

 

이제, 이 12가지의 공리를 이용하여 어떠한 명제식이 참인지를 증명해보자.

명제식이 참인지를 증명하기 위해서는 공리들로 명제식이 치환되어 결과적으로 $T$에 이르러야 한다.

 

예를 들어서 $P \vee T$라는 명제식은 axiom 10에 의해 $T$로 치환할 수 있으므로, 참이다. 

 

명제식의 일부분도 위의 공리를 이용하여 치환할 수 있다.

예를 들어서 $(P \rightarrow Q) \vee R$이라는 명제는 axiom 8에 의해 $(\neg P \vee Q) \vee R$로 치환된다.

 

Axiom 8에 의해 명제식에서 $P \rightarrow Q$라는 부분을 $\neg P \vee Q$로 치환한 것이다.

 

 

 

 

이 두 가지 개념을 이용하여 어떠한 명제식이 참이 되는지를 확인해볼 수 있을 것이다.  

 

명제식 $(P \vee Q) \vee \neg P$가 참임을 증명해보자.

 

$(P \vee Q) \vee \neg P$
$\quad = \neg P \vee (P \vee Q)$	by Axiom 1
$\quad = (\neg P \vee P) \vee Q$	by Axiom 2
$\quad = (P \vee \neg P) \vee Q$	by Axiom 1
$\quad = T \vee Q$	by Axiom 6
$\quad = Q \vee T$	by Axiom 1
$\quad = T$	by Axiom 10

 

 

각 줄마다 공리를 하나씩 적용하여 순차적으로 식을 정리한 것이다.

눈여겨볼 만한 점은, 공리 여러개를 한 번에 적용하지 않는다는 것이다.

 

특히 마지막 세 줄에서 그런 점을 확인할 수 있다.

 

$T \vee Q = T$와 같이 바로 정리하지 않고, 

$T \vee Q = Q \vee T = T$와 같이 axiom 10을 적용할 수 있도록, axiom 1을 먼저 적용해준 것이다. 

 

 

명제식의 증명 가능성

 

어떠한 명제식이 참이라는 것은, 명제식에 위에서 살펴본 axiom들을 적용하여 $T$로 정리가 된다는 것이다.

이것은, 어떠한 명제식이 "증명 가능하다"라고도 말한다.

이를 아래와 같이 새로운 기호를 도입하여 나타낼 수 있다.

 

$$\vdash P$$

 

 

공리를 이용한 증명을 사용한다는 사실을 명시적으로 나타내고 싶으면, $\vdash_{a} P$ 와 같이 나타낼 수도 있다. 

 

 

 

 

증명의 이해

 

몇가지 명제식의 예시를 통해 어떤 명제식이 참임을 증명해보자. 

 

$(P \rightarrow \neg P) \rightarrow \neg P$
$\quad = (\neg P \vee \neg P) \rightarrow \neg P$	by Axiom 8
$\quad = \neg P \rightarrow \neg P$	by Axiom 10
$\quad = \neg \neg P \vee \neg P$	by Axiom 8
$\quad = P \vee \neg P$	by Axiom 5
$\quad = T$	by Axiom 6

 

따라서, 우리는 $\vdash (P \rightarrow \neg P) \rightarrow \neg P$ 임을 알 수 있다. 

 

 

 

 

이번에는 조금 더 복잡한 식을 증명해보자.

 

$P \rightarrow (Q \rightarrow (P \wedge Q))$
$\quad = P \rightarrow (\neg Q \vee (P \wedge Q))$	by Axiom 8
$\quad = P \rightarrow ((\neg Q \vee P) \wedge (\neg Q \vee Q))$	by Axiom 3
$\quad = P \rightarrow ((\neg Q \vee P) \wedge (Q \vee \neg Q))$	by Axiom 1
$\quad = P \rightarrow ((\neg Q \vee P) \wedge T)$	by Axiom 6
$\quad = P \rightarrow (\neg Q \vee P)$	by Axiom 11
$\quad = \neg P \vee (\neg Q \vee P)$	by Axiom 8
$\quad = \neg P \vee (P \vee \neg Q)$	by Axiom 1
$\quad = (\neg P \vee P) \vee \neg Q$	by Axiom 2
$\quad = (P \vee \neg P) \vee \neg Q$	by Axiom 1
$\quad = T \vee \neg Q$	by Axiom 6
$\quad = \neg Q \vee T$	by Axiom 1
$\quad = T$	by Axiom 10

 

따라서, $\vdash P \rightarrow (Q \rightarrow (P \wedge Q))$ 임을 알 수 있다.