나무모에 미러 (일반/어두운 화면)
최근 수정 시각 : 2024-04-13 19:35:36

술어 논리

1차 술어 논리에서 넘어옴
논리학
Logics
{{{#!wiki style="margin: -0px -10px -5px; min-height: 28px"
{{{#!folding [ 펼치기 · 접기 ]
{{{#!wiki style="margin: -6px -1px -11px;"
<colbgcolor=#2ab5b5> 형식 논리 명제 논리(논리 연산 · 삼단논법(정언삼단논법) · 순환 논법) · 공리 · 진리치 · 술어 논리 · 논증(논증의 재구성) · 모순 · 역설 · 논리적 오류(논리적 오류/형식적 오류)
<colcolor=#000,#fff> 비표준 논리 직관 논리 · 양상논리 · 초일관 논리 · 다치논리(퍼지논리) · 선형논리 · 비단조 논리
메타 논리 집합론 · 완전성 정리 · 불완전성 정리
비형식 논리 딜레마(흑백논리)
비형식적 오류 귀납적 오류 · 심리적 오류 · 언어적 오류 · 자료적 오류 · 양비론 · 진영논리 · 편견 및 고정관념 · 궤변
분야 수리철학 · 수리논리학
철학 관련 정보 · 논리학 관련 정보 · 수학 관련 정보 · 수리논리학 둘러보기
}}}}}}}}} ||

수학기초론
Foundations of Mathematics
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)"
{{{#!folding [ 펼치기 · 접기 ]
{{{#!wiki style="margin: -5px -1px -11px"
다루는 대상과 주요 토픽
수리논리학 논리 · 논증{귀납논증 · 연역논증 · 귀추 · 유추} · 공리 및 공준 · 증명{자동정리증명 · 귀류법 · 수학적 귀납법 · 반증 · 더블 카운팅 · PWW} · 논리함수 · 논리 연산 · 잘 정의됨 · 조건문(조각적 정의) · 명제 논리(명제 · 아이버슨 괄호 · · · 대우) · 양상논리 · 술어 논리(존재성과 유일성) · 형식문법 · 유형 이론 · 모형 이론
집합론 집합(원소 · 공집합 · 집합족 · 곱집합 · 멱집합) · 관계(동치관계 · 순서 관계) · 순서쌍(튜플) · 서수(하세 다이어그램 · 큰 가산서수) · 수 체계 · ZFC(선택공리) · 기수(초한기수) · 절대적 무한 · 모임
범주론 범주 · 함자 · 수반 · 자연 변환 · 모나드 · 쌍대성
계산가능성 이론 계산 · 오토마타 · 튜링 기계 · 바쁜 비버 · 정지 문제 · 재귀함수
정리
드모르간 법칙 · 대각선 논법 · 러셀의 역설 · 거짓말쟁이의 역설 · 뢰벤하임-스콜렘 정리 · 슈뢰더-베른슈타인 정리 · 집합-부분합 정리 · 퍼스의 항진명제 · 굿스타인 정리 · 완전성 정리 · 불완전성 정리(괴델 부호화) · 힐베르트의 호텔 · 연속체 가설 · 퍼지 논리
기타
예비사항(약어 및 기호) · 추상화 · 벤 다이어그램 · 수학철학
틀:논리학 · 틀:이산수학 · 틀:이론 컴퓨터 과학 · 철학 관련 정보 · 논리학 관련 정보 · 수학 관련 정보 }}}}}}}}}



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)3.10. 관련 문서
4. 고차 논리

1. 1차 술어논리

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

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

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

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

양화사는 특정 술어를 만족하는 대상이 주어진 논의 영역(혹은 논의 세계, domain; universe of discourse)에 얼마나 존재하는지를 알려주는 의미를 갖는다. 양화사에는 존재양화사와 보편양화사 두 종류가 있다.
일반적으로 존재양화사(∃) 문장은 일상 언어에서의 '어떤 P는 Q다', 'P인 것이 있다', 보편양화사(∀)는 '임의의 P는 Q다', '모든 것은 P다'에 대응하는 것으로 여겨진다. 하지만 임의의 술어 P에 대하여 일상언어 문장인 '만약 모든 [math(P)]가 [math(Q)]이면 어떤 [math(P)]는 [math(Q)]이다'라는 문장은 논리적으로 타당해보이지만, [math((\forall x)(Px \rightarrow Qx) → (\exists x)(Px\;\&\;Qx))]는 논리적으로 타당하지 않다. 즉 양화사 또한 일상 언어에서의 직관과 괴리가 있는데, 직관적으로 설명하면 "모든 대한민국의 왕은 대한민국의 국가원수이다"라는 문장은 "대한민국의 왕이자 대한민국의 국가원수인 사람이 존재한다"를 유도하지 못하는 것과 같다. 보다 자세한 사항은 존재함축 참조.

명제논리에서 사용되던 연결사들은 양화논리에서 역시 거의 동일한 의미로 사용된다. 양화논리에서 추가적으로 도입되는 연결사로는 등호 [math(=)]가 있다. 등호는 대상을 가리키는 두 기호가 논의 영역 내의 동일한 대상을 가리키는 것을 나타내는데 쓰인다.
또한, 술어들 중에는 둘 이상의 대상을 필요로 하는 술어도 있다. 이러한 술어를 n항 술어(n-ary predicate)라고 하며, n항 술어는 공집합이 아니라면 n중쌍(n-tuple)의 집합, 즉 n항 관계를 할당 받는다. 이를테면 'x가 y를 사랑한다'는 'Lxy'와 같이 쓸 수 있다. 원칙적으로는 술어 뒤에 위첨자로 n을 표기해줘야 하지만, 뒤에 이어지는 변항의 수로 n을 짐작할 수 있기 때문에 생략하기도 한다.

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

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

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

1차 술어논리에서 한 문장 [math(\phi)]가 주어졌을 때, [math(\phi)]를 해석한다는 것은 다음과 같은 과정을 거치는 것이다.
  1. 공집합이 아닌 논의 영역을 명시한다.
  2. 개체 상항에 논의 영역에 속한 개체를 할당한다.
  3. 1항 술어에 개체들의 집합을 할당한다. [math(n)]항 술어에는 [math(n)]항 관계를 할당한다.

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

예시를 들면 다음과 같다.

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

이상과 같은 해석 하에서, 문장 [math(Fb)]는 거짓이다. 문장 [math(Fa)]는 참이다. 문장 [math((\forall x)Fx)]는 거짓이다. 문장 [math((\exist x)Fx)]는 참이다.

양화논리에서 참의 의미는 귀납적으로 정의된다. 쉽게 이해할 수 있도록 정의하자면 다음과 같다.이상과 같이 술어 문장의 진리값을 할당하고 나면, 각각의 술어 문장을 명제논리 체계에서와 같은 방식으로 다룰 수 있다.

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

위와 같은 참의 정의에 따라, 양화논리에서 타당성, 귀결, 일관성이 다음과 같이 정의된다.

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

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

이하의 규칙들 중에서 [math(\rm EG)], [math(\rm ES)], [math(\rm Q)]는 단축규칙으로 분류되며 다른 추론 규칙들로부터 연역될 수 있다. 이하의 모든 경우에서 [math(\phi)]와 [math(\psi)]는 임의의 식을, [math(\alpha)]는 변항을, [math(\beta)]는 개체 상항을 의미한다고 하자. 그리고 [math(\psi\alpha/\beta)]를 변항 [math(\alpha)]대신 개체 상항 [math(\beta)]를 대입한 식이라고 하자.

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

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

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

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

3.3. 조건문화(Conditionalization; C)

[math({\rm C}:\psi\vdash(\phi\to\psi))]

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

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

[math({\rm US}:(\forall\alpha)\phi\vdash\phi\alpha/\beta)]
논의세계의 모든 원소가 어떤 문장을 만족한다면, 특정한 대입례 하나가 그 문장을 만족한다는 것은 타당하다.
한국어 추론 예시.
모든 것은 물리적인 것이다.
태양은 물리적인 것이다.

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

보편 일반화에는 '[\math(\beta)]가 [\math(\phi)]에도 [\math(\phi\alpha/\beta)]가 나타나는 항의 어떤 전제에도 나타나지 않을 때'라는 제한 조건이 붙는다.
해당 제한 조건 하에서,
[\math({\rm UG}:\phi\alpha/\beta\vdash(\forall α)\phi)]

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

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

[\math({\rm EG}:\phi\alpha/\beta\vdash(\exist\alpha)\phi)]

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

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

존재 예화에는 '[\math(\beta)]가 [\math(\phi)]에도 [\math(\psi)]에도 [\math(\psi\alpha/\beta)]를 제외한 [\math(\phi)]의 전제에도 나타나지 않을 때'라는 제한 조건이 붙는다.
해당 제한 조건 하에서,
[\math({\rm ES}:(\exist\alpha)\psi,\,\psi\alpha/\beta\Rightarrow\phi\vdash\phi)]

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

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

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

[\math({\rm E}:\neg(\forall\alpha)\neg\phi\vdash(\exist\alpha)\phi,\,(\exist\alpha)\phi\vdash\neg(\forall\alpha)\neg\phi)]
한국어 추론 예시.
사람인 것이 있다.
모든 것이 사람이 아닌 것은 아니다.

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

[\math({\rm Q}:(\forall\alpha)\neg\phi\vdash\neg(\exist\alpha)\phi,\,\neg(\exist\alpha)\phi\vdash(\forall\alpha)\neg\phi)]
한국어 추론 예시.
비물질적인 것은 존재하지 않는다
모든 것은 비물질적인 것이 아니다.

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

이를 풀어서 설명하면 다음과 같다.

3.10. 관련 문서

4. 고차 논리

고차 논리(higher-order logic)에서는 술어를 양화할 수 있다. 즉 1차 술어 논리에서는 논의영역 내의 대상들을 두고 "모든 대상은 이러하다", "어떤 대상은 저러하다"라고 밖에 표현할 수 없는 반면, 2차 논리 이상의 고차 논리에서는 "모든 속성은 이러하다", "어떤 속성은 저러하다"라는 명제 또한 표현할 수 있다. 예컨대 고차 논리에서는 다음과 같은 명제를 서술할 수 있다:

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

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



파일:CC-white.svg 이 문서의 내용 중 전체 또는 일부는
문서의 r224
, 4번 문단
에서 가져왔습니다. 이전 역사 보러 가기
파일:CC-white.svg 이 문서의 내용 중 전체 또는 일부는 다른 문서에서 가져왔습니다.
[ 펼치기 · 접기 ]
문서의 r224 (이전 역사)
문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)


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