1차 논리

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

논리학에서, 1차 논리(一次論理, 영어: first-order logic)는 원소에만 한정 기호를 가할 수 있고, 술어에는 한정 기호를 가할 수 없는 형식 언어이다. 명제 논리에 한정 기호를 추가하여 얻는다. 술어에도 한정 기호를 가할 수 있는 2차 논리와 달리, 완전성 정리가 성립한다. 수학, 철학, 언어학, 컴퓨터 과학 등에서 쓰인다.

1차 논리의 구성[편집]

1차 논리는 다음의 요소들로 이루어진다.

여기에서 공리는 논리 공리를 말한다. 1차 논리의 공리에 비논리 공리를 추가하여 여러 1차 이론을 만들 수 있는데, 이 추가된 공리들은 "논리적 사실"이 아닌 해당 이론 체계 내에서만 성립하는 명제들로 취급된다. 1차 이론의 대표적인 예로 체르멜로-프렝켈 집합론이 있는데, 이는 1차 논리에 "무한 집합이 존재한다"(무한 공리)를 비롯한 여러 비논리 공리를 추가한 것이다.

공리의 숫자가 무한한 경우에는 잘 구성된 논리식이 주어졌을 때 이것이 공리인지 아닌지를 판별할 수 있는 알고리즘이 있어야 한다. 또한, 추론 규칙이 올바르게 적용되었는지를 판별할 알고리즘도 있어야 한다.

논리식의 구성요소[편집]

1차 이론의 논리식은 다음의 요소들로 이루어진다.

  1. 술어변수(혹은 관계)들의 집합. 각 술어변수는 알파벳 대문자 P, Q, R, ...등으로 나타내며, 각자 항수(arity)를 갖고 있다.
  2. 상수들의 집합. 각 상수는 소문자 a, b, c, ...등으로 나타낸다.
  3. 함수들의 집합. 각 함수는 소문자 f, g, h, ...등으로 나타내며, 함수의 항수는 1 이상이다.
  4. 변수들의 무한 집합. 각 변수는 소문자 x, y, z, ...등으로 나타낸다.
  5. 논리 연산을 나타내는 기호: \neg(논리적 부정), \wedge(논리곱), \vee(논리합), →(조건기호), ↔(쌍조건기호).
  6. 한정기호를 나타내는 기호: \forall (전칭기호), \exists (존재기호).
  7. 좌측 괄호 "("와 우측 괄호 ")".
  8. 경우에 따라 동일성 기호 =를 포함시키기도 한다.

여기에서 변수와 논리 연산 및 한정기호 등은 논리 자체에 속하는 요소인 반면, 상수와 함수 및 술어변수의 집합은 각각의 1차 이론을 구성하는 요소가 된다. 예를 들어 군론의 언어는 하나의 상수(단위원)와 하나의 1항 함수(역원) 및 두 개의 2항 함수(곱셈과 동일성)로 이루어져 있다. (물론 동일성을 논리 자체의 요소로 본다면 2항 함수는 하나로 충분하다.)

구성 규칙[편집]

다음의 구성 규칙에 따라 항, 논리식 및 자유변수 등의 용어를 정의한다.

의 집합은 다음 규칙에 따라 반복적으로 정의된다:

  1. 임의의 상수는 항이다.
  2. 임의의 변수는 항이다.
  3. f가 n변수 함수이고 각 ti가 항이면 f(t1,...,tn)도 항이다.
  4. 위의 규칙들을 통해 항으로 규정되지 않는 것은 항이 아니다.

잘 구성된 논리식(간단히 줄여서 논리식이라고 함)의 집합은 다음 규칙에 따라 반복적으로 정의된다:

  1. P가 n항 술어변수이고 각 ai가 항이면 P(a1,...,an)은 논리식이다. 동일성을 논리의 일부분으로 보는 경우, (a1 = a2)도 논리식이다. 이 규칙만으로 생성되는 논리식을 원자논리식이라고 한다.
  2. φ가 논리식이면 ¬φ도 논리식이다.
  3. φ와 ψ가 논리식이면 (φ → ψ)도 논리식이다.
  4. φ가 논리식이고 x가 변수이면 ∀x φ도 논리식이다.
  5. 위의 규칙들을 통해 논리식으로 규정되지 않는 것은 논리식이 아니다.

같이 보기[편집]