← 블로그로 돌아가기부울 대수 기초 · 2/4

곱의 합(SOP) 마스터하기: 부울 함수 가이드

곱의 합(SOP)은 최소항을 OR로 연결하여 진리표를 부울 식으로 변환합니다. 결과는 AND-OR 또는 NAND-NAND 하드웨어에 직접 매핑됩니다.

DennyDenny
약 6분 소요
Chalkboard feature illustration for “곱의 합(SOP) 마스터하기: 부울 함수 가이드”

요약: 곱의 합(SOP)은 모든 진리표를 부울 식으로 바꾸는 체계적인 방법입니다. 출력이 1인 각 행에 최소항 하나를 쓰고, 그것들을 OR로 연결합니다. 표준형은 정확하지만 거의 최소형은 아니므로 카르노 맵이나 부울 대수로 단순화하세요.

디지털 설계의 근본 과제는 진리표로 표현한 규칙 집합인 원하는 동작을 논리 게이트의 물리적 배열로 번역하는 일입니다. 추측 없이 이 간극을 어떻게 체계적으로 연결할 수 있을까요?

답은 곱의 합(SOP) 형식입니다. SOP는 모든 진리표를 동작하는 게이트 수준 회로로 변환하는 기계적이고 반복 가능한 방법을 제공합니다. 추상적 요구 사항에서 실체 있는 하드웨어로 옮겨 가는 첫 번째 주요 단계입니다.

곱의 합이란?

곱의 합 형식은 핵심적으로 하나 이상의 AND 항을 OR로 연결하여 부울 식을 쓰는 방법입니다. 부울 대수에서는 OR 연산을 흔히 “합”, AND 연산을 “곱”이라고 부릅니다.

다음 식을 생각해 보겠습니다.

Y=(A⋅B‾)+(A‾⋅B)Y = (A \cdot \overline{B}) + (\overline{A} \cdot B)

여기서 (A⋅B‾)(A \cdot \overline{B})는 한 곱항이고 (A‾⋅B)(\overline{A} \cdot B)는 또 다른 곱항입니다. + 기호는 OR 연산, 즉 이 곱들의 “합”을 나타냅니다. 이 구조는 두 단계 회로로 직접 변환됩니다. 첫 단계의 AND 게이트가 두 번째 단계의 단일 OR 게이트로 들어갑니다. 이 예측 가능성이 그 힘의 원천입니다.

원자 단위: 최소항

진리표에서 SOP 식을 만들려면 먼저 그 기본 구성 요소인 최소항을 이해해야 합니다. 최소항은 함수의 모든 변수를 원형 또는 보수형으로 포함하는 특별한 곱항입니다.

세 변수(A, B, C)를 가진 함수에는 23=82^3 = 8개의 가능한 최소항이 있습니다. 각 최소항은 진리표의 정확히 한 행에 대응합니다.

최소항을 만드는 규칙은 간단합니다.

  • 행에서 변수 값이 1이면 변수를 직접 사용합니다(예: A).
  • 행에서 변수 값이 0이면 변수의 보수를 사용합니다(예: A‾\overline{A}).

3변수 시스템의 최소항을 나열해 보겠습니다.

최소항이진수(ABC)식
m0m_0000A‾⋅B‾⋅C‾\overline{A} \cdot \overline{B} \cdot \overline{C}
m1m_1001A‾⋅B‾⋅C\overline{A} \cdot \overline{B} \cdot C
m2m_2010A‾⋅B⋅C‾\overline{A} \cdot B \cdot \overline{C}
m3m_3011A‾⋅B⋅C\overline{A} \cdot B \cdot C
m4m_4100A⋅B‾⋅C‾A \cdot \overline{B} \cdot \overline{C}
m5m_5101A⋅B‾⋅CA \cdot \overline{B} \cdot C
m6m_6110A⋅B⋅C‾A \cdot B \cdot \overline{C}
m7m_7111A⋅B⋅CA \cdot B \cdot C

각 최소항은 특정 입력 조합에서만 1로 평가됩니다. 예를 들어 m5m_5(A⋅B‾⋅CA \cdot \overline{B} \cdot C)는 A=1, B=0, C=1일 때에만 참입니다. 나머지 일곱 입력 조합에서는 거짓입니다. 최소항은 진리표의 개별 행을 정확하게 겨냥하는 도구입니다.

진리표에서 SOP까지: 3단계 방법

최소항을 이해했다면, 모든 진리표를 SOP 식으로 변환하는 일은 간단하고 기계적인 과정입니다.

“3개 중 2개 이상 다수결” 함수를 예로 사용해 보겠습니다. 두 개 이상의 입력이 1일 때에만 출력 Y가 1입니다.

ABCY최소항
0000
0010
0100
0111A‾⋅B⋅C\overline{A} \cdot B \cdot C
1000
1011A⋅B‾⋅CA \cdot \overline{B} \cdot C
1101A⋅B⋅C‾A \cdot B \cdot \overline{C}
1111A⋅B⋅CA \cdot B \cdot C

1단계: 출력이 1인 모든 행을 식별합니다. 이 예에서 입력 조합 011, 101, 110, 111일 때 출력 Y는 1입니다.

2단계: 이 각 행의 최소항을 씁니다. 위 표를 사용하면 해당 최소항은 m3,m5,m6,m_3, m_5, m_6, 및 m7m_7입니다.

3단계: 모든 최소항을 OR로 연결합니다. 그러면 함수의 최종 SOP 식을 얻습니다.

Y=(A‾⋅B⋅C)+(A⋅B‾⋅C)+(A⋅B⋅C‾)+(A⋅B⋅C)Y = (\overline{A} \cdot B \cdot C) + (A \cdot \overline{B} \cdot C) + (A \cdot B \cdot \overline{C}) + (A \cdot B \cdot C)

이는 관련된 모든 최소항을 직접적으로, 단순화하지 않고 합한 것이므로 표준 SOP 형식이라고 합니다. 함수를 완벽하게 설명하며 즉시 회로를 만들 수 있습니다.

흔한 함정: 표준형과 최소형

학생이 흔히 혼동하는 점은 표준 SOP가 최종 답이라고 가정하는 것입니다. 기능적으로는 정확하지만 거의 항상 가장 효율적인 구현은 아닙니다. 대개 필요한 것보다 더 많은 게이트와 입력을 사용합니다.

다수결 함수 식을 다시 보세요. 부울 대수로 단순화할 수 있습니다.

Y=(A‾⋅B⋅C)+(A⋅B‾⋅C)+(A⋅B⋅C‾)+(A⋅B⋅C)Y = (\overline{A} \cdot B \cdot C) + (A \cdot \overline{B} \cdot C) + (A \cdot B \cdot \overline{C}) + (A \cdot B \cdot C) Y=B⋅C⋅(A‾+A)+A⋅C⋅(B‾+B)+A⋅B⋅(C‾+C)Y = B \cdot C \cdot (\overline{A} + A) + A \cdot C \cdot (\overline{B} + B) + A \cdot B \cdot (\overline{C} + C)

이 대수적 접근은 작동하지만 더 큰 식에서는 오류가 나기 쉽습니다. 카르노 맵은 SOP 단순화를 위한 시각적 방법을 제공합니다. K-맵에서 진리표의 1들을 묶으면 훨씬 단순한 식을 빠르게 찾습니다.

Y=(A⋅B)+(A⋅C)+(B⋅C)Y = (A \cdot B) + (A \cdot C) + (B \cdot C)

이 최소 SOP 형식은 정확히 같은 논리를 구현하지만 2입력 AND 게이트 세 개와 3입력 OR 게이트 하나만 필요합니다. 표준형의 3입력 AND 게이트 네 개와 4입력 OR 게이트 하나보다 상당히 개선됩니다. 교훈은 명확합니다. 처음 유도한 SOP는 최적화의 출발점이지 목적지가 아닙니다.

digisim.io에서 시뮬레이션하기

개념을 증명하기 위해 다수결 회로의 단순화되지 않은 표준 버전을 만들어 봅시다. 이는 방정식과 하드웨어 사이의 연결을 내면화하는 가장 좋은 방법입니다.

  1. 입력 설정: 도구 모음에서 Input 컴포넌트 세 개를 캔버스로 드래그합니다. A, B, C로 레이블을 붙입니다.
  2. 최소항(곱항) 만들기:
  • 첫 번째 최소항 A‾⋅B⋅C\overline{A} \cdot B \cdot C에는 입력 A용 NOT 게이트 하나가 필요합니다. 이 NOT 게이트의 출력과 입력 B, C를 3입력 AND 게이트에 연결합니다.
  • 나머지 세 최소항 (A⋅B‾⋅C)(A \cdot \overline{B} \cdot C), (A⋅B⋅C‾)(A \cdot B \cdot \overline{C}), (A⋅B⋅C)(A \cdot B \cdot C)에도 이 과정을 반복합니다. 총 3입력 AND 게이트 네 개가 생깁니다.
  1. 합 만들기: 네 AND 게이트의 출력을 하나의 4입력 OR 게이트에 연결합니다.
  2. 출력 추가: 마지막 OR 게이트의 출력을 Output 컴포넌트(또는 시각적 피드백용 LED)에 연결합니다.

이제 회로를 시험하세요! A, B, C 입력을 토글합니다. 적어도 두 입력이 High일 때에만 출력이 활성화되어 원래 진리표와 정확히 일치함을 볼 수 있습니다. 명세를 동작하는 디지털 논리 회로로 성공적으로 변환했습니다.

SOP에서 NAND-NAND로의 연결

SOP의 가장 중요한 성질 중 하나는 NAND-NAND 논리에 직접 매핑된다는 것입니다. CMOS 기술에서 NAND 게이트는 AND 또는 OR 게이트보다 물리적으로 작고 빠릅니다. 다행히 모든 SOP 식은 드모르간의 법칙을 이용해 2단 NAND-NAND 회로로 변환할 수 있습니다.

변환은 기계적입니다. 최소 다수결 함수부터 시작합니다.

Y=AB+AC+BCY = AB + AC + BC

값을 바꾸지 않는 이중 부정을 적용합니다.

Y=AB+AC+BC‾‾Y = \overline{\overline{AB + AC + BC}}

바깥쪽 윗줄에 드모르간의 법칙을 적용합니다.

Y=AB‾⋅AC‾⋅BC‾‾Y = \overline{\overline{AB} \cdot \overline{AC} \cdot \overline{BC}}

각 AB‾\overline{AB}는 NAND 연산이며 그 곱 위의 바깥쪽 윗줄도 NAND입니다. 결과는 2입력 NAND 게이트 세 개가 3입력 NAND 게이트 하나로 들어가는 2단 NAND-NAND 회로입니다. AND-OR 구현과 논리적으로 동일하지만 게이트 종류 하나만 사용하므로 제조와 셀 라이브러리가 단순해집니다.

실제 활용

곱의 합 형식은 현대 컴퓨팅의 아키텍처에 내장되어 있습니다.

  1. 프로그래머블 논리 배열(PLA): 복잡한 조합 논리를 구현하는 집적 회로입니다. PLA의 내부 구조는 SOP 개념의 직접적인 물리적 구현입니다. 곱항을 만드는 프로그래머블 “AND 평면”과 곱을 합하는 프로그래머블 “OR 평면”으로 구성됩니다. 엔지니어는 이 평면에서 만들 연결을 지정하여 함수를 정의하며, 사실상 하드웨어 안에 맞춤 SOP 회로를 만듭니다.
  2. 메모리 주소 디코딩: CPU가 메모리의 특정 위치를 읽거나 써야 할 때 주소 버스에 주소를 둡니다. 메모리 컨트롤러 안의 디코더 회로는 어떤 메모리 칩과 어떤 행/열을 활성화할지 식별해야 합니다. 이 논리는 흔히 SOP로 구현됩니다. 예를 들어 특정 RAM 블록을 인에이블하는 신호는 Enable_Block_3 = A_{15} \cdot A_{14} \cdot \overline{A_{13}}일 수 있습니다. 이 곱항은 상위 주소 비트가 해당 특정 패턴과 일치할 때에만 블록이 선택되도록 합니다. 전체 메모리 맵의 논리는 이러한 곱항의 합입니다.

곱의 합 형식은 아이디어에서 회로까지 신뢰할 수 있고 체계적인 경로를 제공합니다. 아무리 복잡한 부울 함수라도 표준 2단 AND-OR(또는 NAND-NAND) 게이트 구조로 표현하고 만들 수 있음을 보장합니다.

이 시리즈의 다음 글인 합의 곱(POS)으로 계속 진행하세요. 진리표의 1이 아니라 0에서 유도하는 쌍대입니다. 또는 카르노 맵으로 바로 이동해 시각적으로 SOP를 최소화하세요.

관련 게시글

아이디어를 실제로 작동하는 회로로 만들어 보세요.

작업대 열기