부울 대수 법칙과 논리 회로 간소화

부울 대수는 0과 1, 즉 거짓과 참만을 값으로 갖는 변수의 관계를 다루는 대수 체계다. 조지 불이 고안한 이 체계는 복잡한 논리식을 단순한 형태로 바꾸고, 디지털 회로의 비용과 복잡도를 낮추는 이론적 기반이 된다.

논리 설계에서는 AND(·), OR(+), NOT(') 연산을 사용한다. 이 연산과 법칙을 적용하면 조합 논리 회로, 순차 논리 회로, 상태 머신, 제어 유닛을 표현하고 다듬을 수 있다.

논리식을 바꾸는 기본 법칙

항등법칙은 0 또는 1과의 연산 뒤에도 변수 값이 유지되는 경우를 나타낸다.

연산	법칙
OR 항등	A + 0 = A
AND 항등	A · 1 = A

같은 변수를 반복한 항은 하나로 정리할 수 있다.

연산	법칙
OR 동일	A + A = A
AND 동일	A · A = A

보원법칙은 변수와 그 부정의 관계를 정의한다.

연산	법칙
OR 보원	A + A' = 1
AND 보원	A · A' = 0
이중 부정	(A')' = A

다중법칙에서는 OR에 1이 포함되면 결과가 1이 되고, AND에 0이 포함되면 결과가 0이 된다.

연산	법칙
OR 다중	A + 1 = 1
AND 다중	A · 0 = 0

교환법칙과 결합법칙은 항의 순서와 묶는 방식을 바꿀 수 있게 한다.

연산	법칙
OR 교환	A + B = B + A
AND 교환	A · B = B · A
OR 결합	(A + B) + C = A + (B + C)
AND 결합	(A · B) · C = A · (B · C)

분배법칙은 식을 전개하거나 묶어 회로 구조를 변환할 때 쓰인다.

연산	법칙
AND over OR	A · (B + C) = (A · B) + (A · C)
OR over AND	A + (B · C) = (A + B) · (A + C)

흡수법칙은 한 항이 다른 항을 포함할 때 불필요한 부분을 제거한다.

연산	법칙
OR 흡수	A + (A · B) = A
AND 흡수	A · (A + B) = A

합의 정리로 중복 항 제거하기

합의 정리는 다음과 같이 표현된다.

A·B + A'·C + B·C = A·B + A'·C
(A+B)·(A'+C)·(B+C) = (A+B)·(A'+C)

예를 들어 AB + AB'는 분배법칙과 보원법칙을 거쳐 A가 된다.

⤢✕

다음 식도 법칙을 적용해 간소화할 수 있다.

원식: F = A'BC + ABC + AB'C + ABC'

간소화:

ABC 항 제거 (중복)
F = A'BC + ABC + AB'C + ABC'
F = BC(A' + A) + AB'C + ABC'
F = BC + AB'C + ABC'
F = BC + AC

부정을 AND와 OR 사이에서 변환하는 드모르간 법칙

드모르간 법칙은 AND와 OR의 부정을 서로 변환하는 규칙이다. OR 전체를 부정하면 각 항의 부정을 AND로 연결한다.

(A + B)' = A' · B'
OR의 부정 = 각각 부정의 AND

반대로 AND 전체를 부정하면 각 항의 부정을 OR로 연결한다.

(A · B)' = A' + B'
AND의 부정 = 각각 부정의 OR

NAND와 NOR를 다른 형태의 논리식으로 바꿀 때도 이 법칙을 적용한다.

⤢✕

카르노 맵으로 진리표를 묶는 방법

카르노 맵(Karnaugh Map, K-map)은 2, 3, 4변수 진리표를 시각적으로 나타내 논리식 간소화를 돕는다.

2변수 카르노 맵

A\B	0	1
0	m0	m1
1	m2	m3

3변수 카르노 맵

AB\C	0	1
00	m0	m1
01	m2	m3
11	m6	m7
10	m4	m5

4변수 카르노 맵

AB\CD	00	01	11	10
00	m0	m1	m3	m2
01	m4	m5	m7	m6
11	m12	m13	m15	m14
10	m8	m9	m11	m10

간소화할 때는 1로 표시된 인접 셀을 묶는다. 가능한 큰 그룹을 만들며, 그룹 크기는 1, 2, 4, 8개가 된다. 모든 1을 최소 그룹으로 커버한 뒤 각 그룹을 곱항으로 표현하고, 그 곱항을 합으로 결합한다.

회로 최적화로 이어지는 흐름

부울식은 진리표에서 도출한 뒤 법칙이나 카르노 맵으로 간소화할 수 있다. 두 경로 모두 최적 회로를 만드는 데 연결된다.

⤢✕

이 과정은 게이트 수 감소, 전력 소비 절감, 지연 시간 최소화, 비용 절감으로 이어진다.