1차 논리

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

1차 논리(first-order logic)는 1차 술어 논리수학, 철학, 언어학, 컴퓨터 과학 등에서 쓰이는 형식 언어이다. 일반적으로 술어논리로 부르기도 하지만, 술어논리에는 1차논리 이외에 다른 고차 술어논리가 포함된다. 명제 논리를 보다 강력하게 확장한 것이다.

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. 위의 규칙들을 통해 논리식으로 규정되지 않는 것은 논리식이 아니다.

함께 보기[편집]