본 포스팅은 ‘Mano의 컴퓨터시스템구조’ 교재를 참고했습니다.

2진법과 논리 게이트

2진법은 0과 1이라는 두개의 숫자만을 사용하여 수를 나타내는 것이다.

디지털 컴퓨터는 0과 1 두개의 숫자만을 사용하는데, 하나의 이진 숫자를 bit라고 부른다. 컴퓨터는 전압 신호를 이용하여 0과 1로 표현한다.

이전 정보의 처리는 게이트라 불리는 논리 회로에서 이루어진다. 아래 표는 각 게이트의 이름, 대수 표현식, 진리표를 나타낸 것이다.

부울 대수

부울 대수는 19세기 중반 조지 불이 만든 대수 체계로, 디지털 회로의 해석과 설계를 쉽게 하는 것이 목적이다.

부울 대수의 기본 관계는 아래와 같다. 각각은 모두 진리표로 증명할 수 있다.

부울 대수의 기본 관계

1. $x + 0 = x$
2. $x \cdot 0 = 0$
3. $x + 1 = 1$
4. $x \cdot 1 = x$
5. $x + x = x$
6. $x \cdot x = x$
7. $x + x^\prime= 1$
8. $x \cdot x^\prime 0$
9. $x + y = y + x$
10. $x \cdot y = y \cdot x$
11. $x + (y + z) = (x + y) + z$
12. $x \cdot (y \cdot z) = (x \cdot y) \cdot z$
13. $x (y + z) = xy + xz$
14. $x + yz = (x + y)(x + z)$
15. $(x + y)^\prime= x^\prime \cdot y^\prime $
16. $(x \cdot y)^\prime = x^\prime + y^\prime $
17. $(x^\prime)^\prime = x$

위 식은 부울 대수의 기본적인 관계를 나타낸다. 부울대수는 교환 법칙과 결합 법칙이 성립한다. 또한 식 15번과 16번은 드 모르간의 정리이다.

수식의 보수

드 모르간의 정리는 모든 $\text{OR}$ 연산은 $\text{AND}$ 로, 모든 $\text{AND}$ 연산은 $\text{OR}$ 로 바꾸어 주고, 각 변수를 보수화하면 간단히 적용할 수 있다.

예들들어 다음과 같이 수식의 보수를 만들 수 있다.

$$ F=AB+C^\prime D^\prime +B^\prime D $$ $$ F^\prime =(A^\prime +B^\prime )(C+D)(B+D^\prime ) $$

부울 대수의 활용

부울 대수를 통해 디지털 회로를 간단히 하는 데 사용할 수 있다. 아래와 같은 회로 $F$가 있다고 가정해 보자.

$$ F=ABC+ABC^\prime +A^\prime C $$

부울 대수를 적용하면, $(C+C)^\prime =1$이고, $AB \cdot 1=AB$ 이므로,

$$ F=ABC+ABC^\prime +A^\prime C=AB(C+C^\prime )+A^\prime C=AB+A^\prime C $$

이다. 따라서 4개의 게이트만 사용하여 효율적인 회로를 설계할 수 있는 것이다.

부울 대수 문제

1. $A \cdot (A + B) = A$ 임을 보여라.

   풀이

   $$ \begin{aligned} AA + AB &= A + AB \\ &= A (1 + B) \\ &= A \cdot 1 \\ &= A \end{aligned} $$

2. $ (A + B) \cdot (A + B^\prime ) = A $ 임을 보여라.

   풀이

   $$ \begin{aligned} AA + AB{^\prime} + AB + BB{^\prime} &= AA + AB{^\prime} + AB + BB{^\prime} \\ &= A + A(B{^\prime} + B) \\ &= A + A \cdot 1 \\ &= A \end{aligned} $$