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

카르노맵 문제 풀기

by 지식id 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로 묶어 주기만 하면 정답이 나오는 것이다.

반응형

댓글