최근 수정 시각 : 2019-04-23 02:43:09

술어 논리


1. 1차 술어논리2. 1차 술어논리에서의 해석3. 1차 술어논리의 추론 규칙
3.1. 동어반복적 추론(Tautological inference; T)3.2. 전제도입(Introduction of premises; P)3.3. 조건문화(Conditionalization; C)3.4. 보편 예화(Universal specification; US)3.5. 보편 일반화(Universal generalization; UG)3.6. 존재 일반화(Existential generalization; EG)3.7. 존재 예화(Existential specification; ES)3.8. 존재양화사 전환(Existential quantification; E)3.9. 양화사 전환(Quantifier exchange; Q)
4. 고차 논리

1. 1차 술어논리

이하의 내용은 벤슨 메이츠 저, 김영정 및 선우환 역, 『기호논리학(Elementary Logic)』, 문예출판사, 1995의 내용을 참고했다.

1차 술어 논리(first-order predicate logic) 혹은 기초 논리(elementary logic)명제 논리를 확장한 언어이며, 명제를 쪼개서 대상과 술어 간의 관계까지 기호화하는 체계에 해당한다. 예를 들어 '소크라테스는 사람이다'가 명제논리에서는 'P'로 표현될 수 있지만, 양화 논리에서는 'Qs'로 표현될 수 있다. 양화 논리에서 술어('F', 'G', 'H' ...)는 영문 대문자이탤릭체로, 특정 개체는 영문 소문자 이탤릭체('a', 'b', 'c')로 표기하는 것이 관례다. 이때 특정 개체를 지시하는 영문 소문자를 개체 상항(혹은 상수, constant)이라고 한다.

또한 명제논리와는 달리 술어논리에서는 임의의 대상들을 논항으로 갖는 변항(variable)이 등장한다. 예를 들어 'x는 사람이다'는 'Hx'라고 표현될 수 있다. 변항은 일반적으로 'x', 'y', 'z' 등 소문자 이탤릭체로 표기한다. 개체 상항과 같은 영문 소문자 알파벳이라 헷갈리기 쉽지만 개체 상항과 변항은 다르다. 변항은 특정한 개체를 지시하는 것이 아니며, 문장의 대상이 변항이 된다면 그 문장은 열린 문장(open sentence), 즉 진리값을 가질 수 없는 문장이 된다. 예를 들어서 'Fa'는 열린 문장이 아니지만 'Fx'는 열린 문장이다. 일반적으로 개체상항은 'a' ~ 't'까지의 알파벳을 사용하고, 변항은 'u' ~ 'z'까지의 알파벳을 사용한다. 또한 아래 첨자로 양의 정수를 붙여 가산 무한개의 개체상항과 변항, 그리고 술어를 표현할 수 있다. 또한 변항, 개체상항, 술어를 이탤릭체로 표기하는 것이 관례긴 하지만, 정자체로 표기하는 경우도 있다.

열린 문장이 의미를 지닐 수 있게 하기 위해서는 변항이 양화사(quantifier)를 통해 속박(bound)되어야 한다. 이때 양화사에 의해 속박되지 않은 변항을 자유 변항(free variable)이라고 한다. 자유 변항만으로 이루어진 표현을 식(formula)이라고 한다. 어떠한 변항도 자유롭게 나타나지 않는 식이 문장(sentence)이다.

양화사는 특정 술어를 만족하는 대상이 주어진 논의 영역(혹은 논의 세계, domain; universe of discourse)에 얼마나 존재하는지를 알려주는 의미를 갖는다. 양화사에는 존재양화사와 보편양화사 두 종류가 있다.
  • 존재양화사 \exists (existential quantifier)
    -한 것이 존재한다(exist). Exist의 E를 뒤집어서 따왔다.
    • 예. 파랑색이면서 둥그런 것이 존재한다 ⇒ (∃x)(Bx & Cx)
  • 보편양화사 \forall (universal quantifier)
    모든 것이(all) -하다. All의 A를 뒤집어서 따왔다.
    • 예. 모든 것은 파랑색이면서 동그랗다 ⇒ (∀x)(Bx & Cx)

일반적으로 존재양화사(∃) 문장은 일상 언어에서의 '어떤 P는 Q다', 'P인 것이 있다', 보편양화사(∀)는 '임의의 P는 Q다', '모든 것은 P다'에 대응하는 것으로 여겨진다. 하지만 임의의 술어 P에 대하여 일상언어 문장인 '만약 모든 P가 Q이면 어떤 P는 Q이다'라는 문장은 논리적으로 타당해보이지만, (∀x)(Px → Qx) → (∃x)(Px & Qx)는 논리적으로 타당하지 않다. 즉 양화사 또한 일상 언어에서의 직관과 괴리가 있다. 보다 자세한 사항은 존재함축 참조.

명제논리에서 사용되던 연결사들은 양화논리에서 역시 거의 동일한 의미로 사용된다. 양화논리에서 추가적으로 도입되는 연결사로는 등호 '='가 있다. 등호는 대상을 가리키는 두 기호가 논의 영역 내의 동일한 대상을 가리키는 것을 나타내는데 쓰인다.
  • 예시1. 관우는 미염공과 같다 ⇒ g=m
  • 예시2. 관우는 존재한다 ⇒ (∃x)(x=g)

또한, 술어들 중에는 둘 이상의 대상을 필요로 하는 술어도 있다. 이러한 술어를 n항 술어(n-ary predicate)라고 하며, n항 술어는 공집합이 아니라면 n중쌍(n-tuple)의 집합, 즉 n항 관계를 할당 받는다. 이를테면 'x가 y를 사랑한다'는 'Lxy'와 같이 쓸 수 있다. 원칙적으로는 술어 뒤에 위첨자로 n을 표기해줘야 하지만, 뒤에 이어지는 변항의 수로 n을 짐작할 수 있기 때문에 생략하기도 한다.

1차 술어논리는 결정가능하지 않다. 1차 술어논리에서 역시 진리표와 같은 방법을 사용할 수는 있지만, 진리표는 단지 특정 문장이 동어반복적이라는 것만을 검증할 수 있을 뿐이다. 1차 술어논리에서는 동어반복적이지 않더라도 타당한 문장이 존재한다. 예를 들어 ‘모든 사람은 죽는다. 따라서 소크라테스는 죽는다’라는 추론은 동어반복적이지 않지만 타당하다. 명제 논리에서는 아무리 복잡한 명제라도 진리표 방법을 통해 검증할 수 있지만, 1차 술어논리에서는 그렇지 않기 때문에 추론 규칙의 활용이 더욱 중요해진다.

양화논리 체계 하에서 모든 문장의 진리치를 기계적으로 결정하는 방법은 존재하지 않는다는 것이, 즉 결정 불가능 문제가 있다는 것이 1936년 알론조 처치(Alonzo Church)의 람다 대수 논문에서 처음으로 증명되었다. 곧이어(처치의 논문은 1936년 4월, 튜링의 논문은 1936년 5월에 발표되었다.) 앨런 튜링(Alan Turing)에 의해 정지 문제(halting problem)가 이와 같은 결정 불가능 문제에 속한다는 것이 증명되었다.

2. 1차 술어논리에서의 해석

1차 술어논리에서 한 문장 ϕ가 주어졌을 때, ϕ를 해석한다는 것은 다음과 같은 과정을 거치는 것이다.

1. 공집합이 아닌 논의 영역을 명시한다.
2. 개체 상항에 논의 영역에 속한 개체를 할당한다.
3. 1항 술어에 개체들의 집합을 할당한다. n항 술어에는 n항 관계를 할당한다.

이상과 같은 작업을 거치고 나면 문장 ϕ의 주어진 해석 하에서의 참 혹은 거짓을 판별할 수 있다.

예시를 들면 다음과 같다.

해석 I에 대해
1. I의 논의 영역을 {1, 2, 3}이라고 하자
2. 개체 상항 a, b, c가 각각 1, 2, 3이라고 하자
3. 술어 F, G, H에 {1}과 {2}와 {3}을 할당하자

이상과 같은 해석 하에서, 문장 Fb는 거짓이다. 문장 Fa는 참이다. 문장 (∀x)Fx는 거짓이다. 문장 (∃x)Fx는 참이다.

양화논리에서 참의 의미는 귀납적으로 정의된다. 쉽게 이해할 수 있도록 정의하자면 다음과 같다.
  • Fa가 해석 I 하에서 참이다 ↔ I가 Fa에 T를 할당한다 ↔ 해석 I 하에서 a가 F의 원소다
  • Ra1a2a3a4....an이 해석 I 하에서 참이다 ↔ I가 Ra1a2a3a4...an에 T를 할당한다 ↔ 해석 I 하에서 n중쌍 <a1, a2, a3, ... , an>이 R의 원소다
  • (∀x)Fx가 참이다 ↔ I가 (∀x)Fx에 T를 할당한다 ↔ I의 논의 영역의 모든 대상이 F의 원소다
  • (∃x)Fx가 참이다 ↔ I가 (∃x)Fx에 T를 할당한다 ↔ I의 논의 영역에서 적어도 하나의 대상이 F의 원소다
  • 이상과 같이 술어 문장의 진리값을 할당하고 나면, 각각의 술어 문장을 명제논리 체계에서와 같은 방식으로 다룰 수 있다.

엄밀한 정의는 이와 다르지만, 대략적으로 위와 같다고 이해하면 된다. 엄밀한 정의에서는 메타 문장을 사용하고, 보다 엄밀한 표현을 사용하며, '각각의 술어 문장을 명제논리 체계에서와 같은 방식으로 다룰 수 있다'고 간략하게 언급한 부분을 보다 상세하게 다루고 있다. 또한, I가 Fa에 T를 할당한다는 표현 대신, I가 Fa의 모형이라고 표현하기도 한다.

위와 같은 참의 정의에 따라, 양화논리에서 타당성, 귀결, 일관성이 다음과 같이 정의된다.
  • 문장 ϕ가 모든 해석 하에서 참일 경우 문장 ϕ는 타당하다.
  • 문장 ϕ와 문장집합 Γ에 대해, Γ의 모든 문장들을 참이게 하면서 ϕ를 거짓이게 하는 해석이 존재하지 않을 경우 Φ는 Γ의 귀결이다.
  • 문장집합 Γ에 대해, Γ의 모든 문장들을 참이게 하는 해석이 하나라도 존재할 경우 Γ는 일관적이다.

3. 1차 술어논리의 추론 규칙


1차 술어논리에서는 모든 명제 논리에서의 추론 규칙과 논리적 정리를 활용한다. 이 추론 규칙들과 정리들을 양화논리에서는 ‘동어반복적 추론(Tautological inference; T)’이라고 한다. 이에 더해 1차 술어논리에서 추가적으로 필요한 추론 규칙들이 있다. 추론 규칙을 사용하면 해석을 거치지 않아도 문장의 변형이 가능하다는 장점이 있으며, 진리표와 같은 기계적 검산이 불가능한 1차 술어논리에서 논리적 추론은 훨씬 더 중요하다. 무한한 해석에 대한 기계적인 검산은 불가능하다 하더라도, 1차 술어논리 체계는 건전하고 완전한 체계이기 때문에, 어떤 문장이 어떤 문장집합의 귀결이라는 것과 어떤 문장집합으로부터 어떤 문장을 도출하는 형식적으로 올바른 추론이 존재한다는 것은 동치이다. 즉 형식적 도출만으로 귀결 관계를 보일 수 있다.

이하의 규칙들 중에서 EG, ES, Q는 단축규칙으로 분류되며 다른 추론 규칙들로부터 연역될 수 있다. 이하의 모든 경우에서 ϕ와 ψ는 임의의 식을, α는 변항을, β는 개체 상항을 의미한다고 하자. 그리고 ϕα/β를 변항 α대신 개체 상항 β를 대입한 식이라고 하자.

3.1. 동어반복적 추론(Tautological inference; T)

앞서 설명한 것과 같이, 명제논리의 모든 추론은 동어반복적 추론으로 1차 술어논리 체계에서 활용될 수 있다.

3.2. 전제도입(Introduction of premises; P)

임의의 문장이 전제로서 임의의 행에 도입될 수 있다는 규칙이다.

3.3. 조건문화(Conditionalization; C)

C: ψ ⊢ (ϕ → ψ)

조건문화 규칙은 사실상 명제논리의 조건도입 규칙과 큰 차이가 없다.

3.4. 보편 예화(Universal specification; US)

US: (∀α)ϕ ⊢ ϕα/β

논의세계의 모든 원소가 어떤 문장을 만족한다면, 특정한 대입례 하나가 그 문장을 만족한다는 것은 타당하다.
한국어 추론 예시.
모든 것은 물리적인 것이다.
태양은 물리적인 것이다.

3.5. 보편 일반화(Universal generalization; UG)

보편 일반화에는 'β가 ϕ에도 ϕα/β가 나타나는 항의 어떤 전제에도 나타나지 않을 때'라는 제한 조건이 붙는다.
해당 제한 조건 하에서, UG: ϕα/β ⊢ (∀α)ϕ

이는 β가 특정 개체를 가리키기보다는 변항에 대해 임시적인 대입항으로 사용되었을 때, 보편 예화된 문장을 다시 일반화할 수 있다는 규칙이다.
한국어 추론 예시.
모든 사람은 죽는다.
소크라테스는 죽는다.
따라서, 모든 사람은 죽는다.[1]

3.6. 존재 일반화(Existential generalization; EG)

EG: ϕα/β ⊢ (∃α)ϕ

특정한 개체상항이 어떤 문장을 만족한다면, 어떤 문장을 만족하는 것이 있다고 쓸 수 있다.
한국어 추론 예시.
소크라테스는 사람이다.
사람인 것이 있다.

3.7. 존재 예화(Existential specification; ES)

존재 예화에는 'β가 ϕ에도 ψ에도 ψα/β를 제외한 ϕ의 전제에도 나타나지 않을 때'라는 제한 조건이 붙는다.
해당 제한 조건 하에서, ES: (∃α)ψ, ψα/β ⇒ ϕ ⊢ ϕ

이는 네가지의 예화/일반화 규칙 중에 가장 복잡한 규칙이며, 보편 예화와 보편 일반화가 서로 대응되는 규칙인 반면 존재 일반화와 존재 예화는 서로 대응되지 않는다.

좀 더 구체적으로 설명하자면 이렇다. 어떤 존재양화문이 나타나고, 그 존재양화문을 만족하는 임의의 개체를 하나 가정하자. 그러한 대입례로부터 도출되는 문장이 있고, 도출되는 문장에 앞서 가정된 개체상항이 나타나지 않는다면, 그것은 참인 존재양화 문장의 임의의 대입례로부터 도출된 것이므로 참이라고 할 수 있다.
한국어 추론 예시.
모든 한국인은 아시아인이다.
한국인인 사람이 있다.
철수가 그러한 한국인이라고 가정하자.
첫번째 전제에 의해, 철수가 한국인이라면 철수는 아시아인이다.
철수는 아시아인이다.(전건긍정식)
아시아인인 사람이 있다.(존재 일반화)
따라서, 아시아인인 사람이 있다.

3.8. 존재양화사 전환(Existential quantification; E)

E: ~(∀α)~ϕ ⊢ (∃α)ϕ, (∃α)ϕ ⊢ ~(∀α)~ϕ
한국어 추론 예시.
사람인 것이 있다.
모든 것이 사람이 아닌 것은 아니다.

3.9. 양화사 전환(Quantifier exchange; Q)

Q: (∀α)~ϕ ⊢ ~(∃α)ϕ, ~(∃α)ϕ ⊢ (∀α)~ϕ
한국어 추론 예시.
비물질적인 것은 존재하지 않는다
모든 것은 비물질적인 것이 아니다.

존재양화사 전환과 양화사 전환으로부터, 그리고 약간의 추가적인 추론을 거치면, 양화사는 다음과 같은 규칙에 따라서 전환 가능하다고 할 수 있다. 우선, 양화사가 속박하고 있는 열린 문장을 부정한다. 다음으로 양화사의 종류를 바꾼다. 마지막으로 문장 전체를 부정한다. 이상의 작업을 거친 문장과 원래의 문장은 동치이다.

이를 풀어서 설명하면 다음과 같다.
  • ~(∀x)~Φx ↔ (∃x)Φx '모든 x가 Φ가 아닌 것은 아니다'와 'Φ인 x가 존재한다'는 동치이다.
  • (∀x)Φx ↔ ~(∃x)~Φx '모든 x는 Φ이다'와 'Φ이지 않은 x는 존재하지 않는다'는 동치이다.
  • (∀x)~Φx ↔ ~(∃x)Φx '모든 x는 Φ가 아니다'와 'Φ인 x는 존재하지 않는다'는 동치이다.
  • ~(∀x)Φx ↔ (∃x)~Φx '모든 x가 Φ인 것은 아니다'와 'Φ이지 않은 x가 적어도 하나 존재한다'는 동치이다.

4. 고차 논리

고차 논리(higher-order logic)에서는 술어를 양화할 수 있다. 즉 1차 술어 논리에서는 논의영역 내의 대상들을 두고 "모든 대상은 이러하다", "어떤 대상은 저러하다"라고 밖에 표현할 수 없는 반면, 2차 논리 이상의 고차 논리에서는 "모든 속성은 이러하다", "어떤 속성은 저러하다"라는 명제 또한 표현할 수 있다. 예컨대 고차 논리에서는 다음과 같은 명제를 서술할 수 있다:
  • 라이프니츠 법칙(Leibniz's law): 모든 속성에서 일치하는 두 대상은 동일하다.
    • 기호화: "∀F∀x∀y(((Fx → Fy) & (Fy → Fx)) → x = y)"
    • 해석: 임의의 술어 F에 대해 임의의 대상 x와 y가 F를 만족시키는지 아닌지 여부에서 항상 일치하는 경우, x와 y는 같은 대상을 가리킨다. 이 법칙은 항상 성립하는지 아닌지에 대한 논란이 있다.

고차 논리에서는 1차 술어논리 및 명제 논리에서와 달리 건전성, 완전성, 일관성이 동시에 성립하지 않는다. 또한 속성이라는 추상적 대상을 양화하는 과정에서 문제가 발생하기 때문에, 그 논리적 기초가 1차 술어논리에 비해 안정적이지 못한 것으로 여겨진다. 반대로 말하자면 건전성, 완전성, 일관성이 모두 성립하며 논리적 기반이 안정적인 1차 술어논리가 현재 가장 기초적인 논리체계 중의 하나라는 뜻이기도 하다. 그래서 1차 술어논리의 다른 이름이 기초 논리인 것이다.

또한 집합론은 2차 술어논리의 체계로 환원될 수 있다. 집합론의 바탕을 이루는 공리계인 ZFC 공리계에는 1차 술어논리로 환원될 수 없는 공리꼴(Axiom schema)이 있는데, 이 공리꼴들은 2차 술어논리를 통해서는 설명될 수 있다.

파일:크리에이티브 커먼즈 라이선스__CC.png 이 문서의 내용 중 전체 또는 일부는 수리 논리학 문서의 r224 판, 4번 문단에서 가져왔습니다. 이전 역사 보러 가기




[1] 바로 위의 문장은 보편양화 문장의 임의의 대입례로 사용되었기 때문에, 이로부터 다시 일반화할 수 있다.