부울함수의 간소화 및 구현(1)

카르토 도표를 이용한 간소화

카르노 도표의 개요

1. 여러개의 사각형으로 된 다이어그램
2. 사각형은 각각 하나의 최소항 또는 최대항을 의미
3. 최소항 또는 최대항들이 차지하는 도표내의 면적을 이용하여 간소화
4. 부울함수의 입력변수의 수에 따라 기본 도표의 형태가 결정
   
5. 카르노 도표를 이용하면

• 정규형 부울함수 => 표준형 부울함수로 간소화
• 즉 최소항의 합 형태가 곱의합 형태나, 최대항의 곱 형태가 합의 곱 형태로 간소회됨

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

인접사각형

1. 인접사각형의 정의

• 각 정사각형은 하나의 최소항 or 최대항을 의미
• 인접사각형이란
  - 두 정사각형에 대응되는 각 최소항 or 최대항의 구성변수 둥 다른 모든 변수는 동일하되 오직 하나의 변소만 서로 보수관계에 있을떄 두 정사각형은 서로 인접한다.
  
  -> m4와 m6는 서로 인접한다
  

2. 인접 사각형끼리 묶는 방법
   

2,3,4 변수의 카르노도표

2번 카르노 도표

• 두개의 변수를 가지는 부울함수 -> 4개의 최소항
  - 2변수 카르노 도표는 4개의 정사각형으로 구성
  - 각가의 정사각형은 하나의 최소항에 대응
  
  

3번 카르노 도표

• 세개의 변수를 가지는 부울함수 -> 8개의 최소항
  - 3변수 카르노도표는 8개의 정사각형으로 구성
  - 각각의 정사각형은 하나의 최소항에 대응
  
  -> '1 1', '1 0' 순서 바뀌는 것 중요! 인접항을 나타내기 위해서
  

4번 카르노 도표

• 네개의 변수를 가지는 부울함수 -> 16개의 최소항