[계산논리] 명제논리의 증명 2. Hilbert System을 이용한 증명

증명의 의미

 

 

이전 글에서 공부한 내용을 다시 살펴보자.

 

정해진 공리들을 이용해 주어진 명제식을 참으로 만드는 과정을 증명이라고 하였다. 

그리고, 공리들을 이용해 명제식을 참으로 치환할 수 있으면, 해당 명제는 증명 가능하다고 한다.

이를 다음과 같이 표현한다.

 

$$ \vdash_{a} P$$

 

 

Hilbert system을 살펴보기 전, 이 표기를 약간 확장해보자.

 

 

 

 

증명의 확장

 

어떤 명제식 $P$와 $Q$에 대하여, $P \vdash Q$를 다음과 같이 정의하자 :

정의된 공리와 더불어 $P = T$임을 이용하여 명제식 $Q$가 참임을 증명할 수 있다

 

 

여기에서 약간 더 확장해서, 명제식들의 집합 $\Gamma = \left\{P_1, ... , P_n \right\}$에 대해 $\Gamma \vdash Q$는 다음과 같이 정의된다 : 

공리들의 집합 $A$와 집합 $\Gamma ' = \left\{P_1 = T, ... , P_n = T \right\}$ 에 대해, $A \cup \Gamma '$을 이용하여 명제식 $Q$가 참임을 증명할 수 있다

 

 

구체적인 예시를 살펴보자. 

 

$A \wedge B \vdash_{a} A \vee B$임을 보이자.

 

 

$A \vee B$
$\quad = (A \vee B) \wedge T$	axiom 11
$\quad = T \wedge (A \vee B)$	axiom 1
$\quad = (A \wedge B) \wedge (A \vee B)$	주어진 $A \wedge B = T$ 이용
$\quad = ((A \wedge B) \wedge A) \vee ((A \wedge B) \wedge B))$	axiom 3
$\quad = (A \wedge (A \wedge B) \vee ((A \wedge B) \wedge B))$	axiom 1
$\quad = ((A \wedge A) \wedge B) \vee ((A \wedge B) \wedge B))$	axiom 2
$\quad = (A \wedge B) \vee ((A \wedge B) \wedge B)$	axiom 11
$\quad = T \vee ((A \wedge B) \wedge B)$	주어진 $A \wedge B = T$ 이용
$\quad = T$	axiom 10

 

 

연습문제

 

$A \wedge B \vDash A \vee B$인지 확인해보고, 위의 결과와 비교해보자.

 

 

 

 

---

Hilbert System을 이용한 명제의 증명

 

이 사람이 David Hilbert이다

 

 

 

눈치챘을지도 모르겠지만, 우리가 이전 글에서 알아봤던 12개의 공리는 약간의 요약이 가능하다. 

 

Hilbert system은, 12개의 공리를 4개로 요약하여 정리한 것이다.

즉, 아래 4개의 명제식에서 명제 변수에 어떤 식을 대입하더라도, 12개의 공리들을 이용하여 증명할 수 있다. 

그 4개의 공리는 다음과 같다.

 

Axiom 1	$p \rightarrow p$
Axiom 2	$p \rightarrow (q \rightarrow p)$
Axiom 3	$(p \rightarrow (q \rightarrow r)) \rightarrow ((p \rightarrow q) \rightarrow (p \rightarrow r))$
Axiom 4	$(\neg p \rightarrow \neg q) \rightarrow (q \rightarrow p)$

 

$($단, axiom 1은 axiom 2, 3, 4를 이용하여 증명할 수 있다$)$

 

 

 

공리들의 특징중 하나는 $\wedge$나 $\vee$를 사용하지 않은 점이다.

하지만, $p \rightarrow q$가 $\neg p \vee q$와 동일하다는 점을 이용하여, 동일하게 사용할 수 있다. 

 

Hilbert system을 이용한 증명은 위의 공리들과 함께 "Modus Ponens $($전건 긍정$)$"을 이용하여 진행된다.

 

 

 

Modus ponens는 다음과 같다 : 

가정 1 : $p \rightarrow q$
가정 2 : $p$
결론 : $q$

 

복잡해 보이지만, 생각해보면 간단하다. 자연어를 이용하여 예시를 들어보면 다음과 같다 : 

 

가정 1 : 만약 비가 온다면, 축제가 취소된다.

가정 2 : 비가 온다.

결론 : 축제가 취소된다. 

 

 

 

 

결과적으로, 저 4가지 공리와 Modus ponens를 이용하면 12개의 공리를 이용하는 것처럼 명제식을 증명할 수 있다.

 

 

 

앞에서 말했듯, 첫 번째 공리는 뒤의 세 공리를 이용하여 증명할 수 있다.

그 증명은 다음과 같다.

 

$\vdash_{H} A \rightarrow A$임을 보이자. 

 

Step	명제식	설명
1	$(A \rightarrow ((B \rightarrow A) \rightarrow A)$	공리 2의 $p$에 $A$, $q$에 $(B \rightarrow A)$ 대입
2	$(A \rightarrow ((B \rightarrow A) \rightarrow A))$ $\quad \rightarrow ((A \rightarrow (B \rightarrow A)) \rightarrow (A \rightarrow A))$	공리 3의 $p$에 $A$, $q$에 $(B \rightarrow A)$, $r$에 $A$ 대입
3	$(A \rightarrow (B \rightarrow A)) \rightarrow (A \rightarrow A)$	Modus ponens 1, 2
4	$(A \rightarrow (B \rightarrow A))$	공리 2의 $p$에 $A$, $q$에 $B$ 대입
5	$A \rightarrow A$	Modus ponens 4, 3

 

 

Hilbert system에서의 증명은, 공리에 명제식을 대입하거나 Modus ponens를 이용하여 진행된다. 

 

Step 1에서 공리 2에 명제식 $A$와 $B \rightarrow A$를 대입하였다.

공리들은 명제 변수에 무엇을 대입하든 참이므로 step 1의 명제는 참이다. 

$($ $\vdash (A \rightarrow ((B \rightarrow A) \rightarrow A)$ $)$

 

Step 2에서는 공리 3에 명제식 $A$, $(B \rightarrow A)$, $A$를 대입하였다.

마찬가지로, step 2의 명제는 참이다.

 

 

이때, step 3에서는, step 1과 step 2의 명제식에서 전건 긍정을 이용하여, $(A \rightarrow (B \rightarrow A)) \rightarrow (A \rightarrow A)$라는 결론을 얻어낸 것이다. 

 

 

 

 

 

Hilbert System의 문제점

 

Hilbert system은 어렵고 비직관적이다.

위에서 $p \rightarrow p$라는, 보기에는 매우 간단한 식을 저렇게 복잡하게 보인것만 봐도...

 

그래서 Gentzen이라는 사람이, 인간이 생각하는 방법을 흉내낸 증명 방법을 만들어내었다.

다음 글에서는 Gentzen의 자연 연역법을 이용한 증명 방법을 소개하도록 하겠다.