Prove a set of connectives is functionally complete

Question

What is the right way of proving that a set of logical connectives is or not functionally complete? For example, if I have

{→,∨}

how can I show it is or not functionally complete? Any ideas?

Answer 1

To prove that a set of connectives is functionally complete, you simply need to show that you can derive any other logical connective using only this restricted set.

In your case, you want to show that you can obtain definitions for $\left\{\land,\leftrightarrow,\neg\right\}$ from $\left\{\to,\lor\right\}$, i.e. the question you have to ask yourselves is:

What combination of $\left\{\to,\lor\right\}$ and sentence symbols $A$ and $B$ is equivalent to...

• $A\land B$ ?
• $A\leftrightarrow B$ ?
• $\neg A$ ?

And by definition, if you cannot show that the set $\left\{\to,\lor\right\}$ is functionally complete, then it is not.

Playing around with these questions should give you a good idea of how connectives are related to each other and what functional completeness really means.

For a more formal approach, consider the following characterization of functional completeness. A set of connectives is functionally complete if it is not:

• monotonic : changing the truth value of any connected variable from false to true never makes the return value change from true to false;
• self-dual : reversing the truth value of the connected variables revers the truth value of the return value;
• affine : each connected variable either always or never affects the truth value of the return value;
• truth-preserving : when all variables are true, the return value is also true;
• falsity-preserving: when all variables are false, the return value is also false.

Thus, if you can show that $\left\{\to,\lor\right\}$ has any of the above properties, then it is not functionally complete.