부제: 논리 회로 간소화의 핵심
디지털 논리 회로 설계에서 복잡한 논리식을 간소화하는 것은 비용 절감과 속도 향상에 직결된다. 불 대수(Boolean Algebra)의 기본 법칙부터 이를 시각적으로 도식화한 카르노맵(K-Map)까지, 엔지니어링 관점에서 핵심을 정리한다.
1. 불 대수의 기본 법칙
논리 연산의 기초가 되는 법칙들이다. 사칙연산과 유사하지만, 디지털 논리만의 특징적인 법칙(드모르간, 흡수 법칙 등)이 존재한다.
교환법칙 (Commutative Law)
순서를 바꿔도 결과는 같다.
$$A + B = B + A$$
$$A \cdot B = B \cdot A$$
결합법칙 (Associative Law)
연산 순서는 결과에 영향을 주지 않는다.
$$A + (B + C) = (A + B) + C$$
$$(A \cdot B) \cdot C = A \cdot (B \cdot C)$$
분배법칙 (Distributive Law)
괄호를 풀거나 묶을 때 사용한다. 두 번째 식은 일반 대수와 다르니 주의해야 한다.
$$A \cdot (B + C) = A \cdot B + A \cdot C$$
$$A + (B \cdot C) = (A + B) \cdot (A + C)$$
드모르간의 법칙 (De Morgan’s Laws)
NAND와 NOR 게이트 변환의 핵심이다. 전체의 부정은 각각의 부정의 반대 연산과 같다.
$$\overline{(A + B)} = \overline{A} \cdot \overline{B}$$
$$\overline{(A \cdot B)} = \overline{A} + \overline{B}$$
2. 기본 연산 및 정리
기본 항등식
$$A \cdot 0 = 0, \quad A \cdot 1 = A$$
$$A + 0 = A, \quad A + 1 = 1$$
$$A + \overline{A} = 1, \quad A \cdot \overline{A} = 0$$
$$A + A = A, \quad A \cdot A = A$$
특히 $A + \overline{A} = 1$은 카르노맵의 기본 원리다.
간소화 정리
다음 정리들은 회로의 게이트 수를 줄이는 데 매우 유용하다.
$$A + A \cdot \overline{B} = A$$
($A (1+ \overline{B})$에서 1+X는 항상 1이므로 윗 식이 성립된다.)
$$A + \overline{A}B = (A + \overline{A}) \cdot (A + B) = A + B$$
(덧셈의 분배 법칙으로 바로 확인이능하다.)
$$\overline{A} B + \overline{B} = \overline{A \cdot B}$$
(세 번째 식도 분배법칙으로 풀이된다. 물론 우변은 드모르간 법칙으로 풀어 놓는다.)
3. 카르노맵 (Karnaugh Map)
불 대수식을 대수적으로 풀면 실수가 잦다. 카르노맵은 이를 2차원 그리드로 펼쳐 시각적으로 묶어내는(Grouping) 도구를 제안했다.
기본 원리
예를 들어, 다음 논리식을 보자.
$$F = \overline{A} B + A \overline{B} + AB$$
원래 위와 같이 풀었는데, 아래의 묶는 규칙에 따라 이 식을 맵에 배치하고 인접한 ‘1’끼리 최대한 많이 묶으면 공통인수는 남고 변화하는 변수는 사라진다. ($A + \overline{A} = 1$ 원리 이용). 최대한 많이 묶는다는 것은 묶을 수 있는 도구가 추가 가능하기 때문이다. $(AB+AB=AB)$가 자동적으로 적용된다.
위와 같이, 여러 대수식을 써 놓으면 어떻케 묶어야 할지 한 참 찾아봐야 하는 문제점이 카르노맵에서는 바로 해결된다. 묶는 규칙만 잘 따르면 된다.
묶는 규칙 (Grouping Rules)
- 2의 거듭제곱 개수로 묶는다 ($1, 2, 4, 8, 16 \dots$).
- 가능한 크게 묶어야 항이 더 많이 줄어든다.
- Map Rolling: 상하좌우 끝은 서로 연결되어 있다. (지구가 둥근 것처럼 벽을 통과하여 묶을 수 있다.)
- 대각선으로는 묶을 수 없다.
3변수와 4변수 맵
카르노맵의 축은 그레이 코드(Gray Code) 순서로 배치해야 한다. 즉, 인접한 칸끼리는 반드시 비트가 하나만 달라야 한다.
그림 3. 3변수 카르노맵 작성법
3변수 및 4변수 내부의 값은 2진수를 10진수로 나타낸 값들이다.
실전 예제
다음과 같은 진리표 출력을 가지는 4변수 함수가 있다고 하자.
$$F(A,B,C,D) = \Sigma(4, 5, 12, 13, 15, 16)$$
카르노맵을 그린 후 간소화된 논리식을 세우시오.
다른 문제.
$$F = \overline{A}\overline{B}\overline{C}\overline{D} + A\overline{B}\overline{C}\overline{D} + \overline{A}\overline{B}C\overline{D} + A\overline{B}C\overline{D}$$
4변수 맵의 경우, 네 귀퉁이가 모두 ‘1’이라면 이를 하나로 묶을 수 있다. 이는 맵이 토러스(Toroidal) 형태, 즉 도넛 모양처럼 상하좌우가 모두 연결된 공간임을 의미한다.
2026.1.17 문서표준화 함