컴퓨터란 논리 연산 밖에 하지 못하는 기계에 불과합니다. 그런데 어떻게 사칙연산 같은 일을 할 수 있는 것일까요?

컴퓨터를 구성하는 기본적인 요소로 논리 게이트logic gate가 있습니다. 대표적인 예로 AND 게이트는 두 입력이 모두 참일때만 결과를 참으로 내놓습니다. 이것은 논리곱conjunction이라는 논리 연산을 물리적으로 구현한 장치인데요. 컴퓨터란 이런 게이트의 조합으로 이뤄지기 때문에, 곧 논리 연산을 처리하는 기계로 볼 수 있습니다.

한편 이런 장치에서 쓰이는 논리는, 보통 말하는 논리와는 조금 다른 것을 의미하는 것처럼 보입니다. 논리란 어떤 근거 때문에 결론이 옳다는 뜻으로서 쓰일텐데, 그게 이런 기계 부품과 무슨 관련이 있을까요? 정작 논리 게이트는 수학적인 연산을 처리하는 장치로 보입니다.

이렇게 논리학이 수학적인 언어로 표현될 수 있는 것은 우연이 아니라, 오늘날 불 논리Boolean logic라고 불리는 것이 발전된 과정에서 수학의 영역에 들어왔기 때문입니다. 반면 그 이전 시대에서 논리학이란 기원전 아리스토텔레스Aristotle가 정리해놓은 작업을 의미했습니다. 그러면 여기서부터 컴퓨터가 나타나기까지의 역사를 훑어보겠습니다.

기원전 시대의 논리학

아리스토텔레스의 논리학의 중요한 발견은, 타당한valid 주장은 그 내용이 아니라 그 형태 때문이라는 사실이었습니다. 여기서 타당하다는 말은 특별한 의미를 가지는데요. 근거로 쓰인 문장이 맞기만 하면 결론이 틀릴 수가 없다는 뜻입니다.

이런 형태는 삼단논법syllogism이라는 이름을 갖게 되었습니다. 예를 들어, 이런 주장은 삼단논법 중 하나입니다.

• 사람은 죽는다.
• 소크라테스는 사람이다.
• 그러므로 소크라테스는 죽는다.

앞서 언급했듯이 삼단논법은 내용보다 형태가 중요하기 때문에 내용을 걷어내보면 이런 형태만 남습니다.

• 모든 A는 B다.
• C는 A다.
• 그러므로 C는 B다.

아리스토텔레스의 논리학은 이런 삼단논법의 형태를 열 다섯 개 정도로 정리해 둔 것입니다. (개수는 책마다 다르기는 합니다.) 따라서 여기서는 어떤 주장이 그런 삼단논법에 속하는지 분석하는 것이 가장 중요한 일이 됩니다. 내용은 그 다음에 검토해도 늦지 않으니까요.

논리학에서 수학으로

삼단논법은 무엇이 논리적인지 그 기준을 제시해주지만, 각기 다른 형태가 관련 없어 보이기도 합니다. 그런데 불Boole의 작업 덕분에, 논리학은 단순한 수학적인 계산 하나로 정리되었습니다. 하나의 대수 구조algebraic structure로 정리했다는 편이 더 정확할 것입니다. 그래서 불 대수Boolean algebra라고도 부릅니다.

곱셈 같은 것

간단한 수학을 새로 만들어봅시다. $A \otimes B$가 ‘$A$이고 $B$인 것’을 나타낸다고 해봅시다. 그러면 ‘빨간 사과’는 곧 ‘빨간 것 $\otimes$ 사과’가 됩니다.

이렇게 일일이 쓰는 대신 $x \otimes y$라고 합시다. 즉 ‘빨간 것’은 $x$로, ‘사과’는 $y$로 나타낸 것입니다. 이걸 더 줄여서 $xy$로 쓰기로 해봅시다. 마치 곱셈처럼 보이게끔요.

이런 약속으로부터 중요한 특징을 발견할 수 있습니다. 먼저, ‘빨갛고 사과인 것’과 ‘사과이면서 빨간 것’은 같다는 것입니다. 즉 $xy = yx$이므로, 이 연산은 교환법칙commutative law이 성립합니다.

사실 방금 정의한 연산은 논리곱이라고 불리는 연산이지만, 곱셈과 비슷할 것 같다는 인상을 줍니다. 곧 보겠지만, 이런 연산을 실제로 사칙연산이나 다름없게 만들 것입니다.

덧셈 같은 것

이어서, $A \oplus B$가 ‘$A$이거나 $B$인 것’이라고 해봅시다. 즉 ‘빨갛거나 사과인 것’은 $x \oplus y$가 됩니다. 그러면 여기서도 교환법칙이 성립합니다.

또한 결합법칙associative law도 성립합니다. 즉 다음과 같이 어느 부분부터 연산하더라도 똑같은 것을 가리키게 됩니다.

따라서 $x \oplus y \oplus z$ 라고 써도 아무런 애매함이 없게 됩니다. 이는 $\otimes$ 연산도 마찬가지입니다.

마지막으로 분배법칙distributive law 또한 성립합니다. 즉 $x$, $y$, $z$가 무엇을 말하든지 다음 식이 성립한다는 뜻입니다.

방금 보인 세 가지 특징은 사칙연산이 가지는 특징입니다. 다시 말해, 두 논리 연산 $\otimes$, $\oplus$을 마치 사칙연산처럼 다뤄도 좋다는 것을 방금 증명한 것입니다.

사칙연산이 된 논리학

$xx = x$는 항상 성립합니다. ‘빨갛고 빨간 것’이 그냥 ‘빨간 것’과 다르지 않다면요. 이것이 만약 단순한 이차 방정식이었다면, $x$는 $0$이거나 $1$일 것입니다. 그런데 이 결과를 논리학의 영역에서 어떻게 해석할 수 있을까요?

원래의 식은 인수분해를 통해 다음과 같이 고칠 수 있습니다.

여기서 1을 ‘전부’로, 0을 ‘없는 것’으로, 뺄셈을 앞쪽에서 뒷쪽을 제거한 것이라고 해석해봅시다. 그러면, 빨간 것이면서 동시에 빨갛지 않은 것은 없다는 얘기가 됩니다. 이는 긍정과 부정을 동시에 할 수 없다는 모순율law of contradiction과 똑같은 의미를 가집니다.

앞서 언급한 대로 논리 연산을 사칙연산처럼 다뤘지만, 일반적인 수학과 차이점이 있는데요. 어떤 값이든 $0$과 $1$ 중에 하나만 가진다는 점입니다. 불이 해낸 작업은, 아리스토텔레스 논리학의 모든 삼단논법을 $0$과 $1$의 연산으로 유도해낸 것이었습니다.

예를 들어, 이런 삼단논법이 있다고 해봅시다.

• 모든 A는 B이다.
• 모든 B는 C이다.
• 따라서 모든 A는 C이다.

그러면 각각 다음과 같은 식으로 표현할 수 있습니다.

• $a(1-b) = 0$
• $b(1-c) = 0$
• 따라서 $a(1-c) = 0$

결론을 이끌어내는 작업은 쉽기 때문에 직접 해보는 것으로 남기고 생략하겠습니다. (나눗셈은 정의한 적이 없기 때문에 나눗셈 사용만 주의해서 피해야 합니다.)

영향

불은 $0$과 $1$, 그리고 적절한 연산을 통해 논리 법칙을 만들어냈습니다. 논리학에서는 이런 숫자보다는 참true, 거짓false 같은 표현을 대신 사용하기도 하고, 전자공학에서는 이를 전압으로 구현하여 하이high, 로우low로 부르기도 합니다. 무엇이 됐든 두 가지 값을 가지기 때문에 투 밸류 로직two-valued logic으로 불리기도 합니다.

두 개의 값을 쓰지 않는 논리중에는, 대표적으로 데이터베이스를 위한 언어인 SQL이 있습니다. 여기서는 참과 거짓 외에 모름unknown 이라는 값도 더한 쓰리 밸류 로직three-valued logic을 이용합니다. 아니면 퍼지 로직fuzzy logic처럼 $0$과 $1$ 사이의 무한히 많은 숫자를 쓰는 경우도 있는데요. 신경망nueral networks을 이용한 인공지능에서 이를 사용하기도 합니다. 이렇게 다른 종류의 논리 또한 컴퓨터 과학에서 적용되고 있습니다.

앞서 불이 어떻게 삼단논법을 수학으로 가져왔는지 예시를 보였는데요. 오늘날 불의 체계를 그대로 쓰는 일은 드물고, 대신 그것과 유사한 명제 논리학propositional logic이 주로 사용됩니다. 여기에 ‘모든’이나 ‘어떤’ 같은 표현이 필요하다면 수량자quantifier라는 개념을 더할 수 있는데요. 이는 1차 논리학first-order logic이라고 불립니다. 수학에서 명제를 표현할 때 흔히 사용되고, $\forall$과 $\exists$와 같은 기호가 그런 수량자를 나타냅니다.

오직 하나로도 충분한 연산

몇 개의 논리 연산만 있으면 충분할까요? 방금 언급한 명제 논리학에 흥미로우면서도 유용한 정리theorem가 있습니다. 다음과 같이 마음대로 정의한 연산이 있다고 해봅시다.

이걸 기존의 논리 연산을 갖고 만들어낼 수 있을까요? 이뿐만 아니라 다른 어떤 것도 그럴 수 있을까요?

이 질문이 중요한 이유는, 기존의 논리 연산이 모든 경우를 표현할 만큼 충분한 지를 묻기 때문입니다. 그리고 그런 논리 연산들을 묶어 완전complete하다고 부릅니다. 증명은 생략하겠지만, 논리곱과 논리합disjunction, 그리고 부정negation 연산만 있어도 완전하게 됩니다.

사실 오직 하나의 연산도 완전할 수 있는데요. 이는 하나만 갖고도 논리곱과 논리합을 비롯한 모든 종류의 연산을 만들어낼 수 있음을 의미합니다. 그 중에 셰퍼 스트로크Sheffer stroke라고 불리는 연산이 있습니다.

이는 마치 논리곱의 반대 값을 가진 것 같은데요. 이를 물리적으로 구현한 것이 NAND 게이트가 됩니다. 다른 종류 없이 NAND 게이트 하나만으로 컴퓨터의 모든 하드웨어를 만들어낼 수 있는 원리이기도 합니다.

논리학에서 계산기로

불 논리를 이용해 덧셈 기계를 만들려고 합니다. 일단 어떻게 물리적으로 구현할 지는 고민하지 않으려고 합니다. 그냥 전기를 이용해 불 논리를 구현할 수 있다고 칩시다. 사실 클로드 섀넌Claude Shannon이라는 사람이 이미 그런 일을 해놨습니다. 그리고 오늘날 논리 게이트는 모스펫MOSFET이라는 반도체를 통해 물리적으로 구현되어 있습니다.

그러면 계산기는 거의 완성된 거나 다름 없습니다. 간단히 두 숫자를 더한다고 해봅시다. 불 논리를 따라 $0$과 $1$ 만 쓰겠지만, 이진법만으로도 모든 숫자를 표현할 수 있으니 상관없습니다. 그러면 남은 작업은 다음과 같은 연산을 구현하는 것입니다.

이전에 정의했던 연산 $\otimes$, $\oplus$를 이용하면, 여기서 $c$는 마치 $x \otimes y$, $s$는 $x \oplus y$ 처럼 보입니다. 사실 $\otimes$는 논리곱, $\oplus$는 (XOR 연산이라고도 불리는) 배타논리합exclusive disjunction이라고 불리는 것입니다.

따라서 다음과 같은 논리 연산이 덧셈을 하는 것과 다름 없게 됩니다.

이렇게 완성한 덧셈 계산기는 반가산기half adder라고 불리는 회로입니다.

만약 여러 자리 비트의 덧셈을 계산하고 싶다면, 이전 자릿수의 덧셈에서 자리올림한 것, 즉 $c$ 값 또한 고려해야 합니다. 그런 덧셈을 하는 회로는 전가산기full adder라고 불리는데요. 이를 이어 붙여 리플 캐리 가산기ripple-carry adder라고 하는 것을 만들어, 여러 자릿수의 덧셈을 할 수 있게 됩니다. 이는 곧 ALUarithmetic logic unit라고 불리는 회로의 구성 요소가 되고, 이는 다시 프로세서processor라고 불리는 컴퓨터 하드웨어의 핵심적인 구성 요소가 됩니다. (자세한 내용에 흥미가 있다면 컴퓨터 구조를 다루는 자료에서 확인할 수 있습니다.)

정리하면 이렇게 컴퓨터가 오직 논리 연산만으로 덧셈이라는 연산을 해낼 수 있게 됩니다.

레퍼런스

• Introduction to Logic (14th ed., Irving Copi, Carl Cohen, Kenneth D. McMahon, 2011)

• A Mathematical Introduction to Logic (2nd ed., Herbert Enderton): 명제 논리학과 1차 논리학을 소개하고 있습니다.

• An Investigation of the Laws of Thought (George Boole, 1854)

• The Universal Computer (Martin Davis, 2000): 불의 작업을 간략하게 소개하고 있습니다.

• Computer Organization and Design (David Patterson, John Hennessy, 2013), 또는 컴퓨터 구조 및 설계 (2015): 가산기 관련 내용을 찾아볼 수 있습니다.