1
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.