Logic – Prove that the Set {?, ¬} is Functionally Complete

boolean-algebralogic

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, the set can be used to express all possible truth tables by combining members of the set into a Boolean expression

Best Answer

The implication $\to$ is defined by $$ a\to b \equiv \neg a \vee b. $$

This means, that $$ \neg a \to b \equiv a \vee b$$ and thus, you can express logical or using $\to$ and $\neg$. Furthermore you know de Morgans rules and you have $$ \neg(\neg a \vee \neg b) \equiv \neg\neg a\wedge \neg\neg b = a\wedge b.$$

Thus you can express all logical operators using $\to$ and $\neg$. The set of these is known to be functionally complete.