Boolean 함수 공간과 S₄ 군론적 분류 그리고 구조 인식 이론과의 연결

초록 (Abstract)

1. 서론

1.1 연구의 배경

4변수 Boolean 함수 전체 공간 $\mathcal{F}_4$는 $2^{16} = 65{,}536$개의 함수를 포함한다. 이 방대한 공간 안에서 연구할 "주목할 만한 구조"를 발견하는 과정은 어떻게 이루어지는가? 선행 연구(Repo 1–3)는 이 질문에 대한 경험적 관찰을 축적해 왔다.

• Repo 1 — Karnaugh map에서 특정 함수들이 변수 배열에 무관하게 동일한 패턴을 보임을 발견
• Repo 2 — 대칭 Boolean 함수들이 Hamming weight 레이어 구조를 형성함을 관찰
• Repo 3 — 변수 재배열(S₄ 치환) 하의 동치류를 체계적으로 분류

이 세 연구는 각각 독립적으로 진행되었으나, 하나의 공통 수학적 프레임워크로 통합될 수 있다는 감각이 본 연구의 출발점이다.

1.2 연구 목표

본 연구는 두 가지 목표를 가진다.

목표 1 (수학적). 4변수 Boolean 함수 공간의 게이트 생성 관점과 S₄ 군론 관점에서의 완전한 분류를 수행한다. 구체적으로, 주요 게이트(XOR, AND, NOT)로 생성되는 함수 공간 Space(G) 각각에서 S₄ 작용에 의한 궤도 수 및 각 궤도의 구조를 결정한다.

목표 2 (이론적). 분류 결과를 구조 인식 이론(SRT, Repo 4)의 핵심 가설들과 연결한다. 특히, 수학적 분류가 "인간이 어떤 함수에 먼저 주의를 기울이는가"(H3)와 "어떤 함수를 연구 가치가 있다고 판단하는가"(H4)를 설명하는 데 어떻게 기여하는지를 논의한다.

1.3 논문의 구성

§2에서 이론적 배경(Space(G) 정의, Post 격자, 카르노 맵 기하학)을 정리한다. §3에서 핵심 수학적 결과인 S₄ 궤도 분류를 공간별로 전개한다. §4에서 선행 연구(Repo 1–3)와의 통합 관계를 명식한다. §5에서 SRT 가설과의 연결을 논의한다. §6에서 이 연구에 이르기까지의 연구 기원 타임라인을 정리한다.

2. 이론적 배경

2.1 4변수 Boolean 함수 공간

정의 2.1 (전체 함수 공간).

$$\mathcal{F}_4 = \{ f : \{0,1\}^4 \to \{0,1\} \}$$

이 공간의 크기: $|\mathcal{F}_4| = 2^{2^4} = 2^{16} = 65{,}536$. 각 함수는 16비트 진리표 벡터, 4×4 카르노 맵, 또는 게이트 회로로 표현된다.

2.2 게이트 생성 함수 공간 Space(G)

단일 게이트 G에 의해 G만을 사용하여 구성 가능한 모든 Boolean 함수의 집합을 Space(G)로 정의한다.

정의 2.2 (Space(G)).

$$\text{Space}(G) = \{ f \in \mathcal{F}_4 \mid f\text{는 게이트 }G\text{와 입력 변수, 상수 }\{0,1\}\text{만으로 구성 가능} \}$$

이는 수학적 클론(clone) 개념과 일치한다: $\text{Space}(G) = [G]$ (G가 생성하는 Post 클론).

명제 2.1 (Space(G)의 S₄ 불변성). 정의된 게이트 G에 대해, Space(G)는 S₄ 작용 하에 닫혀 있다. 즉, $f \in \text{Space}(G)$이고 $\sigma \in S_4$이면 $f \circ \sigma \in \text{Space}(G)$.

증명 요지: f가 G-게이트만으로 구현되는 회로를 가진다면, $f \circ \sigma$는 같은 회로에서 입력 레이블만 재배치한 것이다. 회로의 게이트 종류(G)는 변하지 않으므로 $f \circ \sigma \in \text{Space}(G)$. □

이 명제의 결론으로, 각 Space(G)는 S₄ 궤도들의 합집합으로 분해된다.

2.3 Post의 격자와 만능성

정리 2.1 (Post, 1941). Boolean 함수 집합 $F$가 함수적으로 완전하기 위한 필요충분조건은 F가 다음 5가지 Post 클래스 중 어느 것에도 포함되지 않는 것이다.

NAND는 5가지 클래스 중 어느 것도 보존하지 않으므로 만능 게이트다.

2.4 카르노 맵의 기하학적 해석

4변수 카르노 맵은 단순한 회로 최소화 도구가 아니라 $\mathcal{F}_4$를 기하학적으로 시각화하는 공간이다.

        CD
        00  01  11  10
AB  00 | 0 | 1 | 3 | 2 |
    01 | 4 | 5 | 7 | 6 |
    11 |12 |13 |15 |14 |
    10 | 8 | 9 |11 |10 |
    

• 인접 칸끼리 정확히 한 변수만 다름 (Gray 코드 순서)
• 맵은 환면체(Torus) 위에 놓인 구조: AB=00 행과 AB=10 행이 연결되고, CD=00 열과 CD=10 열이 연결된다
• ⚠️ 위상적 함의: 토러스이므로 "좌상단", "우하단", "모서리" 등 절대 위치 표현은 의미가 없다 — 어떤 셀도 다른 셀보다 특별히 "끝"에 있지 않으며, 패턴의 위치는 변수 배열 방식에만 의존한다
• 65,536개 Boolean 함수 = 4×4 격자의 서로 다른 0/1 채색

Space(G)에 속하는 함수들은 카르노 맵 위에서 공통 시각적 시그니처를 보인다: 아핀 함수의 체커보드·줄무늬 패턴, 단조 함수의 "위로 닫힌(upward-closed)" 패턴 (단, Gray 코드 배열로 인해 이 패턴은 직관적 방향과 일치하지 않을 수 있으며, "왼쪽 위"처럼 보이는 것은 배열 방식의 결과일 뿐임), 자기쌍대 함수의 180° 회전 후 0↔1 교환하는 패턴.

2.5 S₄의 Boolean 함수에 대한 작용

표기: $S_4$ = 4개 원소 $\{A, B, C, D\}$의 모든 순열들의 군 (크기 24).

작용:

$$(\sigma \cdot f)(A, B, C, D) = f(\sigma^{-1}(A), \sigma^{-1}(B), \sigma^{-1}(C), \sigma^{-1}(D))$$

S₄의 5가지 켤레류(conjugacy class):

Burnside의 보조정리. S₄ 궤도 수를 계산하는 핵심 공식:

$$|\text{Orbits}| = \frac{1}{|S_4|} \sum_{\sigma \in S_4} |\text{Fix}(\sigma, \text{Space}(G))|$$

여기서 $\text{Fix}(\sigma, \text{Space}(G)) = \{ f \in \text{Space}(G) : f \circ \sigma = f \}$이다.

3. 핵심 결과: S₄ 궤도 완전 분류

3.1 Space(XOR) = L (아핀 이론): 10개 궤도

3.1.1 구조

4변수 아핀 함수:

$$f(A, B, C, D) = a_0 \oplus a_1 A \oplus a_2 B \oplus a_3 C \oplus a_4 D, \quad a_i \in \{0, 1\}$$

전체 원소 수: $2^5 = 32$개.

S₄ 작용의 효과: 순열 σ가 변수 $x_i$와 $x_j$를 교환하면, 불동점 조건은 $a_i = a_j$.

3.1.2 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}$$

3.1.3 10개 궤도 완전 열거

검증: $1+1+4+4+6+6+4+4+1+1 = 32$ ✓

3.1.4 S₄ 불동점

S₄의 모든 원소에 의해 고정되는 함수(4-순환 조건: $a_1 = a_2 = a_3 = a_4$):

3.2 Space(AND) = M (단조 이론): 30개 궤도

3.2.1 구조

4변수 단조 함수의 수: Dedekind 수 D(4) = 168.

단조 함수는 반사슬(antichain) $\mathcal{A} \subseteq 2^{\{A,B,C,D\}}$와 일대일로 대응한다: $f_\mathcal{A}(x) = 1$ iff $\exists S \in \mathcal{A}$ s.t. $S \subseteq \{i : x_i = 1\}$.

3.2.2 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}$$

검증: Python 직접 열거(컴퓨터 계산)로 30개 독립 확인, 크기 합 = 168 ✓

3.2.3 S₄ 불동점: 대칭적 단조 함수 6개

S₄ 전체에 의해 고정되는 단조 함수는 입력의 Hamming 가중치(HW)에만 의존하는 함수, 즉 대칭적 단조 함수(threshold function)다.

3.3 Space(NOT) = D (자기쌍대 이론): 32개 궤도

3.3.1 구조

자기쌍대 함수: $f(\bar{x}) = \overline{f(x)}$를 만족하는 함수. 4변수 자기쌍대 함수의 수: 256개.

3.3.2 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}$$

3.3.3 핵심 정리: S₄ 불동점 부재

3.4 L ∩ M 공간: 3개 궤도

선형이면서 단조인 함수들의 교집합. 4변수에서 총 6개 함수:

$\{0,\ 1,\ A,\ B,\ C,\ D\}$ — 상수 함수 2개 + 단일 변수 투영 4개.

4. 선행 연구 통합 (Repo 1–3)

4.1 통합의 원리: 정제 관계

선행 연구 3편의 핵심 발견들은 본 논문의 S₄ 궤도 분류로 수학적으로 재해석된다. 각 Repo의 관찰은 특정 Space(G)와 특정 궤도에 대응한다.

4.2 Repo 1 연결: 체커보드 = Space(XOR)의 S₄ 불동점

Repo 1의 핵심 발견: "XOR 함수 $A \oplus B \oplus C \oplus D$는 변수 배열에 무관하게 동일한 체커보드 패턴을 보인다."

4.3 Repo 2 연결: 대칭 함수 = Space(AND)의 S₄ 불동점

Repo 2의 핵심 발견: "대칭 Boolean 함수들이 Hamming weight 레이어 구조를 형성한다."

4.4 Repo 3 연결: 변수 재배열 = S₄ 군 작용

Repo 3의 핵심 작업: "변수 재배열(S₄ 치환) 하의 동치류를 체계적으로 분류."

4.5 통합 정리

5. 구조 인식 이론(SRT)과의 연결

5.1 SRT 핵심 가설 요약

SRT(Repo 4)는 "인간이 어떻게 새로운 구조를 인식하고 연구 질문을 생성하는가"를 설명하는 메타 이론이다. 본 논문과 관련된 핵심 가설:

5.2 S₄ 불동점과 H3: 주의 필터의 수학적 설명

H3의 예측: 인간은 65,536개의 K-map 패턴 중 특정 패턴에 먼저 주의를 기울인다.

수학적 설명: S₄ 불동점 함수는 24가지 변수 배열 모두에서 동일한 패턴을 보인다. 반면 궤도 크기가 큰 함수는 대부분의 배열에서 다른 패턴을 보인다. 따라서, 임의의 변수 배열에서 카르노 맵을 관찰했을 때:

• S₄ 불동점 (궤도 크기 1): 어떤 배열에서도 동일한 패턴 → 계획적으로 "눈에 띄는" 함수
• 궤도 크기 큰 함수 (크기 12, 24): 배열에 따라 다른 패턴 → 우연히 발견하기 어려움

$$\text{H3 예측 주의 순서: 아핀(체커보드) > 대칭(Maj) > 2-AND/2-OR > 일반 함수}$$

5.3 궤도 크기 스펙트럼과 H4: 유의 필터의 수치화

H4는 "연구 가치가 있는 구조를 판단하는 기준"으로 압축성(compressibility)을 제안한다. 궤도 크기는 압축성과 역비례한다:

Space(NOT)의 의의: Space(NOT)에 S₄ 불동점이 없다는 사실은 "자기쌍대이면서 완전히 변수-대칭적인 함수"가 존재하지 않음을 뜻한다. 이는 H4 유의 필터 관점에서, 자기쌍대 공간은 다른 공간(아핀, 단조)보다 "완벽히 규칙적인" 구조를 포함하지 않는다는 새로운 의미를 가진다.

5.4 H8–H9–H10: 개념 진화의 실사례

본 연구 프로그램 전체가 H8→H9→H10의 연쇄적 동작의 실사례를 보여준다:

특히 Repo 1의 체커보드 발견과 Repo 6의 S₄ 불동점 분류가 정확히 같은 함수를 지목한다는 사실은 H5(설명 예감)에 대한 증거다: 연구자가 처음 "왜?"라고 물었던 바로 그 함수가, 수학적으로도 "가장 설명 가치가 있는" 함수(S₄ 불동점)임이 드러났다.

6. 연구 기원 타임라인

이 연구에 이르기까지의 인지 발달 과정을 SRT 프레임으로 정리한다. 개인 경험 섹션은 연구자가 직접 보완해야 한다.

Phase 0 — 패턴 인식의 시작

SRT 프레임: 이 경험은 H3(주의 필터)의 최초 동작 시점이며, H1(구조 발견자 가설)의 원형이다.

Phase 1 — Karnaugh Map 체커보드 발견 (→ Repo 1)

핵심 발견 (문서화됨): 4변수 카르노 맵에서 XOR 함수($A \oplus B \oplus C \oplus D$)가 만드는 체커보드 패턴은 변수 배열 방식에 무관하게 동일하다. 현재(Repo 6)의 군론적 설명: 체커보드는 Space(XOR)의 S₄ 불동점.

SRT 프레임: H3 최초 동작 (주의 착지) → H5 발동 (설명 예감).

Phase 2 — 대칭 Boolean 함수의 시각 패턴 (→ Repo 2)

SRT 프레임: H4 동작 (유의 필터 — 이 구조는 연구 가치가 있는가?) → H6 동작 (설명적 의미성).

Phase 3 — 변수 재배열 동치류 분류 (→ Repo 3)

SRT 프레임: H9 동작 — "불변성" → "S₄ 작용"으로 개념 진화.

Phase 4 — 구조 인식 이론 (→ Repo 4, 5)

SRT 프레임: H10 동작 — SRT 자체가 Repo 5, 6을 생성하는 생성적 개념이 됨.

Phase 5 — Boolean 함수 공간 이론 (→ Repo 6, 현재)

SRT 프레임: H8 동작 — Space(G) 개념이 렌즈로 기능 → Repo 1의 체커보드가 이제 군론으로 완전히 설명됨.

7. 결론 및 향후 연구

7.1 주요 성과 요약

7.2 이론적 의의

• 수학적 의의: 4변수 Boolean 함수 공간을 게이트 생성 관점과 군론적 관점에서 완전히 분류. Post 격자의 주요 클래스들에 대한 S₄ 궤도 구조를 명시화.
• SRT와의 연결: 인간의 구조 인식(H3·H4)에 수학적 대응물을 제시 — 궤도 크기가 주의 순서와 연구 유의성 판단의 정량적 척도가 될 수 있음.
• H8·H9 실사례: 본 연구 프로그램 전체의 개념 발전 경로(체커보드 → 불변성 → S₄ 작용 → 구조 인식)가 H8·H9·H10의 연쇄 동작을 보여준다.

7.3 향후 연구

향후 연구의 전체 로드맵과 세부 계획: FUTURE_RESEARCH.md

참고 저장소 및 관련 문서

본 논문은 6BooleanFunctionSpaceTheory 저장소의 Phase 1·2 완료 시점을 기준으로 작성된 통합 본문 문서입니다.
Phase 3(인지 실험)은 후속 연구로 이관되었습니다. §6의 [연구자 보완 필요] 섹션은 연구자가 직접 채워야 합니다.
관련 이론: StructureRecognitionTheory_Unified.md H8·H9·H10, Def. 3.1–3.3