진리표와 정규형: Σm과 ΠM

읽는 시간 8분 · bitGateLab 팀

디지털 설계 문제는 거의 모두 말로 된 조건("경보는 ...일 때 울린다")에서 시작해 진리표로 옮겨집니다. 다음 단계는 그 표에서 게이트로 만들 수 있는 식을 뽑아내는 것입니다. 여기서는 이를 체계적으로 해내는 방법을 배웁니다. 최소항과 최대항, 곱의 합과 합의 곱 정규형, 그리고 교재와 시뮬레이터, 카르노 맵에서 쓰는 간결한 표기법 Σm과 ΠM입니다.

진리표의 행 순서

변수가 n개이면 행은 2ⁿ개입니다. 행은 첫 번째 변수를 최상위 비트로 하여 2진수 오름차순으로 적습니다. 이렇게 하면 각 행을 10진수 하나로 식별할 수 있습니다. A, B, C의 표에서 A = 1, B = 0, C = 1인 행은 101₂ = 5입니다. 이 번호가 최소항이나 최대항의 인덱스로 쓰이므로 변수의 순서가 중요합니다. 순서를 바꾸면 번호도 바뀝니다.

최소항과 곱의 합

최소항은 모든 변수를 한 번씩만, 부정하거나 부정하지 않은 형태로 포함하는 곱(AND)입니다. 만드는 방법은 이렇습니다. 그 행에서 값이 1인 변수는 막대 없이, 0인 변수는 막대를 붙여 적습니다. 최소항은 자기 행에서만 1이 되고 나머지 모든 행에서는 0이 됩니다. 이름은 m_i로 붙이며, i는 행 번호입니다.

행	A	B	C	최소항	최대항
0	0	0	0	m₀ = ABC	M₀ = A + B + C
1	0	0	1	m₁ = ABC	M₁ = A + B + C
2	0	1	0	m₂ = ABC	M₂ = A + B + C
3	0	1	1	m₃ = ABC	M₃ = A + B + C
4	1	0	0	m₄ = ABC	M₄ = A + B + C
5	1	0	1	m₅ = ABC	M₅ = A + B + C
6	1	1	0	m₆ = ABC	M₆ = A + B + C
7	1	1	1	m₇ = ABC	M₇ = A + B + C

함수가 1이 되는 모든 행의 최소항을 더하면(OR) 정확히 그 행들에서만 1이 되는 식을 얻습니다. 이것이 곱의 합 정규형(영어 약어로 SOP) 또는 제1 정규형입니다. 간결한 표기로는 F = Σm(1인 행의 목록)으로 씁니다.

최대항과 합의 곱

최대항은 모든 변수를 포함하는 합(OR)입니다. 규칙은 반대입니다. 그 행에서 값이 0인 변수는 막대 없이, 1인 변수는 막대를 붙여 적습니다. 최대항은 자기 행에서만 0이 됩니다. 이름은 M_i(대문자 M)로 붙입니다.

함수가 0이 되는 모든 행의 최대항을 곱하면(AND) 바로 그 행들에서 0이 되고 나머지에서는 1이 되는 식을 얻습니다. 이것이 합의 곱 정규형(POS) 또는 제2 정규형입니다. F = ΠM(0인 행의 목록)으로 씁니다.

같은 행의 최소항과 최대항은 서로 보수입니다: m_i = M_i. 따라서 어떤 함수의 Σm 목록을 알고 있다면, ΠM 목록은 그 목록에 없는 모든 번호로 이루어집니다.

예제 1: 진리표에서 두 가지 형태로. 변수가 세 개인 함수가 1, 3, 6, 7행에서 1이 됩니다.

#	A	B	C	F
0	0	0	0	0
1	0	0	1	1
2	0	1	0	0
3	0	1	1	1
4	1	0	0	0
5	1	0	1	0
6	1	1	0	1
7	1	1	1	1

간결한 표기: F = Σm(1, 3, 6, 7) = ΠM(0, 2, 4, 5).
곱의 합 정규형: F = ABC + ABC + ABC + ABC.
합의 곱 정규형: F = (A + B + C)(A + B + C)(A + B + C)(A + B + C).
SOP를 간소화합니다: ABC + ABC = AC이고 ABC + ABC = AB입니다. 따라서 F = AC + AB.

5행(A = 1, B = 0, C = 1)에서 검산하면 AC = 0이고 AB = 0이므로 F = 0이며, 표와 같습니다.

어느 형태가 유리할까요?

두 형태는 같은 함수를 나타내지만 크기는 같지 않습니다. 항이 더 적은 쪽을 쓰세요. 함수에 1이 적으면 Σm이 더 짧고, 0이 적으면 ΠM이 더 짧습니다. 8행 가운데 1이 2개인 함수는 SOP가 2항이고 POS가 6항입니다.

구현 방식도 중요합니다. 곱의 합은 AND 게이트들이 OR 하나로 들어가는 구조로 만들며, 이 두 단계 구조는 그대로 NAND-NAND로 바뀝니다. 합의 곱은 OR들이 AND 하나로 들어가는 구조로 만들며 NOR-NOR로 바뀝니다.

예제 2: 문제 설명에서 식으로. 탱크에 수위 센서가 세 개 있습니다: A(저), B(중), C(고). 각 센서는 물이 닿으면 1을 냅니다. "잘못된 수위" 램프는 물리적으로 불가능한 조합일 때, 즉 높은 쪽 센서는 켜져 있는데 그보다 낮은 센서가 꺼져 있을 때 켜져야 합니다.

유효한 조합(ABC): 000, 100, 110, 111. 즉 0, 4, 6, 7행입니다.
램프는 나머지 행에서 켜집니다: F = Σm(1, 2, 3, 5).
같은 표현: F = ΠM(0, 4, 6, 7).
간소화합니다: m₁ + m₃ = AC, m₁ + m₅ = BC, m₂ + m₃ = AB. m₁과 m₃을 두 번씩 사용하면(멱등 법칙) F = BC + AB.

확인해 봅시다. 1행(001)은 BC = 1, 2행(010)은 AB = 1, 3행(011)은 AB = 1, 5행(101)은 BC = 1입니다. 000, 100, 110, 111에서는 두 항 모두 0입니다. "B 없이 C가 켜짐" 또는 "A 없이 B가 켜짐"으로 읽을 수 있습니다.

함수의 보수

F = Σm(1, 3, 6, 7)이면 그 보수는 F가 0인 곳에서 1이 됩니다: F = Σm(0, 2, 4, 5). 이는 간소화된 POS를 구하고 싶을 때 유용합니다. F를 곱의 합으로 간소화한 다음 드 모르간의 정리를 적용하면 됩니다. 예를 들어 F = AC + AB이고(0, 2, 4, 5행으로 확인해 보세요), 보수를 취하면 F = (A + C)(A + B)가 됩니다. 전개하면 AB + AC + BC이고, 합의 정리에 따라 이는 AB + AC, 곧 예제 1과 같은 결과입니다.

이런 식 변형을 더 깊이 알고 싶다면 부울 대수를 복습하고, 그림으로 간소화하는 방법은 카르노 맵에서 이어집니다.

흔한 실수

막대 규칙을 거꾸로 적용하는 것: 최소항에서는 0에 막대가 붙고, 최대항에서는 1에 막대가 붙습니다.
함수가 1인 행을 ΠM에 넣는 것. ΠM은 0을, Σm은 1을 나열합니다.
진리표와 식 사이에서 변수 순서를 바꾸는 것. 순서가 C, B, A이면 "5"행은 더 이상 같은 행이 아닙니다.
정규형의 항에서 변수를 빠뜨리는 것. 변수가 네 개인 최소항에는 언제나 리터럴이 네 개 있습니다. 그보다 적다면 이미 간소화된 것이므로 정규형이 아닙니다.

시뮬레이터에서 해 보기

진리표 모듈에서는 함수를 행 단위로 입력하면 정규형과 간소화된 식을 바로 볼 수 있으므로, 손으로 한 각 단계를 검토할 수 있습니다.

입력 세 개, 출력 하나인 진리표를 만듭니다.
예제 1의 1, 3, 6, 7행을 1로 표시하고 나머지는 0으로 둡니다.
생성되는 Σm과 ΠM 식을 살펴보고 직접 구한 것과 비교합니다.
진리표를 회로로 변환하고 입력을 바꿔 가며 출력이 표를 따르는지 확인합니다.
탱크 문제로 반복하고, 불가능한 조합에서만 램프가 켜지는지 확인합니다.

연습문제

최소항 m₉와 최대항 M₉를 쓰세요. 함수의 변수는 A, B, C, D 네 개입니다.
정답
9 = 1001. m₉ = ABCD이고 M₉ = A + B + C + D입니다.
F(A, B, C) = Σm(0, 1, 5)일 때 F를 ΠM 표기로 쓰세요.
정답
F = ΠM(2, 3, 4, 6, 7).
A와 B가 같을 때만 1이 되는, 변수가 두 개인 함수의 곱의 합 정규형을 구하고, 가능하면 간소화하세요.
정답
F = Σm(0, 3) = AB + AB. 더 줄일 수 없습니다. XNOR입니다.
F(A, B, C) = Σm(1, 2, 3, 4, 5, 6, 7)의 합의 곱 정규형을 쓰세요.
정답
0행에서만 0이 되므로 F = ΠM(0) = A + B + C입니다. 입력이 세 개인 OR 하나입니다.