편집토론기록

1차 논리

1차 논리(一次論理, 영어:first-order logic)는 단순히 기호와 연결자를 이용해서 논리를 전개하는 명제 논리에 ∀, ∃라는 한정자(Quantifier)를 도입하는 논리이다.

엄밀한 정의[편집 | 원본 편집]

1차 논리(一次論理, 영어:first-order logic)는 원소에만 한정 기호를 가할 수 있고, 술어에는 한정 기호를 가할 수 없는 술어 논리이다.[1] 명제 논리와 달리 변수에 대하여 한정 기호를 사용할 수 있으나, 2차 논리와 달리 변수들의 집합에 대하여 한정 기호를 사용할 수 없다. 1차 논리의 경우, (2차 논리와 달리) 괴델의 완전성 정리 · 콤팩트성 정리 · 뢰벤하임-스콜렘 정리와 같은 중요한 성질들이 성립한다.

자세한 설명[편집 | 원본 편집]

우선 명제 논리에서는 명제를 원소로 갖는 집합 [math]\displaystyle{ \mathcal{L} }[/math]과 명제를 부정하는 단항 연산자 [math]\displaystyle{ \neg }[/math] 와 원인-결과에 의해 참/거짓을 정의하는 이항 연산자 [math]\displaystyle{ \rightarrow }[/math]를 이용해 전개한다. 여기서 ￢p는 p를 부정하는 것으로, p가 참일 때 거짓, p가 거짓일 때 참의 값을 가진다. p→q는 p가 참일 때 q가 참이라는 뜻으로 p가 참이고 q가 거짓일 때 거짓의 값을, p가 거짓이거나 q가 참일 때 참의 값을 가진다. 연산의 우선순위를 결정하기 위해 괄호 (,)를 사용할 수 있다.

명제 논리에서 두 연산자를 사용하는 이유는 두 연산자를 모두 사용할 때 완전한 논리표를 갖출 수 있기 때문이다. 예를 들면 명제 p,q에 대해 p 또는 q가 참일 때 참인 문장 p∨q는 ￢p→q와 동치, p와 q 모두 참일 때 참인 문장 p∧q는 ￢(p→￢q)가 된다.

이러한 명제 논리만으로도 몇 가지 사실을 유도할 수 있다. 대표적인 항진명제로 명제 p,q에 대해서 Modus Ponens(p∧(p→q)→q)가 있는데, p가 참이고 p→q가 참일 때 q도 참이라는 것이다. 일례로 아래의 문장을 생각해보자.

p: 봄이 온다.
q: 벚꽃이 핀다.
p→q: 봄이 오면 벚꽃이 핀다.

그렇다면 봄이 온다는 것(p)과, 봄이 오면 벚꽃이 핀다(p→q)가 참일 때 벚꽃이 핀다(q)도 참이라는 것이다.

하지만 명제 논리는 단순히 문장 하나의 참/거짓을 판별하기에 변수를 이용해서 논리를 전개하는 데에는 부족하다. 그래서 단순한 명제(proposition)가 아닌 변수(variable)들의 집합, 변수를 한정하는 한정자 ∀(모든 변수 x에 대해), ∃(변수 x가 존재함), 하나 또는 유한개의 변수에 의해 정의되는 술어(Formula), 그리고 여러 개의 변수를 하나의 변수로 치환하는 함수(function)를 추가해서 논리를 더 많이 전개할 수 있다.

또한 단어(term)을 변수 x 또는 n변수 함수 f와 단어 x1,...xn에 대해 f(x1, ..., xn) 형태로 정의한다. 그리고 변수 없는 문장 c 또는 n개의 단어 c1,...cn과 n변수 술어 φ에 대해 φ(c1, ..., cn) 형태로 정의되는 식을 원자식(atomic formula)라고 정의한다.

이제 명제 혹은 원자식 p,q에 대해서 명제 논리에서의 ￢p, p→q, 가산개의 변수 x1, ..., xn,...에 대해 한정자에 의해 정의된 문장 [math]\displaystyle{ \forall v_i \phi (i \in \omega) }[/math]를 모두 식(formula)이라고 부른다.

예를 들면 변수 x가 주어졌을 때 변수 x에 대해서 "x가 인간이다"를 표현하는 술어 Man(x)를 표현할 수 있다. 또는 변수 x를 입력하고, x의 한글 이름을 값(nx)으로 호출하는 함수 Name(x)도 정의할 수 있다.

Man(x): x는 인간이다. -
Name(x) = nx : x에 대해서 x의 한글 이름 nx를 호출하는 함수.

여기서 우리는 "모든 사람은 한글로 이름을 표현할 수 있다."라는 문장을 기호 형태로 만들어 보면.

∀x(Man(x)→∃n(n=Name(x))

라고 표현할 수 있다.

1차 논리와 모델[편집 | 원본 편집]

우선 1차 논리의 언어의 집합은 위에서 설명한 논리 연산자, 한정자, 특정한 변수의 모임, 특정한 n변수 술어의 모임, 그리고 특정한 n변수 함수들의 모임을 모은 것이다. 여기서 논리 연산자와 한정자는 언어와는 무관하게 성립하기에 그런데 명제, 변수, 술어, 함수의 모임에 특정한 조건을 부여할 경우 그 1차 논리의 언어의 집합으로 유도할 수 있는 원소들은 제한적이 된다. 여기서 1차 논리의 상수들을 vi, 함수들을 fj, 술어들의 모임을 φk로 한정지으면, 이 상수, 함수, 술어들로 유도할 수 있는 모든 문장들의 집합 [math]\displaystyle{ \mathcal{L}=\left\lt v_i, f_j, \phi_k \right\gt }[/math]을 정의할 수 있는데, 이 유도되는 집합을 1차 논리 언어 [math]\displaystyle{ \mathcal{L} }[/math]에 의해 유도되는 모델(model) 혹은 L-구조체(structure)라고 부른다.

예를 들면 덧셈 연산자가 정의된 자연수 집합은 자연수 집합 [math]\displaystyle{ \mathbb{N} }[/math]과 시작수 0, 계승수(successor) 단항함수 S : x →x+와 덧셈함수 + : (a,b) →a+b에 의해 정의된 모델이라고 부를 수 있다.

[math]\displaystyle{ \mathcal{L} = \{ 0, S, +\}, M= (\mathbb{N}, \mathcal{L}) }[/math]

특히 변수의 집합 S와 S를 변수로 하는 식 φ에 대해서 모델 M이 φ(S)를 참으로 하는 경우에는 M이 φ(S)를 만족한다(M satisfies φ(S))라고 부르고 기호로는 M|=φ(S)로 표시한다. 예를 들면 선형 순서 연산자가 있는 실수의 집합 [math]\displaystyle{ M=\{ \mathbb{R}, \mathcal{L}=\{0^M , 1^M , +, \times, -, {}^{-1} , \leq \}\} }[/math]가 있을 때 "a>b이면 a+c>b+c이다"라는 문장이 실수의 집합에 대해 성립한다는 것은

[math]\displaystyle{ M\models (\forall a,b(a\gt b \rightarrow (\forall c(a+c\gt b+c))) }[/math]

형태로 표현가능하다.

무모순성[편집 | 원본 편집]

만약 어떤 모델이 고정된 변수 s에 대해서 식 φ(s)와 그의 부정 ￢φ(s)를 동시에 유도한다면 모델이 모순성을 갖고 있다(Model M is inconsistent)고 정의한다. 모순성이 없으면 그 모델 M은 무모순(consistent)이라고 부른다.

괴델의 불완정성 정리에 의해서 어떠한 모델도 스스로의 무모순성을 증명할 수 없다. 하지만 우리는 모든 집합에서 체르멜로-프랑켈 집합론 공리들을 언어로 하는 모델같이 충분히 "무모순성이 있다고 여겨지는" 모델들을 이용해서 다른 모델들의 무모순성을 증명할 수 있다.

참조[편집 | 원본 편집]

각주

  1. ↑ Hodges, Wilfrid (2001년 8월 1일). 〈Classical logic I: first order logic〉, 《The Blackwell Guide to Philosophical Logic》 (en). Blackwell. 틀:Zbl. ISBN 978-0-631-20693-4