1차 논리
위키백과 ― 우리 모두의 백과사전.
1차 논리(first-order logic)는 수학, 철학, 언어학, 컴퓨터 과학 등에서 쓰이는 형식 언어로, 술어논리(predicate calculus)라고도 한다. 명제논리를 보다 강력하게 확장한 것이다.
목차 |
[편집] 1차 논리의 구성
1차 논리는 다음의 요소들로 이루어진다.
여기에서 공리는 논리 공리를 말한다. 1차 논리의 공리에 비논리 공리를 추가하여 여러 1차 이론을 만들 수 있는데, 이 추가된 공리들은 "논리적 사실"이 아닌 해당 이론 체계 내에서만 성립하는 명제들로 취급된다. 1차 이론의 대표적인 예로 체르멜로-프란켈 집합론이 있는데, 이는 1차 논리에 "무한 집합이 존재한다"(무한공리)를 비롯한 여러 비논리 공리를 추가한 것이다.
공리의 숫자가 무한한 경우에는 잘 구성된 논리식이 주어졌을 때 이것이 공리인지 아닌지를 판별할 수 있는 알고리즘이 있어야 한다. 또한, 추론 규칙이 올바르게 적용되었는지를 판별할 알고리즘도 있어야 한다.
[편집] 논리식의 구성요소
1차 이론의 논리식은 다음의 요소들로 이루어진다.
- 술어변수(혹은 관계)들의 집합. 각 술어변수는 알파벳 대문자 P, Q, R, ...등으로 나타내며, 각자 항수(arity, 변수의 수)를 갖고 있다.
- 상수들의 집합. 각 상수는 소문자 a, b, c, ...등으로 나타낸다.
- 함수들의 집합. 각 함수는 소문자 f, g, h, ...등으로 나타내며, 함수의 항수는 1 이상이다.
- 변수들의 무한집합. 각 변수는 소문자 x, y, z, ...등으로 나타낸다.
- 논리 연산을 나타내는 기호:
(논리적 부정),
(논리곱),
(논리합), →(조건기호), ↔(쌍조건기호).
- 한정기호를 나타내는 기호:
(전칭기호),
(존재기호).
- 좌측 괄호 "("와 우측 괄호 ")".
- 경우에 따라 동일성 기호 =를 포함시키기도 한다.
여기에서 변수와 논리 연산 및 한정기호 등은 논리 자체에 속하는 요소인 반면, 상수와 함수 및 술어변수의 집합은 각각의 1차 이론을 구성하는 요소가 된다. 예를 들어 군론의 언어는 하나의 상수(단위원)와 하나의 1변수 함수(역원) 및 두 개의 2변수 함수(곱셈과 동일성)로 이루어져 있다. (물론 동일성을 논리 자체의 요소로 본다면 2변수 함수는 하나로 충분하다.)
[편집] 구성 규칙
다음의 구성 규칙에 따라 항, 논리식 및 자유변수 등의 용어를 정의한다.
항의 집합은 다음 규칙에 따라 반복적으로 정의된다:
- 임의의 상수는 항이다.
- 임의의 변수는 항이다.
- f가 n변수 함수이고 각 ti가 항이면 f(t1,...,tn)도 항이다.
- 위의 규칙들을 통해 항으로 규정되지 않는 것은 항이 아니다.
잘 구성된 논리식(간단히 줄여서 논리식이라고 함)의 집합은 다음 규칙에 따라 반복적으로 정의된다:
- P가 n항 술어변수이고 각 ai가 항이면 P(a1,...,an)은 논리식이다. 동일성을 논리의 일부분으로 보는 경우, (a1 = a2)도 논리식이다. 이 규칙만으로 생성되는 논리식을 원자논리식이라고 한다.
- φ가 논리식이면 ¬φ도 논리식이다.
- φ와 ψ가 논리식이면 (φ → ψ)도 논리식이다.
- φ가 논리식이고 x가 변수이면 ∀x φ도 논리식이다.
- 위의 규칙들을 통해 논리식으로 규정되지 않는 것은 논리식이 아니다.
[편집] 함께 보기
- 자동 정리 증명
- 괴델의 불완전성 정리
- 1차 이론의 목록
- 추론 규칙의 목록
- 수리논리학
- 명제논리