2
$\begingroup$

Hi I am looking to prove

$r\wedge q\Leftrightarrow r \vdash r\Rightarrow q$

using natural deduction

I get:

  • $r\wedge q\Leftrightarrow r$, assumption
  • $r\vdash q$
  • $r$, assumption

I assume that I also need to formally prove $q$ but cant figure out how to do it(and what rule would I use?) Am I correct so far? thank you.

$\endgroup$
  • $\begingroup$ Is there any typo in $r\wedge q\Leftrightarrow p$? Maybe you meant $r$ instead of $p$? And also, is it $r\wedge (q\Leftrightarrow p)$ or $(r\wedge q)\Leftrightarrow p$? $\endgroup$ – frabala Feb 26 '14 at 17:20
  • $\begingroup$ yes sorry i have fixed it $\endgroup$ – user131673 Feb 26 '14 at 17:23
  • $\begingroup$ Are you attending same class or have you crated duplicate user to post duplicate post? math.stackexchange.com/questions/691161/formal-proof-logic $\endgroup$ – Trismegistos Feb 27 '14 at 8:36
4
$\begingroup$

(1) Assume $r$.

Then from the premise $(r\land q) \longleftrightarrow r$, which means $((r\land q)\rightarrow r)\land (r\rightarrow (r\land q))$, we have

(2) $r\rightarrow (r\land q)$,

Since $r$ is assumed, we have, by modus ponens using $(1), (2)$, we have

(3) $r\land q$.

This gives us, from (3),

(4) $q$.

From the assumption of $r$, we've deduced $q$.

Therefore, $r\rightarrow q$.

$\endgroup$
  • $\begingroup$ sorry I am still confused how you get to r→(r∧q). is this derived by implication introduction? To do this do you not have to prove (r∧q) on its own? $\endgroup$ – user131673 Feb 26 '14 at 17:32
  • $\begingroup$ @user131673 It's $\to \text{elimination}$ that is used. $\endgroup$ – Git Gud Feb 26 '14 at 17:34
  • $\begingroup$ Actually, we use biconditional elimination in defining $(r\land q)\iff r$ to be the conjunction of two implications, $((r\land q)\rightarrow r)\land (r\rightarrow (r\land q))$, and then use "and"-elimination to get the implication we want: $r\rightarrow (r\land q).$ With $r$ as an assumption then, by using $\rightarrow$-elimination, we get $r\land q$... $\endgroup$ – Namaste Feb 26 '14 at 17:36
  • $\begingroup$ thank you very much. apologies again, i am thick with a capital T. I worked this out. is this also valid: 1. p∧q⇔p assumption 2. r⇒r∧q,⇔Elimination, 1 3. r turnstile p∧q √ 3.1 r, assumption, 3 3.2 r, ∧Elimination,3 3.3 r⇒q, ⇒Introduction. 3.1,3.2 $\endgroup$ – user131673 Feb 26 '14 at 18:15
  • $\begingroup$ thank you again, you have been a big help $\endgroup$ – user131673 Feb 26 '14 at 18:47

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.