HOTIAN’S ARROW / 풀이 02
칸을 묶고, 선을 잇고.
같은 식에 도착합니다.
카르노맵의 0 묶음과
줄타기의 원을 함께 읽습니다.
0인 칸을 묶어 ‘또는’ 항을 만들고, 그 항들을 ‘그리고’로 잇는 형식을 POS라고 합니다. 다섯 식의 완성 풀이를 살펴보고, ‘차례로 재생’으로 같은 함수가 더 짧은 식이 되는 과정을 따라가 보세요.
(p ∨ q) ∧ (p ∨ ¬q) ≡ p
0인 두 칸에서는 p=0이고 q만 바뀝니다.
이 묶음의 합항도, 두 행을 묶은 결과도 p입니다.
칸의 값과 원의 표기카르노맵의 0·1은 함수값입니다. 줄타기의 ●는 긍정형, ○는 부정형을 나타냅니다.
00, 01, 11, 10두 변수를 붙여 쓴 축은 이 Gray 순서를 따릅니다. 이웃한 칸은 한 변수만 바뀌며, 양끝도 이어집니다.
0 묶음에서 합항 읽기묶음 안에서 고정값 0은 긍정형, 1은 부정형으로 읽습니다. 값이 바뀌는 변수는 항에서 빠집니다.
한 행은 OR, 여러 행은 AND새 행을 얻은 뒤, 남길 행들이 보장하는 조건을 정리합니다. 남은 행 전체가 원식과 같은 함수를 나타냅니다.
2변수 · 한 묶음
두 칸을 묶어 p만 남기기
q의 두 값에서 모두 0인 칸을 묶으면, 바뀌지 않는 p만 남습니다.
두 풀이의 동치식이 같습니다: p. 묶음 A와 오른쪽의 같은 이름 행을 비교해 보세요.
KARNAUGH MAP
카르노맵
모든 괄호식을 함께 적용한 함수값입니다.
- A2개의 0을 한 묶음으로
p=0 → p
p=0인 두 칸입니다. q는 바뀌므로 빠지고, 고정된 0에 대응하는 합항 p를 읽습니다.
- ✓최종식 확인
p
한 묶음이 모든 0을 덮으므로, 읽은 합항 하나가 최종식입니다.
p
모든 0을 덮는 한 묶음에서 읽은 합항이 최종식입니다.
0 묶음 1 / 1개
최종식 확인 완료 · 입력 괄호식 2 / 2개 · 카르노맵 4칸
VERTICAL LINES & CIRCLES
Hotian’s Arrow
한 행 안은 OR, 여러 행 사이는 AND입니다.
묶음 A와 같은 이름의 행을 함께 읽습니다.
p가 참이면 p∨q와 p∨¬q도 참입니다. 남길 p행이 두 원래 행을 각각 보장하므로, 전체 뜻을 유지하며 두 긴 행을 정리합니다.
p
남은 한 행은 p입니다. 해소행 추가와 정리를 거쳐 원식과 같은 뜻을 보존했습니다.
해소 1 / 1회 · 행 정리 1 / 1회
입력 OR 행 2개 · 현재 남은 행 1개
행을 정리해도 같은 식인 근거
- 1·2행 → 3행 pq의 반대 원 한 쌍. 1행과 2행에서 q의 상보쌍 하나를 선택합니다. 두 행에 남은 p는 한 번만 적어 새 행으로 추가합니다.
- 정리한 행: 1, 2p가 참이면 p∨q와 p∨¬q도 참입니다. 남길 p행이 두 원래 행을 각각 보장하므로, 전체 뜻을 유지하며 두 긴 행을 정리합니다.
- 1행은 3행에 포함된 조건으로 충족됩니다.
- 2행은 3행에 포함된 조건으로 충족됩니다.
0 묶음에서 p=0은 고정되고 q는 0과 1로 바뀝니다. 이 묶음 밖에서 참이 되는 합항은 p이므로 전체 식은 p와 같습니다.
지도에서는 q가 바뀌는 두 칸을 묶고, 줄타기에서는 q와 ¬q를 해소한 뒤 p가 보장하는 긴 행을 정리합니다.
3변수 · 포섭
하나의 q가 세 행을 보장하기
q=0인 네 칸을 하나로 묶고, q∨r까지 불필요해지는 이유를 확인합니다.
두 풀이의 동치식이 같습니다: q. 묶음 A와 오른쪽의 같은 이름 행을 비교해 보세요.
KARNAUGH MAP
카르노맵
모든 괄호식을 함께 적용한 함수값입니다.
- A4개의 0을 한 묶음으로
q=0 → q
두 행에 걸친 q=0의 네 칸입니다. p와 r은 바뀌고 q=0만 고정되므로 합항 q를 읽습니다.
- ✓최종식 확인
q
한 묶음이 모든 0을 덮으므로, 읽은 합항 하나가 최종식입니다.
q
모든 0을 덮는 한 묶음에서 읽은 합항이 최종식입니다.
0 묶음 1 / 1개
최종식 확인 완료 · 입력 괄호식 3 / 3개 · 카르노맵 8칸
VERTICAL LINES & CIRCLES
Hotian’s Arrow
한 행 안은 OR, 여러 행 사이는 AND입니다.
묶음 A와 같은 이름의 행을 함께 읽습니다.
남길 q행은 p∨q, ¬p∨q, q∨r를 모두 보장합니다. 세 긴 행을 정리해도 새로운 참·거짓 경우가 생기지 않습니다.
q
q 하나가 원식과 정확히 같은 참·거짓 값을 갖습니다.
해소 1 / 1회 · 행 정리 1 / 1회
입력 OR 행 3개 · 현재 남은 행 1개
행을 정리해도 같은 식인 근거
- 1·2행 → 4행 qp의 반대 원 한 쌍. 1행과 2행의 p 상보쌍을 해소하면 q가 남습니다. 3행은 이 해소에 사용하지 않아도 됩니다.
- 정리한 행: 1, 2, 3남길 q행은 p∨q, ¬p∨q, q∨r를 모두 보장합니다. 세 긴 행을 정리해도 새로운 참·거짓 경우가 생기지 않습니다.
- 1행은 4행에 포함된 조건으로 충족됩니다.
- 2행은 4행에 포함된 조건으로 충족됩니다.
- 3행은 4행에 포함된 조건으로 충족됩니다.
q=0인 네 칸이 전체 0 영역이며 p와 r은 묶음 안에서 바뀝니다. q를 남기면 q∨r도 이미 보장되므로, 세 번째 합항을 따로 유지할 필요가 없습니다.
지도에서는 큰 0 묶음 하나가 모든 0을 덮고, 줄타기에서는 q행 하나가 원래 세 행을 포섭합니다.
4변수 · 8칸 묶음
겹치는 두 큰 묶음을 함께 읽기
p=0인 여덟 칸과 r=0인 여덟 칸을 묶어 p∧r를 얻습니다.
두 풀이의 동치식이 같습니다: p ∧ r. 묶음 A·B와 오른쪽의 같은 이름 행을 비교해 보세요.
KARNAUGH MAP
카르노맵
모든 괄호식을 함께 적용한 함수값입니다.
- A8개의 0을 한 묶음으로
p=0 → p
위쪽 두 행의 여덟 칸에서는 p=0만 고정됩니다. q, r, s가 바뀌므로 합항 p를 읽습니다.
- B8개의 0을 한 묶음으로
r=0 → r
왼쪽 두 열의 여덟 칸에서는 r=0만 고정됩니다. 첫 묶음과 네 칸이 겹치며, 합항 r를 읽습니다.
- ∧읽은 합항을 ‘그리고’로 묶기
p ∧ r
모든 0을 덮는 묶음에서 같은 함수의 식을 얻었습니다.
p ∧ r
0 묶음에서 읽은 합항들을 함께 적용합니다.
0 묶음 2 / 2개 · 식으로 묶기 1 / 1회
입력 괄호식 4 / 4개 · 카르노맵 16칸
VERTICAL LINES & CIRCLES
Hotian’s Arrow
한 행 안은 OR, 여러 행 사이는 AND입니다.
묶음 A·B와 같은 이름의 행을 함께 읽습니다.
p가 첫 두 행을, r가 나머지 두 행을 보장합니다. 네 긴 행을 정리하고 p와 r를 서로 다른 행에 유지합니다.
p ∧ r
남은 p행과 r행을 함께 읽은 p∧r가 원식과 동치입니다.
해소 2 / 2회 · 행 정리 1 / 1회
입력 OR 행 4개 · 현재 남은 행 2개
행을 정리해도 같은 식인 근거
- 1·2행 → 5행 pq의 반대 원 한 쌍. 1행과 2행의 q 상보쌍을 해소하여 p행을 추가합니다.
- 3·4행 → 6행 rs의 반대 원 한 쌍. 3행과 4행의 s 상보쌍을 해소하여 r행을 추가합니다. p행과 r행은 독립된 두 행으로 남깁니다.
- 정리한 행: 1, 2, 3, 4p가 첫 두 행을, r가 나머지 두 행을 보장합니다. 네 긴 행을 정리하고 p와 r를 서로 다른 행에 유지합니다.
- 1행은 5행에 포함된 조건으로 충족됩니다.
- 2행은 5행에 포함된 조건으로 충족됩니다.
- 3행은 6행에 포함된 조건으로 충족됩니다.
- 4행은 6행에 포함된 조건으로 충족됩니다.
두 0 묶음은 네 칸에서 겹쳐도 됩니다. 각각의 합항 p와 r를 AND로 묶으면 p∧r이며, 두 조건이 모두 참일 때만 전체 식이 참입니다.
카르노맵의 두 묶음은 줄타기의 서로 다른 p행과 r행에 대응하며, 두 결과를 한 OR 행으로 합치지 않습니다.
3변수 · 중복절
다른 두 행에서 이미 나오는 조건
q∨r가 나머지 두 합항에서 이미 따라 나온다는 근거를 확인합니다.
두 풀이의 동치식이 같습니다: (p ∨ q) ∧ (¬p ∨ r). 묶음 A·B와 오른쪽의 같은 이름 행을 비교해 보세요.
KARNAUGH MAP
카르노맵
모든 괄호식을 함께 적용한 함수값입니다.
- A2개의 0을 한 묶음으로
p=0, q=0 → p ∨ q
p=0, q=0인 두 칸에서 r가 바뀝니다. 두 고정값이 0이므로 합항 p∨q를 읽습니다.
- B2개의 0을 한 묶음으로
p=1, r=0 → ¬p ∨ r
아래 행의 양끝 열은 이웃입니다. p=1, r=0이 고정되므로 합항 ¬p∨r를 읽습니다.
- ∧읽은 합항을 ‘그리고’로 묶기
(p ∨ q) ∧ (¬p ∨ r)
모든 0을 덮는 묶음에서 같은 함수의 식을 얻었습니다.
(p ∨ q) ∧ (¬p ∨ r)
0 묶음에서 읽은 합항들을 함께 적용합니다.
0 묶음 2 / 2개 · 식으로 묶기 1 / 1회
입력 괄호식 3 / 3개 · 카르노맵 8칸
VERTICAL LINES & CIRCLES
Hotian’s Arrow
한 행 안은 OR, 여러 행 사이는 AND입니다.
묶음 A·B와 같은 이름의 행을 함께 읽습니다.
1·2행을 남기면 3행과 4행의 q∨r는 둘 다 다시 도출됩니다. 삭제할 두 행끼리 서로를 근거로 삼지 않고, 남는 두 행을 근거로 정리합니다.
(p ∨ q) ∧ (¬p ∨ r)
남은 두 행은 (p∨q)∧(¬p∨r)입니다. 원래 식의 모든 0과 1이 그대로 유지됩니다.
해소 1 / 1회 · 행 정리 1 / 1회
입력 OR 행 3개 · 현재 남은 행 2개
행을 정리해도 같은 식인 근거
- 1·2행 → 4행 q ∨ rp의 반대 원 한 쌍. 1행과 2행의 p 상보쌍을 해소하면 이미 3행에 있는 q∨r가 다시 나옵니다. 새 행은 이 조건이 두 행만으로 보장된다는 근거입니다.
- 정리한 행: 3, 41·2행을 남기면 3행과 4행의 q∨r는 둘 다 다시 도출됩니다. 삭제할 두 행끼리 서로를 근거로 삼지 않고, 남는 두 행을 근거로 정리합니다.
- 3행은 1·2행에서 p의 반대 원 한 쌍으로 다시 얻습니다.
- 4행은 1·2행에서 p의 반대 원 한 쌍으로 다시 얻습니다.
남길 두 행에서 q∨r를 다시 얻을 수 있으므로, 이 조건을 따로 요구하지 않아도 전체 뜻은 같습니다. 지도에서도 q∨r가 0인 칸은 선택한 두 묶음이 이미 나누어 덮습니다.
이 예제의 정리는 한 짧은 행의 포섭이 아니라, 남길 두 행에서 삭제할 조건을 재도출하는 방식입니다.
4변수 · 양쪽 경계 연결
네 모서리를 이어 한 묶음으로
좌상단 네 칸과 네 모서리의 네 칸을 묶어 두 합항을 읽습니다.
두 풀이의 동치식이 같습니다: (p ∨ r) ∧ (q ∨ s). 묶음 A·B와 오른쪽의 같은 이름 행을 비교해 보세요.
KARNAUGH MAP
카르노맵
모든 괄호식을 함께 적용한 함수값입니다.
- A4개의 0을 한 묶음으로
p=0, r=0 → p ∨ r
좌상단 2×2의 네 칸입니다. p=0, r=0이 고정되고 q와 s가 바뀌므로 합항 p∨r를 읽습니다.
- B4개의 0을 한 묶음으로
q=0, s=0 → q ∨ s
네 모서리는 양끝 행·열을 이어 만든 네 칸 묶음입니다. q=0, s=0이 고정되므로 합항 q∨s를 읽습니다. A와는 한 칸이 겹칩니다.
- ∧읽은 합항을 ‘그리고’로 묶기
(p ∨ r) ∧ (q ∨ s)
모든 0을 덮는 묶음에서 같은 함수의 식을 얻었습니다.
(p ∨ r) ∧ (q ∨ s)
0 묶음에서 읽은 합항들을 함께 적용합니다.
0 묶음 2 / 2개 · 식으로 묶기 1 / 1회
입력 괄호식 4 / 4개 · 카르노맵 16칸
VERTICAL LINES & CIRCLES
Hotian’s Arrow
한 행 안은 OR, 여러 행 사이는 AND입니다.
묶음 A·B와 같은 이름의 행을 함께 읽습니다.
p∨r는 1·2행을, q∨s는 3·4행을 각각 보장합니다. 네 긴 행을 정리하고 서로 다른 두 결과 행을 AND로 읽습니다.
(p ∨ r) ∧ (q ∨ s)
두 결과 행은 (p∨r)∧(q∨s)입니다. 0인 일곱 칸과 나머지 1인 칸 모두 원식과 일치합니다.
해소 2 / 2회 · 행 정리 1 / 1회
입력 OR 행 4개 · 현재 남은 행 2개
행을 정리해도 같은 식인 근거
- 1·2행 → 5행 p ∨ rq의 반대 원 한 쌍. 1행과 2행에서 q와 ¬q만 선택합니다. 남은 p와 r를 같은 새 행에 놓아 p∨r를 얻습니다.
- 3·4행 → 6행 q ∨ sr의 반대 원 한 쌍. 3행과 4행에서 r와 ¬r만 선택합니다. 나머지 q와 s로 q∨s행을 추가합니다.
- 정리한 행: 1, 2, 3, 4p∨r는 1·2행을, q∨s는 3·4행을 각각 보장합니다. 네 긴 행을 정리하고 서로 다른 두 결과 행을 AND로 읽습니다.
- 1행은 5행에 포함된 조건으로 충족됩니다.
- 2행은 5행에 포함된 조건으로 충족됩니다.
- 3행은 6행에 포함된 조건으로 충족됩니다.
- 4행은 6행에 포함된 조건으로 충족됩니다.
Gray 순서에서는 양끝 행과 양끝 열이 각각 이웃이어서 네 모서리를 하나의 네 칸 묶음으로 읽을 수 있습니다. 두 묶음은 좌상단 한 칸에서 겹치며, (p∨r)∧(q∨s)를 함께 나타냅니다.
지도에서 경계를 이어 찾는 두 묶음은 줄타기에서 q와 r를 각각 한 번 해소해 얻은 두 짧은 행에 대응합니다.
다섯 풀이를 마치고
칸과 행을 따라,
같은 함수를 정리했습니다.
카르노맵에서는 0인 칸을 묶고 고정된 변수로 합항을 읽었습니다. 줄타기에서는 행 사이의 관계를 확인하며 같은 뜻의 짧은 식으로 정리했습니다. 마지막 식은 처음 식과 모든 입력에서 같은 값을 냅니다.
0 묶음과 동치 정리를 읽는 방법
0인 칸만 1·2·4·8개처럼 2의 거듭제곱 개수로 묶어 직사각형을 만듭니다. 가장자리를 넘어 이어질 수 있고, 묶음끼리 겹쳐도 됩니다. 모든 0인 칸을 덮은 뒤 각 묶음의 합항을 AND로 연결합니다. 예를 들어 p=0, q=1로 고정된 묶음은 p ∨ ¬q로 읽습니다.
오른쪽은 시작 식을 OR 행으로 놓은 뒤, 해소로 새 행 추가·포섭·중복 조건 정리를 구분해 보여 줍니다. 포섭은 짧은 행이 긴 행의 조건까지 보장하여 긴 행을 정리하는 과정입니다. 남은 행 전체는 이전과 같은 함수를 나타냅니다.
표 채우기와 시작 행 준비, 이후의 묶음 읽기와 동치 정리는 따로 셉니다. 재생은 양쪽의 다음 기록을 한 단계씩 보여 주며, 횟수와 간격은 이 풀이에 표시한 절차를 기준으로 합니다.
규칙 확인: 0 묶음·Gray 순서·경계와 겹침 · POS 합항의 부호와 읽는 법