부울 대수
IT 위키
(불 대수에서 넘어옴)
Boolean Algebra; 불 대수; 논리 대수
참(1)과 거짓(0) 두 값만 다루는 대수 체계
1847년 조지 불(George Boole)이 만들었고, 1938년 클로드 섀넌이 이를 스위치 회로에 적용하면서 논리 회로 설계의 기초가 되었다.
- 논리곱 A·B (AND)
- 논리합 A+B (OR)
- 보수 A' 또는 Ā (NOT)
우선순위는 NOT → AND → OR 순이다.
| 법칙 | 논리곱 | 논리합 |
|---|---|---|
| 항등 | A·1 = A | A+0 = A |
| 영(지배) | A·0 = 0 | A+1 = 1 |
| 멱등 | A·A = A | A+A = A |
| 보수 | A·A' = 0 | A+A' = 1 |
| 교환 | A·B = B·A | A+B = B+A |
| 결합 | (A·B)·C = A·(B·C) | (A+B)+C = A+(B+C) |
| 분배 | A·(B+C) = A·B + A·C | A+(B·C) = (A+B)·(A+C) |
| 흡수 | A·(A+B) = A | A + A·B = A |
| 이중 부정 | (A')' = A | |
논리합 쪽의 분배 법칙 A+(B·C) = (A+B)·(A+C) 는 보통의 수 연산에는 없는 형태다.
(A·B)' = A' + B' (A+B)' = A' · B'
전체의 보수는 각각의 보수를 취하고 연산을 바꾼 것과 같다. 이 법칙 덕분에 NAND 게이트만으로, 또는 NOR 게이트만으로 모든 논리 회로를 만들 수 있다.
- 가산 표준형 (SOP, Sum of Products) : 최소항(minterm)의 합. `Σm(0, 1, 3)` 으로 표기한다.
- 승산 표준형 (POS, Product of Sums) : 최대항(maxterm)의 곱. `ΠM(2, 4)` 으로 표기한다.
변수가 n개면 최소항은 2n개다. 진리표에서 출력이 1인 행을 모으면 SOP, 0인 행을 모아 보수를 취하면 POS가 된다.
- 대수적 간소화 : 위 법칙을 차례로 적용한다.
- 카르노맵(Karnaugh Map) : 인접한 1을 2의 거듭제곱 개수만큼 묶어 항을 없앤다.
인접 칸이 한 비트만 달라지도록 그레이 코드 순서로 배치하는 것이 핵심이다.
- 퀸-맥클러스키법 : 변수가 많을 때 쓰는 표 기반의 기계적 방법
간소화하면 게이트 수와 전파 지연이 줄어 회로의 비용과 속도가 개선된다.
