집합과 명제 — 수학적 논리의 토대

"모든 소수는 홀수이다" — 참일까요? 2가 반례입니다. 수학적 명제는 한 줄의 반례로 뒤집힐 수 있습니다. 집합은 이를 정확히 기술하는 언어이고, 명제 논리는 수학적 사고의 규칙입니다.

1. 집합의 기초

조건이 분명하여 그 대상을 명확히 결정할 수 있는 것의 모음을 집합이라 합니다.

표현법	예시
원소나열법	$A=\{1,2,3,4\}$
조건제시법	$A=\{x\mid x$는 4 이하의 자연수$\}$
벤 다이어그램	원으로 시각화

• 공집합 $\varnothing$: 원소가 없는 집합 (모든 집합의 부분집합)
• 부분집합: $A\subseteq B⟺A$의 모든 원소가 $B$에 속함
• $n$개 원소를 가진 집합의 부분집합 수: $2^n$

2. 집합의 연산

연산	기호	뜻
합집합	$A\cup B$	$A$ 또는 $B$에 속하는 원소 전체
교집합	$A\cap B$	$A$와 $B$ 모두에 속하는 원소
여집합	$A^c$	전체집합 $U$에서 $A$를 뺀 것
차집합	$A-B$	$A$에 속하고 $B$에 속하지 않는 원소

집합의 원소 개수

$$n(A\cup B)=n(A)+n(B)-n(A\cap B)$$

n(A)=20, n(B)=15, n(A∩B)=7 이면
n(A∪B) = 20+15−7 = 28

드 모르간 법칙

$$(A\cup B{)}^c=A^c\cap B^c$$

$$(A\cap B{)}^c=A^c\cup B^c$$

3. 명제

참 또는 거짓을 판별할 수 있는 문장·식을 명제라 합니다.

역·이·대우

종류	형태	참거짓 관계
원래 명제	$p\Rightarrow q$	-
역	$q\Rightarrow p$	원래와 무관
이	$\neg p\Rightarrow \neg q$	원래와 무관
대우	$\neg q\Rightarrow \neg p$	원래와 항상 같음

"a>0이고 b>0이면 a+b>0"  → 참
역: "a+b>0이면 a>0이고 b>0"  → 거짓 (반례: a=3, b=−1)
대우: "a+b≤0이면 a≤0 또는 b≤0"  → 참 (원래와 동치)

4. 충분·필요조건

$p\Rightarrow q$가 참일 때: $p$는 $q$이기 위한 충분조건, $q$는 $p$이기 위한 필요조건

p: x=2,  q: x²=4

p→q: x=2이면 x²=4  ✓ (참)
q→p: x²=4이면 x=2  ✗ (거짓, x=−2도 가능)

∴ p는 q의 충분조건 (but not 필요조건)
  q는 p의 필요조건 (but not 충분조건)

$p\iff q$ (필요충분조건): $p\Rightarrow q$이고 $q\Rightarrow p$

5. 증명법

직접증명

"n이 홀수이면 n²도 홀수"
n = 2k+1로 놓으면
n² = (2k+1)² = 4k²+4k+1 = 2(2k²+2k)+1
→ 홀수  ✓

귀류법 (모순에 의한 증명)

"√2는 무리수"
√2 = p/q (기약분수)로 가정
2 = p²/q²  →  p² = 2q²
→ p²이 짝수 → p가 짝수 → p=2m
→ 4m² = 2q²  →  q² = 2m²
→ q도 짝수 → p,q가 공약수 2를 가짐 ← 기약 가정에 모순
∴ √2는 무리수