여기서는 두 주장 사이의 관계를 정의합니다. 언제나 거짓인 하나의 논리식을 가리키는 ‘모순식’과 구별합니다. 여섯 전등이 존재할 때 ‘모두 켜짐’과 ‘모두 꺼짐’은 함께 거짓일 수 있으므로 모순 관계가 아닙니다. 대당사각형의 다른 관계는 대상의 존재 조건도 따로 확인합니다.
함께 찾는 표현: contradictories · contradictory propositions · 모순 대당 · 모순대당 · 모순 · A와 ¬A
양화사 앞의 부정을 안쪽으로 옮기면 ∀와 ∃가 서로 바뀝니다. 이 사전은 ≡를 논리적 동치를 나타내는 설명용 표시로 사용합니다. 참고 교재의 ‘양화사의 전환’은 같은 관계를 증명 규칙 CQ로도 제시합니다. 여기서는 법칙의 의미를 먼저 설명하며, 모든 논리 체계에 그대로 적용한다고 가정하지 않습니다.
함께 찾는 표현: 양화사 부정 · 전칭 부정 · 존재 부정 · conversion of quantifiers · ¬∀ · ¬∃ · ∃¬ · ∀¬
장별 개념 연결, 영문 색인, 기호·규칙·비교 자료와 참고문헌을 원고의 순서대로 함께 제공합니다. 도식 안의 문구는 글 형태로 표시합니다.
2권 · 논리학 개념어 100: 기초편
이 책을 읽는 법
한 페이지에 하나의 개념만 둔다
각 개념은 한 문장 정의, 왜 필요한가, 예시, 구별 포인트, 함께 보기, 생각해
보기의 순서로 한 페이지 안에서 완결한다.
설명이 긴 개념도 핵심을 먼저 보여 주고, 도식은 개념 사이의 관계를 한눈에
파악하도록 돕는다.
다음 개념은 항상 새 페이지에서 시작한다. 원하는 개념을 사전처럼 찾아 읽을
수도 있고 처음부터 교재처럼 읽을 수도 있다.
정의 → 이유 → 예시 → 구별
개념의 뜻을 읽고, 예시와 도식을 살핀 뒤
마지막 질문에 자신의 말로 답해 보자.
프롤로그
논리학을 배우기 전에, 논리학의 말을 배운다
논리학을 처음 배우는 사람은 기호보다 용어에서 먼저 어려움을 겪곤 한다.
명제와 문장은 무엇이 다른가? 타당하다는 말은 참이라는 뜻인가?
필요조건과 충분조건은 어느 방향으로 읽어야 하는가? 용어의 뜻을 분명히
알아야 기호와 증명도 이해할 수 있다.
이 책은 논리학의 기초 개념어 100개를 학습 순서에 따라 배치한다. 앞에서
익힌 개념을 바탕으로 다음 개념을 배울 수 있도록, 문장과 명제에서 시작해
논증의 구조, 추론의 종류, 논증 평가, 조건, 오류, 비판적 질문으로 이어진다.
각 용어가 무엇을 구분하기 위해 필요한지, 실제 글에서 어떤 역할을 하는지
알아보는 것이 이 책의 목표다.
01
1장
논리의 언어를 시작하다
생각과 말의 기본 단위를 구별하고, 논리학이 무엇을 연구하는지 이해한다.
001 논리 002 논리학
003 형식논리학 004 비형식논리학
005 사고 006 추론
007 판단 008 주장
009 명제 010 진리값
02
2장
문장과 의미를 가려 읽다
문장·진술·진리·의미를 구분하고, 논증을 읽는 데 필요한 언어의 뜻과
차이를 분명히 한다.
011 문장 012 진술
013 참 014 거짓
015 진리 016 의미
017 정의 018 사용-언급 구분
019 애매성 020 모호성
03
3장
논증의 뼈대를 찾다
전제와 결론을 찾고, 글에 드러나지 않은 전제와 결론까지 공정하게 복원한다.
021 논증 022 전제
023 결론 024 논거
025 근거 026 증거
027 전제 지시어 028 결론 지시어
029 암묵적 전제 030 암묵적 결론
04
4장
논증의 구조를 그리다
복잡한 글을 중간결론과 전제의 관계로 나누고, 논증 지도와 표준화로
구조를 시각화한다.
031 주결론 032 중간결론
033 독립 전제 034 결합 전제
035 연쇄 논증 036 수렴 논증
037 복합논증 038 논증 재구성
039 논증 표준화 040 논증 지도
05
5장
추론의 여러 길을 따라가다
연역·귀납·가추를 중심으로 서로 다른 추론 방식이 어떤 질문에
적합한지 비교한다.
041 연역 042 귀납
043 가추 044 유추
045 일반화 046 통계적 일반화
047 인과 추론 048 확률
049 설명 050 최선의 설명에 의한 추론
06
6장
좋은 논증을 판별하다
타당성, 건전성, 귀납적 강도와 수용가능성·관련성·충분성 기준으로
논증을 평가한다.
051 타당성 052 부당성
053 건전성 054 귀납적 강도
055 귀납적 설득력 056 수용가능성
057 관련성 058 충분성
059 일관성 060 반례
07
7장
조건과 관계를 정확하게 읽다
조건문의 방향, 필요·충분조건, 모순, 인과와 상관을 구별해 관계를
정확하게 해석한다.
061 조건 062 조건문
063 전건 064 후건
065 필요조건 066 충분조건
067 필요충분조건 068 모순
069 인과관계 070 상관관계
08
8장
잘못된 추론의 형태를 발견하다
형식과 증거의 결함에서 생기는 대표 오류를 구조적으로 살핀다.
071 오류 072 형식적 오류
073 비형식적 오류 074 후건긍정의 오류
075 전건부정의 오류 076 논점 선취
077 거짓 양자택일 078 성급한 일반화
079 거짓 원인의 오류 080 잘못된 유추
09
9장
말과 설득에서 오류를 찾아내다
사람·권위·대중·언어에 기대는 논증을 맥락 속에서 평가하고 오류
여부를 판단한다.
081 인신공격 082 허수아비 논증
083 권위에의 호소 084 대중에의 호소
085 무지에의 호소 086 논점 일탈
087 미끄러운 경사면 088 애매어의 오류
089 합성의 오류 090 분할의 오류
10
10장
논증을 비판하고 다시 세우다
쟁점과 입장을 분명히 하고, 반론·입증책임·논증 스킴과 비판적 질문으로
논증을 개선한다.
091 쟁점 092 입장
093 가정 094 반론
095 반박 096 입증책임
097 자비의 원칙 098 논증 스킴
099 비판적 질문 100 신뢰성
에필로그
백 개의 말이 하나의 사고 체계가 될 때
100개의 개념어를 익히고 나면 처음에는 비슷해 보였던 말들의 차이가
분명해진다. 문장과 명제, 주장과 논증, 참과 타당성, 필요조건과 충분조건을
구분하고, 긴 글에서도 전제와 결론, 중간결론, 암묵적 가정을 찾아낼 수 있다.
기초편에서 익힌 개념은 상대의 입장을 정확히 재구성하고, 관련 있는 근거를
요구하며, 자신의 주장에도 같은 기준을 적용하는 데 쓰인다.
다음 중급편에서는 이 용어들을 기호와 규칙으로 표현한다. 명제논리,
진리표, 자연연역, 일차논리를 배우며 “이 결론이 따라오는가?”라는 물음에
계산과 증명으로 답한다.
부록
논리학 개념어 100
한눈에 보기
개념어와 영어 표기
개념어 한눈에 보기 001 - 025
번호 개념어 영어 표기
001 논리 logic
002 논리학 logic
003 형식논리학 formal logic
004 비형식논리학 informal logic
005 사고 thinking
006 추론 inference
007 판단 judgment
008 주장 claim
009 명제 proposition
010 진리값 truth value
011 문장 sentence
012 진술 statement
013 참 true
014 거짓 false
015 진리 truth
016 의미 meaning
017 정의 definition
018 사용-언급 구분 use-mention distinction
019 애매성 ambiguity
020 모호성 vagueness
021 논증 argument
022 전제 premise
023 결론 conclusion
024 논거 reason
025 근거 ground
개념어 한눈에 보기 026 - 050
번호 개념어 영어 표기
026 증거 evidence
027 전제 지시어 premise indicator
028 결론 지시어 conclusion indicator
029 암묵적 전제 implicit premise
030 암묵적 결론 implicit conclusion
031 주결론 main conclusion
032 중간결론 intermediate conclusion
033 독립 전제 independent premise
034 결합 전제 linked premise
035 연쇄 논증 chain argument
036 수렴 논증 convergent argument
037 복합논증 complex argument
038 논증 재구성 argument reconstruction
039 논증 표준화 argument standardization
040 논증 지도 argument map
041 연역 deduction
042 귀납 induction
043 가추 abduction
044 유추 analogy
045 일반화 generalization
046 통계적 일반화 statistical generalization
047 인과 추론 causal inference
048 확률 probability
049 설명 explanation
050 최선의 설명에 의한 추론 inference to the best explanation
개념어 한눈에 보기 051 - 075
번호 개념어 영어 표기
051 타당성 validity
052 부당성 invalidity
053 건전성 soundness
054 귀납적 강도 inductive strength
055 귀납적 설득력 cogency
056 수용가능성 acceptability
057 관련성 relevance
058 충분성 sufficiency
059 일관성 consistency
060 반례 counterexample
061 조건 condition
062 조건문 conditional
063 전건 antecedent
064 후건 consequent
065 필요조건 necessary condition
066 충분조건 sufficient condition
067 필요충분조건 necessary and sufficient condition
068 모순 contradiction
069 인과관계 causal relation
070 상관관계 correlation
071 오류 fallacy
072 형식적 오류 formal fallacy
073 비형식적 오류 informal fallacy
074 후건긍정의 오류 affirming the consequent
075 전건부정의 오류 denying the antecedent
개념어 한눈에 보기 076 - 100
번호 개념어 영어 표기
076 논점 선취 begging the question
077 거짓 양자택일 false dilemma
078 성급한 일반화 hasty generalization
079 거짓 원인의 오류 false cause
080 잘못된 유추 weak analogy
081 인신공격 ad hominem
082 허수아비 논증 straw man
083 권위에의 호소 appeal to authority
084 대중에의 호소 appeal to popularity
085 무지에의 호소 appeal to ignorance
086 논점 일탈 red herring
087 미끄러운 경사면 slippery slope
088 애매어의 오류 equivocation
089 합성의 오류 fallacy of composition
090 분할의 오류 fallacy of division
091 쟁점 issue
092 입장 position
093 가정 assumption
094 반론 objection
095 반박 refutation
096 입증책임 burden of proof
097 자비의 원칙 principle of charity
098 논증 스킴 argument scheme
099 비판적 질문 critical question
100 신뢰성 credibility
참고자료
용어와 설명을 다듬을 때 참고한 자료
P. D. Magnus 외, 《forall x: Calgary: An Introduction to Formal Logic》,
Open Logic Project.
Stanford Encyclopedia of Philosophy, “Informal Logic”.
Trudy Govier, 《A Practical Study of Argument》.
Douglas Walton, Christopher Reed, Fabrizio Macagno,
《Argumentation Schemes》.
Patrick J. Hurley, 《A Concise Introduction to Logic》.
Irving M. Copi, Carl Cohen, Kenneth McMahon, 《Introduction to Logic》.
3권 · 논리학 개념어 100: 중급편
이 책을 읽는 법
한 페이지에 하나의 개념
각 개념은 한 문장 정의, 왜 필요한가, 예시, 구별 포인트, 함께 보기, 생각해
보기 순서로 읽는다. 정의의 뜻을 자기 말로 설명한 뒤 예시의 기호를 다시
문장으로 읽어 보자.
본문은 고전 명제논리와, 논의영역이 비어 있지 않은 표준 일차논리를 기준으로
한다. 전통논리를 다루는 마지막 장에서는 부류의 존재 가정을 따로 확인한다.
P와 Q는 앞부분에서 명제문자로 사용한다. A·B·C는 임의의 논리식을
가리키는 도식 문자다. 일차논리의 P(x)와 R(x,y)에서는 술어와 항을
구별한다.
기호의 읽는 법은 134쪽, 증명 규칙은 136~137쪽에 모았다. 함께 보기의
개념을 누르면 해당 쪽으로 이동한다. 생각해 보기의 답은 138쪽부터
확인한다.
정의 → 이유 → 예시 → 구별
기호를 읽고, 직접 계산하고, 근거를 말해 보자.
프롤로그
말로 읽은 논증을 기호와 규칙으로
기초편에서는 논증을 읽는 말을 익혔다. 전제와 결론을 찾고, 타당성과 참을
구별하며, 필요한 조건과 충분한 조건을 살폈다. 중급편에서는 그 관계를
기호로 옮기고 계산과 증명으로 확인한다.
기호가 늘어나면 처음에는 문장이 낯설게 보인다. 그러나 P → Q는 두 주장의
연결을, ∀x는 모든 대상을, ∃x는 하나 이상의 대상을 가리킨다. 기호마다
하는 일을 알면 긴 식도 작은 단위로 나누어 읽을 수 있다.
이 책의 앞부분은 형식화와 진리표를, 가운데는 자연연역과 일차논리를
다룬다. 뒤에서는 해석과 모형을 만들고 양화 추론을 증명한다. 마지막에는
정언명제와 삼단논법을 현대적인 표기와 함께 읽는다.
개념을 외우는 데서 멈추지 말고 직접 한 번씩 적용해 보자. 같은 식을 다른
표현으로 바꾸고, 작은 반례를 만들고, 증명 한 줄의 근거를 말해 보는 일이
논리의 언어를 익히는 연습이 된다.
01
1장
논리를 기호로 옮기다
말의 뜻을 정하고, 논리식의 구조와 읽는 순서를 익힌다.
001 형식화 002 형식언어
003 논리식 004 원자식
005 복합식 006 구문 규칙
007 주연결사 008 괄호와 결합 범위
009 해석 열쇠 010 대상언어와 메타언어
참고: [1] 4~8장
02
2장
연결사의 진리값을 계산하다
부정·연언·선언·조건문을 구별하고, 복합식의 진리값을 계산한다.
011 명제논리 012 명제변수
013 진리함수 014 부정
015 연언 016 선언
017 배타적 선언 018 실질조건문
019 쌍조건문 020 진리값 배정
참고: [1] 5장, 9~10장
03
3장
진리표로 관계를 판별하다
가능한 배정을 빠짐없이 살펴, 동치·귀결·충족가능성을 판별한다.
021 진리표 022 항진식
023 모순식 024 우연식
025 논리적 동치 026 논리적 귀결
027 충족가능성 028 동시 충족가능성
029 반례 배정 030 결정 절차
참고: [1] 11~15장
04
4장
규칙으로 증명을 구성하다
도입과 제거의 원리를 익히고, 근거를 밝히며 증명을 이어 간다.
031 형식적 증명 032 자연연역
033 도입 규칙 034 제거 규칙
035 연언 도입 036 연언 제거
037 선언 도입 038 선언 제거
039 조건문 제거 040 조건문 도입
참고: [1] 16~18장
05
5장
가정을 열고 닫다
부분증명의 범위를 관리하고, 부정과 조건문을 증명하는 법을 익힌다.
041 부분증명 042 가정의 해제
043 부정 도입 044 모순 도출
045 폭발 원리 046 이중부정 제거
047 귀류법 048 쌍조건문 도입
049 쌍조건문 제거 050 도출가능성
참고: [1] 17~21장
06
6장
대상과 성질을 표현하다
대상·술어·관계·함수를 구별하고, 일차논리의 기본 표현을 익힌다.
051 일차논리 052 논의영역
053 개체상수 054 개체변수
055 술어 056 관계술어
057 함수기호 058 항
059 자유변수 060 속박변수
참고: [1] 23장, 27장; [2] 항과 논리식
07
7장
양화사의 범위를 읽다
모든 대상과 어떤 대상을 구별하고, 양화사의 순서와 범위를 읽는다.
061 전칭양화사 062 존재양화사
063 양화사의 범위 064 열린 논리식
065 닫힌 논리식 066 전칭조건문
067 존재연언 068 양화사 부정
069 양화사 순서 070 변수 포획
참고: [1] 24~29장, 38장
08
8장
해석과 모형으로 확인하다
논리식에 의미를 부여하고, 작은 모형으로 주장과 관계를 점검한다.
071 해석 072 변수 할당
073 만족 관계 074 모형
075 반례 모형 076 동일성
077 유일 존재 078 반사성
079 대칭성 080 추이성
참고: [1] 30~35장
09
9장
양화논리를 증명하다
양화사와 동일성의 추론 규칙을 익히고, 이름과 대입 조건을 점검한다.
081 전칭 제거 082 전칭 도입
083 임의의 대상 084 존재 도입
085 존재 제거 086 새 이름 조건
087 대입 가능성 088 동일성 도입
089 동일성 제거 090 양화논리의 동치
참고: [1] 36~41장; [2] 대입
10
10장
전통논리를 형식으로 읽다
정언명제와 삼단논법을 분석하고, 대상의 존재를 가정하는지 확인한다.
091 정언명제 092 전칭긍정명제
093 전칭부정명제 094 특칭긍정명제
095 특칭부정명제 096 주연
097 대당사각형 098 정언삼단논법
099 중항 100 존재 함축
참고: [3] 제1권 1~7장; [4] 6~7장
에필로그
식을 읽는 힘에서 증명하는 힘으로
기호의 이름을 알게 되면 논리식이 읽힌다. 진리표를 만들면 가능한 경우를
빠짐없이 살필 수 있고, 추론 규칙을 익히면 전제에서 결론으로 가는 과정을
설명할 수 있다.
양화논리에서는 대상을 고르는 방식이 중요하다. 한 사례와 모든 사례, 각자
다른 상대와 모두에게 같은 상대, 임의의 대상과 특정 이름을 구별해야 한다.
식을 고칠 때도 자유변수와 속박변수의 관계를 살펴야 한다.
다음 고급편에서는 논리 체계 자체의 성질을 탐구한다. 어떤 결론이
증명되는지에 더하여, 체계가 얼마나 많은 진리를 포착하는지, 어떤 문제를
결정할 수 있는지, 해석과 증명의 관계가 무엇인지 질문한다.
중급편의 백 개 개념은 그 탐구의 도구가 된다. 계산과 증명을 함께 사용하고,
결론을 얻은 뒤에도 전제와 규칙의 조건을 다시 확인하는 습관을 이어 가자.
부록
논리학 개념어 100
한눈에 보기
개념어 · 기호 · 규칙 · 생각해 보기 길잡이
개념어와 영어 표기 130
기호 읽기 134
동치식 빠르게 확인하기 135
명제논리의 증명 규칙 136
양화 추론의 점검표 137
생각해 보기 길잡이 129
개념어 한눈에 보기
001 - 025
번호 개념어 영어 표기 쪽
001 형식화 formalization 9
002 형식언어 formal language 10
003 논리식 formula 11
004 원자식 atomic formula 12
005 복합식 compound formula 13
006 구문 규칙 formation rules 14
007 주연결사 main connective 15
008 괄호와 결합 범위 parentheses and scope 16
009 해석 열쇠 symbolization key 17
010 대상언어와 메타언어 object language and metalanguage 18
011 명제논리 propositional logic 21
012 명제변수 propositional variable 22
013 진리함수 truth function 23
014 부정 negation 24
015 연언 conjunction 25
016 선언 disjunction 26
017 배타적 선언 exclusive disjunction 27
018 실질조건문 material conditional 28
019 쌍조건문 biconditional 29
020 진리값 배정 valuation 30
021 진리표 truth table 33
022 항진식 tautology 34
023 모순식 contradiction 35
024 우연식 contingent formula 36
025 논리적 동치 logical equivalence 37
개념어 한눈에 보기
026 - 050
번호 개념어 영어 표기 쪽
026 논리적 귀결 logical consequence 38
027 충족가능성 satisfiability 39
028 동시 충족가능성 joint satisfiability 40
029 반례 배정 countervaluation 41
030 결정 절차 decision procedure 42
031 형식적 증명 formal proof 45
032 자연연역 natural deduction 46
033 도입 규칙 introduction rule 47
034 제거 규칙 elimination rule 48
035 연언 도입 conjunction introduction 49
036 연언 제거 conjunction elimination 50
037 선언 도입 disjunction introduction 51
038 선언 제거 disjunction elimination 52
039 조건문 제거 conditional elimination 53
040 조건문 도입 conditional introduction 54
041 부분증명 subproof 57
042 가정의 해제 discharge of an assumption 58
043 부정 도입 negation introduction 59
044 모순 도출 contradiction introduction 60
045 폭발 원리 principle of explosion 61
046 이중부정 제거 double-negation elimination 62
047 귀류법 proof by contradiction 63
048 쌍조건문 도입 biconditional introduction 64
049 쌍조건문 제거 biconditional elimination 65
050 도출가능성 derivability 131
개념어 한눈에 보기
051 - 075
번호 개념어 영어 표기 쪽
051 일차논리 first-order logic 69
052 논의영역 domain of discourse 70
053 개체상수 individual constant 71
054 개체변수 individual variable 72
055 술어 predicate 73
056 관계술어 relation predicate 74
057 함수기호 function symbol 75
058 항 term 76
059 자유변수 free variable 77
060 속박변수 bound variable 78
061 전칭양화사 universal quantifier 81
062 존재양화사 existential quantifier 82
063 양화사의 범위 scope of a quantifier 83
064 열린 논리식 open formula 84
065 닫힌 논리식 sentence; closed formula 85
066 전칭조건문 universally quantified conditional 86
067 존재연언 existentially quantified conjunction 87
068 양화사 부정 quantifier negation 88
069 양화사 순서 quantifier order 89
070 변수 포획 variable capture 90
071 해석 interpretation 93
072 변수 할당 variable assignment 94
073 만족 관계 satisfaction relation 95
074 모형 model 96
075 반례 모형 countermodel 97
개념어 한눈에 보기
076 - 100
번호 개념어 영어 표기 쪽
076 동일성 identity 98
077 유일 존재 unique existence 99
078 반사성 reflexivity 100
079 대칭성 symmetry 101
080 추이성 transitivity 102
081 전칭 제거 universal elimination 105
082 전칭 도입 universal introduction 106
083 임의의 대상 arbitrary object 107
084 존재 도입 existential introduction 108
085 존재 제거 existential elimination 109
086 새 이름 조건 fresh-name condition 110
087 대입 가능성 free substitutability 111
088 동일성 도입 identity introduction 112
089 동일성 제거 identity elimination 113
090 양화논리의 동치 equivalence in first-order logic 114
091 정언명제 categorical proposition 117
092 전칭긍정명제 universal affirmative 118
093 전칭부정명제 universal negative 119
094 특칭긍정명제 particular affirmative 120
095 특칭부정명제 particular negative 121
096 주연 distribution 122
097 대당사각형 square of opposition 123
098 정언삼단논법 categorical syllogism 124
099 중항 middle term 125
100 존재 함축 existential import 133
기호 읽기
이 책에서 사용하는 읽기와 표기 관례
기호 읽기 이 책에서의 뜻
¬ 부정 ~이 아니다
∧ 연언 그리고; 둘 다
∨ 선언 또는; 적어도 하나
→ 실질조건문 ~이면 ~이다
↔ 쌍조건문 ~일 때 그리고 그때에만
∀ 전칭양화사 모든 대상에 대해
∃ 존재양화사 어떤 대상이 존재한다
= 동일성 같은 대상이다
⊥ 모순 모순이 도출되었음을 표시
⊢ 도출가능성 규칙으로 증명할 수 있다
⊨ 귀결·만족 의미에 따라 성립한다
≡ 논리적 동치 모든 경우에 진리값이 같다
P·Q는 명제문자, x·y는 개체변수, a·b는 개체상수로 쓴다. A·B·C는 임의의 논리식을
나타내는 도식 문자다.
도식의 연결선과 ⇒는 설명용이다. ≡의 뜻은 교재마다 다를 수 있으므로 이 책의 관례를
따른다.
동치식 빠르게 확인하기
아래 관계는 고전논리에서 성립한다. ≡는 동치를 뜻한다.
조건문
A → B ≡ ¬A ∨ B
쌍조건문
A ↔ B ≡ (A → B) ∧ (B → A)
이중부정
¬¬A ≡ A
드모르간 법칙
¬(A ∧ B) ≡ ¬A ∨ ¬B
드모르간 법칙
¬(A ∨ B) ≡ ¬A ∧ ¬B
양화사 부정
¬∀x P(x) ≡ ∃x ¬P(x)
양화사 부정
¬∃x P(x) ≡ ∀x ¬P(x)
모양이 비슷한 식도 동치라고 단정하지 않는다. 진리표 또는 해석을 이용해 모든 경우에서
값을 비교한다. 참고: [1] 5장, 19장, 38장.
명제논리의 증명 규칙
A·B·C는 논리식을 뜻한다. 대괄호는 임시 가정 구간이다.
∧도입 A, B에서 A ∧ B
∧제거 A ∧ B에서 A 또는 B
∨도입 A에서 A ∨ B 또는 B ∨ A
∨제거 A ∨ B, [A에서 C], [B에서 C]로 C
→제거 A → B, A에서 B
→도입 [A에서 B]의 가정을 해제하여 A → B
¬도입 [A에서 ⊥]의 가정을 해제하여 ¬A
모순 도출 A와 ¬A에서 ⊥
⊥제거 ⊥에서 임의의 식 C
이중부정 제거 ¬¬A에서 A
↔도입 A → B와 B → A에서 A ↔ B
↔제거 A ↔ B와 A에서 B; 또는 B에서 A
각 행에는 인용한 행과 규칙을 적는다. 이미 닫힌 부분증명의 개별 행은 바깥에서 직접
인용하지 않는다. 귀류법은 고전논리에서 사용할 수 있다.
참고: [1] 17~21장. 표기는 이 책에 맞추어 정리하였다.
양화 추론의 점검표
규칙의 모양과 적용 조건을 함께 확인한다.
전칭 제거
∀x A(x)에서 A(t)
t는 x 자리에 대입할 수 있는 항이어야 한다. 변수 포획이 생기면 먼저 속박변수의 이름을
정리한다.
전칭 도입
A(a)에서 ∀x A(x)
a는 전제·열린 가정과 목표 전칭문에 나타나지 않는 임의의 새 이름이다. 일반화할 위치도
변수 포획 없이 바꾸어야 한다.
존재 도입
A(t)에서 ∃x A(x)
사례 A(t)가 확보되어야 한다. t를 x로 바꾸어 양화할 때, 기존 변수에 뜻하지 않은 포획이
생기지 않아야 한다.
존재 제거
∃x A(x), [A(a)에서 C]로 C
a는 전제·이전의 열린 가정·최종 결론 C에 나타나지 않는 새 이름이다. A(a) 가정은
부분증명을 닫으며 해제한다.
동일성 도입은 t = t를, 동일성 제거는 같은 대상을 가리키는 항의 안전한 대체를 허용한다.
이 책은 비어 있지 않은 영역과, 대상이 정해진 상수·함수의 표준 해석을 사용한다.
참고: [1] 36~39장; [2] 변수 대입.
생각해 보기 길잡이
1장 논리를 기호로 옮기다
001 형식화
① P ∧ Q이다. ∧는 두 내용을 함께 주장하는 연언이다. ② 해석 열쇠에 따라 ‘경기가
취소된다’를 뜻한다.
002 형식언어
① 표현을 만드는 구성 규칙도 정해야 한다. ② 어떤 기호 배열을 올바른 논리식으로
인정할지 정한다.
003 논리식
① 둘 다 논리식이다. P는 원자식이고 ¬P는 복합식이다. ② 그렇다. P(x)는 열린
논리식의 예다.
004 원자식
① 복합식이다. 연결사 ∧가 P와 Q를 결합한다. ② 관계술어와 항으로 이루어지며,
연결사나 양화사로 결합되지 않았다.
005 복합식
① 그렇다. 하나의 식에 부정을 적용한 경우도 포함한다. ② 전건 P ∧ Q와 후건 R이다.
006 구문 규칙
① 오른쪽 논리식이 빠져 있어 완성되지 않았다. ② 구문 규칙에 맞는다. 다만 모든
배정에서 거짓이다.
007 주연결사
① 식 전체에 작용하는 부정 ¬이다. ② 두 큰 부분을 묶는 연언 ∧이다.
008 괄호와 결합 범위
① 왼쪽은 참, 오른쪽은 거짓이다. ② 괄호를 써서 연산이 적용되는 부분을 명확히 한다.
009 해석 열쇠
① 추론 중에는 정한 뜻을 유지해야 한다. ② 서로 다른 명제문자를 배정해 구별한다.
010 대상언어와 메타언어
① 표현 자체를 설명하는 메타언어의 진술이다. ② A는 여러 논리식을 대신하는
메타변수로 쓰인 것이다.
생각해 보기 길잡이
2장 연결사의 진리값을 계산하다
011 명제논리
① 기본적으로 문장을 하나의 단위로 다룬다. 양화의 내부 구조는 일차논리에서 분석한다.
② Q이다.
012 명제변수
① 같은 배정에서는 모든 P에 같은 값을 주어야 한다. ② 같은 값도 가능하다. 서로 다른
기호라는 사실이 진리값의 차이를 강제하지 않는다.
013 진리함수
① 진리함수에서는 출력이 하나로 정해진다. ② 그렇지 않다. P의 진리값만으로 누군가의
믿음을 결정할 수 없다.
014 부정
① 참이다. ② 한국어 문장은 범위가 모호할 수 있다. ‘모두 도착한 것은 아니다’로 범위를
분명히 한다.
015 연언
① 거짓이다. 두 조건이 모두 참이어야 한다. ② 참이다.
016 선언
① 참이다. 이 책의 ∨는 포괄적 선언이다. ② Q만 참인 경우도 있으므로 P를 확정할
수 없다.
017 배타적 선언
① 거짓이다. ② 둘 다 참인 경우를 제외하는 ¬(P ∧ Q)를 더한다.
018 실질조건문
① 참이다. ② 진리함수의 값만으로 인과관계까지 확정할 수 없다.
019 쌍조건문
① 참이다. ② 반대 방향 Q → P도 확보해야 한다.
020 진리값 배정
① 참이다. ② 각각 두 값을 가지므로 2 × 2 = 4개다.
생각해 보기 길잡이
3장 진리표로 관계를 판별하다
021 진리표
① 2³ = 8행이다. ② 같은 P의 반복은 변수 수를 늘리지 않는다.
022 항진식
① 그렇다. 전건만 참이고 후건은 거짓인 배정이 없다. ② P에 거짓을 배정할 수 있으므로
P 자체는 항진식이 아니다.
023 모순식
① 항진식을 부정했으므로 모순식이다. ② 없다. 모순식은 충족불가능하다.
024 우연식
① 참과 거짓을 각각 배정할 수 있으므로 우연식이다. ② 모든 배정에서 참인 항진식이다.
025 논리적 동치
① 모든 배정에서 값이 같아야 한다. ② 항진식이다. ≡는 두 식의 관계를 설명하는
메타언어 표기다.
026 논리적 귀결
① 전제가 모두 참이고 결론이 거짓인 행을 찾아야 한다. ② 그렇다. 연언이 참이면 두
연언지 모두 참이다.
027 충족가능성
① 그렇다. 모든 배정에서 참이므로 참인 배정이 있다. ② 우연식도 참인 배정이 있으므로
충족가능하다.
028 동시 충족가능성
① P를 거짓, Q를 참으로 두면 두 식이 모두 참이다. ② 같은 P에 반대 값을 요구하므로
동시 충족불가능하다.
029 반례 배정
① P → Q와 Q가 모두 참이다. ② 논증이 부당하며 결론이 전제들의 논리적 귀결이 아님을
보인다.
030 결정 절차
① 2⁴ = 16행이다. ② 그렇다. 결정 가능성과 계산의 효율성은 구별한다.
생각해 보기 길잡이
4장 규칙으로 증명을 구성하다
031 형식적 증명
① 전제·가정이라는 표시 또는 앞선 행과 적용 규칙을 밝힌 근거가 필요하다. ② 전제에서
결론으로 이어지는 허용된 단계를 제시해야 한다.
032 자연연역
① 연언 제거다. ② 연언 도입이다.
033 도입 규칙
① 만들려는 연언의 두 연언지다. ② 목표 조건문의 전건을 임시로 가정한다.
034 제거 규칙
① 연언 제거로 얻을 수 있다. ② 선언의 어느 쪽이 참인지 아직 정해지지 않았으므로 바로
얻을 수 없다.
035 연언 도입
① 같은 P를 두 번 근거로 써서 얻을 수 있다. ② 닫힌 부분증명의 개별 행은 바깥에서 직접
인용할 수 없다.
036 연언 제거
① 그렇다. R은 바깥 연언의 오른쪽 연언지다. ② 이 예시에서는 두 번 쓴다.
037 선언 도입
① 그렇다. P가 참이면 선언은 참이다. ② 연언에는 Q도 필요하므로 P만으로는
충분하지 않다.
038 선언 제거
① 선언 제거로 얻으려는 같은 결론을 두 경우에서 모두 도출해야 한다. ② Q인 경우도
검토해야 한다.
039 조건문 제거
① 전건긍정식이라고도 한다. ② 후건긍정의 오류다. P가 거짓, Q가 참인 반례가 있다.
040 조건문 도입
① 그럴 필요가 없다. P를 임시 가정하여 관계를 증명한다. ② P를 무조건 주장하는 대신 P
→ P를 얻는다.
생각해 보기 길잡이
5장 가정을 열고 닫다
041 부분증명
① 사용 범위가 유효한 바깥 전제는 안쪽에서도 사용할 수 있다. ② 바깥에서는 닫힌
구간의 개별 행을 직접 인용할 수 없다.
042 가정의 해제
① 해제한 임시 가정에 대한 의존만 끝난다. 다른 전제는 남을 수 있다. ② 조건문 도입으로
P → Q를 쓴다.
043 부정 도입
① 가정을 해제하고 ¬A를 쓴다. ② 어느 식과 그 부정에서 모순이 나왔는지 밝혀야 한다.
044 모순 도출
① P와 Q가 별개인 한 바로 모순이라고 할 수 없다. ② 같은 식 A와 그 부정 ¬A가
충돌한다.
045 폭발 원리
① 모순된 전제에서의 형식적 도출이다. 현실의 Q를 독립적으로 확인한 것은 아니다. ②
전제들을 동시에 참으로 받아들일 수 있는지 점검해야 한다.
046 이중부정 제거
① 모든 진리값 배정에서 값이 같으므로 동치다. ② 직관주의 논리 등에서는 일반적인 제거
규칙으로 허용하지 않는다.
047 귀류법
① 고전적 귀류법으로 P를 얻는다. ② 부정 도입은 A를 가정해 ¬A를 얻고, 귀류법은
¬A를 가정해 A를 얻는다.
048 쌍조건문 도입
① 두 방향이 모두 필요하다. ② P ↔ Q와 동치인 (P → Q) ∧ (Q → P)이다.
049 쌍조건문 제거
① 두 식이 모두 거짓인 경우도 있으므로 P를 확정할 수 없다. ② Q이다.
050 도출가능성
① 지정된 체계 안에서 결론에 이르는 증명의 존재다. ② 그렇다. 어떤 체계를 사용하는지
함께 밝혀야 한다.
생각해 보기 길잡이
6장 대상과 성질을 표현하다
051 일차논리
① 논의영역 안의 개별 대상을 가리킨다. ② 성질 자체를 양화하는 것은 기본적인
일차논리의 범위를 넘어선다.
052 논의영역
① 그렇다. 새로 포함된 대상이 반례가 될 수 있다. ② 그렇다. 비어 있지 않은 영역 안에서
특정 술어의 외연만 비어 있을 수 있다.
053 개체상수
① 추가 조건 a ≠ b가 없다면 같은 대상을 가리킬 수도 있다. ② 표준 해석에서는 영역
안의 대상을 가리킨다.
054 개체변수
① 의미를 평가할 때 x에는 영역의 대상을 할당한다. 기호 대입에서는 항을 넣는다. ②
그렇다. 서로 다른 변수라고 다른 대상이어야 하는 것은 아니다.
055 술어
① 대상에 성질을 귀속하는 원자 논리식이다. ② 한 개의 항을 넣는다.
056 관계술어
① 대칭성이 별도로 주어져야 한다. ② 그렇다. 세 자리 관계술어 등을 사용할 수 있다.
057 함수기호
① 각 입력 조합에 출력 대상 하나를 대응시킨다. ② P(a)는 참·거짓을 평가하는
논리식이고 f(a)는 대상을 가리키는 항이다.
058 항
① 그렇다. 변수도 항이다. ② P(a)는 논리식이므로 대상을 나타내는 항 자리에 그대로
대입하지 않는다.
059 자유변수
① 서로 다른 위치에서 그렇게 나타날 수 있다. ② y가 자유롭게 나타난다.
060 속박변수
① ∀이 묶는 것은 x다. y는 자유롭게 남는다. ② 변수 포획이 생기지 않도록 안전한 새
이름으로 일관되게 바꿀 수 있다.
생각해 보기 길잡이
7장 양화사의 범위를 읽다
061 전칭양화사
① 전칭문 ∀x P(x)는 거짓이다. ② ∀(모든)이다.
062 존재양화사
① 그렇다. 적어도 하나라는 조건을 충족한다. ② 여러 대상도 허용한다. 정확히 하나는
유일 존재로 따로 표현한다.
063 양화사의 범위
① 전칭양화사에 속박된다. ② 바깥에 있으므로 자유롭게 나타난다.
064 열린 논리식
① y가 자유롭게 남으므로 열린 식이다. ② 자유변수가 없으므로 닫힌 식이다.
065 닫힌 논리식
① P(a)처럼 상수만 포함한 원자식도 닫혀 있을 수 있다. ② 두 변수 모두 속박되어
있으므로 없다.
066 전칭조건문
① 영역의 모든 대상이 회원이면서 등록자여야 한다고 요구한다. ② 현대 일차논리
해석에서 전칭조건문은 참이다.
067 존재연언
① 두 존재문의 대상이 서로 다를 수 있어 충분하지 않다. ② 조건문은 회원이 아닌
대상만으로도 참이 될 수 있어 뜻이 달라진다.
068 양화사 부정
① ∀x ¬P(x)다. ② 한 명만 P가 아니어도 왼쪽은 참이다. 전부 P가 아닌지는 별도로
확인해야 한다.
069 양화사 순서
① 각 x에 그 자신을 y로 고르면 참이다. ② 1과 2 모두와 같은 하나의 y가 없으므로
거짓이다.
070 변수 포획
① ∀z R(y,z)다. 대입한 y가 자유롭게 남는다. ② 기존 자유변수와 충돌하거나 새 포획을
만들지 않는 이름을 고른다.
생각해 보기 길잡이
8장 해석과 모형으로 확인하다
071 해석
① 비논리 기호의 의미가 바뀌면 값이 달라질 수 있다. ② 변수 할당이 정한다.
072 변수 할당
① 그렇다. 여러 변수에 같은 대상을 줄 수 있다. ② 같은 해석의 닫힌 식은 변수 할당에
따라 진리값이 바뀌지 않는다.
073 만족 관계
① 3은 P에 해당하지 않으므로 P(x)는 거짓이다. ② 양화된 변수의 대상을 바꾸면서 범위
안의 식을 검사한다.
074 모형
① 그 문장들을 참으로 만드는 해석만 모형이다. ② 그렇다. 같은 해석에서 모두
참이어야 한다.
075 반례 모형
① 2다. 1은 P에 해당하고 2는 해당하지 않는다. ② 전제들도 모두 참이어야 한다.
076 동일성
① 그럴 수 있다. 이름의 차이가 대상의 차이를 뜻하지 않는다. ② ¬(a = b)의 줄임이다.
077 유일 존재
① 서로 다른 두 대상이라면 유일 존재 조건에 어긋난다. ② P인 대상이 전혀 없는 경우도
허용된다.
078 반사성
① 모든 정수 n에 대해 n ≤ n이므로 반사적이다. ② 영역의 모든 대상을 확인해야 한다.
079 대칭성
① 부모와 자녀의 방향이 다르므로 대칭적이지 않다. ② 관계가 실제로 성립하는 경우에 그
역방향도 성립할 것을 요구한다.
080 추이성
① a = b이고 b = c이면 a = c이므로 추이적이다. ② 서로 다른 성질이다. 양방향 관계가
있어도 세 대상 사이의 연결은 빠질 수 있다.
생각해 보기 길잡이
9장 양화논리를 증명하다
081 전칭 제거
① b가 허용된 항이면 얻을 수 있다. ② 항의 변수가 새로 속박되는 변수 포획이 생기는지
점검한다.
082 전칭 도입
① P(a)는 특정 대상의 성질을 가정하므로 그 추론은 허용되지 않는다. ② 열린 가정과
목표 전칭문에 얽매이지 않는 임의의 새 이름이어야 한다.
083 임의의 대상
① 키가 크다는 특별한 성질에 기대면 모든 대상으로 일반화할 수 없다. ② 아직 해제되지
않은 가정과 전제에 대한 의존을 점검한다.
084 존재 도입
① 존재는 한 사례로 충분하지만 전칭은 모든 대상을 다루어야 한다. ② 적어도 하나의
존재를 증명하며, 유일성은 별도 조건이다.
085 존재 제거
① 존재 제거의 최종 결론에는 그 새 이름이 나타나지 않아야 한다. ② 부분증명으로
표시하고 결론을 얻을 때 그 가정을 해제한다.
086 새 이름 조건
① 존재문만으로는 어느 기존 이름의 대상인지 확정되지 않는다. ② 열린 가정·존재
전제·최종 결론에 나타나는지 등 규칙의 조건도 점검해야 한다.
087 대입 가능성
① ∀y R(a,y)다. ② 변수 대입은 해당 변수의 자유로운 출현을 대상으로 한다.
088 동일성 도입
① 서로 다른 항의 동일성은 별도 근거가 필요하다. ② 필요하지 않다. 동일성 도입은 그런
성질을 전제로 요구하지 않는다.
089 동일성 제거
① P(b)를 얻는다. ② 그렇다. 변수 포획 없이 허용되는 위치에 대입해야 한다.
090 양화논리의 동치
① ∃x P(x) ∨ ∃x Q(x)와 동치다. ② ∃x P(x) ∧ ∃x Q(x)는 두 대상이 서로 달라도
참이므로 일반적으로 동치가 아니다.
생각해 보기 길잡이
10장 전통논리를 형식으로 읽다
091 정언명제
① 특칭긍정명제다. ② 둘 다 부정명제이며, E형은 전칭이고 O형은 특칭이다.
092 전칭긍정명제
① 포함 방향을 뒤집는 근거는 없다. ② 반례가 될 S가 없으므로 A형은 참이다.
093 전칭부정명제
① 그렇다. 두 부류가 겹치지 않는 관계는 양쪽에서 성립한다. ② E형 명제는 거짓이다.
094 특칭긍정명제
① 적어도 하나이며 여러 대상도 허용한다. ② 그렇다. S이면서 P인 대상이 존재한다.
095 특칭부정명제
① 현대 일차논리 해석에서는 O형이 거짓이다. ② 주어와 술어의 위치를 바꾸는 추론은
일반적으로 허용되지 않는다.
096 주연
① 주어항 S와 술어항 P가 모두 주연된다. ② 주어항과 술어항 모두 주연되지 않는다.
097 대당사각형
① A와 O, E와 I다. 각 쌍에서 하나가 참이면 다른 하나는 거짓이다. ② A는 참이고 I는
거짓이므로 그 추론은 성립하지 않는다.
098 정언삼단논법
① S다. 결론의 술어항은 P다. ② 그렇다. 방향을 바꾸면 같은 결론이 보장되지 않을
수 있다.
099 중항
① 표준 정언삼단논법의 결론에는 중항이 나타나지 않는다. ② 서로 다른 부분 부류일 수
있으므로 포함 관계를 단정할 수 없다.
100 존재 함축
① ∃x(S(x) ∧ P(x))이므로 S와 P에 함께 속하는 대상이 존재해야 한다. ② ∃x S(x), 즉
주어 부류 S가 비어 있지 않다는 조건을 더한다.
참고자료
[1] 형식화·진리표·자연연역·일차논리
매그너스·버튼·트루먼·자크(P. D. Magnus, Tim Button, Robert Trueman,
Richard Zach), 『모든 x: 캘거리 - 형식논리 입문(forall x: Calgary. An
Introduction to Formal Logic)』, 오픈 로직 프로젝트, 온라인판.
참고 범위: 4~15장(형식화와 진리표), 16~21장(자연연역), 23~29장(일차논리의
문법), 30~41장(해석과 양화 추론). 각 장의 기초 개념과 규칙 조건을 대조하는 데
사용하였다.
자료 페이지 열기
[2] 항·논리식·변수 대입
오픈 로직 프로젝트(Open Logic Project), 『오픈 로직 텍스트(Open Logic
Text)』, 일차논리 구문·의미론의 「항과 논리식(Terms and Formulas)」 및
「대입(Substitution)」.
참고 범위: 각 절 1쪽의 정의. 함수기호와 항의 구성, 자유변수에 대한 대입, 대입
가능성의 조건을 확인하는 데 사용하였다.
항과 논리식 원문 변수 대입 원문
온라인 자료 확인일: 2026년 9월 17일
https://forallx.openlogicproject.org/
https://builds.openlogicproject.org/content/first-order-logic/syntax-and-semantics/terms-formulas.pdf
https://builds.openlogicproject.org/content/first-order-logic/syntax-and-semantics/substitution.pdf
참고자료
[3] 정언명제와 삼단논법
아리스토텔레스(Aristotle), 『분석론 전서(Prior Analytics)』 제1권 1~7장. A. J.
젠킨슨(A. J. Jenkinson) 영역본, 인터넷 고전 아카이브.
전칭·특칭, 긍정·부정, 항과 삼단논법의 설명을 참고하였다. 본문의 한국어 예시와
현대 기호 표기는 새로 구성하였다.
『분석론 전서』 원문
[4] 긍정·부정과 대당 관계
아리스토텔레스(Aristotle), 『명제론(On Interpretation)』 6~7장. E. M.
에지힐(E. M. Edghill) 영역본, 인터넷 고전 아카이브.
『명제론』 원문
자료 이용과 이 책의 설명 범위
[1]과 [2]는 저작자 표시 4.0(CC BY 4.0) 조건으로 공개된 교재다. 본문은 이 자료의
표준 정의와 규칙을 참고하여 한국어 설명·예시·도식을 새로 구성하였다. 원저자의
보증이나 승인을 뜻하지 않는다.
CC BY 4.0 이용 조건
10장의 대당 관계는 현대 일차논리로 해석한 A·E·I·O를 기준으로 설명하며, 주어 부류가
존재할 때 추가되는 관계를 구별한다. 역사적 논리 체계의 다양한 관례는 고급편의 별도 탐구
주제로 남긴다.
https://classics.mit.edu/Aristotle/prior.1.i.html
https://classics.mit.edu/Aristotle/interpretation.1.1.html
https://creativecommons.org/licenses/by/4.0/
논리학 36권 시리즈 · 3
논리를 형식화하고
계산하는 언어
생각을 형식으로 옮기는 100개의 개념어.
논리의 구조를 명확하게 표현하고,
추론을 체계적으로 다루는 언어를 익힌다.
논리학 개념어 100
02 기초편 · 논증을 읽는 언어
03 중급편 · 논리를 형식화하고 계산하는 언어
04 고급편 · 논리 체계 자체를 연구하는 언어
한국논리학협회
이호찬
에듀이음
표제
차례
이 책을 읽는 법
프롤로그
1장 논리를 기호로 옮기다
001 형식화
002 형식언어
003 논리식
004 원자식
005 복합식
006 구문 규칙
007 주연결사
008 괄호와 결합 범위
009 해석 열쇠
010 대상언어와 메타언어
2장 연결사의 진리값을 계산하다
011 명제논리
012 명제변수
013 진리함수
014 부정
015 연언
016 선언
017 배타적 선언
018 실질조건문
019 쌍조건문
020 진리값 배정
3장 진리표로 관계를 판별하다
021 진리표
022 항진식
023 모순식
024 우연식
025 논리적 동치
026 논리적 귀결
027 충족가능성
028 동시 충족가능성
029 반례 배정
030 결정 절차
4장 규칙으로 증명을 구성하다
031 형식적 증명
032 자연연역
033 도입 규칙
034 제거 규칙
035 연언 도입
036 연언 제거
037 선언 도입
038 선언 제거
039 조건문 제거
040 조건문 도입
5장 가정을 열고 닫다
041 부분증명
042 가정의 해제
043 부정 도입
044 모순 도출
045 폭발 원리
046 이중부정 제거
047 귀류법
048 쌍조건문 도입
049 쌍조건문 제거
050 도출가능성
6장 대상과 성질을 표현하다
051 일차논리
052 논의영역
053 개체상수
054 개체변수
055 술어
056 관계술어
057 함수기호
058 항
059 자유변수
060 속박변수
7장 양화사의 범위를 읽다
061 전칭양화사
062 존재양화사
063 양화사의 범위
064 열린 논리식
065 닫힌 논리식
066 전칭조건문
067 존재연언
068 양화사 부정
069 양화사 순서
070 변수 포획
8장 해석과 모형으로 확인하다
071 해석
072 변수 할당
073 만족 관계
074 모형
075 반례 모형
076 동일성
077 유일 존재
078 반사성
079 대칭성
080 추이성
9장 양화논리를 증명하다
081 전칭 제거
082 전칭 도입
083 임의의 대상
084 존재 도입
085 존재 제거
086 새 이름 조건
087 대입 가능성
088 동일성 도입
089 동일성 제거
090 양화논리의 동치
10장 전통논리를 형식으로 읽다
091 정언명제
092 전칭긍정명제
093 전칭부정명제
094 특칭긍정명제
095 특칭부정명제
096 주연
097 대당사각형
098 정언삼단논법
099 중항
100 존재 함축
에필로그
부록
개념어 001~025
개념어 026~050
개념어 051~075
개념어 076~100
기호 읽기
동치식 빠르게 확인하기
명제논리의 증명 규칙
양화 추론의 점검표
생각해 보기 길잡이
생각해 보기 길잡이 · 1장
생각해 보기 길잡이 · 2장
생각해 보기 길잡이 · 3장
생각해 보기 길잡이 · 4장
생각해 보기 길잡이 · 5장
생각해 보기 길잡이 · 6장
생각해 보기 길잡이 · 7장
생각해 보기 길잡이 · 8장
생각해 보기 길잡이 · 9장
생각해 보기 길잡이 · 10장
참고자료
4권 · 논리학 개념어 100: 고급편
독서 안내
이 책을 읽는 방법
01 한 페이지에서 개념 하나를 익힌다
정의를 먼저 읽고, 왜 필요한지와 예시를 확인한다. 가운데 도식은 비교할
방향이나 조건을 드러낸다. 아래의 두 질문에 답한 뒤 관련 개념으로 이동한다.
02 기호의 역할을 먼저 구별한다
⊢는 증명, ⊨는 의미론적 귀결을 나타낸다. T는 문장들의 이론이고, M은 구조나
모형이다. 같은 글자라도 문맥에 따라 역할이 달라지므로 기호 읽기 부록을 함께
본다.
03 정리의 가정을 함께 읽는다
완전성·콤팩트성·불완전성에는 적용 대상과 조건이 있다. 본문은 핵심을 짧게
설명하고, 부록에서는 언어의 크기, 효과적 공리화, 의미론의 선택 등을 덧붙인다.
04 표준으로 삼는 범위를 정한다
별도 설명이 없으면 비어 있지 않은 영역을 가진 고전 일차논리를 기준으로 한다.
양상·직관주의·선형논리에서는 해당 페이지의 규칙과 의미론을 따른다.
05 개념을 연결해 읽는다
목차, 장의 개념 목록, 함께 보기, 개념어 색인에는 해당 페이지로 가는 링크를
넣었다. 생각해 보기 길잡이는 정답의 핵심과 조건을 설명하며 다른 타당한
표현도 허용한다.
프롤로그
논리의 규칙을 다시 묻다
논리식을 읽고 증명 규칙을 적용할 수 있게 되면 새로운 질문이 생긴다. 이
규칙으로 증명한 결론은 언제나 타당한가? 타당한 결론은 모두 증명할 수
있는가? 모든 문제를 끝까지 판정하는 절차가 있는가?
고급편은 이 질문들을 다룬다. 논리 체계를 연구 대상으로 삼아 언어, 증명,
모형, 계산의 관계를 살핀다. 같은 공리의 여러 모형을 비교하고, 증명을 다른
형태로 바꾸며, 한 체계가 해결하는 문제의 범위를 검토한다.
완전성과 불완전성은 이름이 닮아 있어도 서로 다른 대상을 말한다. 어떤
논리의 증명 규칙이 의미론적 귀결을 모두 포착한다는 사실과, 특정 산술
공리계가 모든 산술 문장을 결정한다는 주장을 나누어 읽어야 한다.
후반부에서는 가능성, 시간, 지식과 의무를 표현하는 논리로 나아간다.
이어서 진리값이나 전제 사용의 규칙을 바꾸는 논리들을 비교한다.
마지막에는 성질과 함수를 다루는 고차언어, 유형, 프로그램과 증명의 관계를
연결한다.
이 책의 목표는 각 분야의 모든 증명을 한 권에 담는 데 있지 않다. 논문과
전문서를 읽을 때 개념의 위치와 정리의 조건을 스스로 확인할 수 있는 기초
지도를 제공한다. 한 페이지의 개념을 이해한 뒤 예시와 질문을 통해 그
경계를 확인해 보자.
01
1장
논리학을 논리학의 대상으로 삼다
기호로 쓴 논증에서, 그 기호와 규칙을 연구하는 단계로 나아간다.
001 메타논리 002 구문론
003 의미론 004 형식체계
005 공리화 006 이론
007 증명가능성 008 논리적 귀결
009 논리상항 010 메타정리
참고: [1] 구문·의미론, 증명 체계
1장 · 정리
개념 연결하기
논리학을 논리학의 대상으로 삼다
대상언어와 연구 수준
P → P를 증명하는 작업과 모든 증명의 건전성을 보이는 작업은 수준이
다르다. 연구 대상을 먼저 정하면 구문론·의미론·메타정리의 관계가
분명해진다.
두 기호의 역할
Γ ⊢ A는 정해진 체계 안에 증명이 있다는 뜻이다. Γ ⊨ A는 모든 허용된
해석에서 참이 보존된다는 뜻이다. 두 관계를 연결하려면 별도의 메타정리가
필요하다.
다시 확인할 질문
증명과 의미의 관계를 각각 어떤 기호로 쓰는가?
본문의 예시를 바꾸어, 같은 구별을 다시 설명해 보자.
02
2장
논리 체계의 힘을 측정하다
무엇을 증명하고, 무엇을 결정하며, 어떤 모형을 허용하는지 살핀다.
011 건전성 012 완전성
013 무모순성 014 이론의 완전성
015 공리의 독립성 016 보수적 확장
017 결정가능성 018 콤팩트성
019 뢰벤하임-스콜렘 정리 020 범주성
참고: [1] 건전성·완전성·콤팩트성; [4] 모형이론
2장 · 정리
개념 연결하기
논리 체계의 힘을 측정하다
세 질문을 분리한다
증명 가능한 결론이 타당한가, 타당한 결론을 모두 증명하는가, 모든 문장을
결정하는가는 서로 다르다. 건전성·논리의 완전성·이론의 완전성을
구별한다.
무한을 다루는 조건
콤팩트성은 모든 유한 부분집합을 대상으로 한다. 뢰벤하임-스콜렘
정리에서는 언어와 모형의 크기를 확인한다. 범주성을 말할 때도 비교할
모형의 크기를 함께 적는다.
다시 확인할 질문
논리의 완전성과 이론의 완전성은 무엇이 다른가?
본문의 예시를 바꾸어, 같은 구별을 다시 설명해 보자.
03
3장
모형으로 논리의 세계를 해석하다
같은 공리의 여러 모형을 비교하고, 언어로 구별할 수 있는 성질을 찾는다.
021 모형이론 022 구조
023 동형 024 초등동치
025 부분구조 026 초등부분구조
027 정의가능성 028 양화사 제거
029 비표준 모형 030 유형
참고: [1] 모형이론; [4] 구조·정의가능성·유형
3장 · 정리
개념 연결하기
모형으로 논리의 세계를 해석하다
동형과 초등동치
동형은 영역의 전단사와 기호 해석의 보존을 요구한다. 초등동치는 일차
문장의 진리값이 같다는 조건이다. 전자는 후자를 보장하지만 역은
일반적으로 성립하지 않는다.
부분과 표현의 범위
부분구조를 택해도 모든 양화식의 참이 보존되지는 않는다. 초등부분구조는
작은 구조의 대상을 넣은 식까지 보존한다. 정의가능성은 언어와 매개변수의
허용 범위에 달려 있다.
다시 확인할 질문
두 구조가 문장으로 구별되지 않아도 동형일 수 없는 이유는?
본문의 예시를 바꾸어, 같은 구별을 다시 설명해 보자.
04
4장
증명의 구조를 분석하다
증명을 하나의 수학적 대상으로 보고, 규칙과 변환 과정을 분석한다.
031 증명이론 032 시퀀트
033 시퀀트 계산 034 구조 규칙
035 절단 규칙 036 절단 제거
037 부분식 성질 038 정규화
039 증명 복잡도 040 구성적 증명
참고: [1] 시퀀트 계산; [5] 증명 변환·절단 제거
4장 · 정리
개념 연결하기
증명의 구조를 분석하다
증명은 변환할 수 있다
절단은 중간 결론으로 두 증명을 연결한다. 절단 제거와 정규화는 최종
결론을 유지하면서 증명의 구성을 바꾼다. 변환 가능성과 짧은 증명의
존재는 별개다.
가정도 규칙의 일부다
전제를 더하거나 합치거나 재배열할 수 있는지는 구조 규칙이 정한다.
전제를 자원으로 다루는 논리에서는 이 규칙들의 허용 범위가 달라진다.
다시 확인할 질문
증명 변환 뒤 무엇은 보존되고 무엇은 커질 수 있는가?
본문의 예시를 바꾸어, 같은 구별을 다시 설명해 보자.
05
5장
계산의 가능성과 한계를 밝히다
계산 절차를 엄밀하게 정의하고, 알고리즘이 해결하는 문제의 범위를 묻는다.
041 계산가능성 042 튜링 기계
043 처치-튜링 논제 044 계산적 열거가능성
045 결정불가능성 046 정지 문제
047 환원 048 원시재귀함수
049 부분재귀함수 050 람다 계산
참고: [1] 계산가능성·튜링 기계; [2] 재귀함수·람다 계산
5장 · 정리
개념 연결하기
계산의 가능성과 한계를 밝히다
종료와 효율을 구별한다
결정 절차는 모든 입력에서 종료하고 정확히 답해야 한다. 계산적
열거가능성은 속하는 사례를 확인하는 능력이다. 오래 걸린다는 사실만으로
결정불가능성을 말할 수는 없다.
환원의 방향을 읽는다
A ≤m B이면 B의 판정으로 A를 판정한다. A의 결정불가능성은 B로
전달된다. 화살표의 직관적 인상보다 입력과 답이 어느 방향으로 바뀌는지
추적한다.
다시 확인할 질문
참인 입력을 인식하는 일과 모든 입력을 결정하는 일의 차이는?
본문의 예시를 바꾸어, 같은 구별을 다시 설명해 보자.
06
6장
산술로 증명의 한계를 묻다
산술 안에 증명을 표현하고, 공리계의 완전성과 무모순성을 구별한다.
051 페아노 산술 052 괴델 번호화
053 대각화 보조정리 054 증명가능성 술어
055 제1불완전성 정리 056 제2불완전성 정리
057 타르스키의 진리 정리 058 상대적 무모순성
059 독립 명제 060 힐베르트 프로그램
참고: [1] 불완전성; [2] 괴델·타르스키 정리
6장 · 정리
개념 연결하기
산술로 증명의 한계를 묻다
정리의 적용 대상을 정한다
괴델-로서 형태의 제1불완전성은 무모순성, 효과적 공리화, 충분한 산술을
요구한다. 제2불완전성에서는 무모순성을 표현하는 술어와 도출 조건도
확인한다.
표현 가능성과 진리 정의
증명 코드를 다루는 술어를 산술 안에 만들 수 있어도, 산술 전체의 참을
같은 산술언어로 정의할 수 있는 것은 아니다. 메타언어와 대상언어의
구별이 다시 중요해진다.
다시 확인할 질문
제2불완전성에서 내부 증명이라는 조건은 무엇을 뜻하는가?
본문의 예시를 바꾸어, 같은 구별을 다시 설명해 보자.
07
7장
가능성과 필연성을 해석하다
세계와 세계 사이의 관계를 정하여, 가능성과 필연성의 조건을 읽는다.
061 양상논리 062 필연성
063 가능성 064 가능세계
065 접근가능성 관계 066 크립키 의미론
067 정상 양상논리 068 체계 T
069 체계 S4 070 체계 S5
참고: [3] 정상 양상논리·크립키 의미론
7장 · 정리
개념 연결하기
가능성과 필연성을 해석하다
세계보다 관계를 먼저 본다
□A와 ◇A의 값은 현재 세계에서 접근하는 세계들에 달려 있다. 현재 세계도
검사하는지는 반사성에 달려 있다. 접근 세계가 없는 경우도 참 조건대로
계산한다.
체계 이름에 조건을 붙인다
T는 반사성, S4는 반사성과 추이성, S5는 동치관계에 대응한다. 필연화는
열린 가정이 아니라 전제 없이 얻은 정리에 적용한다.
다시 확인할 질문
□A를 판정하기 전에 어떤 접근 관계를 확인해야 하는가?
본문의 예시를 바꾸어, 같은 구별을 다시 설명해 보자.
08
8장
시간·지식·의무의 논리를 읽다
언제, 누가, 어떤 기준에서 성립하는 주장인지 구별하여 형식화한다.
071 시간논리 072 선형시간논리
073 분기시간논리 074 인식논리
075 공통지식 076 믿음논리
077 의무논리 078 허용과 금지
079 반사실 조건문 080 동적논리
참고: [3] 인식·시간·의무·조건 논리; [7, 8] 시스템과 시간
8장 · 정리
개념 연결하기
시간·지식·의무의 논리를 읽다
시간과 경로의 양화를 구별한다
언젠가와 항상은 시점의 범위를 달리한다. 분기시간에서는 어떤 경로와 모든
경로도 구별한다. 모든 경로에서 완료되더라도 완료 시점이 서로 같을
필요는 없다.
모형이 채택한 이상화를 확인한다
앎의 사실성과 믿음의 성찰, 의무와 현실의 관계는 서로 다른 조건이다. 실제
사람이나 제도가 모형의 모든 가정을 만족한다고 단정하지 않는다.
다시 확인할 질문
어떤 경로에서 언젠가와 모든 경로에서 언젠가는 무엇이 다른가?
본문의 예시를 바꾸어, 같은 구별을 다시 설명해 보자.
09
9장
고전논리의 가정을 바꾸다
참의 값, 증명의 뜻, 전제의 사용 규칙을 바꾸어 여러 논리를 비교한다.
081 비고전논리 082 직관주의 논리
083 배중률 084 이중부정 제거
085 다치논리 086 퍼지논리
087 파라일관 논리 088 폭발 원리
089 관련논리 090 선형논리
참고: [1, 3] 직관주의·다치논리; [5] 자원과 구조 규칙
9장 · 정리
개념 연결하기
고전논리의 가정을 바꾸다
무엇을 바꾼 논리인지 묻는다
직관주의는 구성적 증거를, 다치논리는 값과 지정값을, 선형논리는 전제
사용을 검토한다. 서로 다른 변화의 지점을 한 가지 기준으로 섞지 않는다.
거부하는 원리를 정확히 적는다
표준 직관주의는 일반 배중률을 채택하지 않지만 폭발은 허용한다.
파라일관성은 모순에서 임의의 결론이 따라오는 것을 막는 성질이다. 두
입장은 별개의 선택이다.
다시 확인할 질문
배중률을 일반적으로 쓰지 않는 것과 폭발을 막는 것은 같은가?
본문의 예시를 바꾸어, 같은 구별을 다시 설명해 보자.
10
10장
언어와 증명의 차원을 넓히다
성질과 함수를 양화하고, 유형과 프로그램으로 증명을 표현한다.
091 이차논리 092 전체 의미론
093 헨킨 의미론 094 고차논리
095 유형이론 096 단순유형 람다 계산
097 의존유형 098 커리-하워드 대응
099 형식검증 100 정리증명 보조기
참고: [1, 2] 이차논리·람다 계산; [6] 유형과 증명
10장 · 정리
개념 연결하기
언어와 증명의 차원을 넓히다
양화 범위가 의미를 바꾼다
이차논리의 같은 구문에도 전체 의미론과 헨킨 의미론을 줄 수 있다.
범주성과 완전성을 비교할 때는 선택한 의미론과 증명 체계를 반드시
명시한다.
검증의 결론과 전제를 함께 읽는다
유형 검사는 표현의 적격성을, 정리 검사는 지정된 체계에서 증명의
적합성을 확인한다. 형식 명세가 실제 의도와 맞는지, 어떤 공리에
의존하는지도 검토한다.
다시 확인할 질문
같은 이차언어라도 의미론에 따라 어떤 성질이 달라지는가?
본문의 예시를 바꾸어, 같은 구별을 다시 설명해 보자.
에필로그
조건을 읽는 연구자의 언어
논리 체계를 연구한다는 것은 가능성과 한계를 함께 명시하는 일이다.
건전성은 증명이 의미를 보존하는지 묻고, 완전성은 의미론적 귀결을 증명이
포착하는지 묻는다. 결정가능성은 이 질문들을 알고리즘으로 끝까지 판정할
수 있는지 살핀다.
모형이론과 증명이론은 같은 논리를 서로 다른 방향에서 비춘다. 모형은
공리의 여러 실현을 보여 주고, 증명은 결론을 얻는 규칙과 자원을 드러낸다.
계산가능성과 불완전성은 이러한 연구가 어디에서 서로 만나는지 보여 준다.
여러 논리를 비교할 때는 기준을 분명히 해야 한다. 무엇을 양화하는가, 어떤
값을 참으로 받아들이는가, 전제를 몇 번 사용할 수 있는가, 어떤 의미론과
증명 체계를 선택하는가를 차례로 묻는다.
앞으로 전문서를 읽다가 익숙한 이름을 만나면 정의와 가정을 다시 확인하자.
같은 이름이 다른 수준에서 쓰일 수도 있다. 개념의 이름을 아는 데서 나아가
그 개념이 답하는 질문을 설명할 수 있을 때, 논리 체계를 연구하는 언어가
자신의 언어가 된다.
부록
논리학 개념어 100
한눈에 보기
기호 · 정리의 조건 · 비교표 · 확장 예시 · 답안 길잡이
개념어와 영어 표기 130
기호 읽기 135
주요 정리의 적용 조건 137
개념 비교표 140
확장 예시 네 가지 142
생각해 보기 길잡이 146
참고자료와 출처 129
개념어 한눈에 보기
개념어와 영어 표기
001 - 020
번호 개념어 영어 표기 쪽
001 메타논리 metalogic 9
002 구문론 syntax 10
003 의미론 semantics 11
004 형식체계 formal system 12
005 공리화 axiomatization 13
006 이론 theory 14
007 증명가능성 provability 15
008 논리적 귀결 logical consequence 16
009 논리상항 logical constant 17
010 메타정리 metatheorem 18
011 건전성 soundness 21
012 완전성 completeness 22
013 무모순성 consistency 23
014 이론의 완전성 completeness of a theory 24
015 공리의 독립성 independence of axioms 25
016 보수적 확장 conservative extension 26
017 결정가능성 decidability 27
018 콤팩트성 compactness 28
019 뢰벤하임-스콜렘 정리 Löwenheim-Skolem theorem 29
020 범주성 categoricity 30
개념어 한눈에 보기
개념어와 영어 표기
021 - 040
번호 개념어 영어 표기 쪽
021 모형이론 model theory 33
022 구조 structure 34
023 동형 isomorphism 35
024 초등동치 elementary equivalence 36
025 부분구조 substructure 37
026 초등부분구조 elementary substructure 38
027 정의가능성 definability 39
028 양화사 제거 quantifier elimination 40
029 비표준 모형 nonstandard model 41
030 유형 type in model theory 42
031 증명이론 proof theory 45
032 시퀀트 sequent 46
033 시퀀트 계산 sequent calculus 47
034 구조 규칙 structural rule 48
035 절단 규칙 cut rule 49
036 절단 제거 cut elimination 50
037 부분식 성질 subformula property 51
038 정규화 normalization 52
039 증명 복잡도 proof complexity 53
040 구성적 증명 constructive proof 131
개념어 한눈에 보기
개념어와 영어 표기
041 - 060
번호 개념어 영어 표기 쪽
041 계산가능성 computability 57
042 튜링 기계 Turing machine 58
043 처치-튜링 논제 Church-Turing thesis 59
044 계산적 열거가능성 computable enumerability 60
045 결정불가능성 undecidability 61
046 정지 문제 halting problem 62
047 환원 reduction 63
048 원시재귀함수 primitive recursive function 64
049 부분재귀함수 partial recursive function 65
050 람다 계산 lambda calculus 66
051 페아노 산술 Peano arithmetic 69
052 괴델 번호화 Gödel numbering 70
053 대각화 보조정리 diagonal lemma 71
054 증명가능성 술어 provability predicate 72
055 제1불완전성 정리 first incompleteness theorem 73
056 제2불완전성 정리 second incompleteness theorem 74
057 타르스키의 진리 정리 Tarski's undefinability theorem 75
058 상대적 무모순성 relative consistency 76
059 독립 명제 independent sentence 77
060 힐베르트 프로그램 Hilbert's program 78
개념어 한눈에 보기
개념어와 영어 표기
061 - 080
번호 개념어 영어 표기 쪽
061 양상논리 modal logic 81
062 필연성 necessity 82
063 가능성 possibility 83
064 가능세계 possible world 84
065 접근가능성 관계 accessibility relation 85
066 크립키 의미론 Kripke semantics 86
067 정상 양상논리 normal modal logic 87
068 체계 T modal system T 88
069 체계 S4 modal system S4 89
070 체계 S5 modal system S5 90
071 시간논리 temporal logic 93
072 선형시간논리 linear temporal logic 94
073 분기시간논리 branching-time logic 95
074 인식논리 epistemic logic 96
075 공통지식 common knowledge 97
076 믿음논리 doxastic logic 98
077 의무논리 deontic logic 99
078 허용과 금지 permission and prohibition 100
079 반사실 조건문 counterfactual conditional 101
080 동적논리 dynamic logic 133
개념어 한눈에 보기
개념어와 영어 표기
081 - 100
번호 개념어 영어 표기 쪽
081 비고전논리 non-classical logic 105
082 직관주의 논리 intuitionistic logic 106
083 배중률 law of excluded middle 107
084 이중부정 제거 double-negation elimination 108
085 다치논리 many-valued logic 109
086 퍼지논리 fuzzy logic 110
087 파라일관 논리 paraconsistent logic 111
088 폭발 원리 principle of explosion 112
089 관련논리 relevance logic 113
090 선형논리 linear logic 114
091 이차논리 second-order logic 117
092 전체 의미론 full semantics 118
093 헨킨 의미론 Henkin semantics 119
094 고차논리 higher-order logic 120
095 유형이론 type theory 121
096 단순유형 람다 계산 simply typed lambda calculus 122
097 의존유형 dependent type 123
098 커리-하워드 대응 Curry-Howard correspondence 124
099 형식검증 formal verification 125
100 정리증명 보조기 proof assistant 126
부록 · 기호
기호 읽기
1 / 2 · 기호의 역할은 문맥과 체계에 따라 읽는다.
Γ, Δ 감마, 델타
전제나 식들의 모음을 나타낸다. 시퀀트에서는 왼쪽과 오른쪽의 식 모음을 구별한다.
T, S 티, 에스
특정 언어의 이론 또는 공리 집합을 나타낸다. 양상 체계 T와는 문맥으로 구별한다.
M, N 엠, 엔
구조나 모형을 나타낸다. M ⊨ T는 M이 T의 모든 문장을 만족한다는 뜻이다.
⊢ / ⊬ 도출한다 / 도출하지 못한다
선택한 증명 체계에 증명이 존재하는지 나타낸다.
⊨ 만족한다 / 논리적으로 따라온다
M ⊨ A는 모형의 만족, Γ ⊨ A는 모든 Γ의 모형에서의 참을 뜻한다.
⇒ / → 시퀀트 구분 / 조건문
⇒는 전제 쪽과 결론 쪽을 나눈다. →는 식 안의 연결사나 문맥에 따른 함수 유형이다.
≅ / ≡ / ≺ 동형 / 초등동치 / 초등부분구조
구조 전체의 대응, 일차 문장의 일치, 매개변수를 포함한 보존을 각각 나타낸다.
⌜A⌝ / PrT A의 코드 / 티의 증명 술어
⌜A⌝는 구문 코드다. 산술식 안에서는 그 수를 나타내는 수항을 쓰는 것으로 이해한다.
Con(T) 티의 무모순성
표준적으로 ¬PrT(⌜⊥⌝)를 뜻한다. 어느 술어를 택했는지와 도출 조건을 확인한다.
≤m 다대일 환원
x ∈ A와 f(x) ∈ B가 동치가 되는 전계산가능 함수 f가 있으면 A ≤m B라 쓴다.
부록 · 기호
기호 읽기
2 / 2 · 기호의 역할은 문맥과 체계에 따라 읽는다.
□A / ◇A 필연적으로 A / 가능하게 A
현재 세계에서 접근하는 모든 세계 / 어떤 세계에서 A가 참이라는 조건이다.
W, R, V 세계, 접근 관계, 값 배정
크립키 모형 M = (W, R, V)를 구성한다. 틀은 (W, R)이다.
F A / G A / X A 언젠가 / 항상 / 다음에
이 책의 선형시간 예시는 현재를 포함하는 F, G와 바로 다음 시점의 X를 쓴다.
EF A / AF A 어떤 경로 / 모든 경로에서 언젠가
무한 실행을 기준으로 한다. 끝나는 상태는 자기 반복으로 처리할 수 있다.
Ki / Bi / CG 앎 / 믿음 / 공통지식
아래첨자 i는 행위자, G는 집단을 나타낸다.
O A / P(A) A의 의무 / A의 약한 허용
P(A) = ¬O¬A로 정의한다. A의 금지는 O¬A다.
[α]A / 〈α〉A 모든 종료 결과 / 어떤 종료 결과
프로그램 α의 종료하는 실행 뒤 A를 말한다. [α]A만으로 종료를 보장하지 않는다.
λx.t / →β 함수 추상화 / 베타 환원
변수 포획을 피하여 인수를 본문에 대입한다. 함수 적용의 계산 규칙이다.
t : A / A → B 티의 유형은 A / 함수 유형
A → B의 함수는 A의 값을 받아 B의 값을 준다. 증명 해석에서는 함의에 대응한다.
A ⊗ B / !A 자원의 결합 / 재사용 표지
선형논리의 결합과 지수 연산자다. 고전논리의 자유로운 복제와 구별한다.
부록 · 정리의 조건
완전성·콤팩트성·모형의 크기
건전성과 강한 완전성
고전 일차논리의 표준 의미론과 적절한 증명 체계를 고정한다. Γ ⊢ A와 Γ ⊨
A가 동치라는 주장은 Γ의 모든 모형을 대상으로 한다. 무한한 Γ에서도 개별
증명은 유한한 전제만 사용한다. [1]
콤팩트성의 범위
임의의 문장 집합 Γ의 모든 유한 부분집합에 모형이 있으면 Γ에도 모형이
있다. 유한 부분마다 모형이 달라도 되며, 전체 모형이 유한하다는 결론은 없다.
이차논리의 전체 의미론에는 이 정리를 그대로 적용할 수 없다. [1]
하향 뢰벤하임-스콜렘
본문은 가산 일차언어에서 무한 모형의 존재가 가산 무한 모형의 존재를
보장한다는 형태를 쓴다. 더 일반적인 크기 정리에서는 언어의 크기와 보존할
매개변수 집합의 크기를 함께 고려한다. [1]
범주성과 유형
범주성은 비교할 모형의 기수를 정해 진술한다. 30번의 유형은 고정한 이론 및
매개변수와 양립하는 부분 유형을 포함한다. 모든 식이나 그 부정 가운데 하나를
고르는 완전 유형과 구별한다. [4]
부록 · 정리의 조건
불완전성과 진리 정리의 조건
제1불완전성: 괴델-로서 형태
로빈슨 산술 Q를 포함하는 무모순인 계산적 열거가능 공리계 T를 택하면,
T에서 A도 ¬A도 증명되지 않는 산술 문장 A가 있다. 이 책의 짧은 진술은 이
형태를 기준으로 한다. 원래 괴델 문장의 반증 불가능성에 쓰인 강화된 조건과
구별한다. [1, 2]
제2불완전성: 표준 증명 술어
PA를 포함하는 무모순인 효과적 공리계와 통상적인 증명가능성 술어를
기준으로 생각한다. 표준 도출 조건을 만족할 때 T는 Con(T)를 증명하지
못한다. 자기 체계 안에서의 결과이며, 더 강한 이론에서의 증명을 금지하지
않는다. [1, 2]
타르스키의 정의불가능성
표준 자연수의 모든 참인 산술 문장의 코드를 정확히 골라내는 산술식은 없다.
다른 메타언어의 의미론이나 제한된 복잡도의 부분 진리 술어까지 금지한다는
뜻은 아니다. [1, 2]
효과적 공리화의 의미
공리들을 알고리즘으로 열거할 수 있다는 조건을 사용한다. 필요한 경우 공리의
열거 기록을 증명 코드에 함께 넣어, 주어진 유한 증명의 적격성을 기계적으로
확인할 수 있게 한다. [1, 2]
부록 · 정리의 조건
증명 변환·양상·이차 의미론
절단 제거와 부분식 성질
본문은 순수한 고전 시퀀트 계산을 기본 사례로 쓴다. 비논리 공리의 추가, 등호
규칙, 양화사 대입에 따라 정확한 정식화가 달라진다. 절단 제거가 증명의
크기를 줄인다는 보장은 없다. [1, 5]
정상 양상논리의 필연화
전제 없이 얻은 정리 A에서 □A를 얻는다. 열린 가정 A에 곧바로 적용하면
건전성이 깨질 수 있다. T·S4·S5는 각각 반사적 틀, 반사적·추이적 틀,
동치관계 틀에 대한 표준 체계를 말한다. [3]
전체 의미론과 헨킨 의미론
전체 의미론은 해당 차수의 모든 관계를 양화한다. 헨킨 의미론은 허용된 관계
영역과 필요한 닫힘 조건을 모형에 포함한다. 포괄 공리 등의 공리화에 맞는
헨킨 모형을 택할 때 완전성을 논한다. 임의의 관계 몇 개를 고르는 것만으로
모든 정리가 따라오지는 않는다. [1, 2]
유형과 종료
단순유형 람다 계산의 강한 정규화는 일반 재귀를 더하지 않은 기본 체계의
성질이다. 정리증명 보조기의 검사는 채택한 공리와 커널 규칙에 상대적이다.
소프트웨어의 버전별 문법과 기능은 공식 문서에서 확인한다. [1, 6]
부록 · 비교표
논리 체계와 이론의 성질
건전성 증명에서 의미로
Γ ⊢ A → Γ ⊨ A
논증의 전제가 실제로 참인지와는 별도 문제다.
논리의 완전성 의미에서 증명으로
Γ ⊨ A → Γ ⊢ A
모든 Γ의 모형에서의 참이 출발점이다.
이론의 완전성 각 문장의 결정
T ⊢ A 또는 T ⊢ ¬A
무모순성도 함께 확인한다.
결정가능성 모든 입력에서 종료
정답인 예·아니요를 산출
짧은 실행 시간까지 뜻하지는 않는다.
범주성 모형의 유일성
지정한 크기에서 M ≅ N
같은 진리값만으로는 충분하지 않다.
부록 · 비교표
여러 논리가 구별하는 것
양상논리 평가 범위
A / □A / ◇A
현재·모든 접근 세계·어떤 접근 세계를 구별한다.
직관주의 논리 증거의 구성
A ∨ B / ∃x P(x)
어느 쪽인지, 어떤 대상인지의 증거를 확인한다.
다치논리 값과 지정값
참·거짓 외의 값
연결사의 표와 귀결의 기준을 함께 정한다.
파라일관 논리 모순의 확산
A, ¬A에서 임의의 B?
폭발을 일반적으로 허용하지 않는다.
선형논리 전제의 사용
A / A ⊗ A / !A
소비되는 자원과 재사용 가능한 자원을 구별한다.
부록 · 확장 예시
1. 콤팩트성으로 무한을 얻다
관련 개념 018 · 029
01 문제를 정한다
자연수 구조의 참인 일차 문장들을 모은 이론에 새 상항 c를 더한다. 여기에 c >
0, c > 1, c > 2, …을 모두 추가하여 이론 Γ를 만든다.
02 유한 부분집합을 본다
Γ의 어느 유한 부분 Δ를 택하든 c에 관한 조건은 유한 개만 들어 있다. 그
조건에 나오는 표준 수들보다 큰 자연수를 c로 해석하면 Δ를 표준 자연수에서
만족시킬 수 있다.
03 전체에 정리를 적용한다
모든 유한 부분집합에 모형이 있으므로 콤팩트성에 의해 Γ 전체에도 모형 M이
있다. 그 모형의 c는 모든 표준 수항보다 크다.
04 얻은 결론의 범위를 읽는다
표준 자연수에는 모든 자연수보다 큰 자연수가 없다. 따라서 M은 표준 자연수
구조와 동형이 아니다. 어떤 원소가 단지 매우 크다는 설명과 모든 표준 수항을
넘어선다는 조건을 구별한다.
각 유한한 요구는 표준 구조에서 만족된다. 모든 요구를 한꺼번에 만족시키는 모형에는
비표준 원소가 생긴다. [1]
부록 · 확장 예시
2. 정지 판정기의 가정을 시험하다
관련 개념 046 · 047
01 판정기를 가정한다
H(p, x)가 프로그램 p의 입력 x에서의 종료를 언제나 정확히 판정하고, H
자체도 모든 입력에서 종료한다고 가정한다.
02 반대로 행동하는 프로그램을 만든다
D(p)는 H(p, p)를 계산한다. H가 종료한다고 답하면 D는 무한 반복하고,
종료하지 않는다고 답하면 D는 즉시 종료하도록 정한다.
03 자기 코드를 입력한다
D 자신의 코드를 d라 하고 D(d)를 살핀다. H(d, d)가 종료라고 답하면 실제
D(d)는 반복한다. 비종료라고 답하면 실제 D(d)는 종료한다.
04 가정을 되짚는다
두 경우 모두 H의 정확성과 충돌한다. 따라서 모든 프로그램과 입력을 정확히
판정하며 종료하는 H는 존재하지 않는다. 특정 프로그램의 종료를 증명하는
일은 여전히 가능하다.
모순이 겨냥하는 것은 모든 경우에 답하는 일반 판정기다. 개별 사례나 제한된 언어의
판정 가능성은 따로 검토한다. [1, 2]
부록 · 확장 예시
3. 작은 모형에서 양상을 계산하다
관련 개념 062 · 063 · 068
01 모형을 고정한다
세계는 w, u, v 세 개다. w는 u와 v에만 접근한다. u에서 A는 참이고 v에서 A는
거짓이다. 우선 w 자신으로 향하는 관계는 두지 않는다.
02 가능성과 필연성을 판정한다
u라는 참인 접근 세계가 있으므로 w에서 ◇A는 참이다. v라는 거짓인 접근
세계가 있으므로 w에서 □A는 거짓이다. w에서의 A 값만으로 이 판정이
바뀌지는 않는다.
03 반사성을 추가한다
모든 세계가 자신에 접근하도록 관계를 바꾼다. 이제 □A가 참이라면 현재
세계도 그 검사 범위에 들어가므로 A가 참이어야 한다. 이것이 T의 □A → A와
연결된다.
04 공집합인 경우를 확인한다
어떤 세계에 접근 세계가 전혀 없으면 □A는 반례가 없어 참이고, ◇A는 증인이
없어 거짓이다. 이 경우를 배제하려면 모든 세계에 후속 세계가 있다는 관계
조건을 별도로 넣어야 한다.
화살표가 검사할 세계들을 정한다. 진리값의 배정과 접근 관계를 함께 바꾸거나
혼동하지 않는다. [3]
부록 · 확장 예시
4. 증명을 함수로 읽다
관련 개념 096 · 098 · 100
01 목표 유형을 정한다
A → A를 증명하는 과제를, A의 증거를 받아 A의 증거를 돌려주는 함수를 만드는
과제로 읽는다. 이 예시는 단순유형 람다 계산의 수학적 표기다.
02 가정을 입력으로 둔다
x : A라고 가정한다. x 자체가 이미 A의 증거이므로 다른 정보를 만들 필요가
없다. 가정을 닫아 λx:A.x라는 함수를 얻는다.
03 적용을 계산한다
이 함수를 a : A에 적용하면 (λx:A.x)a가 a로 베타 환원된다. 함의의 도입 뒤
제거를 수행하는 증명의 우회가 함수의 계산과 대응한다.
04 확인한 내용을 구별한다
유형 검사는 이 항의 유형이 A → A인지 판정한다. 임의의 현실적 주장 A가 이미
참이라고 선언하는 것은 아니다. 보조기에 형식화할 때도 목표와 가정, 추가
공리를 명확히 적는다.
명제와 유형, 증명과 항, 증명 정규화와 계산 사이의 대응을 구체적인 항등함수에서
확인할 수 있다. [1, 6]
부록 · 답안
생각해 보기 길잡이
1장 · 001 - 005 · 논리학을 논리학의 대상으로 삼다
001 메타논리
1 증명 체계 자체의 성질을 다루므로 메타논리의 수준이다.
2 그 자체로는 체계 안의 증명이다. 체계의 성질에 관한 정리를 증명할 때 메타정리가
된다.
002 구문론
1 참인지의 판단에는 해석이 필요하다. 구문론은 식의 구성과 형식적 도출을 다룬다.
2 어떤 배열을 논리식으로 인정하는지 정한 구문 규칙에서 묻는다.
003 의미론
1 주어진 해석과 각 연결사·양화사의 의미 규칙을 기준으로 정한다.
2 잘 구성되었다는 것은 구문적 조건이다. 참인지는 별도로 해석해야 한다.
004 형식체계
1 식의 구성 규칙과 공리·추론 규칙 등도 정해야 한다.
2 그렇다. 같은 언어를 쓰면서 서로 다른 도출 관계를 갖는 체계를 만들 수 있다.
005 공리화
1 무한한 공리 집합이나 공리 도식을 사용할 수도 있다.
2 공리는 출발점이다. 귀결은 그 출발점에서 논리적으로 따라오는 문장이다.
부록 · 답안
생각해 보기 길잡이
1장 · 006 - 010 · 논리학을 논리학의 대상으로 삼다
006 이론
1 T에 들어 있는 모든 문장을 함께 만족한다.
2 귀결에 대해 닫혀 있을 것을 요구하는 관례도 있다. 해당 문헌의 정의를 확인한다.
007 증명가능성
1 선택한 증명 체계의 형식적 도출 관계를 나타낸다.
2 탐색의 실패만으로 결론 내릴 수 없다. 증명이 존재하지 않음을 별도로 보여야 한다.
008 논리적 귀결
1 모든 Γ의 모형을 대상으로 해야 한다. 하나의 모형만으로는 충분하지 않다.
2 Γ ⊨ A가 성립하지 않음을 보여 주는 반모형이다.
009 논리상항
1 개체상항은 특정 대상을 지시하도록 해석되는 비논리 기호로 다룬다.
2 논리성의 기준 자체가 연구 주제다. 여기서는 선택한 논리의 통상적 구별을 따른다.
010 메타정리
1 도출 관계와 의미론적 귀결을 연결하는 메타수준의 정리다.
2 그렇다. 명시한 가정과 메타이론을 바탕으로 증명해야 한다.
부록 · 답안
생각해 보기 길잡이
2장 · 011 - 015 · 논리 체계의 힘을 측정하다
011 건전성
1 형식적 도출인 Γ ⊢ A에서 출발한다.
2 기초편은 타당하고 전제가 참인 개별 논증을 말한다. 여기서는 증명 체계와
의미론의 관계를 말한다.
012 완전성
1 완전성 정리는 모든 Γ의 모형에서 참일 때 적용된다.
2 충돌하지 않는다. 논리의 완전성과 특정 산술 이론이 모든 문장을 결정한다는
성질은 다르다.
013 무모순성
1 무모순성은 충돌을 배제할 뿐, 모든 문장의 증명이나 반증을 보장하지 않는다.
2 건전한 체계에서는 모형의 존재가 무모순성을 보장한다.
014 이론의 완전성
1 T의 언어로 된 모든 닫힌 문장을 대상으로 한다.
2 고전논리의 모순된 이론도 모든 문장을 증명하므로, 결정 성질만으로 충돌이
배제되지는 않는다.
015 공리의 독립성
1 A는 나머지 공리들에 대해 독립적이지 않다.
2 집합 전체의 독립성을 보이려면 각 공리에 대해 같은 종류의 검토를 해야 한다.
부록 · 답안
생각해 보기 길잡이
2장 · 016 - 020 · 논리 체계의 힘을 측정하다
016 보수적 확장
1 정의적 확장처럼 기존 언어의 귀결을 늘리지 않는 경우가 있다.
2 확장 전에 사용하던 언어로 된 문장의 증명가능성을 비교한다.
017 결정가능성
1 종료의 보장과 실행 시간의 효율성은 별개의 조건이다.
2 거짓인 입력도 종료하여 정확히 거짓이라고 판정해야 결정 절차가 된다.
018 콤팩트성
1 각 유한 부분집합은 서로 다른 모형을 가져도 된다.
2 그럴 필요가 없다. 각 유한 부분에 유한 모형이 있어도 전체는 무한 모형만 가질 수
있다.
019 뢰벤하임-스콜렘 정리
1 기호와 식을 가산하게 나열할 수 있는 일차언어라는 조건이다.
2 원래 모형의 크기가 바뀌는 것은 아니다. 같은 이론을 만족하는 가산 모형의 존재를
보장한다.
020 범주성
1 범주성은 어느 기수의 모형을 비교하는지에 따라 달라진다.
2 범주성에는 해당 크기의 모든 모형 사이에 동형이 필요하다. 초등동치만으로는
부족하다.
부록 · 답안
생각해 보기 길잡이
3장 · 021 - 025 · 모형으로 논리의 세계를 해석하다
021 모형이론
1 동형이 아닌 여러 모형을 갖는 이론도 많다.
2 어떤 관계와 연산을 표현할 수 있는지가 언어에 따라 달라지기 때문이다.
022 구조
1 언어에 포함된 개체상항·함수·술어의 해석도 주어야 한다.
2 그 구조가 T의 모든 문장을 만족할 때 T의 모형이라 부른다.
023 동형
1 언어에 지정된 상항·연산·관계도 보존해야 한다.
2 같은 언어의 일차 문장에 같은 진리값을 부여하므로 구별되지 않는다.
024 초등동치
1 그렇지 않다. 순서 구조로서 유리수와 실수는 크기가 달라도 초등동치다.
2 그렇다. 동형은 모든 일차 문장의 참을 보존한다.
025 부분구조
1 그 함수에 대해 닫혀 있지 않으므로 해당 언어의 부분구조가 될 수 없다.
2 양화 문장의 참이 달라질 수 있으므로 일반적으로 성립하지 않는다.
부록 · 답안
생각해 보기 길잡이
3장 · 026 - 030 · 모형으로 논리의 세계를 해석하다
026 초등부분구조
1 작은 구조의 대상을 매개변수로 넣은 식까지 보존해야 한다.
2 그렇다. 매개변수가 없는 닫힌 문장도 그 조건에 포함된다.
027 정의가능성
1 언어의 기호와 해석에 따라 표현할 수 있는 집합이 달라진다.
2 그렇다. 매개변수 허용 여부에 따라 정의가능성이 달라질 수 있다.
028 양화사 제거
1 모든 식에 대한 변환 가능성을 보여야 이론의 양화사 제거가 된다.
2 x = 0, z = 1이면 사이의 정수가 없으므로 성립하지 않는다.
029 비표준 모형
1 지정된 산술 이론을 만족하면서도 표준 자연수 구조와 동형이 아니다.
2 각각의 표준 자연수보다 크므로 어느 표준 자연수와도 같지 않다.
030 유형
1 특정 모형에서 빠져 있는 유형도 있다. 위 조건은 표준 자연수에서는 실현되지
않는다.
2 여기서는 원소의 성질을 모은 식의 집합이다. 유형이론의 표현 분류와 구별한다.
부록 · 답안
생각해 보기 길잡이
4장 · 031 - 035 · 증명의 구조를 분석하다
031 증명이론
1 그렇다. 증명을 유한한 기호 구조로 보고 성질을 분석한다.
2 의미론은 해석과 참의 조건을, 증명이론은 도출의 구성과 변환을 중심으로 다룬다.
032 시퀀트
1 고전 다중 결론 시퀀트에서는 적어도 하나가 참이면 된다.
2 ⇒는 시퀀트의 양쪽을 나누고, →는 논리식 안의 조건문을 만든다.
033 시퀀트 계산
1 전체 증명이 목표로 하는 최종 추론 상황이다.
2 오른쪽에 허용하는 식의 수와 규칙 등에 차이가 있을 수 있다.
034 구조 규칙
1 선형논리나 순서논리 등에서는 특정 구조 규칙을 제한한다.
2 가정의 중복 사용과 축약 규칙의 허용 여부를 살펴야 한다.
035 절단 규칙
1 첫 증명의 결론이자 다음 증명의 가정인 A다.
2 그렇다. 따로 얻은 결론을 중간 근거로 이용하는 구조를 표현한다.
부록 · 답안
생각해 보기 길잡이
4장 · 036 - 040 · 증명의 구조를 분석하다
036 절단 제거
1 증명의 크기가 오히려 크게 늘어날 수 있다.
2 추가한 공리와 규칙에 따라 달라지므로 해당 체계에서 다시 확인해야 한다.
037 부분식 성질
1 A와 B가 부분식이며, A ∧ B 자체도 부분식으로 센다.
2 양화사 규칙에서 생기는 대입 사례를 포함하도록 정확한 정식화를 확인해야 한다.
038 정규화
1 증명 변환에서는 최종 결론과 필요한 가정을 유지해야 한다.
2 종료성은 체계마다 다르다. 무유형 람다 계산에는 끝나지 않는 환원이 있다.
039 증명 복잡도
1 선택한 증명 체계, 식의 표현 방식, 길이를 세는 기준 등에 따라 달라진다.
2 완전성은 증명의 존재를 보장하며, 짧은 길이나 빠른 탐색까지 보장하지는 않는다.
040 구성적 증명
1 대상 하나와 그 대상이 P를 만족한다는 증명이 들어 있다.
2 전칭 증명에는 임의의 대상에 적용되는 근거가 필요하다.
부록 · 답안
생각해 보기 길잡이
5장 · 041 - 045 · 계산의 가능성과 한계를 밝히다
041 계산가능성
1 유한한 규칙으로 무한히 반복할 수도 있다.
2 그렇다. 계산가능한 전함수의 절차는 모든 입력에서 종료하여 값을 낸다.
042 튜링 기계
1 상태와 전이 규칙은 유한하게 주어진다. 테이프는 필요한 만큼 사용할 수 있다고
가정한다.
2 기계적 계산의 성질을 연구하기 위한 수학적 모형이다.
043 처치-튜링 논제
1 명확히 정의된 두 계산 모형의 동등성은 수학적 정리로 증명할 수 있다.
2 기본 논제는 계산가능성에 관한 것이다. 계산 시간의 효율성은 별도로 다룬다.
044 계산적 열거가능성
1 결정가능 집합은 열거가능하지만 그 역은 일반적으로 성립하지 않는다.
2 그때까지 증명을 찾지 못했다는 것만 알 수 있다. 정리가 아님이 확인된 것은
아니다.
045 결정불가능성
1 개별 사례나 제한된 하위 문제는 해결할 수 있다.
2 모든 입력에서 종료하며 정확히 판정하는 알고리즘 자체가 없다는 뜻이다.
부록 · 답안
생각해 보기 길잡이
5장 · 046 - 050 · 계산의 가능성과 한계를 밝히다
046 정지 문제
1 모든 경우에 정확히 답하고 종료하는 알고리즘은 존재하지 않는다.
2 그런 개별 사례는 쉽게 판정할 수 있다. 정리는 전체 문제의 일반 알고리즘에 관한
것이다.
047 환원
1 A도 결정가능하다. f를 계산한 뒤 B의 판정기를 사용한다.
2 B도 결정불가능하다. B가 결정가능하다고 하면 A까지 결정되어 모순이다.
048 원시재귀함수
1 그렇다. 정의 규칙에 따라 항상 종료하는 전함수다.
2 아니다. 아커만 함수처럼 전함수로 계산가능하지만 원시재귀는 아닌 예가 있다.
049 부분재귀함수
1 모든 입력에 값이 있는 전함수도 부분함수의 특수한 경우에 포함된다.
2 부분재귀함수와 튜링 계산가능한 부분함수는 같은 함수 부류를 이룬다.
050 람다 계산
1 (λx.x)z는 z로 환원된다.
2 끝없이 환원되는 항도 있다. 종료 성질은 유형 체계와 계산 규칙에 따라 달라진다.
부록 · 답안
생각해 보기 길잡이
6장 · 051 - 055 · 산술로 증명의 한계를 묻다
051 페아노 산술
1 산술식 각각에 대응하는 공리 도식으로 주어지므로 무한히 많은 사례가 있다.
2 일차 PA에는 비표준 모형도 있다.
052 괴델 번호화
1 A라는 기호 표현의 코드다. 참이나 거짓의 값과 다르다.
2 표현을 효과적으로 다루고 복원할 수 있는 적절한 부호화 조건을 갖추어야 한다.
053 대각화 보조정리
1 형식체계 안에서 동치가 증명된다는 뜻이다. 기호 배열이 동일할 필요는 없다.
2 구문을 부호화하고 필요한 대입 계산을 표현할 만큼의 산술적 조건이 필요하다.
054 증명가능성 술어
1 서로 다른 식이다. 하나는 A의 증명가능성을 말하고, 다른 하나는 A 자체다.
2 공리와 규칙을 바꾸면 어떤 문장이 증명되는지도 달라질 수 있기 때문이다.
055 제1불완전성 정리
1 산술적 표현력과 효과적 공리화 등 정리의 조건을 갖춘 체계에 적용된다.
2 표준 모형의 참과 특정 공리계의 증명가능성을 구별해야 한다는 점을 드러낸다.
부록 · 답안
생각해 보기 길잡이
6장 · 056 - 060 · 산술로 증명의 한계를 묻다
056 제2불완전성 정리
1 정리는 자기 체계 안의 증명에 관한 것이다. 더 강한 체계에서의 증명은 별도로
검토한다.
2 표준적인 증명가능성 술어와 도출 조건 등 정확한 가정을 확인해야 한다.
057 타르스키의 진리 정리
1 더 풍부한 메타언어에서 말할 수 있다. 정리는 같은 산술언어 내부의 전체 진리
정의를 제한한다.
2 정리는 산술 문장 전체에 관한 것이다. 제한된 복잡도의 문장에는 부분 진리 정의가
가능하다.
058 상대적 무모순성
1 Con(S)라는 가정이나 그 증명이 추가로 필요하다.
2 반대 방향은 별도로 증명해야 한다.
059 독립 명제
1 공리를 추가하거나 바꾸면 그 문장이 결정될 수 있다.
2 건전성에 의해 기존 공리에서 A도 ¬A도 도출할 수 없음을 보여 준다.
060 힐베르트 프로그램
1 정한 방법으로 형식체계의 무모순성을 정당화하는 목표가 더 있다.
2 체계별 증명력, 상대적 무모순성, 허용할 증명 방법을 분석하는 연구로 이어졌다.
부록 · 답안
생각해 보기 길잡이
7장 · 061 - 065 · 가능성과 필연성을 해석하다
061 양상논리
1 현재의 참만으로 다른 접근 가능한 세계에서의 참까지 보장되지 않는다.
2 기본 양상논리의 □와 ◇는 확률을 수치화하는 기호가 아니다.
062 필연성
1 wRw가 있을 때 현재 세계도 검사 대상에 들어간다.
2 표준 크립키 의미론에서는 반례가 없으므로 □A가 참이다.
063 가능성
1 가능성은 한 세계로 충분하므로 필연성까지 따라오지는 않는다.
2 참인 사례가 없으므로 ◇A는 거짓이다.
064 가능세계
1 논리 모형에서는 목적에 맞게 정한 상태나 평가 지점으로 사용할 수 있다.
2 원자식의 참은 세계별로 다르게 배정할 수 있다.
065 접근가능성 관계
1 대칭성을 가정하지 않으면 반대 방향의 접근은 보장되지 않는다.
2 각 세계 w가 자기 자신에 접근하는 wRw를 요구한다.
부록 · 답안
생각해 보기 길잡이
7장 · 066 - 070 · 가능성과 필연성을 해석하다
066 크립키 의미론
1 틀은 보통 (W, R)이고, 모형은 거기에 원자식의 참을 정하는 V를 더한 것이다.
2 같은 세계와 접근 관계에도 여러 진리값 배정을 줄 수 있다.
067 정상 양상논리
1 일반적인 필연화 규칙은 열린 가정 A에 그렇게 적용할 수 없다.
2 체계 K다. 추가 양상 공리 없이 공리 K와 기본 규칙으로 출발한다.
068 체계 T
1 현재 세계도 접근 가능한 세계에 포함되므로 □A의 참 조건에 들어간다.
2 T 공리는 반대 방향인 □A → A다. A → □A는 일반적으로 타당하지 않다.
069 체계 S4
1 접근 관계의 추이성을 요구한다.
2 대칭성은 S4의 기본 틀 조건에 포함되지 않는다.
070 체계 S5
1 여러 동치류를 허용한다. 모든 세계 사이의 보편 관계만을 요구하는 것은 아니다.
2 그렇다. 자기 자신을 포함하여 동치류 안의 모든 세계가 서로 접근한다.
부록 · 답안
생각해 보기 길잡이
8장 · 071 - 075 · 시간·지식·의무의 논리를 읽다
071 시간논리
1 선택한 연산자의 의미 규칙을 정할 때 명시한다.
2 한 시점의 참으로 모든 시점의 참을 보장할 수 없다.
072 선형시간논리
1 미래의 한 시점에서만 A가 참일 수 있으므로 일반적으로 성립하지 않는다.
2 선형시간 예시에서는 현재를 포함하도록 정의한다.
073 분기시간논리
1 A에 도달하지 않는 다른 경로가 있으면 AF A는 거짓일 수 있다.
2 경로마다 A가 성립하는 시점이 달라도 된다.
074 인식논리
1 지식의 사실성을 가정하므로 Ki A에서 A가 따라온다.
2 이상화된 모형의 특징이다. 실제 사람의 계산 능력을 그대로 기술한다고 볼 수는
없다.
075 공통지식
1 서로가 안다는 사실을 모를 수 있으므로 별개다.
2 표준 공통지식은 모든 유한한 깊이의 반복을 요구한다.
부록 · 답안
생각해 보기 길잡이
8장 · 076 - 080 · 시간·지식·의무의 논리를 읽다
076 믿음논리
1 믿음만으로 사실의 참이 보장되지는 않는다.
2 여러 체계가 있다. KD45는 일관성과 자기 믿음에 대한 이상화된 성찰을 가정한 한
모형이다.
077 의무논리
1 의무를 위반하는 현실도 표현해야 하므로 O A와 A를 구별한다.
2 표준 의무논리는 일반적으로 O A → A를 요구하지 않는다.
078 허용과 금지
1 허용은 의무보다 약한 조건이다. 해도 된다는 것에서 반드시 해야 함이 따라오지는
않는다.
2 A를 하지 않아야 한다는 O¬A다.
079 반사실 조건문
1 반사실 조건문은 실질조건문과 다른 의미론을 사용하므로 그렇게 처리하지 않는다.
2 어떤 배경 조건을 유지하는지에 따라 후건의 성립이 달라질 수 있기 때문이다.
080 동적논리
1 표준 프로그램 동적논리의 [α]A는 종료하는 실행의 결과를 말하며, 종료 자체는
별도 조건이다.
2 종료하여 A인 상태에 도달하는 실행이 적어도 하나 있을 것을 요구한다.
부록 · 답안
생각해 보기 길잡이
9장 · 081 - 085 · 고전논리의 가정을 바꾸다
081 비고전논리
1 여러 목적과 규칙을 가진 다양한 논리 계열을 가리킨다.
2 증명의 뜻, 진리값, 구조 규칙 등 서로 다른 지점을 바꾼다.
082 직관주의 논리
1 일반 원리로 채택하지 않는다는 뜻이다. 결정 가능한 명제의 배중률은 증명할 수
있다.
2 통상적인 구성적 해석에서는 대상과 그 대상이 조건을 만족한다는 증거를 준다.
083 배중률
1 어느 쪽인지를 알려 주는 판정 절차까지 포함하는 것은 아니다.
2 A의 증거나 ¬A의 증거를 구성할 수 있는 경우에는 그 선언을 증명할 수 있다.
084 이중부정 제거
1 직관주의에서도 증명할 수 있다.
2 일반적으로 같은 정보를 주지 않는다. 특정 명제나 추가 원리에서는 제거가 가능할
수 있다.
085 다치논리
1 연결사의 계산 규칙과 귀결에서 보존할 지정값도 정해야 한다.
2 여기서는 미정이라는 의미의 값이다. 확률 1/2과 동일시하지 않는다.
부록 · 답안
생각해 보기 길잡이
9장 · 086 - 090 · 고전논리의 가정을 바꾸다
086 퍼지논리
1 정도의 값과 확률은 다른 해석이다. 어떤 성질을 수치화하는지 먼저 명시해야 한다.
2 여러 연산 체계가 있다. 이 페이지는 최소·최대와 1 − A의 방식만 예시한다.
087 파라일관 논리
1 모순에서 모든 결론이 따라오지 않도록 하는 추론 성질이다. 모든 모순의 사실적
수용을 뜻하지 않는다.
2 폭발을 일반적으로 허용하지 않는 것이 핵심이다.
088 폭발 원리
1 임의의 B를 대상으로 하므로 별도의 내용 제한이 없다.
2 표준 직관주의 논리는 ⊥에서 임의의 결론을 얻는 폭발을 허용한다. 배중률 문제와
구별한다.
089 관련논리
1 변수 공유만으로 충분하지 않다. 선택한 체계의 추론 규칙과 의미론을 만족해야
한다.
2 논리 체계의 규칙과 의미 조건으로 명시하는 관련성이다.
090 선형논리
1 자유로운 복제를 허용하지 않으므로 일반적으로 얻을 수 없다.
2 ! 같은 지수 연산자로 통제된 재사용을 표현할 수 있다.
부록 · 답안
생각해 보기 길잡이
10장 · 091 - 095 · 언어와 증명의 차원을 넓히다
091 이차논리
1 성질이나 관계를 나타내는 고차의 변수다.
2 같은 구문에도 여러 의미론을 줄 수 있으므로 별도의 해석 규칙이 필요하다.
092 전체 의미론
1 이차 변수의 값으로 허용할 모든 관계를 빠짐없이 포함한다는 뜻이다.
2 전체 이차 의미론의 타당성을 정확히 포착하는 효과적인 건전·완전 증명 체계는
없다.
093 헨킨 의미론
1 그렇다. 어떤 관계를 양화 범위에 넣는지 모형에서 지정한다.
2 헨킨 의미론에서는 허용된 성질만 대상으로 하므로 전체 의미론의 범주성을 그대로
얻지 못한다.
094 고차논리
1 각 차수에서 허용하는 값과 양화 범위를 계속 명시해야 한다.
2 고차언어와 유형을 정하여 그런 대상을 표현할 수 있다.
095 유형이론
1 각 표현이 들어갈 자리를 유형 규칙으로 제한한다.
2 입출력의 유형을 말한다. 원하는 계산을 수행한다는 더 구체적인 성질은 별도로
증명한다.
부록 · 답안
생각해 보기 길잡이
10장 · 096 - 100 · 언어와 증명의 차원을 넓히다
096 단순유형 람다 계산
1 같은 유형 A다. 전체 함수의 유형은 A → A다.
2 추가 규칙은 종료 성질을 바꿀 수 있다. 강한 정규화는 여기서 명시한 기본 체계의
성질이다.
097 의존유형
1 다른 유형뿐 아니라 자연수 n 같은 값에 의존할 수 있다.
2 길이 조건이 다르므로 자동으로 같은 유형의 항으로 사용할 수 없다.
098 커리-하워드 대응
1 해당 대응에 맞는 유형 규칙을 만족하는 항이어야 하며, 사용한 공리와 계산 체계도
확인해야 한다.
2 A의 증거를 받아 B의 증거를 만들어 낸다.
099 형식검증
1 모형과 가정의 범위에서 보장한다. 명세의 누락과 구현의 불일치도 검토해야 한다.
2 시험은 실행 사례를 관찰하고, 형식검증은 정한 모형과 규칙에서 성질을
증명하거나 체계적으로 검사한다.
100 정리증명 보조기
1 정해진 형식체계에서의 도출을 확인한다. 가정과 현실의 대응은 별도로 확인한다.
2 일반적인 자동 결정 능력을 보장하지 않는다. 사람의 형식화와 증명 구성, 필요한
보조 절차를 함께 사용한다.
부록 · 문헌
참고자료와 출처
1 / 4 · 각 장과 부록의 번호에 대응한다.
[1] 오픈 로직 프로젝트
『오픈 로직 텍스트』
The Open Logic Text
온라인 전체판. 구문·의미론, 증명 체계, 완전성·콤팩트성, 계산가능성, 불완전성,
고차논리를 참고한다.
연결: 1~6장, 9~10장 및 정리의 조건·확장 예시
원문·공식 자료 열기
[2] 리처드 자크(Richard Zach)
『불완전성과 계산가능성: 괴델 정리의 열린 입문』
Incompleteness and Computability: An Open Introduction to Gödel’s Theorems
오픈 로직 프로젝트 기반 교재. 산술의 표현, 재귀함수, 대각화, 불완전성, 진리 정의의
논의를 참고한다.
연결: 5~6장 및 불완전성의 적용 조건
원문·공식 자료 열기
[3] 오드리 얍·리처드 자크(Audrey Yap · Richard Zach)
『만약 그렇다면? 비고전논리의 열린 입문』
What If? An Open Introduction to Non-Classical Logics
2025년 가을 편성본의 온라인판. 다치논리, 양상논리, 인식·시간논리, 직관주의와
조건논리를 참고한다.
연결: 7~9장 및 양상 모형의 확장 예시
원문·공식 자료 열기
https://builds.openlogicproject.org/open-logic-complete.pdf
https://ic.openlogicproject.org/ic-screen.pdf
https://builds.openlogicproject.org/courses/what-if/wi-screen.pdf
부록 · 문헌
참고자료와 출처
2 / 4 · 각 장과 부록의 번호에 대응한다.
[4] 데이비드 마커(David Marker)
『모형이론 I: 정의가능성 / II: 양화사 제거』
Model Theory I: Definability / II: Quantifier Elimination
2020년 MSRI 입문 강의. 구조와 이론, 초등동치, 정의가능성, 양화사 제거, 초등확장을
확인하는 자료다.
연결: 2~3장. 저자 홈페이지의 MSRI 입문 강의 1·2 및 모형이론 교재 안내
원문·공식 자료 열기
[5] 프랭크 페닝(Frank Pfenning)
『선형논리 강의 노트』
15-816 Linear Logic: Lecture Notes
카네기멜런대학교, 2012. 특히 Cut Elimination(절단 제거), Choice and
Replication(선택과 복제)을 참고한다.
연결: 4장과 9장의 절단 제거·구조 규칙·자원 사용
원문·공식 자료 열기
[6] 제러미 애비거드 등(Jeremy Avigad et al.)
『린 4로 정리 증명하기』
Theorem Proving in Lean 4
공식 교재의 Introduction, Dependent Type Theory, Propositions and Proofs를
참고한다. 이 책의 람다식은 특정 버전의 실행 코드가 아닌 수학적 예시다.
연결: 10장. 유형·명제와 증명·커널 검사의 역할
원문·공식 자료 열기
https://homepages.math.uic.edu/~marker/
https://www.cs.cmu.edu/~fp/courses/15816-s12/schedule.html
https://lean-lang.org/theorem_proving_in_lean4/
부록 · 문헌
참고자료와 출처
3 / 4 · 각 장과 부록의 번호에 대응한다.
[7] 레슬리 램포트(Leslie Lamport)
『시스템 명세하기』
Specifying Systems
Addison-Wesley, 2002. 상태·실행·시간 조건과 명세 검토의 관계를 이해하는 후속
읽기 자료다.
연결: 8·10장의 시스템 명세와 형식검증
원문·공식 자료 열기
[8] 올라프 바이어스도르프 등(Olaf Beyersdorff et al.)
『CTL 모형 검사는 거의 언제나 본질적으로 순차적이다』
Model Checking CTL is Almost Always Inherently Sequential
Logical Methods in Computer Science 7(2:12), 2011, 1~21쪽. 2.1절의 CTL
경로 양화와 시간 연산자 정의를 참고한다.
연결: 8장 073 및 시간 기호 설명
원문·공식 자료 열기
문헌을 읽을 때
책의 번호와 원자료의 장 번호는 서로 다르다. 원자료에서는 용어의 정의, 정리의
가정, 사용한 증명 체계와 의미론을 함께 확인한다. 본문의 예시는 해당 개념을
설명하기 위해 별도로 구성했다.
https://lamport.azurewebsites.net/tla/book.html
https://arxiv.org/abs/1103.4990
부록 · 출처 고지
자료 이용과 구성
이 책은 개념의 핵심을 한국어로 새롭게 설명하고 예시·질문·도식을 새로 구성한
시리즈 원고다. 각 장과 부록의 [번호]는 아래 참고자료에 대응한다. 참고자료의
문장이나 도판을 그대로 옮긴 번역서는 아니다.
오픈 로직 프로젝트의 The Open Logic Text, 리처드 자크의 Incompleteness
and Computability, 오드리 얍·리처드 자크의 What If?는 CC BY 4.0에 따라
제공된다. 해당 자료를 토대로 재구성한 설명의 출처를 밝히며, 원저자의 본서
승인이나 보증을 뜻하지 않는다.
본문의 한국어 서술·예시와 페이지 도식은 본서의 구성에 맞추어 작성했다.
원자료의 표지 그림·사진·별도 라이선스 도판은 사용하지 않았다. 그 밖의
참고자료는 개념 확인과 후속 읽기를 위한 서지로 제시한다.
온라인 자료 확인 기준: 2026년 9월 17일. 온라인 교재는 개정될 수 있으므로
문헌의 판본과 해당 절을 확인한다. CC BY 4.0의 이용 조건은 아래 링크에서
확인할 수 있다.
CC BY 4.0 이용 조건
https://creativecommons.org/licenses/by/4.0/
논리학 36권 시리즈 · 4
논리 체계 자체를
연구하는 언어
논리 체계를 탐구하는 100개의 개념어.
논리를 바라보는 관점을 넓히고,
체계의 성질과 한계를 연구하는 언어를 익힌다.
논리학 개념어 100
02 기초편 · 논증을 읽는 언어
03 중급편 · 논리를 형식화하고 계산하는 언어
04 고급편 · 논리 체계 자체를 연구하는 언어
한국논리학협회
이호찬
에듀이음
차례
이 책을 읽는 방법
프롤로그
1장 논리학을 논리학의 대상으로 삼다
001 메타논리
002 구문론
003 의미론
004 형식체계
005 공리화
006 이론
007 증명가능성
008 논리적 귀결
009 논리상항
010 메타정리
개념 연결하기
2장 논리 체계의 힘을 측정하다
011 건전성
012 완전성
013 무모순성
014 이론의 완전성
015 공리의 독립성
016 보수적 확장
017 결정가능성
018 콤팩트성
019 뢰벤하임-스콜렘 정리
020 범주성
개념 연결하기
3장 모형으로 논리의 세계를 해석하다
021 모형이론
022 구조
023 동형
024 초등동치
025 부분구조
026 초등부분구조
027 정의가능성
028 양화사 제거
029 비표준 모형
030 유형
개념 연결하기
4장 증명의 구조를 분석하다
031 증명이론
032 시퀀트
033 시퀀트 계산
034 구조 규칙
035 절단 규칙
036 절단 제거
037 부분식 성질
038 정규화
039 증명 복잡도
040 구성적 증명
개념 연결하기
5장 계산의 가능성과 한계를 밝히다
041 계산가능성
042 튜링 기계
043 처치-튜링 논제
044 계산적 열거가능성
045 결정불가능성
046 정지 문제
047 환원
048 원시재귀함수
049 부분재귀함수
050 람다 계산
개념 연결하기
6장 산술로 증명의 한계를 묻다
051 페아노 산술
052 괴델 번호화
053 대각화 보조정리
054 증명가능성 술어
055 제1불완전성 정리
056 제2불완전성 정리
057 타르스키의 진리 정리
058 상대적 무모순성
059 독립 명제
060 힐베르트 프로그램
개념 연결하기
7장 가능성과 필연성을 해석하다
061 양상논리
062 필연성
063 가능성
064 가능세계
065 접근가능성 관계
066 크립키 의미론
067 정상 양상논리
068 체계 T
069 체계 S4
070 체계 S5
개념 연결하기
8장 시간·지식·의무의 논리를 읽다
071 시간논리
072 선형시간논리
073 분기시간논리
074 인식논리
075 공통지식
076 믿음논리
077 의무논리
078 허용과 금지
079 반사실 조건문
080 동적논리
개념 연결하기
9장 고전논리의 가정을 바꾸다
081 비고전논리
082 직관주의 논리
083 배중률
084 이중부정 제거
085 다치논리
086 퍼지논리
087 파라일관 논리
088 폭발 원리
089 관련논리
090 선형논리
개념 연결하기
10장 언어와 증명의 차원을 넓히다
091 이차논리
092 전체 의미론
093 헨킨 의미론
094 고차논리
095 유형이론
096 단순유형 람다 계산
097 의존유형
098 커리-하워드 대응
099 형식검증
100 정리증명 보조기
개념 연결하기
에필로그
부록
개념어와 영어 표기
기호 읽기
주요 정리의 적용 조건
개념 비교표
확장 예시
생각해 보기 길잡이
참고자료와 출처
사전의 설명 범위
2·3·4권의 승인 원고를 바탕으로 구성했습니다. 기초편의 일상 논증부터 중급편의 형식화·계산, 고급편의 모형·증명·계산가능성과 비고전논리까지 다룹니다. 같은 이름도 논증이나 체계에 따라 뜻과 적용 조건이 다를 수 있으므로 권별 설명을 함께 확인해 주세요.
기존 수업 용어 11개의 그림·예시·출처도 보존했습니다. 함께 보기에는 관련 개념이 포함되며, 모두 같은 뜻이라는 의미는 아닙니다.
