Logic gates, also known as logical connectives, are Boolean functions that accept a fixed number of inputs, referred to as their arity, and produce a single Boolean output. In computer architecture, these connectives form the foundation of digital computation, allowing complex circuits and computational systems to be constructed from simple logical operations.
A connective is considered functionally complete when every possible Boolean function can be expressed solely through repeated compositions of that connective. This project investigates functional completeness through both theoretical and computational methods. Post’s Functional Completeness Theorem is used to characterize the properties that determine whether a Boolean connective is functionally complete, while formulas for enumerating Sheffer functions are used to examine how the number of functionally complete connectives changes with arity.
Using these results, the project computationally identifies functionally complete connectives and derives explicit expressions for other Boolean functions through repeated self-composition. The resulting framework is then extended to cellular automata, where Boolean connectives serve as local update rules. This extension explores how functional completeness and gate composition can be interpreted within rule-based dynamical systems and how complex cellular behavior may emerge from a single logical operation.