논리회로설계 03 - Combinational Logic

 

개요

 

논리 회로를 설계하려면 두 가지가 필요합니다. 하나는 회로의 동작을 수식으로 표현하는 방법이고, 다른 하나는 그 수식을 간단하게 만드는 도구입니다. 이번 강의는 그 두 가지를 모두 다룹니다.

크게 세 가지 주제를 다룹니다. 첫 번째는 조합 논리(Combinational Logic)로, 논리 회로의 종류와 규칙을 설명합니다. 두 번째는 SOP / POS 표준 형식으로, 진리표에서 논리식을 도출하는 방법을 다룹니다. 세 번째는 불 대수(Boolean Algebra)로, 공리·정리·성질을 이용해 논리식을 수학적으로 간소화하는 방법을 설명합니다.

---

1. 논리 회로의 두 종류

조합 논리 vs 순서 논리

논리 회로는 크게 두 종류로 나뉩니다. 출력이 현재 입력만으로 결정되는 조합 논리(Combinational Logic)와, 이전 상태까지 고려하는 순서 논리(Sequential Logic)입니다.

구분	조합 논리	순서 논리
메모리	없음 (Memoryless)	있음
출력 결정	현재 입력만으로 결정	현재 입력 + 이전 상태
타이밍 사양	불필요	필요
예시	AND/OR/NOT 게이트, 가산기	플립플롭, 레지스터, 카운터

 

조합 논리의 3가지 규칙

어떤 회로가 조합 논리인지 판별할 때는 아래 세 가지 조건을 모두 만족하는지 확인합니다.

• 모든 구성 요소가 조합 논리여야 한다.
• 모든 노드는 입력이거나 정확히 하나의 출력에만 연결된다.
• 회로에 순환 경로(cycle)가 없어야 한다 — 비순환(acyclic) 구조.

특히 세 번째 조건이 중요합니다. 출력이 다시 입력으로 돌아오는 경로(피드백)가 있으면 조합 논리가 아닙니다. 이 경우 출력이 과거 상태에 의존하게 되어 순서 논리의 특성을 띠기 때문입니다.

---

2. 불 대수 주요 용어

논리식을 다루기 전에 반드시 알아야 할 용어들입니다. 변수가 A, B, C 세 개라고 가정합니다.

용어	설명	예시
보수 (Complement)	변수에 NOT을 취한 것	A', B', C'
리터럴 (Literal)	변수 또는 그 보수	A, A', B, B', C, C' → 총 2n개
함의항 (Implicant)	리터럴의 곱(AND)	AB, AC', BC
최소항 (Minterm)	모든 입력 변수를 포함하는 곱항	A'B'C, ABC', ABC
최대항 (Maxterm)	모든 입력 변수를 포함하는 합항	(A+B+C), (A'+B+C')

n개의 변수가 있을 때 최소항과 최대항은 각각 2ⁿ개 존재합니다. 두 변수면 4개, 세 변수면 8개입니다. A·A' = 0이므로 같은 변수와 그 보수가 하나의 항에 함께 있으면 그 항은 항상 0이 됩니다.

 

 

---

3. SOP 형식 (Sum-of-Products)

SOP는 이름 그대로 곱항(AND)들의 합(OR) 형태입니다. 진리표에서 출력이 1인 행의 최소항들을 OR로 연결해 만듭니다.

 

작성 방법

• 진리표에서 출력이 1인 행을 찾는다.
• 해당 행의 최소항을 구한다. (입력이 1이면 변수 그대로, 0이면 보수로 표현)
• 최소항들을 OR로 연결한다.

예시 (2변수 A, B)

A	B	Y	최소항	이름
0	0	0	A'B'	m₀
0	1	1	A'B	m₁
1	0	0	AB'	m₂
1	1	1	AB	m₃

Y = F(A, B) = A'B + AB = Σ(1, 3)

출력이 1인 행(m₁, m₃)의 최소항만 골라 OR로 연결했습니다. Σ 표기는 괄호 안의 행 번호에서 출력이 1임을 의미합니다.

---

4. POS 형식 (Product-of-Sums)

POS는 합항(OR)들의 곱(AND) 형태입니다. SOP와 반대로 출력이 0인 행의 최대항들을 AND로 연결합니다.

작성 방법

• 진리표에서 출력이 0인 행을 찾는다.
• 해당 행의 최대항을 구한다. (입력이 0이면 변수 그대로, 1이면 보수로 표현)
• 최대항들을 AND로 연결한다.

Y = F(A, B) = (A+B)(A'+B) = Π(0, 2)

 

 

 

 

 

핵심 정리: SOP는 출력이 1인 최소항의 합 → Σ(1이 나오는 행 번호) / POS는 출력이 0인 최대항의 곱 → Π(0이 나오는 행 번호). 두 표현 모두 같은 함수를 나타내며, 어느 것이 더 간결한지에 따라 선택합니다.

---

5. 불 대수 (Boolean Algebra)

불 대수는 논리식을 수학적으로 다루는 도구입니다. 일반 대수와 비슷하지만, 변수가 0과 1 두 값만 가진다는 점이 다릅니다. 공리에서 출발해 정리를 증명하고, 이를 이용해 복잡한 논리식을 간소화합니다.

또한 불 대수에는 쌍대성(Duality)이 있습니다. AND와 OR, 0과 1을 서로 맞바꾸면 참인 식은 여전히 참입니다. 그래서 공리와 정리가 항상 쌍(pair)으로 제시됩니다.

공리 (Axioms)

공리는 증명 없이 참으로 받아들이는 기본 명제입니다. AND·OR·NOT의 정의로부터 직접 유도됩니다.

공리	듀얼	이름
B ≠ 1 이면 B = 0	B ≠ 0 이면 B = 1	이진 필드
0̄ = 1	1̄ = 0	NOT
0 · 0 = 0	1 + 1 = 1	AND / OR
1 · 1 = 1	0 + 0 = 0	AND / OR
0 · 1 = 1 · 0 = 0	1 + 0 = 0 + 1 = 1	AND / OR

정리 (Theorems) — 단일 변수

정리	듀얼	이름
B · 1 = B	B + 0 = B	항등 (Identity)
B · 0 = 0	B + 1 = 1	지배 (Null Element)
B · B = B	B + B = B	멱등 (Idempotency)
B̄̄ = B		누승 (Involution)
B · B' = 0	B + B' = 1	보수 (Complements)

성질 (Properties) — 다변수

두 개 이상의 변수가 관계할 때 적용되는 성질입니다. 이 중 분배 법칙과 드모르간 정리는 논리식 변환에서 가장 자주 쓰입니다.

성질	듀얼	이름
B · C = C · B	B + C = C + B	교환 (Commutativity)
(B·C)·D = B·(C·D)	(B+C)+D = B+(C+D)	결합 (Associativity)
B·(C+D) = B·C + B·D	B+(C·D) = (B+C)·(B+D) ⚠️	분배 (Distributivity)
B·(B+C) = B	B+(B·C) = B	흡수 (Covering)
B·C + B·C' = B	(B+C)·(B+C') = B	결합 (Combining)
(x·y)' = x' + y'	(x+y)' = x'·y'	드모르간 (De Morgan's)

⚠️ 분배 법칙 듀얼 주의 — 일반 대수와 달리 불 대수에서는 OR(+)이 AND(·)에 대해서도 분배됩니다. 즉 B + (C·D) = (B+C)·(B+D) 가 성립합니다. 이 점은 일반 수학과 다르기 때문에 특히 유의해야 합니다.

---

6. 드모르간 정리 — 진리표로 증명

드모르간 정리는 논리식의 부정을 다루는 핵심 성질입니다. 진리표로 (x·y)' = x' + y' 를 직접 확인해 봅니다.

x	y	x·y	(x·y)' [LHS]	x'	y'	x'+y' [RHS]
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

LHS와 RHS의 값이 모든 행에서 일치합니다. 진리표가 같으면 두 함수는 동치입니다.

---

7. 대수적 조작 예제

불 대수 성질을 적용하는 연습입니다. 각 단계에서 어떤 성질을 사용했는지 확인하면서 읽으면 도움이 됩니다.

예제 1: (a·b·c) + (a·b·c') = a·b ?

(a·b·c) + (a·b·c')
= (a·b)·c + (a·b)·c'    ← 결합 법칙
= (a·b)·(c + c')         ← 분배 법칙
= (a·b)·1               ← 보수 법칙: c + c' = 1
= a·b                    ← 항등 법칙: x·1 = x  ✓

예제 2: x + (x'·z) = x + z ?

x + (x'·z)
= (x + x')·(x + z)       ← 분배 법칙 듀얼: x + (y·z) = (x+y)·(x+z)
= 1·(x + z)              ← 보수 법칙: x + x' = 1
= x + z                  ← 항등 법칙: 1·x = x  ✓

예제 3: (x·x') + (x·y)·(x' + y') = 항상 0 ?

(x·x') + (x·y)·(x' + y')
= 0 + (x·y)·(x' + y')    ← 보수 법칙: x·x' = 0, 항등 법칙: 0+A = A
= (x·y)·(x' + y')
= (x·y·x') + (x·y·y')    ← 분배 법칙
= (y·0) + (x·0)          ← 보수 법칙: x·x' = 0, y·y' = 0
= 0 + 0                  ← 지배 법칙: x·0 = 0
= 0                       ← 항등 법칙  ✓

---

8. 논리식 증명 세 가지 방법

두 논리식이 같음을 보이는 방법은 세 가지입니다. 상황에 따라 적절한 방법을 선택합니다.

방법	원리	장단점
진리표 (완전 귀납)	모든 입력 조합 열거	확실하지만 변수가 많으면 방대해짐
대수적 조작	공리·정리를 단계별로 적용	유연하지만 경로 선택에 경험 필요
벤 다이어그램	집합으로 시각화	직관적이지만 복잡한 식엔 한계

---

핵심 요약

주제	핵심 내용
조합 논리	메모리 없음, 출력 = f(현재 입력). 비순환 구조 필수
SOP	출력 1인 행의 최소항을 OR 연결 → Σ(행 번호)
POS	출력 0인 행의 최대항을 AND 연결 → Π(행 번호)
공리·정리	항등·지배·멱등·누승·보수 법칙으로 단일 변수 처리
분배 법칙 주의	OR도 AND에 대해 분배됨: B+(C·D) = (B+C)·(B+D)
드모르간 정리	(x·y)' = x'+y' / (x+y)' = x'·y'. NAND·NOR 회로 분석의 핵심
간소화의 목적	게이트 수 감소 → 비용 절감 + 동작 속도 향상

Digital Logic Design — Yongsoo Joo (Kookmin Univ. KESL) | Lecture 4 정리