1
$\begingroup$

I have the following:

$$p\land\neg q\to r, \neg r, p ⊢ q$$

I know that my attempt is incorrect, but I will show it anyways:

Step 1) $p\land\neg q\to r$ ----premise

Step 2) $\neg r$ -----premise

Step 3) $p$ -----premise

Step 4) $\neg q\to r$ ---- e1

Step 5) $\neg \neg q$ ----MT4,2

Can someone show me the proper steps? I do not think I can use MT in the way shown above, but I cannot find out how to get to q.

OP's remark from a comment: "I was curious, is there a way to bypass DeMorgan's law?"

$\endgroup$
  • $\begingroup$ In Step 4) you are reading the premise : $p∧¬q→r$ as $p∧(¬q→r)$; if you think that MT is not available, after Step 4) you have to (temporary) assume $\lnot q$ and derive : $r$. With the premise $\lnot r$ you have a contradiction and you can "blame" the assumption $\lnot q$ in order to derive (by Double Negation) : $q$. If instead you read the premise $p∧¬q→r$ as $(p∧¬q)→r$, the proof is different (see answers below) : from premise $p$ and (temporary) assumption $\lnot q$ derive $p \land \lnot q$ by $\land$-intro and then derive $r$ which gives you a contradiction with $\lnot r$. $\endgroup$ – Mauro ALLEGRANZA Feb 9 '15 at 11:03
0
$\begingroup$

Something like this?

$$\begin{split} p\wedge\neg q \to r , \neg r &\vdash \neg (p\wedge \neg q)&\quad&\textsf{Premise 1,Premise 2, Modus Tollens} \\ \neg (p\wedge \neg q)&\vdash \neg p\vee q &&1,\textsf{de Morgan's} \\ \neg p\vee q, p &\vdash q&&2,\textsf{Premise 3},\textsf{Disjunctive Syllogism} \\\hline p∧¬q→r,¬r,p &⊢q \end{split}$$


Avoiding de Morgan's

$$\begin{split} (p\wedge \neg q)\to r, p, \lnot q&\vdash r &\quad&\textsf{Premise 1,Premise 3, Assumption of $q$, Modus Tolens} \\ r, \lnot r &\vdash \bot&&1,\textsf{Premise 2},\textsf{Negation Elimination}\\\hline(p\wedge\neg q)\to r,\lnot r,p,\lnot q&\vdash \bot&&\textsf{Cut}\\\hline (p\wedge\neg q)\to r,\lnot r,p&\vdash \lnot\lnot q&&\textsf{Negation Introduction (discharges the assumtion)}\\\hline (p\wedge\neg q)\to r,\lnot r,p& \vdash q &&\textsf{Double Negation Elimination}\end{split}$$

$\endgroup$
  • 1
    $\begingroup$ this is really good, but I was curious, is there a way to bypass DeMorgan's law? $\endgroup$ – Bolboa Feb 9 '15 at 20:39
1
$\begingroup$

$$p\land\neg q\to r \iff \neg(p\land\neg q) \vee r \iff (\neg p \vee q \vee r)$$ (ref)

Since $\neg r$ and $p$ are in the premise, $q$ follows.

$\endgroup$
  • $\begingroup$ I think the question asked for natural deduction steps to prove the result: Can someone show me the proper steps? Because of that I don't think this is an answer. $\endgroup$ – Frank Hubeny Feb 21 '19 at 18:19
0
$\begingroup$

$$¬r \Rightarrow ¬(p \land ¬q) \mbox{ by modus tollens}$$

$$¬(p \land ¬q) \iff ¬p \lor ¬¬q \iff ¬p \lor q$$

$$( ¬p \lor q) \land p \Rightarrow q \mbox{ by definition of the disjunction operator.}$$

$$\therefore p\land\neg q\to r, \neg r, p ⊢ q$$

$\endgroup$
  • $\begingroup$ I don't think this answer shows the natural deduction steps asked for in the question. $\endgroup$ – Frank Hubeny Feb 21 '19 at 18:21
0
$\begingroup$

The following proof uses neither modus tollens nor De Morgan's law.

It, however, uses the precedence of logical operators where the conjunction operator (∧) has higher precedence over the conditional operator (→). That is, $p∧¬q→r$ is the same as $(p∧¬q)→r$.

Given the above, here is a proof:

enter image description here


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.