# Thread: Not functionally complete set of connectives

1. ## Not functionally complete set of connectives

Hello,
the task is to show that the following set of connectives isn't (functionally) complete: $\{ \vee, \wedge, \rightarrow, \leftrightarrow, \top \}$

I know that the negation connective can't be expressed with those, but the problem is how to prove that. I tried to roll some truth tables, but that didn't help. I think some kind of inductive proof is needed.

Any help is appreciated, thank you very much!

2. From Wikipedia: "Emil Post proved that a set of logical connectives is functionally complete if and only if it is not a subset of any of the following sets of connectives: ..." I don't remember if I studied the proof, but I would guess that the hard part is to prove the "if" part, i.e., not being a subset implies completeness. Your set of connectives is one of the five listed in the theorem, and once you know the name of this set, it is easy to see that it is not complete.

3. Thanks for help. I browsed Wikipedia, but somehow managed to skip part of that article. I think the following (from Wikipedia) definition is enough for my purposes:
"The truth-preserving connectives; they return the truth value T under any interpretation which assigns T to all variables"

There seems to be some kind of modernized version of Post's proof about functional completeness:
http://www.sfu.ca/~jeffpell/papers/PostPellMartin.pdf

Maybe I study that, if I have enough time.