논리 회로를 구성하기 위해서 진리표를 보고 "직감적으로" 구성하는 방식으로 논리 회로를 설계하는 것은 무리가 있습니다. 간단한 논리 회로일 때는 별 문제가 없겠지만, 복잡한 회로가 된다면 최적화 문제 등에 부딪히게 되기 때문입니다.
"부울 대수"는 하나의 명제가 참 또는 거짓임을 판단하는 데 사용되는 수학적 방법인데, 이 부울 대수의 규칙을 통해 최적의 논리 회로를 설계할 수 있습니다. 지금부터 부울 대수 법칙에 대해서 알아보도록 하겠습니다.
부울 대수 법칙
부울 대수 법칙은 생각보다 굉장히 많습니다. 중고등학교 수준의 수학(집합, 명제 등)을 할 줄 안다면 쉽게 이해할 수 있습니다.
| Commutative (교환 법칙) |
1) $x + y = y + x$ 2) $x * y = y * x$ |
| Associative (결합 법칙) |
1) $(x + y) + z = z + (y + z)$ 2) $(x * y) * z = z * (y * z)$ |
| Distributive (분배 법칙) |
1) $x + (y * z) = (x + y) * (x + z)$ 2)$x * (y + z) = (x * y) + (x * z)$ |
| Identity (항등 법칙) |
1) $x + 0 = x$ 2) $x + 1 = 1$ 3) $x * 0 = 0$ 4) $x * 1 = x$ |
| Complement (보수 법칙) |
1) $x + x' = 1$ 2) $x * x' = 0$ |
| Idempotent Property (멱등 법칙) |
1) $x + x = x$ 2) $x * x = x$ |
| Absorption Theorem (흡수 법칙) |
1) $x + (x * y) = x$ 2) $x * (x + y) = x$ |
| De Morgan's Law (드모르간 법칙) |
1) $(x * y)' = x' + y' $ 2) $(x + y)' = x' * y' $ |
| Complement Theorem (부정 법칙) |
1) $(x')' = x$ 2) $1'= 0$ 3) $0'= 1$ |
이 포스팅에서는 각 규칙의 식들이 성립함을 증명하는 것은 하지 않도록 하겠습니다.
간단하게 직접 진리표를 작성하며 식의 만족함을 확인해보는 것을 추천드립니다.
논리식의 간소화
지금까지 살펴본 부울 대수 법칙은 결국 "논리 회로의 최적화"를 위한 것입니다. 논리 회로의 최적화가 필요한 이유는 실제로 회로가 간단하게 되면 사용하는 게이트의 숫자가 줄어들고, 그것은 논리 회로를 설계할 때 드는 비용에도 많은 영향을 끼치게 됩니다. 그러면 최적화가 잘 될 수록 논리 회로를 설계할 때 드는 비용도 많이 줄어들게 됩니다.
논리 회로의 최적화는 "논리식의 간소화"로부터 비롯됩니다. 결국 부울 대수 법칙을 배우는 이유는 바로 "논리식의 간소화"를 진행하기 위함입니다. 논리식의 간소화 과정을 식을 통해서 알아보겠습니다.
$$ F = A(A' + B) $$
라는 식이 있다고 합시다. 이 식은 얼핏 보았을 때 최적화에 큰 문제를 끼치는 것 같아 보이지는 않습니다. 그러니 이 식을 부울 대수 법칙을 활용하여 전개하고 식을 전개한다면 생각치도 못한 식이 나오게 됩니다.
$$ \begin{align}
F &= A(A' + B) \\ &= AA' + AB \\ &= 0 + AB \\ &= AB
\end{align} $$
이 식의 결과를 보면 알 수 있듯이 얼핏 보았을 때 간단한 식도 부울 대수 법칙을 활용하여 식을 전개하며 정리하면 생각치도 못하게 간단한 식을 얻을 수 있습니다. 이것이 바로 논리식 간소화의 장점입니다. 이 논리식 간소화를 통해 줄어든 게이트의 개수는 2개입니다. 논리식이 길어지고 회로가 복잡해지면 논리식 간소화는 빛을 발하게 될 것입니다.
