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이 붙어있으며 괄호 전체에는 붙어있지 않은 형태가 된다.


Posted by Nicatio

댓글을 달아 주세요

  1. 학생 2012.03.19 12:49  수정/삭제 댓글쓰기

    아 정말 이렇게 좋은 블로그가 있었다니ㅠㅠ
    only to single variables가 무슨 뜻인지 몰라서 과제 망할 뻔 했는데
    덕분에 살았어요!!!!
    감사합니다!!!

  2. 영찌 2012.04.16 18:21  수정/삭제 댓글쓰기

    드모르간의 법칙 증명을 찾고있는데여ㅜㅜ 방법 혹시 아시나요?? ㅜㅡㅡㅡㅡㅡㅡㅜ

    • Nicatio 2012.04.16 18:54 신고  수정/삭제

      여기서 배운 것만 가지고 설명하면,
      증명은 각각의 truth table을 통해 가능합니다.

      그렇지 않으면 sequent notation을 써서
      http://www.proofwiki.org/wiki/De_Morgan's_Laws_(Logic)
      와 같이 증명하는데, 참고해 보시기 바랍니다.
      다만 저는 sequent에 대해서는 자세히 배운적이 없어서 추가적인 설명이 어렵네요 ㅜㅜ

  3. 질문 2012.04.25 00:52  수정/삭제 댓글쓰기

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

    여기서 C'은 C로 안바뀌나요??