Universal logical functions

The fact that combinations of Nand or Nor are adequate to reproduce any logical function was noted by Charles Peirce around 1880, and became widely known after the work of Henry Sheffer in 1913. (See also page 1096.) Nand and Nor are the only 2-input functions universal in this sense. ({Equal} can for example reproduce only functions {9, 10, 12, 15}, {Implies} only functions {10, 11, 12, 13, 14, 15}, and {Equal, Implies} only functions {8, 9, 10, 11, 12, 13, 14, 15}.) For 3-input functions, corresponding to elementary cellular automaton rules, 56 of the 256 possibilities turn out to be universal. Of these, 6 are straightforward generalizations of Nand and Nor. Other universal functions include rules 1, 45 and 202 (If[a  1, b, c]), but not 30, 60 or 110. For large n roughly 1/4 of all n-input functions are universal. (See also page 1175.)