Prove that the set {→, ¬} is functionally complete

16.7k Views Asked by At

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

2

There are 2 best solutions below

8
On 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.

0
On

No, $\to$ alone is not complete because you cannot get to negation, for example.