드 모르간의 정리

                                                                                                  출처 : 위키피디아

 

 

 

 

 

집합에서 드 모르간의 정리는 집합의 연산에서 자주 쓰이는 정리입니다.

 

 

드 모르간의 정리 (De Morgan's theorem)   임의의 두 집합 A, B에 대해서   ,

 

 

 

처음 드 모르간의 정리를 외울때 c로 표현되는 여집합 기호가 괄호 안으로 들어가면서

 

괄호안의 집합에 여집합 기호 c를 붙이고

 

합집합은 교집합으로 ( ∪ => ∩ ),

 

교집합은 합집합으로 ( ∩ => ∪ ) 바꾼다고 외운 기억이 납니다. ^^

 

 

 

첫번째 식부터 보도록 하겠습니다.

 

 

 

등호 왼쪽의 는 ( A ∪ B )의 여집합 즉 ( A ∪ B )에 들어가지 않는 원소들의 집합이므로

 

벤 다이어그램으로 다음과 같이 나타나게 됩니다.

 

 

 

 

 

A에도 포함되지 않고 B에도 포함되지 않아야 하죠?

 

즉 A의 여집합과 B의 여집합의 교집합이 되는 것이죠

 

 

 

 

 

 

 

두번째 식도 같은 방식으로 이해할 수 있습니다.

 

 

등호 왼쪽의 는 ( A ∩ B )의 여집합

 

즉 A와 B에 동시에 포함되는것은 아닌 원소들의 집합이 됩니다.

 

 

 

 

 

즉 A나 B 둘중 한군데만 포함되지 않으면 되므로

 

A의 여집합에 포함되거나 B의 여집합에 포합되면 됩니다.

 

 

 

 

 

 

 

조금만 응용을 해보겠습니다.

 

  <= 이건 어떻게 풀까요?

 

 

이런 경우 가장 바깥에 있는 괄호부터 드 모르간의 정리를 적용하면 됩니다.

 

 

가장 바깥이 있는 괄호를 드 모르간의 정리를 이용해서 벗겨내면

 

<== 이렇게 됩니다.

 

 

그리고 두번째 괄호도 벗겨내면

 

<== 이렇게 됩니다. 괄호가 벗겨지진 않았군요 ^^;;

 

 

 

 

 

처음식 을 다시보니 가장 바깥에 있는 괄호 안에 분배법칙을 쓸수가 있겠군요

 

 

그러면 분배법칙을 먼저 사용해도 같은 결과가 나올까요?

 

 

  <= 여기서 분배법칙을 쓰면

 

  <= 이렇게 되겠죠? 여기에 드 모르간의 정리를 사용하면

 

  <= 이렇게 됩니다. 다시한번 드 모르간의 정리를 사용하면

 

  <= 여기에 다시한번 분배법칙을 사용하면

 

  <= 같은 결과가 나옵니다.