퍼스의 항진명제

덤프버전 :

수학기초론
Foundations of Mathematics


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





1. 개요
2. 증명
2.1. 전제는 없다(1번 라인)
2.2. 조건문의 조건을 작성한다(2번 라인)
2.3. 귀류법을 사용해보자(3-13번 라인)
2.3.1. 대우명제를 사용하자(4-7번 라인)
2.3.2. [math(p)]는 아무래도 좋게 되었다(8-11번 라인)
2.3.3. 그러나 그러면 모순(12번 라인)
2.4. 그렇기에 [math(p)](13번 라인)
2.5. 조건명제의 증명이 끝났다(14번 라인)
3. 진리표를 이용한 증명
4. 관련 문서


1. 개요[편집]


퍼스(Peirce)의 항진명제는, 다음과 같은 항진명제이다.

  • [math(((p \rightarrow q) \rightarrow p) \rightarrow p)]

기호논리학의 선구자 중 한 명인 찰스 샌더스 퍼스의 이름을 따서 만들어졌다.[1]

2. 증명[편집]


이게 항진이라는 것을, 다음과 같이 증명할 수 있다.

파일:퍼스의 토톨로지 증명.jpg

2.1. 전제는 없다(1번 라인)[편집]


항진명제를 증명함에 있어서 중요한 것은, 이 명제가 어떤 경우에서라도 참으로 도출되어야 하는 것이다. 즉, 어떤 전제를 작성하거나 작성하지 않거나에 상관없이, 항진명제라고 하는 것에 대해서는 그 증명이 가능해야 한다는 것이다. 제시한 증명에서는 1번 라인[2]의 우측에 적힌 hyp[3]로 지정되어 있는 부분이 비어있다. 즉, 없다. 그런 상태에서 퍼스의 항진명제라 하는 조건명제를 증명하는 것이다.

2.2. 조건문의 조건을 작성한다(2번 라인)[편집]


퍼스의 항진명제를 구성하는 것은, 결론적으로 [math(\rightarrow)]로 연결되어 있는 부분이다. 이를 사이에 두고, 화살표의 왼쪽에는 [math((p \rightarrow q)\rightarrow p)]가, 오른쪽에는 [math(p)]가 나타나고 있다. 즉, 이를 증명하기 위해서 조건인 것을 2번에서 가정[4]을 노드 2에 세우고, 그 안에서 결론으로 [math(p)]를 얻으려는 과정을 시작한다.

2.3. 귀류법을 사용해보자(3-13번 라인)[편집]


3번 라인에서는 다시 [math(p)]가 거짓이라고 가정해 본다. 그리고 12번에서 결국 모순이 되는 것을 보임으로써, 결국 [math(p)]가 거짓이 아니어야 함을 13번 라인에서 제시한다. 그 과정에서 다음과 같은 시도들을 하게 된다.

2.3.1. 대우명제를 사용하자(4-7번 라인)[편집]


2번 라인의 조건명제에서 결론인 부분을 3번에서 부정하였다. 즉, 조건인 부분이 부정되어 나오는 것이 당연하므로, 7번에서는 2번 명제의 조건 부분이 부정되어 있다.

2.3.2. [math(p)]는 아무래도 좋게 되었다(8-11번 라인)[편집]


8번 라인에서 [math(p)]가 참이라고 다시 가정해 본다. 그러면 조건인 [math(p)]가 어차피 거짓인 명제이므로, 이를 조건으로 갖는 조건명제는 어떤 것이든지 참이다. 즉, 11번 라인에서 [math(p \rightarrow q)]가 참이라고 해도 할 말 없다는 것.

2.3.3. 그러나 그러면 모순(12번 라인)[편집]


11번 라인에서 [math(p \rightarrow q)]가 참이라고 내놓긴 했지만, 이건 7번에서 이미 거짓이라고 나와 있는 부분이다. 즉, 모순일 수 밖에 없으므로, 12번 라인에 모순이라고 표시해 둔다.

2.4. 그렇기에 [math(p)](13번 라인)[편집]


3번 라인의 가정에서부터 12번 라인의 모순이 도출되었으므로, 3번 라인의 가정은 거짓이어야 한다. 이는 [math(p)]의 거짓이 거짓이라고 하는 것이므로, 13번 라인에서는 [math(p)]를 참이라고 작성한다.

2.5. 조건명제의 증명이 끝났다(14번 라인)[편집]


2번 라인의 조건, [math((p \rightarrow q)\rightarrow p)]으로부터 13번 라인의 결론, [math(p)]로 도착하였다. 즉, 2번 라인의 조건은 13번 라인의 결론을 함의하고 있다. 이를 하나의 조건명제로 표현하여, 14번 라인에 다음과 같이 작성한다.

  • [math(((p \rightarrow q ) \rightarrow p ) \rightarrow p )]

3. 진리표를 이용한 증명[편집]


진리표를 이용하면 [math(p\rightarrow q)]는 [math(\neg p\vee q)]와 동등하다. 따라서 [math(((p \rightarrow q ) \rightarrow p ) \rightarrow p )]를 [math(\neg \left(\neg \left(\neg p\vee q\right)\vee p\right)\vee p)]로 변형하면 드 모르간의 법칙에 따라 [math(\left(\left(\neg p\vee q\right)\wedge \neg p\right)\vee p)]가 되고, 이는 다시 [math(\neg p\vee p)]가 되어 항진임을 알 수 있다.

4. 관련 문서[편집]



파일:크리에이티브 커먼즈 라이선스__CC.png 이 문서의 내용 중 전체 또는 일부는 2023-12-23 17:03:57에 나무위키 퍼스의 항진명제 문서에서 가져왔습니다.

[1] 퍼스 사후 하버드 대학에서 출판한 그의 저작을 모은 퍼스의 전집(Collected Papers of Charles Sanders Peirce)의 Volume 3에 퍼스가 직접 증명한 내용이 실려있다.[2] 세로줄의 단계를 노드, 가로줄의 순서를 라인으로 부른다.[3] hypothesis의 준말.[4] 우측의 hyp 표시로부터 확인한다.