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?
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this communityTo 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:
Thus, if you can show that $\left\{\to,\lor\right\}$ has any of the above properties, then it is not functionally complete.