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이다.
하지만, 두번째의 경우는 그렇지 못하다. 이 법칙에 대해서는 다음과 같은 증명이 가능하다.

\begin{array}{rll} \\(X+Y)(X+Z)&=X(X+Z) + Y(X+Z)& \\&=XX+XZ+YX+YZ& \\&=X+XZ+XY+YZ&(\because~Idempotent~Laws) \\&=X\cdot 1+XZ+XY+YZ&(\because~Operations~with~0~and~1) \\&=X(1+Z+Y)+YZ& \\&=X\cdot 1+YZ &(\because~Operations~with~0~and~1) \\&=X+YZ &(\because~Operations~with~0~and~1)  \end{array}


여기서 나온 distributive law는 이후에도 자주 사용되므로 꼭 기억해두길 바란다.

Posted by Nicatio

댓글을 달아 주세요

  1. skj 2013.04.09 18:50  수정/삭제 댓글쓰기

    아 분배법칙 이유가 항상 궁금했는데 정말 감사합니다. 여기 정말 정리 잘되어있네요!!

  2. 서영현 2014.03.07 15:39  수정/삭제 댓글쓰기

    저도 분배법칙이 왜 이렇게 되나 싶어서 찾다가 여기서 명쾌하게 해결하고 갑니다. 감사합니다~!

  3. 김차영 2014.03.10 20:44  수정/삭제 댓글쓰기

    정말감사합니다 분배법칙에 관해 궁금했었는데 잘 설명되어있네요