진리표는 원하는 논리적 동작을 적어 둔 설계도입니다. ‘초록불이고 장애물이 없으면 직진’처럼 간단한 판단은 AND, OR, NOT 게이트를 직관적으로 조합해 회로로 옮길 수 있습니다.
하지만 모든 불 함수가 이렇게 쉽게 분해되지는 않습니다. 임의의 진리표를 AND, OR, NOT으로 체계적으로 변환하는 방법은 없을까요?
있습니다. 그 방법 중 하나를 알아봅시다. 시리즈 초반에서 가장 추상적인 부분이지만, 예시를 따라가면 어렵지 않습니다.
핵심 아이디어는 간단합니다. 출력 값이 참(1)이 되는 모든 입력 조합들을 찾아서, 그 각각의 조합을 AND 게이트로 만들고, 마지막으로 이 AND 결과들을 모두 OR 게이트로 합치는 것입니다.
말로만 들으면 조금 복잡하게 느껴질 수 있으니 예시를 통해 자세히 살펴볼까요? 두 입력이 같을 때 출력이 1인 게이트를 AND, OR, NOT만으로 만들어 봅시다. 우선 진리표를 살펴보면 다음과 같습니다.
| A == B | ||
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
이제 간단한 세 단계를 거치면 됩니다.
우선 출력 값이 1인 행을 모두 찾습니다. 위 진리표에서 출력이 1인 행은 첫 번째 행 (A=0, B=0)과 네 번째 행 (A=1, B=1)입니다.
그 다음 각 행을 표현하는 AND 조건을 만듭니다. 첫 번째 행 (A=0, B=0)은
입력 A가 0이고 입력 B가 0일 때 출력이 1이라는 뜻이며 이는
(입력 A가 0이다) AND (입력 B가 0이다) 즉, (NOT A) AND (NOT B)로 표현할 수
있습니다. 네 번째 행 (A=1, B=1)은
입력 A가 1이고 입력 B가 1일 때 출력이 1이라는 뜻이며 이는 A AND B로 표현할
수 있습니다.
마지막으로 이렇게 만들어진 각 AND 조건들을 OR 게이트로 모두 연결합니다. 출력이 1이 되는 경우는 ‘첫 번째 행의 조건이 만족’ 또는 ‘네 번째 행의 조건이 만족’일 때입니다. 따라서 위에서 만든 두 식을 OR로 연결하면 됩니다.
최종 논리식은 ((NOT A) AND (NOT B)) OR (A AND B) 가 됩니다.
| NOT A | NOT B | (NOT A) AND (NOT B) | A AND B | ((NOT A) AND (NOT B)) OR (A AND B) | ||
|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 | 0 | 1 | 1 |
원래 진리표와 똑같이 작동하는 회로가 완성됐습니다.
이처럼 진리표는 원하는 논리적 동작을 정의하는 ‘설계도’ 역할을 하고, 방금 소개한 방법은 이 설계도를 AND, OR, NOT이라는 ‘기본 부품’을 이용해 실제 회로로 만드는 과정을 보여줍니다.
AND, OR, NOT은 사람에게 직관적이지만, 하드웨어 엔지니어의 관점에서는 물리적으로 얼마나 효율적이고 간단하게 구현할 수 있는지가 더 중요합니다.
AND, OR, NOT은 물론 그 어떤 복잡한 논리 게이트도 오직 NAND 게이트 하나만으로 모두 만들 수 있습니다. 이를 NAND의 완전성 또는 보편성이라고 부릅니다. 마치 레고 블록 중에 특정 모양 하나만 있어도 다른 모든 모양을 조립할 수 있는 만능 블록이 있는 것처럼. NAND와 NOR 게이트가 바로 그런 만능 블록입니다.
다음 글에서는 어떻게 NAND 게이트 하나만으로도 모든 논리 회로를 구성할 수 있는지 알아보겠습니다.