메뉴
[Boolean Algebra] Simplification Skills

2012. 2. 9. 01:26

Simplifying Theorem

\begin{array}{rlll} XY + XY' &=& X&(1)\\ (X + Y)(X + Y') &=& X&(2)\\ X + XY &=& X &(3)\\ X(X + Y) &=& X&(4)\\ (X + Y')Y &=& XY&(5)\\ XY' + Y &=& X + Y &(6)\end{array}


어떤 expression이 좌변과 같은 형태인 경우에 우변으로 간단하게 바꿀 수 있다.
(1), (2), (5)의 경우에는 앞서 배웠던 associative / distributive law를 이용하면 간단히 증명된다.
나머지의 경우는 다음과 같이 증명된다.

\\ \begin{array}{lrll} (3)&X+XY&=&X\cdot1 + XY \\&&=&X(1+Y) \\&&=&X\cdot 1 \\&&=&X \end{array} \\\\\\ \begin{array}{lrll} (4)&X(X+Y)&=&XX+XY \\&&=&X+XY \\&&=&X \end{array} \\\\\\ \begin{array}{lrll} (6)&Y+XY'&=&(Y+X)(Y+Y') \\&&=&(Y+X)1 \\&&=&Y+X \end{array}


이러한 법칙들은 다양하게 이용할 수 있는데,
보통 복잡해 보이는 식들도 치환법과 위의 법칙을 함께 사용하면 매우 쉽게 정리된다.
몇 가지 예제를 살펴보자.



Simplifying Examples

Z = A'BC + A'


X = A', Y = BC 로 치환하면,
Z = XY + X 와 같이 나타낼 수 있으므로, 위의 (3)번 식을 적용할 수 있다. 즉
Z = X = A' 로 간단히 할 수 있다.



Z = (A + B'C + D + EF){A + B'C + (D + EF)'}


X = A + B'C, Y = D + EF로 치환하면
Z = (X + Y)(X + Y') = X = A + B'C 가 된다.



Z = (AB + C)(B'D + C'E') + (AB + C)'


X = AB + C, Y = B'D + C'E'로 치환하면
Z = XY + X' = (X + X')(Y + X') = Y + X' 이므로 
Z = B'D + C'E' + (AB + C)' 가 된다.



Multiplying Out

여기서는 간단히 곱하는 방법과 다시 인수분해 하는 방법에 대해 다룰 것이다.
먼저 곱하는데에도 역시 치환과 위에서 배운 simplifying skill을 사용하면 된다.
예를 들어

(A + BC)(A + D + E)


겹치는 항인 A는 굳이 치환할 필요가 없고 나머지를 치환(X = BC, Y = D + E)하여 생각해보면,
(A + BC)(A + D + E) = (A + X)(A + Y) = A + XY = A + BC(D + E) = A + BCD + BCE
와 같다. 치환을 이용하지 않고 곧이곧대로 계산하는 경우에 항이 6개가 나와 매우 복잡해진다.



Product-of-sums

ABC + DEF + GH는 다항식이면서 sum-of-products 즉, 곱셈(AND)으로 이루어진 항들의 합이다.
그 반대의 형태는 (A + B + C)(D + E + F)(G + H) 와 같은 식은 덧셈(OR)으로 이루어진 항들의 곱이다.
우리는 이런 형태를 product-of-sums라고 부른다.

ABC(D+E) 같은 형태도 product-of-sums라고 할 수 있다.
하지만 ABC(D+EF)의 경우는 EF가 제대로 factoring 되지 않은 상태이므로 product-of-sums 라고 할 수 없다.
동시에 sum-of-products도 되지 못한다.

product-of-sums로 변형하는 이유는 gate를 더 적게 사용할 수 있는지를 생각해 본다든지,
혹은 AND보다 OR를 더 많이 사용하는것이 유리할 경우 라든지,
혹은 기타 어떠한 스펙이나, 논리적인 간편함을 얻기 위해 사용되기도 한다.
이런 product-of-sums를 얻기 위해서는 factoring 하는 방법에 대해 알아볼 필요가 있다.




Factoring

반면 factoring(인수분해)은 치환을 먼저 할 수 없다.
즉, 위에서 배운 simplifying skill을 먼저 사용해야 한다.
몇 가지 예제를 살펴보자.



A + B'CD


A + B'CD = (A + B')(A + CD) = (A + B')(A + C)(A + D)
앞에서 배웠던 distributive law를 반복해서 이용하면 위와 같은 결과를 얻는다.



AB' + C'D


여기서도 마찬가지로 distribute law의 반복사용이 계속된다.
AB' + C'D = (AB' + C')(AB' + D) = (A + C')(B' + C')(A + D)(B' + D)



C'D + C'E' + G'H


먼저 distributive law를 사용하면
C'D + C'E' + G'H = C'(D + E') + G'H

여기에 다시 distributive law를 사용하면
C'(D + E') + G'H = (C + G'H)(D + E' + G'H)

나머지 부분은 G'H를 분해하는 것이므로 역시 계속 distributive law의 반복사용이다.
최종적으로는 (C' + G')(C' + H)(D + E' + G')(D + E' + H) 가 된다.
이는 product-of-sums 이다. 



More Useful Skill for Multiplying Out and Factoring

좌변이 다음과 같은 형태의 expression인 경우 우변과 같이 simplify가 가능하다.

(X + Y)(X' + Z) = XZ + X'Y
AB + A'C = (A + C)(A' + B)

첫번째 식의 좌변을 잘 보면, X와 Z가 가장 바깥에 있다.
이것을 서로 곱한다. 마찬가지로 안쪽에 있는것 끼리 묶어서 곱한다.
그리고 나서 더하면 우변이 되는데, 그 결과는 서로 같다. 
왜 같아지는지 증명하려면 X가 0일때와 X가 1일 경우를 나누어서 직접 대입해 보면 된다.
직접 대입한 결과는 모두 참이 되므로, 결과적으로 X에 어느것이 오든 위의 식은 참이 된다.

밑에 AB + A'C의 경우도 마찬가지다.
바깥쪽에 있는것 과 안쪽에 있는 것 끼리 더한 다음 곱하면 factoring이 끝난다.

두 식 모두 형태를 잘 보면 중복되는 variable이 서로 complement 관계를 이루고 있으며,
나머지 variable은 서로 다를 때, 위 공식을 적용시킬 수 있다.

이러한 공식을 모르는 경우, 그냥 곧바로 식을 factoring하는것이 불가능 하고,
multiplying out의 경우에는 4개의 항이 나오게 되는데, 그 중간 항을 삭제하는 것이 힘들다.
따라서 위 공식을 반드시 기억해 두도록 하자.