배타적 논리합(Exclusive or)

계단 아래와 위에 스위치가 하나씩 있고 전등은 하나인 집을 떠올려 봅시다. 어느 스위치를 눌러도 전등의 상태가 바뀝니다. 스위치의 두 위치를 0과 1로 적고 둘 다 0일 때 전등이 꺼지도록 배선했다면, 전등은 두 스위치의 위치가 서로 다를 때만 켜집니다. 이 규칙이 배타적 논리합이고, 영어 약자로 XOR, 기호로는 ⊕(동그라미 안의 더하기)를 씁니다. 네 경우를 모두 적으면 이렇습니다.

$$\begin{array}{cc|c|c} a & b & a \oplus b & a \lor b \\ \hline 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \end{array}$$

셋째 칸이 XOR이고, 넷째 칸은 비교를 위한 보통의 논리합 OR(기호 ∨)입니다. 둘은 마지막 줄 하나만 다릅니다. OR은 '하나라도 1이면 1'이고, XOR은 '정확히 하나만 1이면 1', 곧 둘 다 1인 경우를 빼는(배타적인) 합입니다. 짧게 말하면 XOR은 같으면 0, 다르면 1입니다. 이런 표를 진리표라 하고, 참과 거짓을 1과 0으로 두고 AND·OR·NOT으로 계산하는 체계가 불 대수⁠(Boolean algebra)⁠입니다. AND를 ∧, NOT을 ¬로 적으면 XOR은 $a \oplus b = (a \lor b) \land \lnot(a \land b)$, 곧 'OR이면서 둘 다는 아님'입니다.

수를 이진법⁠(binary)⁠으로 적으면 XOR을 자리마다 따로 할 수 있습니다. 컴퓨터의 비트 연산⁠(bitwise operation)⁠ XOR이 이것입니다.

$$\begin{array}{r} 1011 \\ \oplus\ 0110 \\ \hline 1101 \end{array}$$

오른쪽 자리부터 1 ⊕ 0 = 1, 1 ⊕ 1 = 0, 0 ⊕ 1 = 1, 1 ⊕ 0 = 1입니다. 받아올림을 버린 덧셈과 같습니다. 1 + 1 = 2를 2로 나눈 나머지⁠(remainder)⁠는 0이니, XOR은 2를 법으로 하는 덧셈입니다. 그래서 덧셈의 성질이 그대로 따라옵니다. 순서를 바꿔도($a \oplus b = b \oplus a$), 묶는 방법을 바꿔도 결과가 같고, 0과 XOR하면 그대로입니다($a \oplus 0 = a$). 여기에 덧셈에 없는 성질이 하나 더 있습니다. 자기 자신과 XOR하면 0입니다($a \oplus a = 0$). 모든 원소⁠(element)⁠가 자기 자신의 역원⁠(inverse element)⁠인 셈이고, 0과 1이 XOR로 이루는 구조는 원소가 둘뿐인 군입니다.

이 마지막 성질에서 '두 번 하면 되돌아온다'가 나옵니다. $(a \oplus k) \oplus k = a \oplus (k \oplus k) = a \oplus 0 = a$입니다. 위의 예로 보면 1011에 0110을 XOR해 1101을 얻었고, 1101에 다시 0110을 XOR하면 1011로 돌아옵니다. 1917년 AT&T의 기술자 길버트 버냄은 이 성질로 전신 암호 기계를 만들었습니다. 보낼 비트(평문⁠, plaintext⁠)에 열쇠 테이프의 비트를 XOR해 보내고, 받는 쪽은 같은 열쇠를 한 번 더 XOR해 평문을 되찾습니다. 미 육군의 조지프 모보인은 열쇠를 완전히 무작위로 만들고 한 번만 쓰자는 조건을 덧붙였고, 이것이 일회용 난수표입니다.

1949년 섀넌은 일회용 난수표⁠(one-time pad)⁠가 완벽하게 안전하다는 것, 곧 암호문⁠(ciphertext)⁠을 보아도 평문에 대해 아무것도 알 수 없다는 것을 증명했습니다. 까닭은 XOR의 성질 그대로입니다. 가로챈 암호문이 c일 때, 어떤 평문 p든 열쇠가 $p \oplus c$였다면 c가 나옵니다. 열쇠가 무작위이면 그 열쇠들은 모두 같은 확률⁠(probability)⁠이니, c는 어느 평문 쪽으로도 기울지 않습니다. 규칙을 어기면 같은 성질이 약점이 됩니다. 두 평문 $p_1, p_2$를 같은 열쇠 k로 보내면, 두 암호문을 XOR하는 것만으로 열쇠가 지워집니다.

$$(p_1 \oplus k) \oplus (p_2 \oplus k) = p_1 \oplus p_2$$

남은 것은 두 평문의 XOR뿐이고, 말이 되는 문장 둘을 맞춰 보며 풀어 나갈 수 있습니다. 1941년 8월 한 독일 운영자가 긴 전문을 같은 열쇠로 조금 바꾸어 다시 보냈을 때, 영국의 암호 해독가 존 틸트먼이 두 전문에서 평문과 열쇠를 뽑아낸 것이 이런 경우입니다.

여러 비트를 차례로 XOR하면 1의 개수가 홀수일 때 1, 짝수일 때 0이 나옵니다. 1 ⊕ 1 = 0이라 1이 둘씩 지워지기 때문입니다. 이 값(패리티 비트⁠, parity bit⁠)을 함께 보내면, 오는 도중 비트 하나가 뒤집혔을 때 받은 비트 전체의 XOR이 0이 아니게 되어 알아챌 수 있습니다. 리처드 해밍이 1950년 발표한 해밍 부호⁠(Hamming code)⁠는 이런 검사를 여러 개 겹쳐 뒤집힌 자리까지 찾아냅니다(오류 정정 부호⁠(error-correcting code)⁠). 7비트 해밍 부호에서는 1이 있는 자리의 번호들을 이진수로 적어 모두 XOR하면 됩니다. 올바른 부호어⁠(codeword)⁠ 0110011에서 1이 있는 자리는 2, 3, 6, 7이고 $010 \oplus 011 \oplus 110 \oplus 111 = 000$입니다. 다섯째 비트가 뒤집혀 0110111이 오면 101이 더해지므로 결과는 101, 곧 5가 되어 뒤집힌 자리를 가리킵니다.

XOR은 신경망⁠(neural network)⁠의 역사에서도 이정표입니다. 입력에 가중치⁠(weight)⁠를 곱해 더한 값이 문턱⁠(threshold)⁠ θ(세타) 이상이면 1을 내는 퍼셉트론⁠(perceptron)⁠ 하나는 AND와 OR은 흉내 내지만 XOR은 흉내 내지 못합니다. 가중치를 $w_1, w_2$라 하면 네 입력 (0, 0), (1, 0), (0, 1), (1, 1)에 대해 차례로 $0 \lt \theta$, $w_1 \ge \theta$, $w_2 \ge \theta$, $w_1 + w_2 \lt \theta$가 모두 성립해야 합니다. 가운데 둘을 더하면 $w_1 + w_2 \ge 2\theta$이고, θ가 양수라 $2\theta \gt \theta$이니 넷째 조건과 부딪힙니다. 그림으로 보면 1을 내야 하는 (1, 0), (0, 1)과 0을 내야 하는 (0, 0), (1, 1)이 정사각형의 두 대각선에 엇갈려 있어서, 직선 하나로는 둘을 가를 수 없습니다.

1969년 마빈 민스키와 시모어 패퍼트는 책 『퍼셉트론』에서 이런 한계를 훨씬 일반적인 형태로 다루었습니다. 해법은 층을 쌓는 것입니다. XOR은 'OR이면서 NAND(AND의 부정)'이니, OR 뉴런과 NAND 뉴런의 출력을 AND 뉴런에 넣으면 됩니다. 남은 문제는 그렇게 쌓은 여러 층의 가중치를 예에서 배우게 하는 방법이었고, 그 답이 역전파⁠(backpropagation)⁠입니다.

이어지는 곳. AND·OR·NOT과 진리표⁠(truth table)⁠, XOR과 AND로 만드는 반가산기⁠(half adder)⁠는 불 대수에, 2로 나눈 나머지의 덧셈은 모듈러 연산⁠(modular arithmetic)⁠에 있습니다. 두 비트열을 XOR해 1의 개수를 세면 해밍 거리⁠(Hamming distance)⁠가 되고, 검사 비트⁠(check bit)⁠로 오류를 고치는 방법은 오류 정정 부호가 이어 갑니다. 돌무더기의 크기를 이진법으로 적어 XOR한 값으로 이기는 수를 찾는 게임은 님입니다. 직선 하나의 한계는 퍼셉트론과 신경망에서 이어집니다. XOR과 인공지능⁠(artificial intelligence)⁠의 겨울은 「배우는 기계」 3절이, 덧셈을 AND와 XOR로 바꾸는 회로는 「기계가 풀 수 없는 문제」 1절이, 버냄의 기계와 일회용 난수표는 「나머지로 지키는 비밀」 7절이, 해밍 부호의 검사 비트는 「짧게 보내기」 7절이 보여 줍니다.