부울 대수 법칙
논리 회로를 구성하기 위해서 진리표를 보고 "직감적으로" 구성하는 방식으로 논리 회로를 설계하는 것은 무리가 있다. 간단한 논리 회로일 때는 별 문제가 없겠지만, 복잡한 회로가 된다면 최적화 문제 등에 부딪히게 되기 때문이다. 이때 사용되는 "부울 대수"는 하나의 명제가 참 또는 거짓임을 판단하는 데 사용되는 수학적 방법이다.
| 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) \\[5pt] &= AA' + AB \\[5pt] &= 0 + AB \\[5pt] &= AB \end{align} $$
TIP!
위의 결과를 보면 알 수 있듯이, 얼핏 보았을 때 간단한 식도 부울 대수 법칙을 활용하여 식을 전개하며 정리하면 생각치도 못하게 간단한 식을 얻을 수 있다.
이것이 바로 논리식 간소화의 장점이다. 이 논리식 간소화를 통해 줄어든 게이트의 개수는 2개인데, 논리식이 길어지고 회로가 복잡해지면 논리식 간소화는 빛을 발하게 될 것이다.
