# Is the set $\tau := \left\{\vee, \wedge, 0\right\}$ adequate? Prove your answer

Is the set $\tau := \left\{\vee, \wedge, 0\right\}$ adequate? Prove your answer.

A set of connectives is adequate if all other connectives can be expressed in terms of it.

By just looking at this set, you cannot express all the other connectives with it ($1, \neg, \rightarrow)$.

There is no way to get $1$ by only using $\left\{\vee, \wedge, 0\right\}$. The other connectives aren't possible either...

But how can you prove this? Maybe by using a truth table?

    A  |  ¬A  |  0  |  A∧0
--------------------------
0  |   1  |  0  |   0
0  |   1  |  0  |   0
1  |   0  |  0  |   0
1  |   0  |  0  |   0


So the set is not adequate because there is no way to express $\neg\psi$ (where $\psi$ is some propositional formula) by just using $\wedge, \vee, 0$.

• What is 0? Contradiction? Commented Nov 13, 2017 at 20:33
• What does it have to do with general topology (or discrete math or set theory)? Commented Nov 13, 2017 at 20:39
• @ab123 Boolean constants, where $0$ stands for FALSE and $1$ for TRUE Commented Nov 13, 2017 at 20:45
• Give a look here: en.wikipedia.org/wiki/Functional_completeness#Formal_definition Commented Nov 13, 2017 at 23:50

You can prove by induction on the complexity of the formulae constructible with $0$, conjunction, and disjunction that when the value of all propositional variables are $0$, the value of the formula is also $0$. That is not the case for the formula $\neg P$, so this shows that negation cannot be expressed.