불 대수(Boolean algebra)

불 대수는 참과 거짓을 1과 0으로 적고, '그리고'(AND, $\land$), '또는'(OR, $\lor$), '아니다'(NOT, $\lnot$)를 곱셈과 덧셈처럼 계산하는 대수입니다. 조지 불이 『논리의 수학적 분석』(1847)과 『사고의 법칙』(1854)에서 논리적 추론을 방정식처럼 다루자고 제안한 데서 시작했습니다. 변수가 0과 1 두 값만 가지므로 어떤 식이든 가능한 입력을 모두 넣어 보는 표 한 장으로 끝까지 확인할 수 있습니다. 이 표가 진리표입니다. 입력이 n개면 진리표는 $2^n$줄이고, n개의 입력을 받아 0이나 1을 내는 함수⁠(function)⁠는 모두 $2^{2^n}$가지입니다. 입력이 둘이면 16가지입니다.

원소⁠(element)⁠ 하나를 정해 두고 '그 원소가 A에 속한다'를 참·거짓으로 읽으면 $\land$는 교집합⁠(intersection)⁠, $\lor$는 합집합⁠(union)⁠, $\lnot$은 여집합⁠(complement)⁠이 됩니다(집합의 연산⁠(set operations)⁠). 한 집합⁠(set)⁠의 모든 부분집합⁠(subset)⁠, 곧 멱집합⁠(power set)⁠이 불 대수를 이루는 까닭이고, 확률⁠(probability)⁠에서 사건⁠(event)⁠을 '그리고·또는·아니다'로 묶는 계산도 같은 대수입니다. 벤 다이어그램(집합을 겹쳐 그린 원으로 나타낸 그림)으로 확인하던 법칙은 모두 진리표로 확인됩니다. 대표가 19세기 영국 수학자 오거스터스 드모르간의 이름을 딴 드모르간 법칙⁠(De Morgan's laws)⁠ $\lnot(A \land B) = \lnot A \lor \lnot B$입니다. 말로 하면 "'A이고 B'가 아니다"는 "A가 아니거나 B가 아니다"와 같다는 뜻입니다. '비가 오고 춥다'가 거짓이라면, 비가 안 오거나 춥지 않거나 둘 중 적어도 하나입니다. 아래 표의 청록색 두 열은 모든 줄에서 똑같습니다.

1937년 섀넌은 석사 논문에서 스위치로 만든 회로를 불 대수로 설계하고 단순하게 만들 수 있음을 보였습니다. 스위치 두 개를 한 줄로 이으면 둘 다 닫혀야 전류가 흐르니 AND이고, 나란히 이으면 하나만 닫혀도 흐르니 OR입니다. 이렇게 AND·OR·NOT 같은 연산 하나를 해내는 작은 회로를 논리 게이트라고 합니다. 오늘날 칩 안에 있는 수십억 개의 트랜지스터(전기 신호로 여닫는 아주 작은 스위치)도 결국 이런 게이트를 이룹니다. 한 자리 이진수 두 개를 더하는 반가산기⁠(half adder)⁠는 게이트 두 개로 됩니다. 합의 자리는 $S = A \oplus B$(배타적 논리합⁠(exclusive or)⁠, XOR: 두 입력 가운데 정확히 하나만 1일 때 1), 올림은 $C = A \land B$입니다. 지금 A = , B = 이면 S = , C = , 곧 입니다.

XOR은 2를 법으로 하는 덧셈입니다. 1 ⊕ 1 = 0이고, 넘친 1은 올림으로 넘어갑니다. 반가산기 둘과 OR 하나로 올림까지 받는 전가산기⁠(full adder)⁠를 만들고, 이를 줄줄이 이으면 여러 자리 이진수의 덧셈기가 됩니다. 여러 비트를 XOR로 이어 붙이면 1의 개수가 홀수일 때 1, 짝수일 때 0이 나옵니다. 이 값을 함께 보내 두면 비트 하나가 뒤집혔을 때(더 일반적으로는 홀수 개가 뒤집혔을 때) 알아챌 수 있는데, 이것이 패리티 검사⁠(parity check)⁠이고, 해밍 부호⁠(Hamming code)⁠는 이런 검사 여러 개를 겹쳐 뒤집힌 자리까지 찾아냅니다. NAND(AND의 부정) 하나만 있어도 NOT, AND, OR을 모두 만들 수 있어서, 이론상 모든 회로를 한 종류의 게이트로 지을 수 있습니다.

이어지는 곳. 식을 참으로 만드는 입력이 있는지 묻는 충족 가능성 문제(SAT)는 진리표 $2^n$줄을 다 보면 풀립니다. 입력 크기의 다항식⁠(polynomial)⁠만큼의 걸음으로 푸는 방법이 있느냐는 물음은 P 대 NP 문제⁠(P versus NP problem)⁠와 같은 물음입니다. SAT가 NP 완전⁠(NP-complete)⁠이기 때문입니다. 게이트만 이은 회로는 기억이 없습니다. 출력을 입력으로 되먹여 상태를 기억하게 하면 유한 오토마톤⁠(finite automaton)⁠이 되고, 끝없는 테이프를 붙이면 튜링 기계⁠(Turing machine)⁠가 됩니다. 함수만으로 계산을 적는 람다 계산⁠(lambda calculus)⁠에서는 참과 거짓조차 '둘 중 하나를 고르는 함수'로 정의하고, 그 위에 불 대수 전체를 다시 짓습니다. 입력에 가중치⁠(weight)⁠를 곱해 더한 값이 문턱⁠(threshold)⁠을 넘는지로 1과 0을 내는 퍼셉트론⁠(perceptron)⁠ 하나는 AND·OR·NOT을 흉내 낼 수 있지만 XOR는 흉내 낼 수 없습니다. 퍼셉트론은 입력 평면을 직선 하나로 둘로 가를 뿐인데, XOR에서 1이 나오는 입력 (0, 1), (1, 0)과 0이 나오는 입력 (0, 0), (1, 1)은 어떤 직선으로도 가를 수 없기 때문입니다. 참·거짓인 문장을 AND·OR·NOT으로 엮는 논리를 명제 논리라 하는데, 이것은 불 대수 그 자체라서 진리표로 늘 참인 식을 모두 기계적으로 가려낼 수 있습니다. '참'을 '증명이 있다'로 읽는 직관주의 논리⁠(intuitionistic logic)⁠에서는 배중률⁠(law of excluded middle)⁠ A ∨ ¬A가 늘 참이지는 않아서, 불 대수 대신 그보다 약한 헤이팅 대수⁠(Heyting algebra)⁠가 명제들의 구조가 됩니다. 부분집합이 불 대수를 이루는 것은 부분집합 하나가 '원소마다 참·거짓을 답하는 함수' 하나와 일대일로 대응하기 때문입니다. 이 두 값짜리 진릿값⁠(truth value)⁠을 더 풍부한 진릿값의 대상으로 바꾼 세계가 토포스⁠(topos)⁠이고, 그 안의 부분 대상⁠(subobject)⁠들은 일반적으로 헤이팅 대수를 이룹니다. 두 구조 모두에서 '그리고'와 '이면'은 짝을 이룹니다. 불 대수라면 $a \land b \le c$와 $a \le \lnot b \lor c$가 같은 말이어서, b를 부등식의 왼쪽에서 오른쪽으로 옮길 수 있습니다. 이렇게 두 연산이 부등식을 사이에 두고 자리를 맞바꾸는 짝을 갈루아 연결⁠(Galois connection)⁠이라 합니다. 그러나 '모든 자연수⁠(natural number)⁠에 대해'라고 말하는 자연수의 산술로 올라가면 사정이 다릅니다. 참인 문장을 모두, 그리고 참인 문장만 증명해 내는 기계적인 체계는 없습니다. 이것이 괴델의 불완전성 정리⁠(Gödel's incompleteness theorems)⁠입니다.