1차 논리

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

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

정의[편집]

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

  • 특정 문자열들의 집합을 논리식의 집합라고 한다. 논리식이 만족시켜아 하는 문법은 재귀적으로 정의된다.
  • 특정 논리식 집합으로부터 다른 논리식을 추론할 수 있다. 이에 대한 규칙은 힐베르트 체계 및 다른 여러 방식으로 명시될 수 있다.
  • 1차 논리 언어의 의미론이란, 그 언어의 문장들에 대하여 참인지 여부를 일관적으로 부여하는 구조이다. 이는 보통 모형으로 주어진다.

문법[편집]

다음과 같은 데이터가 주어졌다고 하자. (여기서 자연수, 즉 음이 아닌 정수의 집합이다.)

  • 집합 및 함수 , . 는 유한 집합이거나 무한 집합일 수 있다. 이를 연산(演算, 영어: operation)의 집합이라고 한다.
  • 집합 및 함수 , . 는 유한 집합이거나 무한 집합일 수 있다. 이를 관계(關係, 영어: relation)의 집합이라고 한다.

그렇다면, 으로 정의되는 1차 논리 언어 는 특정한 문자열들의 집합이다. 이 문자열을 구성하는 문자 집합

은 구체적으로 다음과 같다.

  • 가산 무한 개의 변수들
    • 가산 무한 개의 변수들만으로 충분한 이유는 모든 논리식의 길이가 유한하기 때문이다. 무한 논리의 경우 더 많은 변수들을 추가할 수 있다.
  • 명제 논리의 연산 (함의) 및 (부정).
    • 그 대신 다른 기호들을 사용할 수도 있다. 예를 들어, 논리합 또는 논리곱 등이 있다.
  • 등호
  • 전칭 기호(全稱記號, 영어: universal quantifier) .
    • 그 대신 존재 기호(存在記號, 영어: existential quantifier) 를 사용할 수도 있다. 사실, 임의의 변수 에 대하여 이며 이므로, 이들은 서로 동치이다.
  • 에 대하여, 기호 . 이를 연산이라고 하며, 항수(項數, 영어: arity)라고 한다. 0항 연산을 상수(영어: constant)라고 한다.
  • 에 대하여, 기호 . 이를 관계라고 하며, 항수(項數, 영어: arity)라고 한다. 1항 관계를 술어(영어: predicate)라고 한다. (항수가 0인 관계는 고전 명제 논리에서는 참 또는 거짓이 되므로 자명하다.)
  • 이 밖에도, 괄호 및 반점 등은 엄밀히 말해 불필요하지만, 가독성을 돕기 위해 첨가한다. 예를 들어, 대신 로 쓴다.

이 기호들 가운데, 를 제외한 기호들을 논리 기호(영어: logical symbol)라고 한다.

1차 논리의 (項, 영어: term)은 다음 문법을 따른다.

  • 모든 변수는 항이다.
  • 임의의 개의 항 에 대하여, 은 항이다. (상수의 경우, 즉 일 때, 보통 괄호 를 생략하여 로 쓴다.)

1차 논리의 논리식(영어: (well-formed) formula)은 다음 문법을 따르는, 위 기호들의 문자열이다.

  • 임의의 개의 항 에 대하여, 은 논리식이다.
  • 두 항 , 에 대하여, 는 논리식이다.
  • 논리식 에 대하여, 는 논리식이다.
  • 논리식 에 등장하는 변수 가 자유 변수라면, 는 논리식이다.

여기서 논리식 및 그 속에 등장하는 변수 에 대하여, 만약 를 포함하지 않는다면, 자유 변수(영어: free variable)라고 하며, 그렇지 않다면 종속 변수(영어: bound variable)라고 한다.

자유 변수를 갖지 않는 (즉, 그 속에 등장하는 모든 변수가 종속 변수인) 논리식을 문장(文章, 영어: sentence)이라고 한다.

공리와 추론 규칙[편집]

1차 논리의 증명 이론은 다양한 방식으로 공리화할 수 있다. 예를 들어 다비트 힐베르트의 힐베르트 체계(영어: Hilbert system)나, 게르하르트 겐첸의 시퀀트 계산법(영어: sequent calculus)이나 자연 언역(영어: natural deduction) 등을 사용할 수 있다.

1차 논리를 힐베르트 체계를 사용하여 공리화하면, 다음과 같다. 우선, 편의상 다음과 같은 기호만을 사용한다고 하자.

  • 명제 논리에서, 오직 함의 부정 만을 사용한다고 하자. (논리합이나 논리곱과 같은 다른 명제 논리 기호는 이 둘로 나타낼 수 있다.)
  • 술어 논리에서, 오직 전칭 기호 만을 사용한다고 하자. (존재 기호 만으로 나타낼 수 있다.)

이 경우, 다음과 같은 공리 기본꼴(영어: axiom schema)들을 정의한다. 이 공리 기본꼴들에서 사용된 기호들은 다음과 같다.

  • , , 는 임의의 논리식을 뜻한다.
  • , 는 임의의 항을 뜻한다.
  • 는 임의의 변수를 뜻한다.

즉, 공리 기본꼴에서 위의 기호들을 실제의 논리식·항·변수로 치환하면 공리들을 얻는다.

우선, 추론 규칙으로 전건 긍정의 형식

가 있다. 이 밖에, 다음과 같은 명제 논리의 공리 기본꼴들이 사용된다.

1차 술어 논리의 경우, 다음과 같은 추가 공리 기본꼴들이 사용된다.

공리 기본꼴 ㈆에서, 의 자유 변수일 수 없다.
공리 기본꼴 ㈈에서, 논리식 의 자유 변수이어야 한다.

위 공리 기본꼴들에서, 논리식 에 등장하는 자유 변수 를 항 로 대체하여 얻는 논리식을 뜻한다. 예를 들어, 의 언어에서

이다. 이때, 논리식 내부의 ‘’에서 가 치환되지 않는 이유는 이 부분에서는 가 종속 변수이기 때문이다.

성질[편집]

의미론[편집]

1차 논리의 의미론은 보통 모형으로 주어진다. 주어진 연산 집합 와 관계 집합 을 갖는 1차 논리 언어 가 주어졌다고 하자. 그렇다면, 이 언어의 모형은 집합 및 각 항 연산 에 대하여 해석 및 각 항 관계 에 대하여 그 해석 으로 구성된다. 이를 통해, 의 문장 의 모형 에 대하여, 에서 참인지 또는 거짓인지 여부를 정의할 수 있다. 에서 참이라는 것은

로 표기한다.

보다 일반적으로, 의 논리식 가 자유 변수 를 갖는다고 하자. 그렇다면, 의 모형 및 그 속의 개의 원소

가 주어졌을 때,에서 에 대하여 참인지 또는 거짓인지 여부를 정의할 수 있다. 이는

로 표기한다.

1차 논리의 경우 콤팩트성 정리뢰벤하임-스콜렘 정리가 성립한다.

증명 이론[편집]

비논리 기호를 포함하지 않는 1차 논리 문장들의 집합을 라고 하자. 그 가운데, 모든 모형에서 참인 문장들의 부분 집합

을 생각하자. 또한, 속에서, 위의 힐베르트 체계를 통해 증명할 수 있는 문장들의 집합을

그렇다면, 다음이 성립한다.

  • 1차 논리의 건전성 정리에 따르면, 이다. 즉, 명제가 증명 가능한지 여부는 명제가 참인지 여부와 동치이다.
  • 재귀 집합이다. (이는 레오폴트 뢰벤하임이 1915년에 증명하였다.)

보다 일반적으로, 임의의 가산 연산 집합 와 관계 집합 를 갖는 1차 논리 언어 속에서, 문장들의 집합을 라고 하자. 그 가운데, 모든 모형에서 참인 문장들의 부분 집합

을 생각하자.

  • 괴델의 완전성 정리에 따르면, 재귀 열거 집합이다.
  • 만약 에 (등호를 제외한) 2항 이상의 항수를 갖는 관계가 존재한다면, 재귀 집합이 아니다.
  • 만약 이며, 의 모든 관계가 술어(1항 관계) 또는 등호라면, 재귀 집합이다. 이러한 언어를 1항 1차 언어(영어: monadic first-order language)라고 한다.

린드스트룀 정리[편집]

린드스트룀 정리(영어: Lindström’s theorem)에 따르면, 1차 술어 논리는 (가산) 콤팩트성 정리와 하향 뢰벤하임-스콜렘 정리를 만족시키는 가장 강력한 논리 체계이다.[1]

[편집]

집합론[편집]

체르멜로-프렝켈 집합론의 언어는 하나의 2항 관계 만을 포함하며, 아무런 연산을 갖지 않는다. 집합론에서 사용되는 대부분의 명제들은 이 언어로 나타낼 수 있다.

체와 순서체[편집]

의 1차 논리 언어

는 두 개의 이항 연산과 하나의 1항 연산 및 두 개의 상수(0항 연산)을 포함하며, 등호 밖의 관계를 갖지 않는다. 보통 와 같이 표기한다.

순서체의 1차 논리 언어

는 두 개의 이항 연산과 하나의 1항 연산 및 두 개의 상수(0항 연산)을 포함하며, 하나의 2항 관계를 갖는다. 보통 와 같이 표기한다.

역사[편집]

고틀로프 프레게가 1879년에 출판된 《개념 표기법》[2]에서 사용한 논리는 (현대적 용어로는) 2차 논리였다.[3]:295 이후 찰스 샌더스 퍼스가 1차 논리와 2차 논리를 구분하였으며, "1차 논리"라는 용어를 도입하였다.[3]:296

참고 문헌[편집]

  1. Lindström, Per (1969년 4월). “On extensions of elementary logic”. 《Theoria》 (영어) 35 (1): 1–11. doi:10.1111/j.1755-2567.1969.tb00356.x. ISSN 0040-5825. 
  2. Frege, Gottlob (1879). 《Begriffsschrift, eine der arithmetischen nachgebildete Formelsprache des reinen Denkens》 (독일어). 할레: Verlag von Louis Nebert. 
  3. Putnam, Hilary (1982). “Peirce the logician”. 《Historia Mathematica》 (영어) 9 (3): 290–301. doi:10.1016/0315-0860(82)90123-9. ISSN 0315-0860. 
  • Hodges, Wilfrid (2001년 8월). 〈Classical logic I: first order logic〉. Goble, Lou. 《The Blackwell Guide to Philosophical Logic》 (영어). Blackwell. ISBN 978-0-631-20693-4. 
  • Moore, Gregory H. (1988). 〈The emergence of first-order logic〉 (PDF). Aspray, William; Kitcher, Philip. 《History and Philosophy of Modern Mathematics》. Minnesota Studies in the Philosophy of Science (영어) 11. University of Minnesota Press. 95–135쪽. JSTOR 10.5749/j.cttttp0k.7. 
  • Eklund, Matti (1996년 12월). “On how logic became first-order” (PDF). 《Nordic Journal of Philosophical Logic》 (영어) 1 (2): 147–167. 

바깥 고리[편집]