포스테키안

2020 겨울호 / 지식더하기 ②

2021-01-18 76

컴퓨터의 언어 -불 대수
Boolean algebra

01110… IT 영화를 보다 보면 주인공이 0과 1만 사용하여 컴퓨터를 사용하는 장면을 볼 수 있습니다. 하지만 다행히도, 현실에서는 우리가 이해할 수 있는 자연어로 컴퓨터를 사용할 수 있습니다. 그럼 0과 1은 무엇을 뜻하는 걸까요? 바로 2진수, 즉 컴퓨터의 언어를 나타내는 것입니다. 우리가 컴퓨터에 내리는 모든 명령은 2진수로 변환되어야 컴퓨터가 이해할 수 있는데요, 이번 글에서는 컴퓨터 동작의 가장 기초가 되는 불 대수에 대해 알아보겠습니다.

 

불 대수는 영국의 수학자 조지 불 George Boole이 19세기 중엽에 창안한 대수의 한 형식인데요1. 입력에 대해 참(1), 거짓(0) 2가지 상태만을 판단하는 일종의 논리적 연산입니다. 이런 논리적 연산은 다양한 연산자 Gate를 통해 이루어지는데요. 가장 기초적인 연산자로 NOT, AND, OR이 있습니다. NOT은 이름 그대로 하나의 입력을 받아 반전시켜 출력합니다. 예를 들어 1이 입력으로 들어온다면 0을 내보내는 식이죠.

그다음으로 AND gate는 수학적으로 곱셈 연산을 의미하는데요. 그렇기 때문에 입력 모두가 1이어야 1을 출력하고 하나라도 0이면 0을 출력합니다. OR gate는 곱셈이 아닌 덧셈 연산을 의미합니다. 따라서 n개의 입력 중 하나라도 1이 있다면 1을 출력하는 것이겠죠. 이를 한눈에 알아볼 수 있게 만든 것이 바로 Truth Table인데요, 그림과 같이 입력에 따라 출력되는 결괏값을 표로 정리한 것을 뜻합니다. 연산자에는 앞서 소개한 3개뿐 아니라 다양한 종류가 있는데요. 각 gate의 설명을 읽고 직접 Truth Table을 그려본다면 논리 연산을 더 잘 이해할 수 있게 될 거예요!

  출처 https://introcs.cs.princeton.edu/java/71boolean/

불 대수를 사용함으로써 얻을 수 있는 장점 중 하나는 바로 불필요한 연산을 줄인다는 점, 즉 최적화를 하기 쉬워진다는 점입니다. 최적화를 배우기 전, 먼저 2가지 가장 기초적인 연산에 대해 알아보겠습니다. XX’는 X와 X’이 AND gate로 묶여 있는 것을 나타낸 것입니다2. 둘 중에 하나는 항상 0이기 때문에 출력은 0입니다. 유사하게 X+X’는 X와 X’이 OR gate로 묶여 있고, 둘 중 하나는 항상 1이므로 출력은 1입니다. 이 간단한 규칙을 사용하여 직접 최적화를 진행해 봅시다.

Z = A(A’+B) + B(A+A’)라는 연산이 있습니다. 입력으로는 A, B가 들어오고 있고 출력은 Z가 되겠네요. 이를 실제 Gate로 그려본다면 1개의 NOT gate (A’)와 각각 2개의 AND, OR gate가 필요한 것을 알 수 있습니다. 간단해 보이지만 꽤 많은 연산자가 필요하죠? 그럼 한번 최적화를 해 봅시다. 순서대로 A(A’+B)를 풀어보면 AA’+AB가 나옵니다. 이때 앞서 설명했듯이 AA’는 0이므로 AB만 남게 됩니다. 뒤에는 A+A’이 보이네요! 이는 항상 1이므로 B만 남을 것입니다. 남은 항을 모아보면 Z = AB + B가 되고 이를 B로 묶으면 B(A+1)이 됩니다. 그런데 (A+1)은 항상 1이므로 결국 Z = B라는 결과를 얻을 수 있습니다. 사실 이 연산은 단 하나의 연산자도 필요가 없었네요! 이렇게 불대수를 사용하면 복잡한 연산을 최적화할 수 있습니다.

이번 글에서는 불 대수의 정의와 간단한 논리 Gate, 그리고 최적화에 대해 알아 보았는데요, 컴퓨터의 동작을 깊게 이해하기 위해서는 불 대수에 대한 이해가 필수적입니다. 여기서 설명하지 않은 다양한 gate와 불 대수의 특징들을 공부해 본다면 분명 좋은 공부가 될 거예요!

 

각주
1 네이버 지식백과, 「불대수」, https://terms.naver.com/entry.nhn?docId=844426&cid=42346&categoryId=42346
2 X’은 X에 NOT 연산을 한 것을 의미합니다.