Boolean Algebra & Circuit Logic

1. Overview

부울 대수와 회로 논리(Boolean Algebra & Circuit Logic, BAC)는 철학적 논리를 0과 1이라는 전압(Voltage)의 유무로 치환하여, 차가운 실리콘 반도체 위에서 컴퓨터가 '생각'을 할 수 있게 만드는 물리학과 수학의 결합점입니다.

학습자는 명제의 참/거짓을 이진수 논리로 매핑하는 **부울 방정식(Boolean Equation)**을 설계하고, 이를 카르노 맵(K-Map)을 이용해 트랜지스터 개수를 최소화하는 방향으로 **논리식 간소화(Simplification)**를 해부합니다. 나아가 이 수식들이 어떻게 실제 하드웨어인 AND, OR, NOT 게이트를 거쳐 덧셈을 수행하는 **조합 논리 회로(Combinational Logic)**로 조립되는지 통달하여, 추상적인 소프트웨어 로직이 물리적 CPU 코어의 회로 설계로 맵핑되는 딥 아키텍처 역량을 확보합니다.

2. Scope & Boundaries

In-Scope

• 부울 대수 역학 (Boolean Mechanics): 0과 1의 이진수 대수학, 기본 공리(Axioms), 드모르간의 법칙(De Morgan's Theorem), 쌍대성의 원리(Duality).
• 논리 함수와 정규형 (Normal Forms): 곱의 합(SOP: Sum of Products)과 합의 곱(POS: Product of Sums), 최소항(Minterm)과 최대항(Maxterm).
• 논리 최소화 (Logic Minimization): 카르노 맵(Karnaugh Map), 퀸-맥클러스키 알고리즘(Quine-McCluskey).
• 조합 논리 회로 (Combinational Logic): 논리 게이트(AND, OR, NOT, XOR), 가산기(Adder), 멀티플렉서(Multiplexer, MUX), 디코더(Decoder).

Out-of-Scope

• 클럭과 메모리(순차 논리): 시간에 따라 상태가 변하는 플립플롭(Flip-Flop)이나 클럭 사이클 $\rightarrow$ 02-01. Digital Logic & Processor Physics 영역.
• 반도체의 양자역학적 전기 특성: P-N 접합과 MOSFET의 정밀한 전압 임계치 계산 $\rightarrow$ 전자공학/물리학 영역.

Boundaries

• BAC vs. Propositional Logic (01-02-01): 명제 논리가 인간의 언어를 참/거짓으로 쪼개는 '기호학'이라면, BAC는 그 기호들을 AND/OR 게이트라는 물리적 하드웨어 부품으로 조립하여 실제 연산을 수행하는 '디지털 공학'의 관점입니다.

3. Counterexample

• 최소화 없는 게이트 낭비 (Unoptimized Logic Fallacy): 기능이 똑같다고 해서 아무 생각 없이 논리식 $F = AB + A\bar{B}C + ABC$를 있는 그대로 하드웨어에 때려 박는 행위. 카르노 맵으로 간소화하면 $F = A$처럼 트랜지스터 수천 개를 날려버릴 수 있는데, 이를 무시하면 칩의 면적이 커지고 발열이 심해지며 제조 단가가 기하급수적으로 폭발하는 비효율의 극치를 맛보게 됩니다.
• XOR의 배타성 오판 (Exclusive OR Misinterpretation): 일상어의 "A 거나 B 다(OR)"를 논리합(Inclusive OR)으로만 이해하고, 두 개가 동시에 켜졌을 때는 꺼져야 하는 배타적 논리합(XOR)의 물리를 간과하는 설계. 덧셈기의 코어를 설계할 때 비트 연산에서 1+1=0(캐리 발생)이 되는 것은 XOR 게이트의 물리적 특성인데, 이를 단순 OR로 짜면 산술 연산 장치(ALU)가 완전히 붕괴합니다.

4. Prerequisites

• 명제 및 술어 논리 (Basic): AND, OR, NOT의 논리적 의미와 드모르간의 법칙을 부울 변수($A, B, C$)로 치환하기 위한 사전 지식. (01-02-01 PPL)

5. Learning Map

6. Learning Topics

Basic

Core Topic 01: 부울 공리와 0/1의 대수학 (Boolean Postulates)

• Why to Learn: 10진수 수학의 사칙연산을 버리고, 컴퓨터가 유일하게 이해하는 전압의 On(1)/Off(0) 상태를 더하고 곱하는 새로운 물리 법칙을 머리에 박기 위해서입니다.
• What to Learn:
  • Concepts: 논리 변수, 0과 1, 부울 공리(Identity, Null, Idempotent, Complement).
  • Skills: 분배 법칙(Distributive Law), 흡수 법칙(Absorption Law, $A + AB = A$), 쌍대성(Duality).
  • Tools: 부울 대수 계산기.
  • Trade-offs: 인간의 수학에서는 성립하지 않는 $A + BC = (A+B)(A+C)$ 분배 법칙이 부울 대수에서는 성립하는 기이함 vs 이를 통해 수식을 기계적으로 비틀어버리는 강력한 치환 능력.
• How to Learn:
  • 1단계: "A 스위치를 켜거나(OR) A 스위치를 켠다($A + A$)"는 물리적으로 그냥 A 스위치를 켠 것($A$)과 똑같다는 멱등 법칙(Idempotent Law)을 스위치 회로의 직렬/병렬로 해부합니다.
  • 2단계: 수식 $A + \bar{A}B$가 있을 때, 인간의 직관으로는 복잡해 보이지만 부울 대수의 분배 법칙을 쓰면 $A + B$로 증발해버리는(흡수) 마법을 뜯어봅니다.
• Implement: 3개의 부울 변수를 가진 복잡한 조건문 if (A || (!A && B))를 인자로 받아, 하드코딩된 부울 법칙(흡수 법칙 등)을 적용해 A || B라는 최적화된 논리 트리(AST)로 줄여주는 수식 평가기 작성.

Recommended

Core Topic 02: 최소항, 최대항과 정규형 (Minterms & SOP/POS)

• Why to Learn: "이런이런 조건일 때만 불이 켜지게 해주세요"라는 고객의 진리표(Truth Table) 요구사항을 보고, 즉시 에러가 안 나는 100% 완벽한 부울 방정식으로 자동 변환하기 위함입니다.
• What to Learn:
  • Concepts: 최소항(Minterm), 최대항(Maxterm).
  • Skills: 곱의 합(Sum of Products, SOP), 합의 곱(Product of Sums, POS), 정규형(Canonical Form).
  • Tools: 진리표 $\rightarrow$ 부울 식 컨버터.
  • Trade-offs: 결과가 1이 나오는 줄(Row)만 골라내어 AND 덩어리들을 OR로 묶는 직관적이고 쉬운 SOP 방식 vs 결과가 0이 나오는 줄이 훨씬 적을 때는 POS 방식을 써서 게이트 수를 절반으로 줄이는 물리적 최적화의 딜레마.
• How to Learn:
  • 1단계: 변수 A, B, C가 있을 때 진리표에서 결과가 1인 줄이 0, 1, 1이라면 이를 $\bar{A}BC$라는 하나의 최소항(Minterm) 곱으로 묶어버리는 논리를 해부합니다.
  • 2단계: 여러 개의 최소항들을 덧셈(OR)으로 쫙 나열한 SOP 형태가, 논리 설계의 "단 하나의 거짓도 없는 완벽한 원본 설계도(정규형)"임을 증명합니다.
• Implement: $2^N$ 줄짜리 0과 1 배열(Truth Table 결과열)을 입력받으면, 결과가 1인 항들만 싹 쓸어 모아 인간이 읽을 수 있는 SOP(Sum of Products) 문자열 수식(예: A'BC + AB'C + ABC)으로 자동 생성하는 컴파일러 1단계 모듈 구현.

Practical

Core Topic 03: 카르노 맵과 하드웨어 다이어트 (K-Map Minimization)

• Why to Learn: 정규형(SOP)으로 뽑아낸 길고 거추장스러운 수식을, 트랜지스터(돈)를 제일 적게 쓰는 최적의 상태로 '시각적'으로 압축해 내기 위해서입니다.
• What to Learn:
  • Concepts: 카르노 맵(Karnaugh Map), 인접성(Adjacency), 그레이 코드(Gray Code).
  • Skills: 1 묶기(Grouping: 2, 4, 8개 단위), 필수 주항(Essential Prime Implicant), 무관 조건(Don't Care, X).
  • Tools: 2/3/4 변수 K-Map 그리드.
  • Trade-offs: 사람의 눈으로 1의 무리를 사각형으로 묶어 순식간에 중복을 지우는 K-Map의 직관성 vs 변수가 5개 이상 넘어가면 4차원 도형이 되어버려 인간의 뇌로는 풀 수 없는 공간적 한계.
• How to Learn:
  • 1단계: K-Map의 축이 00, 01, 10, 11이 아니라 단 1비트만 바뀌는 그레이 코드 00, 01, 11, 10으로 배열되어야만, 시각적으로 인접한 사각형을 묶었을 때 잉여 변수($A + \bar{A}$)가 물리적으로 소거되는 원리를 해부합니다.
  • 2단계: "이 조건은 절대 발생하지 않는다"는 무관 조건(Don't Care, X)을 1로 취급해서 더 큰 사각형으로 묶었을 때, 트랜지스터(논리 게이트) 10개가 2개로 압축되는 기적의 최적화율을 뜯어봅니다.
• Implement: 4변수 부울 배열(16비트)을 입력하면, 인접한 1들(비트마스크)을 재귀적으로 묶어 소거 가능한 최대 크기의 사각형(Prime Implicants)을 찾아내고, 최적화된 수식을 반환하는 퀸-맥클러스키 알고리즘 기반 최소화 엔진.

Advanced

Core Topic 04: 조합 논리 회로 설계 (Combinational Circuits)

• Why to Learn: 종이 위에서 끄적이던 부울 수식들을 가져와, 컴퓨터의 심장인 ALU(산술논리장치)의 덧셈 연산기법과 데이터 선택 스위치(MUX)로 물리적 조립을 해내기 위함입니다.
• What to Learn:
  • Concepts: 반가산기(Half Adder), 전가산기(Full Adder), 멀티플렉서(MUX), 디코더/인코더.
  • Skills: XOR 게이트를 활용한 덧셈 로직, 제어선(Select Line)을 통한 데이터 라우팅.
  • Tools: Logisim 회로 시뮬레이터.
  • Trade-offs: 단일 트랜지스터로 덧셈을 수행하려는 미시적 접근 vs 하위 전가산기 수십 개를 레고 블록처럼 이어 붙여 32비트 가산기를 순식간에 만들어내는(Ripple Carry) 추상화 계층의 편의성과 신호 지연(Propagation Delay)의 모순.
• How to Learn:
  • 1단계: 1 + 1 = 10 이 되는 이진수 덧셈의 합(Sum)이 완벽한 XOR 게이트($A\bar{B} + \bar{A}B$)이고, 올림수(Carry)가 완벽한 AND 게이트($AB$)임을 진리표로 증명하여 반가산기를 납땜해 봅니다.
  • 2단계: 4개의 입력 채널 중 하나만 골라서 CPU로 보내는 멀티플렉서(MUX)가, 어떻게 제어 신호(Selector)의 부울 논리식으로 동작하는 데이터계의 물리적 스위치가 되는지 해부합니다.
• Implement: AND, OR, XOR 소프트웨어 게이트 함수만 조합하여 8비트 이진수 A와 B를 인자로 받아 올림수(Carry) 처리를 포함해 덧셈 결과를 리턴하는 전가산기(Full Adder) 클래스 체인 구현.

7. Terminology

8. References

Primary

• [P1] CS2023 - DS/Boolean Algebra — Formal foundations of logic.
• [P1] CS2023 - AR/Digital Logic and Digital Systems — Physical hardware mapping.

Secondary

• [Digital Design and Computer Architecture] Harris & Harris — Integrated view of logic and arch.
• [Digital Systems: Principles and Applications] Tocci — Deep dive into gate mechanics.

Industry

• [IEEE Standard for Logic Symbols] — Industry graphical standards.
• [Intel/AMD Instruction Set Architecture] — Boolean logic at scale.

9. Final Checklist

Primary

• 불 대수의 이중성(Duality) 원리를 설명하고, 특정 논리식의 듀얼 식을 물리적으로 도출할 수 있는 가? (P1)
• 3변수와 4변수 카르노 맵을 사용하여 복잡한 논리식을 주프라임 함축항(Prime Implicants)으로 최소화 가능한가? (P1)

Secondary

• NAND 게이트만을 사용하여 OR, XOR 게이트의 기능을 물리적으로 구현하고 그 타당성을 입증할 수 있는가?
• 조합 회로 설계 시 발생할 수 있는 '해저드(Hazard)'를 카르노 맵 상의 인접 항 결합으로 제거할 수 있는가?

Industry

• 실무 회로 설계 시 게이트의 팬-인(Fan-in)과 팬-아웃(Fan-out) 제한이 논리적 계층 구조에 미치는 물리적 영향을 분석할 수 있는가? (SFIA)
• 대용량 데이터 버스의 멀티플렉싱(Multiplexing) 구조를 논리 게이트 관점에서 설계하여 자원 충돌을 방지할 수 있는 가?