[Boolean Algebra] The Consensus Theorem

정의

XY + X'Z + YZ =  XY + X'Z

어떤 식이 위와 같은 형태를 띄고 있을 때, redundant term (필요없는 항) YZ를 소거할 수 있다.
이러한 항을 consensus term 이라고 한다.
증명은 아래와 같다.

이전의 simplification skill 관련 포스트의 맨 마지막 부분에
multiplying out과 factoring에 활용할 수 있는 유용한 방법에 대해서 설명하고 있다.
거기에 있던 식을 가져와 약간 변형시켜 보면 (X' + Y)(X + Z) 가 되는데, 이것을 무턱대고 풀어보면
X'X + X'Z + XY + YZ 가 된다. X'X = 0이므로 소거되버리지만 YZ가 남는다.
이 때 남아버린 YZ를 소거시킬 수 있는 방법이 바로 the consensus theorem인 것이다.
이 정리를 제때 적용시키려면 형태를 잘 기억해 두는 것이 좋다.

한편, product-of-sums에서도 이 법칙을 비슷하게 적용할 수 있다. 

(X + Y)(X' + Z)(Y + Z) =  (X + Y)(X' + Z)

맨 끝에 있던 (Y + Z)가 사라졌다.
증명은 아래와 같이 간단히 가능하다.
(X + Y)(X' + Z)(Y + Z) =  (XZ + X'Y)(Y + Z) = XYZ + XZ + X'Y + X'YZ = YZ + XZ + X'Y = XZ + X'Y 
이제 이 정리를 직접 적용해 보도록 하자.

예제 1

A'C'D + A'BD + BCD + ABC + ACD'

BCD의 왼쪽과 오른쪽에 A'BD와 ABC가 보인다.
B를 공통으로 가지고 있으므로 그것을 제외하면 A'D 와 AC, 즉 the consensus theorem을 적용시킬 수 있다.
따라서 BCD는 consensus term이 되어 삭제가 되고, 식은 A'C'D + A'BD + ABC + ACD' 으로 쓸 수 있다. 
하지만 이 이상은 the consensus theorem으로 소거가 불가능하다.

다시 처음으로 돌아와서 식을 다시 살펴보면 A'BD는 A'C'D와 BCD를 이용해 소거가 가능하고,
ABC는 BCD와 ACD'를 이용해 소거할 수 있다.
최종적으로 식은 A'C'D + BCD + ACD' 로 간단히 할 수 있게 된다.

어떤 경우에는 없던 항을 새로 만들어서 간단화 할 수도 있다. 예제 2를 보자.

예제 2

ABCD + B'CDE + A'B' + BCE'

당장 봐서는 소거할 수 있는 항이 잘 보이지 않는다. 
우리는 여기에 ABCD와 B'CDE로 부터 새로운 항, 즉,  consensus term을 새로 만들어 내려고 한다.
공통된 요소는 CD이고 A, E를 각각 가지고 있으므로, ACDE가 consensus term이 될 수 있겠다.
식을 다시 써보면,

ABCD + B'CDE + A'B' + BCE' + ACDE

위와 같이 쓸 수 있다. 이제 다시 식을 찬찬히 살펴보면, 
A'B'와 ACDE를 통해 B'CDE를 소거할 수 있고,
BCE'와 ACDE를 통해 ABCD를 소거할 수 있음을 알 수 있다.
최종적으로 A'B' + BCE' + ACDE 가 남는다.

위와 같이, 기존에 없던 consensus term을 되살려서, 다른 term들을 소거할 수도 있다.
이것이 가능하려면 특별한 방법이 있다기 보다는,
the consensus theorem을 사용할 수 있는지에 대한 여부를 잘 살펴보는 수밖에 없다.