3
$\begingroup$

In my book about Logic, which is called 'Language, Proof and Logic', by the way, there is explained that the conditional $ P \rightarrow Q $ is equivalent with $\neg P \lor Q$.

There is another answer on math.stackexchange that gives as answer: 'just compare the truth tables and you can see that they are equivalent'. However, I would like to know how to prove this using formal propositional logic. This should be possible, right?

$\endgroup$
  • 4
    $\begingroup$ How do you define $P \to Q$? $\endgroup$ – Adriano Sep 17 '14 at 22:12
  • 2
    $\begingroup$ Which kind of formal proof system for propositional logic do you want to prove the equivalence in? There are several quite different ones. $\endgroup$ – Henning Makholm Sep 17 '14 at 22:35
  • $\begingroup$ This is often given as the definition, although I prefer $P\implies Q\equiv \neg[P \land \neg Q]$. $\endgroup$ – Dan Christensen Sep 18 '14 at 17:27
  • $\begingroup$ Possible duplicate of Equivalence of $a \rightarrow b$ and $\lnot a \vee b$ $\endgroup$ – Greek - Area 51 Proposal Nov 13 '16 at 12:22
6
$\begingroup$

Layout:

To prove that $\neg P\lor Q$ is a formal consequence of $P\to Q$, start by assuming $P\to Q$ and further suppose that $\neg (\neg P\lor Q)$ holds. At this point you should prove $P\lor \neg P$ and perform $\lor$-$\text{Elim}$ on this disjunction. It's easy to find contradictions on both cases yielding $\neg \neg (\neg P\lor Q)$.

For the other direction, naturally start by assuming that $\neg P\lor Q$ holds and then assume $P$. Now start yet another subproof (within the assumption that $P$ holds) assuming that $\neg Q$ holds. At this point perform $\lor$-$\text{Elim}$ on the assumption $\neg P\lor Q$. It's easy to find a contradiction in this last subproof.

$\endgroup$
2
$\begingroup$
  1. $P → Q$ (given)
  2. $Q \lor \neg Q$ (tautology)
  3. $\neg Q → \neg P$ (modus tollens)
  4. from (2) and (3): $Q \lor \neg P$
$\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.