Research Repository · Boolean Function Space Theory
Gate-Generated Function Spaces, Structural Classification of the 65,536 Four-Variable Boolean Functions, and Karnaugh Map Geometry of Function Classes
Overview
This repository investigates the mathematical structure of function spaces generated by single primitive Boolean gates, and explores how these spaces can be recognized, classified, and visualized through Karnaugh maps.
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.
The four-variable Boolean function space contains exactly 216 = 65,536 distinct functions. The central question is: what is the geometry of this space when viewed through the lens of gate-generated function classes?
Q1 — Universal Gate Demonstration
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. The research value is in the Karnaugh map visualization of the generation process.
Q2 — Gate-Generated Function Space Characterization ★ Primary Research Target
For each primitive gate, determine:
| Gate | Generated Space | Known Class |
|---|---|---|
| XOR | Affine (linear) functions | Well-characterized |
| AND | Subset of monotone functions | Partially known |
| NAND | Entire Boolean space (65,536) | Post's theorem |
| NOR | Entire Boolean space (65,536) | Post's theorem |
The unexplored question: what do these function classes look like on Karnaugh maps? This is where this research makes its contribution.
Q3 — Constructibility Framework
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?
| Target: 3-input AND | Constructible? |
|---|---|
| NAND-generated space | Yes |
| NOR-generated space | Yes |
| AND-generated space | Yes |
| XOR-generated space | No (AND is not affine) |
Q4 — Function Space Structure ★ Foundational Question
For any primitive gate G, define and characterize Space(G):
Q1–Q3 are all special cases of Q4. This is the foundational question of the repository.
Emil Post's theorem (1941) characterizes exactly which sets of Boolean functions are functionally complete — capable of generating all Boolean functions through composition. A gate G generates all Boolean functions if and only if its one-element set {G} is not contained in any of Post's five maximal clones:
| Maximal Clone | Description | NAND ∈? | XOR ∈? |
|---|---|---|---|
| T₀ (truth-preserving) | f(0,...,0) = 0 | No | Yes |
| T₁ (falsity-preserving) | f(1,...,1) = 1 | No | Yes |
| M (monotone) | x ≤ y ⟹ f(x) ≤ f(y) | No | No |
| S (self-dual) | f(¬x) = ¬f(x) | No | Yes |
| L (affine/linear) | f = a₀ ⊕ a₁x₁ ⊕ ... ⊕ aₙxₙ | No | Yes |
NAND is not in any of these five maximal clones → NAND generates all functions. XOR is in T₀, T₁, S, and L → XOR generates only the affine (linear) functions.
The set of all clones (sets of functions closed under composition and containing all projections) forms a lattice under set inclusion. The five maximal clones described above are the top elements below the full clone. Understanding where Space(G) sits in this lattice is a core research direction.
A core hypothesis of this research: functions belonging to the same gate-generated space share recognizable geometric patterns on Karnaugh maps. This connects the algebraic structure of clones to the visual, spatial intuition developed in Papers 1–3.
| Function Class | Karnaugh Map Characteristic | Connection to Previous Papers |
|---|---|---|
| Affine (XOR-generated) | Checkerboard pattern in Gray Code arrangement; double-diagonal in standard binary arrangement | Paper 1 (Repo 1): checkerboard invariance; Paper 2 (Repo 2): layer-based analysis |
| Monotone functions | No "isolated 0 islands" surrounded by 1s; patterns monotone in coordinate ordering | Open question: visual characterization unexplored |
| Self-dual functions | Complement of pattern equals pattern under bitwise negation of inputs | Open question: Karnaugh map geometry not systematically studied |
| NAND-generated (all functions) | All 65,536 patterns — no restriction | Paper 2 (Repo 2): classification of all 65,536 functions by symmetry |
The unexplored territory: for each non-trivial gate G, what is the visual invariant shared by all functions in Space(G)? If such invariants exist, they would create a new classification system for the 65,536 four-variable Boolean functions — based not on syntactic form but on generative origin.
Key Insight from Research Notes
The four-variable Boolean function space contains exactly 216 = 65,536 distinct functions. In general, an n-variable Boolean function space contains 2(2n) functions.
However, these 65,536 functions are not all "structurally independent." Under axis-swap symmetry (F(A,B,C,D) = F(C,D,A,B)), functions form equivalence classes (orbits under the symmetry group).
Research question: When the 65,536 four-variable Boolean functions are classified by axis-swap symmetry, how many distinct equivalence classes result? This is a problem in combinatorics and group theory, and represents a natural extension of Papers 1–3.
| n (variables) | Total functions |
|---|---|
| 1 | 22 = 4 |
| 2 | 24 = 16 |
| 3 | 28 = 256 |
| 4 | 216 = 65,536 |
| 5 | 232 = 4,294,967,296 |
The classification problem — "how many distinct classes under symmetry G?" — is where the study of function spaces (this repository) intersects with the study of structural invariance (Papers 1–3).
| Repository | Relationship to This Work |
|---|---|
| Paper 1 · KMap Structure Invariance | Shared visual domain: Karnaugh maps as the primary representation. The checkerboard pattern studied in Paper 1 is the Karnaugh map signature of the XOR-generated function space (affine functions). |
| Paper 2 · Symmetric Boolean Functions | Representation transformation: same function viewed through truth table, Hamming weight layer structure, and Karnaugh map geometry. The layer-based analysis in Paper 2 is a classification of a function's inputs; this repository classifies the function's generative origin. |
| Paper 3 · Variable Rearrangement Invariance | Structural invariance: Paper 3 asks "does the pattern survive variable rearrangement?" This repository asks "does the pattern survive gate substitution?" The symmetry classification of 65,536 functions initiated in Paper 3 directly extends into this repository. |
| Paper 4 · Structure Recognition Theory | Direct application of SRT: the hypothesis that "functions in the same generated space share recognizable structural properties" is an application of SRT H2 (structural invariance) and H4 (research-worthiness recognition) to the Boolean function space domain. |
| Paper 5 · Human-AI Research Collaboration | Collaboration testbed: the finite, well-defined structure of Boolean function spaces (65,536 functions, exact lattice structure) makes this domain ideal for studying Human-AI collaborative mathematical exploration. AI can systematically enumerate; humans recognize patterns and ask new questions. |
The following 20 questions were generated as natural extensions of the core research questions Q1–Q4.
Detailed answers are being developed in FOLLOW_UP_ANSWERS.md.
Potential Future Repositories
Analysis of FQ-1 to FQ-20 identifies three clusters that may warrant independent repositories:
| Repository | Role |
|---|---|
| Research-Portfolio | Program Hub — navigation, concept genealogy, timeline |
| 1KMapStructureInvariance | Empirical Case Study 1 — Karnaugh Map Structure Invariance |
| 2SymmetricBooleanFunctionMinorThesis | Empirical Case Study 2 — Symmetric Boolean Functions |
| 3VariableRearrangementInvarianceMinorThesis | Empirical Case Study 3 — Variable Rearrangement Invariance |
| 4StructureRecognitionTheory | Theoretical Hub — Structure Recognition Theory (SRT) |
| 5HumanAIResearchCollaboration | Methodological Meta-layer — Human-AI Research Collaboration |
| 6BooleanFunctionSpaceTheory | ← You are here — Applied Mathematics, Boolean Function Spaces |
| ANTIGRAVITY | AI Workspace — handover documents, session logs |