= Solution
There are sixteen binary <Boolean functions>, one for each four-bit <truth table>. \b[Exactly eight give an adequate basis together with <negation>.]
The eight affine functions are $0,1,p,\neg p,q,\neg q,p\oplus q,\neg(p\oplus q)$. Each is affine over the field with two elements, and composition with other affine functions or <negation> remains affine. Since <conjunction> is not affine, none of these eight bases is adequate.
Each remaining <truth table> has either one true row or three true rows. In the latter case negate its output to obtain a function with one true row. Negate selected inputs to move that row to $(1,1)$: the resulting function is <conjunction>. <Conjunction> together with <negation> expresses every <disjunctive normal form>, proving adequacy of all remaining eight. They are AND, NAND, OR, NOR, the two directed implications, and the two asymmetric conjunctions $p\land\neg q$, $\neg p\land q$. The count treats the binary connective by its truth function rather than by arbitrary choices of its printed symbol.
Back to article page
