I'm trying to re-learn first-order logic and so I've tried to prove the following statement

$$ (p \rightarrow q) \rightarrow q \Leftrightarrow p \vee q $$

I tried to begin like this using the implication equivalence twice:

\begin{array} ((p \rightarrow q) \rightarrow q &\Leftrightarrow (\neg p \vee q) \rightarrow q\\ &\Leftrightarrow \neg (\neg p \vee q) \vee q\\ &\Leftrightarrow (p \wedge \neg q) \vee q \end{array}

Then I used the distributive property:

\begin{array} &\Leftrightarrow p \vee q \wedge \neg q \vee q \end{array}

And because $(\neg q \vee q)$ is a tautology, we can omit it in the formula:

\begin{array} &\Leftrightarrow p \vee q \end{array}

Is my reasoning correct? My logic skills have become really rusty as I've not seen in several years and I'm not really sure about it.

  • 1
    $\begingroup$ I think it's correct $\endgroup$ – Motaka Jun 12 '17 at 12:00
  • 1
    $\begingroup$ correct answer... $\endgroup$ – Muse_China Jun 12 '17 at 12:02
  • $\begingroup$ @Muse_China Thank you too! $\endgroup$ – Eenoku Jun 12 '17 at 12:12
  • $\begingroup$ @Stefan Thank you, it's corrected now. $\endgroup$ – Eenoku Jun 12 '17 at 12:12

Considering the comments of Mokata, Muse_China and Stefan, the proof is correct.

| cite | improve this answer | |
  • $\begingroup$ you can accept your own answer to close this case... $\endgroup$ – draks ... Jun 12 '17 at 12:43
  • $\begingroup$ @draks... Unfortunately, only after two days $\endgroup$ – Eenoku Jun 12 '17 at 12:58

An an additional 'brushing up your skills' exercise, you can also solve this using logical equivalences involving conditional statements \ Rules (1) thru (8).

The following are logical rewrites:

$(p \rightarrow q) \rightarrow q \Leftrightarrow p \vee q$
$(p \rightarrow q) \rightarrow q {\;\Leftrightarrow}^3\;\; \neg q \rightarrow p$
$\neg q \rightarrow \neg (p \rightarrow q) {\;\Leftrightarrow}^2\;\; \neg q \rightarrow p$
$\neg q \rightarrow (p \wedge \neg q) {\;\Leftrightarrow}^5\;\; \neg q \rightarrow p$
$(\neg q \rightarrow p) \wedge (\neg q \rightarrow \neg q) {\;\Leftrightarrow}^6\;\; \neg q \rightarrow p$

But $(\neg q \rightarrow \neg q)\;$ is $(q \vee \neg q)$ is TRUE, and so by the Identity Law we are left with

$\neg q \rightarrow p {\;\Leftrightarrow}\, \neg q \rightarrow p$

| cite | improve this answer | |

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.