8칸과 16칸,
가장자리까지 이어서.

기초편에서 배운 것 중 무엇을 먼저 떠올리면 되나요?

먼저 두 조건 A와 B를 사용하는 작은 표를 다시 보겠습니다. 바깥의 숫자는 조건의 값이고, 칸 안의 숫자는 결과 F입니다.

아랫줄의 두 1을 묶으면 A는 두 칸 모두 1입니다. B는 왼쪽에서 0, 오른쪽에서 1입니다. B가 가질 수 있는 두 값을 모두 포함하므로 이 묶음은 A 하나로 읽습니다. 따라서 F=A입니다.

여기서 사용한 약속을 다시 확인하겠습니다. A·B는 두 조건을 모두 충족하는 AND, A+B는 하나 이상을 충족하는 OR, ¬A는 A의 부정을 뜻합니다. A=0일 때 ¬A=1입니다. OR는 두 조건을 함께 충족하는 경우도 포함합니다.

한 묶음 안에서 남는 조건들은 AND로 연결하고, 여러 묶음은 OR로 연결합니다.

중급편에서도 결과가 1인 칸을 묶습니다. 모든 1을 적어도 한 묶음에 넣고, 결과가 0인 칸은 묶음에 넣지 않습니다. 풀이를 마친 뒤에는 가능한 모든 경우에서 원래 표와 새 식의 결과가 같은지 확인합니다.

조건이 세 개가 되면 무엇부터 약속해야 하나요?

기초편의 연습용 행사에 조건 하나를 더해 보겠습니다. 이 글에서 이어서 풀 첫 사례는 다음 약속을 사용합니다.

A, B, C는 확인할 조건입니다. F는 그 조건들을 보고 결정할 결과입니다. 조건 하나가 늘어났으므로 방문자를 설명할 때도 세 가지 값을 함께 적습니다.

예를 들어 A=0, B=1, C=1은 “입장권은 없고, 초대 명단에 이름이 있으며, 사전 안내를 마친 방문자”입니다. A=1, B=0, C=0은 “입장권이 있고, 명단에는 이름이 없으며, 사전 안내를 아직 마치지 않은 방문자”입니다.

이 세 조건 사이에 별도의 관계가 주어지지는 않았습니다. 따라서 각 조건에 0과 1을 모두 넣어 가능한 조합을 살펴봅니다. 어떤 조합을 실제로 허용할지는 곧 정할 입장 규칙에 따라 결정됩니다. 규칙을 읽고 나서 각 칸의 F를 채웁니다.

학습자 · C를 더했으니 A와 B의 뜻도 바뀌나요?

안내 · 이번 사례에서는 A와 B의 뜻을 그대로 두고 C만 추가했습니다. 뒤에서 다른 사례를 시작할 때는 글자의 뜻을 새로 적어 두겠습니다. 각 사례의 약속을 확인하며 읽으면 됩니다.

세 조건이 만들 수 있는 경우는 왜 여덟 가지인가요?

기초편의 A와 B는 00, 01, 10, 11 네 경우를 만들었습니다. 그 네 경우마다 C가 0인 경우와 1인 경우를 하나씩 붙여 봅시다.

한 줄마다 두 경우가 생깁니다. 네 줄이므로 4×2=8가지입니다. 처음부터 세 조건의 선택 수를 곱하면 2×2×2=8로 계산할 수도 있습니다.

세 자리의 순서는 항상 A, B, C로 정하겠습니다. 101을 읽을 때 첫 자리는 A=1, 가운데는 B=0, 마지막은 C=1입니다. 앞으로 01이나 101을 볼 때마다 어떤 글자들의 값을 어떤 순서로 적었는지 확인하세요.

가능한 경우를 빠짐없이 적으려면 A를 0으로 둔 네 경우를 먼저 쓰고, A를 1로 둔 네 경우를 이어 쓰면 됩니다. 각 묶음 안에서는 B=0인 두 경우를 먼저, B=1인 두 경우를 다음에 적습니다. C는 그때마다 0, 1로 바꿉니다.

가로 순서는 왜 00, 01, 11, 10인가요?

여덟 칸짜리 맵에서는 세로에 A를 놓고, 가로에 B와 C의 조합을 놓겠습니다. A는 0, 1 두 줄이고, BC는 네 열입니다. 가로의 순서는 00, 01, 11, 10으로 정합니다.

왼쪽에서 오른쪽으로 한 번씩 이동하면서 두 자리 중 무엇이 달라지는지 확인해 보세요.

각 이동에서 조건 하나만 달라집니다. 이렇게 이웃한 조합 사이에서 한 자리만 바뀌게 배열한 순서를 그레이 코드라고 부릅니다. 0 또는 1 한 자리를 ‘비트’라고 하므로, 자료에서는 ‘한 비트만 달라진다’고 설명하기도 합니다.

학습자 · 숫자를 세듯이 00, 01, 10, 11로 적으면 어떨까요?

안내 · 가운데의 01과 10을 비교해 보세요. B는 0에서 1로, C는 1에서 0으로 함께 바뀝니다. 그 두 칸을 같은 방식으로 묶으면 어떤 조건을 남겨야 할지 달라집니다. 카르노 맵은 이웃한 두 칸에서 조건 하나만 달라지도록 순서를 정해 둡니다.

이 순서는 큰 표에서 조건을 정확하게 묶기 위한 약속입니다. 네 조합 자체는 모두 한 번씩 들어 있습니다. 이제 아래에서 이웃한 조합을 하나씩 골라, 어느 글자만 바뀌는지 확인해 보세요.

여덟 칸에서 A, B, C의 값을 어떻게 찾나요?

A=0은 윗줄, A=1은 아랫줄입니다. BC는 왼쪽부터 00, 01, 11, 10입니다. 위치를 익히기 위해 아래 표의 칸 안에는 해당 위치의 입력 조합을 적었습니다.

이 표의 긴 문구는 칸의 위치를 설명하는 안내입니다. 실제 문제를 풀 때는 그 자리에 결과 F의 값인 0 또는 1을 적습니다.

예를 들어 A=1, B=1, C=0인 경우를 찾아보겠습니다. 먼저 A=1인 아랫줄로 갑니다. B와 C를 차례로 붙이면 BC=10입니다. 10은 네 번째 열이므로, 아랫줄 맨 오른쪽 칸을 고르면 됩니다.

이번에는 윗줄 세 번째 칸을 거꾸로 읽어 보세요. 윗줄이므로 A=0입니다. 세 번째 열의 이름은 BC=11이므로 B=1, C=1입니다. 이 칸은 011이라는 입력 조합에 해당합니다.

먼저 A로 줄을 찾고, B와 C를 붙인 두 자리로 열을 찾습니다. 칸 안에 적는 값은 그 경우의 결과 F입니다.

칸에 붙은 m번호와 Σm은 어떻게 읽나요?

카르노 맵 자료에는 m0, m1 같은 번호가 자주 나옵니다. 이 번호는 입력 조합을 짧게 부르기 위해 붙입니다. 이번 글에서는 A를 가장 왼쪽 자리에 두고 ABC의 순서로 읽습니다.

번호를 계산하면 4×A+2×B+C입니다. 예를 들어 101은 4×1+2×0+1=5이므로 m5입니다. 이 계산은 경우 번호를 구하는 일반 산술입니다. 앞에서 OR를 나타낼 때 쓰던 논리식의 +와 구별해 읽습니다.

m3이라는 표시 자체는 결과가 1이라는 뜻을 담고 있지 않습니다. m3은 A=0, B=1, C=1인 경우를 가리킵니다. 그 경우의 F가 0인지 1인지는 별도로 적습니다.

칸의 순서는 그레이 배열을 따르지만, m번호는 원래의 이진 입력값을 따라갑니다. 그래서 윗줄 번호가 0, 1, 3, 2로 보입니다. 번호를 표의 왼쪽부터 새로 붙이지 않는다는 점을 기억하세요.

F=Σm(3,4,5,6,7)이라고 쓰면, 나열한 다섯 경우의 결과가 1이고 나머지 경우는 0이라는 뜻입니다. Σ는 여기서 각 경우를 나타내는 항들을 OR로 연결한다는 표시입니다. 지금은 “이 번호의 칸들에 1을 쓴다”라고 읽어도 됩니다.

새 입장 규칙을 여덟 줄의 진리표로 어떻게 적나요?

이제 첫 사례의 입장 규칙을 정하겠습니다. 입장권이 있거나, 초대 명단에 이름이 있으면서 사전 안내를 마쳤으면 입장을 허용합니다. 이 조건에 해당하면 F=1, 나머지 경우에는 F=0입니다.

A는 입장권, B는 명단, C는 사전 안내를 뜻했습니다. 명단에 이름이 있고 안내도 마친 조건은 B·C입니다. 이 조건 또는 A가 충족되면 되므로 전체 규칙은 F=A+(B·C)입니다. 괄호 안의 AND를 먼저 확인한 뒤 A와 OR로 연결합니다.

m1을 보세요. A=0이므로 입장권이 없습니다. B=0, C=1이므로 사전 안내는 마쳤지만 명단에는 이름이 없습니다. B·C=0이며, A도 0이므로 결과는 0입니다.

m3에서는 A=0이지만 B와 C가 모두 1입니다. B·C=1이므로 입장을 허용합니다. m4에서는 B와 C가 모두 0이지만 A=1이므로 입장을 허용합니다. 서로 다른 두 허용 조건이 표의 여러 줄에 나타난 것입니다.

결과가 1인 경우를 모으면 m3, m4, m5, m6, m7입니다. 다음 단계에서는 이 결과들을 정해진 칸에 옮기겠습니다.

진리표의 결과를 여덟 칸에 어떻게 옮기나요?

처음 네 줄은 A=0이므로 모두 맵의 윗줄로 갑니다. 다음 네 줄은 A=1이므로 모두 아랫줄로 갑니다. 각 줄 안에서는 BC를 보고 정확한 열을 고릅니다.

특히 m2와 m3을 천천히 옮겨 보세요. 진리표에서는 m2가 먼저 나오지만, 맵에서 m2의 열은 10이어서 네 번째입니다. 그다음 m3은 열 11을 찾아 세 번째 칸에 들어갑니다. 결과를 그대로 옮기면서 위치만 열 이름에 맞춥니다.

윗줄을 왼쪽부터 읽으면 0, 0, 1, 0입니다. 아랫줄은 네 칸 모두 1입니다. 진리표에서 결과가 1이었던 다섯 경우가 맵에서도 모두 1인지 번호를 하나씩 찾아 확인해 보세요.

아래 시범에서는 한 경우를 고르고, 줄과 열을 찾고, 결과를 쓰는 과정을 차례로 살펴봅니다. 읽은 뒤 다음 단계로 넘어가세요. 위치가 헷갈리면 직전 단계로 돌아가 A와 BC를 다시 확인하면 됩니다.

아랫줄 네 개의 1을 묶으면 어떤 글자가 남나요?

완성한 표에서 아랫줄을 먼저 보겠습니다. 네 칸 모두 1이므로 가로로 네 칸을 묶을 수 있습니다. 이 묶음에는 m4, m5, m7, m6이 들어 있습니다. 순서를 입력값과 함께 다시 써 보겠습니다.

A는 모든 칸에서 1입니다. B는 0과 1을 모두 포함하고, C도 0과 1을 모두 포함합니다. 여기서는 B와 C가 만들 수 있는 네 조합 00, 01, 11, 10이 빠짐없이 들어 있습니다.

그래서 B와 C의 값을 따로 제한할 필요가 없습니다. A=1이라는 조건만으로 이 네 칸을 정확히 가리킬 수 있습니다. 첫 번째 묶음에서 얻는 항은 A입니다.

학습자 · B와 C가 각각 바뀐다는 사실만 확인하면 되나요?

안내 · 먼저 올바른 모양의 묶음인지 확인해야 합니다. 이번 묶음은 연속한 네 칸의 직사각형이고, B와 C의 네 조합이 모두 들어 있습니다. 이런 묶음에서 유지되는 글자를 읽습니다. 떨어진 칸들을 임의로 고른 뒤 글자를 지우면 원래 표의 결과와 달라질 수 있습니다.

입장 규칙으로 다시 읽으면 “입장권이 있는 방문자”라는 조건입니다. 이 조건을 충족하는 네 경우는 명단과 사전 안내의 상태에 관계없이 F=1입니다.

윗줄에 남은 1은 어떻게 묶고 겹침은 왜 허용하나요?

아랫줄을 묶고 나면 윗줄의 m3이 남습니다. m3은 BC=11인 세 번째 열에 있습니다. 바로 아래의 m7도 1이므로, 두 칸을 세로로 묶습니다.

A는 0과 1을 모두 포함합니다. B와 C는 두 칸에서 모두 1입니다. 따라서 이 묶음에 남는 조건은 B·C입니다. “초대 명단에 이름이 있고, 사전 안내를 마쳤다”로 읽습니다.

이제 첫 묶음의 A와 두 번째 묶음의 B·C를 OR로 연결합니다. A에 해당하거나 B·C에 해당하면 결과가 1입니다.

F=A+(B·C)

m7은 아랫줄 묶음과 세로 묶음에 함께 들어 있습니다. A=1이면서 B·C=1인 경우이므로 두 조건을 모두 충족합니다. OR에서는 두 조건이 모두 1이어도 결과가 1입니다. 그래서 한 칸이 여러 묶음에 들어가도 결과는 그대로 유지됩니다.

m3을 혼자 한 칸으로 묶는 방법도 가능합니다. 그러면 두 번째 항은 ¬A·B·C가 됩니다. F=A+¬A·B·C도 같은 결과를 내지만, m7과 함께 묶으면 ¬A를 빼서 더 짧게 쓸 수 있습니다.

얻은 식이 맞는지 여덟 경우를 어떻게 검산하나요?

간단한 식을 얻었으면 원래 진리표와 비교합니다. 한두 경우가 맞는지 확인하는 데서 멈추지 않고 여덟 경우를 모두 살펴봅니다.

000, 001, 010에서는 A가 0이고 B·C도 0이므로 결과가 0입니다. 011에서는 B·C가 1이므로 결과가 1입니다. 나머지 네 경우에서는 A가 1이므로 결과가 모두 1입니다.

원래 표의 0인 칸도 반드시 비교하세요. 묶음에 0을 잘못 포함하면 새 식이 그 경우까지 허용할 수 있습니다. 원래 표에서 1인 칸을 빠뜨리면 새 식은 그 경우를 0으로 계산할 수 있습니다. 검산은 두 종류의 차이를 함께 찾아줍니다.

원래 결과와 새 식의 결과가 가능한 모든 입력에서 같으면 두 표현은 같은 규칙을 나타냅니다.

처음에는 간단한 식에서 표를 만들었고, 맵을 읽어 다시 그 식을 얻었습니다. 출발과 도착을 비교할 수 있도록 고른 연습입니다. 식이 주어지지 않고 결과표만 주어져도 같은 방법으로 묶음의 조건을 읽을 수 있습니다.

두 칸, 네 칸, 여덟 칸을 묶으면 글자는 몇 개 남나요?

세 변수의 한 칸을 지정하려면 A, B, C의 값을 모두 정해야 합니다. 예를 들어 m3 한 칸은 ¬A·B·C입니다. 조건을 세 개 써야 합니다.

올바르게 이웃한 두 칸을 묶으면 한 변수의 두 값을 모두 포함합니다. 그래서 그 변수의 제한을 풀고 두 글자를 남깁니다. 네 칸이면 두 변수가 만들 수 있는 네 조합을 모두 포함하므로 한 글자가 남습니다.

여덟 칸 전체가 1이면 전체를 묶습니다. 모든 입력에서 결과가 1이므로 F=1입니다. 반대로 여덟 칸 전체가 0이면 묶을 1이 없고 F=0입니다.

한 묶음에 들어 있는 칸이 많아질수록 그 묶음을 설명하는 조건은 줄어듭니다. 다만 묶음은 허용된 모양을 이루어야 하고, 이 글에서 다루는 문제에서는 그 안의 결과가 모두 1이어야 합니다.

멀리 떨어져 보이는 양 끝의 칸은 왜 함께 묶을 수 있나요?

이번에는 새 결과표를 보겠습니다. 맨 왼쪽과 맨 오른쪽 열의 네 칸이 1입니다. 번호로는 m0, m2, m4, m6입니다.

윗줄의 양 끝부터 비교해 보세요. 왼쪽 m0은 000이고 오른쪽 m2는 010입니다. A=0, C=0은 같고 B만 달라집니다. 따라서 이 두 칸은 조건 하나만 다른 이웃입니다. 아랫줄의 m4=100과 m6=110도 B만 다릅니다.

표의 처음 열 BC=00과 마지막 열 BC=10 사이에서도 조건 하나만 달라지도록 그레이 순서를 정했습니다. 맵에서는 이 처음과 끝을 서로 연결된 이웃으로 취급합니다. 화면 양 끝에 그려져 있다는 위치와, 입력 조건이 얼마나 다른지를 함께 살펴보면 이해할 수 있습니다.

양 끝 두 열을 두 줄에 걸쳐 함께 묶으면 네 칸입니다. A와 B의 네 조합이 모두 들어 있고 C는 계속 0입니다. 따라서 남는 조건은 ¬C입니다. 이 표의 규칙은 F=¬C입니다.

양 끝을 함께 묶을 때도, 묶음 속에서 같은 값을 유지하는 조건을 읽습니다. 이번에는 C=0이 유지됩니다.

네 조건을 사용하면 표의 두 축은 어떻게 달라지나요?

D를 더하면 가능한 경우는 2×2×2×2=16가지입니다. 이번에는 가로 네 칸, 세로 네 칸의 표를 사용합니다. 한 축에는 A와 B, 다른 축에는 C와 D를 놓겠습니다.

이 글의 네 변수 맵에서는 세로가 AB, 가로가 CD입니다. 두 축 모두 00, 01, 11, 10 순서를 사용합니다. 다른 자료에서 축을 바꾸어 그렸다면 그 자료의 축 이름에 맞추어 읽으면 됩니다.

이 표의 네 자리 숫자는 위치를 익히기 위한 입력 조합입니다. 앞의 두 자리는 왼쪽의 AB에서 가져오고, 뒤의 두 자리는 위쪽의 CD에서 가져옵니다. 실제 결과표에서는 칸 안에 F를 적습니다.

오른쪽으로 한 칸 이동하면 A와 B는 그대로이고 C 또는 D 중 하나만 달라집니다. 아래로 한 칸 이동하면 C와 D는 그대로이고 A 또는 B 중 하나만 달라집니다.

예를 들어 AB=01, CD=11인 칸은 0111입니다. 같은 줄에서 바로 왼쪽의 CD=01로 가면 0101이 되어 C만 바뀝니다. 같은 열에서 바로 아래의 AB=11로 가면 1111이 되어 A만 바뀝니다. 네 자리 전체를 비교하면 어느 조건이 달라지는지 확인할 수 있습니다.

열여섯 경우의 번호와 맵의 위치를 어떻게 연결하나요?

네 변수에서도 번호는 입력값의 원래 이진 순서를 따릅니다. A를 가장 왼쪽 자리로 두므로 경우 번호는 8×A+4×B+2×C+D입니다. 예를 들어 1010은 8+2=10이어서 m10입니다.

m10을 직접 찾아보겠습니다. 앞의 두 자리 AB=10은 네 번째 줄입니다. 뒤의 두 자리 CD=10도 네 번째 열입니다. 따라서 m10은 오른쪽 아래 모서리에 놓입니다.

m15는 1111입니다. AB=11은 세 번째 줄이고 CD=11도 세 번째 열이므로, m15는 세 번째 줄의 세 번째 칸입니다. 가장 큰 번호가 맨 마지막 칸에 오는 것은 아니라는 점을 위치표에서 확인할 수 있습니다.

표에 결과를 옮길 때 번호만 보고 차례로 밀어 넣지 말고, AB와 CD를 나누어 읽으세요. 예를 들어 문제에 Σm(0,2,8,10)이 주어지면 이 네 번호의 위치를 찾아 1을 적고, 나머지 위치에는 0을 적습니다. 바로 다음에 이 표를 읽어 보겠습니다.

네 모서리의 1을 함께 묶으면 왜 ¬B·¬D가 남나요?

m0, m2, m8, m10에 1을 적었습니다. 네 칸은 표의 네 모서리에 있습니다.

왼쪽 위 m0의 입력은 0000입니다. 오른쪽 위 m2는 0010이어서 C만 달라집니다. 왼쪽 아래 m8은 1000이어서 m0과 비교하면 A만 달라집니다. 오른쪽 아래 m10은 1010입니다.

네 칸에서 B는 모두 0이고 D도 모두 0입니다. A와 C는 00, 01, 10, 11의 모든 조합을 이룹니다. 따라서 A와 C의 값을 따로 제한할 필요가 없습니다. 남는 조건은 B=0 그리고 D=0입니다.

F=¬B·¬D

표의 위아래 끝 AB=00과 AB=10은 A만 다른 이웃입니다. 좌우 끝 CD=00과 CD=10은 C만 다른 이웃입니다. 두 방향의 연결을 함께 사용하면 네 모서리는 두 줄과 두 열로 이루어진 네 칸 묶음이 됩니다.

학습자 · 모서리에 있다는 이유만으로 묶어도 되나요?

안내 · 이번처럼 네 모서리가 모두 1이고 축이 그레이 순서로 놓여 있을 때 네 칸을 묶습니다. 입력값으로 다시 확인하면 B와 D가 0으로 유지됩니다. 모양과 값, 두 가지를 함께 확인하세요.

위아래 연결과 좌우 연결은 각각 어떻게 읽나요?

위와 아래를 연결하면 어떤 값이 유지되나요?

이번 표에서는 맨 윗줄과 맨 아랫줄의 가운데 두 칸이 1입니다. 번호는 m1, m3, m9, m11입니다.

두 줄의 이름은 AB=00과 AB=10입니다. A는 0과 1을 모두 포함하고 B는 0으로 유지됩니다. 두 열의 이름은 CD=01과 CD=11입니다. C는 두 값을 모두 포함하고 D는 1로 유지됩니다. 따라서 이 네 칸의 조건은 ¬B·D입니다.

왼쪽과 오른쪽을 연결하면 어떤 값이 유지되나요?

이번에는 가운데 두 줄의 양 끝 칸을 보겠습니다. 번호는 m4, m6, m12, m14입니다.

두 줄 AB=01과 AB=11에서는 B=1이 유지됩니다. 양 끝 열 CD=00과 CD=10에서는 D=0이 유지됩니다. A와 C는 각각 두 값을 모두 포함합니다. 따라서 조건은 B·¬D입니다.

두 예시에서 남는 글자는 모두 B와 D였지만 그 값이 다릅니다. 첫 표는 B=0, D=1이고 둘째 표는 B=1, D=0입니다. 같은 크기와 모양의 묶음이라도 어느 위치에 놓였는지에 따라 표현이 달라집니다.

네 변수에서 여덟 칸을 묶으면 왜 글자 하나가 남나요?

네 변수의 표에서 여덟 칸짜리 묶음을 만들어 보겠습니다. 먼저 위쪽 두 줄 AB=00과 AB=01을 모두 1로 둡니다.

두 줄에서 A는 계속 0이고 B는 0과 1을 모두 포함합니다. 네 열에서는 C와 D의 네 조합이 모두 포함됩니다. B, C, D가 만들 수 있는 여덟 조합을 전부 넣었으므로 A=0만 남습니다. 답은 F=¬A입니다.

이번에는 네 줄 전체에서 양 끝 두 열 CD=00과 CD=10을 1로 둡니다.

양 끝 열에서는 D=0이 유지되고 C는 두 값을 모두 포함합니다. 네 줄에는 A와 B의 네 조합이 모두 있습니다. 따라서 답은 F=¬D입니다. 화면에서는 두 덩어리처럼 보이지만 좌우 연결을 이용한 하나의 여덟 칸 묶음입니다.

세 변수에서 네 칸을 묶을 때도 글자 하나가 남았고, 네 변수에서는 여덟 칸을 묶어야 하나가 남습니다. 전체 변수의 수와 묶음의 크기를 함께 보아야 합니다.

칸 수만 맞으면 어떤 모양으로 묶어도 되나요?

묶을 칸 수는 1, 2, 4, 8, 16처럼 두 배씩 늘어납니다. 이 조건과 함께 확인할 것이 있습니다. 선택한 칸들이 가로와 세로로 이어진 직사각형을 이루어야 합니다. 각 방향의 길이도 1, 2, 4칸 가운데 하나이며, 앞서 배운 가장자리 연결을 사용할 수 있습니다.

마지막 경우를 세 변수 표로 살펴보겠습니다. m0, m1, m6, m7만 1입니다.

윗줄 왼쪽 두 칸과 아랫줄 오른쪽 두 칸으로 갈라져 있습니다. 이를 하나로 잡고 A, B, C가 모두 바뀐다고 해서 세 글자를 전부 빼면 F=1이 됩니다. 그러면 원래 0인 네 경우까지 1로 계산하게 됩니다.

올바르게는 윗줄 두 칸을 ¬A·¬B로, 아랫줄 두 칸을 A·B로 읽어 연결합니다. F=¬A·¬B+A·B입니다.

겹치는 묶음 중 어떤 것을 남기고 어떤 것을 줄이면 되나요?

모든 1을 포함하려고 묶음을 만들다 보면 같은 칸이 여러 묶음에 들어갈 수 있습니다. 겹침 자체는 허용됩니다. 다만 어떤 묶음은 이미 다른 묶음들이 표현한 경우만 다시 나타낼 수도 있습니다.

첫 사례 F=A+B·C를 다시 보겠습니다. 아랫줄 네 칸을 A로 묶고, 세 번째 열 두 칸을 B·C로 묶으면 모든 1을 포함합니다. 여기에 아랫줄 왼쪽 두 칸 m4, m5를 추가로 묶었다면 그 항은 A·¬B입니다.

이 추가 묶음의 두 칸은 이미 A 묶음에 모두 들어 있습니다. 추가 묶음을 없애도 원래의 모든 1이 남은 묶음에 들어 있고, 0을 새로 포함하지도 않습니다. 따라서 A·¬B를 덧붙이지 않아도 됩니다.

반면 B·C 묶음을 없애면 m3이 빠집니다. m7이 A 묶음과 겹쳐 있다고 해도, B·C 전체를 없앨 수는 없습니다. 겹치는 칸이 있는지와 묶음 전체가 필요한지는 따로 확인합니다.

더 간단한 답을 비교할 때 이 편에서는 먼저 OR로 연결한 항의 수를 셉니다. 항수가 같으면 항 안에 사용한 글자의 총수를 비교합니다. ¬A도 글자 하나로 세며, 서로 다른 항에 같은 글자가 다시 나오면 각각 셉니다.

큰 묶음을 먼저 찾는 방법은 좋은 출발점입니다. 그다음에는 다른 1들을 어떤 묶음으로 포함할지 함께 살펴보아야 합니다. 처음 고른 가장 큰 묶음만으로 전체 최소식이 보장되는 것은 아닙니다. 또한 여기서 비교하는 항수와 글자 수가 실제 회로의 모든 비용이나 작동 시간을 대신하지는 않습니다.

같은 표에서 똑같이 간단한 답이 둘 나올 수도 있나요?

이번 세 변수 표는 m0, m1, m2, m5, m6, m7의 결과가 1입니다. m3과 m4의 결과는 0입니다.

여섯 개의 1을 두 칸씩 묶는 방법을 두 가지 찾아보겠습니다. 첫 번째 방법은 다음 세 묶음을 사용합니다.

첫 번째 방법의 식은 F₁=¬A·¬B+B·¬C+A·C입니다. 두 번째 방법의 식은 F₂=¬A·¬C+¬B·C+A·B입니다. 두 번째 방법의 m0, m2는 윗줄의 양 끝을 연결한 묶음입니다.

두 식에 사용한 항은 각각 세 개입니다. 각 항에 글자가 두 개씩 있으므로 글자 수는 각각 여섯 개입니다. 식의 모습은 다르지만 결과도 같은지 직접 확인하겠습니다.

여덟 경우의 결과가 모두 같습니다. 이 표에서는 0인 m3과 m4 때문에 네 칸 묶음을 만들 수 없습니다. 한 묶음에 넣을 수 있는 1이 최대 두 개이므로, 여섯 개를 모두 포함하려면 적어도 세 묶음이 필요합니다. 두 방법 모두 세 묶음으로 완성했으므로 앞서 정한 기준에서 최소입니다.

최소인 답이 여러 개일 수 있습니다. 묶음 모양이 해설과 달라도, 모든 경우의 결과와 비교 기준을 확인해 판단합니다.

일상에서 정한 네 가지 조건도 표로 바꿀 수 있나요?

이번에는 책상등의 동작을 연습용 규칙으로 정해 보겠습니다. 앞선 입장 사례를 마쳤으므로 글자의 뜻을 새로 약속합니다.

규칙은 다음과 같습니다. 전원이 공급되어야 등불을 켤 수 있습니다. 전원이 공급되는 동안에는 자동 켜기를 사용하면서 주변이 어두운 경우, 또는 사용자가 수동 켜기를 요청한 경우에 켭니다. 이 조건을 모두 정한 학습용 규칙이며, 그 밖의 경우에는 F=0입니다.

자동 켜기와 어두운 상태가 함께 필요한 조건은 A·B입니다. 이 조건 또는 수동 요청 C가 있으면 되므로 괄호 안은 A·B+C입니다. 여기에 전원 공급 D가 함께 필요하므로 F=D·(A·B+C)입니다.

우선 D=0인 여덟 경우는 모두 0입니다. D=1이고 C=1인 네 경우는 수동 요청으로 켜집니다. D=1이고 C=0이면 A와 B가 모두 1인지 확인합니다. 이 과정을 열여섯 경우에 적용하면 다음 표가 됩니다.

CD=11인 열 네 칸을 묶으면 C·D가 남습니다. AB=11인 줄에서 CD=01, 11인 두 칸을 묶으면 A·B·D가 남습니다. 따라서 맵으로 읽은 식은 F=C·D+A·B·D입니다. 두 묶음은 m15에서 겹칩니다.

처음 식과 맵에서 읽은 식은 같은 결과를 냅니다. 수동 요청과 전원 공급이 함께 있는 경우를 C·D가 나타내고, 자동 기능·어두운 상태·전원 공급이 함께 있는 경우를 A·B·D가 나타냅니다.

이제 여덟 칸과 열여섯 칸을 직접 묶어 볼까요?

아래 연습에서는 칸의 값과 축 이름을 먼저 확인하세요. 세 변수 문제는 A가 줄, BC가 열입니다. 네 변수 문제는 AB가 줄, CD가 열입니다. 문제를 바꿀 때마다 어떤 표인지 확인한 뒤 시작하면 위치를 혼동하는 일을 줄일 수 있습니다.

첫 단계는 1이 어디에 있는지 찾는 것입니다. 다음에는 이웃한 1들로 묶음을 만듭니다. 가장자리의 1도 지나치지 말고 양 끝의 입력값을 비교해 보세요. 네 모서리가 모두 1이면 두 축의 연결을 함께 사용할 수 있는지도 살펴봅니다.

묶음을 만든 뒤 곧바로 식을 외워 쓰기보다, 묶음 속 A, B, C, D의 값을 하나씩 읽어 보세요. 어떤 글자가 모두 1인지, 모두 0인지, 두 값을 모두 포함하는지 설명하면 항을 정확히 쓸 수 있습니다.

모든 1을 포함했으면 각 항을 OR로 연결하고 검산합니다. 작은 묶음 여러 개로 정확한 결과를 만들었다면 풀이 자체는 성립합니다. 그다음 더 간단한 묶음 조합을 찾을 수 있는지 살펴보면 됩니다.

위치 확인 → 묶음 만들기 → 유지되는 조건 읽기 → 모든 1 확인 → 전체 경우 검산의 순서로 진행해 보세요.

해설과 묶음 모양이 다르면 먼저 결과를 비교하세요. 같은 결과를 내는지, 필요한 묶음 수와 사용한 글자 수가 어떤지 차례로 확인하면 자신의 풀이를 판단할 수 있습니다.

내가 만든 표를 실험한 뒤 고급편에서는 무엇을 배우나요?

자유 실험에서는 칸 안의 결과를 0과 1 사이에서 직접 바꿀 수 있습니다. 세 변수 표의 모든 칸을 0으로 만든 뒤 아랫줄 네 칸만 1로 바꾸어 보세요. A라는 조건이 나오는지 확인합니다.

이어서 윗줄 BC=11인 칸도 1로 바꿔 보세요. 처음 예시의 A+B·C가 됩니다. 이번에는 모든 값을 다시 0으로 두고 양 끝 두 열을 1로 바꿔 보세요. ¬C가 나오는 이유를 자신의 말로 설명해 봅니다.

네 변수 표에서는 네 모서리만 1로 만들어 ¬B·¬D를 확인할 수 있습니다. 그다음 양 끝 두 열 전체를 1로 넓혀 보세요. B의 두 값을 모두 포함하게 되어 ¬D만 남는 과정을 살펴봅니다.

칸 안의 결과를 바꾸면 규칙 자체가 바뀝니다. 같은 표에서 묶는 방법을 바꾸는 것은 같은 규칙을 다른 식으로 표현하는 과정입니다.

고급편에서는 실제로 사용하지 않는 입력 조합을 X로 표시해 다루는 방법을 배우겠습니다. X를 넣을 근거가 무엇인지부터 확인하고, 0을 묶어 다른 형태의 식을 만드는 방법도 살펴봅니다. 또 여러 후보 묶음에서 최소 조합을 고르는 절차와, 실제 회로에서 신호 전달 시간 때문에 생기는 순간적인 출력 변화를 다룹니다.

이번 편에서는 입력값과 묶음을 근거로 조건을 읽는 과정을 충분히 익혀 두세요. 한 묶음을 가리키며 “이 글자는 이 값으로 유지되고, 저 글자는 두 값을 모두 포함합니다”라고 설명할 수 있다면 다음 내용을 배울 준비가 된 것입니다.