부울 대수: 법칙, 드 모르간의 정리, 간소화

읽는 시간 7분 · bitGateLab 팀

부울 대수는 디지털 회로를 기술하고 변형하는 데 쓰는 언어입니다. 식 하나하나가 게이트의 배치에 대응하고, 식을 간소화하려고 적용하는 법칙 하나하나가 게이트의 절약으로 이어집니다. 여기서는 공리, 가장 유용한 법칙, 드 모르간의 정리를 복습하고, 각 단계의 근거를 밝혀 가며 식을 단계별로 간소화하는 방법을 알아봅니다.

변수와 연산

부울 변수는 0과 1의 값만 가집니다. 기본 연산은 세 가지입니다. 보수(A, NOT 게이트), 논리곱(A·B 또는 AB, AND 게이트), 논리합(A + B, OR 게이트)입니다. 괄호가 없을 때의 연산 우선순위는 보수가 가장 먼저이고, 그다음이 곱, 마지막이 합입니다. 따라서 A + BC는 일반 대수에서와 마찬가지로 A + (B·C)를 뜻합니다.

공리

부울 대수 전체는 몇 가지 공리 위에 세워져 있습니다. 공리가 합에 대한 것 하나, 곱에 대한 것 하나씩 쌍으로 되어 있다는 점을 눈여겨보세요.

공리	합의 형태	곱의 형태
항등원	A + 0 = A	A · 1 = A
교환 법칙	A + B = B + A	AB = BA
분배 법칙	A + BC = (A + B)(A + C)	A(B + C) = AB + AC
보원 법칙	A + A = 1	A · A = 0

쌍대성 원리: 어떤 등식이 성립하면, 변수와 그 위의 막대는 그대로 둔 채 +와 ·를 서로 바꾸고 0과 1을 서로 바꾼 등식도 성립합니다. 그래서 모든 법칙에는 "쌍둥이" 형태가 있습니다. 합에 대한 분배 법칙 A + BC = (A + B)(A + C)를 보세요. 실수의 대수에는 없는 법칙이지만 여기서는 완벽하게 성립합니다.

유용한 법칙과 정리

공리로부터 다음 규칙들이 유도되며, 간소화할 때 가장 자주 쓰게 됩니다.

법칙	합의 형태	곱의 형태
멱등 법칙	A + A = A	AA = A
영 법칙	A + 1 = 1	A · 0 = 0
이중 부정(대합)	A = A
결합 법칙	A + (B + C) = (A + B) + C	A(BC) = (AB)C
흡수 법칙	A + AB = A	A(A + B) = A
보수 흡수 법칙	A + AB = A + B	A(A + B) = AB
인접 법칙	AB + AB = A	(A + B)(A + B) = A
합의 정리	AB + AC + BC = AB + AC	(A + B)(A + C)(B + C) = (A + B)(A + C)

이 법칙들은 모두 진리표로 확인할 수 있습니다. 두 열이 모든 행에서 일치하면 등식이 성립합니다. 예를 들어 A + AB = A의 경우, A = 0이면 B와 관계없이 양변이 0이고, A = 1이면 양변이 1입니다. 보수 흡수 법칙은 합에 대한 분배 법칙을 써서 다음과 같이 증명합니다: A + AB = (A + A)(A + B) = 1·(A + B) = A + B.

드 모르간의 정리

이 두 정리는 긴 막대를 어떻게 "끊는지" 알려 줍니다.

A · B = A + B (곱의 보수는 보수의 합입니다).
A + B = A · B (합의 보수는 보수의 곱입니다).

실전 규칙은 이렇습니다. 막대를 끊을 때 그 아래에 있던 연산을 바꾸고(·는 +로, +는 ·로) 각 항을 부정합니다. 변수가 몇 개든 성립합니다: ABC = A + B + C.

A	B	AB	A + B	A + B	AB
0	0	1	1	1	1
0	1	1	1	0	0
1	0	1	1	0	0
1	1	0	0	0	0

회로에서 드 모르간의 정리는 NAND가 입력에 버블이 달린 OR와 같고, NOR가 입력에 버블이 달린 AND와 같다는 것을 뜻합니다. 이것이 어떤 설계든 NAND만으로 또는 NOR만으로 바꾸는 방법의 바탕이며, 자세한 내용은 논리 게이트에서 설명합니다.

예제 1: 드 모르간의 정리 적용하기. F = AB + C를 간소화하세요.

긴 막대가 합을 덮고 있습니다: AB + C = AB · C.
곱 위의 막대를 끊습니다: AB = A + B.
결과: F = (A + B)C = AC + BC.

A = 1, B = 1, C = 0으로 검산하면 원래 식은 1 + 0 = 0, 결과 식은 (0 + 0)·1 = 0입니다. A = 0, B = 1, C = 0이면 원래 식은 0 + 0 = 1, 결과 식은 (1 + 0)·1 = 1입니다.

단계별 대수적 간소화

간소화란 항의 수와 리터럴(부정되었든 아니든 변수가 한 번 나타나는 것)의 수를 줄이는 일입니다. 리터럴이 적을수록 게이트 입력도 적어집니다. 순수한 대수만으로는 정해진 알고리즘이 없지만, 다음 전략은 거의 언제나 통합니다.

변수 하나만 다른 항의 쌍을 찾아 인접 법칙을 적용합니다.
공통 인수를 묶어 내고 숨어 있는 A + A = 1을 찾습니다.
어떤 항이 다른 항에 포함되어 있으면 흡수 법칙으로 없앱니다.
한 항을 복제해(멱등 법칙) 서로 다른 두 이웃 항과 각각 결합할 수 있습니다.

예제 2. F = AB + AB + AB를 간소화하세요.

앞의 두 항을 인수분해합니다: AB + AB = A(B + B) = A·1 = A.
F = A + AB가 남습니다.
보수 흡수 법칙: A + AB = A + B.

F = A + B. AND 게이트 세 개, 입력이 세 개인 OR 하나, 인버터 두 개가 OR 하나로 줄었습니다.

예제 3: 다수결 함수. F = ABC + ABC + ABC + ABC를 간소화하세요.

멱등 법칙에 따라 ABC = ABC + ABC + ABC입니다. 세 개로 복제해 각각을 이웃 항 하나와 결합합니다.
ABC + ABC = BC(A + A) = BC.
ABC + ABC = AC(B + B) = AC.
ABC + ABC = AB(C + C) = AB.

F = AB + AC + BC. 세 입력 중 둘 이상이 1일 때 1이 됩니다. 다수결 회로입니다. 뒤에서 보겠지만 전가산기의 캐리 출력이기도 합니다.

예제 4: 합에 대한 분배 법칙. F = (A + B)(A + C)를 간소화하세요.

전개합니다: AA + AC + AB + BC = A + AC + AB + BC.
A로 묶습니다: A(1 + C + B) + BC.
영 법칙: 1 + C + B = 1이므로 A + BC가 남습니다.

합에 대한 분배 공리를 거꾸로 읽은 것과 정확히 같습니다.

흔한 실수

연산을 바꾸지 않고 드 모르간의 정리를 적용하는 것: AB는 AB가 아니라 A + B입니다.
일반 대수에서처럼 항을 "소거"하는 것. 부울 대수에는 뺄셈도 나눗셈도 없습니다. A + B = A + C라고 해서 B = C가 되는 것은 아닙니다.
우선순위를 잊는 것: A + BC는 (A + B)C가 아닙니다.
긴 막대의 일부만 끊는 것. AB + C의 막대는 합 전체에 걸려 있습니다. 가장 바깥쪽 막대에서 안쪽으로 작업하세요.
너무 일찍 멈추는 것. 각 단계가 끝날 때마다 흡수할 수 있는 항이나 불필요한 합의항이 남아 있지 않은지 확인하세요.

시뮬레이터에서 해 보기

올바르게 간소화했다면 원래 회로와 진리표가 정확히 같은 회로가 나옵니다. 시뮬레이터를 쓰면 표를 손으로 만들지 않고도 이를 확인할 수 있습니다.

편집기에서 AB + AB + AB 같은 예제의 원래 회로를 입력, 출력과 함께 만듭니다.
진리표를 생성해 적어 둡니다.
같은 캔버스의 다른 출력에, 같은 입력을 사용해 간소화한 회로(A + B)를 만듭니다.
입력을 모든 조합으로 바꿔 가며 두 출력이 항상 일치하는지 관찰합니다.
진리표로부터 간소화된 식을 구하게 한 뒤 손으로 구한 식과 비교합니다.

연습문제

F = AB + AB + AB를 간소화하세요.
정답
AB + AB = A. 이어서 A + AB = A + B(보수 흡수 법칙). F = A + B = AB: NAND입니다.
F = A + B를 간소화하세요.
정답
드 모르간의 정리: A · B = AB.
F = A(A + B) + B(B + C)를 간소화하세요.
정답
흡수 법칙에 따라 A(A + B) = A이고 B(B + C) = B입니다. F = A + B.
합의 정리 AB + AC + BC = AB + AC를 증명하세요.
정답
BC = BC(A + A) = ABC + ABC로 씁니다. 그러면 AB + ABC = AB(흡수 법칙)이고 AC + ABC = AC(흡수 법칙)입니다. AB + AC가 남습니다.