Boolean Algebra & Circuit Logic

1. Overview

불 대수 및 회로 논리(Boolean Algebra & Circuit Logic, BCL)는 0과 1이라는 추상적 기호가 어떻게 물리적 전압과 트랜지스터의 상호작용으로 치환되어 명령을 수행하는지 그 접점을 다룹니다.

모든 디지털 컴퓨팅 하드웨어는 불 대수의 물리적 발현입니다. 학습자는 불 대수의 공리와 연산 법칙, 논리 게이트(AND, OR, NOT, XOR)의 물리적 조합, 그리고 회로의 복잡도를 낮추어 효율을 극대화하는 회로 최적화(Minimization) 기술을 배웁니다. 이를 통해 수조 개의 연산이 1초 만에 이루어지는 현대 CPU의 논리적 아키텍처를 이해하고, 불필요한 연소와 지연이 없는 효율적인 하드웨어-소프트웨어 통합 설계를 수행하는 능력을 갖춥니다.

2. Scope & Boundaries

In-Scope

• Boolean Axiomatics: 보충 법칙, 항등 법칙 및 이중 부정 등 불 대수의 수학적 기초
• Gate Mechanics: 기본 논리 게이트의 스위칭 물리 및 범용 게이트(NAND, NOR)의 역학
• Combinational Systems: 가산기(Adder), 멀티플렉서(MUX) 등 조합 논리 회로의 수학적 모델링
• Simplification Physics: 카르노 맵(Karnaugh Map) 및 퀸-맥클러스키 알고리즘을 이용한 최소화

Out-of-Scope

• 트랜지스터 내의 반도체 물리 상세 (전자공학 특계 영역)
• 순차 회로(Sequential Circuit)의 클록 동기화 깊은 논리 (02-01 DLP 영역으로 위임)

Boundaries

• BCL vs. Digital Logic Physics: 02-01(DLP)이 주로 '클록과 타이밍'에 집중한다면, BCL은 입력값에 따른 출력값의 '순수 논리적 결정 관계'와 그 수리적 간소화에 집중합니다.

3. Counterexample

• 단순히 "논리 연산자를 코드에서 사용하는 것"은 BCL 학습이 아닙니다. 왜 NAND 게이트만으로 모든 논리 회로를 물리적으로 재현할 수 있는지(Functional Completeness) 그 증명 과정을 설명할 수 있어야 하고, 특정 회로 설계에서 글리치(Glitch) 현상이 왜 논리적 인접 항의 누락에서 기인하는지 카르노 맵으로 규명하지 못한다면 BCL의 깊이를 이해하지 못한 것입니다.

4. Prerequisites

• 명제 및 서술어 논리 (Basic): 진리표와 기본 논리 연산자 이해가 필수입니다. (02-01 PPL)
• 컴퓨터 아키텍처 (Recommended): 2진수 연산과 CPU 기본 구조 기초가 권장됩니다. (02. CA)

5. Learning Map

1. Symbolic Logic: 0과 1을 변수로 하는 대수 체계를 확립합니다.
2. Physical Translation: 수학적 기호를 물리적 신호로 바꾸는 게이트 추상화를 이해합니다.
3. Synthesis & Design: 여러 게이트를 묶어 특정 기능을 수행하는 논리 뭉치를 설계합니다.
4. Energy & Area Optimization: 동일한 기능을 수행하되 게이트 수를 최소화하는 물리적 압축을 수행합니다.

6. Learning Topics

Basic

Core: 불 대수의 연산과 법칙 (Boolean Foundations)

• Why to Learn: 복잡한 조건식을 수학적으로 정제하여 코드 가독성과 하드웨어 효율을 동시에 높이기 위함입니다.
• What to Learn:
  • 교환, 결합, 분배 법칙의 불 대수적 성질
  • 흡수 법칙(Absorption Law)과 0/1의 지배력
  • 대수적 간소화: 식을 전개하고 묶어 항의 개수를 줄이는 물리적 과정
• How to Learn:
  • $A + AB = A$ 와 같은 불 대수 식의 타당성을 벤 다이어그램과 진리표로 동시 증명
  • 복잡한 불린 변수 4개를 사용하는 식을 대수 법칙으로만 최소화해 보는 연습
• Implement: 입력된 불 대수 식을 단계별 대수 법칙을 적용해 줄여나가는 단계별 계산기

Recommended

Core: 논리 게이트와 유니버설 로직 (Gate Physics)

• Why to Learn: 추상적 수식이 하드웨어에서 실제 칩으로 구현되는 방식을 이해하기 위해서입니다.
• What to Learn:
  • AND, OR, NOT, XOR, XNOR 게이트의 동작 특성
  • 유니버설 게이트: NAND와 NOR 게이트의 물리적 유연성
  • 버퍼(Buffer)와 인버터(Inverter)의 신호 강화 및 반전 물리
• How to Learn:
  • 회로 시뮬레이터(Logisim 등)를 이용해 XOR 게이트를 NAND 게이트로만 재구성해 보는 실습
  • 게이트 지연(Gate Delay)이 전체 연산 속도에 미치는 물리적 누적 효과 분석
• Implement: 기본 게이트들의 조합으로 $n$-bit 비교기를 설계하는 논리 회로도

Practical

Core: 회로 최소화와 카르노 맵 (Circuit Minimization)

• Why to Learn: 칩의 크기를 줄이고 전력 소모를 물리적으로 개선하는 핵심 기술이기 때문입니다.
• What to Learn:
  • 곱들의 합(SOP)과 합들의 곱(POS) 표현법
  • 카르노 맵(Karnaugh Map): 인접한 1들을 묶어 간소화하는 시각적 규칙
  • Don't Care 항: 출력값이 상관없는 구간을 이용한 극한의 최적화
• How to Learn:
  • 4변수 카르노 맵에서 '감싸기(Wrapping)' 규칙을 적용해 가장 큰 묶음을 찾는 연습
  • 퀸-맥클러스키 알고리즘을 수동으로 수행하며 컴퓨터가 어떻게 대량의 변수를 최소화하는지 학습
• Implement: 0, 1, X(don't care)를 입력받아 최적의 SOP 형태를 출력하는 최적화 모듈

Advanced

Core: 조합 논리 설계와 데이터 경로 (Functional Units)

• Why to Learn: CPU의 데이터 처리부(ALU)가 어떻게 산술 및 논리 연산을 수행하는지 이해하기 위해서입니다.
• What to Learn:
  • 가산기(Adder): 하프/풀 에더를 통한 비트 캐리 전파 물리
  • 인코더와 디코더: 신호의 압축과 확장을 관장하는 논리 위계
  • ALU(Arithmetic Logic Unit)의 기본 구조와 제어 신호 역학
• How to Learn:
  • 4비트 리플 캐리 가산기(Ripple Carry Adder)의 지연 시간을 계산하고 성능 한계 분석
  • 7-Segment 디스플레이 구동을 위한 디코더 논리를 직접 설계해 보는 실습
• Implement: 논리 게이트로만 구현된 소프트웨어 기반 8비트 가상 ALU

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) 구조를 논리 게이트 관점에서 설계하여 자원 충돌을 방지할 수 있는 가?