유용성 지금까지의 simplification 방법은 물론 유용하긴 하지만 일반적으로 적용하기 어려운 것이 사실이다. 좀 더 간단하게 simplify하기 위한 방법 중 하나가 Karnaugh map이다. Variable이 2~5개 정도인 expression이나 equation에 대해서 상당히 유용한 방법이다. 해야할 일은 Karnaugh map을 만들고, 'looping' 과정을 통해서 minimum solution을 얻는 것이다. 그 과정이 몇 줄에 걸쳐서 식을 쓰는 것에 비해 비교적 간단하기 때문에 자주 사용되며, Boolean algebra를 이용해 얻은 식이 minimum solution인지 확인하는데 쓰이기도 한다. 모양 위 그림은 2개의 variable에 대해 Karnaugh map의 틀을 그려..

Methods for Determining if an Equation is Valid 모든 variable combination에 대해서 어떤 equation이 유효한지를 알아보는 방법은 여러가지가 있다. 여기서 지금까지 배운 내용을 바탕으로 몇 가지를 정리해보면, 1. Truth table을 만들고, 모든 variable combination에 대해서 좌우변이 동일한 값을 갖는지 확인한다. 이 방법은 variable의 개수가 늘어날 수록 검사해야 하는 경우의 수가 기하급수적으로 늘어나게 되므로, 상당히 비효율적인 방법이라고 할 수 있다. 2. 지금까지 배운 여러 theorem을 이용하여 equation의 한 변을 다른 한변과 동일하게 만든다. 3. 양변을 개별적으로 simplify해서 같은지 확인한다...

정의 XY + X'Z + YZ = XY + X'Z 어떤 식이 위와 같은 형태를 띄고 있을 때, redundant term (필요없는 항) YZ를 소거할 수 있다. 이러한 항을 consensus term 이라고 한다. 증명은 아래와 같다. 이전의 simplification skill 관련 포스트의 맨 마지막 부분에 multiplying out과 factoring에 활용할 수 있는 유용한 방법에 대해서 설명하고 있다. 거기에 있던 식을 가져와 약간 변형시켜 보면 (X' + Y)(X + Z) 가 되는데, 이것을 무턱대고 풀어보면 X'X + X'Z + XY + YZ 가 된다. X'X = 0이므로 소거되버리지만 YZ가 남는다. 이 때 남아버린 YZ를 소거시킬 수 있는 방법이 바로 the consensus theo..

Exclusive-OR (XOR) Exclusive-OR, 이하 XOR은 위와 같이 정의된다. Operator의 형태는 덧셈기호를 원으로 둘러 싼 모습을 하고 있다. 같은 숫자일 경우에는 0을, 서로 다른 숫자일 경우에는 1을 나타낸다. XOR gate의 모양은 위와 같다. OR gate의 왼쪽에 둥근 호를 더해놓은 형태를 하고 있다. 한편, XOR operator는 아래와 같이 풀어 쓸 수 있다. 위 식에 대한 증명은 생략한다. XOR에 대해서는 다음과 같은 유용한 공식을 사용해 볼 수 있다. Basic Theorems of XOR 대부분의 공식은 truth table을 이용하거나, 혹은 위에서 언급한 관계식을 이용하면 증명 된다. Equivalence Operation (Exclusive NOR; X..

DeMorgan's Laws (X + Y)' = X'Y' (XY)' = X' + Y' (X' + Y')' = XY (X'Y')' = X + Y (A + B + C + D + E + F + … )' = A'B'C'D'E'F' … ABCDEF … = A' + B' + C' + D' + E' + F' + … NOT operation을 통해서 OR operation과 AND operation을 서로 맞바꿀 수 있다. 우리는 이를 complement operation이라고 부르기도 한다. OR이나 AND operator가 여러개 붙어있더라도 모두 적용된다. 몇 가지 예제를 살펴보자. Finding a Complement (A' + B)C' '위 expression의 complement를 찾아라'라는 문제는 곧 [..

Simplifying Theorem 어떤 expression이 좌변과 같은 형태인 경우에 우변으로 간단하게 바꿀 수 있다. (1), (2), (5)의 경우에는 앞서 배웠던 associative / distributive law를 이용하면 간단히 증명된다. 나머지의 경우는 다음과 같이 증명된다. 이러한 법칙들은 다양하게 이용할 수 있는데, 보통 복잡해 보이는 식들도 치환법과 위의 법칙을 함께 사용하면 매우 쉽게 정리된다. 몇 가지 예제를 살펴보자. Simplifying Examples Z = A'BC + A' X = A', Y = BC 로 치환하면, Z = XY + X 와 같이 나타낼 수 있으므로, 위의 (3)번 식을 적용할 수 있다. 즉 Z = X = A' 로 간단히 할 수 있다. Z = (A + B'C..