Boolean 함수 공간과 S₄ 군론적 분류 그리고 구조 인식 이론과의 연결
Gate-Generated Function Spaces, S₄ Orbit Classification of the Affine, Monotone and Self-Dual Subspaces of the 65,536 Four-Variable Boolean Functions, and Connection to Structure Recognition Theory
초록 (Abstract)
본 논문은 4변수 Boolean 함수 공간의 게이트 생성(Space(G)) 관점과 $S_4$ 군론 관점에서의 분류를 수학적으로 기술한다. 핵심 결과는 세 가지 주요 함수 공간에서의 완전한 궤도 분류다: Space(XOR)(아핀 함수 32개, $S_4$ 궤도 10개), Space(AND)(단조 함수 168개, $S_4$ 궤도 30개), Space(NOT)(자기쌍대 함수 256개, $S_4$ 궤도 32개). 또한 Space(NOT)에는 $S_4$ 불동점이 존재하지 않음을 증명한다(정리 3.5.2).
이 수학적 결과는 선행 연구 3편(Repo 1–3)의 경험적 발견을 군론 언어로 통일하며, 구조 인식 이론(SRT, Repo 4)의 핵심 가설(H3·H4·H8·H9)에 구체적인 수학적 대응을 제공한다. 분류의 정확성은 Burnside 보조정리에 의한 이론적 계산과 Python 컴퓨터 검증으로 양쪽에서 확인되었다.
1. 서론
1.1 연구의 배경
4변수 Boolean 함수 전체 공간 $\mathcal{F}_4$는 $2^{16} = 65{,}536$개의 함수를 포함한다. 이 방대한 공간 안에서 인간은 어떻게 주목할 만한 규칙적 구조를 발견하는가? 선행 연구(Repo 1–3)는 이 질문에 대한 경험적 관찰을 축적해 왔다.
- Repo 1 (KMap Structure Invariance): XOR/XNOR 체커보드 패턴의 변수 배열 불변성 발견
- Repo 2 (Symmetric Boolean Functions): 대칭 함수의 Hamming Weight Layer 구조 해석
- Repo 3 (Variable Rearrangement Invariance): 변수 재배열($S_4$ 순열) 하의 24개 순열 동치류 축약 실증
본 논문은 이 세 연구의 개별적 관찰을 게이트 생성 클론(Post Lattice)과 $S_4$ 군론이라는 하나의 수학적 프레임워크로 연결한다.
1.2 연구 목표
목표 1 (수학적 완전 분류): 주요 게이트(XOR, AND, NOT)가 생성하는 함수 공간 Space(G) 각각에서 $S_4$ 궤도 수를 Burnside 보조정리로, 궤도별 크기를 열거로 완전 결정한다.
목표 2 (SRT 이론적 연결): 구조 인식 이론(SRT)의 주의 필터(H3), 유의 필터(H4), 개념 진화(H8-H10) 가설에 수학적 엄밀성을 부여한다.
2. 이론적 배경
2.1 4변수 Boolean 함수 공간과 Space(G)
$$\mathcal{F}_4 = \{ f : \{0,1\}^4 \to \{0,1\} \}, \quad |\mathcal{F}_4| = 2^{16} = 65{,}536$$
게이트 집합 $G$와 입력 변수, 상수 $\{0, 1\}$만으로 합성 가능한 모든 함수의 집합을 $\text{Space}(G) = [G]$로 정의한다(표에서 '상수 제외'로 표시한 행은 상수 없이 합성). 이하 Space(XOR), Space(AND), Space(NOT)은 각각 위 표의 XOR, (AND, OR), (MAJ, NOT)이 생성하는 아핀 클론 $L$, 단조 클론 $M$, 자기쌍대 클론 $D$를 가리키는 약칭이다.
| 게이트 G | 생성 공간 Space(G) | 함수 수 | Post 격자 클론 |
|---|---|---|---|
| NAND / NOR | 전체 Boolean 공간 ($\Omega$) | 65,536 | 만능 클론 (Universal) |
| XOR | 아핀(Affine) 함수 공간 ($L$) | 32 | 선형 클론 |
| AND, OR (상수 포함) | 단조(Monotone) 함수 공간 ($M$) | 168 | 단조 클론 ($D(4)$ Dedekind 수) |
| MAJ, NOT (상수 제외) | 자기쌍대(Self-dual) 공간 ($D$) | 256 | 쌍대 클론 |
2.2 카르노맵의 환면체(Torus) 위상
4변수 카르노맵은 Gray Code 순서에 의해 상하 및 좌우 경계가 맞물린 2차원 토러스(Torus) 위상을 갖는다. 따라서 평면 상의 '모서리'나 '외곽'은 인간 시각 표현의 편의일 뿐이며, 본질적 불변성은 군 작용 하의 궤도에 존재한다.
CD
00 01 11 10
AB 00 | 0 | 1 | 3 | 2 | (Torus Topology)
01 | 4 | 5 | 7 | 6 | Row 00 ↔ Row 10 연결
11 |12 |13 |15 |14 | Col 00 ↔ Col 10 연결
10 | 8 | 9 |11 |10 |
2.3 Burnside의 보조정리
$|S_4| = 24$개 순열의 작용 하에서 궤도 수는 다음과 같이 계산된다:
$$|\text{Orbits}| = \frac{1}{|S_4|} \sum_{\sigma \in S_4} |\text{Fix}(\sigma, \text{Space}(G))|$$
3. 핵심 결과: S₄ 궤도 완전 분류
3.1 Space(XOR) = L (아핀 이론): 10개 궤도
아핀 함수 $f = a_0 \oplus a_1 A \oplus a_2 B \oplus a_3 C \oplus a_4 D$ (32개). Burnside 계산:
$$|\text{Orbits}(S_4, L)| = \frac{1}{24}(32 + 6 \times 16 + 8 \times 8 + 6 \times 4 + 3 \times 8) = \frac{240}{24} = \mathbf{10}$$
$\{0, 1, A \oplus B \oplus C \oplus D, A \oplus B \oplus C \oplus D \oplus 1\}$
특히 $A \oplus B \oplus C \oplus D$ (체커보드)는 $S_4$ 모든 원소에 의해 불변인 불동점으로, Repo 1의 발견이 군론적으로 완전히 증명된다.
3.2 Space(AND) = M (단조 이론): 30개 궤도
단조 함수 $D(4) = 168$개. Burnside 계산:
$$|\text{Orbits}(S_4, M)| = \frac{1}{24}(168 + 6 \times 50 + 8 \times 15 + 6 \times 8 + 3 \times 28) = \frac{720}{24} = \mathbf{30}$$
Hamming Weight에만 의존하는 대칭적 단조 함수(Threshold Function) 6개:
$\{f_0, f_1, f_2, f_3, f_4, f_{1+}\}$ — Repo 2의 대칭 함수 층 구조(32개 완전 대칭 함수) 가운데 단조인 6개에 해당한다.
3.3 Space(NOT) = D (자기쌍대 이론): 32개 궤도
자기쌍대 함수 256개. Burnside 계산:
$$|\text{Orbits}(S_4, D)| = \frac{1}{24}(256 + 6 \times 64 + 8 \times 16 + 6 \times 0 + 3 \times 0) = \frac{768}{24} = \mathbf{32}$$
정리: Space(NOT) = D에는 $S_4$ 불동점이 존재하지 않는다 ($\text{Fix}(4\text{-cycle}, D) = 0$).
수학적 의미: 4변수에서 "자기쌍대이면서 완전 변수-대칭적인 함수"는 수학적으로 존재할 수 없다.
4. 선행 연구 통합 (Repo 1–3)
| 선행 리포지토리 | 경험적 관찰 | 본 연구의 군론적 증명 |
|---|---|---|
| Repo 1 (KMap Structure) | XOR 체커보드 패턴의 변수 불변성 | $A \oplus B \oplus C \oplus D$(및 그 보수)는 $\text{Space(XOR)}$의 비상수 전역 $S_4$ 불동점 |
| Repo 2 (Symmetric Function) | Hamming Weight Layer 구조 | 대칭적 단조 함수 6개 = $\text{Space(AND)}$의 $S_4$ 불동점 |
| Repo 3 (Variable Rearrangement) | 24개 순열의 3대 대표 배열 축약 | 카르노맵 격자 대칭군(토러스 이동 포함) 하에서 24개 배열이 3개 동치류로 나뉨 (위의 $S_4$ 궤도 계산과는 별개의 작용) |
5. 구조 인식 이론(SRT)과의 수학적 연결
본 논문의 궤도 분류는 인간의 인지적 주의(Attention)와 연구 유의성 판단에 관한 SRT 가설을 수학적 구조(궤도 크기)와 연결해 해석한다:
- H3 (주의 착지 필터): $S_4$ 불동점(궤도 크기 1)은 24개 모든 배열에서 동일 패턴을 유지하며, 이는 인간의 주의가 먼저 착지할 것이라는 H3의 예측과 일치한다.
- H4 (유의성 필터): 궤도 크기는 압축성(Compressibility)의 후보 지표로 제안되지만, 압축성의 정의와 연구 가치와의 관계는 후속 과제이다(예: 상수 0, 1은 궤도 크기 1이지만 연구 가치가 높다고 할 수 없다).
- H8–H10 (개념 진화 연쇄): 체커보드(Repo 1) ⟶ 불변성 렌즈(Repo 2,3) ⟶ SRT 메타이론(Repo 4) ⟶ $S_4$ 군론 완전 분류(Repo 6)로 이어지는 자율적 개념 진화의 실증 사례.
6. 연구 기원 타임라인
↓
Phase 1: Karnaugh Map 체커보드 발견 (Repo 1: XOR 불변성)
↓
Phase 2: 대칭 Boolean 함수의 시각 패턴 분석 (Repo 2: Layer 구조)
↓
Phase 3: 변수 재배열 동치류 분류 (Repo 3: S₄ 작용 발견)
↓
Phase 4: Structure Recognition Theory 정립 (Repo 4: 인지 메타이론)
↓
Phase 5: Boolean 함수 공간과 S₄ 군론적 분류 (Repo 6: 완전한 수학적 원점 복귀)
7. 결론 및 향후 연구
- 4변수 Boolean 함수 공간 Space(XOR), Space(AND), Space(NOT)의 $S_4$ 궤도 완전 분류 (10, 30, 32개)
- Space(NOT) 내 $S_4$ 불동점 부재 정리(3.5.2) 엄밀 증명
- 선행 3대 경험적 연구(Repo 1–3)의 군론적 정제 관계 규명
- SRT 인지 가설(H3, H4)에 대응하는 수학적 후보 지표(궤도 크기) 제시
참고 저장소 및 관련 문서
| 문서 / 리포지토리 | 내용 | 본 연구와의 관계 |
|---|---|---|
| 1KMapStructureInvariance | K-Map 패턴 불변성 발견 | Space(XOR) 체커보드 불동점 실증 사례 |
| 2SymmetricBooleanFunctionMinorThesis | 대칭 함수 K-Map 패턴 | Space(AND) 대칭적 단조 함수 불동점 대응 |
| 3VariableRearrangementInvarianceMinorThesis | 변수 재배열 동치류 분류 | $S_4$ 순열 작용의 경험적 기초 |
| 4StructureRecognitionTheory (SRT) | SRT 통합 인지 프레임워크 | H3, H4, H8-H10 가설의 이론적 허브 |
| theory/02_S4GroupAnalysis.pdf | S₄ 군론 분석 이론서 (14p) | §3 궤도 분류 세부 증명 원본 PDF |