논리 게이트
논리 게이트¶
개요¶
논리 게이트는 디지털 회로의 기본 구성 요소로, 하나 이상의 입력 신호를 받아 논리 연산을 수행하고 출력 신호를 생성합니다. 이 레슨에서는 기본 논리 게이트의 종류, 진리표 작성법, 불 대수의 법칙, 그리고 논리식 간소화 방법을 학습합니다.
난이도: ⭐ (기초)
목차¶
- 논리 게이트 기초
- 기본 게이트 (AND, OR, NOT)
- 유니버설 게이트 (NAND, NOR)
- XOR과 XNOR 게이트
- 진리표 작성법
- 불 대수 기초
- 불 대수 법칙
- 논리식 간소화
- 연습 문제
1. 논리 게이트 기초¶
디지털 신호¶
┌─────────────────────────────────────────────────────────────┐
│ 디지털 신호 │
├─────────────────────────────────────────────────────────────┤
│ │
│ 아날로그 vs 디지털: │
│ │
│ 아날로그: 연속적인 값 디지털: 이산적인 값 │
│ │
│ │ /\ /\ │ ┌──┐ ┌──┐ │
│ │/ \ / \ │ │ │ │ │ │
│ ───┼────\/────\── ───┼─┘ └──┘ └── │
│ │ │ │
│ │
│ 디지털 논리에서: │
│ - HIGH (1, True): 전압이 높음 (예: 5V, 3.3V) │
│ - LOW (0, False): 전압이 낮음 (예: 0V) │
│ │
└─────────────────────────────────────────────────────────────┘
논리 게이트란?¶
논리 게이트 (Logic Gate):
입력 신호의 논리 연산을 수행하여 출력을 생성하는 전자 회로
┌─────────────────────────────────────────────────────────────┐
│ │
│ 입력 A ─────┐ │
│ │ │
│ ├───[ 논리 게이트 ]─────→ 출력 Y │
│ │ │
│ 입력 B ─────┘ │
│ │
│ Y = f(A, B) ← 논리 함수 │
│ │
└─────────────────────────────────────────────────────────────┘
게이트의 물리적 구현:
- 트랜지스터 (CMOS, TTL 등)
- 릴레이 (초기 컴퓨터)
- 진공관 (1세대 컴퓨터)
논리 게이트 종류 요약¶
┌─────────────┬────────────┬────────────────────────────────────┐
│ 게이트 │ 기호 │ 설명 │
├─────────────┼────────────┼────────────────────────────────────┤
│ AND │ A·B │ 둘 다 1일 때만 1 │
│ OR │ A+B │ 하나라도 1이면 1 │
│ NOT │ A' │ 입력 반전 │
├─────────────┼────────────┼────────────────────────────────────┤
│ NAND │ (A·B)' │ AND의 반전 │
│ NOR │ (A+B)' │ OR의 반전 │
├─────────────┼────────────┼────────────────────────────────────┤
│ XOR │ A⊕B │ 서로 다를 때 1 │
│ XNOR │ (A⊕B)' │ 서로 같을 때 1 │
└─────────────┴────────────┴────────────────────────────────────┘
2. 기본 게이트 (AND, OR, NOT)¶
AND 게이트¶
AND 게이트: 모든 입력이 1일 때만 출력이 1
회로 기호:
┌────┐
A ───┤ │
│ & ├───Y Y = A · B = A AND B
B ───┤ │
└────┘
IEEE/ANSI 기호:
A ───┬────╮
│ ├───Y
B ───┴────╯
진리표:
┌───┬───┬───────┐
│ A │ B │ A·B │
├───┼───┼───────┤
│ 0 │ 0 │ 0 │
│ 0 │ 1 │ 0 │
│ 1 │ 0 │ 0 │
│ 1 │ 1 │ 1 │
└───┴───┴───────┘
실생활 비유:
- 직렬 연결된 스위치
- 두 스위치가 모두 ON일 때만 전구가 켜짐
A B 전구
─/ ─────/ ─────◯─
OR 게이트¶
OR 게이트: 하나 이상의 입력이 1이면 출력이 1
회로 기호:
┌────╲
A ───┤ ╲
│ ≥1 >───Y Y = A + B = A OR B
B ───┤ ╱
└────╱
IEEE/ANSI 기호:
A ───╲╲
╲╲────Y
B ───╱╱
진리표:
┌───┬───┬───────┐
│ A │ B │ A+B │
├───┼───┼───────┤
│ 0 │ 0 │ 0 │
│ 0 │ 1 │ 1 │
│ 1 │ 0 │ 1 │
│ 1 │ 1 │ 1 │
└───┴───┴───────┘
실생활 비유:
- 병렬 연결된 스위치
- 하나만 ON이어도 전구가 켜짐
┌──/ ──┐ A
────┤ ├────◯──
└──/ ──┘ B
전구
NOT 게이트 (인버터)¶
NOT 게이트: 입력을 반전시킴
회로 기호:
┌────╲
A ───┤ 1 o───Y Y = A' = Ā = NOT A = ¬A
└────╱
진리표:
┌───┬───────┐
│ A │ A' │
├───┼───────┤
│ 0 │ 1 │
│ 1 │ 0 │
└───┴───────┘
표기법:
- A' (프라임)
- Ā (윗줄, 오버바)
- NOT A
- ¬A
- !A (프로그래밍)
- ~A (비트 연산)
실생활 비유:
- 상시 닫힘(NC) 스위치
- 버튼을 누르면 회로가 끊어짐
기본 게이트 조합¶
3입력 AND 게이트:
A ───┐
│ ┌────┐
B ───┼────┤ │
│ │ & ├───Y Y = A · B · C
C ───┘ │ │
└────┘
진리표 (8가지 조합):
┌───┬───┬───┬───────┐
│ A │ B │ C │ A·B·C │
├───┼───┼───┼───────┤
│ 0 │ 0 │ 0 │ 0 │
│ 0 │ 0 │ 1 │ 0 │
│ 0 │ 1 │ 0 │ 0 │
│ 0 │ 1 │ 1 │ 0 │
│ 1 │ 0 │ 0 │ 0 │
│ 1 │ 0 │ 1 │ 0 │
│ 1 │ 1 │ 0 │ 0 │
│ 1 │ 1 │ 1 │ 1 │
└───┴───┴───┴───────┘
3입력 OR 게이트:
Y = A + B + C
하나라도 1이면 출력이 1
모두 0일 때만 출력이 0
3. 유니버설 게이트 (NAND, NOR)¶
NAND 게이트¶
NAND 게이트: AND의 반전 (NOT AND)
회로 기호:
┌────╲
A ───┤ o───Y Y = (A · B)' = A NAND B
B ───┤ ╱
└────╱
진리표:
┌───┬───┬──────────┐
│ A │ B │ (A·B)' │
├───┼───┼──────────┤
│ 0 │ 0 │ 1 │
│ 0 │ 1 │ 1 │
│ 1 │ 0 │ 1 │
│ 1 │ 1 │ 0 │
└───┴───┴──────────┘
AND와 비교:
┌───┬───┬───────┬──────────┐
│ A │ B │ A·B │ (A·B)' │
├───┼───┼───────┼──────────┤
│ 0 │ 0 │ 0 │ 1 │
│ 0 │ 1 │ 0 │ 1 │
│ 1 │ 0 │ 0 │ 1 │
│ 1 │ 1 │ 1 │ 0 │
└───┴───┴───────┴──────────┘
NOR 게이트¶
NOR 게이트: OR의 반전 (NOT OR)
회로 기호:
┌────╲
A ───╲ o───Y Y = (A + B)' = A NOR B
B ───╱ ╱
└────╱
진리표:
┌───┬───┬──────────┐
│ A │ B │ (A+B)' │
├───┼───┼──────────┤
│ 0 │ 0 │ 1 │
│ 0 │ 1 │ 0 │
│ 1 │ 0 │ 0 │
│ 1 │ 1 │ 0 │
└───┴───┴──────────┘
OR와 비교:
┌───┬───┬───────┬──────────┐
│ A │ B │ A+B │ (A+B)' │
├───┼───┼───────┼──────────┤
│ 0 │ 0 │ 0 │ 1 │
│ 0 │ 1 │ 1 │ 0 │
│ 1 │ 0 │ 1 │ 0 │
│ 1 │ 1 │ 1 │ 0 │
└───┴───┴───────┴──────────┘
유니버설 게이트의 의미¶
┌─────────────────────────────────────────────────────────────┐
│ 유니버설 게이트 (Universal Gate) │
├─────────────────────────────────────────────────────────────┤
│ │
│ NAND와 NOR는 "유니버설 게이트"입니다. │
│ → 이 게이트만으로 모든 논리 연산을 구현할 수 있습니다. │
│ │
│ NAND로 다른 게이트 구현: │
│ │
│ NOT: │
│ A ───┬───┤ NAND ├───→ A' │
│ └───┤ │ │
│ │
│ AND: │
│ A ───┤ NAND ├───┤ NAND ├───→ A·B │
│ B ───┤ │───┤ │ │
│ │
│ OR: │
│ A ───┤ NAND ├─┐ │
│ A ───┤ │ └───┤ NAND ├───→ A+B │
│ B ───┤ NAND ├─────┤ │ │
│ B ───┤ │ │
│ │
└─────────────────────────────────────────────────────────────┘
NAND로 기본 게이트 구현¶
1. NOT from NAND:
┌───────┐
A ─┤ │
│ NAND ├─── Y = A'
A ─┤ │
└───────┘
(A·A)' = A'
2. AND from NAND:
┌───────┐ ┌───────┐
A ─┤ │ │ │
│ NAND ├────┤ NAND ├─── Y = A·B
B ─┤ │ │ │
└───────┘ └───────┘
│
(동일 입력)
((A·B)')' = A·B
3. OR from NAND:
┌───────┐
A ─┤ │
│ NAND ├─────┐
A ─┤ │ │ ┌───────┐
└───────┘ ├───┤ │
│ │ NAND ├─── Y = A+B
┌───────┐ ├───┤ │
B ─┤ │ │ └───────┘
│ NAND ├─────┘
B ─┤ │
└───────┘
(A'·B')' = A+B (드모르간)
4. XOR과 XNOR 게이트¶
XOR 게이트 (배타적 OR)¶
XOR 게이트: 입력이 서로 다를 때 1
회로 기호:
┌────╲
A ───╲ =1 ╲───Y Y = A ⊕ B = A XOR B
B ───╱ ╱
└────╱
IEEE 기호: =1 또는 ⊕
진리표:
┌───┬───┬───────┐
│ A │ B │ A⊕B │
├───┼───┼───────┤
│ 0 │ 0 │ 0 │ ← 같음
│ 0 │ 1 │ 1 │ ← 다름
│ 1 │ 0 │ 1 │ ← 다름
│ 1 │ 1 │ 0 │ ← 같음
└───┴───┴───────┘
등가 표현:
A ⊕ B = A'B + AB' (한쪽만 1)
= (A + B)(A' + B')
= (A + B)(AB)'
XOR의 특성:
- A ⊕ 0 = A
- A ⊕ 1 = A'
- A ⊕ A = 0
- A ⊕ A' = 1
- A ⊕ B = B ⊕ A (교환법칙)
- (A ⊕ B) ⊕ C = A ⊕ (B ⊕ C) (결합법칙)
XNOR 게이트 (동치)¶
XNOR 게이트: 입력이 서로 같을 때 1
회로 기호:
┌────╲
A ───╲ =1 o───Y Y = (A ⊕ B)' = A XNOR B
B ───╱ ╱
└────╱
진리표:
┌───┬───┬─────────┐
│ A │ B │ (A⊕B)' │
├───┼───┼─────────┤
│ 0 │ 0 │ 1 │ ← 같음
│ 0 │ 1 │ 0 │ ← 다름
│ 1 │ 0 │ 0 │ ← 다름
│ 1 │ 1 │ 1 │ ← 같음
└───┴───┴─────────┘
등가 표현:
(A ⊕ B)' = A'B' + AB (둘 다 같음)
= A ⊙ B (동치 기호)
XOR의 응용¶
┌─────────────────────────────────────────────────────────────┐
│ XOR의 주요 응용 │
├─────────────────────────────────────────────────────────────┤
│ │
│ 1. 가산기 (Adder) │
│ - 반가산기의 합(Sum) 계산 │
│ - A + B의 LSB = A ⊕ B │
│ │
│ 2. 패리티 검사 (Parity Check) │
│ - 여러 비트의 XOR = 1의 개수가 홀수면 1 │
│ - 오류 검출에 사용 │
│ │
│ 3. 비교기 (Comparator) │
│ - A ⊕ B = 0 이면 A = B │
│ - A ⊕ B = 1 이면 A ≠ B │
│ │
│ 4. 토글 (Toggle) │
│ - A ⊕ 1 = A' (비트 반전) │
│ - A ⊕ 0 = A (유지) │
│ │
│ 5. 암호화 (Encryption) │
│ - 메시지 ⊕ 키 = 암호문 │
│ - 암호문 ⊕ 키 = 메시지 │
│ │
│ 6. 스왑 (Swap without temp) │
│ - a = a ⊕ b │
│ - b = a ⊕ b │
│ - a = a ⊕ b │
│ │
└─────────────────────────────────────────────────────────────┘
기본 게이트로 XOR 구현¶
XOR = A'B + AB'
회로 구현:
┌─────┐
A ────┬────┤ NOT ├────┐
│ └─────┘ │ ┌─────┐
│ └────┤ │
│ │ AND ├────┐
│ ┌──────────────┤ │ │ ┌────┐
│ │ └─────┘ ├────┤ │
B ────┼────┼──────────┐ │ │ OR ├───Y
│ │ │ │ │ │
│ │ ┌─────┐ ┌─────┐ │ └────┘
│ │ │ NOT ├────┤ │ │
│ └────┤ │ │ AND ├───┘
└─────────┴─────┘ │ │
└─────┘
게이트 수:
- 2 NOT + 2 AND + 1 OR = 5개
NAND만으로 XOR 구현:
- 4개의 NAND 게이트 필요
5. 진리표 작성법¶
진리표 기초¶
┌─────────────────────────────────────────────────────────────┐
│ 진리표 (Truth Table) │
├─────────────────────────────────────────────────────────────┤
│ 논리 함수의 모든 가능한 입력 조합과 해당 출력을 나열 │
│ │
│ n개 입력 → 2ⁿ개 행 │
│ - 1입력: 2행 │
│ - 2입력: 4행 │
│ - 3입력: 8행 │
│ - 4입력: 16행 │
└─────────────────────────────────────────────────────────────┘
입력 나열 규칙 (카운팅 순서):
┌───┬───┬───┐
│ A │ B │ C │
├───┼───┼───┤
│ 0 │ 0 │ 0 │ ← 0
│ 0 │ 0 │ 1 │ ← 1
│ 0 │ 1 │ 0 │ ← 2
│ 0 │ 1 │ 1 │ ← 3
│ 1 │ 0 │ 0 │ ← 4
│ 1 │ 0 │ 1 │ ← 5
│ 1 │ 1 │ 0 │ ← 6
│ 1 │ 1 │ 1 │ ← 7
└───┴───┴───┘
복합 논리식의 진리표¶
예시: Y = AB + A'C
단계별 계산을 위한 중간 열 추가:
┌───┬───┬───┬─────┬──────┬─────┬───────────┐
│ A │ B │ C │ A' │ AB │ A'C │ Y=AB+A'C │
├───┼───┼───┼─────┼──────┼─────┼───────────┤
│ 0 │ 0 │ 0 │ 1 │ 0 │ 0 │ 0 │
│ 0 │ 0 │ 1 │ 1 │ 0 │ 1 │ 1 │
│ 0 │ 1 │ 0 │ 1 │ 0 │ 0 │ 0 │
│ 0 │ 1 │ 1 │ 1 │ 0 │ 1 │ 1 │
│ 1 │ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │
│ 1 │ 0 │ 1 │ 0 │ 0 │ 0 │ 0 │
│ 1 │ 1 │ 0 │ 0 │ 1 │ 0 │ 1 │
│ 1 │ 1 │ 1 │ 0 │ 1 │ 0 │ 1 │
└───┴───┴───┴─────┴──────┴─────┴───────────┘
진리표에서 논리식 유도¶
주어진 진리표에서 논리식 구하기:
┌───┬───┬───┐
│ A │ B │ Y │
├───┼───┼───┤
│ 0 │ 0 │ 1 │ ← 항목 0: A'B'
│ 0 │ 1 │ 0 │
│ 1 │ 0 │ 1 │ ← 항목 2: AB'
│ 1 │ 1 │ 1 │ ← 항목 3: AB
└───┴───┴───┘
방법 1: 곱의 합 (SOP, Sum of Products)
- 출력이 1인 행만 선택
- 각 행을 AND 항으로 표현 (0이면 NOT 붙임)
- OR로 연결
Y = A'B' + AB' + AB
방법 2: 합의 곱 (POS, Product of Sums)
- 출력이 0인 행만 선택
- 각 행을 OR 항으로 표현 (1이면 NOT 붙임)
- AND로 연결
Y = (A + B') ← 0,1 행에서
6. 불 대수 기초¶
불 대수란?¶
┌─────────────────────────────────────────────────────────────┐
│ 불 대수 (Boolean Algebra) │
├─────────────────────────────────────────────────────────────┤
│ │
│ 조지 불(George Boole)이 1847년 개발한 대수 체계 │
│ 두 가지 값(0, 1)과 논리 연산을 다룸 │
│ │
│ 기본 연산: │
│ - AND (논리곱): · 또는 생략 │
│ - OR (논리합): + │
│ - NOT (보수): ' 또는 ̄ (오버바) │
│ │
│ 연산 우선순위: │
│ 1. 괄호 () │
│ 2. NOT (') │
│ 3. AND (·) │
│ 4. OR (+) │
│ │
│ 예: A + B · C' = A + (B · (C')) │
│ │
└─────────────────────────────────────────────────────────────┘
기본 공리¶
불 대수의 공리 (Axioms):
1. 닫힘 (Closure):
- A · B ∈ {0, 1}
- A + B ∈ {0, 1}
2. 항등원 (Identity):
- A · 1 = A
- A + 0 = A
3. 교환법칙 (Commutative):
- A · B = B · A
- A + B = B + A
4. 분배법칙 (Distributive):
- A · (B + C) = A·B + A·C
- A + (B · C) = (A+B) · (A+C) ← 일반 대수와 다름!
5. 보수 (Complement):
- A · A' = 0
- A + A' = 1
7. 불 대수 법칙¶
기본 정리¶
┌─────────────────────────────────────────────────────────────┐
│ 기본 정리 (Theorems) │
├─────────────────────────────────────────────────────────────┤
│ │
│ 멱등법칙 (Idempotent): │
│ - A · A = A │
│ - A + A = A │
│ │
│ 영원법칙 (Null/Domination): │
│ - A · 0 = 0 │
│ - A + 1 = 1 │
│ │
│ 이중 부정 (Involution): │
│ - (A')' = A │
│ │
│ 흡수법칙 (Absorption): │
│ - A + A·B = A │
│ - A · (A + B) = A │
│ │
│ 결합법칙 (Associative): │
│ - (A · B) · C = A · (B · C) │
│ - (A + B) + C = A + (B + C) │
│ │
└─────────────────────────────────────────────────────────────┘
드모르간 법칙¶
┌─────────────────────────────────────────────────────────────┐
│ 드모르간 법칙 (De Morgan's Laws) │
├─────────────────────────────────────────────────────────────┤
│ │
│ 정리 1: (A · B)' = A' + B' │
│ "AND의 NOT = 각각의 NOT을 OR" │
│ │
│ 정리 2: (A + B)' = A' · B' │
│ "OR의 NOT = 각각의 NOT을 AND" │
│ │
│ 일반화: │
│ (A₁ · A₂ · ... · Aₙ)' = A₁' + A₂' + ... + Aₙ' │
│ (A₁ + A₂ + ... + Aₙ)' = A₁' · A₂' · ... · Aₙ' │
│ │
│ 응용: NAND/NOR 변환 │
│ (AB)' = A' + B' → NAND를 NOR과 인버터로 │
│ (A+B)' = A'B' → NOR를 NAND와 인버터로 │
│ │
└─────────────────────────────────────────────────────────────┘
드모르간 법칙 증명 (진리표):
(A · B)' = A' + B'
┌───┬───┬─────┬────────┬─────┬─────┬──────────┐
│ A │ B │ A·B │ (A·B)' │ A' │ B' │ A' + B' │
├───┼───┼─────┼────────┼─────┼─────┼──────────┤
│ 0 │ 0 │ 0 │ 1 │ 1 │ 1 │ 1 │
│ 0 │ 1 │ 0 │ 1 │ 1 │ 0 │ 1 │
│ 1 │ 0 │ 0 │ 1 │ 0 │ 1 │ 1 │
│ 1 │ 1 │ 1 │ 0 │ 0 │ 0 │ 0 │
└───┴───┴─────┴────────┴─────┴─────┴──────────┘
같음!
합의 법칙¶
합의 (Consensus):
A·B + A'·C + B·C = A·B + A'·C
"중복 항 제거"
증명:
B·C = B·C·(A + A') (A + A' = 1)
= A·B·C + A'·B·C
= A·B·C + A'·B·C (이미 AB와 A'C에 포함)
쌍대 형태:
(A + B)·(A' + C)·(B + C) = (A + B)·(A' + C)
불 대수 법칙 요약표¶
┌──────────────────────┬─────────────────────┬─────────────────────┐
│ 법칙 │ AND │ OR │
├──────────────────────┼─────────────────────┼─────────────────────┤
│ 항등원 (Identity) │ A · 1 = A │ A + 0 = A │
├──────────────────────┼─────────────────────┼─────────────────────┤
│ 영원 (Null) │ A · 0 = 0 │ A + 1 = 1 │
├──────────────────────┼─────────────────────┼─────────────────────┤
│ 멱등 (Idempotent) │ A · A = A │ A + A = A │
├──────────────────────┼─────────────────────┼─────────────────────┤
│ 보수 (Complement) │ A · A' = 0 │ A + A' = 1 │
├──────────────────────┼─────────────────────┼─────────────────────┤
│ 교환 (Commutative) │ A · B = B · A │ A + B = B + A │
├──────────────────────┼─────────────────────┼─────────────────────┤
│ 결합 (Associative) │ (AB)C = A(BC) │ (A+B)+C = A+(B+C) │
├──────────────────────┼─────────────────────┼─────────────────────┤
│ 분배 (Distributive) │ A(B+C) = AB + AC │ A+BC = (A+B)(A+C) │
├──────────────────────┼─────────────────────┼─────────────────────┤
│ 흡수 (Absorption) │ A(A+B) = A │ A + AB = A │
├──────────────────────┼─────────────────────┼─────────────────────┤
│ 드모르간 │ (AB)' = A' + B' │ (A+B)' = A'B' │
└──────────────────────┴─────────────────────┴─────────────────────┘
8. 논리식 간소화¶
대수적 간소화¶
예제 1: Y = AB + AB'
Y = AB + AB'
= A(B + B') (분배법칙 역)
= A · 1 (B + B' = 1)
= A (항등원)
예제 2: Y = A'B'C + A'BC + AB'C + ABC
Y = A'B'C + A'BC + AB'C + ABC
= A'C(B' + B) + AC(B' + B) (분배법칙 역)
= A'C · 1 + AC · 1 (B' + B = 1)
= A'C + AC
= C(A' + A) (분배법칙 역)
= C · 1
= C
예제 3: Y = AB + A'C + BC
Y = AB + A'C + BC
= AB + A'C + BC(A + A') (A + A' = 1)
= AB + A'C + ABC + A'BC
= AB(1 + C) + A'C(1 + B) (1 + X = 1)
= AB + A'C (합의 법칙)
카르노 맵 (Karnaugh Map)¶
┌─────────────────────────────────────────────────────────────┐
│ 카르노 맵 (K-Map) │
├─────────────────────────────────────────────────────────────┤
│ 진리표를 2차원으로 배열하여 시각적으로 간소화하는 방법 │
│ 인접한 1들을 묶어서 변수를 소거 │
└─────────────────────────────────────────────────────────────┘
2변수 K-맵:
B
0 1
┌─────┬─────┐
0 │ A'B'│ A'B │
A ├─────┼─────┤
1 │ AB' │ AB │
└─────┴─────┘
3변수 K-맵 (그레이 코드 순서):
BC
00 01 11 10
┌────┬────┬────┬────┐
0 │ 0 │ 1 │ 3 │ 2 │
A ├────┼────┼────┼────┤
1 │ 4 │ 5 │ 7 │ 6 │
└────┴────┴────┴────┘
(민텀 번호)
4변수 K-맵:
CD
00 01 11 10
┌────┬────┬────┬────┐
00 │ 0 │ 1 │ 3 │ 2 │
├────┼────┼────┼────┤
01 │ 4 │ 5 │ 7 │ 6 │
AB ├────┼────┼────┼────┤
11 │ 12 │ 13 │ 15 │ 14 │
├────┼────┼────┼────┤
10 │ 8 │ 9 │ 11 │ 10 │
└────┴────┴────┴────┘
K-맵 사용법¶
예제: Y = Σm(0, 1, 3, 5, 7) (3변수)
1단계: K-맵에 1 표시
BC
00 01 11 10
┌────┬────┬────┬────┐
0 │ 1 │ 1 │ 1 │ │ ← m0, m1, m3
A ├────┼────┼────┼────┤
1 │ │ 1 │ 1 │ │ ← m5, m7
└────┴────┴────┴────┘
2단계: 인접한 1들을 그룹화 (2의 거듭제곱 크기)
BC
00 01 11 10
┌────┬────┬────┬────┐
0 │[1] │ 1──┼─1 │ │ 그룹1: m1,m3,m5,m7 (세로 2칸)
A ├────┼────┼────┼────┤
1 │ │ 1──┼─1 │ │
└────┴────┴────┴────┘
│
그룹2: m0,m1 (가로 2칸)
3단계: 각 그룹의 공통 변수 추출
- 그룹1 (4칸): C만 공통 → C
- 그룹2 (2칸): A'와 B'가 공통 → A'B'
결과: Y = C + A'B'
검증:
원래: A'B'C' + A'B'C + A'BC + AB'C + ABC
= A'B'(C'+C) + C(A'B + AB' + AB)
= A'B' + C(A'B + A) = A'B' + C
K-맵 그룹화 규칙¶
┌─────────────────────────────────────────────────────────────┐
│ K-맵 그룹화 규칙 │
├─────────────────────────────────────────────────────────────┤
│ │
│ 1. 그룹 크기는 2의 거듭제곱 (1, 2, 4, 8, 16...) │
│ │
│ 2. 인접한 셀만 그룹화 (대각선 X) │
│ - K-맵의 가장자리는 반대편과 연결됨 (토러스 형태) │
│ │
│ 3. 모든 1이 최소 하나의 그룹에 포함되어야 함 │
│ │
│ 4. 그룹은 가능한 크게 만들어야 함 │
│ (더 큰 그룹 = 더 적은 변수) │
│ │
│ 5. 필요하다면 같은 1을 여러 그룹에 포함 가능 │
│ │
│ 6. Don't Care (X)는 필요시 1로 취급 가능 │
│ │
└─────────────────────────────────────────────────────────────┘
가장자리 연결 예시 (4변수):
CD
00 01 11 10
┌────┬────┬────┬────┐
00 │ 1 │ │ │ 1 │ ← 좌우 연결
├────┼────┼────┼────┤
01 │ │ │ │ │
AB ├────┼────┼────┼────┤
11 │ │ │ │ │
├────┼────┼────┼────┤
10 │ 1 │ │ │ 1 │ ← 상하 연결
└────┴────┴────┴────┘
↑ ↑
└──────────────┘
좌우 연결
4개의 1이 하나의 그룹 (네 모서리)
→ B'D' (공통 변수)
9. 연습 문제¶
기초 문제¶
1. 다음 논리 연산의 결과를 구하시오. - (a) 1 AND 0 - (b) 1 OR 0 - (c) NOT 1 - (d) 1 NAND 1 - (e) 0 NOR 0 - (f) 1 XOR 1
2. 다음 논리식의 진리표를 작성하시오. - (a) Y = A + B' - (b) Y = AB + A'B' - (c) Y = (A + B)(A' + C)
3. 다음 진리표에 해당하는 논리식을 SOP 형식으로 구하시오.
┌───┬───┬───┐
│ A │ B │ Y │
├───┼───┼───┤
│ 0 │ 0 │ 0 │
│ 0 │ 1 │ 1 │
│ 1 │ 0 │ 1 │
│ 1 │ 1 │ 0 │
└───┴───┴───┘
불 대수 문제¶
4. 다음 논리식을 간소화하시오. - (a) Y = A + A'B - (b) Y = AB + AB' - (c) Y = (A + B)(A + B') - (d) Y = A'B + AB' + AB + A'B'
5. 드모르간 법칙을 사용하여 변환하시오. - (a) (ABC)' = ? - (b) (A + B + C)' = ? - (c) ((A + B)C)' = ?
6. 다음 등식을 불 대수로 증명하시오. - (a) A + AB = A - (b) A(A + B) = A - (c) A + A'B = A + B
K-맵 문제¶
7. 다음 논리식을 K-맵을 사용하여 간소화하시오. - (a) Y = Σm(0, 2, 4, 6) (3변수) - (b) Y = Σm(0, 1, 2, 3, 5, 7) (3변수) - (c) Y = Σm(0, 1, 2, 5, 8, 9, 10) (4변수)
8. Don't Care 조건을 포함한 다음 함수를 간소화하시오. Y = Σm(1, 3, 7) + d(0, 5) (3변수)
심화 문제¶
9. NAND 게이트만 사용하여 다음을 구현하시오. - (a) NOT 게이트 - (b) AND 게이트 - (c) OR 게이트 - (d) XOR 게이트
10. 다음 회로의 출력을 논리식으로 표현하고 간소화하시오.
┌─────┐
A ──────┤ │
│ AND ├─────┐
B ──────┤ │ │ ┌─────┐
└─────┘ ├────┤ │
│ │ OR ├──── Y
┌─────┐ ├────┤ │
A ──┬───┤ NOT ├─────┘ └─────┘
│ └─────┘
│ ┌─────┐
└───┤ │
│ AND ├─────────────────┘
C ──────┤ │
└─────┘
정답
**1. 논리 연산 결과** - (a) 1 AND 0 = 0 - (b) 1 OR 0 = 1 - (c) NOT 1 = 0 - (d) 1 NAND 1 = 0 - (e) 0 NOR 0 = 1 - (f) 1 XOR 1 = 0 **2. 진리표** - (a) Y = A + B': [1,0,1,1] (순서대로) - (b) Y = AB + A'B': [1,0,0,1] - (c) Y = (A+B)(A'+C): [0,C,B,1] 즉 [0,0,0,1,0,1,0,1] **3.** Y = A'B + AB' = A XOR B **4. 간소화** - (a) Y = A + A'B = A + B (흡수) - (b) Y = AB + AB' = A(B + B') = A - (c) Y = (A+B)(A+B') = A + BB' = A - (d) Y = A'B + AB' + AB + A'B' = A'(B+B') + A(B'+B) = A' + A = 1 **5. 드모르간** - (a) (ABC)' = A' + B' + C' - (b) (A+B+C)' = A'B'C' - (c) ((A+B)C)' = (A+B)' + C' = A'B' + C' **6. 증명** - (a) A + AB = A(1 + B) = A·1 = A - (b) A(A+B) = AA + AB = A + AB = A - (c) A + A'B = (A+A')(A+B) = 1·(A+B) = A+B **7. K-맵 간소화** - (a) Y = B' (m0,m2,m4,m6은 B=0인 열) - (b) Y = A' + C (m0,1,2,3=A', m1,3,5,7=C) - (c) Y = B'D' + A'B'C' + A'CD' **8.** Don't Care 포함: Y = B' 또는 Y = A' + B' (d 활용에 따라) **9. NAND 구현** - (a) NOT: A NAND A = A' - (b) AND: (A NAND B) NAND (A NAND B) - (c) OR: (A NAND A) NAND (B NAND B) - (d) XOR: 4개의 NAND 필요 **10.** Y = AB + A'C = A와 B의 AND 또는 A의 NOT과 C의 AND 간소화 결과는 그대로 AB + A'C (더 이상 간소화 불가)다음 단계¶
- 05_Combinational_Logic.md - 가산기, 멀티플렉서, 디코더
참고 자료¶
- Digital Design (Morris Mano)
- Computer Organization and Design (Patterson & Hennessy)
- Logic Gate Simulator
- Boolean Algebra Calculator
- Karnaugh Map Solver