설찬범의 파라다이스
글쓰기와 닥터후, 엑셀, 통계학, 무료프로그램 배우기를 좋아하는 청년백수의 블로그
카노맵 (1)
카르노 맵(Karnaugh map)과 짝사랑
반응형



1

대학생 철민이는 같은 과 영희를 짝사랑한다.

그래서 영희와 같이 있고 싶다.

철민, 영희, 민수는 같이 뭉쳐다니는 사이인데,

철민이는 영희를 좋아하는 마음이 커지다 보니

영희가 있을 때만 점심을 같이 먹는다.

민수만 있으면 같이 안 먹고,

영희가 있으면 민수가 있든 없든 같이 식사를 하는 것이다.


철민이의 속내를 모르는 민수는

철민이가 왜 이날은 같이 점심을 먹고 저날은 안 먹는지

아리송할 뿐이다.




논리식을 간소화하는 카르노 맵




카르노 맵(카노 맵, Karnaugh map)은 K맵, KM 등으로 불리며,

모리스 카르노가 발표한 논리식 축약 방법이다.


예를 들어 이런 진리표가 있다고 하자.




잘 보면 C는 B로만 결정된다.

(B가 1이면 C는 0, B가 0이면 C는 1)



그러니 논리식에 A가 필요가 없으며,

만약 회로로 이걸 만들어야 한다면

A는 넣지 않아도 되므로 부품값과 전기세를 아낄 수 있다.




카르노 맵을 그리는 규칙


1. 바로 이웃한 칸들을 묶는다.

2. 묶는 칸 수는 2의 제곱수(2, 4, 8...)이어야 한다.

3. 묶는 칸 모양은 직사각형이어야 한다.

4. 묶은 칸들을 더한다. 이때 변하지 않는 변수만을 남기며, 0일 때는 반대 값으로 더한다.


이제 민수의 호기심을 해결해 주자.

'민수가 밥을 먹음'을 A라 하고

'영희가 밥을 먹음'을 B라 하고

'철민이가 이들과 밥을 먹음'을 C라 하자.

진리표는 다음과 같다.




이걸 카르노 맵으로 그리면 다음과 같다.







이 묶인 사각형에서 변하지 않는 값은 B다.

따라서 이 논리식은 이렇게 표현할 수 있다.


C = B





2

그 나이 대학생이 다 그렇듯이

철민이는 순간 짝사랑하는 자신이 부끄러워졌다.

안 그래도 어리둥절한 민수한테 들킬까봐 두려워진 철민이는

이제 그냥 민수와 영희, 둘 중 아무나 있어도 밥을 먹기로 했다.


진리표는 다음과 같다.




카르노 맵을 그리면 다음과 같다.




카르노 맵에서 사각형을 묶을 때, 공통으로 묶인 칸이 생겨도 상관은 없다.


하늘색 네모에선 B가 변하지 않으며

노란색 네모에선 A가 변하지 않는다.

따라서 논리식은 이렇게 표현된다.


C = A + B



3변수 카르노 맵




며칠 후 같은 과 주연이가 이 삼총사에 끼어들었다.

주연이는 영희의 소꿉친구였다.

철민이는 이 주연이한테 영희가 무얼 좋아하는지, 어떤 남자를 좋아하는지 물으면 좋을 것 같다고 생각했다.

다시 짝사랑이 불타오른 것이다.


그래서 철민이는 세 경우에만 점심을 먹기로 했다.

영희와 단 둘이 있을 때.

주연이와 단 둘이 있을 때.

영희와 주연이와 있을 때.


'세 변수에서 카르노 맵을 어떻게 그리지?'라고 생각할 수 있지만

생각보다 간단하다.

바로 한쪽 축에 두 변수를 같이 쓰면 된다.


A : 민수가 밥을 먹음

B : 영희가 밥을 먹음

C : 주연이가 밥을 먹음

D : 철민이가 밥을 먹음


그런데 보다시피 00, 01, 10, 11이 아니라

00, 01, 11, 10이다.

이것은 밑으로 가면서 한 변수만 변하게 해서

카르노 맵을 그릴 수 있기 위함이다.



초록색 네모에서는 B가 변하므로 버리고

하늘색 네모에서는 C가 변하므로 버린다.


따라서 논리식은 다음과 같다.

D = A'C + A'B



참고 

카르노 맵에서 칸을 묶을 때

지구본처럼 위아래가 연결된다고 생각한다.

따라서 이렇게 묶을 수도 있다.




'지구는 둥그니까, 자꾸 걸어 나가면~'


반응형
  Comments,     Trackbacks