[Boolean Algebra] DeMorgan's Law

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를 찾아라'라는 문제는 곧 [(A' + B)C']' 를 간단히 하라는 문제과 같은 의미다.
여기서는 DeMorgan's Law를 반복적으로 사용하면 된다.

[(A' + B)C']' = (A' + B)' + C = AB' + C

위와 같이 변환된다.
변환 과정에서 OR 또는 AND를 바꾸지 않고 그대로 남겨놓지 않도록 한다.

Complement Operation only to Single Variables

[(AB' + C)D' + E]'

위의 식은 complement operation이 전체적으로 둘러쌓여있다.
이 식을 각 하나의 variable에만 complement operator가 붙어있도록 하려면
DeMorgan's Law를 사용해야 한다.

[(AB' + C)D' + E]' = [(AB' + C)D']'E' = [(AB' + C)' + D]E' = [(AB')'C' + D]E' = [(A'+ B)C' + D]E'

하나의 variable에만 prime이 붙어있으며 괄호 전체에는 붙어있지 않은 형태가 된다.