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

1 Answer 1

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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .