부울 대수와 논리 회로

명제와 논리 연산에서 "로그인했고, 관리자이거나 작성자이다"를 $L\land(A\lor W)$로 적었습니다. 참을 1, 거짓을 0으로 바꾸어 적으면 이 식은 0과 1에 대한 계산이 되고, 전기 신호가 있으면 1, 없으면 0인 회로로 그대로 옮길 수 있습니다. 1854년 George Boole이 논리를 대수로 다루는 방법을 내놓았고, 1937년 Claude Shannon이 이것이 스위치 회로의 설계에 쓰일 수 있음을 보였습니다. 이 글에서는 이 대수의 법칙과, 진리표에서 식과 회로를 만드는 방법을 다룹니다.

0과 1의 연산

부울 대수(Boolean algebra)에서는 값이 0과 1뿐이고, AND를 곱 $xy$로, OR를 합 $x+y$로, NOT을 보수 $\bar x$로 적습니다. 곱은 두 값이 모두 1일 때만 1이고, 합은 하나라도 1이면 1이며, 보수는 값을 뒤집습니다. 같은 기호를 쓰지만 수의 연산과 다른 점이 있습니다. 1 + 1은 2가 아니라 1이고, 그래서 $x+x=x$이며 $x+1=1$입니다.

교환법칙과 결합법칙, 두 번 뒤집으면 제자리인 $\bar{\bar x}=x$도 성립합니다. 곱이 합에 대해 분배되는 것은 수와 같지만, 합이 곱에 대해 분배되는 $x+yz=(x+y)(x+z)$는 수에서는 성립하지 않는 법칙입니다. 변수가 n개인 법칙은 $2^n$가지 입력을 모두 넣어 양쪽의 값을 비교하면 증명됩니다. 값이 0과 1뿐이라서 가능한 일입니다.

from itertools import product


def equivalent(f, g, n):
    return all(f(*v) == g(*v) for v in product((0, 1), repeat=n))


def nand(x, y):
    return 1 - (x & y)


laws = [
    ("x + xy = x", lambda x, y: x | (x & y), lambda x, y: x, 2),
    ("x(x + y) = x", lambda x, y: x & (x | y), lambda x, y: x, 2),
    ("(xy)' = x' + y'", lambda x, y: 1 - (x & y), lambda x, y: (1 - x) | (1 - y), 2),
    ("x + yz = (x + y)(x + z)", lambda x, y, z: x | (y & z), lambda x, y, z: (x | y) & (x | z), 3),
    ("x(y + z) = xy + z", lambda x, y, z: x & (y | z), lambda x, y, z: (x & y) | z, 3),
    ("nand(x', y') = x + y", lambda x, y: nand(nand(x, x), nand(y, y)), lambda x, y: x | y, 2),
]
for name, left, right, n in laws:
    print(f"{name:25}", equivalent(left, right, n))


def sop(f, names):
    terms = []
    for values in product((0, 1), repeat=len(names)):
        if f(*values):
            terms.append("".join(v if bit else v + "'" for v, bit in zip(names, values)))
    return " + ".join(terms)


def majority(x, y, z):
    return int(x + y + z >= 2)


print(sop(majority, "xyz"))
print(equivalent(majority, lambda x, y, z: (x & y) | (y & z) | (x & z), 3))

x + xy = x                True
x(x + y) = x              True
(xy)' = x' + y'           True
x + yz = (x + y)(x + z)   True
x(y + z) = xy + z         False
nand(x', y') = x + y      True
x'yz + xy'z + xyz' + xyz
True

코드에서는 0과 1을 정수로 두고 &를 AND, |를 OR, 1 - x를 NOT으로 썼으며, 출력의 x'는 $\bar x$를 글자로 적은 것입니다. equivalent는 product((0, 1), repeat=n)으로 n개 변수의 모든 입력을 만들어 두 함수를 비교합니다. 다섯째 줄의 $x(y+z)=xy+z$는 괄호를 잘못 푼 식이라 False가 나왔고, 실제로 x = 0, z = 1에서 왼쪽은 0, 오른쪽은 1입니다.

법칙을 진리표 대신 다른 법칙으로 이끌어 낼 수도 있습니다. 흡수법칙은 $x+xy=x\cdot1+xy=x(1+y)=x\cdot1=x$로 보이고, $xy+x\bar y=x(y+\bar y)=x\cdot1=x$처럼 한 변수만 다른 두 곱을 합치면 그 변수가 사라집니다. 이 마지막 계산은 카르노 맵에서 이웃한 칸을 묶는 원리가 됩니다.

쌍대성

표에서 합의 꼴과 곱의 꼴은 서로 짝을 이룹니다. 어떤 식에서 합과 곱을 서로 바꾸고 0과 1을 서로 바꾼 식을 쌍대(dual)라고 하는데, 부울 대수의 법칙은 언제나 쌍대도 법칙입니다. 법칙을 이끌어 내는 바탕인 기본 법칙들이 모두 쌍대끼리 짝을 지어 있으므로, 한 법칙의 증명에서 쓴 기본 법칙을 모두 쌍대로 바꾸면 쌍대 법칙의 증명이 되기 때문입니다. 그래서 흡수법칙 $x+xy=x$를 증명하면 $x(x+y)=x$는 따로 증명하지 않아도 됩니다.

쌍대를 만들 때 변수와 보수 기호는 그대로 둡니다. 쌍대는 식을 바꾸는 규칙이지, 원래 식과 쌍대 식이 같은 함수라는 뜻은 아닙니다. 예를 들어 $x+y$의 쌍대는 $xy$이고, 두 식은 x = 1, y = 0에서 값이 다릅니다. 이 점에서 모든 변수를 뒤집고 전체를 뒤집어 같은 함수를 얻는 드모르간 법칙과 구별해야 합니다.

진리표에서 식을 만든다

모든 변수가 한 번씩, 원래 모양이나 보수로 들어간 곱을 최소항(minterm)이라고 합니다. 최소항은 진리표의 한 행에서만 1이 됩니다. 변수 x, y, z에 대한 최소항 $\bar x yz$는 x = 0, y = 1, z = 1인 행에서만 1입니다. 그래서 출력이 1인 행마다 최소항을 하나씩 만들어 모두 더하면 그 진리표를 그대로 나타내는 식이 되고, 이런 꼴을 곱의 합(sum of products, SOP)이라고 합니다.

앞의 코드에서 majority는 세 입력 가운데 둘 이상이 1이면 1인 다수결 함수입니다. 출력이 1인 행은 011, 101, 110, 111이므로 sop는 최소항 네 개의 합을 만들었습니다. 이 식은 법칙으로 $xy+yz+xz$까지 줄일 수 있고, 마지막 줄에서 두 식이 같은 함수임을 확인했습니다. 반대로 출력이 0인 행마다 그 행에서만 0이 되는 합, 곧 최대항(maxterm)을 만들어 모두 곱하면 합의 곱(product of sums, POS) 꼴이 됩니다.

이 방법은 어떤 진리표에도 쓸 수 있으므로, 모든 논리 함수는 AND, OR, NOT만으로 적을 수 있습니다. 출력이 모두 0인 함수도 $x\bar x$로 적으면 됩니다. 이렇게 모든 논리 함수를 만들 수 있는 연산의 모음을 함수적으로 완전(functionally complete)하다고 합니다.

더 깊이: 논리 함수의 수와 AND, OR만으로 부족한 이유

변수가 n개인 논리 함수는 진리표의 $2^n$개 행마다 출력을 0이나 1로 정한 것이므로 모두 $2^{2^n}$개입니다. 변수가 둘이면 16개, 셋이면 256개, 넷이면 65,536개로, 행의 수가 지수로 늘고 함수의 수는 그 지수만큼 다시 늘어납니다. 그래서 변수가 조금만 많아져도 모든 함수를 하나씩 따져 보는 것은 불가능하고, 앞에서처럼 어떤 진리표에도 쓸 수 있는 일반적인 방법이 필요합니다.

AND와 OR만으로는, 상수 0과 1을 더해도, 함수적으로 완전하지 않습니다. 입력 가운데 0이었던 것을 1로 바꾸기만 할 때 출력이 1에서 0으로 내려가지 않는 함수를 단조(monotone) 함수라고 하는데, 변수와 상수는 단조이고, 단조 함수 두 개를 AND나 OR로 묶은 결과도 단조입니다. 식을 만드는 단계마다 이 성질이 이어지므로, AND와 OR로 만든 식은 모두 단조 함수를 나타냅니다. 그런데 NOT은 입력을 0에서 1로 올리면 출력이 1에서 0으로 내려가 단조가 아니므로, 어떻게 조합해도 만들 수 없습니다.

게이트와 NAND의 완전성

AND, OR, NOT 같은 연산을 하는 회로 부품을 논리 게이트(logic gate)라고 합니다. 자주 쓰는 게이트로는 AND의 결과를 뒤집는 NAND, OR의 결과를 뒤집는 NOR, 두 입력이 다를 때만 1인 XOR가 더 있습니다.

NAND 하나만으로도 함수적으로 완전합니다. 같은 입력을 두 번 넣으면 $\overline{xx}=\bar x$라 NOT이 되고, NAND의 결과를 다시 NOT으로 뒤집으면 AND가 됩니다. OR는 드모르간 법칙에 따라 $x+y=\overline{\bar x\,\bar y}$이므로, 두 입력을 각각 뒤집은 뒤 NAND에 넣으면 됩니다. 코드의 마지막 법칙이 이것을 확인한 것입니다. AND, OR, NOT을 모두 만들 수 있으므로 SOP로 적을 수 있는 모든 함수를 NAND만으로 만들 수 있고, 실제 칩에서 NAND가 기본 부품으로 많이 쓰이는 이유이기도 합니다.

식을 회로로 옮기면 괄호가 게이트의 연결 순서가 됩니다. $F=L(A+W)$는 A와 W를 OR 게이트에 넣고, 그 출력과 L을 AND 게이트에 넣는 회로입니다. L = 0, A = 0, W = 1이면 OR의 출력은 1이지만 AND의 출력은 0이라 F = 0입니다. 게이트로 회로를 만들고 신호를 추적하는 방법은 컴퓨터 구조 교재에서 더 자세히 다룹니다.

정리

• 부울 대수에서 곱은 AND, 합은 OR, 보수는 NOT이며, 1 + 1 = 1이라 $x+x=x$, $x+1=1$이 성립합니다.
• 합이 곱에 대해 분배되는 $x+yz=(x+y)(x+z)$처럼 수와 다른 법칙이 있고, 모든 법칙은 $2^n$가지 입력을 비교해 증명할 수 있습니다.
• 합과 곱, 0과 1을 바꾼 쌍대 식도 법칙이 되지만, 쌍대 식이 원래 식과 같은 함수라는 뜻은 아닙니다.
• 출력이 1인 행의 최소항을 모두 더하면 곱의 합, 출력이 0인 행의 최대항을 모두 곱하면 합의 곱 꼴이 됩니다.
• AND, OR, NOT은 함수적으로 완전하며, NAND 하나만으로도 세 연산을 모두 만들 수 있습니다.

연습 문제

1. 식 줄이기

$xy+\bar xy$를 줄이고, 네 가지 입력에서 줄인 식과 값이 같은지 확인하세요.

2. XOR를 곱의 합으로

XOR를 AND, OR, NOT만으로 적으세요.

3. NOR의 완전성

NOR 하나만으로 NOT, OR, AND를 만드세요.

1 + 1의 값이 헷갈리면 그 +가 수의 덧셈인지 OR인지부터 적어 두세요. 다음 글인 선택 심화 카르노 맵으로 식 줄이기에서는 곱의 합 식을 그림으로 묶어 짧게 만드는 방법을 다룹니다.