무엇을 묶고,
왜 그 답을 고를까요?

고급편을 시작하기 전에 어떤 약속을 다시 확인하면 되나요?

이 글에서도 1은 참, 0은 거짓입니다. A·B는 AND, A+B는 OR, ¬A는 A의 부정입니다. OR는 두 조건이 모두 참인 경우도 포함합니다. 괄호가 없으면 부정을 먼저 읽고, AND를 계산한 뒤 OR로 연결합니다.

세 변수 맵은 세로 A, 가로 BC이며 열 순서는 00, 01, 11, 10입니다. 네 변수 맵은 세로 AB, 가로 CD이고 두 축 모두 같은 그레이 순서를 따릅니다. m번호는 A를 가장 왼쪽 자리에 둔 입력값의 이진 번호입니다. 세 변수의 m5는 101, 네 변수의 m5는 0101입니다.

올바른 묶음은 가장자리 연결을 포함해 직사각형을 이루며, 각 방향의 길이가 1, 2, 4…칸입니다. 그 안에서 1로 유지되는 글자는 그대로 쓰고, 0으로 유지되는 글자는 부정해 씁니다. 두 값을 모두 포함하는 글자는 묶음의 조건에서 뺍니다.

최소식을 비교할 때에는 기준도 정해야 합니다. 이 글의 SOP 풀이에서는 먼저 OR로 연결한 항수를 줄이고, 항수가 같으면 사용한 글자의 총수를 줄입니다. ¬A도 글자 하나로 세며, 같은 글자가 다른 항에 다시 나오면 각각 셉니다. 이렇게 식에 쓰인 A나 ¬A 하나를 리터럴이라고도 부릅니다. 실습의 ‘남은 조건 수’는 이 글자 수를 뜻합니다.

실습에서 상수 0과 1은 입력 조건이 필요 없는 경우로 보고 항수와 글자 수를 모두 0으로 셉니다. 이 세기 규칙을 정해 두고 같은 기준으로 비교하겠습니다.

표에 적힌 1, 0, X는 각각 어떤 요구를 뜻하나요? ^*

지금까지는 모든 칸의 결과가 0 또는 1로 정해져 있었습니다. 고급 문제에서는 결과 칸에 X가 등장합니다. 먼저 세 표시의 뜻을 구별하겠습니다.

이때 X를 ‘돈트 케어’라고 부릅니다. 해당 입력에서 어느 결과를 내도 된다는 요구사항이 주어졌다는 뜻입니다. 여기서 요구사항은 장치나 프로그램이 어떤 입력에 어떤 결과를 내야 하는지 정한 약속입니다.

X를 사용할 때는 허용 근거가 있어야 합니다. 단순히 결과를 아직 조사하지 못했거나, 센서가 무엇을 읽었는지 불확실하다는 이유만으로 결과 칸을 X로 바꿀 수는 없습니다. 그런 상황에서도 필요한 출력이 있다면 그 요구를 먼저 정해야 합니다.

X는 그 입력의 결과를 선택할 수 있다는 뜻입니다. 반드시 1인 칸과 반드시 0인 칸의 요구는 계속 지켜야 합니다.

어떤 상황에서 X를 사용할 수 있는지 어떻게 판단하나요?

입력 장치가 특정한 입력만 전달한다고 보장하는 경우가 있습니다. 또는 어떤 입력에서는 결과를 사용하지 않으며 0과 1을 모두 허용한다고 기능 요구에 명시할 수도 있습니다. 이런 약속이 유지되는 범위에서 X를 사용할 수 있습니다.

예를 들어 한 자리 십진수를 네 비트로 전달하는 장치가 0부터 9까지의 코드만 내보낸다고 합시다. 뒤에서 계산할 기능이 이 장치의 정상 출력만 받는다는 조건이 보장되면, 10부터 15에 해당하는 입력 조합은 결과 선택에 사용할 수 있습니다.

입력이 바뀌는 중간 순간에도 출력을 사용하는 장치라면, 그때 나타날 수 있는 코드의 결과까지 살펴야 합니다. X를 쓰는 약속은 결과를 확인하거나 사용하는 모든 경우에 맞아야 합니다.

반대로 잘못된 코드가 들어왔을 때 반드시 오류 표시를 해야 한다는 요구가 있다면, 그 결과는 이미 정해져 있습니다. 해당 기능을 설계하면서 그 칸을 자유롭게 선택할 수는 없습니다. 같은 숫자 조합이라도 맡은 기능과 입력 약속에 따라 취급이 달라집니다.

학습자 · 입력이 거의 들어오지 않으면 X로 정해도 되나요?

안내 · 발생 빈도보다 결과를 자유롭게 정할 수 있다는 약속이 중요합니다. 드물게 들어오더라도 그때 지켜야 하는 결과가 있다면 0 또는 1로 지정합니다. X를 채우기 전에 그 입력이 왜 결과 선택의 대상인지 설명할 수 있어야 합니다.

X를 이용하면 두 칸짜리 묶음을 어떻게 넓힐 수 있나요?

세 변수의 m1과 m3은 반드시 1이고, m5와 m7은 X라고 합시다. 나머지 m0, m2, m4, m6은 반드시 0입니다.

우선 반드시 1인 윗줄의 두 칸만 묶어 봅시다. m1=001과 m3=011에서는 A=0과 C=1이 유지되므로 ¬A·C가 됩니다. 이 식은 두 X칸의 결과를 0으로 정합니다.

이번에는 바로 아래의 X 두 칸까지 포함해 보겠습니다. BC=01과 BC=11인 두 열, A=0과 A=1인 두 줄을 모두 포함하는 네 칸 묶음입니다. 그 안에 반드시 0이어야 하는 칸은 없습니다.

A와 B의 네 조합을 모두 포함하면서 C는 계속 1입니다. 따라서 새 식은 F=C입니다. 이 식은 X였던 m5와 m7의 결과를 1로 정합니다. 두 X칸에서 1이 허용되었으므로 문제의 요구를 충족합니다.

¬A·C와 C는 여덟 입력 전체에서 같은 함수는 아닙니다. 차이가 나는 곳은 결과 선택이 허용된 두 X칸입니다. 두 식 모두 반드시 지켜야 하는 네 0과 두 1에서는 요구를 만족하며, C가 글자 하나로 더 간단합니다.

주어진 X를 모두 사용해야 하나요?

이번에는 m1만 반드시 1이고, m0·m2·m6은 X입니다. 나머지 네 칸은 반드시 0입니다.

m1=001의 옆에는 m0=000이 있습니다. 이 X를 함께 묶으면 A=0, B=0이 유지되고 C의 두 값을 모두 포함합니다. 따라서 F=¬A·¬B가 됩니다.

m2와 m6에도 X가 있지만 이 식을 만들기 위해 포함할 필요는 없습니다. ¬A·¬B를 계산하면 m0의 결과는 1이고, m2와 m6의 결과는 0입니다. 세 칸 모두 결과 선택이 허용되었으므로 이 선택은 요구에 맞습니다.

m2와 m6을 따로 묶으면 X 두 칸만 들어 있는 묶음이 됩니다. 그 묶음은 반드시 1이어야 하는 m1을 덮는 데 도움을 주지 않습니다. 필수 1을 모두 표현하는 최소 SOP를 구할 때 이런 묶음을 추가할 필요는 없습니다.

X는 필요한 묶음을 넓히는 데 선택해서 사용합니다. 모든 X를 1로 만들거나 모든 X를 묶을 의무는 없습니다.

X가 있는 문제에서는 무엇을 기준으로 검산하나요?

모든 칸이 0 또는 1로 정해졌던 문제에서는 원래 표와 새 식의 결과가 모든 입력에서 같아야 했습니다. X가 있는 문제에서는 원래 지정의 종류를 함께 비교합니다.

앞의 두 번째 예에서 얻은 F=¬A·¬B를 여덟 입력에 넣어 보겠습니다.

1인 칸은 새 식에서도 1인지 확인합니다. 0인 칸은 새 식에서도 0인지 확인합니다. X인 칸에서는 새 식이 선택한 값을 기록하되, 원래 고정된 값과 틀렸다고 판정하지 않습니다.

이 검산을 통해 “어떤 결과를 그대로 보존했는지”와 “어떤 결과를 새 식이 선택했는지”를 분리해 읽을 수 있습니다. 이후 입력 약속이 바뀌어 X였던 경우에 특정 결과가 필요해지면, 그 새 요구를 넣어 식을 다시 검토해야 합니다.

BCD에서 10부터 15까지를 X로 쓰는 이유는 무엇인가요?

BCD는 십진수 한 자리를 네 비트로 표현하는 방식입니다. 0은 0000, 1은 0001로 쓰고, 9는 1001로 씁니다. 이 절에서는 왼쪽부터 A, B, C, D로 약속하겠습니다. 자리의 값은 각각 8, 4, 2, 1입니다.

여기서 만들 기능은 “입력된 십진 숫자가 5 이상이면 F=1”입니다. 입력 장치가 유효한 한 자리 BCD인 0~9만 전달한다는 조건을 두겠습니다. 그 조건 아래에서 나머지 코드 10~15에는 X를 지정합니다.

유효한 입력 중 0~4는 5보다 작으므로 0입니다. 5~9는 5 이상이므로 1입니다. 10~15에 X를 쓴 근거는 이 기능이 유효한 한 자리 BCD만 받는다는 약속입니다.

1010을 일반적인 네 비트 이진수로 읽으면 10입니다. 그러나 이 문제의 한 자리 BCD에서는 십진 숫자 한 자리를 나타내는 유효 코드로 사용하지 않습니다. 입력의 표현 방식을 먼저 약속한 이유가 여기에 있습니다.

BCD의 다섯 개 1을 어떻게 A+B·C+B·D로 줄이나요?

반드시 1인 칸은 m5, m6, m7, m8, m9이고 X는 m10부터 m15까지입니다. 네 변수 맵에 옮겨 보겠습니다.

먼저 A=1인 아래쪽 두 줄 AB=11과 AB=10을 함께 묶습니다. 여덟 칸 가운데 m8·m9는 필수 1이고 나머지는 X입니다. 반드시 0인 칸이 없으므로 한 묶음으로 잡을 수 있습니다. 이 묶음에서는 A만 남습니다.

이제 A=0인 쪽의 m5, m6, m7을 포함할 묶음을 찾습니다. m6, m7에 X인 m14, m15를 더하면 B=1, C=1인 네 칸입니다. 이 묶음은 B·C입니다.

m5, m7에 X인 m13, m15를 더하면 B=1, D=1인 네 칸입니다. 이 묶음은 B·D입니다. 세 묶음을 OR로 연결하면 F=A+B·C+B·D가 됩니다.

유효한 BCD 0~9에 새 식을 대입하면 결과는 차례로 0, 0, 0, 0, 0, 1, 1, 1, 1, 1입니다. 처음의 요구와 같습니다. 사용하지 않는 코드 10~15에서는 이 식이 모두 1을 선택합니다. 이 결과도 앞서 둔 허용 조건 안에 있습니다.

SOP와 POS는 어떤 방식으로 조건을 연결하나요? ^*

지금까지는 한 묶음을 AND로 읽고, 여러 묶음을 OR로 연결했습니다. 예를 들어 ¬A·B+A·C가 그런 식입니다. 각각의 AND 조건을 항이라고 부르면, 두 항을 OR로 이어 붙인 형태입니다.

이 형식을 SOP, 곧 ‘곱의 합’이라고 부릅니다. 여기서 곱은 AND, 합은 OR를 뜻합니다. 일반적인 숫자 덧셈과 곱셈의 이름을 논리 연산의 표기에 사용한 것입니다.

다른 형태도 있습니다. (A+B)·(¬A+C)는 괄호 안에서 OR를 계산한 뒤, 두 괄호의 결과를 AND로 연결합니다. 이 형식은 POS, 곧 ‘합의 곱’입니다.

POS에서는 모든 괄호 조건이 참이어야 전체가 참입니다. 어느 괄호 하나라도 0이면 AND의 결과가 0이 됩니다. 이 성질을 이용하면 결과가 0인 경우를 묶어 POS를 만들 수 있습니다.

0인 칸을 묶으려면 왜 먼저 ¬F를 생각하나요?

새 문제를 보겠습니다. 세 변수에서 F=1인 경우는 m2, m3, m5, m7입니다. 나머지 m0, m1, m4, m6의 결과는 0입니다. 이번 문제에는 X가 없습니다.

F가 0인 곳에서 1이 되는 결과를 G라고 놓아 봅시다. 즉 G=¬F입니다. F가 1인 곳에서는 G가 0이고, F가 0인 곳에서는 G가 1입니다.

이제 F의 0들을 묶는 일은 G의 1들을 묶는 일과 같습니다. G에 대해서는 앞에서 익힌 SOP 방법을 그대로 사용할 수 있습니다. 묶음에서 0으로 유지되는 글자를 부정하고, 1로 유지되는 글자를 그대로 남깁니다.

G의 식을 얻은 뒤에는 다시 부정해서 F로 돌아와야 합니다. 이 마지막 단계에서 AND와 OR, 각 글자의 부호가 어떻게 바뀌는지 다음 절에서 확인하겠습니다.

괄호 전체를 부정하면 AND와 OR는 왜 바뀌나요?

‘P 또는 Q’가 거짓인 경우를 생각해 보세요. P도 거짓이고 Q도 거짓이어야 합니다. P와 Q 중 하나라도 참이면 OR는 참이 되기 때문입니다. 따라서 ¬(P+Q)는 ¬P·¬Q와 같은 결과를 냅니다.

이번에는 ‘P 그리고 Q’가 거짓인 경우를 생각해 봅시다. 두 조건 중 적어도 하나가 거짓이면 됩니다. 그래서 ¬(P·Q)는 ¬P+¬Q와 같은 결과를 냅니다. 이 두 관계를 드모르간 법칙이라고 부릅니다.

표에서 세 번째와 네 번째 열이 같고, 다섯 번째와 여섯 번째 열도 같습니다. 가능한 네 경우에서 확인한 관계이므로 P와 Q 자리에 더 긴 논리식을 넣어도 같은 방식으로 적용할 수 있습니다.

괄호 전체의 부정을 안으로 옮길 때는 각 부분을 부정하고, OR는 AND로, AND는 OR로 바꿉니다. 두 번 부정한 글자는 원래 글자가 됩니다.

0인 네 칸에서 (A+B)·(¬A+C)를 어떻게 얻나요?

F의 0은 m0, m1, m4, m6이었습니다. 먼저 m0=000과 m1=001을 묶습니다. A=0, B=0이 유지되므로 G=¬F의 한 항은 ¬A·¬B입니다.

다음으로 아랫줄 양 끝의 m4=100과 m6=110을 묶습니다. A=1, C=0이 유지되므로 G의 다른 항은 A·¬C입니다. 따라서 G=¬A·¬B+A·¬C입니다.

첫 0 묶음에서 A와 B는 0이었습니다. G의 항에서는 ¬A·¬B였고, 이를 부정해 F의 괄호로 바꾸면 A+B가 됩니다. 둘째 0 묶음에서 A=1, C=0이었으므로 G의 항 A·¬C를 부정한 ¬A+C가 됩니다.

그래서 F의 0 묶음을 곧바로 POS로 읽을 때는, 0으로 유지되는 글자를 그대로 쓰고 1로 유지되는 글자를 부정해 OR로 연결합니다. 이 읽는 방법은 앞의 부정 계산을 줄여 표현한 것입니다.

여덟 경우에서 원래 결과와 두 괄호를 AND로 연결한 결과가 같습니다. 모든 0을 적어도 한 묶음에 포함했는지도 확인하세요. POS를 구할 때는 어떤 괄호가 어떤 0을 만드는지 설명할 수 있어야 합니다.

SOP와 POS 중 어느 쪽이 더 간단한지 어떻게 비교하나요?

방금 문제의 1들을 묶으면 SOP도 얻을 수 있습니다. m2·m3은 ¬A·B이고, m5·m7은 A·C입니다. 따라서 SOP는 ¬A·B+A·C입니다. POS는 (A+B)·(¬A+C)였습니다.

이 예에서는 SOP가 두 항, POS가 두 괄호이고, 사용한 글자는 양쪽 모두 네 개입니다. 모양은 달라도 같은 결과표를 나타냅니다.

다른 예로 F=(A+B)·(C+D)를 보겠습니다. 앞의 두 조건 중 하나 이상이 참이고, 뒤의 두 조건 중에서도 하나 이상이 참일 때 1입니다. 식을 펼치면 A·C+A·D+B·C+B·D가 됩니다.

이 경우에는 POS가 글자를 적게 사용합니다. 1이 모인 모양과 0이 모인 모양을 함께 살펴보면 어느 형식이 읽기 간단할지 판단하는 데 도움이 됩니다.

다만 SOP의 항수와 POS의 괄호 수를 같은 회로 비용이라고 바로 간주하지는 않습니다. 실제로 어떤 게이트를 쓰는지, 중간 결과를 공유하는지, 신호가 몇 단계를 거치는지에 따라 비교 대상이 달라집니다. 이 글에서는 먼저 각 형식 안에서 결과의 정확성과 표현의 크기를 비교합니다.

주항은 무엇이며 작은 묶음도 주항이 될 수 있나요? ^*

이제 여러 묶음 가운데 어떤 것을 선택할지 살펴보겠습니다. 우선 반드시 0인 칸을 넣지 않으면서 더 넓힐 수 있는 묶음은 넓혀 봅니다. 그렇게 해도 더 큰 유효 묶음 안에 포함시킬 수 없는 항을 주항이라고 부릅니다.

중급편의 F=A+B·C를 다시 사용하겠습니다. 결과가 1인 경우는 m3, m4, m5, m6, m7입니다. 이 표에는 X가 없습니다.

아랫줄 네 칸의 A 묶음은 더 넓힐 수 없습니다. 윗줄 전체를 더하면 0을 포함하기 때문입니다. 이 묶음은 주항입니다.

m3과 m7의 세로 두 칸을 묶은 B·C도 주항입니다. 이 두 칸을 포함하는 네 칸짜리 직사각형으로 넓히면 윗줄의 0을 포함하게 됩니다. 두 칸짜리여도 더 넓힐 수 없으므로 주항입니다.

주항을 찾는 기준은 표 전체에서 가장 큰 묶음인지가 아니라, 현재 묶음을 포함하는 더 큰 유효 묶음이 있는지입니다. 이 예에서는 크기가 다른 두 주항이 있습니다.

X가 있는 SOP 문제에서는 묶음을 넓힐 때 X를 함께 사용할 수 있습니다. 그중 필수 1을 덮는 데 쓸 주항을 후보로 모읍니다. X만 포함하는 묶음은 필수 1의 피복 후보로 추가할 필요가 없습니다.

필수주항은 어떤 칸을 보고 찾나요?

주항을 모두 찾았으면 각 필수 1을 어떤 주항들이 덮는지 확인합니다. 어떤 1을 덮는 주항이 딱 하나라면, 주항들의 조합으로 최소 SOP를 구할 때 그 주항은 반드시 선택해야 합니다. 이를 필수주항이라고 부릅니다.

앞의 예에는 A와 B·C 두 주항이 있었습니다. m3은 B·C만 덮고, m4·m5·m6은 A만 덮습니다. m7은 두 주항이 함께 덮습니다.

m3을 빠뜨릴 수 없으므로 B·C가 필요합니다. m4를 빠뜨릴 수 없으므로 A도 필요합니다. 따라서 이 예의 두 주항은 모두 필수주항입니다. 선택한 두 주항으로 모든 1을 포함하므로 풀이가 끝납니다.

m7이 두 곳에 겹친다는 사실은 이 결론을 바꾸지 않습니다. B·C가 필요한 이유는 m3이고, A가 필요한 이유는 m4·m5·m6입니다. 어떤 칸 때문에 필수인지 함께 말하면 판단이 분명해집니다.

주항이 많아지면 피복표를 어떻게 만들면 되나요?

중급편에서 두 최소 풀이를 찾았던 표를 다시 사용하겠습니다. 필수 1은 m0, m1, m2, m5, m6, m7이고, 나머지 m3·m4는 0입니다.

이 표에서는 네 칸짜리 묶음을 만들 수 없습니다. 가능한 두 칸짜리 주항을 모두 모아 P1부터 P6까지 이름을 붙이겠습니다. P라는 이름은 주항을 선택할 때 편리하게 부르는 이름입니다.

이제 세로에는 주항을, 가로에는 반드시 포함해야 할 1의 번호를 적습니다. 해당 주항이 그 칸을 포함하면 표시합니다. 이를 피복표라고 부릅니다. ‘피복’은 여기서 필요한 칸들을 선택한 묶음으로 모두 덮는다는 뜻입니다.

각 열에는 표시가 두 개씩 있습니다. 따라서 이 표에는 필수주항이 없습니다. 모든 1에 대해 선택할 후보가 둘씩 남아 있으므로, 여러 주항을 어떤 조합으로 골라야 전체를 덮는지 비교해야 합니다.

피복표에서 서로 다른 두 최소 답을 어떻게 찾나요? ^*

먼저 P1을 골라 m0과 m1을 덮어 보겠습니다. 아직 남은 칸은 m2, m5, m6, m7입니다. P4는 m2·m6을, P5는 m5·m7을 덮습니다. 따라서 P1, P4, P5 세 주항으로 모든 1을 포함할 수 있습니다.

다른 출발도 가능합니다. P2로 m0·m2를 덮고, P3로 m1·m5를, P6로 m6·m7을 덮습니다. P2, P3, P6도 세 주항으로 전체를 포함합니다.

왜 최소라고 할 수 있을까요? 이 표의 한 주항은 최대 두 개의 1을 덮습니다. 필수 1이 여섯 개이므로 두 주항으로는 최대 네 칸만 덮을 수 있습니다. 적어도 세 주항이 필요하며, 위의 두 방법은 실제로 세 주항으로 완성했습니다.

항수가 같은 세 주항의 풀이에서 각 항은 글자 두 개를 사용하므로 글자 수는 여섯입니다. 이 기준에서는 두 답을 같은 수준의 최소해로 인정합니다. 실제 입력을 대입해도 두 식은 000, 001, 010, 101, 110, 111에서 1이고, 011과 100에서는 0입니다.

최소성을 설명하려면 실제 풀이와 함께, 그보다 적은 항으로는 필요한 칸을 덮을 수 없다는 근거를 확인합니다.

더 지울 수 없는 풀이와 최소 풀이는 어떻게 다른가요?

같은 표에서 P1, P2, P5, P6 네 주항을 골랐다고 해 보겠습니다. 이 선택도 모든 필수 1을 포함합니다. 각 주항을 하나씩 지워 보면 다음 문제가 생깁니다.

따라서 지금 선택한 네 주항 중 하나만 바로 삭제할 수는 없습니다. 이런 풀이를 더 이상 불필요한 항을 제거할 수 없는 피복이라고 설명할 수 있습니다.

그러나 직전 절에서 세 주항으로 완성한 답을 이미 찾았습니다. 네 항을 그대로 두고 하나만 지우는 방법은 막혔지만, 선택 조합을 다시 구성하면 세 항으로 줄일 수 있습니다.

예를 들어 P1을 유지하고 P2·P5·P6의 선택을 다시 검토하면, P4와 P5로 나머지를 덮어 P1·P4·P5 세 개를 선택할 수 있습니다. 기존 후보를 교체하며 전체 조합을 비교한 것입니다.

현재 풀이에서 하나씩 지울 항이 없다는 사실만으로 전체 최소가 증명되지는 않습니다.

가장 큰 묶음부터 고르면 언제나 최소가 되나요?

이번 네 변수 표에서 결과가 1인 경우는 m0, m1, m2, m3, m4, m7, m9, m10입니다. 그 밖의 경우는 0입니다.

맨 윗줄 m0·m1·m3·m2는 네 칸 묶음입니다. 이 표에서 가장 큰 주항은 이 묶음 하나뿐이며, 조건은 ¬A·¬B입니다. 먼저 선택하기 쉬운 모양입니다.

그런데 윗줄 밖의 m4, m7, m9, m10을 각각 살펴보세요. 이 칸들은 아래 표에 적힌 두 칸짜리 주항으로만 덮을 수 있습니다.

네 바깥 칸 때문에 이 네 주항을 모두 선택해야 합니다. 이들을 고르면 윗줄의 m0, m1, m2, m3도 모두 포함됩니다. 따라서 별도의 네 칸 묶음은 필요하지 않습니다.

유일한 가장 큰 묶음을 먼저 고르고 끝까지 남겨 두면 다섯 항이 됩니다. 필수 두 칸 묶음 네 개만 고르면 네 항입니다. 각 바깥 칸을 덮는 네 주항이 모두 필요하므로 네 항이 최소라는 근거도 갖추었습니다.

큰 묶음을 살펴보는 것은 유용합니다. 이후 다른 칸을 덮는 조합까지 확인한 뒤, 이미 검토한 큰 묶음도 필요 없으면 제거할 수 있어야 합니다. 실전에서는 주항 전체 찾기, 필수주항 선택, 남은 열의 피복 비교, 검산 순서로 진행해 보세요.

표의 결과가 같아도 실제 회로에서는 무엇을 더 살펴야 하나요? ^*

여기부터 세 절은 회로의 시간에 관한 선택 심화입니다. 진리표는 입력값이 정해졌을 때의 논리 결과를 보여줍니다. 실제 전자회로에서는 입력이 바뀐 신호가 게이트를 지나 출력까지 전달되는 데 시간이 걸립니다. 이 시간을 전파 지연이라고 부릅니다.

서로 다른 경로의 전달 시간이 다르면 입력이 바뀌는 도중에 잠깐 예상과 다른 출력이 나타날 수 있습니다. 특히 변화 전과 변화 후의 정상 출력이 모두 1이어야 하는데, 사이에 짧게 0으로 내려갈 가능성을 정적 1 해저드라고 부릅니다.

이번 예에서는 입력 하나만 바뀌고 다른 입력은 안정적으로 유지된다고 가정하겠습니다. 논리 연결은 첫 단계의 AND 게이트들, 다음 단계의 OR 게이트로 구성합니다. 부정된 입력을 만드는 반전기의 지연도 함께 고려합니다.

이 조건을 정해 두는 이유는 이후의 보강 방법이 무엇을 해결하는지 정확히 말하기 위해서입니다. 여러 입력이 함께 바뀌는 경우나 다른 구조의 회로까지 같은 설명 하나로 모두 다룰 수 있는 것은 아닙니다.

A·B+¬A·C에서 어떤 순서로 출력이 잠깐 달라질 수 있나요? ^*

회로의 식을 F=A·B+¬A·C라고 하겠습니다. B=C=1로 고정하고 A가 1에서 0으로 바뀌는 순간을 살펴봅니다.

변화 전에는 A·B=1이고 ¬A·C=0이어서 F=1입니다. 변화 후 정상 상태에서는 A·B=0이고 ¬A·C=1이어서 F=1입니다. 두 정상 결과는 같습니다.

이제 한 가지 가능한 전달 순서를 수치로 따라가겠습니다. 설명용 시간 단위로 반전기의 지연을 2, AND의 지연을 1, OR의 지연을 1이라고 가정합니다. 이 숫자는 실제 장치를 측정한 값이 아니라 전달 순서를 이해하기 위해 정한 값입니다.

아래 시간표의 ¬A는 반전기 출력선의 현재 값을 가리킵니다. A의 변화는 두 시간 단위 뒤 그 선에 반영됩니다. A·B와 ¬A·C 열도 각 AND 게이트의 출력선에서 그 시점에 관찰하는 값입니다.

t=1에는 직접 A를 받은 AND 경로가 먼저 0으로 내려갑니다. 반전 경로는 아직 새 값을 전달하지 못해 0입니다. 두 AND 출력이 모두 0인 동안 OR에도 그 상태가 전달되어 t=2에 F가 0이 됩니다.

t=3에는 반전 경로의 AND 출력이 1로 올라갑니다. 그 값이 OR를 지나면 t=4에 F가 다시 1이 됩니다. 이 지연 조건에서는 정상 결과가 양쪽 모두 1인데도 가운데에 0인 구간이 생깁니다.

실제로 짧은 변화가 출력까지 나타나는지와 그 폭은 회로의 지연 및 게이트 응답에 따라 달라집니다. 여기서는 이런 순서가 가능하다는 점과, 그 가능성을 줄이는 논리적 보강을 이해하는 데 초점을 둡니다.

논리적으로 중복인 B·C를 더하면 무엇이 달라지나요?

같은 함수의 카르노 맵을 보겠습니다. 결과가 1인 경우는 m1, m3, m6, m7입니다. A·B는 m6·m7을, ¬A·C는 m1·m3을 덮습니다.

B=C=1에서 A가 변하는 것은 m7=111과 m3=011 사이를 이동하는 경우입니다. 두 칸은 이웃하지만 원래 두 묶음 중 어느 하나도 두 칸을 함께 포함하지 않습니다.

m3과 m7을 추가로 묶으면 B·C입니다. 이 항을 더한 식은 F=A·B+¬A·C+B·C입니다. B와 C를 1로 안정적으로 유지하는 동안에는 A가 바뀌어도 B·C 경로가 계속 1을 제공합니다.

추가한 항이 정상 논리 결과를 바꾸지 않는 이유도 확인하겠습니다. B·C=0인 입력에서는 더한 항이 0이므로 원래 결과가 그대로입니다. B·C=1인 입력에서는 B=C=1입니다. 그때 A=1이면 A·B가 이미 1이고, A=0이면 ¬A·C가 이미 1입니다. 따라서 원래 식도 이미 1입니다.

즉 정상 논리값만 보면 B·C는 중복입니다. 그러나 앞서 가정한 단일 A 변화와 2단 AND–OR 구조에서는 두 경로가 모두 0이 되는 순간에도 안정적인 1을 유지하는 역할을 합니다. 이를 합의항이라고 부릅니다.

논리식을 가장 짧게 만드는 목표와, 입력이 바뀌는 동안 출력을 안정적으로 유지하는 목표를 함께 살펴야 하는 경우가 있습니다.

아래 시범에서 같은 입력 변화의 두 출력을 비교해 보세요. 처음 두 경로의 값이 잠깐 모두 0이 될 때, B·C를 추가한 경로가 어떤 값을 유지하는지 차례로 확인하면 됩니다. 이 설명은 정적 1 해저드의 해당 조건을 다루며, 모든 종류의 순간 출력 변화를 한꺼번에 없앤다는 뜻은 아닙니다.

다섯 변수는 두 장의 맵에서 어떻게 읽나요? ^*

변수가 다섯 개면 입력 경우는 2×2×2×2×2=32가지입니다. 열여섯 칸짜리 맵 두 장으로 나타낼 수 있습니다. 여기서는 입력을 A, B, C, D, E로 쓰고, 이 절부터 결과의 이름은 Y로 약속하겠습니다.

첫 맵은 A=0, 둘째 맵은 A=1입니다. 두 맵 안에서는 세로가 BC, 가로가 DE이며 각각 00, 01, 11, 10 순서입니다. 서로 같은 좌표의 칸은 B, C, D, E가 모두 같고 A만 다릅니다.

각 맵에서 BC=01, DE=10인 칸을 골라 보겠습니다. 입력값을 적으면 다음과 같습니다.

두 칸이 모두 1이면 맵을 가로질러 함께 묶을 수 있습니다. A는 두 값을 모두 포함하므로 빠지고, 나머지 네 조건이 남습니다. 이 묶음은 ¬B·C·D·¬E입니다.

더 큰 묶음도 같은 원리입니다. 두 맵 모두에서 DE=11인 열 전체를 1로 두고, 나머지 칸은 0으로 둔다고 해 봅시다. 한 맵마다 네 칸, 두 맵을 합쳐 여덟 칸입니다. A, B, C의 모든 조합이 들어 있고 D=1, E=1이 유지되므로 Y=D·E입니다.

이때의 번호는 m3, m7, m11, m15, m19, m23, m27, m31입니다. 여러 맵을 연결할 때에도 같은 위치의 같은 모양을 함께 포함하는지, 그 안에 허용되지 않은 0이 들어 있는지 확인합니다.

여섯 변수의 네 맵은 어떤 순서로 연결하나요?

여섯 변수는 64가지 입력을 만듭니다. 입력 이름은 A, B, C, D, E, F를 쓰고, 결과는 앞 절과 같이 Y라고 하겠습니다. 이 절의 F는 여섯 번째 입력이므로 결과 이름과 구별해 읽으세요.

맵의 주소를 AB로 정하면 네 맵이 필요합니다. 주소 순서는 00, 01, 11, 10입니다. 각 맵 안쪽은 세로 CD, 가로 EF이며 두 축 역시 그레이 순서입니다.

주소 00과 11은 A와 B가 함께 달라지므로 직접 이웃한 두 맵으로 묶지 않습니다. 대신 네 맵의 같은 좌표를 모두 포함하면 A와 B의 네 조합을 전부 포함하게 됩니다.

각 맵에서 CD=01, EF=10인 같은 칸을 모두 1로 두고, 나머지 칸은 0으로 두겠습니다.

네 칸에서 C=0, D=1, E=1, F=0이 유지됩니다. A와 B는 모든 조합을 포함하므로 이 묶음은 ¬C·D·E·¬F입니다. 결과를 쓰면 Y=¬C·D·E·¬F입니다.

큰 맵에서도 계산 원리는 같습니다. 다만 그림의 장수가 늘면 위치를 놓치기 쉬우므로, 맵 주소와 안쪽 좌표를 따로 적어 확인하는 습관이 필요합니다. 이번 절에서는 네 장의 관계와 같은 좌표의 뜻을 이해하는 데 집중해 보세요.

고급 문제를 직접 풀 때는 어떤 순서로 확인하면 되나요?

첫째, 입력 글자와 출력 글자의 뜻을 정합니다. 그다음 반드시 1인 칸, 반드시 0인 칸, 자유롭게 정할 수 있는 X칸을 구별합니다. X에는 어떤 허용 조건이 있는지 먼저 읽습니다.

둘째, 지금 구할 표현이 SOP인지 POS인지 확인합니다. SOP는 1과 필요한 X를 묶고, POS는 0과 필요한 X를 묶습니다. 반드시 반대 값을 내야 하는 칸을 포함하면 안 됩니다.

셋째, 묶음에서 유지되는 조건을 읽습니다. SOP에서는 1로 유지된 글자를 그대로, 0으로 유지된 글자를 부정해 AND로 연결합니다. POS에서는 반대로 0으로 유지된 글자를 그대로, 1로 유지된 글자를 부정해 OR로 연결합니다. 부호가 헷갈리면 ¬F를 먼저 구하는 과정으로 돌아가세요.

넷째, 필수 칸을 모두 포함했는지 확인합니다. X를 모두 포함할 필요는 없습니다. 전체를 덮었다면 항을 더 넓히거나 조합을 바꾸어 줄일 수 있는지 살펴봅니다. 주항과 피복표를 사용하면 선택 이유를 정리할 수 있습니다.

다섯째, 지정된 모든 입력의 결과를 검산합니다. X인 곳에서는 새 식이 어느 값을 선택했는지 구분해 봅니다. 결과가 정확한 풀이와 최소 기준까지 충족한 풀이를 차례로 확인하세요.

먼저 요구를 지킨 식을 만들고, 그다음 같은 요구를 지키는 더 간단한 표현을 찾습니다.

자유 실험에서 0이나 1을 X로 바꾸면 결과를 선택할 수 있는 범위를 바꾸는 것입니다. 이것은 원래 문제의 요구를 바꾸는 조작입니다. 정해진 문제를 풀 때는 X를 임의로 추가하지 않고 주어진 표 안에서 묶음을 선택합니다.

카르노 맵을 실제 문제에 적용할 때 무엇을 남겨 두면 좋나요?

완성한 식과 함께 입력의 뜻, 반드시 지켜야 하는 결과, X를 허용한 이유를 남겨 두세요. 나중에 기능이 바뀌면 어느 약속을 다시 확인해야 하는지 알 수 있습니다. 같은 결과표에 여러 풀이가 있다면 선택 기준도 적어 두면 좋습니다.

수학적으로 같은 결과를 내는지 확인할 때는 진리표 검산이 도움이 됩니다. 실제 회로를 만드는 경우에는 사용한 게이트와 신호 경로, 지연 조건을 별도로 살펴봅니다. 논리 결과와 시간에 따른 동작을 각각 확인한 뒤 연결해야 합니다.

변수가 늘어나면 경우의 수는 2의 거듭제곱으로 증가합니다. 다섯 변수는 32칸, 여섯 변수는 64칸입니다. 손으로 읽는 과정에서 위치 확인이 부담스러워지면, 항을 체계적으로 합치는 퀸–매클러스키 방법이나 피복표를 계산하는 도구를 함께 사용할 수 있습니다. 카르노 맵에서 배운 같은 조건과 변하는 조건의 구분은 그런 결과를 이해하고 점검하는 데도 이어집니다.

도구가 내놓은 짧은 식을 받을 때에도 세 가지 질문은 직접 해 볼 수 있습니다. “반드시 1과 0이어야 하는 입력을 모두 지키나요?”, “어떤 X의 값을 선택했나요?”, “무엇을 줄이는 기준으로 이 답을 골랐나요?” 회로의 순간 동작이 중요하다면 어떤 입력 변화와 지연 조건을 검토했는지도 확인합니다.

마지막으로 한 예를 골라 자신의 말로 설명해 보세요. 어떤 칸을 왜 묶었는지, 어떤 글자가 유지되어 식에 남았는지, 전체 결과를 어떻게 확인했는지 이어서 말할 수 있으면 됩니다. 기초의 네 칸에서 시작한 설명이 X, 여러 최소해, 더 큰 맵에서도 같은 원리로 이어집니다.