[Truth Table] Combinational Logic Design

위 그림의 (a)를 살펴보자.
어떤 logic circuit을 그냥 사각형으로 단순화하여 보여주고 있고,
input으로는 A, B, C가 들어가고, output으로 f가 나오고 있다.
우리는 (b)와 같이 A, B, C와 f, f'의 관계를 truth table을 만들어 볼 수 있다.

우리는 이 logic circuit을 AND와 OR gate를 이용하여 나타내고 싶다.
그러기 위해서는 이 logic circuit을 어떤 boolean expression으로 나타낼 수 있어야 한다.
여기에 truth table을 이용하게 되는 것이다.

Truth table을 살펴보면 ABC가 각각 011, 100, 101, 110, 111일 경우에만 f = 1의 값을 갖는다.
다시말해서 ABC가 011 이거나 100 이거나 ... 111 인 경우에 f = 1을 갖는다.
각각의 경우에서 A = 0 이고, B = 1 이고, C = 1 이어야 한다.
즉, 여기서 AND와 OR를 사용할 수 있는 힌트가 생기는데,
ABC가 011인 것을 우리는 A'BC 라고 나타낼 수 있는 것이다. 
마찬가지로 100을 AB'C' 로 나타낼 수 있다.
이러한 항들을 서로 OR operation을 이용하면, 최종적으로 f는 다음과 같이 나타낼 수 있다.

f = A'BC + AB'C' + AB'C + ABC' + ABC

이런 식을 우리는 지금까지 배운 theorem을 바탕으로 simplify할 수 있다.
AB'C' + AB'C = AB' 이고, ABC' + ABC = AB 이므로,
f = A'BC + AB' + AB가 되며, AB' + AB = A이므로 f = A'BC + A 가 된다.
우리는 이전에 X'Y + X = X + Y 임을 배웠으므로, 최종적으로는
f = A + BC 가 된다.
f를 OR와 AND gate로 나타내면 아래와 같다.

지금까지의 예가 sum-of-products 라면 우리는 f를 product-of-sums로 나타내 볼 수도 있다.
이 경우에는 1을 만들어내는 경우가 아니라 0을 만들어내는 경우에 주목할 필요가 있다.
Truth table을 살펴보면, 0을 만들기 위해서는 A, B, C가 모두 0이거나 C만 1이거나, B만 1이어야 한다.
여기서는 '~이거나'의 의미를 OR operation이 아닌 AND operation으로 나타내야 한다.
이유는 간단하다. 다음 명제를 생각해보자.

A + B + C 가 0이기 위해서는 A, B, C가 모두 0이어야 한다.

즉, A = 0 and B = 0 and C = 0 이어야 하는데, 위 식에서는 OR operation인 '+'가 사용되었다.
한편 ABC = 0이 되려면, A, B, C 중 하나만 0이 되면 된다.
두 가지 operation의 사용이 그 의미와는 정반대로 사용되고 있는 것을 이해하고 있어야 한다.
그렇다면 f는 다음과 같이 쓸 수 있다.

f = (A + B + C)(A + B + C')(A + B' + C)

여기서도 마찬가지로 f를 간단히 할 수 있는데, 결론은 위에서 나온 f = A + BC가 된다. 직접 해보라.

어떻게 f가 나올 수 있는지 이해가 안된다면, 다음의 방법을 써 볼 수 있다.
Sum-of-products 방법을 이용해서 이번엔 f 대신 f'를 나타내 보자. 그러면,

f' = A'B'C' + A'B'C + A'BC'

가 된다. 여기서 (f')' = (A'B'C' + A'B'C + A'BC')' 를 하면
DeMorgan's law 에 의하여 결국엔 product-of-sums의 식이 나온다.