부울대수와 카르노 맵

안전 회로의 식이 AB + A¬B라고 합시다. B가 어느 값이든 A가 1일 때 출력이 켜집니다. 식을 줄이면 회로를 이해하고 검증하기 쉬워집니다. 단순히 짧아 보이는 식으로 바꾸는 것이 아니라 모든 입력에서 같은 출력을 유지해야 합니다.

기호와 법칙

이 절의 곱 AB는 AND, 더하기 A+B는 OR, ¬A는 NOT입니다. 일반 수의 산술과 기호가 같아도 법칙은 다릅니다. A+A=A, A·A=A, A+¬A=1, A·¬A=0입니다. 따라서 AB+A¬B = A(B+¬B) = A입니다.

드모르간 법칙은 ¬(AB)=¬A+¬B, ¬(A+B)=¬A¬B입니다. 식 전체를 반전할 때 AND·OR를 바꾸고 각 입력도 반전합니다. ¬(AB)를 ¬A¬B로 바꾸면 입력 01에서 출력이 달라집니다.

흡수 법칙 A+AB=A는 A가 이미 참이면 B가 무엇이든 OR 결과가 참이라는 뜻입니다. 식 변형 뒤에는 진리표로 확인하면 반례를 찾기 쉽습니다.

카르노 맵의 인접성이 뜻하는 것

카르노 맵(K-map)은 진리표를 한 비트만 다른 입력끼리 이웃하도록 재배치합니다. 3변수 맵에서 BC 열 순서는 00, 01, 11, 10입니다. 십진 순서 00,01,10,11로 쓰면 인접 규칙을 잃습니다.

오른쪽 2열의 네 1을 하나의 2×2 묶음으로 잡습니다. 이 묶음에서는 A와 C가 모두 바뀌고 B만 1로 유지됩니다. 따라서 출력은 B입니다. 묶음 크기는 1·2·4·8처럼 2의 거듭제곱이고 직사각형이어야 합니다. 맵 양 끝은 이어져 있어 가장자리끼리 묶을 수 있습니다. 겹치는 묶음도 허용되며 모든 1을 포함해야 합니다.

무관 조건(don't care)은 그 입력 조합이 발생하지 않거나 출력이 규정되지 않은 경우입니다. 원하는 만큼 0·1로 이용할 수 있지만, 실제 발생하는 입력을 임의로 무관 조건으로 바꿔서는 안 됩니다.

경계 연결과 여러 묶음을 직접 만들기

한 묶음만으로 모든 1을 덮을 수 없는 경우를 봅니다. 다음 표는 A·B·C를 왼쪽부터 쓴 입력이 000,010,101,111일 때만 F=1인 함수입니다. 열의 순서는 앞과 같은 Gray 순서입니다.

1. A=0 행의 첫 열 00과 마지막 열 10을 묶습니다. 경계가 이어지므로 이 두 칸은 이웃입니다. B만 0→1로 바뀌고 A=0·C=0은 고정돼, 이 묶음의 항은 ¬A¬C입니다.
2. A=1 행의 01·11을 묶습니다. 여기서도 B만 바뀌며 A=1·C=1이 고정되므로 항은 AC입니다.
3. 두 묶음을 OR로 합치면 F=¬A¬C+AC입니다. 고정된 A·C가 서로 같을 때만 1이며 B는 출력에 영향을 주지 않습니다.

대각선의 1 두 칸을 붙이거나 중간의 0까지 포함해 네 칸을 묶으면 안 됩니다. 각 묶음은 1만 포함하는 이웃 직사각형이어야 하며, 무관 조건이 따로 주어진 경우에만 그 칸을 이용할 수 있습니다. 이 예제에는 무관 조건이 없습니다. A·C=00,01,10,11에서 각각 F=1,0,0,1이고 각 경우에 B=0·1 모두 같은 결과이므로 원래 여덟 입력과 일치합니다.

줄인 식을 실행으로 검증하기

from itertools import product

for a, b, c in product((0, 1), repeat=3):
    original = ((not a) and b and (not c)) or ((not a) and b and c) or (a and b and c) or (a and b and (not c))
    simplified = bool(b)
    assert bool(original) == simplified
    assert (not (a and b)) == ((not a) or (not b))

product는 가능한 입력 조합을 나열합니다. 이 검사는 샘플 하나가 아니라 세 입력의 8조합을 모두 확인합니다. 회로 지연이나 소비 전력까지 확인하는 검사는 아닙니다.

독립 문제: 두 식 중 어느 것이 등가인가

F = ¬A B + AB를 간소화하고, 두 입력의 진리표로 확인하세요. G=¬(A+B)에 대해 후보 ¬A+¬B와 ¬A¬B 중 올바른 식을 고르되 틀린 후보의 반례도 쓰세요.

힌트

F에서 B를 묶으세요. G는 A·B가 모두 0일 때만 1입니다.

풀이

F=B(¬A+A)=B입니다. 입력 00·01·10·11에서 출력은 0·1·0·1입니다. G의 올바른 식은 ¬A¬B입니다. A=0,B=1에서 G=0이지만 ¬A+¬B=1이므로 첫 후보는 틀립니다.

독립 문제: 반대 위치의 두 묶음

이번에는 입력 001,011,100,110에서만 출력 G=1입니다. A 행·BC 열의 같은 3변수 맵에 값을 채우고, 경계 연결을 포함한 두 묶음을 만드세요. 각 묶음에서 바뀌는 변수와 남는 변수를 적고 간소화한 식을 구하세요. 입력 000과 101에서 출력이 0인지도 확인하세요.

맵 문제 힌트

A=0 행에서는 C=1인 두 칸, A=1 행에서는 C=0인 두 칸이 1입니다. 첫 열과 마지막 열의 B 값 차이는 한 비트입니다.

맵 문제 풀이

맵의 A=0 행은 0,1,1,0, A=1 행은 1,0,0,1입니다. 첫 묶음은 A=0 행의 01·11이므로 B를 제거한 ¬AC, 두 번째는 A=1 행의 양 끝 00·10이므로 A¬C입니다. 따라서 G=¬AC+A¬C, 즉 A와 C의 XOR입니다. B의 두 값 모두 같은 결과를 내며, 입력 000에서는 A=C=0, 101에서는 A=C=1이라 G=0입니다. F 예제의 식을 그대로 쓰면 이 두 입력에서 1이 되어 반례가 됩니다.

게이트 수가 적다고 실제 회로의 지연까지 항상 최적이라는 뜻은 아닙니다. 입력 도착 시점·게이트 종류·배선도 영향을 줍니다. 다음 조합회로에서는 등가성이 검증된 식을 계산·선택 회로에 연결합니다.