Lesson 1

We call \(\Omega \subseteq B^{*}\) a complete basis if any Boolean function \(f(x_{1}, \dotsc, x_{n})\) can be defined using the variables \(x_{1}, \dotsc, x_{n}\) and functions from \(\Omega\) (which we will call connectives). For example, \[\{\operatorname{AND}_{2}, \operatorname{OR}_{2}, \operatorname{NOT}_{1}\}=\{\land, \lor, \neg\}\] is a complete basis (the subscript under each function indicates its arity, i.e., the number of input bits): after all, any function can be represented in CNF/DNF form. In particular, it follows that \[\{\operatorname{AND}_{2}, \operatorname{NOT}_{1}\}=\{\land, \neg\}\] is also complete, because \(\operatorname{OR}_{2}\) can be expressed using the remaining two functions: \[\operatorname{OR}_{2}(x,y) = x \lor y = \neg((\neg x) \land (\neg y))= \operatorname{NOT}_{1}(\operatorname{AND}_{2}(\operatorname{NOT}_{1}(x), \operatorname{NOT}_{1}(y))) \ .\]

The question of which bases are complete is not only of theoretical interest: as we will see below, any Boolean function can be computed using a logic circuit made exclusively of \(\operatorname{NOR}\) gates!

The Apollo program culminated in the first human landing on the Moon in 1969. Its onboard computer, the Apollo Guidance Computer (AGC), was one of the first machines constructed using silicon integrated circuits rather than discrete transistors. In fact, its digital logic was implemented almost entirely from a single primitive: 3-input \(\operatorname{NOR}\) gates! Despite its simplicity, the AGC was a real-time control computer operating at approximately 2 MHz, with only a few kilobytes of RAM. Its overall computational performance was comparable to that of early personal computers of the late 1970s, such as the Apple II. Thus, they proved that \(\operatorname{NOR}\) gates are enough, to navigate safely to the Moon and back!