논리학 (Logic)

논리학은 올바른 추론의 규칙을 연구하는 학문입니다. 수학에서는 명제의 참·거짓을 판별하고, 엄밀한 증명을 구성하기 위한 기초 도구로 활용됩니다. 아리스토텔레스의 삼단논법에서 시작하여 프레게, 러셀, 괴델에 이르기까지 수리논리학은 수학의 기초를 규명하는 핵심 분야로 발전해왔습니다.

일상 속 논리: 우리는 매일 논리를 사용합니다. "내일 비가 오면 우산을 가져가자", "시험이 끝나고 날씨가 좋으면 놀러 가자" — 이런 판단이 모두 논리입니다. 논리학은 이런 추론을 정확하게 다루는 방법을 알려줍니다.

왜 논리학을 배우는가? 수학의 모든 정리는 "~이면 ~이다"라는 형태의 논리적 추론으로 이루어져 있습니다. 논리학을 배우면, 어떤 주장이 정말로 맞는 것인지 판단하는 힘을 기를 수 있습니다. 또한 프로그래밍의 if-else 조건문, 검색 엔진의 AND/OR 검색, 법률의 조건 해석 등 실생활 곳곳에서 논리적 사고가 활용됩니다.

이런 곳에 쓰여요

프로그래밍: if-else 조건문은 논리학의 조건 명제와 같은 구조
법률: 계약서의 "A이고 B이면 C를 이행한다" 같은 조건 해석
회로 설계: 컴퓨터 칩의 AND, OR, NOT 게이트가 논리 연산 그 자체
토론·논증: 상대방 주장의 논리적 오류를 찾아내는 비판적 사고

선수 지식: 수학 입문

난이도: ★★☆☆☆ (고등학교 기초)

명제와 진릿값

명제(Proposition)는 참(True, T) 또는 거짓(False, F)이 분명하게 판별되는 문장입니다. 명제의 참·거짓을 진릿값(Truth Value)이라 합니다.

쉽게 말하면: 명제란 "맞아" 또는 "아니야"로 대답할 수 있는 문장입니다. "서울은 한국의 수도이다"는 "맞아(참)"라고 대답할 수 있으므로 명제입니다. "오늘 날씨 좋지?"는 질문이므로 명제가 아닙니다. "이 노래 좋다"는 사람마다 답이 다르므로 명제가 아닙니다. 핵심은 누가 판단하든 같은 답이 나오는가입니다.

명제의 예

문장	명제 여부	진릿값
$2 + 3 = 5$	명제	참 (T)
$\pi$는 유리수입니다	명제	거짓 (F)
모든 짝수는 2의 배수입니다	명제	참 (T)
$1 + 1 = 3$	명제	거짓 (F)
$x + 1 = 3$	명제 아님 (변수 포함)	—
수학은 재미있습니다	명제 아님 (주관적)	—
이 문장은 거짓이다	명제 아님 (역설)	—

명제를 보통 $p$, $q$, $r$ 등 소문자 알파벳으로 표기합니다. 더 이상 분해할 수 없는 명제를 원자 명제(Atomic Proposition), 논리 연산자로 결합된 명제를 복합 명제(Compound Proposition)라 합니다.

열린 문장과 명제: "$x + 1 = 3$"처럼 변수를 포함한 문장은 그 자체로는 명제가 아니지만, 변수에 값을 대입하거나 한정사를 붙이면 명제가 됩니다. 이런 문장을 열린 문장(Open Sentence) 또는 명제 함수(Propositional Function)라고 합니다.

논리 연산자

논리 연산자(Logical Connective)는 명제를 결합하거나 변형하여 새로운 명제를 만듭니다. 일상생활에서 "그리고", "또는", "~이 아니다", "~이면 ~이다" 같은 말이 논리 연산자에 해당합니다.

비유로 이해하기: 논리 연산자를 전기 스위치로 비유할 수 있습니다. AND는 직렬 연결(두 스위치 모두 켜야 전구가 켜짐), OR는 병렬 연결(하나만 켜도 전구가 켜짐), NOT은 스위치 반전(켜면 꺼지고, 끄면 켜짐)입니다. 아래 다이어그램에서 직접 확인해 봅시다.

부정 (NOT, $\neg$)

명제 $p$의 부정 $\neg p$는 $p$가 참이면 거짓, 거짓이면 참입니다. 쉽게 말해, 원래 문장에 "~이 아니다"를 붙이는 것입니다.

$p$	$\neg p$
T	F
F	T

예: $p$: "5는 소수이다" (참) → $\neg p$: "5는 소수가 아니다" (거짓)

논리곱 (AND, $\wedge$)

$p \wedge q$는 $p$와 $q$가 모두 참일 때만 참입니다.

예: "$3 > 2$이고 $4$는 짝수이다" — 두 부분 모두 참이므로 전체가 참.

실생활 예: "입장권도 있고 신분증도 있어야 입장할 수 있다" — 둘 중 하나라도 없으면 입장 불가입니다.

논리합 (OR, $\vee$)

$p \vee q$는 $p$와 $q$ 중 적어도 하나가 참이면 참입니다. 수학의 "또는"은 포함적 논리합(inclusive or)으로, 둘 다 참이어도 참입니다.

실생활 예: "현금 또는 카드로 결제할 수 있습니다" — 현금이든 카드든 하나만 있으면 됩니다. 둘 다 있어도 결제 가능합니다.

"또는"의 두 가지 뜻: 일상에서 "커피 또는 주스 중 하나를 고르세요"라고 하면 보통 하나만 고르라는 뜻입니다(배타적 또는). 하지만 수학에서 "또는"은 "둘 다도 괜찮다"는 뜻입니다(포함적 또는). 이 차이를 구분하는 것이 중요합니다.

배타적 논리합 (XOR, $\oplus$)

$p \oplus q$는 $p$와 $q$ 중 정확히 하나만 참일 때 참입니다.

$$p \oplus q \equiv (p \vee q) \wedge \neg(p \wedge q) \equiv (p \wedge \neg q) \vee (\neg p \wedge q)$$

조건 (IF-THEN, $\rightarrow$)

$p \rightarrow q$는 $p$가 참이고 $q$가 거짓일 때만 거짓입니다. "$p$이면 $q$이다"로 읽으며, $p$를 가정(hypothesis), $q$를 결론(conclusion)이라 합니다.

약속으로 이해하기: 조건문을 "약속"이라고 생각하면 이해하기 쉽습니다. 부모님이 "시험에서 100점을 받으면 게임기를 사줄게"라고 약속했다고 합시다. 이 약속이 깨지는 경우는 딱 하나입니다: 100점을 받았는데 게임기를 안 사주는 경우. 100점을 못 받았으면? 약속 자체가 해당되지 않으므로 게임기를 사주든 안 사주든 약속을 어긴 것은 아닙니다.

주의: 조건문에서 가정 $p$가 거짓이면 결론 $q$의 값에 관계없이 전체 조건문은 참입니다. 이를 공허한 참(vacuous truth)이라 합니다. 예: "0 = 1이면 하늘은 빨갛다"는 참입니다. 가정이 거짓이므로 결론이 무엇이든 상관없습니다.

비가 오는데 우산을 안 가져간 경우만 거짓 — 약속을 어긴 유일한 경우입니다. 비가 안 오면 우산을 가져가든 말든 약속은 지킨 것입니다 (공허한 참).

조건문의 변형

이름	형태	원래 조건문과의 관계
원래 조건문	$p \rightarrow q$	—
역(Converse)	$q \rightarrow p$	원래와 동치 아님
이(Inverse)	$\neg p \rightarrow \neg q$	원래와 동치 아님, 역과 동치
대우(Contrapositive)	$\neg q \rightarrow \neg p$	원래와 항상 동치

구체적인 예시로 이해하기: 원래 명제를 "비가 오면 땅이 젖는다" ($p \rightarrow q$)라고 합시다.

역: "땅이 젖으면 비가 온다" ($q \rightarrow p$) — 거짓일 수 있습니다. 스프링클러 때문에 젖었을 수도 있습니다.
이: "비가 안 오면 땅이 안 젖는다" ($\neg p \rightarrow \neg q$) — 역시 거짓일 수 있습니다.
대우: "땅이 안 젖었으면 비가 안 왔다" ($\neg q \rightarrow \neg p$) — 원래와 항상 같은 진릿값입니다!

왜 대우만 원래와 같은가? $p \rightarrow q$가 거짓이 되려면 "$p$가 참이고 $q$가 거짓"이어야 합니다. 대우 $\neg q \rightarrow \neg p$가 거짓이 되려면 "$\neg q$가 참이고 $\neg p$가 거짓"이어야 하는데, 이는 곧 "$q$가 거짓이고 $p$가 참"과 같습니다. 결국 두 명제가 거짓이 되는 조건이 정확히 같으므로 항상 동치입니다. 반면 역($q \rightarrow p$)은 "$q$가 참이고 $p$가 거짓"일 때 거짓이므로, 원래 명제와 거짓이 되는 조건이 다릅니다.

대우 증명: $p \rightarrow q$를 직접 증명하기 어려울 때, 대우 $\neg q \rightarrow \neg p$를 증명하면 됩니다. 두 명제는 논리적으로 동치이기 때문입니다.

쌍조건 (IFF, $\leftrightarrow$)

$p \leftrightarrow q$는 $p$와 $q$의 진릿값이 같을 때 참입니다. "필요충분조건" 또는 "$p$일 때, 그리고 그때에만 $q$"라고도 합니다.

$$p \leftrightarrow q \equiv (p \rightarrow q) \wedge (q \rightarrow p)$$

실생활 예: "시험에 합격한다 $\leftrightarrow$ 60점 이상을 받는다"는 쌍조건입니다. 합격하면 반드시 60점 이상이고, 60점 이상이면 반드시 합격합니다. 한쪽 방향만 성립하는 것이 아니라 양쪽 모두 성립해야 쌍조건이 참이 됩니다.

진리표

진리표(Truth Table)는 논리식에 포함된 명제의 모든 진릿값 조합에 대해 결과를 나열한 표입니다. $n$개의 명제 변수가 있으면 $2^n$개의 행이 필요합니다.

진리표 읽는 법: 진리표는 "모든 가능한 경우"를 빠짐없이 나열한 것입니다. 예를 들어 $p$, $q$ 두 명제가 있으면 각각 참(T) 또는 거짓(F)이므로 총 $2 \times 2 = 4$가지 경우가 있습니다. 진리표의 각 행은 하나의 경우이고, 마지막 열에서 전체 논리식의 참·거짓을 확인할 수 있습니다.

기본 연산 종합 진리표

$p$	$q$	$\neg p$	$p \wedge q$	$p \vee q$	$p \oplus q$	$p \rightarrow q$	$p \leftrightarrow q$
T	T	F	T	T	F	T	T
T	F	F	F	T	T	F	F
F	T	T	F	T	T	T	F
F	F	T	F	F	F	T	T

추가 연산자

$p$	$q$	$p \uparrow q$ (NAND)	$p \downarrow q$ (NOR)
T	T	F	F
T	F	T	F
F	T	T	F
F	F	T	T

기능적 완전성: NAND($\uparrow$)만으로 모든 논리 연산을 표현할 수 있습니다. NOR($\downarrow$)도 마찬가지입니다. 이를 기능적 완전성(Functional Completeness)이라 합니다. 따라서 $\{\neg, \wedge\}$, $\{\neg, \vee\}$, $\{\uparrow\}$, $\{\downarrow\}$ 등은 모두 기능적으로 완전한 연산자 집합입니다.

항진명제, 모순명제, 우발명제

항진명제(Tautology): 모든 진릿값 조합에서 참인 논리식. 예: $p \vee \neg p$
모순명제(Contradiction): 모든 진릿값 조합에서 거짓인 논리식. 예: $p \wedge \neg p$
우발명제(Contingency): 항진명제도 모순명제도 아닌 논리식. 예: $p \vee q$

쉽게 이해하기:

항진명제: "내일 비가 오거나 안 온다" — 무조건 참입니다. 비가 오든 안 오든 둘 중 하나는 반드시 맞습니다.
모순명제: "내일 비가 오면서 동시에 안 온다" — 무조건 거짓입니다. 이런 일은 절대 불가능합니다.
우발명제: "내일 비가 온다" — 참일 수도, 거짓일 수도 있습니다. 실제 날씨에 따라 달라집니다.

논리적 동치 법칙

두 논리식이 모든 진릿값 조합에서 같은 결과를 가지면 논리적 동치(Logically Equivalent)라 하며 $\equiv$로 표기합니다.

왜 논리적 동치가 중요한가? 논리적 동치를 이용하면 복잡한 논리식을 더 단순한 형태로 변환할 수 있습니다. 이것은 수학에서 복잡한 식을 정리하는 것과 같습니다. 예를 들어, $a + 0 = a$라는 사실을 알면 불필요한 $+ 0$을 제거하여 식을 간단하게 만들 수 있습니다. 마찬가지로 $p \wedge \text{T} \equiv p$라는 동치 법칙을 알면 논리식을 간결하게 정리할 수 있습니다. 이러한 법칙들은 집합론의 연산 법칙과 정확히 대응합니다.

법칙	동치식
이중부정	$\neg(\neg p) \equiv p$
교환법칙	$p \wedge q \equiv q \wedge p$, $p \vee q \equiv q \vee p$
결합법칙	$(p \wedge q) \wedge r \equiv p \wedge (q \wedge r)$, $(p \vee q) \vee r \equiv p \vee (q \vee r)$
분배법칙	$p \wedge (q \vee r) \equiv (p \wedge q) \vee (p \wedge r)$
	$p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r)$
드모르간	$\neg(p \wedge q) \equiv \neg p \vee \neg q$, $\neg(p \vee q) \equiv \neg p \wedge \neg q$
항등법칙	$p \wedge \text{T} \equiv p$, $p \vee \text{F} \equiv p$
지배법칙	$p \vee \text{T} \equiv \text{T}$, $p \wedge \text{F} \equiv \text{F}$
멱등법칙	$p \wedge p \equiv p$, $p \vee p \equiv p$
흡수법칙	$p \vee (p \wedge q) \equiv p$, $p \wedge (p \vee q) \equiv p$
보원법칙	$p \vee \neg p \equiv \text{T}$, $p \wedge \neg p \equiv \text{F}$
조건문 변환	$p \rightarrow q \equiv \neg p \vee q$
쌍조건 변환	$p \leftrightarrow q \equiv (p \rightarrow q) \wedge (q \rightarrow p)$
대우	$p \rightarrow q \equiv \neg q \rightarrow \neg p$

드모르간 법칙 — 실생활 예시: $\neg(p \wedge q) \equiv \neg p \vee \neg q$를 실생활로 풀어보겠습니다. "영희는 키도 크고 달리기도 빠르다"의 부정은 "영희는 키가 크지 않거나 달리기가 빠르지 않다"입니다. 둘 다 갖추는 것의 부정은, 적어도 하나를 갖추지 못하는 것입니다. 이것이 드모르간 법칙의 핵심이며, 집합론의 드모르간 법칙과 정확히 같은 구조입니다.

동치 증명 예시

$p \rightarrow q \equiv \neg p \vee q$임을 진리표로 확인합니다.

$p$	$q$	$p \rightarrow q$	$\neg p$	$\neg p \vee q$
T	T	T	F	T
T	F	F	F	F
F	T	T	T	T
F	F	T	T	T

$p \rightarrow q$와 $\neg p \vee q$ 열이 동일하므로 동치입니다. $\blacksquare$

추론 규칙

추론 규칙(Rule of Inference)은 알려진 명제(전제)로부터 새로운 명제(결론)를 도출하는 논리적 도구입니다.

쉽게 말하면: 추론 규칙은 "이것이 사실이면, 저것도 반드시 사실이다"라는 것을 보장하는 논리의 도구입니다. 예를 들어, "비가 오면 길이 젖는다"가 사실이고 "지금 비가 온다"가 사실이면, "지금 길이 젖었다"라고 결론 내릴 수 있습니다. 이것이 긍정 논법(Modus Ponens)이며, 가장 기본적인 추론 규칙입니다.

이름	전제	결론	형태
긍정 논법 (Modus Ponens)	$p$, $p \rightarrow q$	$q$	$\frac{p, \; p \rightarrow q}{\therefore q}$
부정 논법 (Modus Tollens)	$\neg q$, $p \rightarrow q$	$\neg p$	$\frac{\neg q, \; p \rightarrow q}{\therefore \neg p}$
가설적 삼단논법	$p \rightarrow q$, $q \rightarrow r$	$p \rightarrow r$	$\frac{p \rightarrow q, \; q \rightarrow r}{\therefore p \rightarrow r}$
선언적 삼단논법	$p \vee q$, $\neg p$	$q$	$\frac{p \vee q, \; \neg p}{\therefore q}$
부가법	$p$	$p \vee q$	$\frac{p}{\therefore p \vee q}$
단순화	$p \wedge q$	$p$	$\frac{p \wedge q}{\therefore p}$
결합법	$p$, $q$	$p \wedge q$	$\frac{p, \; q}{\therefore p \wedge q}$
구성적 양도논법	$p \vee q$, $p \rightarrow r$, $q \rightarrow s$	$r \vee s$	$\frac{p \vee q, \; p \rightarrow r, \; q \rightarrow s}{\therefore r \vee s}$

추론 규칙 적용 예시

전제: (1) "비가 오면 길이 젖는다" ($p \rightarrow q$), (2) "길이 젖지 않았다" ($\neg q$).

부정 논법(Modus Tollens)에 의해: "비가 오지 않았다" ($\neg p$). $\blacksquare$

타당성과 건전성: 전제가 참일 때 결론이 반드시 참이면 추론은 타당(Valid)합니다. 타당한 추론의 전제가 실제로 참이면 건전(Sound)합니다. 타당하지만 건전하지 않은 추론: "모든 새는 날 수 있다 → 펭귄은 새이다 → 펭귄은 날 수 있다" (타당하나 첫 전제가 거짓).

증명 방법

증명이란? 수학에서 증명이란 "이 주장이 왜 반드시 맞는지"를 논리적으로 빈틈없이 설명하는 것입니다. "실험해 보니 맞더라"는 증명이 아닙니다. 예를 들어 "1부터 100까지 다 확인해 보니 짝수의 제곱은 짝수였다"는 101 이상에서도 성립하는지 알 수 없으므로 증명이 되지 않습니다. 증명은 모든 경우에 성립함을 보여야 합니다.

직접 증명 (Direct Proof)

가정에서 출발하여 논리적 추론을 통해 결론에 도달하는 방법입니다. 가장 자연스럽고 기본적인 증명 방법입니다.

단계:

가정 $p$가 참이라고 놓습니다.
정의와 이미 알려진 사실들을 이용하여 논리적으로 추론합니다.
결론 $q$가 참임을 보입니다.

예시: "$n$이 짝수이면 $n^2$도 짝수이다"를 증명합니다.

풀이: $n$이 짝수이므로 $n = 2k$ ($k$는 정수)라고 쓸 수 있습니다. (짝수의 정의: 2로 나누어 떨어지는 수)

따라서 $n^2 = (2k)^2 = 4k^2 = 2(2k^2)$입니다.

$2k^2$는 정수이므로 $n^2 = 2 \times (\text{정수})$ 형태입니다. 따라서 $n^2$도 짝수입니다. $\blacksquare$

대우 증명 (Proof by Contrapositive)

$p \rightarrow q$를 증명하는 대신 대우 $\neg q \rightarrow \neg p$를 증명합니다.

예시: "$n^2$이 짝수이면 $n$은 짝수이다"를 증명합니다.

대우: "$n$이 홀수이면 $n^2$도 홀수이다".

$n$이 홀수이면 $n = 2k + 1$입니다. $n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$이므로 $n^2$은 홀수입니다. $\blacksquare$

귀류법 (Proof by Contradiction)

결론의 부정을 가정한 후 모순을 이끌어내는 방법입니다. 명제 $P$를 증명하려면 $\neg P$를 가정하고 모순($Q \wedge \neg Q$ 형태)을 유도합니다.

왜 이 방법이 통하는가? 귀류법의 원리는 이렇습니다: "만약 결론이 거짓이라면 말도 안 되는 상황(모순)이 벌어진다. 말도 안 되는 상황은 일어날 수 없으므로, 결론은 반드시 참이다." 탐정이 범인을 찾을 때 "만약 이 사람이 범인이 아니라면, 이런 모순이 생긴다. 따라서 이 사람이 범인이다"라고 추리하는 것과 같습니다.

단계:

증명하고 싶은 명제 $P$의 부정 $\neg P$를 가정합니다.
논리적으로 추론하여 모순(동시에 참이 될 수 없는 두 사실)을 이끌어냅니다.
모순이 발생했으므로 처음 가정 $\neg P$가 거짓임을 결론짓습니다.
따라서 $P$가 참입니다.

예시: "$\sqrt{2}$는 무리수이다"를 증명합니다.

풀이: $\sqrt{2}$가 유리수라고 가정하면 $\sqrt{2} = \frac{a}{b}$ (기약분수, $\gcd(a,b) = 1$)입니다. 양변을 제곱하면 $2 = \frac{a^2}{b^2}$, 즉 $a^2 = 2b^2$입니다.

$a^2$이 짝수이므로 $a$도 짝수입니다. $a = 2c$로 놓겠습니다.
대입하면 $(2c)^2 = 2b^2$, 즉 $4c^2 = 2b^2$, 따라서 $b^2 = 2c^2$.
$b^2$이 짝수이므로 $b$도 짝수입니다.
$a$와 $b$가 모두 짝수이므로 $\gcd(a,b) \geq 2$인데, 이는 $\gcd(a,b) = 1$에 모순됩니다.

따라서 $\sqrt{2}$는 무리수입니다. $\blacksquare$

수학적 귀납법 (Mathematical Induction)

자연수에 대한 명제를 증명하는 강력한 방법입니다. "자연수 $n = 1, 2, 3, \ldots$ 모두에 대해 성립한다"는 것을 한꺼번에 보여줍니다.

기본 단계(Base Case): $n = 1$ (또는 시작값)일 때 명제가 참임을 보입니다.
귀납 단계(Inductive Step): $n = k$일 때 참이라고 가정하고(귀납 가설), $n = k+1$일 때도 참임을 보입니다.

도미노 원리: 수학적 귀납법은 도미노와 같습니다. 첫 번째 도미노가 넘어지고(기본 단계), 하나가 넘어지면 다음 것도 넘어진다(귀납 단계)는 것을 보이면 모든 도미노가 넘어집니다. 무한히 많은 도미노(자연수)가 있어도, 이 두 가지만 확인하면 전부 넘어진다고 확신할 수 있습니다.

왜 이 방법이 통하는가? 기본 단계에서 $n = 1$일 때 참임을 보였습니다. 귀납 단계에서 "$k$일 때 참이면 $k+1$일 때도 참"임을 보였습니다. 그러면: $n = 1$ 참 → $n = 2$ 참 → $n = 3$ 참 → $n = 4$ 참 → ... 이렇게 연쇄적으로 모든 자연수에 대해 참이 됩니다. 마치 도미노가 줄줄이 넘어지는 것과 같습니다.

예시: 모든 자연수 $n$에 대하여 $1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$임을 증명합니다.

기본 단계: $n = 1$일 때, 좌변 $= 1$, 우변 $= \frac{1 \cdot 2}{2} = 1$. 같으므로 성립합니다.

귀납 단계: $n = k$일 때 $1 + 2 + \cdots + k = \frac{k(k+1)}{2}$이 성립한다고 가정합니다(귀납 가설).

$n = k + 1$일 때를 보이겠습니다. 좌변에 $(k+1)$을 더합니다:

$$1 + 2 + \cdots + k + (k+1) = \underbrace{\frac{k(k+1)}{2}}_{\text{귀납 가설}} + (k+1) = \frac{k(k+1) + 2(k+1)}{2} = \frac{(k+1)(k+2)}{2}$$

이는 $n = k+1$을 공식에 대입한 $\frac{(k+1)((k+1)+1)}{2}$과 일치합니다. $\blacksquare$

강한 귀납법 (Strong Induction)

귀납 가설에서 $n = k$만이 아니라 $n \leq k$인 모든 경우를 가정합니다.

예시: 모든 $n \geq 2$인 자연수는 소수들의 곱으로 표현됩니다.

기본 단계: $n = 2$는 소수이므로 자명합니다.

귀납 단계: $2 \leq m \leq k$인 모든 $m$이 소수 곱으로 표현된다고 가정합니다. $n = k + 1$이 소수이면 자명합니다. 합성수이면 $k + 1 = a \cdot b$ ($2 \leq a, b \leq k$)이고, 귀납 가설에 의해 $a$와 $b$가 소수 곱으로 표현되므로 $k+1$도 소수 곱입니다. $\blacksquare$

존재성 증명과 구성적 증명

방법	설명	예
구성적 증명	원하는 대상을 직접 구성하여 존재를 보임	$n^2 + n$이 짝수인 $n$ → $n = 1$일 때 $2$
비구성적 증명	대상의 존재만 보이고 구체적으로 제시하지 않음	비둘기집 원리에 의한 존재 증명
경우 분석	가능한 모든 경우로 나누어 각각 증명	$n$이 짝수인 경우와 홀수인 경우

술어 논리

술어 논리(Predicate Logic) 또는 1차 논리(First-Order Logic)는 명제 논리를 확장하여 변수, 술어, 한정사를 도입한 체계입니다.

왜 술어 논리가 필요한가? 명제 논리만으로는 "모든 자연수는 0 이상이다"와 같은 문장을 다룰 수 없습니다. 자연수가 무한히 많으므로 하나하나 명제로 만들 수 없기 때문입니다. 술어 논리에서는 $\forall n \in \mathbb{N}, \; n \geq 0$처럼 "모든"이나 "어떤"을 기호로 표현하여 이런 문장을 간결하게 다룰 수 있습니다.

술어와 변수

술어 $P(x)$는 변수 $x$에 값이 대입되면 명제가 되는 문장입니다. 쉽게 말해, "빈칸이 있는 문장"이며, 빈칸을 채우면 참 또는 거짓이 결정됩니다.

"$P(x)$: $x$는 소수이다" — $P(3)$은 참, $P(4)$는 거짓.
"$Q(x, y)$: $x > y$" — $Q(5, 3)$은 참, $Q(2, 7)$은 거짓.

술어는 하나 이상의 변수를 가질 수 있으며, $n$변수 술어를 $n$항 술어라 합니다.

명제 논리에서는 '모든' 또는 '어떤'을 다루기 어렵습니다. 예를 들어 '모든 자연수는 0 이상이다'를 표현하려면 새로운 기호가 필요합니다. $\forall$은 '모든(for all)'을, $\exists$는 '존재한다(there exists)'를 의미합니다.

한정사 (Quantifiers)

실생활에서의 한정사:

$\forall$ (전칭): "우리 반 모든 학생은 교복을 입었다" — 한 명이라도 안 입었으면 거짓
$\exists$ (존재): "우리 반에 안경을 쓴 학생이 있다" — 한 명만 있어도 참
$\exists!$ (유일 존재): "우리 반 반장은 정확히 한 명이다"

한정사	기호	의미	예시
전칭 한정사	$\forall$	모든 $x$에 대하여	$\forall x \in \mathbb{R}, \; x^2 \geq 0$
존재 한정사	$\exists$	어떤 $x$가 존재하여	$\exists x \in \mathbb{Z}, \; x^2 = 4$
유일 존재 한정사	$\exists!$	정확히 하나의 $x$가 존재하여	$\exists! x \in \mathbb{R}, \; x + 3 = 5$

자유 변수와 속박 변수

한정사에 의해 지배되는 변수를 속박 변수(Bound Variable), 그렇지 않은 변수를 자유 변수(Free Variable)라 합니다.

$\forall x \; P(x, y)$ — $x$는 속박, $y$는 자유
$\exists x \; (x > y)$ — $x$는 속박, $y$는 자유

모든 변수가 속박된 논리식을 문장(Sentence)이라 하며, 이것만이 진릿값을 가집니다.

한정사의 부정

$$\neg(\forall x \; P(x)) \equiv \exists x \; \neg P(x)$$ $$\neg(\exists x \; P(x)) \equiv \forall x \; \neg P(x)$$

직관적으로 이해하기:

"모든 학생이 합격했다"의 부정은 "합격 못한 학생이 있다"입니다. "모든"을 부정하면 "~인 것이 존재한다"가 됩니다.
"합격한 학생이 있다"의 부정은 "모든 학생이 합격하지 못했다"입니다. "존재한다"를 부정하면 "모든 ~가 아니다"가 됩니다.

이것은 집합론의 드모르간 법칙과 같은 구조입니다. $\forall$은 교집합($\cap$)에, $\exists$는 합집합($\cup$)에 대응합니다.

예시: "모든 학생이 시험에 합격했다"의 부정 → "시험에 합격하지 못한 학생이 존재한다".

다중 한정사

한정사가 여러 개 사용될 때 순서가 중요합니다.

논리식	의미	예 ($P(x,y)$: $x + y = 0$, 정의역 $\mathbb{Z}$)
$\forall x \; \forall y \; P(x,y)$	모든 $x, y$에 대해 $P$	거짓
$\forall x \; \exists y \; P(x,y)$	모든 $x$에 대해 적절한 $y$ 존재	참 ($y = -x$)
$\exists x \; \forall y \; P(x,y)$	어떤 $x$가 모든 $y$에 대해 $P$	거짓
$\exists x \; \exists y \; P(x,y)$	적절한 $x, y$ 존재	참 ($x=1, y=-1$)

한정사 순서 주의: $\forall x \; \exists y$와 $\exists y \; \forall x$는 일반적으로 다른 의미입니다. 전자는 "$x$마다 다른 $y$가 가능"하지만, 후자는 "모든 $x$에 대해 하나의 고정된 $y$"를 요구합니다.

정규형

논리식을 표준적인 형태로 변환하면 분석이 용이해집니다.

논리곱 정규형 (CNF)

논리곱 정규형(Conjunctive Normal Form)은 절(clause)들의 논리곱입니다. 각 절은 리터럴의 논리합입니다.

$$\text{CNF}: (p \vee \neg q) \wedge (\neg p \vee r) \wedge (q \vee r)$$

논리합 정규형 (DNF)

논리합 정규형(Disjunctive Normal Form)은 항(term)들의 논리합입니다. 각 항은 리터럴의 논리곱입니다.

$$\text{DNF}: (p \wedge q) \vee (\neg p \wedge r) \vee (p \wedge \neg q \wedge r)$$

모든 논리식은 동치인 CNF와 DNF로 변환할 수 있습니다.

변환 절차 예시

$p \rightarrow (q \wedge r)$을 CNF로 변환합니다.

$$\begin{aligned} p \rightarrow (q \wedge r) &\equiv \neg p \vee (q \wedge r) \quad (\text{조건문 변환}) \\ &\equiv (\neg p \vee q) \wedge (\neg p \vee r) \quad (\text{분배법칙}) \end{aligned}$$

불 대수

불 대수(Boolean Algebra)는 논리 연산을 대수적으로 체계화한 구조로, 조지 불(George Boole)이 1847년에 도입했습니다.

정의

집합 $B$와 이항 연산 $+$, $\cdot$, 단항 연산 $\overline{\phantom{x}}$에 대해 $(B, +, \cdot, \overline{\phantom{x}}, 0, 1)$이 다음을 만족하면 불 대수입니다:

법칙	$+$ (OR)	$\cdot$ (AND)
교환법칙	$a + b = b + a$	$a \cdot b = b \cdot a$
분배법칙	$a + (b \cdot c) = (a+b) \cdot (a+c)$	$a \cdot (b+c) = (a \cdot b) + (a \cdot c)$
항등법칙	$a + 0 = a$	$a \cdot 1 = a$
보원법칙	$a + \overline{a} = 1$	$a \cdot \overline{a} = 0$

불 대수의 예

명제 논리: $(\{\text{T}, \text{F}\}, \vee, \wedge, \neg, \text{F}, \text{T})$
집합론: $(\mathcal{P}(X), \cup, \cap, {}^c, \emptyset, X)$
디지털 회로: $(\{0, 1\}, \text{OR}, \text{AND}, \text{NOT}, 0, 1)$

논리 회로

논리 연산은 전자 회로의 논리 게이트(Logic Gate)로 물리적으로 구현됩니다. 이것이 현대 컴퓨터의 기초입니다.

기본 논리 게이트

게이트	기호	논리식	설명
AND	$\cdot$	$A \cdot B$	두 입력이 모두 1일 때 출력 1
OR	$+$	$A + B$	하나라도 1이면 출력 1
NOT	$\overline{\phantom{x}}$	$\overline{A}$	입력 반전
NAND	$\uparrow$	$\overline{A \cdot B}$	AND의 부정
NOR	$\downarrow$	$\overline{A + B}$	OR의 부정
XOR	$\oplus$	$A \oplus B$	입력이 다르면 출력 1

논리 체계의 완전성

건전성과 완전성

논리 체계에서 두 가지 핵심적인 성질이 있습니다:

건전성(Soundness): 증명 가능한 모든 것은 참이다. ($\vdash \phi \implies \models \phi$)
완전성(Completeness): 참인 모든 것은 증명 가능하다. ($\models \phi \implies \vdash \phi$)

괴델의 완전성 정리 (1929)

1차 논리(술어 논리)는 건전하고 완전합니다. 즉, 1차 논리에서 의미론적으로 참인 문장은 반드시 형식적으로 증명할 수 있습니다.

괴델의 불완전성 정리 (1931)

제1 불완전성 정리: 자연수의 산술을 포함하는 무모순인 형식 체계에는 체계 내에서 증명도 반증도 할 수 없는 명제가 존재합니다.

제2 불완전성 정리: 자연수의 산술을 포함하는 무모순인 형식 체계는 자기 자신의 무모순성을 증명할 수 없습니다.

이 결과는 힐베르트의 프로그램 — 수학 전체를 유한한 공리 체계로부터 기계적으로 유도할 수 있다는 목표 — 에 근본적인 한계를 보여주었습니다.

직관적 이해: 제1 불완전성 정리를 비유하자면 이렇습니다. 아무리 완벽한 규칙책을 만들어도, 그 규칙만으로는 "이 문장은 이 규칙으로 증명할 수 없다"와 같이 맞지만 증명할 수 없는 문장이 반드시 존재합니다. 마치 아무리 상세한 법률을 만들어도 법으로 판단할 수 없는 상황이 반드시 생기는 것과 비슷합니다. 이것은 수학의 한계가 아니라, 형식 체계 자체의 근본적인 성질입니다.

논리적 동치 증명 — 세 가지 방법 비교

하나의 동치식을 여러 방법으로 증명하면 각 방법의 특성을 이해할 수 있습니다. $\neg(p \rightarrow q) \equiv p \wedge \neg q$를 진리표, 논리법칙 변환, 자연연역 세 가지 방법으로 증명하겠습니다.

방법 1: 진리표에 의한 증명

모든 진릿값 조합에서 양쪽 결과가 일치하는지 확인합니다.

$p$	$q$	$p \rightarrow q$	$\neg(p \rightarrow q)$	$\neg q$	$p \wedge \neg q$	일치
T	T	T	F	F	F	✓
T	F	F	T	T	T	✓
F	T	T	F	F	F	✓
F	F	T	F	T	F	✓

네 가지 경우 모두 일치하므로 $\neg(p \rightarrow q) \equiv p \wedge \neg q$입니다. $\blacksquare$

방법 2: 논리법칙 변환에 의한 증명

기존 동치 법칙을 연쇄적으로 적용하여 좌변을 우변으로 변환합니다.

$$\begin{aligned} \neg(p \rightarrow q) &\equiv \neg(\neg p \vee q) \quad &(\text{조건문 변환: } p \rightarrow q \equiv \neg p \vee q) \\ &\equiv \neg(\neg p) \wedge \neg q \quad &(\text{드모르간 법칙}) \\ &\equiv p \wedge \neg q \quad &(\text{이중부정 제거}) \end{aligned}$$

따라서 $\neg(p \rightarrow q) \equiv p \wedge \neg q$입니다. $\blacksquare$

방법 3: 자연연역에 의한 증명

자연연역(Natural Deduction)은 가정과 추론 규칙만으로 증명하는 형식 체계입니다. 양방향 함의를 각각 보입니다.

($\Rightarrow$) $\neg(p \rightarrow q)$로부터 $p \wedge \neg q$ 도출:

$\neg(p \rightarrow q)$ — 가정
$\neg p$를 가정합니다 (귀류법을 위해).
$\neg p$이면 $p \rightarrow q$는 공허한 참이므로 $p \rightarrow q$.
이는 1과 모순이므로 $\neg(\neg p)$, 즉 $p$.
$q$를 가정합니다 (귀류법을 위해).
$q$이면 $p \rightarrow q$. 이는 1과 모순이므로 $\neg q$.
결합법에 의해 $p \wedge \neg q$.

($\Leftarrow$) $p \wedge \neg q$로부터 $\neg(p \rightarrow q)$ 도출:

$p \wedge \neg q$ — 가정
단순화에 의해 $p$, 그리고 $\neg q$.
$p \rightarrow q$를 가정합니다 (귀류법을 위해).
$p$와 $p \rightarrow q$에서 긍정 논법으로 $q$.
이는 $\neg q$와 모순이므로 $\neg(p \rightarrow q)$. $\blacksquare$

세 방법의 비교:

진리표: 기계적이고 확실하지만, 변수가 $n$개이면 $2^n$행이 필요하여 변수가 많으면 비효율적입니다.
논리법칙 변환: 간결하고 우아하지만, 적절한 법칙을 선택하는 통찰이 필요합니다.
자연연역: 실제 수학적 추론 과정을 반영하며, 술어 논리로 확장이 자연스럽습니다.

타당성 검증 — 네 가지 방법 비교

다음 논증의 타당성을 네 가지 방법으로 검증하겠습니다.

논증: 전제 1: $p \rightarrow q$, 전제 2: $q \rightarrow r$, 결론: $p \rightarrow r$ (가설적 삼단논법)

방법 1: 진리표

"전제가 모두 참인 행에서 결론도 반드시 참인가?"를 확인합니다.

$p$	$q$	$r$	$p \rightarrow q$	$q \rightarrow r$	$p \rightarrow r$	판정
T	T	T	T	T	T	전제 모두 T → 결론 T ✓
T	T	F	T	F	F	전제 중 F 있음 (해당 없음)
T	F	T	F	T	T	전제 중 F 있음
T	F	F	F	T	F	전제 중 F 있음
F	T	T	T	T	T	전제 모두 T → 결론 T ✓
F	T	F	T	F	T	전제 중 F 있음
F	F	T	T	T	T	전제 모두 T → 결론 T ✓
F	F	F	T	T	T	전제 모두 T → 결론 T ✓

전제가 모두 참인 행(1, 5, 7, 8행)에서 결론도 항상 참이므로 타당합니다. $\blacksquare$

방법 2: 반례 탐색

논증이 부당함을 보이려면, 전제가 모두 참이면서 결론이 거짓인 경우(반례)를 하나만 찾으면 됩니다. 결론 $p \rightarrow r$이 거짓이려면 $p = \text{T}, r = \text{F}$이어야 합니다.

$p = \text{T}, r = \text{F}$일 때: 전제 1 $p \rightarrow q$가 참이려면 $q = \text{T}$.
그런데 $q = \text{T}, r = \text{F}$이면 전제 2 $q \rightarrow r$은 거짓.
따라서 반례가 존재하지 않습니다. 논증은 타당합니다. $\blacksquare$

방법 3: 귀결 나무 (Semantic Tableau)

결론의 부정을 가정하고, 전제와 함께 모순을 이끌어내는 방법입니다. 모든 가지가 닫히면 타당합니다.

$p \rightarrow q$ — 전제
$q \rightarrow r$ — 전제
$\neg(p \rightarrow r)$ — 결론의 부정 (이것이 가능한지 검사)
3에서: $p = \text{T}$, $r = \text{F}$
1에서: $p = \text{T}$이므로 $q = \text{T}$ (아니면 $\neg p$인데 4에 모순)
2에서: $q = \text{T}$이므로 $r = \text{T}$ (아니면 $\neg q$인데 5에 모순)
$r = \text{T}$는 4의 $r = \text{F}$에 모순 — 가지 닫힘 ✗

모든 가지가 닫혔으므로 결론의 부정은 불가능합니다. 논증은 타당합니다. $\blacksquare$

방법 4: 자연연역

$p \rightarrow q$ — 전제
$q \rightarrow r$ — 전제
$p$를 가정합니다 (조건문 도입을 위해).
1과 3에서 긍정 논법: $q$
2와 4에서 긍정 논법: $r$
3–5에서 조건문 도입: $p \rightarrow r$ $\blacksquare$

모든 가지가 모순(✗)으로 닫혔으므로, 전제 하에서 결론의 부정은 불가능합니다. 따라서 논증은 타당합니다.

증명 기법 심화 — 같은 정리의 다양한 증명

하나의 정리를 여러 방법으로 증명하면 각 기법의 장단점을 파악할 수 있습니다.

정리: $n$이 정수일 때, $n^2$이 홀수이면 $n$은 홀수입니다.

직접 증명 시도

직접 증명은 가정 "$n^2$이 홀수"에서 출발하여 "$n$이 홀수"를 유도해야 합니다. 그러나 $n^2$에서 $n$의 성질을 직접 이끌어내기 어렵습니다. 이런 경우 다른 방법이 더 적합합니다.

대우 증명

대우: "$n$이 짝수이면 $n^2$이 짝수이다."

$n$이 짝수이면 $n = 2k$입니다. $n^2 = 4k^2 = 2(2k^2)$이므로 $n^2$은 짝수입니다. $\blacksquare$

이 증명은 가장 간결하고 자연스럽습니다.

귀류법

$n^2$이 홀수이고 $n$이 짝수라고 가정합니다. $n$이 짝수이면 $n = 2k$이고, $n^2 = 4k^2 = 2(2k^2)$로 짝수입니다. 이는 "$n^2$이 홀수"에 모순입니다. 따라서 $n$은 홀수입니다. $\blacksquare$

구성적 증명 (경우 분석)

정수 $n$은 짝수 또는 홀수입니다.

$n$이 짝수인 경우: $n = 2k$이면 $n^2 = 4k^2$으로 짝수이므로, "$n^2$이 홀수"라는 가정에 해당하지 않습니다.
$n$이 홀수인 경우: $n = 2k+1$이면 $n^2 = 4k^2 + 4k + 1$으로 홀수이므로, 가정을 만족합니다.

따라서 $n^2$이 홀수이면 반드시 $n$이 홀수인 경우에 해당합니다. $\blacksquare$

증명 기법 선택 가이드:

직접 증명: 가정에서 결론으로 자연스럽게 이어질 때 사용합니다.
대우 증명: 결론의 부정에서 출발하는 것이 더 쉬울 때 유용합니다. 특히 "~이면 ~이다" 형태에서 결론 쪽이 복잡할 때 효과적입니다.
귀류법: 직접적인 경로가 보이지 않을 때, 모순을 찾아 간접적으로 증명합니다. 존재성이나 유일성 증명에 특히 강력합니다.
경우 분석: 문제가 자연스럽게 여러 경우로 나뉠 때 사용합니다.

술어 논리 심화

다중 양화사와 순서의 중요성

양화사의 순서를 바꾸면 의미가 완전히 달라질 수 있습니다. 이를 구체적 예로 살펴보겠습니다.

예: $L(x, y)$를 "$x$는 $y$를 좋아한다"로 정의합니다.

$\forall x \, \exists y \, L(x, y)$: "모든 사람에게는 좋아하는 사람이 있다." — 사람마다 다른 대상을 좋아할 수 있습니다.
$\exists y \, \forall x \, L(x, y)$: "모든 사람이 좋아하는 어떤 한 사람이 존재한다." — 한 명의 인기인을 가리킵니다.
$\forall x \, \forall y \, L(x, y)$: "모든 사람은 모든 사람을 좋아한다."
$\exists x \, \exists y \, L(x, y)$: "누군가를 좋아하는 사람이 적어도 한 쌍 존재한다."

같은 종류의 양화사끼리는 교환 가능합니다:

$$\forall x \, \forall y \, P(x,y) \equiv \forall y \, \forall x \, P(x,y)$$ $$\exists x \, \exists y \, P(x,y) \equiv \exists y \, \exists x \, P(x,y)$$

그러나 다른 종류의 양화사는 일반적으로 교환 불가능합니다:

$$\forall x \, \exists y \, P(x,y) \not\equiv \exists y \, \forall x \, P(x,y)$$

다만 $\exists y \, \forall x \, P(x,y) \Rightarrow \forall x \, \exists y \, P(x,y)$는 항상 성립합니다 (역은 성립하지 않습니다).

양화사 부정의 연쇄 적용

복잡한 양화 문장의 부정을 단계적으로 구합니다.

예: $\forall x \, \exists y \, (P(x,y) \rightarrow Q(x,y))$의 부정

$$\begin{aligned} \neg \forall x \, \exists y \, (P(x,y) \rightarrow Q(x,y)) &\equiv \exists x \, \neg \exists y \, (P(x,y) \rightarrow Q(x,y)) \\ &\equiv \exists x \, \forall y \, \neg(P(x,y) \rightarrow Q(x,y)) \\ &\equiv \exists x \, \forall y \, (P(x,y) \wedge \neg Q(x,y)) \end{aligned}$$

즉 "모든 $x$에 대해 적절한 $y$가 존재하여 $P \rightarrow Q$"의 부정은 "어떤 $x$가 존재하여 모든 $y$에 대해 $P$이지만 $Q$가 아닌"입니다.

유일 존재 양화사

$\exists! x \, P(x)$는 "정확히 하나의 $x$가 $P(x)$를 만족한다"를 의미하며, 다음과 같이 풀어 쓸 수 있습니다:

$$\exists! x \, P(x) \equiv \exists x \, \bigl(P(x) \wedge \forall y \, (P(y) \rightarrow y = x)\bigr)$$

이는 두 가지를 동시에 주장합니다: (1) 조건을 만족하는 $x$가 존재한다. (2) 그러한 $x$는 유일하다.

예: $\exists! x \in \mathbb{R}, \; x + 3 = 5$

존재: $x = 2$는 $2 + 3 = 5$를 만족합니다.
유일성: $y + 3 = 5$이면 $y = 2 = x$이므로 유일합니다. $\blacksquare$

수학적 귀납법 심화

약한 귀납법 vs 강한 귀납법

구분	약한 귀납법 (Weak Induction)	강한 귀납법 (Strong Induction)
귀납 가설	$P(k)$가 참이라고 가정	$P(1), P(2), \ldots, P(k)$ 모두 참이라고 가정
증명 목표	$P(k+1)$	$P(k+1)$
적합한 경우	바로 이전 단계만 필요할 때	이전의 여러 단계가 필요할 때
논리적 동치	두 방법은 논리적으로 동치이며, 하나로 증명 가능한 것은 다른 것으로도 증명 가능합니다.

강한 귀납법 예시: 피보나치 수열의 상한

정리: 피보나치 수열 $F_n$에 대해, 모든 $n \geq 1$에서 $F_n \lt 2^n$입니다.

기본 단계: $F_1 = 1 \lt 2 = 2^1$, $F_2 = 1 \lt 4 = 2^2$. 성립합니다.

귀납 단계: 모든 $m \leq k$에 대해 $F_m \lt 2^m$이 성립한다고 가정합니다 ($k \geq 2$).

$$F_{k+1} = F_k + F_{k-1} \lt 2^k + 2^{k-1} = 2^{k-1}(2 + 1) = 3 \cdot 2^{k-1} \lt 4 \cdot 2^{k-1} = 2^{k+1}$$

따라서 $F_{k+1} \lt 2^{k+1}$이 성립합니다. $\blacksquare$

강한 귀납법이 필요한 이유: 위 증명에서 $F_{k+1} = F_k + F_{k-1}$이므로 $P(k)$뿐 아니라 $P(k-1)$도 필요합니다. 약한 귀납법으로는 $P(k-1)$을 가정할 수 없으므로 강한 귀납법이 적합합니다.

구조적 귀납법

구조적 귀납법(Structural Induction)은 재귀적으로 정의된 구조(문자열, 트리, 논리식 등)에 대한 성질을 증명하는 방법입니다.

예: 명제 논리식의 괄호 개수

논리식을 다음과 같이 재귀적으로 정의합니다:

기본: 명제 변수 $p, q, r, \ldots$는 논리식입니다.
재귀: $\phi$가 논리식이면 $(\neg \phi)$도 논리식이고, $\phi, \psi$가 논리식이면 $(\phi \wedge \psi)$, $(\phi \vee \psi)$도 논리식입니다.

정리: 모든 논리식에서 열린 괄호의 수 = 닫힌 괄호의 수.

기본 단계: 명제 변수 $p$에는 괄호가 없으므로 양쪽 모두 0개. 성립합니다.

귀납 단계:

$(\neg \phi)$: 귀납 가설에 의해 $\phi$에서 열린 = 닫힌. $(\neg \phi)$는 양쪽에 각각 1개씩 추가하므로 여전히 같습니다.
$(\phi \wedge \psi)$: 각각 열린 = 닫힌이 성립하고, 바깥 괄호가 양쪽 1개씩이므로 합도 같습니다. $\blacksquare$

정형화 연습 — 일상 문장의 논리식 변환

일상 언어를 논리식으로 변환하는 것은 논리학의 핵심 기술입니다. 다양한 예제를 통해 연습하겠습니다.

명제 논리 정형화

일상 문장	명제 정의	논리식
비가 오고 바람이 불면, 우산을 가져간다	$p$: 비가 온다, $q$: 바람이 분다, $r$: 우산을 가져간다	$(p \wedge q) \rightarrow r$
수학을 공부하지 않으면 시험에 떨어진다	$p$: 수학을 공부한다, $q$: 시험에 떨어진다	$\neg p \rightarrow q$
커피나 주스를 마시지만, 둘 다 마시지는 않는다	$p$: 커피를 마신다, $q$: 주스를 마신다	$p \oplus q$
합격하려면 필기와 면접을 모두 통과해야 한다	$p$: 합격한다, $q$: 필기 통과, $r$: 면접 통과	$p \rightarrow (q \wedge r)$
영어 또는 수학을 잘하면 장학금을 받을 수 있다	$p$: 영어를 잘한다, $q$: 수학을 잘한다, $r$: 장학금을 받는다	$(p \vee q) \rightarrow r$

술어 논리 정형화

일상 문장	논리식
모든 학생은 적어도 한 과목을 수강한다	$\forall x \, (\text{Student}(x) \rightarrow \exists y \, (\text{Course}(y) \wedge \text{Takes}(x,y)))$
어떤 수는 모든 수보다 크지 않다	$\neg \exists x \, \forall y \, (x > y)$
두 사람이 서로 좋아하면 친구이다	$\forall x \, \forall y \, ((L(x,y) \wedge L(y,x)) \rightarrow F(x,y))$
모든 짝수보다 큰 소수가 존재한다	$\forall n \, (\text{Even}(n) \rightarrow \exists p \, (\text{Prime}(p) \wedge p > n))$
정확히 하나의 최솟값이 존재한다	$\exists! x \, \forall y \, (x \leq y)$

정형화 팁:

"~만 ~한다"는 $\text{only } A \text{ do } B$ = $B \rightarrow A$입니다. "학생만 입장할 수 있다" = "입장할 수 있으면 학생이다."
"~하지 않으면 ~이 아니다"는 이중 부정에 주의합니다. $\neg p \rightarrow \neg q$는 $q \rightarrow p$와 동치입니다.
"적어도 하나"는 $\exists$, "모든"은 $\forall$, "정확히 하나"는 $\exists!$에 대응합니다.

불 대수 심화 — 논리회로와 카르노 맵

논리식의 간소화

논리 회로를 설계할 때, 게이트 수를 최소화하면 비용과 전력이 절감됩니다. 불 대수 법칙 또는 카르노 맵(Karnaugh Map)을 사용하여 간소화합니다.

예: $F = A\overline{B}C + A\overline{B}\overline{C} + AB\overline{C} + ABC$를 간소화합니다.

$$\begin{aligned} F &= A\overline{B}(C + \overline{C}) + AB(\overline{C} + C) \quad (\text{분배법칙}) \\ &= A\overline{B} \cdot 1 + AB \cdot 1 \quad (\text{보원법칙}) \\ &= A\overline{B} + AB \quad (\text{항등법칙}) \\ &= A(\overline{B} + B) \quad (\text{분배법칙}) \\ &= A \quad (\text{보원·항등법칙}) \end{aligned}$$

4개의 항이 단일 변수 $A$로 간소화되었습니다.

카르노 맵 (Karnaugh Map)

카르노 맵은 인접한 칸을 묶어 시각적으로 논리식을 간소화하는 방법입니다. 2~4변수에 효과적입니다.

예: 2변수 카르노 맵

$F(A, B) = \overline{A}B + AB$를 카르노 맵으로 간소화합니다.

	$B=0$	$B=1$
$A=0$	0	1
$A=1$	0	1

$B=1$ 열의 두 칸이 묶이므로 $F = B$입니다.

예: 3변수 카르노 맵

$F(A,B,C) = \sum m(0, 2, 4, 5, 6)$을 간소화합니다.

$A \backslash BC$	00	01	11	10
$A=0$	1	0	0	1
$A=1$	1	1	0	1

묶을 수 있는 그룹:

$\overline{C}$ 열 전체 (00, 10열의 4칸) → $\overline{C}$
$A=1, B=0$ 행의 01 칸 → $A\overline{B}$와 결합하면 $A\overline{B}$

결과: $F = \overline{C} + A\overline{B}$

논리 회로 설계 예

반가산기(Half Adder)는 한 자리 이진수 덧셈을 수행합니다.

합(Sum): $S = A \oplus B$
올림(Carry): $C = A \cdot B$

$A$	$B$	$S = A \oplus B$	$C = A \cdot B$
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

비고전 논리 개요

고전 논리(Classical Logic)를 확장하거나 변형한 다양한 논리 체계가 있습니다.

양상 논리 (Modal Logic)

"반드시(필연적으로)"와 "가능하게"라는 양상 개념을 다룹니다.

$\Box \phi$: "$\phi$는 필연적이다" (모든 가능 세계에서 참)
$\Diamond \phi$: "$\phi$는 가능하다" (어떤 가능 세계에서 참)

핵심 관계: $\Diamond \phi \equiv \neg \Box \neg \phi$ (가능하다 = 불가능하지 않다)

크립키 의미론(Kripke Semantics)에서는 가능 세계(Possible Worlds)와 접근 관계(Accessibility Relation)를 이용하여 양상 연산자의 의미를 정의합니다.

양상 논리의 응용: 양상 논리는 컴퓨터 과학에서 프로그램 검증(모델 체킹), 인공지능에서 지식 표현(인식 논리), 철학에서 가능 세계 논의 등에 활용됩니다.

직관주의 논리 (Intuitionistic Logic)

고전 논리에서는 배중률 $p \vee \neg p$가 항상 성립하지만, 직관주의 논리에서는 이를 공리로 인정하지 않습니다. 직관주의에서 "$p$가 참이다"란 "$p$의 증명을 구성할 수 있다"를 의미합니다.

배중률 거부: 증명도 반증도 할 수 없는 명제가 있을 수 있습니다.
이중 부정 제거 거부: $\neg \neg p \not\Rightarrow p$ (반증의 반증이 곧 증명은 아닙니다).
구성적 존재: $\exists x \, P(x)$를 증명하려면 실제로 $P(a)$를 만족하는 $a$를 제시해야 합니다.

다치 논리 (Many-Valued Logic)

고전 논리의 진릿값은 T와 F 두 가지뿐이지만, 다치 논리에서는 중간 값을 허용합니다.

3치 논리 (클리니): T, U(불확정), F. "참인지 거짓인지 아직 모르는" 상태를 표현합니다.
퍼지 논리: $[0, 1]$ 구간의 실수를 진릿값으로 사용합니다. "키가 크다"의 참 정도가 0.7인 것처럼 모호한 개념을 다룹니다.

논리 체계	진릿값	배중률	이중부정 제거	주요 응용
고전 논리	{T, F}	성립	성립	수학, 형식 증명
직관주의 논리	구성적	불성립	불성립	구성적 수학, 타입 이론
3치 논리	{T, U, F}	불성립	조건부	데이터베이스 (SQL NULL)
퍼지 논리	[0, 1]	불성립	조건부	제어 시스템, AI
양상 논리	{T, F} + 양상	성립	성립	프로그램 검증, 지식 표현

증명의 전략 — 존재 증명, 반례, 비둘기집

구성적 존재 증명

원하는 대상을 직접 제시하여 존재를 증명합니다.

예: $a^b$가 유리수인 무리수 $a, b$가 존재함을 구성적으로 보입니다.

$a = \sqrt{2}$, $b = 2$로 놓으면 $a^b = (\sqrt{2})^2 = 2$는 유리수이고, $\sqrt{2}$는 무리수, $2$는 유리수(따라서 무리수가 아님)이므로 조건을 완전히 만족하지 않습니다.

$a = \sqrt{2}$, $b = \log_2 9$로 놓겠습니다. $b = \log_2 9$가 무리수임은 $2^{p/q} = 9$가 정수해를 갖지 않음으로 증명됩니다. 그러면 $a^b = (\sqrt{2})^{\log_2 9} = 2^{(\log_2 9)/2} = 9^{1/2} = 3$으로 유리수입니다. $\blacksquare$

비구성적 존재 증명

대상의 존재만 보이고 구체적으로 어떤 것인지는 밝히지 않습니다.

유명한 예: "$a, b$가 무리수이고 $a^b$가 유리수인 쌍이 존재한다."

$\alpha = \sqrt{2}^{\sqrt{2}}$를 생각합니다.

경우 1: $\alpha$가 유리수이면, $a = b = \sqrt{2}$가 조건을 만족합니다.
경우 2: $\alpha$가 무리수이면, $a = \alpha = \sqrt{2}^{\sqrt{2}}$, $b = \sqrt{2}$로 놓으면 $a^b = (\sqrt{2}^{\sqrt{2}})^{\sqrt{2}} = \sqrt{2}^{2} = 2$로 유리수입니다.

어느 경우든 조건을 만족하는 쌍이 존재합니다. 그러나 $\alpha$가 실제로 유리수인지 무리수인지는 이 증명에서 밝히지 않습니다(실제로는 무리수임이 알려져 있습니다). $\blacksquare$

반례에 의한 반증

전칭 명제 $\forall x \, P(x)$가 거짓임을 보이려면 $P(a)$가 거짓인 구체적 $a$를 하나 제시하면 됩니다.

예 1: "모든 소수는 홀수이다"의 반례 → $2$는 소수이면서 짝수입니다. $\blacksquare$

예 2: "모든 연속함수는 미분 가능하다"의 반례 → $f(x) = |x|$는 연속이지만 $x = 0$에서 미분 불가능합니다. $\blacksquare$

예 3: "$n^2 + n + 41$은 모든 자연수 $n$에 대해 소수이다"의 반례 → $n = 40$일 때 $40^2 + 40 + 41 = 41^2 = 1681$로 소수가 아닙니다. $\blacksquare$

비둘기집 원리 (Pigeonhole Principle)

$n+1$개의 물건을 $n$개의 상자에 넣으면, 적어도 하나의 상자에는 2개 이상의 물건이 들어갑니다.

$$|A| > |B| \implies \text{임의의 함수 } f: A \rightarrow B \text{는 단사(injective)가 아닙니다.}$$

예 1: 13명이 모이면 같은 달에 태어난 사람이 적어도 2명 있습니다 (13명 → 12개월).

예 2: 서울에 머리카락 수가 정확히 같은 두 사람이 존재합니다. 인간의 머리카락은 최대 약 150,000개이고, 서울 인구는 약 950만 명이므로, 비둘기집 원리에 의해 같은 수의 머리카락을 가진 사람이 반드시 존재합니다.

논리 퍼즐

논리 퍼즐은 형식 논리의 개념을 재미있게 연습할 수 있는 좋은 방법입니다.

기사와 악당 (Knights and Knaves)

어떤 섬에는 기사(Knight)와 악당(Knave)이 살고 있습니다. 기사는 항상 참만 말하고, 악당은 항상 거짓만 말합니다.

퍼즐 1: A가 말합니다: "나는 악당이다." A는 기사입니까, 악당입니까?

풀이:

A가 기사라면: "나는 악당이다"가 참이어야 하는데, 그러면 A는 악당 → 모순.
A가 악당이라면: "나는 악당이다"가 거짓이어야 하는데, 실제로 악당이므로 이 말은 참 → 모순.

따라서 이 말은 기사도 악당도 할 수 없습니다. 이 퍼즐은 해가 없습니다. (이는 "거짓말쟁이 역설"의 변형입니다.)

퍼즐 2: A가 말합니다: "우리 둘 다 악당이다." B는 아무 말도 하지 않습니다. A와 B는 각각 무엇입니까?

풀이: $p$: A는 기사, $q$: B는 기사로 정의합니다.

A의 발언: "A도 악당이고 B도 악당이다" = $\neg p \wedge \neg q$
A가 기사($p = \text{T}$)인 경우: 발언 $\neg p \wedge \neg q$가 참이어야 합니다. $\neg p = \text{F}$이므로 전체가 거짓 → 모순.
A가 악당($p = \text{F}$)인 경우: 발언이 거짓이어야 합니다. $\neg(\neg p \wedge \neg q) = p \vee q$. $p = \text{F}$이므로 $q = \text{T}$이어야 합니다.

답: A는 악당, B는 기사입니다. $\blacksquare$

퍼즐 3 (스멀리안 유형): A가 말합니다: "B가 기사라면, 나도 기사이다." A와 B는?

풀이: A의 발언: $q \rightarrow p$

A가 기사($p = \text{T}$)인 경우: $q \rightarrow p$가 참이어야 합니다. $p = \text{T}$이므로 $q$에 관계없이 참. B는 기사일 수도 악당일 수도 있습니다.
A가 악당($p = \text{F}$)인 경우: $q \rightarrow p$가 거짓이어야 합니다. $q = \text{T}$이고 $p = \text{F}$일 때만 거짓. 즉 B는 기사.

가능한 경우: (1) A 기사, B 기사, (2) A 기사, B 악당, (3) A 악당, B 기사. 이 퍼즐은 추가 정보 없이는 유일한 해를 결정할 수 없습니다.

논리 그리드 퍼즐

퍼즐: 민수, 지영, 현우 세 사람이 각각 수학, 과학, 영어 중 하나를 좋아합니다 (서로 다른 과목).

민수는 수학을 좋아하지 않습니다.
지영은 영어를 좋아하지 않습니다.
과학을 좋아하는 사람은 민수가 아닙니다.

풀이: 논리적 추론을 단계적으로 적용합니다.

조건 1에서: 민수 ≠ 수학
조건 3에서: 민수 ≠ 과학
따라서: 민수 = 영어
조건 2에서: 지영 ≠ 영어 (이미 민수가 영어)
남은 과목: 지영은 수학 또는 과학. 제약 없으므로 추가 조건 필요.
조건 3의 "과학을 좋아하는 사람"은 지영 또는 현우. 추가 정보가 없으므로 조건 2로부터: 지영은 수학 또는 과학 가능. 현우는 나머지.

민수가 영어를 확정한 후, 지영이 수학이면 현우가 과학, 지영이 과학이면 현우가 수학입니다. 더 많은 단서가 주어지면 유일한 해가 결정됩니다.

논리 그리드 풀이 전략:

소거법: 확실히 아닌 조합을 제거합니다.
유일 할당: 한 행이나 열에 하나만 남으면 그것이 답입니다.
연쇄 추론: 하나의 확정이 다른 확정을 연쇄적으로 이끌어냅니다.

증명 전략 요약

전략	적용 상황	핵심 아이디어
직접 증명	$p \rightarrow q$, 가정→결론 경로가 명확할 때	정의와 기존 정리를 단계적으로 적용
대우 증명	결론 쪽에서 출발하기 더 쉬울 때	$\neg q \rightarrow \neg p$ 증명
귀류법	직접적 경로가 안 보일 때, 존재/유일성	부정을 가정하고 모순 유도
수학적 귀납법	자연수에 대한 전칭 명제	기본 단계 + 귀납 단계
경우 분석	유한 개의 자연스러운 경우로 나뉠 때	모든 경우를 빠짐없이 다룸
구성적 존재	$\exists x \, P(x)$, 대상 구성이 가능할 때	조건 만족하는 구체적 대상 제시
비구성적 존재	대상 특정은 어렵지만 존재는 보일 수 있을 때	비둘기집 원리, 경우 분석 등
반례	전칭 명제가 거짓임을 보일 때	$P(a)$가 거짓인 $a$ 하나 제시

참고자료

Rosen, K. H. — Discrete Mathematics and Its Applications, McGraw-Hill
Enderton, H. B. — A Mathematical Introduction to Logic, Academic Press
Mendelson, E. — Introduction to Mathematical Logic, CRC Press
Smullyan, R. M. — First-Order Logic, Dover
Nagel, E. & Newman, J. R. — Gödel's Proof, NYU Press
집합론 — 논리와 집합의 관계
이산수학 — 논리학의 응용
정수론 — 수학적 귀납법의 활용