정의
최소항 전개(最小項 展開)는 불대수(Boolean algebra)에서 논리 함수(또는 부울 함수)를 모든 가능한 입력 조합에 대해 1(참)인 경우에만 해당하는 최소항(𝑚‑항)의 논리합(OR) 형태로 표현한 표준 형태를 말한다. 최소항은 각 변수에 대해 변수 자체 또는 그 보수(¬)가 정확히 한 번씩 포함된 곱(AND) 항으로, 해당 입력 조합이 참이 되는 경우에만 1 값을 산출한다. 따라서 최소항 전개는 논리 함수를 “참인 경우의 모든 입력 조합을 나열한 합”으로 나타낸다.
관련 용어
- 카르노 지도(Karnaugh map): 최소항 전개를 간소화하거나 최소화된 표현을 찾는 도구.
- 합곱표현(SOP, Sum‑of‑Products): 최소항 전개는 SOP 표현의 한 형태이며, 특히 모든 항이 최소항일 때를 ‘완전합곱표현’이라고 부른다.
- 최소항(minterm): 변수 n개에 대해 2ⁿ개의 가능한 조합 중 하나에 대응하는, 각 변수와 보수가 정확히 한 번씩 포함된 AND 항.
- 표준합곱표현(Canonical SOP): 모든 최소항을 포함한 SOP 형태로, 최소항 전개와 동등한 의미로 사용된다.
표기법
n개의 변수 $x_1, x_2, \dots, x_n$에 대해, 입력 조합 $(a_1, a_2, \dots, a_n)$가 1인 경우의 최소항은
$$
m_{k}= \bigwedge_{i=1}^{n} \begin{cases}
x_i & \text{if } a_i = 1\
\overline{x_i} & \text{if } a_i = 0
\end{cases}
$$
여기서 $k$는 해당 조합을 2진수로 해석한 정수값이다. 논리 함수 $f$는
$$
f = \bigvee_{k \in T} m_{k}
$$
형태로 전개되며, $T$는 $f$가 1인 입력 인덱스 집합이다.
예시
3변수 함수 $f(A,B,C)=\Sigma m(1,3,5,7)$는 1인 입력 조합이 001, 011, 101, 111인 경우이다. 최소항 전개는
$$
f = \overline{A},\overline{B},C ;+; \overline{A},B,C ;+; A,\overline{B},C ;+; A,B,C
$$
와 같이 표현된다.
활용
- 디지털 회로 설계: 최소항 전개를 기반으로 AND‑OR 회로를 직접 구현한다.
- 논리 최적화: 최소항 전개를 시작점으로 하여 카르노 지도, 퀸즈 메서드, 부울 대수 법칙 등을 적용해 최소화된 논리식을 도출한다.
- 프로그램 검증 및 형식 검증: 부울 함수의 정확성을 증명하기 위해 완전한 최소항 전개를 사용해 모든 경우를 검토한다.
한계
최소항 전개는 모든 1값 입력을 명시적으로 포함하므로 변수 수가 증가할 경우 항의 개수가 급격히 늘어나(최대 $2^{n}$개) 구현 비용이 커진다. 따라서 실무에서는 최소항 전개를 직접 구현하기보다, 이를 간소화한 최소 표현을 사용한다.
참고
- Boolean Algebra 및 디지털 논리 설계 교과서(예: M. Morris Mano, “Digital Logic and Computer Design”).
- IEEE 표준 및 학술 논문에서 사용되는 표기법과 정의.
