# Fundamental Boolean Functions

I can define any boolean function (I think) using and and not, or using or and not (plus a constant 0 or 1). And I can define or in terms of xor. And then there are nor and nand. So I am wondering:

1. Why are we traditionally taught boolean logic using and, or and not?

2. Is there a "simplest" set of boolean functions that can be used to define all the rest? Or are there "families" of functions that are equivalent in some way?

3. Do we always need 0, 1 and 2-argument functions (eg 0 or 1 constants, not, and and) to define a family? Or are there any boolean functions with more than 2 arguments that are fundamental (can appear in an answer to 2)? Or well-known? Or common? If not, what's so special about 0, 1 and 2 arguments?

4. Is there some underlying mathematical theory (perhaps based on symmetry?) that makes these kinds of questions easier to answer? For example, how do you rigorously derive all answers to questions 2 or 3?

(I know that a partial answer to 2 (equivalent families) is "yes" because I remember De Morgan's theorem from college, but that's about as far as I can get).

• A set of logical connectives that defines any boolean function is called adequate. There is a nice introduction in the Wikipedia article on Functional completeness. There is a list of minimal functionally complete operator sets of cardinality $\leq 3$ Sep 10 '13 at 8:51

Your main observation is correct - in order to be able to express all Boolean functions, we need not stick to a certain set of connectives. All we need is a complete set of connectives, which is defined by just this property. There are infinitely many such sets of connectives. One such example is given by NOR (or NAND) and the constant $0$ (or $1$). You can probably do with just one ternary connective, but I'll let you figure that out.
In general, given a set of connectives, you can define the set of all Boolean functions definable from them. Then you can define the concept of equivalent sets of connectives. For example, XOR and NOT is equivalent to XNOR, and $0$ and NOT is equivalent to $1$ and NOT. You can easily prove that two sets $A,B$ of connectives are equivalent if each connective in $A$ can be expressed using connectives in $B$ and vice versa. You can even define an order relation expressing that one set of connectives is at least as expressive as another set of connectives.