8비트 게임기를 만들어보자! (기초 지식 1) 논리 연산과 논리 회로

이 글에서는 8비트 게임기 만들기에 기초적인 지식을 짚고 넘어갑니다.

논리, 명제

'논리적으로 생각해', '논리에 따르면', '그 논리는 틀렸어'... 논리가 뭘까요?
 
논리(論理)는 한자를 풀이하면 '이치를 논한다' 가 됩니다. 논리학은 어떤 말이 맞을 때 다른 어떤 말이 맞는지, 틀린지를 알아내는 과정을 주로 연구하는 학문입니다.
이 '어떤 말'은 누구라도 그 말이 참인지, 거짓인지를 알아낼 수 있어야 합니다. 여러분이 지금 '나는 지금 글을 읽고 있다'고 말한다면, 그건 객관적으로 사실이기 때문에 여러분이 생각했을 때도 참이고, 옆에서 보고 있는 사람이 생각했을 때도 참입니다. 하지만 TV를 보면서 말했다면 누가 생각해도 거짓말입니다. 이처럼 누가 생각했을 때도 참과 거짓을 명료하게 구분할 수 있는 문장을 명제(命題, Proposition)라고 합니다.
 
명제는 전제(前提, Premise)와 귀결(歸結, Conclusion)로 구성됩니다. '이 새는 타조이다' 와 '이 새는 날 수 없다'를 합치면 '타조이면 날 수 없다' 라는 명제가 됩니다. 전제는 밑바탕에 주어진 조건입니다(타조이면 ~ ). 귀결은 전제에 따라 내린 결론입니다(~ 날 수 없다). 명제가 참이면, 전제가 참일 때 귀결이 참입니다. '타조이면 날 수 없다' 는 참이므로, '이 새는 타조이다' 는 전제를 만족하면 '이 새는 날 수 없다'는 귀결은 참입니다.
 
좀 더 알아보기 쉽게 하기 위해, 앞으로 모든 명제는 'A이면 B이다'의 형태로 말하겠습니다.

• 한국에서 스무 살이면 술을 사도 합법이다.(참)
• 타조이면 날 수 없다. (참)
• 계란을 품으면 병아리가 태어난다. (거짓. 무정란일 수도 있으니까요)
• 계란이 유정란이고 어미 닭이 품으면 병아리가 태어난다. (참. 알이 곯아서 죽는 경우는 없다고 가정합시다)
• 계란이 유정란이 아니거나 품지 않으면 병아리가 태어나지 않는다. (참)

 

부울 대수, 논리 연산

4번 명제와 5번 명제는 전제가 둘, 귀결이 하나입니다. 두 전제 사이에 '~이고', '~거나'가 들어가고, 전제나 귀결 뒤에 '~가 아니면'이 붙어도 명제를 만들 수 있습니다. 4번 명제를 '2 × 2 = 4'와 같은 수식처럼 나타내면, '(계란은 유정란이다) 그리고 (계란을 어미 닭이 품었다) = (계란에서 병아리가 태어난다)' 가 됩니다. 전제와 귀결은 참과 거짓을 명백히 판별할 수 있는 요소이기 때문에 단순히 '참' 혹은 '거짓'으로 바꿔 봅시다. 계란이 유정란이고 닭이 품었으면 '(참) 그리고 (참) = (참)' 입니다. 계란이 무정란인데 닭이 품었으면 '(거짓) 그리고 (참) = (거짓)'입니다. '그리고' 라는 말이 숫자 대신 참과 거짓만 값으로 가지는 수식의 연산 기호가 되었습니다. 이렇게 숫자 대신 참(1)과 거짓(0)만 있는 계산법을 부울 대수(Boolean Algebra)라고 하고, 부울 대수에서의 연산을 논리 연산(Logical operation)이라고 합니다.
 
앞에서 '~이고', '~거나', '~가 아니다'를 예시로 든 이유는 그것이 기본적인 논리 연산 세 가지이기 때문입니다. 하나씩 살펴볼까요?

NOT 연산

 

NOT 연산의 진리표

NOT 연산의 벤 다이어그램

'A면 X가 아니다' 형태의 명제는 전제가 하나, 귀결이 하나입니다. 전제가 참이면 귀결은 거짓이고, 전제가 거짓이면 귀결은 참입니다. '이 계란은 유정란이 아니다'는 계란이 유정란이면 거짓이고, 계란이 유정란이 아니면 참입니다. 이것이 NOT 연산입니다. 이름이 말해주는 대로 단순히 귀결을 뒤집기만 하는 연산입니다. 부정이라고도 부릅니다.

NOT을 두 번 반복해서 계산하면 원래의 값이 됩니다. '적의 적은 친구'라는 문장을 생각해 보세요. 위의 벤 다이어그램에서도 오른쪽을 다시 뒤집으면 왼쪽이 됩니다.
 

OR 연산

 

OR 연산의 진리표

OR 연산의 벤 다이어그램

'A이거나 B이면 X이다' 입니다. 전제가 둘이고 귀결이 하나입니다. 전제 둘 중에 하나라도 참이면 귀결이 참입니다. '어떤 숫자가 4의 배수거나 6의 배수이면 짝수이다'는 4의 배수기만 해도 되고, 6의 배수기만 해도 되고, 둘 다여도 참입니다. 이것이 OR 연산입니다. 'A거나 B이면' 이라는 문장 구조와 같습니다. 논리합이라고도 부릅니다. 참을 1, 거짓을 0으로 나타냈을 때 0 + 0일 때만 0이고 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 1(2이지만 0과 1밖에 없으므로 1)이기 때문입니다.
 

AND 연산

 

AND 연산의 진리표

AND 연산의 벤 다이어그램

'A이고 B이면 X이다'입니다. 전제가 둘이고 귀결이 하나입니다. 전제 둘 다 참일 때만 귀결이 참입니다. '어떤 숫자가 4의 배수이고 6의 배수이면 12의 배수이다'는 4의 배수라는 전제와 6의 배수라는 전제 둘을 다 만족해야 12의 배수라는 귀결이 참이 됩니다. 이것이 AND 연산입니다. 'A이고 B이면' 이라는 문장 구조와 같습니다. 논리곱이라고도 부릅니다. 참을 1, 거짓을 0으로 하면 0 × 0 = 0, 0 × 1 = 0, 1 × 0 = 0이고, 1 × 1일 때만 1이기 때문입니다.
 
사칙연산 기호와 같이, 하나의 식은 여러 개의 논리 연산으로 구성됩니다. 논리 연산 사이에도 사칙연산 같은 순서가 있어서, 프로그램은 논리 연산을 NOT, AND, OR 순서로 계산합니다. 사칙연산 중에서 더하기와 곱하기만이 연산 기호의 양쪽 항을 바꿔도 계산 결과가 같은 '교환 법칙'이 성립하는데, NOT은 어차피 전제가 하나이기 때문에 순서를 바꿀 수 없고, AND와 OR은 양쪽 항의 위치를 서로 바꾸어도 결과가 같아 교환 법칙이 성립합니다.
 

논리 회로

논리 연산이 참이나 거짓을 가지고 하는 계산식임을 배웠습니다. 이것이 컴퓨터랑 무슨 상관일까요? 컴퓨터는 전기가 높은 전압에 있거나, 낮은 전압에 있는 두 가지 상태만을 가지고 모든 상황을 인식합니다. 높은 전압을 참(1), 낮은 전압을 거짓(0)으로 바꾸면 앞에서 보았던 명제 간의 계산과 같습니다. 그렇기 때문에 전압을 갖고 논리 연산을 수행한다면 1과 0만 가지고도 수많은 상태를 구별하고 결론이 참인지 거짓인지 판별할 수 있습니다. 이렇게 논리 연산을 수행하는 회로 구성요소를 논리 회로(Logic circuit)라고 부릅니다. 논리 회로 대신 논리 게이트(Logic gate)라고 부르기도 하는데, 논리 게이트가 기본 구성요소만을 포함하는 말이고, 논리 회로라는 말은 논리 게이트를 조합해서 만들어지는 복잡한 장치를 포함하는 말입니다.
 

논리 게이트의 종류.

앞에서 살펴본 논리 연산인 NOT, OR, AND가 보입니다. 다른 연산도 추가되었네요. 편의를 위해 높은 전압은 1, 낮은 전압은 0으로 표시합니다.

• 버퍼 - 입력이 1이면 출력도 1, 입력이 0이면 출력도 0입니다. 'A이면 X이다' 입니다.
• NOT - 입력이 1이면 출력이 0, 입력이 0이면 출력이 1입니다. 'A가 아니면 X이다' 입니다.
• AND - 입력이 둘 다 1일 때만 출력이 1, 나머지 경우는 출력이 0입니다. 'A이고 B이면 X이다' 입니다.
• NAND - 입력이 둘 다 1일 때만 출력이 0, 나머지 경우는 출력이 1입니다. 'A이고 B이면 X가 아니다' 입니다. 
• OR - 입력이 둘 중 하나라도 1이면 출력이 1, 둘 다 0이면 출력이 0입니다. 'A이거나 B이면 X이다' 입니다.
• NOR - 입력이 둘 중 하나라도 1이면 출력이 0, 둘 다 0이면 출력이 1입니다. 'A이거나 B이면 X가 아니다' 입니다.
• XOR - 입력이 둘 중 하나만 1이면 출력이 1, 둘 다 1이거나 둘 다 0이면 출력이 0입니다. 'A와 B가 다르면 X이다' 입니다.
• XNOR(XAND) - 입력이 둘 중 하나만 1이면 출력이 0, 둘 다 1이거나 둘 다 0이면 출력이 1입니다. 'A 와 B가 같으면 X이다' 입니다.

 

NAND와 NOR의 진리표

NAND는 AND의 결론만 뒤집은 것이고, NOR도 OR의 결론만 뒤집은 것입니다. 회로기호로 나타낼 때는 결론이 뒤집혔다(=NOT이 붙었다)는 것을 나타내기 위해 출력 핀에 작은 동그라미를 붙입니다. 입력 핀에 작은 동그라미가 붙는 경우도 있는데, 똑같이 입력에 NOT이 붙어서 반대로 인식한다는 뜻입니다.
전자 회로에서는 AND와 OR 보다는 NAND와 NOR을 쓰는 경우가 더 많습니다. 입력이 켜졌을 때 출력을 차단하는 회로의 구현이 더 쉽고 공간과 자원, 전력을 덜 소모하기 때문입니다.
 

XOR과 XNOR의 진리표

XOR 연산의 벤 다이어그램

 
XOR과 XNOR(XAND)는 새로 보는 게이트입니다. XOR은 두 입력의 상태가 서로 달라야 출력이 참이 되는 특성을 나타내기 위해 배타적 논리합(eXclusive OR)이라는 이름이 붙었습니다. XNOR은 XOR의 결론만 뒤집은 게이트로 두 입력의 상태가 같으면 출력이 참입니다. 다른 말로는 배타적 논리곱(eXclusive AND)이라고 합니다.
 

NOT, AND, OR로 구성된 XOR

XOR과 XNOR은 NOT, AND, OR 게이트의 조합으로 만들 수 있습니다. 수식으로 나타내면 ((NOT A) AND B) OR (A AND (NOT B)) = X입니다.

드모르간의 법칙

앞에서 NOT, AND, OR을 기본적인 논리연산의 구성요소로 소개하고, XOR 게이트도 NOT, AND, OR로 만들 수 있음을 보였습니다. 그런데 이 셋 중 꼭 필요한 것은 NOT 게이트뿐이고, AND와 OR은 사실 둘 중 하나만 있으면 다른 쪽도 만들 수 있습니다! 어떻게 하면 될까요?
계란과 병아리의 명제를 다시 살펴봅시다.

• 계란이 유정란이고 어미 닭이 품으면 병아리가 태어난다.
• 계란이 유정란이 아니거나 품지 않으면 병아리가 태어나지 않는다.

이 둘은 곰곰히 생각해 보면 사실 같은 뜻을 가진 문장입니다. 수학 시간에 배웠던 벤 다이어그램으로 나타내 봅시다.
 
 

(NOT A) OR (NOT B) = A NAND B = NOT(A AND B) 입니다. 만약 얻고 싶은 것이 AND라면, NOT을 하나 더 붙여주면 -1 * -1 = 1인 것처럼 NOT(NOT(A)) = A라는 성질을 이용하면 됩니다. 즉 NOT{(NOT A) OR (NOT B)} = (NOT A) NOR (NOT B) = A AND B입니다. 처음의 식에 있던 OR이 어느새 AND로 전환되었습니다! 신기하지 않나요? 이렇게 NOT만 있으면 OR과 AND 사이를 전환할 수 있는 것을 드모르간의 법칙(De Morgan's law)이라고 합니다.

 

당연히 반대로도 성립합니다. (NOT A) AND (NOT B) = A NOR B = NOT(A OR B) 입니다. 여기에도 출력에 NOT을 붙여 주면 반전되지 않은 결과를 얻을 수 있어서, NOT{(NOT A) AND (NOT B)} = (NOT A) NAND (NOT B) = A OR B입니다.
 
흥미로운 법칙인데 이 법칙을 실용적으로 쓸 수 있을까요? 
 

드모르간의 법칙에 의해 동등한 회로

NOT(NOT A) = A라는 성질과 드모르간의 법칙을 이용하면 회로에 필요한 논리 게이트의 수를 줄일 수 있습니다. 위의 세 개의 조합 논리 회로는 전부 같은 동작을 하는데, 위의 회로가 3개의 게이트를 사용한 반면 아래의 회로는 2개의 게이트만 사용한 것을 볼 수 있습니다. 가운데 회로에 있는 입력 2개가 반전된 AND 게이트는 NOR을 드모르간 변환한 것으로, NOR 게이트의 다른 모습입니다.
 

정리

1. 참과 거짓만을 값으로 갖는 수식을 부울 대수(Boolean Algebra)라고 한다.
2. 부울 대수에서 쓰이는, 참과 거짓만을 인수로 해서 참 혹은 거짓을 내놓는 연산을 논리 연산(Logical operation)이라고 한다.
3. 논리 연산의 기본 연산자는 NOT, AND, OR이 있다.
4. 논리 연산을 수행하는 회로를 논리 회로(Logic circuit)라고 하고, 논리 회로를 구성하는 최소 단위는 논리 게이트(Logic gate)라고 한다.
5. 논리 게이트는 버퍼, NOT, AND, NAND, OR, NOR, XOR, XNOR이 있다.
6. 논리 게이트는 AND와 OR 보다는 출력이 역전된 NAND, NOR이 더 많이 쓰인다.
7. NOT이 있으면 AND와 OR은 서로 전환이 가능하며, 이를 드모르간의 법칙(De Morgan's Law)라고 한다.
8. 드모르간의 법칙을 응용하면 논리 게이트의 수를 줄일 수 있다.
 

참조

한글 위키백과 - 논리학

한글 위키백과 - 명제

한글 위키백과 - 논리 연산

한글 위키백과 - 불 대수

한글 위키백과 - 논리 회로

영어 위키백과 - Logic gate

한글 위키백과 - 드 모르간의 법칙