2012. 2. 10. 20:39
Methods for Determining if an Equation is Valid
모든 variable combination에 대해서 어떤 equation이 유효한지를 알아보는 방법은 여러가지가 있다.
여기서 지금까지 배운 내용을 바탕으로 몇 가지를 정리해보면,
1. Truth table을 만들고, 모든 variable combination에 대해서 좌우변이 동일한 값을 갖는지 확인한다.
이 방법은 variable의 개수가 늘어날 수록 검사해야 하는 경우의 수가 기하급수적으로 늘어나게 되므로,
상당히 비효율적인 방법이라고 할 수 있다.
2. 지금까지 배운 여러 theorem을 이용하여 equation의 한 변을 다른 한변과 동일하게 만든다.
3. 양변을 개별적으로 simplify해서 같은지 확인한다.
4. 양변에 동일한 operation을 가해서 같아지는지 확인한다.
이때에는 양변에 가해지는 operation이 reversible해야 한다.
다시 말해서, multiplication과 같이 division의 개념이 존재하지 않는 operation의 경우에는 irreversible하므로,
양변에 동시에 가할 수 없는 operation이라고 할 수 있다.
(subtraction역시 정의되어 있지 않으므로 더하는 것도 불가능)
어떻게 보면 결론적으로는 지금까지 배운 스킬들 중,
적용 가능한 것들을 파악하고 올바른 위치에 사용해야 한다.
한편, Equation이 invalid하다는것을 증명하기 위해서는,
어떤 variable combination이 양변에서 다른 값을 갖는다는 것을 보여야 한다.
위에서 소개한 방법 2, 3에 대해서 다음과 같은 방법을 써 볼 수 있다.
1. 먼저 양변을 sum-of-products 또는 product-of-sums 로 변환한다.
2. 양변을 비교해서 어떤것이 다른지 본다.
3. 좌변이나 우변에 다른 변에 있는 항을 더한다.
4. 마지막으로 다른 변에 없는 항을 지워나간다.
기본적인 법칙과 정리를 숙지한 상태에서
여러번의 연습을 거치면 대략 어떤 식으로 식을 정리할 수 있을지에 대해 대략적으로 파악이 될 것이다.
흔히 범하게 되는 오류
x + y = x + z, then y = z?
위에서도 잠깐 언급되었던 문제인데, subtraction과 division이 있다고 착각하서 비롯되는 오류가 그것이다.
일반적인 algebra라면 위에 주어진 식은 참이 될 것이다.
Boolean algebra에서는 안타깝게도 적용되지 못한다. 반례를 하나만 들어보자.
x가 1인 경우라면, y, z가 어떤 값이 되든, 위 식 x + y = x + z는 참이 된다.
즉, y = 0, z = 1 이더라도 참이다. 다시말해서 y = z 는 x + y = x + z 가 되기에 충분한 조건이지만, 필요조건은 아니다.
xy = xz, then, y = z?
역시 마찬가지의 문제다. x = 0으로 놓으면 y, z에 뭐가 오든 상관없이 위 식은 참이 된다.
결론적으로, 양변에 같은 식이나 항이 온다고 해서 무턱대고 소거해 버려서는 안된다.
예제 1
다음이 성립하는지 보여라
A'BD' + BCD + ABC' + AB'D = BC'D' + AD + A'BC
좌변을 기준으로 생각하자.
우변에 있는 term들은 BC'D, AD, A'BC가 있다.
좌변의 term들을 잘 살펴보면 이러한 항을 만들어 낼 수 있음을 알 수 있는데,
A'BD'와 ABC'를 이용하면 BC'D'라는 consensus term을 만들어 낼 수 있다. 마찬가지로
A'BD'와 BCD를 이용하면 A'BC, BCD와 ABC'를 이용하면 ABD라는 consensus term을 만들어 낼 수 있다.
ABD는 우변에 없지만 ABD와 AB'D를 이용하면 AD를 만들 수 있다.
정리하면, 좌변은 A'BD' + BCD + ABC' + AD + BC'D' + A'BC 가 된다.
이제는 the consensus theorem을 소거에 이용할 때가 왔다.
목적은 AD + BC'D' + A'BC 이외의 다른 항을 소거해야 한다는 것이다.
A'BD'는 BC'D'와 A'BC를 이용해서, BCD는 AD와 A'BC를 이용해서,
마지막으로 ABC'는 BC'D'와 AD를 이용해서 소거를 할 수 있다.
좌변과 우변이 서로 같음을 알 수 있다.
따라서, equation은 valid하다.
예제 2
다음이 성립하는지 보여라.
여기서는 좌우변을 각각 simplify하는 방법을 사용하는데,
먼저 좌변을 살펴보면 A'BC'를 이용해서 A'BC'D를 소거할 수 있다. (X + XY = X)
괄호로 이루어진 부분을 multiplying out하면 ABC + A'C'D'를 얻을 수 있다. ((X + Y)(X' + Z) = XZ + X'Y)
마지막으로 A'C'D'와 BC'D는 the consensus theorem을 이용해 A'BC'를 소거할 수 있다.
최종적으로 ABC + A'C'D' + BC'D를 얻는다.
한편 우변은 조금 더 간단한데,
ABCD와 ABCD'는 ABC로 간단히 할 수 있다. (XY + XY' = X)
ABD는 BC'D와 ABC의 consensus term이므로 소거된다.
따라서 남는 것은 A'C'D + ABC + BC'D가 된다.
좌우변이 동일하다. 따라서 equation은 valid하다.