Lesson 4

Usually, circuits are constructed over the full binary basis \(B_{2}\), consisting of all binary Boolean operations. However, one particularly useful gate corresponds to the “not-and” operation (also known as NAND): \[p \uparrow q \equiv \neg (p \land q).\] At first glance, this operator may appear somewhat peculiar. Nevertheless, it possesses a remarkable property for the construction of logic circuits: every conventional Boolean operator can be expressed solely in terms of it. For example, \[\begin{align*}\neg p&\equiv p \uparrow p, \\ p \land q&\equiv \neg (p \uparrow q) \equiv (p \uparrow q) \uparrow (p \uparrow q), \\ p \lor q&\equiv (p \uparrow p) \uparrow (q \uparrow q).\end{align*}\]

From the perspective of mass production, NAND gates are therefore ideal: if they can be manufactured cheaply, no other type of gate is required! Regardless of the intended computation, it suffices to determine an appropriate interconnection of such gates.