왜 표준형이 필요한가

09편에서 불 대수 법칙으로 논리식을 자유롭게 변형하는 법을 배웠다. 그런데 법칙을 적용하는 순서에 따라 사람마다 다른 형태의 식을 얻을 수 있다는 문제가 있다. 두 사람이 같은 진리표를 보고 서로 다른 모양의 식을 썼을 때, 그 둘이 정말 같은 함수인지 눈으로 바로 확인하기는 어렵다.

표준형(standard form, canonical form)은 이 문제를 해결한다. 같은 진리표에서 출발하면 누가 쓰더라도 정확히 같은 모양의 식이 나오도록 정해진 규칙이다. 표준형을 알면 (1) 진리표에서 식을 기계적으로, 실수 없이 뽑아낼 수 있고 (2) 두 식이 정말 같은 함수인지 표준형으로 바꿔서 비교할 수 있고 (3) 다음 편에서 배울 카르노맵(Karnaugh map) 간소화의 출발점으로 쓸 수 있다.

쉽게 말하면: 표준형은 “진리표를 식으로 바꾸는 유일한 정답 양식”이다. 정해진 틀에 값만 채우면 되므로 실수할 여지가 적다.

최소항: 정확히 한 줄만 1이 되는 곱 항

쉽게 말하면: 최소항은 진리표의 한 행(row)을 정확히 콕 집어내는 AND 항이다.

정의

최소항(minterm)은 $n$개의 변수를 모두 사용해서 만든 AND 항인데, 그 변수 조합이 정확히 하나의 입력 조합에서만 1이 되도록 만든 것이다. 규칙은 간단하다. 변수 값이 1이면 그 변수를 그대로 쓰고, 변수 값이 0이면 그 변수의 보수(complement, '가 붙은 형태)를 쓴다.

예를 들어 변수가 $A, B, C$ 세 개이고 $(A,B,C) = (1,0,1)$인 행을 콕 집어내려면, $A$는 1이니까 그대로 $A$, $B$는 0이니까 보수 $B'$, $C$는 1이니까 그대로 $C$를 쓰고 이 셋을 AND로 묶는다.

이렇게 만든 항은 $(A,B,C)=(1,0,1)$일 때만 $1 \cdot 1 \cdot 1 = 1$이 되고, 다른 일곱 개 조합에서는 반드시 어느 한 리터럴(literal, 변수 또는 그 보수)이 0이 되어 전체 곱이 0이 된다. 최소항은 보통 아래첨자 번호로도 표기하는데, 이 번호는 변수 조합을 이진수로 읽은 값이다. $(1,0,1)_2 = 5$이므로 이 최소항은 $m_5$라고 쓴다.

3변수 최소항 전체 목록

변수가 $n$개면 최소항은 항상 $2^n$개 존재한다(각 변수가 원래 형태 또는 보수 형태 중 하나를 고르는 경우의 수이므로). 3변수는 $2^3=8$개, 4변수는 $2^4=16$개다.

최대항: 정확히 한 줄만 0이 되는 합 항

쉽게 말하면: 최대항은 최소항의 반대다. 진리표의 한 행을 정확히 콕 집어 0으로 만드는 OR 항이다.

정의

최대항(maxterm)은 $n$개의 변수를 모두 사용해서 만든 OR 항인데, 그 변수 조합이 정확히 하나의 입력 조합에서만 0이 되도록 만든 것이다. 규칙은 최소항과 정반대다. 변수 값이 0이면 그 변수를 그대로 쓰고, 변수 값이 1이면 보수를 쓴다.

$(A,B,C) = (1,0,1)$인 행을 콕 집어 0으로 만들려면, $A$는 1이니까 보수 $A'$, $B$는 0이니까 그대로 $B$, $C$는 1이니까 보수 $C'$를 쓰고 이 셋을 OR로 묶는다.

이 항은 $(A,B,C)=(1,0,1)$일 때만 $0+0+0=0$이 되고, 다른 조합에서는 항상 어느 한 리터럴이 1이 되어 전체 합이 1이 된다. 최대항 번호도 이진수 값을 그대로 쓴다. $(1,0,1)_2=5$이므로 $M_5$다.

자주 틀리는 점: 최소항·최대항 규칙을 헷갈림

• 가장 흔한 실수는 최대항을 만들 때도 최소항 규칙(1이면 그대로, 0이면 보수)을 그대로 적용하는 것이다. 최대항은 반대(0이면 그대로, 1이면 보수)라는 것을 꼭 기억해야 한다.
• 최소항과 최대항은 번호가 같으면($m_5$와 $M_5$) 서로 정확히 보수 관계다. $m_5 = AB'C$의 보수를 드모르간 법칙으로 풀면 $(AB'C)' = A'+B+C' = M_5$가 되어 실제로 일치한다.
• 진리표에서 최소항은 함수 값이 1인 행에서, 최대항은 함수 값이 0인 행에서 가져온다는 점도 자주 뒤바뀐다.

SOP: 최소항들을 OR로 묶은 표준 합의 곱

쉽게 말하면: 진리표에서 결과가 1인 행을 전부 찾아 그 행의 최소항을 OR로 이어붙이면 원래 함수와 완전히 같은 식이 된다.

SOP(Sum of Products, 합의 곱)는 여러 AND 항(곱, product)을 OR(합, sum)로 묶은 형태다. 그중에서도 표준 SOP(canonical SOP)는 그 AND 항이 모두 최소항인 경우를 말한다.

진리표에서 표준 SOP 뽑기: 실제 예제

다음 3변수 함수 $F(A,B,C)$의 진리표를 보자.

$F=1$인 행은 $m_1, m_3, m_5, m_7$ 네 개다. 이 최소항들을 OR로 묶으면 표준 SOP가 된다.

간단히 $F = \sum m(1,3,5,7)$ 이라고도 쓴다. $\sum$(시그마, “모두 더하라”는 뜻)는 뒤에 나열된 최소항 번호들을 OR로 합친다는 표기다.

POS: 최대항들을 AND로 묶은 표준 곱의 합

쉽게 말하면: 진리표에서 결과가 0인 행을 전부 찾아 그 행의 최대항을 AND로 이어붙이면 역시 원래 함수와 완전히 같은 식이 된다.

POS(Product of Sums, 곱의 합)는 여러 OR 항(합, sum)을 AND(곱, product)로 묶은 형태다. 표준 POS(canonical POS)는 그 OR 항이 모두 최대항인 경우다.

같은 진리표에서 $F=0$인 행은 $(A,B,C) = (0,0,0), (0,1,0), (1,0,0), (1,1,0)$, 즉 $M_0, M_2, M_4, M_6$이다. 이 최대항들을 AND로 묶으면 표준 POS가 된다.

간단히 $F = \prod M(0,2,4,6)$ 이라고 쓴다. $\prod$(파이, “모두 곱하라”는 뜻)는 나열된 최대항 번호들을 AND로 합친다는 표기다.

결과 해석: 같은 함수, 두 가지 표준형

SOP와 POS는 같은 함수 $F$를 표현하는 완전히 다른 두 가지 방법이다. SOP는 1이 되는 곳을 기준으로, POS는 0이 되는 곳을 기준으로 만든다. 실제로 위 예제를 대수적으로 전개하면 두 식이 동일한 진리표를 만든다는 것을 확인할 수 있다(직접 검산하려면 아무 입력이나 대입해 둘 다 같은 값이 나오는지 보면 된다. 예를 들어 $(A,B,C)=(0,0,1)$을 SOP에 넣으면 $m_1$ 항만 1이라 $F=1$이고, POS에 넣으면 네 항 $(A+B+C), (A+B'+C), (A'+B+C), (A'+B'+C)$이 각각 $0+0+1=1$, $0+1+1=1$, $1+0+1=1$, $1+1+1=1$로 전부 1이라 AND 결과도 $F=1$이 되어 일치한다).

한 진리표에서 1인 행이 적으면 SOP가 짧아지고, 0인 행이 적으면 POS가 짧아지는 경향이 있다. 그래서 실무에서는 둘 중 항의 개수가 더 적은 쪽을 표준형으로 고른다.

표준형(canonical form)과 최소형(minimal form)의 차이

쉽게 말하면: 표준형은 “정해진 틀대로 기계적으로 뽑은 식”이고, 최소형은 “그 식을 실제로 최대한 줄인 식”이다.

표준형은 모든 항이 변수를 빠짐없이 전부 포함해야 한다(3변수 함수라면 모든 최소항·최대항이 $A, B, C$ 세 개를 다 가진다). 반면 최소형(minimal form)은 09편의 불 대수 법칙이나 다음 편의 카르노맵으로 간소화해서 리터럴 수를 최대한 줄인 식이다. 최소형에서는 항마다 변수 개수가 다를 수 있다.

위 SOP 예제 $F = A'B'C + A'BC + AB'C + ABC$를 09편에서 배운 법칙으로 간소화해보자.

결과 해석: 표준 SOP는 4항 3변수 곱을 OR로 묶은 형태(3입력 AND 4개 + 4입력 OR 1개)였지만, 최소형은 $F=C$ 단 하나의 리터럴이다. 표준형은 항상 정해진 모양이라 “어떤 진리표에서 왔는지” 명확하지만 게이트 수는 최소형이 압도적으로 적다. 다음 편(11편)에서 배울 카르노맵은 이 최소형을 대수적 계산 없이 그림으로 빠르게 찾는 도구다.

자주 틀리는 점

• 표준형 문제에서 “최소형으로 답하라”는 조건을 놓치고 표준 SOP·POS를 그대로 답으로 쓰는 실수가 있다. 문제에서 요구하는 형태를 반드시 확인해야 한다.
• 최소항 번호를 나열할 때 순서를 진리표 순서(오름차순)로 정리하지 않아 검산 시 항을 빠뜨리는 경우가 있다. $\sum m(\cdots)$ 표기는 관례상 오름차순으로 쓴다.
• 변수 개수를 착각해 최소항 개수를 잘못 세는 경우가 있다. 변수가 4개면 최소항은 $2^4=16$개이지 8개가 아니다.

핵심 정리

• 최소항(minterm, $m_i$)은 진리표에서 함수 값이 1인 한 행을 정확히 찍어내는 AND 항이며(값이 1인 변수는 그대로, 0인 변수는 보수), 최대항(maxterm, $M_i$)은 그 반대로 함수 값이 0인 한 행을 찍어내는 OR 항이다(값이 0인 변수는 그대로, 1인 변수는 보수).
• 표준 SOP($F=\sum m(\cdots)$)는 함수 값이 1인 모든 최소항을 OR로 묶은 것이고, 표준 POS($F=\prod M(\cdots)$)는 함수 값이 0인 모든 최대항을 AND로 묶은 것이며, 둘은 같은 함수를 나타내는 서로 다른 두 표준형이다.
• 표준형은 모든 항이 변수를 빠짐없이 포함하는 정해진 틀이고, 최소형은 불 대수 법칙(또는 카르노맵)으로 리터럴 수를 최대한 줄인 식이다.

마무리 복습

참고 자료

• 국가평생교육진흥원 독학학위제 - 평가영역 
• IEEE Standards