부울함수 간소화(1)

카르노 도표를 이용해 간소화를 해보자.

 

카르노 도표를 이용하면 보통 네 개의 변수를 가진 부울함수에 대해 사용한다. 

 

변수가 더 많아지는 경우는 퀸-맥클러스키 방법을 이용하여 간소화시키고 있다.

 

 

카르노 도표는 여러 개의 사각형으로 된 다이어그램을 말한다. 

 

2변수 카르노 도표

사각형은 각각 하나의 최소항 또는 최대항을 의미한다.

 

최소항 또는 최대항들이 차지하는 도표 내의 면적을 이용하여 간소화한다. 

 

부울함수의 입력변수의 수에 따라 기본 도표의 형태가 결정된다 

 

입력변수의 수가 n인 경우, n 변수 카르노 도표라 하고 2^n개의 사격형으로 구성된다

 

 

진리표에서 유도될 수 있는 정규형 부울함수는 표준형 부울함수로 간소화할 수 있다.

정규형에서 표준형으로 간소화할 때 대수식으로만 간소화하는 것은 어느 정도 한계가 존재한다. 

 

즉 최소항의 합 형태가 곱의 합 형태로 표현되거나 최대항의 곱 형태가 합의 곱 형태로 간소화된다.

 

최소항의 합형을 곱의 합형으로 간소화하는 순서.

 

먼저 n 변수의 카르노 도표를 작성한다.

 

이후 최소항의 인덱스에 대응되는 사각형을 1로 표시한다.

 

1로 표시된 사격형들 중 서로 인접한 사각형끼리 묶어준다. 

2변수 카르노 도표

이때 한 묶음은 크게 묶고 전체 묶음의 수는 적게 가져가야 한다.

한 묶음 내의 정사각형의 수는 2^n개가 되도록 묶어야 한다.

크게 묶을수록 소거되는 양이 많아지고 그렇기에 묶음 수는 자동적으로 적어진다.

 

각 묶음이 입력변수 각각에 대해 도표상의 어떤 위치에 있는지 확인한다. 

 

인접사각형으로 판단되면 변수가 소거된다. 그렇기에 인접의 여부가 중요하다.

 

2 X 2 사각형을 행렬로 표현할 때 다음과 같이 최소항이 발생한다.

 

A,B를 ( B =x , A =y로 치환) (0,0) = x̄ · ȳ ,  (0,1) = x̄ · y,  (1,0) =  x · ȳ, (1,1) = x · y 가된다.

 

이후 인접한 사각형은 묶으면 다음과 같은 부울함수가 나온다.

 

x̄ · ȳ + x̄ · y = x̄( ȳ + y) = x̄   ,  (ȳ + y = 1)이다. 

 

이렇게 소거되는 식을 통해 시각적으로 묶고 쉽게 간소화할 수 있다. 

 

이후 구한 각 묶음에 대한 곱항들을 논리합으로 연결시키면 간소화된 표준형이 구해진다.

 

반대로 최대항의 곱형을 합의 곱형으로 간소화할 수 있다.

 

최대항과 최소항은 쌍대의 관계를 가진다. 

2변수 카르노 도표

그렇기에 0으로 표시하면 된다.

 

위와 같은 과정을 거쳐나온 최대항의  합항들을 논리곱으로 연결시키면 간소화된 표준형이 구해진다.

 

사실 쌍대 관계를 이해하니까 최소항만 제대로 알면 최대항은 역산을 시킨다고 생각하면 좀 편한 것 같다.

 

 

3변수 이상으로 가면 더 복잡해진다. 

여기서 확인해 볼 것은  AB의 11과 10이다. 순서가 00, 01, 10, 11이 맞는데 역으로 표현되어 있다는 것을 확인해야 한다.

 

정상적이면 인접한 사각형으로 묶은 경우 소거항이 나오질 않아서 그런 것 같다.

 

재밌는 건 (00, 0)과 (10, 0)이 묶여있다고 판단할 수 있다는 것이다. 둥근 띠를 생각해야 한다.

 

 

그렇다면 순서가 다음과 같을 것이다.

 

 

진리표 -> 입력 변수가 많지 않으면 경우 카르마 도표를 사용 -> 간소화된 표현식을 얻는다.