Minor Thesis · Empirical Case Study 3

Paper 3

카르노맵 패턴의 변수 재배열 기반 해석

구조적 불변성 연구 — Variable Rearrangement Invariance in Karnaugh Map Patterns

Repository: 3VariableRearrangementInvarianceMinorThesis · Choi Jonghun · Independent researcher · Graduate of Inha Technical College

초록 / Abstract

Abstract

카르노맵(Karnaugh Map)은 불 함수(Boolean Function)의 시각적 표현 도구로서 논리식 최소화에 주로 사용되어 왔다. 그러나 동일한 함수라도 변수의 배치 순서가 달라지면 카르노맵 위의 시각 패턴이 변화한다는 사실에 주목할 때, 새로운 연구 질문이 제기된다.

본 연구는 변수 재배열(variable rearrangement)에 따라 카르노맵의 시각 패턴이 어떻게 변화하는지 분석하고, 변화 과정에서도 유지되는 구조적 불변성(structural invariance)을 탐색한다. 분석 대상으로는 체커보드, 대각선, 모서리, 고리, 블록 등 특징적인 시각 패턴을 형성하는 함수를 선정하였으며, 가능한 변수 배열 24종(S₄ 순열)을 체계적으로 비교하였다.

분석 결과, 변수 재배열에 따라 패턴의 위치·방향·대칭축은 변화하지만, 논리적 구조·1의 개수· 패턴의 생성 원인은 유지됨을 확인하였다. 본 연구는 구조적 불변성을 논리적·수량적·관계적· 구조적 불변성으로 분류하는 탐색적 틀을 제안하며, 변수 재배열을 구조 탐색 도구로 활용하는 가능성을 논의한다.

✓ 변수 재배열 후에도 유지되는 것

논리함수 자체의 의미
1이 포함된 셀의 개수 (Hamming weight)
패턴의 생성 원인 (XOR 관계 등)
셀 간 논리적 연결 구조
완전대칭함수의 Layer 구조

✕ 변수 재배열에 따라 변화하는 것

패턴의 위치
패턴의 방향 (회전·반사)
대칭축의 형태
시각적 배치 형태
인간이 인식하는 표면적 구조

이론적 배경

카르노맵과 변수 배열

4변수 카르노맵은 변수 A, B, C, D에 대해 16개의 셀로 구성된 2차원 표현이다. 행과 열은 일반적으로 Gray Code 순서(00 01 11 10)로 배열되며, 인접 셀 사이에서 정확히 하나의 변수만 달라지는 인접성 보존 성질을 가진다.

변수의 배치 순서, 즉 행 레이블에 어떤 변수를 쓰고 열 레이블에 어떤 변수를 쓸지를 결정하는 것을 변수 배열(variable arrangement)이라 한다. 4개 변수에 대해 가능한 순열은 4! = 24종이며, 이는 S₄ 대칭군의 원소들에 대응한다.

대표 배열과 동치류

행/열 내부의 순서 교환과 행·열 축 교환이 동일한 시각 패턴을 생성함을 고려하면, 24개의 배열은 구조적으로 동치인 것끼리 묶을 수 있다. 선행 연구(Paper 1)에서는 이 동치류가 정확히 3개의 대표 배열로 축약됨을 증명하였다.

AB / CD (대표 1) AC / BD (대표 2) AD / BC (대표 3) BA / CD AB / DC CD / AB CA / BD AC / DB BD / AC DA / BC … (총 24종)

굵은 배경 = 대표 배열 3종; 나머지는 동치 변환으로 대표 배열 중 하나와 동치.

구조적 불변성 개념

수학과 과학의 다양한 분야에서는 변환이 이루어지더라도 유지되는 성질을 불변성(invariance) 이라 부른다. 예컨대 도형의 합동 변환(회전·반사·평행이동) 하에서 넓이와 둘레는 불변이다.

본 연구에서는 변수 재배열이라는 변환 하에서 카르노맵의 어떤 구조적 특성이 불변인지를 탐색한다. 이를 구조적 불변성(structural invariance)이라 정의한다.

연구 방법

분석 대상 선정

시각적으로 특징적인 패턴을 형성하는 함수들을 분석 대상으로 선정하였다.

체커보드 패턴

XOR, XNOR — 1과 0이 교차 배치되는 패턴. Gray Code 인접성과 층 구조의 결합에서 발생.

대각선 패턴

특정 변수 간 관계가 강조될 때 나타나는 패턴. 배열 변경에 따라 방향이 크게 변화.

모서리 패턴

Exactly-1, Exactly-3 — 네 모서리에 1이 배치. 변수 재배열 후에도 논리적 구조 유지.

고리 패턴

Exactly-2 — Hamming Weight Layer L₂에 해당하는 6개 셀이 고리 형태로 연결.

블록 패턴

특정 변수 조합이 고정될 때 인접 셀이 하나의 블록을 형성. 위치는 변화하나 크기 유지.

비교 기준

비교 항목	분류	분석 내용
셀 개수	수량적	1이 존재하는 셀 수 (Hamming weight)
패턴 형태	시각적	점, 선, 블록, 체커보드, 대각선 등
대칭성	구조적	대칭 구조 유지 여부 및 대칭축 변화
연결성	관계적	인접 관계 및 연결 구조 유지 여부
위치	시각적	패턴의 이동 방향과 폭
방향	시각적	회전 및 반사 여부

변수 재배열에 따른 패턴 변화 분석

체커보드 패턴 — XOR / XNOR

XOR 함수는 Gray Code 배열(0132)에서 1과 0이 수평·수직 방향으로 교차하는 체커보드 패턴을 형성한다. 변수 재배열을 적용하더라도 체커보드의 반복 구조는 사라지지 않는다. 그러나 반복 방향이나 배치 방식은 변화할 수 있다.

이는 체커보드 패턴이 배열 방식의 산물이 아니라 XOR 함수의 홀수 Layer 선택 구조에서 비롯된 것임을 의미한다. 따라서 체커보드의 근본 원인은 변수 재배열에 의해 변하지 않는다.

기본 배열(AB/CD)에서의 XOR 체커보드 패턴 — **그림 04–07.** XOR/XNOR 체커보드 패턴 — 기본 배열 및 재배열 후 비교

변수 재배열 후 XOR 패턴의 변화 — **그림 04–07.** XOR/XNOR 체커보드 패턴 — 기본 배열 및 재배열 후 비교

대각선 패턴

대각선 패턴은 변수 재배열에 의해 방향이 크게 변한다. 특정 배열에서 오른쪽 아래 방향(↘)으로 나타나던 패턴이 다른 배열에서는 블록 또는 반복 구조로 표현될 수 있다.

이는 대각선 자체가 불변 요소가 아니라, 특정 구조가 현재 변수 배열에서 "투영(projection)"된 결과임을 시사한다.

대각선 패턴 대표 사례 1 — **그림 12–13.** 대각선 패턴 — 변수 재배열에 따른 변화

대각선 패턴 대표 사례 2 — **그림 12–13.** 대각선 패턴 — 변수 재배열에 따른 변화

모서리 패턴 — Exactly-1 / Exactly-3

Exactly-1 함수는 Weight = 1 상태 4개를 선택하며 카르노맵 상에서 모서리 방향으로 분산된 구조를 보인다. 변수 재배열 이후에도 1의 개수(= 4)와 논리적 구조는 유지되지만, 위치와 배치 패턴은 변화할 수 있다.

Exactly-1 함수의 모서리 패턴 — **그림 08, 10.** 모서리 패턴 — 재배열 전후 비교

Exactly-3 함수의 모서리 패턴 — 재배열 전후 비교 — **그림 08, 10.** 모서리 패턴 — 재배열 전후 비교

고리 패턴 — Exactly-2

Exactly-2 함수는 Hamming Weight Layer L₂에 해당하는 6개 셀을 선택한다. Gray Code 배열에서 이 셀들은 연결된 고리 형태를 보이며, 변수 재배열 후에도 동일 Layer 구조에서 유래한 특성이 유지된다.

Exactly-2 함수의 고리 패턴 — **그림 09.** 고리 패턴 — Exactly-2 함수 (Hamming Weight Layer L₂)

블록 패턴

특정 변수 조합이 고정될 때 형성되는 블록 패턴은 변수 재배열 후 위치가 이동하지만, 블록의 크기와 내포하는 논리적 관계는 유지된다. 이는 위치 변화와 구조 유지가 공존하는 대표 사례이다.

변수 재배열 후 블록 패턴 위치 변화 1 — **그림 14–15.** 블록 패턴 — 위치 변화와 구조 유지

구조적 불변성 기반 해석

카르노맵의 재해석

전통적으로 카르노맵은 논리식 최소화 도구로 사용되었다. 그러나 본 연구는 카르노맵을 구조적 불변성의 시각적 탐색 도구로 재해석할 것을 제안한다.

변수 재배열의 역할

변수 재배열은 단순히 표현을 바꾸는 것이 아니다. 다양한 배열을 통해 동일 함수를 여러 관점에서 관찰하면, 우연히 발생한 시각적 특징과 함수의 구조에서 필연적으로 발생하는 특징을 구분할 수 있다.

하나의 관점에서 관찰 → "이 패턴은 이 배열에서만 나타나는가?"
여러 배열에서 반복 확인 → "이 패턴은 구조적 불변성이다"

이런 의미에서 변수 재배열은 구조를 드러내기 위한 분석 도구로서의 역할을 한다.

연구 가설

본 연구는 다음 탐색적 가설을 제안한다.

카르노맵의 시각 패턴에서 관찰되는 대칭성·반복성·연결성은, 함수 자체의 구조적 특성이 특정 배열 방식을 통해 2차원 평면 위에 투영된 결과일 수 있다. 변수 재배열은 이 투영의 방향을 바꿈으로써 숨겨진 구조를 드러내거나 강조할 수 있다.

결론

본 연구는 변수 재배열에 따른 카르노맵 패턴 변화를 분석하고, 변화 속에서 유지되는 구조적 불변성을 탐색하였다.

분석 결과, 패턴의 위치·방향·대칭축은 변화하지만, 논리적 구조·1의 개수·패턴의 생성 원인은 변수 재배열에 의해 영향받지 않는 불변 요소임을 확인하였다. 이를 논리적·수량적·관계적·구조적 불변성으로 분류하는 탐색적 틀을 제안하였다.

핵심 기여

카르노맵을 논리식 최소화 도구를 넘어 시각적 구조 분석 대상으로 확장
변수 재배열에 따른 패턴 변화의 체계적 분석 및 분류
구조적 불변성의 네 가지 유형 분류 (논리적·수량적·관계적·구조적)
변수 재배열을 구조 탐색 도구로 활용하는 방법론 제안
S₄ 군론을 통한 형식적 불변성 이론으로의 확장 가능성 제시

향후 연구 방향

S₄ 대칭군의 작용과 구조적 불변성의 수학적 관계 형식화, 5변수 이상 확장, 그리고 인간이 변수 재배열 과정에서 어떻게 구조를 인식하는지에 대한 인지과학적 탐구가 향후 과제이다. 이 마지막 방향은 Structure Recognition Theory (Paper 4)와 직접적으로 연결된다.

연구 프로그램 내 위치

이 논문은 Structure Recognition Research Program의 세 번째 경험적 사례 연구이다. Papers 1–3은 Paper 4(Structure Recognition Theory)의 경험적 토대를 구성한다.

Series — Structure Recognition Research Program

1 KMap Structure Invariance — XOR/XNOR 체커보드 패턴 발견 및 분류

2 Symmetric Boolean Function Patterns — Hamming Weight Layer 구조 해석

3 Variable Rearrangement Invariance — 구조적 불변성 탐색 (현재 페이지)

4 Structure Recognition Theory — 메타 이론적 통합 프레임워크

5 Human-AI Research Collaboration — 장기 인간-AI 공동 연구 방법론

프로그램 허브: Research Portfolio · AI 작업 공간: ANTIGRAVITY