보관된 이전 연구 노트. 이 저장소는 저자의 이전 연구 노트이며, 내용은 7번 논문(수학)과 8번 논문(이론과 사례)으로 정리·정정되었습니다. 일부 서술과 옛 포털에는 정정 전 내용이 있을 수 있으니 인용은 7·8번을 사용해 주세요.
연구 제목: Boolean Function Space Theory
부제: Gate-Generated Function Spaces, Karnaugh Map Geometry, and Structural Classification
GitHub Pages: 논문 온라인 보기
Boolean function space, Post's lattice, clone theory, gate-generated function space, Karnaugh map geometry, structural classification, universal gate, function space visualization, affine functions, monotone functions, self-dual functions, constructibility, structure recognition
This repository investigates the structure of Boolean function spaces generated by single primitive gates, and explores how these spaces can be recognized, classified, and visualized through Karnaugh maps.
The central research question is: What is the mathematical structure of the function space generated by a single gate G?
Unlike conventional digital logic courses that focus on gate design and circuit minimization, this repository treats Boolean function spaces as mathematical objects with structural properties — analogous to how the Structure Recognition Research Program studies structure spaces in Karnaugh maps.
This work extends the existing research ecosystem by:
- Providing a finite, enumerable mathematical domain (2^16 = 65,536 four-variable Boolean functions)
- Exploring representation transformations among truth tables, Karnaugh maps, gate networks, and algebraic normal forms
- Serving as a testbed for Human-AI collaborative mathematical exploration
- Applying Structure Recognition Theory (SRT) to function-space classification problems
Demonstrate that NAND alone can generate all 65,536 four-variable Boolean functions.
Demonstrate the same for NOR.
(This is an application of Post's Functional Completeness Theorem, with educational value through Karnaugh map visualization.)
For each primitive gate, determine:
- The size of the generated function space
- The characterization of the generated class
- The visual patterns these functions form on Karnaugh maps
Key known results:
| Gate | Generated Space |
|---|---|
| XOR | Affine (linear) functions |
| AND | Subset of monotone functions |
| NAND | Entire Boolean space (65,536) |
| NOR | Entire Boolean space (65,536) |
The unexplored question: What do these function classes look like on Karnaugh maps?
Given a target function (e.g., 3-input AND), determine which single gate types can generate it and which cannot.
Generalize this into a constructibility framework — equivalent to asking: is f contained in the clone generated by G?
For any primitive gate G, define:
- Generated function space Space(G)
- Closure properties
- Visual characteristics on Karnaugh maps
- Structural invariants
Q1–Q3 are all special cases of Q4.
6BooleanFunctionSpaceTheory/
├── README.md ← This file
├── paper.md (+ 01_paper.pdf) ← Paper: Function Space Theory (integrates the former FunctionSpaceTheory, PostLattice, KarnaughGeometry, IntegrationMap, exploration, questions)
├── TODO.md ← Master roadmap (Phase 1–5), future research (FutureWorks), archived details of removed files
├── SubTODO.md ← Current sprint micro-tasks
├── index.html ← GitHub Pages portal
├── theory/
│ └── S4GroupAnalysis.md ← ★ S₄ orbit classification (OC-1~OC-5)
└── scripts/
└── s4_orbit_calculator.py ← ★ S₄ orbit enumeration & Burnside verification
Earlier planned documents (
FutureWorks.md,IntegrationMap.md,theory/FunctionSpaceTheory.md,theory/PostLattice.md,theory/KarnaughGeometry.md,exploration/,questions/,fq/) were merged intopaper.mdandTODO.mdand removed as separate files.
scripts/s4_orbit_calculator.py computes S₄ group orbits over four-variable Boolean function spaces using full enumeration cross-validated against Burnside's Lemma.
Python 3.8 or later. No external packages required — standard library only.
python --version # must be 3.8+# Full analysis: all four spaces + n=5 scaffold
python scripts/s4_orbit_calculator.py
# Quick verification only (no detailed output)
python scripts/s4_orbit_calculator.py --verify
# Single space analysis
python scripts/s4_orbit_calculator.py --space XOR
python scripts/s4_orbit_calculator.py --space AND
python scripts/s4_orbit_calculator.py --space NOT
python scripts/s4_orbit_calculator.py --space LM
# n=5 theoretical scaffold
python scripts/s4_orbit_calculator.py --n5 Space(XOR) : 10궤도 (기대 10) ✅
Space(AND) : 30궤도 (기대 30) ✅
Space(NOT) : 32궤도 (기대 32) ✅
L∩M : 3궤도 (기대 3) ✅
전체: ✅ 모두 통과
| Space | Description | Functions | S₄ Orbits | Fixed Points |
|---|---|---|---|---|
| Space(XOR) | Affine (linear) functions | 32 | 10 | 4 |
| Space(AND, OR, 0, 1) | Monotone functions (Dedekind D(4)) | 168 | 30 | 6 |
| Space(MAJ, NOT) (no constants) | Self-dual functions | 256 | 32 | 0 |
| L ∩ M | Affine ∧ Monotone | 6 | 3 | 2 |
Theoretical basis: theory/S4GroupAnalysis.md v1.2 (OC-1–OC-5).
- 궤도 (열거) — orbit count from direct BFS enumeration over the function space
- 궤도 (Burnside) — orbit count from Burnside's Lemma applied to conjugacy class representatives
- S₄-불동점 (◆) — functions fixed by every permutation in S₄; these are maximally symmetric and correspond to the functions first noticed in Repos 1–3 (checkerboard, threshold functions)
- 궤도 크기 — orbit size equals |S₄| / |stabilizer|; size-1 orbits are exactly the fixed points
This repository is part of the Structure Recognition Research Program and is designed to integrate with — not stand apart from — Papers 1–5.
| Repository | Relationship |
|---|---|
| 1KMapStructureInvariance | Shared visual domain: Karnaugh maps as the primary representation tool |
| 2SymmetricBooleanFunctionMinorThesis | Representation transformation: same function, multiple representations |
| 3VariableRearrangementInvarianceMinorThesis | Structural invariance: which properties are preserved across transformations? |
| 4StructureRecognitionTheory | Direct application: SRT applied to function-space classification |
| 5HumanAIResearchCollaboration | Collaboration testbed: finite Boolean spaces as benchmark for Human-AI exploration |
Long-term goal: Develop a theory of Boolean Function Spaces analogous to how Structure Recognition Theory studies structure spaces. The focus is not gates themselves — it is the relationship between representation, generation, transformation, recognition, and function-space structure.
| Repository | Role |
|---|---|
| Research-Portfolio | Program Hub |
| 1KMapStructureInvariance | Empirical Case Study 1 |
| 2SymmetricBooleanFunctionMinorThesis | Empirical Case Study 2 |
| 3VariableRearrangementInvarianceMinorThesis | Empirical Case Study 3 |
| 4StructureRecognitionTheory | Theoretical Hub |
| 5HumanAIResearchCollaboration | Methodological Meta-layer |
| 6BooleanFunctionSpaceTheory | Applied Mathematics ← You are here |
| ANTIGRAVITY | AI Workspace |
AI 단일 진입점: SESSION_START.md
The 65,536 four-variable Boolean functions are not all independent. Under axis-swap symmetry (F(A,B,C,D) = F(C,D,A,B)), functions form equivalence classes (orbits under the symmetry group). Result: When the 65,536 functions are classified by the axis swap alone, 33,280 classes result (1,024 functions satisfy F(A,B,C,D) = F(C,D,A,B) themselves); this is a one-step Burnside count, (65,536 + 1,024)/2, and classification by the full S₄ gives 3,984 classes.
Choi Jonghun (최종훈)
Independent researcher · 2nd-year student at Inha Technical College
Structure Recognition Research Program