3
$\begingroup$

I have the following: $$⊢p \land q \to (p\to q)$$

I'm having a difficult time trying to figure out where to begin. I believe that I am supposed to assume p and q and then somehow use the copy rule to construct the equation, however I am not quite sure.

Can someone help me out?

Attempt taken from a comment: "...this is my attempt... first assume p, assume q, copy p, copy q, introduce →, introduce ∧, then introduce → between both... in that order"

$\endgroup$
4
  • 1
    $\begingroup$ Hint: Show the contrapositive. $\endgroup$
    – Extremal
    Feb 8 '15 at 23:46
  • 1
    $\begingroup$ Hint: The operator precedence is $\;\vdash \mathbf (p\wedge q\mathbf ) \to (p\to q)\;$. $\endgroup$ Feb 8 '15 at 23:51
  • $\begingroup$ Or you may use truth table $\endgroup$
    – Extremal
    Feb 9 '15 at 0:04
  • $\begingroup$ the problem is I don't have a solution to this question and I've never dealt with this kind of problem before, but this is my attempt... first assume p, assume q, copy p, copy q, introduce $\to$, introduce $\land$, then introduce $\to$ between both... in that order $\endgroup$
    – buydadip
    Feb 9 '15 at 0:04
2
$\begingroup$

To prove $A \to B$ in a natural deduction system you assume $A$ and derive $B$, and then apply Conditional Proof. OK? That's the standard way of proving a conditional.

To prove $(p \land q) \to (p \to q)$ in a natural deduction system, you need to assume $(p \land q)$ as a temporary assumption and aim for $(p \to q)$.

So assume $p \land q$. That gives you immediately $p$ and $q$.

Can you now get to $p \to q$?

Well there's a standard trick for getting from $q$ to $A \to q$ for any $A$ at all. Do you know it? The fine details of how you set it out will depend, however, on your exact system. (Basically, in an application of Conditional Proof, we are usually allowed "vacuous discharge" of premisses that were never in fact used. You may need to check out how this is handled in the system you are working with! It will be, so to speak, in the fine print!)

$\endgroup$
2
  • $\begingroup$ so if I assume $p\land q$ which gives me $p$ and $q$, can't I just copy $p$ and $q$ and then use $\to i$ on it to get $p\to q$? $\endgroup$
    – buydadip
    Feb 9 '15 at 0:11
  • $\begingroup$ It will depend on your system: some ND systems allow "reiteration" or what you are calling "copying", some don't. It is one of those fine-print differences between different versions on the market! You need to look at the fine print, and I really can't tell you what will work in your particular system, sight unseen. $\endgroup$ Feb 9 '15 at 0:16
-1
$\begingroup$

Assuming the conjunction operator has higher precedence than the conditional operator, what needs to be proved is the same as this:

$$⊢(p∧q)→(p→q)$$

Here is a proof:

enter image description here

The OP made the following attempt:

this is my attempt... first assume p, assume q, copy p, copy q, introduce →, introduce ∧, then introduce → between both... in that order

The above proof uses these steps:

  1. Assume $P∧Q$ as the antecedent of the desired conditional.
  2. Assume $P$ as the antecedent of the conditional in the conclusion.
  3. Derive $Q$ from the first assumption using conjunction elimination.
  4. Discharge the assumption on line 2 by rewriting the subproof in lines 2-3 as $P→Q$ on line 5 with conditional introduction as the justification.
  5. Discharge the assumption on line 1 by rewriting the subproof in lines 1-4 as $(P∧Q)→(P→Q)$ on line 5 with conditional introduction as the justification.

That completes the proof.


Kevin Klement's JavaScript/PHP Fitch-style natural deduction proof editor and checker http://proofs.openlogicproject.org/

"Operator Precedence" Introduction to Logic http://intrologic.stanford.edu/glossary/operator_precedence.html

$\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.