✔ 카르노 도표를 이용한 간소화
부울함수의 간소화 방법
1. 대수적인 방법
- 주어진 부울함수에 부울대수 정리를 대수적으로 적용해 간소화
- 도표 방법과 테이블 방법의 이론적 바탕
2. 도표 방법
- 카르노 도표(Karnaugh map)를 사용하는 방법
- 카르노 도표를 사용하여 부울함수의 각 항들을 곱이나 합 형태로 간소화
- 여섯 개 이하의 변수를 가진 부울함수에 사용
3. 테이블 방법
- 퀸-맥클러스키(Quine-Mcluskey) 방법
- 테이블을 사용해 간소화 알고리즘을 구현한 방법
- 많은 변수를 가진 부울함수에 적합
카르노 도표의 개요
카르노 도표
- 여러 개의 사각형으로 된 다이어그램
- 사각형은 각각 하나의 최소항 또는 최대항을 의미
- 최소항 또는 최대항들이 차지하는 도표내의 면적을 이용하여 간소화
- 카르노 도표는 부울함수의 입력변수의 수에 따라 기본 도표의 형태가 결정
- 입력변수의 수가 n인 경우, n 변수 카르노 도표라고 하고 2^n개의 사각형으로 구성
카르노 도표 이용 시
정규형 부울 함수 > 표준형 부울함수로 간소화
- 최소항의 합 형태가 곱의 합 형태
- 최대항의 곱 형태가 합의 곱 형태
1) 최소항의 합형을 곱의 합형으로 간소화하는 순서
- 입력변수의 수 n에 따라 n 변수 카르노 도표 작성
- 최소항의 인덱스에 대응되는 사각형을 1로 표시
- 1로 표시된 사각형들 중 서로 인접한 사각형끼리 묶음 (한 묶음은 크게, 전체 묶음 수는 적게)
- 각 묶음이 입력변수 각각에 대해 도표상 어떤 위치에 있는지 파악
만일 해당 묶음이 입력변수 X에 대해 X=1인 곳에만 존재하면 곱항에 X를 남기고, X=0인 곳에만 존재하면 곱항에서 X바를 남긴다. 만일 묶음이 X=0인 곳과 X=1인 곳에 걸쳐 존재한다면 곱항에서 X변수를 소거한다. - 4에서 구한 각 묶음에 대한 곱항들을 논리합(OR)으로 연결시키면 간소화된 표준형(곱의 합형)이 구해진다.
2) 최대항의 곱형을 합의 곱협으로 간소화하는 순서
- 앞 (1)의 1과 동일 과정 수행
- 최소항의 인덱스에 대응되는 사각형을 0 으로 표시
- 0 으로 표시된 사각형들 중 서로 인접한 사각형끼리 묶음 (앞 3과정과 동일)
- 각 묶음이 입력변수 각각에 대해 도표상 어떤 위치에 있는지 파악
만일 해당 묶음이 입력변수 X에 대해 X=1인 곳에만 존재하면 곱항에 X바를 남기고, X=0인 곳에만 존재하면 곱항에서 X를 남긴다. 만일 묶음이 X=0인 곳과 X=1인 곳에 걸쳐 존재한다면 합항에서 X변수를 소거한다. - 4에서 구한 각 묶음에 대한 합항들을 논리곱(AMD)으로 연결시키면 간소화된 표준형(합의 곱형)이 구해진다.
인접 사각형
3) 인접 사각형의 정의
카르노 도표에서 각 정사각형은 하나의 최소항 또는 최대항을 의미
두 정사각형에 대응되는 각 최소항 또는 최대항의 구성변수 중 다른 모든 변수는 동일하되 오직 하나의 변수만 서로 보수관계에 있을 때 두 정사각형은 서로 인접한다고 정의
4) 인접 사각형끼리 묶는 방법
1. 한 묶음 내의 정사각형의 수는 2^n(n=0, 1, 2...n)개가 되도록 묶는다.
2. 한 묶음은 크게, 전체 묶음 수는 적게 묶는다.
✔ 2, 3, 4 변수의 카르노 도표
2변수 카르노 도표
두 개의 변수를 가지는 부울함수 > 4개의 최소항
: 4개의 정사각형으로 구성되고 각각의 정사각형은 하나의 최소항에 대응
3변수 카르노 도표
세 개의 변수를 가지는 부울함수 > 8개의 최소항
: 8개의 정사각형으로 구성되고 각각의 정사각형은 하나의 최소항에 대응
끝에 있는 00, 10 사각형이 서로 맞닿으면 묶음2가 인접하게된다.
01, 11 가운데 묶음1끼리도 인접이 성립됨
만약 10 11 순으로 되어있다면 인접하지않음
오직 하나의 변수만 보수관계에 있는 친구들만 인접하기 때문임
4변수 카르노 도표
네 개의 변수를 가지는 부울함수 > 16개의 최소항
: 16개의 정사각형으로 구성되고 각각의 정사각형은 하나의 최소항에 대응
WX 변수의 11, 10 상하 위치 주의할 것
정사각형들의 묶음 > 곱항으로 간소화
- 하나의 정사각형 : 네 개 문자의 곱항으로 표시
- 두 개의 인접 정사각형 : 세 개 문자의 곱항으로 표시
- 네 개의 인접 정사각형 : 두 개 문자의 곱항으로 표시
- 여덟 개의 인접 정사각형 : 한 개 문자의 항으로 표시
- 열 여섯 개의 인접 정사각형 : 상수 1로 부울함수가 표시