보이는 카르노 맵

1. 식을 읽습니다. 괄호와 ¬를 먼저 확인하고, ·는 AND, +는 OR로 읽습니다.
2. 입력을 하나씩 대입합니다. A를 맨 왼쪽 비트로 두고 모든 0·1 조합을 계산합니다. 두 변수는 4행, 세 변수는 8행, 네 변수는 16행입니다.
3. 계산한 값을 맵으로 옮깁니다. 행·열의 입력값을 찾아 F의 0 또는 1을 적습니다. 두 비트 축의 순서는 00 → 01 → 11 → 10입니다.
4. 후보 묶음을 찾습니다. 같은 목표값의 칸으로 1·2·4·8…칸짜리 직사각형을 만듭니다. 가장자리도 이어서 읽고, 더 넓힐 수 없는 후보를 남깁니다.
5. 빠짐없이 덮는 조합을 고릅니다. 특정 칸을 덮는 후보가 하나뿐이면 그 후보는 필수입니다. 남은 칸까지 덮는 조합을 비교합니다.
6. 묶음을 식으로 읽습니다. 묶음 안에서 값이 고정된 글자를 남기고, 0과 1이 모두 나타난 글자를 없앱니다. 선택한 SOP 또는 POS 방식으로 연결합니다.
7. 모든 입력으로 검산합니다. 원래 식과 완성한 식의 결과가 4·8·16행에서 각각 같은지 확인합니다.

그레이 순서·가장자리 연결·SOP/POS의 원리: 참고 자료 1. 주항과 최소 피복을 고르는 절차: 참고 자료 2.

¬A는 A의 반대, A·B는 둘 다 1일 때 1, A+B는 하나 이상이 1이면 1입니다. +는 불 논리의 OR이므로 1+1도 1입니다. 괄호를 먼저 계산하고, 괄호가 없으면 ¬ → · → + 순서를 지킵니다.

m번호는 입력을 이진수로 읽은 번호입니다. 예를 들어 세 변수의 m5는 ABC=101이고, 네 변수의 m5는 ABCD=0101입니다. 칸 안에 크게 적는 0·1은 그 입력에서 계산한 출력 F입니다.

진하게 표시한 입력과 칸이 지금 보는 대상입니다. 묶음에는 색과 번호를 함께 붙입니다. 맵 양 끝에 같은 번호의 테두리가 나타나면 가장자리를 넘어 이어지는 하나의 묶음입니다.

SOP는 AND로 만든 항들을 OR로 연결하는 형태이고, POS는 OR로 만든 괄호들을 AND로 연결하는 형태입니다. SOP에서는 1을, POS에서는 0을 묶습니다. 이 실습은 문제에 지정한 형태 안에서 묶음 수를 먼저 줄이고, 그 수가 같으면 식에 남은 글자의 총수를 줄입니다. A와 ¬A는 각각 글자 하나로 셉니다.

모든 입력의 결과가 같다는 검산은 두 식이 같은 기능을 한다는 뜻입니다. 최소인지 확인하는 일에는 후보 묶음들의 비용 비교가 따로 필요합니다. 가장 큰 묶음을 먼저 잡거나, 선택한 묶음을 더 지울 수 없다는 사실만으로 전체 최소가 되지는 않습니다.

괄호를 중첩하거나 XOR 같은 다른 연산을 허용하면 더 짧게 쓸 수 있는 식도 있습니다. 따라서 여기서 얻은 최소 SOP/POS가 모든 표기 방식 가운데 가장 짧은 식이라는 뜻은 아닙니다. 15번에서는 이 차이도 확인합니다.