1
$\begingroup$

For any formula, there exists an equivalent formula that contains no connectives other than ⊃ and ⊥. In this sense, {⊃, ⊥} is an “adequate” set of connectives.

I want to prove that {∧, ¬} is adequate.

My solution is, A and B is an atom. Recall that any general form (AVB) is truth-functionality equivalent to ¬(¬A∧¬B)

I prove this with truth table.

A|B|AVB|¬(¬A∧¬B)

t t| t | t

t f| t | t

f t| t | t

f f| f | f

yes it is adequate, but i want to prove it more general ex, any formula can prove this.

How can i prove it for general?

$\endgroup$
3
$\begingroup$

If you already know that $\{ ⊃, ⊥ \}$ is adequate, the simplest way to prove that also $\{ ∧, ¬ \}$ is so is to show how to define :

$p ⊃ q$ and $⊥$

in terms of $\{ ∧, ¬ \}$.

$\endgroup$
  • $\begingroup$ So can i say that, ¬p ~ p ⊃ ⊥ if F~G then for every interpretation of F must be equal to the truth table of G. In the truth table i will prove they are true, then i will show that p ∧q ~(p ⊃(q ⊃ ⊥)) ⊃ ⊥ i prove it in the truth table then, can i say that {∧,¬} is adequate? $\endgroup$ – M.J.Watson Nov 16 '16 at 10:11
  • $\begingroup$ @M.J.Watson - more or less; proving (with truth-table) that $p \to q$ is equiv to $\lnot (p \land \lnot q)$ you can conclude that you can dispense with $\to$ . The next step is to find an equivalent for $\bot$. $\endgroup$ – Mauro ALLEGRANZA Nov 16 '16 at 10:29

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.