2

I guess the biggest issue for me is not knowing how to work with $\wedge$.

I'm not new to the concept of proof... just formal proofs.

Here is my attempt:

Show: $(P \wedge \lnot R \rightarrow \lnot Q)$

$P \wedge \lnot R$

Show $\lnot Q$

$Q$. (assumption for contradiction)

$(P \wedge Q) \rightarrow R$

now I'm stuck.... Really I just don't know how to work with $\wedge$, any help appreciated. Or maybe if I could see half the proof, then I could work the other direction. Thank you

Heptapod
  • 1,123
user351797
  • 1,005

3 Answers3

1

Almost there!

Isolate the $P$ from $P \land \neg R$ by $\land$ Elim.

Combine this with the $Q$ from the Assumption to get $P \land Q$ using $\land $ Intro

Now you can use $\rightarrow$ Elim with $(P \land Q) \rightarrow R$ and $P \land Q$ to get $R$, and that will contradict the $\neg R$ that you can isolate from the $P \land \neg R$ by $\land$ Elim.

Here it is more formally (and inside the larger $\leftrightarrow$ proof):

enter image description here

Bram28
  • 100,612
  • 6
  • 70
  • 118
  • I think perhaps "∧ Elim" is what I was precisely unsure if I could do.

    So is it a basic "rule of inference" that if we have $P$ and $Q$ in our proof then we automatically get $P\wedge Q$? Conversely, if we have $P\wedge Q$ then we automatically get $P$ and $Q$.
    This seems obvious.... but is there a name for these steps. Is this what you mean by "∧ Elim"?

     – user351797 Sep 08 '17 at 19:51
  • Also..... When trying to show $(P \wedge \sim R \rightarrow \sim Q)$ you are allowed to assume both $P \wedge \sim R$ and $\sim \sim Q$? This seems to be combining "conditional derivation" and "indirect derivation" techniques. Sorry if my question is super basic or unclear.... let me know if I can clarify more – user351797 Sep 08 '17 at 20:02
  • 1
    @Clclstdnt No apologies needed! OK, yes, from $P \land Q$ you can infer either $P$ or $Q$ by themselves, and that's called $\land $ Elim in most proof systems (some systems call it Simplification). And yes, from $P$ and $Q$ individually you can infer $P \land Q$ by $\land $ Intro, sometimes called Conjunction. And when trying to show $(P \land \neg R) \rightarrow \neg Q$ you first assume $P \land \neg R$ as part of the conditional derivation (I do this on line 3), and then assume $Q$ (or $\neg \neg Q$ as part of the indirect derivation (I do this on line 4). So one is inside the other. – Bram28 Sep 08 '17 at 21:04
  • @Clclstdnt: Wikipedia https://en.wikipedia.org/wiki/Natural_deduction#Introduction_and_elimination confirms that $\land_I$ and $\land_E$ are indeed rules of inference in natural deduction. – beroal Sep 10 '17 at 09:03
1

Proof for $\rightarrow$ part
To show that $(P \wedge Q \rightarrow R) \leftrightarrow (P \wedge \sim R \rightarrow Q)$.
We can assume $(P \wedge Q \rightarrow R)$ and $P \wedge \sim R$ and then show $Q$.
Or, we can assume $(P \wedge Q \rightarrow R)$, $P \wedge \sim R$ and $Q$ and arrive at a contradiction.
$P \wedge \sim R \rightarrow P$ and $P \wedge \sim R \rightarrow \sim R$.
Also, $P \wedge Q \rightarrow R$.
So, we have both $R$ and $\sim R$ and this is a contradiction.
I hope you can do the other half yourself.

Apurv Anand
  • 332
1

I only give you the proof of the forward direction i.e. "$\Rightarrow$" so you could have the chance to work on the proof for the backward direction.

Proof. ($\Rightarrow$) Suppose $P∧Q \rightarrow R$. Now we prove the contrapositive. Suppose $Q$. Now we have two cases:

Case 1. $\lnot P$, ergo we obviously have $\lnot P \lor R$.

Case 2. $P$. Since we had $Q$, then from $P$ and $Q$ and "$P∧Q \rightarrow R$", by modus ponens we get R. Hence $\lnot P \lor R$.

Since from both cases we had $\lnot P \lor R$, then $Q \rightarrow \lnot P \lor R$ which is equivalent to $P∧\lnot R \rightarrow \lnot Q$. Therefore, if $P∧Q \rightarrow R$, then $P∧\lnot R \rightarrow \lnot Q$.

Hope this helps.

Heptapod
  • 1,123