건전성

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 정의
3. 건전한 논증
- 3.1. 건전한 논증의 예 (삼단논법)
- 3.2. 타당하지만 건전하지 않은 논증의 예
4. 수학적 논리에서의 사용
- 4.1. 논리 체계
- 4.2. 건전성의 종류
5. 건전성 정리의 증명
6. 완전성과의 관계
참조

1. 개요

건전성은 형식 체계에서 구문론적 귀결 관계가 의미론적 귀결 관계를 함축하는 성질을 의미한다. 건전한 논증은 타당하며 모든 전제가 참인 논증을 뜻하며, 수학적 논리에서는 체계 내에서 증명 가능한 모든 명제가 체계의 의미론에 대해 논리적으로 유효할 때 건전성을 갖는다고 정의한다. 건전성은 약건전성, 강건전성, 산술적 건전성으로 구분되며, 건전성의 역은 완전성이다. 건전성 정리는 완전성 정리보다 증명이 간단하며, 괴델의 불완전성 정리는 건전한 연역 체계가 완전할 수 없음을 보여준다.

더 읽어볼만한 페이지

연역 - 마음
마음은 의식, 사고, 지각, 감정, 동기, 행동, 기억, 학습 등을 포괄하는 심리적 현상과 능력의 총체이며, 다양한 분야에서 연구되고 인간 삶의 중추적인 역할을 한다.
연역 - 통계적 추론
통계적 추론은 표본 데이터를 통해 모집단에 대한 결론을 도출하는 방법론으로, 추정과 가설 검정을 포함하며, 다양한 접근 방식과 통계 모델을 기반으로 여러 분야에서 활용된다.
증명 이론 - 힐베르트 프로그램
힐베르트 프로그램은 20세기 초 수학의 기초를 형식 체계로 구축하고 무모순성과 완전성을 증명하려 했으나, 괴델의 불완전성 정리에 의해 원래 목표 달성이 불가능해졌고 수정된 형태로 연구가 지속되고 있다.
증명 이론 - 괴델의 불완전성 정리
괴델의 불완전성 정리는 산술을 표현할 수 있는 무모순적 공리계는 그 안에서 증명하거나 반증할 수 없는 명제가 존재하며, 특히 체계 스스로의 무모순성을 증명할 수 없다는 수학적 논리 분야의 핵심 정리이다.
논증 - 삼단논법
삼단논법은 아리스토텔레스가 제시한 논리적 추론 방법으로, 대개념, 소개념, 매개념을 통해 결론을 이끌어내며, 명제의 양과 질, 중명사의 위치에 따라 다양한 형식이 존재한다.
논증 - 이유
이유는 철학에서 현상이나 주장을 설명하고 정당화하는 근거로, 규범적 이유(상황 지지), 설명적 이유(현상 원인), 동기 부여 이유(행동 설명)로 나뉘며, 인식적 이유(믿음 근거)와 실천적 이유(행동 근거)로 구분되고 논증에서는 증거 및 설명을 제공한다.

건전성
개요
분야	논리학, 수학, 컴퓨터 과학
관련 개념	완전성, 타당성
논리학에서
정의	논리 체계의 추론 규칙이 참인 전제로부터 항상 참인 결론을 도출하는 성질
설명	어떤 논리 체계가 건전하다는 것은 그 체계에서 증명 가능한 모든 논리식이 그 체계의 의미론에서 항상 참임을 의미함.
수학에서
의미	증명된 모든 정리가 실제로 참임을 의미
중요성	건전성은 수학적 체계의 신뢰성을 보장하는 필수적인 요소
컴퓨터 과학에서
관련 분야	형식 검증, 프로그램 검증
의미	프로그램이 명세된 대로 정확하게 동작함을 의미
예시	컴파일러가 건전하다면, 컴파일러가 생성한 코드는 원래 프로그램의 의미를 보존함.

2. 정의

형식 체계에서 구문론적 귀결 관계 $\vdash$ 와 의미론적 귀결 관계 $\vDash$ 가 있을 때, 임의의 논리식들의 집합 G와 논리식 p에 대하여 다음이 항상 성립하면 해당 형식 체계는 '''건전'''(sound^영어)하다고 한다.^[5]

$G \vdash p$ 이면, $G \vDash p$ 이다.

연역 추론에서 건전한 논증은 타당하며 모든 전제가 참인 논증이다(결과적으로 결론도 참이다). 논증이 타당하다는 것은 전제가 참이라고 가정할 때 결론이 ''반드시'' 참이어야 함을 의미한다. 건전한 논증의 예시는 다음과 같은 잘 알려진 삼단논법이다.

: ''(전제)''

: 모든 사람은 죽는다.

: 소크라테스는 사람이다.

: ''(결론)''

: 그러므로 소크라테스는 죽는다.

결론의 논리적 필연성 때문에 이 논증은 타당하며, 논증이 타당하고 그 전제가 참이기 때문에 이 논증은 건전하다.

하지만 논증은 건전하지 않아도 타당할 수 있다. 예를 들어,

: 모든 새는 날 수 있다.

: 펭귄은 새이다.

: 그러므로 펭귄은 날 수 있다.

이 논증은 전제가 참이라고 가정할 때 결론이 ''반드시'' 참이므로 타당하다. 그러나 첫 번째 전제는 거짓이다. 모든 새가 날 수 있는 것은 아니다(예를 들어 타조). 논증이 건전하려면 논증이 타당해야 ''하고'' 그 전제가 참이어야 한다.

3. 건전한 논증

연역 추론에서 건전한 논증은 타당하며 모든 전제가 참인 논증이다(결과적으로 결론도 참이다). 논증이 타당하다는 것은 전제가 참이라고 가정할 때 결론이 ''반드시'' 참이어야 함을 의미한다. 논증이 건전하려면 논증이 타당해야 ''하고'' 그 전제가 참이어야 한다.

존 레몬과 같은 일부 저자는 "건전성"이라는 용어를 현재 "타당성"이 의미하는 것과 동의어로 사용하기도 했으나, 오늘날 이러한 용어의 구분은 널리 퍼져 있다.

타당하지만 건전하지 않은 논증의 예시로는 대전제가 거짓인 경우가 있다.^[1]

3. 1. 건전한 논증의 예 (삼단논법)

다음은 건전한 삼단논법의 예시이다.^[1]

(전제) 모든 사람은 죽는다.^[1]
(전제) 소크라테스는 사람이다.^[1]
(결론) 그러므로 소크라테스는 죽는다.^[1]

이 논증은 결론의 논리적 필연성 때문에 타당하며, 전제가 참이므로 건전하다.^[1]

3. 2. 타당하지만 건전하지 않은 논증의 예

: 모든 새는 날 수 있다.

: 펭귄은 새이다.

: 그러므로 펭귄은 날 수 있다.

이 논증은 전제가 참이라고 가정할 때 결론이 ''반드시'' 참이므로 타당하다. 그러나 첫 번째 전제는 거짓이다. 모든 새가 날 수 있는 것은 아니다(예를 들어 타조). 논증이 건전하려면 논증이 타당해야 ''하고'' 그 전제가 참이어야 한다.

4. 수학적 논리에서의 사용

수학적 논리에서 논리 체계는 체계 내에서 증명될 수 있는 모든 명제가 체계의 의미론에 대해 논리적으로 유효한 경우 건전성 속성을 갖는다. 대부분의 경우, 이는 규칙이 진리를 보존하는 속성을 갖는 것으로 귀결된다.^[4] 건전성의 역은 완전성으로 알려져 있다.

건전성은 수학적 논리에서 가장 기본적인 속성 중 하나이며, 논리 체계가 바람직한 것으로 간주되는 주된 이유를 제공한다. 완전성은 모든 유효성(진리)이 증명 가능하다는 것을 의미하며, 건전성과 완전성이 함께 있으면 모든 유효성만이 증명 가능하다는 것을 의미한다.

건전성의 증명은 대부분 간단하다. 예를 들어, 공리적 체계에서 건전성을 증명하는 것은 공리의 유효성을 확인하고, 추론 규칙이 유효성(또는 더 약한 속성인 진리)을 보존하는지 확인하는 것으로 충분하다. 체계가 힐베르트식 연역 체계를 허용하는 경우, 공리의 유효성과 전건 긍정 (그리고 때로는 치환)과 같은 하나의 추론 규칙만 확인하면 된다.

건전성에는 약건전성과 강건전성의 두 가지 주요 유형이 있으며, 약건전성은 강건전성의 제한된 형태이다. (자세한 내용은 건전성의 종류 하위 섹션을 참고)

4. 1. 논리 체계

형식 체계에서 구문론적 귀결 관계

\vdash

와 의미론적 귀결 관계

\vDash

가 있을 때, 임의의 논리식들의 집합 G와 논리식 p에 대하여 다음이 항상 성립하면 그 형식 체계는 '''건전'''(sound^영어)하다고 한다.^[5]

$G \vdash p$ 이면, $G \vDash p$ 이다.

잘 정의된 명제 논리 체계에서는 건전성이 성립해야 한다. 흔히 논리 체계에서는 건전성 정리(soundness theorem)가 간단한 귀납법에 의해 이루어지므로 완전성 정리의 증명보다 훨씬 간략하다. "모든 논리적 공리는 항진"이라는 것과 "모든 논리적 추론규칙(보통 전건 긍정을 포함)은 타당성을 가진다"는 보조정리를 바탕으로 증명은 쉽게 끝난다.^[5] 이 보조정리는 공리와 추론규칙마다 확인해보는 것으로 간단히 얻을 수 있으며, 이를 전제로 증명은 다음과 같이 완성된다.

(명제의 구성법과 증명관계가 귀납적으로 잘 정의되어 있다는 가정 하에)

G \vdash p

인 경우 p는 다음의 세 가지 경우 중 하나이다.

# 논리적 공리이거나,

# 전제 G의 원소이거나,

# 공리와 전제에 추론규칙들을 적용하여 나온 명제.

# p가 논리적 공리일 경우 위의 보조정리와 타당성의 정의에 의해 곧바로

G \vDash p

을 얻는다.

# p가 G의 원소인 경우에도 곧바로

G \vDash p

을 얻는다.

# 공리나 G의 원소에 추론규칙을 0번 사용하여 증명된 명제는 위의 2가지 경우에 해당하여 의미론적으로 참이다. 이제 추론규칙을 n번 적용하여 나온 명제들

p_1, p_2, ..., p_i

가 의미론적으로도 귀결인 것이 보여졌다고 가정하고 그러한 명제들에 임의의 추론규칙을 적용하여 나온 명제 q를 가정하면 보조정리에 의해 항진성이 보존되므로 q, 즉 추론규칙을 n+1번 적용하여 나온 임의의 명제도 항상 의미론적으로 참이다.

그렇다면 귀납법에 의해 모든 증명되는 명제는 의미론적으로 참이다.

잘 정의된 1차 논리에 대해서도 마찬가지로 양화사를 포함하는 공리나 추론규칙이 타당하다는 것만 추가로 보이면 비슷한 방식의 증명이 이루어질 수 있다. 완전성도 성립할 경우 이 논리체계에서 구문론적 참과 의미론적 참은 일치한다고 간주할 수 있다.

수학적 논리에서, 논리 체계는 체계 내에서 증명될 수 있는 모든 명제가 체계의 의미론에 대해 논리적으로 유효한 경우 건전성 속성을 갖는다. 대부분의 경우, 이것은 규칙이 ''진리''를 보존하는 속성을 갖는 것으로 귀결된다.^[4] 건전성의 역은 완전성으로 알려져 있다.

구문적 함의

\vdash

와 의미적 함의

\models

를 가진 논리 체계는 언어의 모든 시퀀스

A_1, A_2, ..., A_n

에 대해, 만약

A_1, A_2, ..., A_n\vdash C

이면,

A_1, A_2, ..., A_n\models C

일 경우 '''건전'''하다고 한다. 즉, 체계의 모든 정리가 항진명제일 때 체계는 건전하다.

건전성은 수학적 논리의 가장 기본적인 속성 중 하나이다. 건전성 속성은 논리 체계를 바람직한 것으로 간주하는 최초의 이유를 제공한다. 완전성 속성은 모든 유효성(진실)이 증명 가능하다는 것을 의미한다. 이 둘은 함께 모든 유효성만이 증명 가능하다는 것을 의미한다.

건전성의 대부분의 증명은 사소하다. 예를 들어, 공리적 체계에서 건전성 증명은 공리의 유효성을 확인하고 추론 규칙이 유효성(또는 더 약한 속성인 진리)을 보존하는 것으로 귀결된다. 체계가 힐베르트식 연역 체계를 허용하는 경우, 공리의 유효성과 하나의 추론 규칙, 즉 전건 긍정 (그리고 때로는 치환)을 확인하기만 하면 된다.

건전성 속성은 약건전성과 강건전성, 두 가지 주요 유형으로 나뉘며, 전자는 후자의 제한된 형태이다.

4. 2. 건전성의 종류

수학적 논리에서 논리 체계가 건전하다는 것은, 그 체계 내에서 증명될 수 있는 모든 명제가 체계의 의미론에 대해 논리적으로 유효하다는 것을 의미한다. 대부분의 경우, 이것은 체계의 규칙이 진리를 보존한다는 것을 의미한다.^[4] 건전성의 역은 완전성이다.

건전성은 약건전성과 강건전성 두 가지로 나뉜다.

'''약건전성''': 연역 체계에서 증명 가능한 모든 문장이 해당 체계의 의미론적 이론의 모든 해석 또는 구조에서 참인 성질이다.
'''강건전성''': 추론 체계에서 유도될 수 있는 모든 문장이 해당 문장 집합의 모든 구성원을 참으로 만드는 모든 모델에서 참인 성질이다.

4. 2. 1. 약한 건전성

연역 체계의 약한 건전성은 해당 연역 체계에서 증명 가능한 모든 문장이 해당 체계가 기반을 둔 언어의 의미론적 이론의 모든 해석 또는 구조에서도 참이라는 성질을 말한다.^[4] 기호로 나타내면, ''S''는 연역 체계, ''L''은 의미론적 이론과 함께 언어, ''P''는 ''L''의 문장이라고 할 때, 만약 ⊢_''S'' ''P''이면, ⊨_''L'' ''P''도 성립한다.

4. 2. 2. 강한 건전성

추론 체계의 강한 건전성은 그 추론 체계가 기반하고 있는 언어의 모든 문장 ''P''가 그 언어의 문장 집합 Γ에서 유도될 수 있다면, Γ의 모든 구성원을 참으로 만드는 모든 모델이 ''P''도 참으로 만든다는 의미에서, 또한 해당 집합의 논리적 결과라는 성질을 의미한다. 기호로 나타내면 Γ가 ''L''의 문장 집합일 때 다음과 같다.

: 만약 Γ ⊢_''S'' ''P''이면, 또한 Γ ⊨_''L'' ''P''이다.

강한 건전성의 명제에서 Γ가 비어 있을 때, 약한 건전성의 명제를 얻는다.^[4]

4. 2. 3. 산술적 건전성

''T''가 자연수로 해석될 수 있는 담론의 대상을 가진 이론일 때, ''T''의 모든 정리가 표준 수학적 정수에 대해 실제로 참이면 ''T''는 ''산술적으로 건전하다''라고 말한다.^[4] 자세한 내용은 ω-무모순 이론을 참고하면 된다.

5. 건전성 정리의 증명

잘 정의된 명제 논리 체계에서는 건전성이 성립해야 한다. 흔히 논리 체계에서는 건전성 정리(soundness theorem)가 간단한 귀납법에 의해 이루어지므로 완전성 정리의 증명보다 훨씬 간략하다. "모든 논리적 공리는 항진"이라는 것과 "모든 논리적 추론규칙(보통 전건 긍정을 포함)은 타당성을 가진다"는 보조정리를 바탕으로 증명은 쉽게 끝난다.^[5] (명제의 구성법과 증명관계가 귀납적으로 잘 정의되어 있다는 가정 하에) $G \vdash p$ 인 경우 p는 다음의 세 가지 경우 중 하나이다. 논리적 공리이거나, 전제 G의 원소이거나, 공리와 전제에 추론규칙들을 적용하여 나온 명제이거나. 그렇다면 귀납법에 의해 모든 증명되는 명제는 의미론적으로 참이다. 잘 정의된 1차 논리에 대해서도 마찬가지로 양화사를 포함하는 공리나 추론규칙이 타당하다는 것만 추가로 보이면 비슷한 방식의 증명이 이루어질 수 있다.

6. 완전성과의 관계

논리적 건전성의 역은 의미적 완전성 속성이다. 어떤 연역 체계에서, 문장 집합 Γ의 의미적 결과인 모든 문장 ''P''가 해당 집합에서 연역 체계를 통해 유도될 수 있다면, 그 연역 체계는 강하게 완전하다고 한다. 이를 기호로 나타내면 다음과 같다. Γ ⊨ ''P'' 이면 Γ ⊢ ''P'' 이다.^[4] 일차 논리의 완전성은 괴델의 완전성 정리에 의해 명시적으로 확립되었지만, 주요 결과 중 일부는 스콜렘의 이전 연구에 이미 포함되어 있었다.

비공식적으로, 연역 체계의 건전성 정리는 증명 가능한 모든 문장이 참임을 나타낸다. 반면, 완전성은 모든 참인 문장이 증명 가능하다는 것을 의미한다.

괴델의 불완전성 정리는 일정량의 산술을 수행하기에 충분한 언어의 경우, 해당 언어의 기호의 의도된 해석과 관련하여 완전하고 일관되며 효과적인 연역 체계가 존재할 수 없음을 보여준다.

참조

_[1] 웹사이트 Types of proof system http://www.logicmatt[...] 2010
_[2] 서적 Introduction to logic 2017-01-06
_[3] 서적 Beginning logic Chapman & Hall/CRC 1998
_[4] 서적 A Real Mind: The Life and Work of Axel Hägerström https://books.google[...] Springer Science & Business Media 2009-09-18
_[5] 서적 A mathematical introduction to logic Academic Press(Elsevier) 2002

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com