[Solved]: Fundamental Boolean Functions

Problem Detail: 

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

Asked By : andrew cooke

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/14226

3.2K people like this

 Download Related Notes/Documents