28. AND / OR / NOT 게이트 상세 (Boolean Expression & Circuit)

핵심 인사이트 (3줄 요약)

본질: AND·OR·NOT은 디지털 논리의 3대 기본 연산이자 불 대수(Boolean Algebra)의 기본 연산자다. 이 세 연산의 조합으로 모든 논리 함수를 표현할 수 있으며, 이를 기능적 완전성(Functional Completeness)이라 한다.

가치: AND·OR·NOT은 단순 게이트 이상의 의미가 있다. 데이터베이스 WHERE 절, 프로그래밍 조건문, 암호화 알고리즘, CPU 제어 신호 모두 이 세 연산의 조합으로 구현된다. 불 대수를 이해하면 디지털 시스템 전체를 이해할 수 있다.

판단 포인트: 드 모르간 법칙(De Morgan's Law)은 AND/OR/NOT을 상호 변환하는 핵심 규칙이다. NOT(A AND B) = NOT(A) OR NOT(B), NOT(A OR B) = NOT(A) AND NOT(B). 이 법칙으로 NAND를 OR로, NOR를 AND로 등가 변환하여 회로를 최소화한다.

Ⅰ. 개요 및 필요성

┌──────────────────────────────────────────────────────┐
│        AND / OR / NOT 진리표 & 표현                   │
├──────────────────────────────────────────────────────┤
│ AND: F = A·B  (둘 다 1이면 1)                        │
│  A=0,B=0→0 / A=0,B=1→0 / A=1,B=0→0 / A=1,B=1→1    │
│                                                       │
│ OR:  F = A+B  (하나라도 1이면 1)                      │
│  A=0,B=0→0 / A=0,B=1→1 / A=1,B=0→1 / A=1,B=1→1    │
│                                                       │
│ NOT: F = Ā   (반전)                                   │
│  A=0→1 / A=1→0                                       │
└──────────────────────────────────────────────────────┘

📢 섹션 요약 비유: AND는 경비원 두 명이 모두 "통과"해야 들어갈 수 있는 이중 보안문, OR는 한 명만 "통과"해도 들어갈 수 있는 문, NOT는 "예"를 "아니오"로 바꾸는 반전 스위치다.

Ⅱ. 아키텍처 및 핵심 원리

불 대수 기본 법칙

항등법칙:  A·1 = A   / A+0 = A
영법칙:    A·0 = 0   / A+1 = 1
멱등법칙:  A·A = A   / A+A = A
보수법칙:  A·Ā = 0   / A+Ā = 1
이중부정:  NOT(NOT A) = A

드 모르간 법칙:
  NOT(A·B) = NOT(A) + NOT(B)   → NAND = NOR(NOT inputs)
  NOT(A+B) = NOT(A)·NOT(B)     → NOR  = NAND(NOT inputs)

SOP와 POS 형식

SOP (Sum of Products): F = AB + ĀC + BC
  → 각 행이 1인 최소항(Minterm)의 OR 합

POS (Product of Sums): F = (A+B)·(Ā+C)
  → 각 행이 0인 최대항(Maxterm)의 AND 곱

📢 섹션 요약 비유: SOP는 메뉴판에서 원하는 메뉴를 선택하는 것(참인 경우만 골라 OR로 합침), POS는 불만족 메뉴를 제외하는 것(거짓인 경우를 AND로 곱하여 제외)이다.

Ⅲ. 비교 및 연결

비교	AND	OR	NAND (드 모르간 변환)
기본 식	A·B	A+B	NOT(A·B)
드 모르간 변환	-	-	NOT(A)+NOT(B)
CMOS 트랜지스터	6T	6T	4T
실무 선호	논리 설계	논리 설계	물리 구현

📢 섹션 요약 비유: 드 모르간 법칙은 교통 신호 변환이다. "직진 AND 좌회전 금지" = "직진 금지 OR 좌회전 금지". 표현 방식이 달라도 같은 의미를 전달한다.

Ⅳ. 실무 적용 및 기술사 판단

SQL 에서의 AND/OR/NOT

SELECT * FROM orders
WHERE status = 'active'         -- 조건 1
  AND (amount > 100             -- AND 연산
       OR priority = 'high')    -- OR 연산
  AND NOT cancelled;            -- NOT 연산

카르노 맵 최소화

불 대수 식을 카르노 맵으로 그리면 AND/OR 게이트 수를 최소화하는 최적 식 도출.
인접 1을 묶어 공통 인수 제거 → 게이트 수 감소 → 회로 면적·전력 절감.
📢 섹션 요약 비유: 카르노 맵은 숫자 퍼즐 스도쿠다. 1이 몰려있는 블록을 찾아 묶으면(그룹화) 공통 패턴이 드러나고, 그것이 게이트를 최소화하는 최적 식이 된다.

Ⅴ. 기대효과 및 결론

기대효과	내용
회로 최적화	불 대수 간소화로 게이트 수 최소화
전력 절감	게이트 수 감소 → CMOS 전력 소모 감소
논리 검증	드 모르간 법칙으로 회로 등가성 증명

양자 컴퓨팅에서는 고전 AND/OR/NOT 대신 양자 게이트(Hadamard, CNOT, Toffoli)를 사용하며, Toffoli 게이트는 고전 AND와 NOT을 가역적(Reversible)으로 구현한 양자 등가 게이트다.

📢 섹션 요약 비유: 양자 게이트는 AND/OR/NOT을 4D 공간에서 표현한 것이다. 고전 게이트가 0 또는 1만 다루는 흑백 논리라면, 양자 게이트는 중첩·얽힘으로 무한한 색 조합을 다룰 수 있다.

📌 관련 개념 맵

개념	연결 포인트
불 대수	AND/OR/NOT의 수학적 체계
드 모르간 법칙	AND↔OR 변환의 핵심 규칙
NAND/NOR	AND+NOT, OR+NOT 조합 (기능 완전)
카르노 맵	불 식 최소화 시각화 도구
SOP/POS	논리 함수의 두 가지 정규 표현

📈 관련 키워드 및 발전 흐름도

[불 대수 — AND/OR/NOT 기본 연산 체계]
    │
    ▼
[드 모르간 법칙 — 게이트 등가 변환]
    │
    ▼
[카르노 맵 — 불 식 최소화]
    │
    ▼
[CMOS 게이트 구현 — 트랜지스터 최소화]
    │
    ▼
[양자 게이트 — Toffoli/CNOT 가역 논리]

👶 어린이를 위한 3줄 비유 설명

AND는 두 자물쇠가 모두 열려야 열리는 문, OR는 하나만 열려도 열리는 문, NOT은 열린 것을 닫고 닫힌 것을 여는 마법 버튼이에요!
드 모르간 법칙은 "두 사람 모두 오면 안 돼" = "한 사람이 안 오거나 다른 사람이 안 오면 돼"와 같은 논리 변환이에요!
카르노 맵으로 게이트를 최소화하면 칩이 더 작고 전기도 적게 써요!