[Boolean Algebra] Basic Laws
2012. 2. 8. 23:44
Basic of Basic
이 포스트에서는 boolean algebra의 가장 기초적인 법칙들에 대해서 다루도록 하겠다.
먼저 다음에 소개될 법칙들은, 그 중에서도 가장 기본적인 법칙으로
그 증명은 그냥 X에 0 또는 1을 넣는 것이면 된다. (여기서 부가적인 증명은 하지 않는다.)
또한 X 대신 어떤 expression을 넣는다 하더라도 아래의 법칙들은 모두 true이다.
Operations with 0 and 1
X + 0 = X
X + 1 = 1
X · 0 = 0
X · 1 = X
Idempotent Laws
X + X = X
X · X = X
Involution Law
(X')' = X
Laws of Complementarity
X + X' = 1
X · X' = 0
Commutative Law
XY = YX, X + Y = Y + X
일반적인 교환법칙과 동일한 결론을 얻는다.
즉 AND나 OR operation은 각각 앞 뒤 operand의 순서를 맞바꾸더라도 결과에 변화가 없다.
Associative Law
(XY)Z = X(YZ) = XYZ
(X + Y) + Z = X + (Y + Z) = X + Y + Z
마찬가지로 결합법칙 역시 일반적인 algebra와 동일한 결과를 얻게 된다.
증명을 하려면 truth table을 만들어보면 된다.
Distributive Law
X(Y + Z) = XY + XZ
X + YZ = (X + Y)(X + Z)
첫번째 줄은 일반적인 분배법칙과 동일하다. 증명방법은 마찬가지로 truth table이다.
하지만, 두번째의 경우는 그렇지 못하다. 이 법칙에 대해서는 다음과 같은 증명이 가능하다.
여기서 나온 distributive law는 이후에도 자주 사용되므로 꼭 기억해두길 바란다.