4. 불 대수

논리 회로를 설계할 때 빠질 수 없는 핵심 수학 도구가 바로 불 대수(Boolean Algebra)입니다. 이번 포스팅에서는 불 대수의 기초 개념부터 법칙, SOP/POS 표현, 그리고 실제 간소화 과정까지 한 번에 정리합니다.

 

01 불 대수란? 기본 논리식 표현

Boolean Algebra의 탄생과 AND·OR·NOT 표현법

 

불 대수(Boolean Algebra)는 1854년 영국 수학자 조지 불(George Boole)이 논리 계산을 형식화하여 도입한 대수 체계입니다. 디지털 회로에서 0(Low)과 1(High)을 다루며, 논리식을 간소화하기 위한 수학적 도구로 활용됩니다.

 

기본 표현 규칙 및 우선순위

 

· AND식 : 곱셈 형식으로 표현 → F = A·B

· OR식 : 덧셈 형식으로 표현 → F = A+B

· NOT식 : 글자 위에 선을 긋는 Bar(A) 형태로 표현

💡 연산 우선순위 : 괄호 ( ) ➔ NOT ➔ AND ➔ OR 순서로 계산합니다.

 

 

조건	출력 논리식	설명
A=0 and B=1 일 때 출력 1	F = AB	NOT A AND B
A=0 or B=1 일 때 출력 1	F = A+B	NOT A OR B
(A=0,B=1) or (A=1,B=0)	F = AB + AB	XOR 동작

 

 

02 불 대수 공리와 법칙 총정리

증명 없이 받아들이는 공리부터 교환·결합·분배법칙까지

 

불 대수 기본 공리

공리(axiom)는 논리적 체계를 구성하기 위한 가장 기본 명제로, 0과 1의 기본적인 덧셈(OR)과 곱셈(AND) 규칙을 따릅니다. (예: 0+0=0, 1·1=1, 1+0=1 등)

 

기본 법칙 9가지

 

번호	법칙	설명
1	A + 0 = 0 +  A =  A	동일(항등) 법칙
2	A · 1 =  1 · A =  A
3	A + 1 = 1 + A =  1	지배 법칙
4	A · 0 = 0 · A =  0
5	A + A = A	멱등 법칙 (같은 항 중복)
6	A · A = A
7	A + A = 1	보수 법칙 (서로 반대되는 값과의 연산)
8	A · A = 0
9	A = A	이중 부정 (NOT을 두 번 거치면 원래대로)

 

교환·결합·분배 법칙

 

교환법칙 · A + B = B + A · AB = BA

결합법칙 · (A+B)+C = A+(B+C) · (AB)C = A(BC)

분배법칙 · A(B+C) = AB+AC · A+BC = (A+B)(A+C)

 

⚠️ 주의 — 분배법칙의 특이점
일반 대수와 달리 불 대수에서는 A + BC = (A+B)(A+C) 가 성립합니다. 식을 묶고 풀 때 가장 헷갈리기 쉬운 공식이므로 꼭 외워두세요.

 

흡수 법칙 & 합의의 정리

 

· 흡수 법칙 : A + AB = A  /  A(A+B) = A

· 합의의 정리 : AB + BC + AC = AB + AC

 

 

03 드모르간의 정리

De Morgan's Theorem — 논리식 변환의 핵심 도구

 

제1 정리 A + B = A · B → 전체의 OR NOT = 각각의 NOT AND

제2 정리 A · B = A + B → 전체의 AND NOT = 각각의 NOT OR

 

 

적용 예제

· ( A+B + C ) = (A+B) · C = (A+B)C = AC + BC
· ( A+B ) · CD = ( A+B ) + CD = (A · B) + (C + D) = AB + C + D

 

 

04 SOP(곱의 합)와 최소항

Sum of Products · Minterm

 

곱의 합(SOP, Sum of Products)은 가장 많이 사용되는 불 대수 표현 형식입니다. 1단계에서 AND항(곱의 항)을 만들고, 2단계에서 그 AND항들을 OR(+)로 묶는 구조입니다.

 

① 1단계 AND항 생성 (A, B, C 등 곱의 항)

→

② 2단계 OR로 합산 (ABC + ABD...)

→

③ 결과 SOP 형태 F = ABC + ABD + AC

 

최소항 (Minterm)

 

최소항은 함수에 사용되는 모든 변수를 포함하는 표준 곱의 항입니다. 진리표에서 출력 F=1인 행만 뽑아 해당 입력 조합을 AND 항으로 표현합니다.

 

최소항 표기 규칙 및 포인트

· 변수값이 1이면 정(正) 변수 (예: A), 0이면 부(負) 변수 (예: A)를 AND로 곱합니다.
· 예) 3입력에서 A=1, B=0, C=1 이면 결과가 1일 때 → 최소항은 ABC 가 됩니다.
· 2변수 AB=01 → A·B → 기호 m₁
· 수식으로는 Σm(1,2,3) 처럼 합산 기호로 간단히 표현 가능합니다.

 

 

05 POS(합의 곱)와 최대항

Product of Sums · Maxterm

 

합의 곱(POS, Product of Sums)은 SOP와 반대 구조입니다. 1단계에서 OR항(합의 항)을 만들고, 2단계에서 AND(·)로 묶습니다.

 

 

SOP (곱의 합) · 1단계: AND항 · 2단계: OR로 합산 · 최소항(Minterm) 사용 · 진리표에서 F=1인 행 사용 · 표기: Σm(…)

POS (합의 곱) · 1단계: OR항 · 2단계: AND로 곱함 · 최대항(Maxterm) 사용 · 진리표에서 F=0인 행 사용 · 표기: ΠM(…)

 

최소항과 최대항의 관계

 

최소항(mᵢ)과 최대항(Mᵢ)은 상호 보수 관계를 가집니다. 즉, Mᵢ = mᵢ 가 성립합니다. 예를 들어 m₀ = A·B·C 이고 M₀ = A+B+C 이므로 두 항은 드모르간 정리에 의해 서로 보수입니다.

 

 

06 불 대수 법칙을 이용한 논리식 간소화

복잡한 최소항 표현을 단순화하는 실전 과정

 

최소항(Minterm)으로 완전히 전개된 식은 아직 간소화할 여지가 있습니다. 불 대수 법칙, 특히 A+A=A (같은 항 중복 추가 가능)와 분배법칙을 이용하면 게이트 수를 획기적으로 줄일 수 있습니다.

 

핵심 간소화 테크닉

 

· 같은 항 추가 : X + X = X 이므로, 식에 이미 존재하는 항을 마음껏 복제하여 다른 항과 짝짓는 데 활용할 수 있습니다.

· 보수 관계 묶기 : 공통 변수로 묶었을 때 (A+A) 형태가 나오면 1이 되어 사라집니다.

 

간소화 예제 (방법 1 - 순차적으로 묶기)

ABC + ABC + ABC + ABC + ABC
= (ABC + ABC) + (ABC + ABC) + ABC
= AB(C+C) + AB(C+C) + ABC
= AB·1 + AB·1 + ABC
= AB + AB + ABC
(※ 이 상태도 간소화된 편이지만, 최적의 상태는 아닙니다.)

 

✓ 간소화 예제 (방법 2 — 항 중복을 이용한 최적화)

원래 식에 존재하는 ABC 항을 짝짓기를 위해 한 번 더 복제해 봅니다. (A+A=A 이용)
= (ABC + ABC) + (ABC + ABC) + (ABC + ABC)
= AB(C+C) + AB(C+C) + AC(B+B)
= AB·1 + AB·1 + AC·1
= AB + AB + AC
(※ 이렇게 항을 유연하게 중복 사용하면 불필요한 게이트를 완전히 제거할 수 있습니다.)

 

진리표 → 간소화 전 과정 예

 

A	B	C	F	최소항
0	0	0	0	—
0	0	1	1	ABC = m₁
0	1	0	1	ABC = m₂
0	1	1	1	ABC = m₃
1	0	0	1	ABC = m₄
1	0	1	1	ABC = m₅
1	1	0	0	—
1	1	1	0	—

 

전개 및 간소화 과정

F = Σm(1,2,3,4,5)
= ABC + ABC + ABC + ABC + ABC

💡 여기서 m5에 해당하는 ABC 항을 한 번 더 복제하여 짝을 지어줍니다.
= (ABC + ABC) + (ABC + ABC) + (ABC + ABC)
= BC(A+A) + AB(C+C) + AB(C+C)
= BC·1 + AB·1 + AB·1
= BC + AB + AB

 

 

태그 : 불대수BooleanAlgebra디지털공학드모르간정리논리회로SOPPOS최소항최대항논리식간소화