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

컴퓨터를 구성하는 기본적인 요소인 논리 게이트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$일 것입니다. 그런데 이 결과를 논리학의 영역에서 어떻게 해석할 수 있을까요?

원래의 식 $xx = x$는 인수분해를 통해 다음과 같이 고칠 수 있습니다.

여기서 1을 ‘전부’로, 0을 ‘없는 것’으로 해석해봅시다. 그리고 뺄셈을 앞쪽에서 뒷쪽을 뺀 것이라고 해봅시다. 예를 들어, $1-x$는 ‘전부’에서 ‘빨간 것’을 뺐으니 ‘빨갛지 않은 것’입니다.

그러면 $x(1-x) = 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가 있습니다. 다음과 같이 마음대로 정의한 연산이 있다고 해봅시다.

이걸 기존의 논리 연산으로 만들어낼 수 있을까요?

이 질문이 중요한 이유는, 기존의 논리 연산이 모든 경우의 수를 다룰 수 있을 만큼 충분한 지를 묻기 때문입니다. 예를 들어, 논리곱만으로는 $\circledcirc$를 표현할 수 없지만, 논리곱과 부정negation이 있으면 가능합니다.

여기서 부정 $\neg x$는 $x$가 $0$일 때 $1$이고, $1$일 때 $0$인 것입니다. 따라서 오직 $x$가 $0$이고 $y$가 $1$일 때에만 $(\neg x)y$는 $1$이므로, $\circledcirc$를 표현할 수 있게 됩니다.

만약 $\circledcirc$ 뿐만 아니라, 생각해낼 수 있는 모든 종류의 연산을 전부 논리곱과 부정으로 표현할 수 있다면, 논리곱과 부정은 완전complete하다고 부릅니다. 예를 들어, 논리곱만으로는 $\circledcirc$를 표현할 수 없으므로 완전하지 않은 것입니다. 그리고 증명은 생략하겠지만, 논리곱과 부정은 실제로 완전합니다.

그러면 두 개가 최소일까요? 답은 하나의 연산도 완전할 수 있습니다. 다음과 같이 셰퍼 스트로크Sheffer stroke라고 부르는 연산이 있습니다.

이 연산으로 논리곱과 부정을 만들어낼 수 있기 때문에, 셰퍼 스트로크만으로도 완전하게 됩니다. (증명은 직접 해보세요.) 그리고 NAND 게이트라고 부르는 것이 이 연산을 구현합니다. 이것이 NAND 게이트가 컴퓨터의 모든 하드웨어를 만들어낼 수 있는 이유입니다.

논리학에서 계산기로

이제 논리학이 어떻게 계산기가 되는지 설명할 차례입니다.

일단 어떻게 물리적으로 만들지는 고민하지 않으려고 합니다. 옛날에는 물을 이용한 기계도 있었던 것 같지만, 그냥 전기를 이용해 불 논리를 구현할 수 있다고 치겠습니다. (사실 클로드 섀넌Claude Shannon이라는 사람이 이미 그런 일을 해놨습니다. 오늘날 논리 게이트는 모스펫MOSFET이라는 반도체를 통해 물리적으로 구현됩니다.)

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

이전에 정의했던 연산을 이용하면, $c$는 마치 $xy$, $s$는 $(x \oplus y) \neg (xy)$처럼 보입니다. 따라서 이 논리 연산이 1비트 덧셈을 하는 것과 다름 없게 됩니다. 이렇게 완성한 덧셈 계산기는 반가산기half adder라고 부르는 회로입니다.

만약 여러 자리 비트의 덧셈을 계산하고 싶다면, $x$, $y$ 뿐만 아니라 이전 자릿수의 덧셈에서 자리올림한 것 또한 고려해야 합니다. 이렇게 세 개의 입력을 받아 덧셈 하는 회로를 전가산기full adder라고 부르고, 여러 개를 이어 붙여 리플 캐리 가산기ripple-carry adder라고 하는 것을 만들면 여러 자릿수의 덧셈을 할 수 있게 됩니다. 이 장치는 나아가 ALUarithmetic logic unit라고 부르는 회로의 구성 요소가 되고, 이것은 다시 프로세서, 또는 CPU라고 부르는 하드웨어의 핵심적인 구성 요소가 됩니다.

레퍼런스

• 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): 가산기 관련 내용을 찾아볼 수 있습니다.