본문 바로가기
IT 이론/컴퓨터구조

카르노맵 문제 풀기

by 아이들링 2016. 10. 12.

가장 많이 나오는 문제는 카르노맵을 주고 식을 도출해내는 문제이다. 역으로 식을 주고 카르노맵을 그리는 문제도 나오지만 둘중 하나만 이해해도 카르노맵과 관련된 문제는 다 풀 수 있다. 우선은 카르노맵을 식으로 풀어내는 것만 보자. 아래 3가지는 꼭 기억하고 넘어가야 한다.


  1) 카르노맵의 가로축은 00 01 11 10 순서이다.

     * 그레이코드를 이용한 것인데 혹시 그려야 될 경우도 있기 때문에 언급해 둔다.

  2) 카르노맵의 맨 좌측과 우측은 지구본 처럼 이어진다. 반지처럼, 밴드처럼 이어져 있다.

  3) 2의 승수로 같은 값이 연속될 경우에만 묶을 수 있다.


말이 어려워 보여도 굳이 이해하려고 애쓰지 말자. 위 공식을 보면서 아래 예제만 몇개 풀어보면 된다.




이렇게 묶어주면 된다. 2개 또는 4개 단위로 묶는다. 물론 2의 승수라고 했으므로 8개나 16개로도 묶을수 있지만 그런 문제는 나올수 없다.

3개가 연속될 경우 2개로 나눠서 묶어야 한다. 양 끝을 이어서 묶을 수도 있다. 

이정도 예제면 이제 어떻게 묶어야 하는지는 이해가 될 것이다. 그럼 이제 이를 어떻게 읽는지 알아보자


카르노 맵에서 숫자는 표에 있는 알파벳을 의미한다. 1은 그대로이고 0은 NOT을 붙인다. 즉 01 은 B'C 라는 뜻이다. 표를 아예 고쳐 써 보면 아래와 같다.


처음부터 이렇게 동그라미를 쳐 놓고 저렇게 알파벳을 써 놓고 풀기 시작 하는 것이 편하다.


묶음 안의 요소들은 AND로 묶는다.

묶음 끼리는 OR로 묶는다.

단, 0과 1에 모두 해당하는 알파벳은 제외한다. 즉, X·X'라고 적히는 것들은 1로 생각하고다 지워주면 된다.


아래쪽 길다란 묶음은 A·B'·C'·B'·C·B·C·B·C' 이렇게 구성요소들을 죽 써 주면 된다. 여기서 B·B'는 1이므로 이렇게 1이 되는 것들을 정리해 주면

A밖에 안남는다. 그래서 굳이 죽 써 놓고 지울 필요도 없이 지워질 애들을 빼고 써 주면 편하다.


아래쪽 길다란 묶음을 해결 했으니 잘린 묶음을 처리 해 보자. 여기서도 A·A'는 1이므로 굳이 적을 필요 없다. B·B'도 보이는데 이것도 마찬가지. 결국 C'·C' 즉 C'밖에 남는 것이 없다. 굳이 풀이 과정을 쓰자면

A·A'·B'·C'·B·C' = B'·C'·B·C' = C'·C' = C' 이다.


결국 길쭉한 묶음의 결과는 A이고 잘린 묶음의 결과는 C'이다. 묶음끼리는 OR로 묶는다고 했으므로 결국 답은 A+C' 이다.


결국 이렇게 2개 또는 4개씩 묶어 주고,

묶음 하나하나 구성요소들을 죽 AND로 써서 풀어주고

묶음끼리 OR로 묶어 주기만 하면 정답이 나오는 것이다.

댓글8

  • dd 2017.02.17 12:34

    덕분에 이해하고 넘어갑니다!! 감사해요
    답글

  • 개쩔었다설명 2017.06.18 23:32

    개쩔었습니다 스승님 설명 굿이네요
    답글

  • 멋짐 2017.08.04 20:15

    문제집에서 설명을 꼬아 해놔가지고 뭔소린가 하고 있었는데.. 감사합니다.
    답글

  • 2017.09.30 14:52

    비밀댓글입니다
    답글

    • 아이들링 2017.10.09 11:35 신고

      6번의 경우 4개를 한꺼번에 묶으면서 자연스럽게 아래위로도 관계가 형성이 되었습니다. 하지만 1번 같은 경우 가로로 2묶음을 하다 보니 중간에 세로로 겹치는 부분은 묶이지 않은 것입니다.
      가로로든 세로로든 2의 승수개 이상 모여 있는데 한번이라도 묶이지 않은 모든 경우를 다 묶어 준다고 생각 하시면 될것 같습니다.

  • 665 2018.03.09 14:01

    와 감사합니다!!
    답글

  • ㄷㄷㄷ 2018.05.11 09:37

    교재로는 이해가 잘 안됐는데 감사해요!
    답글

  • 안졸리 2018.06.26 21:38

    에이*에이바=1
    보수의 법칙 따르면 에이*에이바=0 아닌지요
    혹시 제가 잘 모르는 부분이 있어 도움 부탁드립니다,
    왜 1이 되는지 여쭤봐도 될까요?
    답글