Functional Completeness - Proving {⇒,∧,∨} is functionally complete.

Question

I am not sure how to do this question. I have looked at some of the other similar questions but to no avail.

I know that for a set of operators to be functionally complete I need to just prove ¬ in this case as we have ∧,∨ already.

Answer 1

That's impossible. Look at what happens when you put any expression using $\land$, $\lor$, and $\rightarrow$ on a truth table: when the atomic statements involved are all true, then this will evaluate to true, no matter what the expression is. So, some functions cannot be captured with these three operators.

In fact, just try to capture $\neg P$ with any number of $P$'s, and $\land$, $\lor$ and $\rightarrow$'s. Since $T\land T=T$, $T\lor T= T$, and $T \rightarrow T= T$, the row where P is T will have ro evaluate to T. So you can't do it.

Unless, of course, you are given the $\bot$ as another primitive. Then $\neg P = P \rightarrow \bot. $ But typically, we will then say that $\{\land, \lor, \rightarrow, \bot \}$ is complete.