컴퓨터는 엄마가 좋은지 아빠가 좋은지로 구성됨

지난 글에서는 ‘신호등이 초록불이고 전방에 장애물이 없으면 직진한다’라는 판단을 불 대수와 진리표로 표현했다. 그리고 섀넌의 통찰 덕분에 이런 논리가 실제 전기 회로로 구현될 수 있음을 확인했다.

하지만 진리표는 종이 위의 설계도일 뿐이다. 이 설계도대로 실제로 작동하는 회로를 만들려면 어떻게 해야 할까? 바로 논리 게이트가 필요하다.

불 대수에는 다양한 연산이 있지만, AND, OR, NOT은 특별하다. 우리가 일상에서 ‘그리고’, ‘또는’, ‘아닌’이라는 말로 사고하는 방식과 직결되어 직관적이고, 이 세 가지만으로 어떤 복잡한 불 함수도 표현할 수 있기 때문이다. 정말 그런지는 이 세 게이트를 하나씩 살펴본 후에 확인해보자.

엄마 아빠가 모두 좋은 AND 게이트

AND는 ‘그리고’를 의미한다. 두 가지 조건이 모두 참일 때만 결과가 참이 된다. ‘엄마가 좋다 AND 아빠가 좋다’는 엄마 아빠가 모두 좋아야 참이다.

AND 게이트는 특정 조건들이 모두 충족되었는지 판단하는 데 주로 사용된다. 예를 들어, 비밀번호와 지문이 모두 맞아야 스마트폰 잠금이 해제되는 경우를 생각해볼 수 있다.

적어도 한 분은 좋은 OR 게이트

OR는 ‘또는’을 의미한다. 두 가지 조건 중 하나라도 참이면 결과가 참이 된다.

여러 가능한 조건들 중 하나만 만족해도 되는 상황을 판단하는 데 사용된다. 예를 들어, 집 앞문이나 뒷문 중 하나만 열려 있어도 환기가 되는 경우를 생각해볼 수 있다.

좋으면 싫고 싫으면 좋은 NOT 게이트

NOT는 ‘아니다’를 의미한다. 입력된 비트의 상태를 반전시키는 논리이다.

어떤 상태를 반대로 뒤집거나 특정 조건이 아닌 경우를 판단할 때 사용된다. 예를 들어, 스마트폰이 잠겨 있지 않을(NOT) 때만 터치가 작동하는 경우를 생각해볼 수 있다.

직진 판단 회로 만들기

이제 세 가지 게이트를 모두 배웠으니, 이전 글의 직진 판단을 실제 회로로 만들어 보자. 직진 = 초록불 ∧ ¬장애물이었다. 이를 게이트로 표현하면 장애물 신호를 NOT 게이트로 뒤집고, 그 결과를 초록불 신호와 함께 AND 게이트에 넣으면 된다.

이를 회로로 표현하면 다음과 같다. 입력을 클릭해서 값을 바꿔보자.

이전 글에서 만들었던 직진 판단 진리표와 똑같이 작동한다. 이처럼 AND, OR, NOT 게이트를 조합하면 진리표를 실제 회로로 구현할 수 있다.

이 예시는 직관적으로 게이트를 조합할 수 있었다. 하지만 모든 불 함수가 이렇게 쉽게 분해되지는 않는다. 임의의 진리표를 AND, OR, NOT으로 체계적으로 변환하는 방법은 없을까?

AND, OR, NOT으로 모든 불 함수 만들기

있다. 그 방법 중 하나를 알아보겠다.

핵심 아이디어는 간단하다. 출력 값이 참(1)이 되는 모든 입력 조합들을 찾아서, 그 각각의 조합을 AND 게이트로 만들고, 마지막으로 이 AND 결과들을 모두 OR 게이트로 합치는 것이다.

말로만 들으면 조금 복잡하게 느껴질 수 있으니 예시를 통해 자세히 살펴볼까? 두 입력이 같을 때 출력이 1인 게이트를 AND, OR, NOT만으로 만들어 보자. 우선 진리표를 살펴보면 다음과 같다.

이제 간단한 세 단계를 거치면 된다.

우선 출력 값이 1인 행을 모두 찾는다. 위 진리표에서 출력이 1인 행은 첫 번째 행 (A=0, B=0)과 네 번째 행 (A=1, B=1)이다.

그 다음 각 행을 표현하는 AND 조건을 만든다. 첫 번째 행 (A=0, B=0)은 입력 A가 0이고 입력 B가 0일 때 출력이 1이라는 뜻이며 이는 (입력 A가 0이다) AND (입력 B가 0이다) 즉, (NOT A) AND (NOT B)로 표현할 수 있다. 네 번째 행 (A=1, B=1)은 입력 A가 1이고 입력 B가 1일 때 출력이 1이라는 뜻이며 이는 A AND B로 표현할 수 있다.

마지막으로 이렇게 만들어진 각 AND 조건들을 OR 게이트로 모두 연결한다. 출력이 1이 되는 경우는 ‘첫 번째 행의 조건이 만족’ 또는 ‘네 번째 행의 조건이 만족’일 때이다. 따라서 위에서 만든 두 식을 OR로 연결하면 된다.

최종 논리식은 ((NOT A) AND (NOT B)) OR (A AND B) 가 된다.

원래 진리표와 똑같이 작동하는 회로가 완성됐다.

이처럼 진리표는 원하는 논리적 동작을 정의하는 ‘설계도’ 역할을 하고, 방금 소개한 방법은 이 설계도를 AND, OR, NOT이라는 ‘기본 부품’을 이용해 실제 회로로 만드는 과정을 보여준다.

논리 게이트의 물리적 구현

물리적인 내용이니 간단하게만 살펴보자. 논리 게이트 구현의 핵심은 전기 신호의 흐름을 제어하는 스위치를 만드는 것이다. 이 스위치 역할을 하는 부품이 트랜지스터이다. 트랜지스터는 특정 조건이 만족되면 전기가 흐르는 통로를 열고, 그렇지 않으면 막는다. AND, OR, NOT 게이트는 이 트랜지스터를 특정 방식으로 연결해서 만들어진다.

마무리

AND, OR, NOT은 사람에게 직관적이지만, 하드웨어 엔지니어의 관점에서는 물리적으로 얼마나 효율적이고 간단하게 구현할 수 있는지가 더 중요하다.

AND, OR, NOT은 물론 그 어떤 복잡한 논리 게이트도 오직 NAND 게이트 하나만으로 모두 만들 수 있다. 이를 NAND의 완전성 또는 보편성이라고 부른다. 마치 레고 블록 중에 특정 모양 하나만 있어도 다른 모든 모양을 조립할 수 있는 만능 블록이 있는 것처럼. NAND와 NOR 게이트가 바로 그런 만능 블록이다.

다음 시간에는 어떻게 NAND 게이트 하나만으로도 모든 논리 회로를 구성할 수 있는지에 대해 더 깊이 있게 알아보겠다.