들어가며.
컴퓨터는 논리 회로의 집합이다. 이 논리 회로는 컴퓨터 뿐만 아니라 디지털 장치에서 많이 사용되기 때문에 논리회로나 디지털 기기의 설계자가 고려해야 할 중요한 요소이다. 회로를 최대한 간단하고 낮은 비용으로 만들 수 있다면 가격이 싸지고, 설계자가 만든 제품은 경쟁력이 살아날 것이며, 큰 돈을 벌 수 있을 것이다.
그렇다면. 논리회로를 간단하게 만드는 방법이란 무엇일까?
바로 "부울 대수학 (boolean Alegebra)"을 이용하는 것이다.이름부터 생소한 이 녀석을 이해하면 회로를 최적화하는 방법과 수백만개의 논리 회로로 구성되는 복잡한 회로들을 설계할 때 사용하는 소프트웨어의 원리까지도 깨우칠 수 있다.
사실 부울 대수는 원소, 연산자, 공리, 공중으로 정의할 수 있고 결합, 교환, 분배 법칙이 성립하며 (일반적 결합,교환 x)...
하는 이런 기본 이론적 부분은 생략하고 넘어가겠다. (알면 좋지만 처음부터 이론을 깨우치고 들어가긴 어려움.)
그냥 먼저 우리는 두가지 입력에 대한 논리 게이트 (논리 연산)을 진행할 것이고. 그 과정을 반복숙달 하다가 다시 부울 대수에 대한 검색을 해서 기본 정의에 대한 부분을 읽어보면 이해가 되기 때문이다.
2-1. 2값 부울대수 (boolean algebra)와 기본 성질, 정리
이제부터 우리는 '2값 부울대수'를 사용할 것이다. 말 그대로 두개의 입력을 가지고 하는 논리 연산을 하겠다는 말이다.
먼저 기본적인 2진 연산자 +와 ●으로 정의되는 규칙을 가진 AND와 OR이라는 연산이 있다.
먼저 AND 연산이란. 두개의 값 중 두개 모두 1인 경우에는 1을 출력하고 그 외의 경우는 모두 0 인 연산이다.
그림의 왼쪽 표에서도 볼 수 있듯이. x와 y라는 입력이 둘중 하나만 0이여도 값은 0으로 출력되고, x와 y 둘 다 1이 입력됐을 때에만 1을 출력한다. 표기는 우리가 사용하는 곱샘과 비슷하게 ●으로 표기한다.
다음은 OR 연산이다. 두개의 값 중 하나라도 1이라면 1을 출력하고, 두 입력이 0인 경우만 0이 되는 연산이다.
그림의 중간의 표에서도 볼 수 있듯이. x, y의 입력이 둘 다 0인 경우를 제외하고 모두 1을 출력한다.
표기는 우리가 사용하는 덧셈과 같은 (+)의 기호를 사용한다.
마지막은 NOT 연산이다.(인버터가 대표적인 NOT 연산을 한다.)
우리가 앞에서 배운 보수(complement)와 같은 개념으로, 2진법에서 반대변환의 연산이다.
그림의 마지막 표에서도 볼 수 있듯이. 2진법의 보수는 각 자리의 0과 1을 서로 반대로 바꾸어 주면 되기 때문에 각 입력에 따라서 반대의 출력을 나타내고 있다.
표기는 첨자에 '(prime)을 붙여서 표기한다.
즉 정리하자면. AND 연산은 곱으로, OR은 덧셈으로, NOT은 반대변환의 prime첨자로 표기된다.
(그러나 실제로 곱, 덧셈 연산을 하면 된다는 뜻이 아니다, 논리연산을 해야한다.)
이러한 기본 연산 AND, OR, NOT을 바탕으로 위와 같은 표의 연산 성질을 표현할 수 있다. (이해와 약간의 암기 필요)
우리가 기본적으로 사칙연산을 할 때와 비슷한 성질을이 많이 보이지만, 또 아예 그렇지 않은 것도 존재한다.
이 때 부울대수의 정의에 의한 성질중 쌍대 원리 (duality)라는 성질이 존재한다. (표에서 a와 b는 서로 쌍대관계)
즉 같은 값을 나타내지만 다른 쌍대로도 같은 값을 표기할 수 있다는 것이다.
이 쌍대(duality)도 구하는 방법이 정해져 있다.
-쌍대(duality) 구하기-
1. AND는 OR로, OR은 AND로 바꿔준다.
2. 1은 0으로, 0은 1로 바꿔준다 (NOT연산)
3. (a)가 성립하면. (a)의 쌍대인 (b)도 성립한다.
그리고 사칙연산에도 곱,나누기,더하기,빼기가 섞여있을 때 먼저 풀어줘야 하는 우선순위가 있는것처럼 부울대수도 마찬가지이다.
-부울대수 연산순서-
1. 괄호 (parentheses)
2. NOT
3. AND
4. OR
2-2. 부울 함수
부울대수는 위에서 살펴보았든, 2진 변수와 논리 연산을 다루는 대수라는 것을 파악했다.
대수식으로 표현되는 부울 함수는 2진 변수, 상수 0과 1, 논리 연산 기호로 구성된다.
따라서 주어진 2진 변수로 구성된 함수의 결과값은 0 또는 1이다. (함수로 표현되는 인과)
하나의 부울함수 예시를 보자.
F1과 F2 함수에는 x, y, z라는 세가지 변수로 이루어져 있고. 여기서 하나의 항(term)에 있는 하나의 변수를 리터럴(literal)이라고 정의한다. 따라서 F1의 함수에는 두개의 항, 3개의 리터럴을 가지고 있다.
이 변수에는 2진 변수 (0과 1)만 들어갈 수 있으므로.
변수에 대입될 수 있는 경우의 수는 2^3개. 즉 8가지의 경우가 가능하다. 이 조건에 따라 대입하여 결과값을 정리해 놓은 표를 진리표 (truth table)라고 한다.
이렇게 주어진 부울 함수에 대해서 진리표와 논리 게이트를 설계하여 표현할 수 있다.
따라서 부울 함수를 표현할 수 있는 방법은 1. 진리표 2. 수학적 연산자 표현 3. 논리회로 의 세가지 방법이다.
이 중 하나만 주어지더라도. 이 논리연산에 적용된 부울함수를 알아낼 수 있다.
그러나 이 때. 진리표와 달리. 부울함수의 수학적 수식과, 논리회로의 표현 가짓수는. 유일하지 않고 다양할 수 있다.
다시 말해보자면, 부울함수에 대응하는 진리표는 유일하지만, 그 진리표나 논리회로에서 유추해낸 부울함수의 수학적 표현이나, 진리표를 바탕으로 쓴 논리회로의 경우의 수는 다양할 수 있다.
이렇게 다양한 함수의 표현으로 변화가 가능한 것은 부울대수의 특성때문이다. 즉 여러 수식끼리 같아질 수 있는 '쌍대 (duality)', 다양한 '공준과 정리' 때문이다. (위의 table 2.1 참고)
그리고 당연하게도.
가장 심플하고 축약된 형태의 부울 함수가 선호되고, 그 부울함수를 이용한 Gate implement (logic circuit)가 중요하다.
(이렇게 가장 심플한 부울함수를 구하는 방법은 Chapter 3. 에서 배워볼 것이다.)
2-3. 함수의 보수
2진 논리 연산에서 보수(complement)라는 것은. NOT의 연산이라고 앞서 말해둔 바 있다.
함수에서 보수의 개념이 적용될 때에도 동일하다.
즉. 함수의 보수라는 것은. 원함수와 반대의 출력값을 가지는 함수라는 것이다.
이 함수의 보수를 구하기 위해선 부울함수의 '드모르간의 정리'를 이용할 필요가 있다.
예시를 보겠다.
그런데 이 때 드모르간의 법칙에서 확장하여, 더 간단하게 함수의 보수를 구할 수 있는 방법이 있다.
-함수의 보수 구하기-
1. 함수의 쌍대(dual)을 구한다.
2. 각 리터럴의 보수(complement)화 한다.
위에서 사용했던 F1, F2함수를 그대로 이용하여 이 패턴대로 구해보자.
'디지털공학 > Chap 2.' 카테고리의 다른 글
| Chap 2. 부울 대수와 논리 게이트 (2) . Boolean Algebra and Logic Gates (0) | 2022.01.09 |
|---|