1

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$.

William Elliot
  • 17,598
cnmesr
  • 4,720
  • 7
  • 44
  • 83

1 Answers1

4

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.

Casper
  • 1,024