1. 부울 대수란 무엇인가
부울 대수는 인간의 논리적 사고를 0과 1이라는 이진수로 번역하여 수학적으로 표현하고 계산할 수 있게 하는 대수학 시스템이다. 1854년 조지 불이 저서 『생각의 법칙(The Laws of Thought)』 에서 처음 제시했다.
핵심 아이디어는 단순하다. "참(True)"은 1로, "거짓(False)"은 0으로 치환하면, 추상적인 논리 판단을 숫자 연산으로 다룰 수 있다는 것이다.
| "하늘이 파랗다" → 참 | 1 |
| "고양이는 식물이다" → 거짓 | 0 |
| "맑고 따뜻하면 소풍 간다" | 1 AND 1 = 1 |
이러한 변환 덕분에 컴퓨터는 인간의 논리적 사고 과정을 수학적으로 처리할 수 있게 되었다.
2. 명제(Proposition) — 논리의 최소 단위
명제란 참(True, 1)이거나 거짓(False, 0)을 명확히 판별할 수 있는 문장을 말한다. 부울 대수는 모든 정보를 명제로 쪼개는 것에서 시작된다.
명제의 조건
- 객관적으로 참/거짓이 판별 가능해야 함
- 주관적 판단·의문문·명령문은 명제가 아님
| "17은 소수이다" | ⭕ 명제 (참) | 객관적 판별 가능 |
| "서울은 대한민국의 수도이다" | ⭕ 명제 (참) | 사실 확인 가능 |
| "사과는 맛있다" | ❌ 명제 아님 | 주관적 판단 |
| "오늘 서울 최고기온은 25도 이상이다" | ⭕ 명제 | 측정 가능한 객관 기준 |
| "창문을 닫아라" | ❌ 명제 아님 | 명령문 |
💡 컴퓨터는 모호함을 처리할 수 없다. 그래서 모든 정보를 명확한 0/1의 팩트로 분해하는 것이 부울 대수의 출발점이다.
3. 논리 연산자(Operators) — 명제를 조립하는 도구
명제가 '벽돌'이라면, 논리 연산자는 벽돌을 이어 붙이는 '시멘트'다. 단순 명제를 결합하여 복잡한 논리를 표현하게 해준다.
| AND (논리곱) | ∧ | 그리고 | 모든 명제가 참일 때 | 교집합(∩) |
| OR (논리합) | ∨ | 또는 | 하나라도 참일 때 | 합집합(∪) |
| NOT (부정) | ¬ | 아니다 | 명제의 상태를 반전 | 여집합 |
| XOR (배타적 OR) | ⊕ | 둘 중 하나만 | 정확히 하나만 참일 때 | 대칭차집합 |
실생활 예시
| p ∧ q | "이산구조 수강(p) 그리고 평점 3.0 이상(q)" → 둘 다 충족해야 장학금 |
| p ∨ q | "토익 800점 이상(p) 또는 토플 90점 이상(q)" → 하나만 충족해도 OK |
| ¬p | "오늘은 일요일이다(p)" → "오늘은 일요일이 아니다(¬p)" |
| p ⊕ q | "고양이는 동물이다 ⊕ 고양이는 식물이다" → 둘 중 하나만 참 |
4. 함축(IMPLY, →) — 조건부 약속
함축은 "만약 P라면 Q이다(If P, then Q)"의 형식으로 표현되는 조건부 관계를 말한다. 일상의 '약속'과 비슷하다.
예: "학점이 4.0 이상이면(P) 기숙사를 배정한다(Q)"
여기서 가장 중요한 포인트는 가정(P)이 거짓이면 결론(Q)에 관계없이 함축은 항상 참이라는 것이다. 직관과 다르므로 시험에 자주 나온다.
함축의 진리표
| T | T | T | 약속 이행 |
| T | F | F | 약속 위반 (유일한 거짓 케이스) |
| F | T | T | 약속과 무관 (참) |
| F | F | T | 약속과 무관 (참) |
💡 핵심 규칙: 가정이 참이면서 결론이 거짓일 때만 함축이 거짓이다. 나머지는 모두 참.
왜 P가 거짓일 때 항상 참인가? "비가 오면 우산을 쓴다"고 약속했을 때, 비가 안 오는 날엔 우산을 써도, 안 써도 약속을 어긴 게 아니다. 약속 조건 자체가 발동되지 않았기 때문이다.
5. 상호조건 명제(IFF, ↔) — 완전한 동등
상호조건은 "P와 Q가 완벽하게 동등(필요충분조건)"한 관계를 표현한다. P가 참이면 Q도 참, P가 거짓이면 Q도 거짓이어야 한다.
예: "전원 스위치 ON(P) ↔ 전구 불빛 들어옴(Q)" 스위치를 켰는데 불이 안 오면 논리 오류!
상호조건의 진리표
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
💡 핵심 규칙: P와 Q의 진리값이 같을 때만 참.
함축과의 관계 (시험 빈출)
상호조건은 두 함축의 결합과 같다.
P ↔ Q ≡ (P → Q) ∧ (Q → P)
즉, "P이면 Q이고, 동시에 Q이면 P"가 모두 성립할 때만 P ↔ Q가 참이다.
6. 진리표(Truth Table) — 논리의 매뉴얼
진리표는 논리 명제의 가능한 모든 입력 조합에 대한 결과를 표로 정리한 것이다. 어떤 기계에 모든 재료를 넣어보고 결과를 기록한 매뉴얼과 같다.
기본 연산자 진리표 총정리
| 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 |
💡 학습 팁: 복잡한 논리식은 반드시 진리표로 분해해 검증하라. 오류를 찾고 일관성을 확인하는 가장 확실한 방법이다.
7. 클로드 섀넌의 발견 — 논리가 기계가 된 순간
1937년, MIT 대학원생이었던 클로드 섀넌(Claude Shannon) 은 석사 논문에서 결정적인 발견을 했다. 조지 불의 대수학이 전기 스위치 회로와 완벽하게 일치한다는 사실이었다.
| True (1) | 스위치 닫힘 (ON) — 전류 흐름 |
| False (0) | 스위치 열림 (OFF) — 전류 차단 |
| AND (∧) | 스위치 직렬 연결 |
| OR (∨) | 스위치 병렬 연결 |
| NOT (¬) | 반전(인버터) 회로 |
이 발견이 왜 결정적인가? 추상적이던 '논리'가 물리적인 '하드웨어'로 구현될 수 있는 다리가 놓였기 때문이다. 오늘날 우리가 쓰는 모든 디지털 기기는 수십억 개의 미세한 스위치(트랜지스터)들이 섀넌이 밝힌 원리에 따라 켜지고 꺼지며 정보를 처리한다.
인간 논리가 물리적 현실이 된 과정
| 1854년 | 조지 불 | 『생각의 법칙』 출간, 부울 대수 창시 |
| 1937년 | 클로드 섀넌 | 부울 대수 = 전기 스위치 회로 발견 |
| 현재 | — | DB 검색(SQL), 검색 엔진, AI 프로세서로 확장 |
8. 논리식의 수학적 표현 (전공자 심화)
부울 대수에서는 논리 연산을 일반 수학 연산처럼 표현할 수 있다. 이는 디지털 회로 설계에서 게이트 동작을 분석·최적화할 때 필수적이다.
| ¬p (NOT) | 1 − p |
| p ∧ q (AND) | p · q |
| p ∨ q (OR) | p + q − p·q |
| p ⊕ q (XOR) | p·(1−q) + q·(1−p) |
예시 검증 (p = 0, q = 1일 때)
- p ∧ q = 0 · 1 = 0 (거짓) ✅
- p ∨ q = 0 + 1 − 0·1 = 1 (참) ✅
- p ⊕ q = 0·(1−1) + 1·(1−0) = 0 + 1 = 1 (참) ✅
이 수학적 표현은 프로그래밍에서 비트 연산이나 조건문 최적화에도 그대로 활용된다.
📌 한눈에 보는 핵심정리
| 부울 대수 | 논리를 0/1로 표현하는 대수 | 조지 불(1854) 창시 |
| 명제 | 참/거짓 판별 가능한 문장 | 주관·명령·의문문은 제외 |
| AND (∧) | 논리곱 | 모두 참일 때만 참 |
| OR (∨) | 논리합 | 하나라도 참이면 참 |
| NOT (¬) | 부정 | 진리값 반전 |
| XOR (⊕) | 배타적 OR | 정확히 하나만 참일 때 참 |
| IMPLY (→) | 함축 | T→F만 거짓, 나머지는 참 |
| IFF (↔) | 상호조건 | 진리값이 같을 때만 참 |
| 진리표 | 모든 입력 조합의 결과 표 | 논리식 검증의 핵심 도구 |
| 섀넌의 발견 | 부울 대수 = 전기 회로 | 디지털 컴퓨팅의 시작 |
🧠 예상문제 2제
문제 1. 함축 명제의 진리값 판별
다음 함축 명제 중 거짓인 것은?
① P: "2+2=4" (참), Q: "지구는 둥글다" (참) → P → Q ② P: "고양이는 새다" (거짓), Q: "1+1=3" (거짓) → P → Q ③ P: "물은 H₂O이다" (참), Q: "태양은 차갑다" (거짓) → P → Q ④ P: "1=2" (거짓), Q: "하늘은 파랗다" (참) → P → Q
👉 정답: ③
함축 명제는 가정(P)이 참이면서 결론(Q)이 거짓일 때만 거짓이 된다.
- ① T → T = T
- ② F → F = T
- ③ T → F = F ✅ (정답)
- ④ F → T = T
문제 2. 상호조건과 함축의 관계
다음 명제와 논리적으로 동치(같은 의미)인 것은?
P ↔ Q
① P ∧ Q ② P ∨ Q ③ (P → Q) ∧ (Q → P) ④ (P → Q) ∨ (Q → P)
👉 정답: ③
상호조건 P ↔ Q는 "P이면 Q이고, 동시에 Q이면 P"를 의미하므로, 두 함축의 논리곱(AND) 으로 표현된다.
P ↔ Q ≡ (P → Q) ∧ (Q → P)
'📌 SW전공-개념 > 이산구조' 카테고리의 다른 글
| [이산구조 개념-07] 형식적 증명 — 추론 규칙으로 결론 만들기 (1) | 2026.05.30 |
|---|---|
| [이산구조 개념-06] 추론 규칙 7선 — 논리적 추론의 도구함 (0) | 2026.05.29 |
| [이산구조 개념-05] 한정자의 순서·부정·동치 — 술어 논리 심화 (0) | 2026.05.28 |
| [이산구조 특별편 1] 드모르간과 AI — 19세기 논리가 21세기 인공지능이 되기까지 (1) | 2026.05.26 |
| [이산구조 개념-02] 항진·부정·동치 — 명제의 세 가지 운명 (0) | 2026.05.24 |