[Section 1] 알고리즘과 논리학 증명 시스템

대수학 목차 보기

[INTRO] 대수학 미리보기

0. INTRO

수학의 명제적 형태와 논리관계에 따른 해석에 의해서, 수학적으로 계산(calculus)한다는 개념이 탄생했다. 즉, 계산한다는 것은 방정식(equation)의 형태와 그 변수를 만족하는 참 조건을 찾는다는 것이다. 기원전 약 800년 경 페르시아의 대수학자 알콰리즈미의 이름을 딴 알고리즘(algorithm)은 이 해를 구하기 위한 일반적인 방법론을 단계별로 제시하는 것이다.

1. 알고리즘을 위한 기호

수학적 방정식에 의해서 다양한 수학자들의 서로 다른 문제들의 해결 방법이 제시되고, 심지어 해를 구하기 위한 체계화된 단계적 방법을 제시하는 알고리즘의 형태까지 존재하게 되었다. 일반적으로 해를 구하는 방법은 계산(calculus)이라는 용어로 정의된다. 다른 말로도 알고리즘이라고 하는데, 이 알고리즘을 표시하는 기호를 먼저 알아보자.

A. 공리 기호, |

하나의 공리를 나타내는 기호는 다음과 같다.

"|"

 

공리에 의해서 귀결된 일련의 공리계를 순차적으로 다음과 같은 표현 한다.

 

"||, |||, ||||..."

 

어떤 공리에서 변수가 사용되는 경우, 그 변수와 함께 표시한다

 

"x |, y |, 등등 "

 

B. 공식(formulas), f

일반적으로 함수의 형태를 f로 나타낸다. 유한한 집합의 숫자 영역에서 십진수 형태의 숫자를 변수에 대입함으로써, 방정식을 구하는 기본 단계가 성립한다. 처음에 알고리즘은 두 개의 공식으로 나타난다. 이 알고리즘에서 나타나는 제일 처음의 공식을 공리계라고도 부르기도 한다. 이것이 바로 추론의 첫 번째 규칙이다. 일련의 규칙들을 통해서 나타나는 각각의 공식들의 일련의 단계를 유도(derivation) 과정이라고 한다. 

 

C. 유도 규칙, a/b

일반적으로 분수 꼴은 분수 막대라는 기호, /으로 표시하는데, 알고리즘상에 나타나는 기호 / 는 유도과정이 다음 단계로 넘어감을 표시한다. 예를 들어, a/b라는 기호는 알고리즘상에서 a에서부터 b로 진행되었음을 의미한다. 

 

D. 예시, X + 1 = 10

자연수 공리 체제를 따른다고 가정해보자. 그러면 상수 1은 자연수 공리계로부터 지정된 상수를 의미함으로 공리 기호로 대체할 수 있다. 따라서 첫 번째 알고리즘의 형태는 다음과 같다.

 

"X + | = X |"

 

X에 자연수 공리 체제의 숫자를 대입함으로써, 두 번째 알고리즘 형태는 다음과 같다.

 

"| + | = ||"

 

첫 번째 알고리즘인 계산과정 1은 두 번째 알고리즘 형태로 유도되었다. 이를 통해서 우리는 일반적인 해를 구할 수 있음을 알고리즘으로 제시하는 것이다. 

2. 증명(proof)이란?

A. 추론의 규칙들의 의미

알고리즘에서 제시한 일련의 유도과정은 우리가 어떤 공리계로부터 출발한 증명이 얼마나 합당한가를 단계적으로 보여준다. 이러한 알고리즘에서 추론의 규칙은 다음 공식으로의 전이 가능성을 명시적으로 보여주는 것을 의미한다.  

B. 자연 연역(natural deduction)

술어 논리의 법칙은 대부분 논리적 상수의 도입과 소거에 관련이 있고 이는 논리학 체제를 따른다. 증명 이론에서 자연 연역(natural deduction)이란 논리적 추론을 나타내는 증명의 일종이라고 하고. 이 자연 연역에서는 최대한 공리를 배제하고 오직 구문적인 추론 규칙만을 사용하여 증명이 이루어진다. 여기에는 다음의 9가지 추론 규칙이 존재한다.

 

1) 가정 규칙 (The Rule of Assumption), A

2) 전건 긍정 (Modus Ponendo Ponens), MPP

3) 이중 부정 규칙 (The Rule of Double Negation)

4) 조건 증명 규칙 (The Rule of Conditional Proof), CP

5) ^도입 규칙(The Rule of ^-introduction), ^|

6) ^제거 규칙 (The Rule of ^-elimination),  ^E

7) v도입 규칙 (The Rule of v-introduction), v|

8) v제거 규칙 (The Rule of v-elimination), vE

9) 귀류법 (Reductio Ad Absurdum) RAA

 

수학 체제에서 나타나는 공식(formula)은 논리학에서의 정형 논리식(well-formed formula, WFF)과 다르지 않으며, 증명은 다음의 조건으로 이루어진다.

 

a) 정형 논리식의 유한열로 이루어진다.

b) 각 행은 규칙에 의해서 형성된다.

c) 증명의 마지막 줄이 '결론' 부이다.

*전제는 존재하지 않을 수도 있지만, 결론부는 전제만을 사용하여 도출해야 한다. 

 

전제가 없는 증명 열의 경우를 정리(theorem)라고 한다. 따라서 정리는 공리계 내에서 공집합인 전제를 사용하여 증명 가능한 열이 된다.

 

3. 추론 법칙 9 가지에 대해서...

A. 가정 규칙 (The Rule of Assumption)

가정 규칙은 가장 기본적인 수학적 증명 규칙으로 어떠한 수학적 명제, 공식을 A라는 기호로 나타낸다. 이때 발생하는 증명 열은 i부터 k 그리고 l까지 (i <... <k <... <l)의 순서를 따라가면서 전전 긍정, 대입, 소거 등의 추론 법칙에 따라서 증명과정을 전개한다. 다른 말로 추론의 법칙이라고도 불리는 이 가정 규칙은 개개의 수학적 증명식을 의미한다. 

B. 전건 긍정(modus ponens)

함의 소거(implication elmination)로도 불리는 이 전건 긍정은 가언 명제와 그 전제로부터 결론을 유도해낸다.

대수학에서는 공식이라는 가언 명제를 통해서 결론을 이끌어내는 것을 의미한다. 그렇다면 전제는 무엇인가? 여기서 전제는 "가언 명제라면 결론이다"와 "가언 명제로부터 결론이 나왔다"가 된다. 따라서 수학적인 증명이란, 유한한 일련의 추론 규칙을 통해서 앞선 공식으로 유도가 될 수 있다는 것을 의미한다. 

 

* 가언 명제란, 어떤 조건을 가정한 명제를 뜻한다. 

C. 이중 부정 규칙 (The Rule of Double Negation)

어떤 명제 A와 --A는 같다는 것을 의미한다. 수학적 명제 또한 이 이중 부정 규칙을 따른다. 

D. 조건 증명 규칙 (The Rule of Conditional Proof)

조건 증명 규칙은 기호로 CP로 표시한다. 어떤 가정 규칙 A 중에서 가언 명제를 참이라고 가정한 A를 조건 증명 규칙이라고 한다. 다시 말해서, 어떤 가언 명제가 참이라고 가정하에 결론을 도출하는 것이 가능하다고 보는 규칙이라고 할 수 있다. 

E. ^도입 규칙(The Rule of ^-introduction)

이전에 우리는 ^ 기호가 '그리고'를 뜻한다는 것을 배웠다. ^ 도입 규칙은 논리 체계에서 어떤 명제 A와 B가 각각 참일 때, A and B 또한 참이라는 결과를 도출한다는 규칙을 의미한다. 

F. ^제거 규칙 (The Rule of ^-elimination)

^제거 규칙은 어떤 명제 A and B 가 참일 때, A와 B 각각 참이라는 결과를 도출하는 추론 규칙을 의미한다. 

G. v도입 규칙 (The Rule of v-introduction)

^ 도입과 마찬가지로 v 도입 규칙은 어떤 명제 A 또는 B가 참임을 A가 참 인 명제 또는 B가 참인 명제로부터 결론을 이끌어내는 추론을 의미한다. 

H. v제거 규칙 (The Rule of v-elimination)

^ 제거와 마찬가지로 v 제거 규칙은 어떤 명제 A 또는 B가 참임을 통해서 A가 참이거나 거짓이라는 C 결과를 도출하고 B가 참이거나 거짓이라는 C 결과를 도출한다는 사실을 통해서 결론 C에 이르는 추론을 의미한다.

I. 귀류법 (Reductio Ad Absurdum)

어떤 주장에 대한 함의 내용을 계속 따라가면, 거짓 결론에 다다르게 되는 것을 보이고 이 모순적 상황으로 말미암아 어떤 주장이 잘못되었다는 것을 증명하는 방법이다. 이 추론 법칙은 간접적인 증명 방법인데, 수학에서는 배리법 이라고도 알려져 있으며 어떤 수학적 명제가 참 임을 간접적으로 증명하는데 귀류법이 사용된다. 

 

 

* 다음 강의는 논리 상수를 통해서 나타내는 수학 증명입니다.

[Section 1] 논리 상수를 통해서 나타내는 수학 증명