1
$\begingroup$

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).

$\endgroup$
  • 1
    $\begingroup$ 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$ $\endgroup$ – Dmitri Chubarov Sep 10 '13 at 8:51
3
$\begingroup$

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.

Why are we taught AND, OR and NOT? Because these are familiar and useful. It is also common to define propositional logic using the connectives IMPLIES and NOT. It's just a matter of convenience. It is also a matter of convenience that all usual connectives are nullary, unary and binary - already ternary connectives are more awkward to write, functional notation being necessary.

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.

One relevant mathematical area is universal algebra. For an application to computer science, you can have a look at Schaefer's theorem and its modern descendants, which form a very active research area. Another connection to computer science is Reckhow's theorem that shows that every formula written using one complete set of connectives can be rewritten using any other set of connectives with only polynomial blowup, and furthermore proofs in any complete propositional proof system can be converted to any other (with a different set of connectives), again with only polynomial blowup.

$\endgroup$
  • $\begingroup$ thanks. intuitively it seems to me that the "simplest" complete set is the one with the minimum number of total inputs. so that would be nor/nand and a constant? so what is "special" about nor or nand, that and/or don't have? it seems like they are somehow "more complex". is there a formal way to state that? something related to the order relation you mention, i guess. $\endgroup$ – andrew cooke Sep 9 '13 at 6:01
  • $\begingroup$ There is no formal definition of "simplest", so you could choose your own criterion and then find the "simplest" sets of connectives according to that criterion. Also, there is nothing "special" about NAND or NOR, other than the property you mention. These properties are not as deep as you make them to be. $\endgroup$ – Yuval Filmus Sep 9 '13 at 14:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.