What does it mean for a set of connectives to be adequate for truth functional logic? How would you show that if $\{\neg , \vee , \land , \rightarrow , \leftrightarrow \}$ is adequate then so is $\{\neg , \vee \}$? Same for if $\{\neg ,\land\}$ is adequate then so is $\{ \downarrow \}$?

• Is there a set process or method that shows that the subset is adequate? – Andy Dec 21 '16 at 9:00

A set of truth functional connectives is said to be adequate if every boolean function can be implemented as a expression using only those connectives.

The standard procedure to show that a set of connectives is adequate is to use them to simulate all the connectives in a known adequate set.

For example, we can simulate the OR expression $A\vee B$ in terms of $\{\neg, \wedge\}$ as $\neg (\neg A \wedge \neg B)$ (check the truth functional tables if you do not believe this assertion).

Can you do the rest of the exercise on your own?

• Thank you very much for your kind help. – Andy Dec 21 '16 at 9:12

A Boolean function $f$

-is truth-preserving if: $f(1,1,...,1) = 1$

-is false-preserving if $f(0,0,...,0) = 0$

-is self-dual if $f(X_1 , X_2 , ... , X_n) = \neg f(\neg X_1 , \neg X_2 , ... , \neg X_n)$ for every row of its truth table (in other words, this given condition holds for everyassignment given to the variables).

-is linear if it is such that changing the truth-value of any single non-dummy variable, always changes the output of the function.

-is monotone if after switching the truth-value of any single argument from false to true, the function does not switch from having originally outputted true, to now outputting false.

Post's Completeness Theorem says that a set of Boolean functions is functionally complete (also called adequate) iff the set contains at least one function which:

1. is not truth-preserving
2. is not false-preserving
3. is not self-dual
4. is not linear
5. is not monotone

If it has been proven that a set of Boolean functions is functionally complete, then to prove a different set is itself functionally complete, one needs only to show that the elements of this different set can produce any function which the elements of the original set can produce.

The following are some good resources to take a look at:

http://www.sfu.ca/~jeffpell/papers/PostPellMartin.pdf

http://cs.ucsb.edu/~victor/ta/cs40/posts-criterion.pdf