본 포스팅은 ‘Mano의 컴퓨터시스템구조’ 교재를 참고했습니다.
2진법과 논리 게이트
2진법은 0과 1이라는 두개의 숫자만을 사용하여 수를 나타내는 것이다.
디지털 컴퓨터는 0과 1 두개의 숫자만을 사용하는데, 하나의 이진 숫자를 bit라고 부른다. 컴퓨터는 전압 신호를 이용하여 0과 1로 표현한다.
이전 정보의 처리는 게이트라 불리는 논리 회로에서 이루어진다. 아래 표는 각 게이트의 이름, 대수 표현식, 진리표를 나타낸 것이다.
Name | Algebraic function | Truth table |
---|
AND | x=A⋅B | |
OR | x=A+B | |
Inverter | x=A′ | |
Buffer | x=A | |
NAND | x=(A⋅B)′ | |
NOR | x=(A+B)′ | |
XOR | x=A⊕B | |
XNOR | x=(A⊕B)′ | |
부울 대수
부울 대수는 19세기 중반 조지 불이 만든 대수 체계로, 디지털 회로의 해석과 설계를 쉽게 하는 것이 목적이다.
부울 대수의 기본 관계는 아래와 같다. 각각은 모두 진리표로 증명할 수 있다.
부울 대수의 기본 관계
- x+0=x
- x⋅0=0
- x+1=1
- x⋅1=x
- x+x=x
- x⋅x=x
- x+x′=1
- x⋅x′0
- x+y=y+x
- x⋅y=y⋅x
- x+(y+z)=(x+y)+z
- x⋅(y⋅z)=(x⋅y)⋅z
- x(y+z)=xy+xz
- x+yz=(x+y)(x+z)
- (x+y)′=x′⋅y′
- (x⋅y)′=x′+y′
- (x′)′=x
위 식은 부울 대수의 기본적인 관계를 나타낸다. 부울대수는 교환 법칙과 결합 법칙이 성립한다. 또한 식 15번과 16번은 드 모르간의 정리이다.
수식의 보수
드 모르간의 정리는 모든 OR 연산은 AND 로, 모든 AND 연산은 OR 로 바꾸어 주고, 각 변수를 보수화하면 간단히 적용할 수 있다.
예들들어 다음과 같이 수식의 보수를 만들 수 있다.
F=AB+C′D′+B′D
F′=(A′+B′)(C+D)(B+D′)
부울 대수의 활용
부울 대수를 통해 디지털 회로를 간단히 하는 데 사용할 수 있다. 아래와 같은 회로 F가 있다고 가정해 보자.
F=ABC+ABC′+A′C
부울 대수를 적용하면, (C+C)′=1이고, AB⋅1=AB 이므로,
F=ABC+ABC′+A′C=AB(C+C′)+A′C=AB+A′C
이다. 따라서 4개의 게이트만 사용하여 효율적인 회로를 설계할 수 있는 것이다.
부울 대수 문제
A⋅(A+B)=A 임을 보여라.
풀이
AA+AB=A+AB=A(1+B)=A⋅1=A (A+B)⋅(A+B′)=A 임을 보여라.
풀이
AA+AB′+AB+BB′=AA+AB′+AB+BB′=A+A(B′+B)=A+A⋅1=A