Reason it Out: Basic implication reasoning

Question

It is possible to do a truth table, but my instructor says we should be able to just reason it out:

$P\Rightarrow (Q\Rightarrow R)$ is equivalent to $(P\wedge Q) \Rightarrow R$.

My instructor says something like, "The second statement just points out the underlying meaning of the first statement. They both rely on two assumptions--$P$ and $Q$. So, they are equivalent."

I do not quite understand how to reason it out. Could anyone explain it a little bit?

Answer 1

Assume $$P\Rightarrow (Q\Rightarrow R)\tag{$*$}$$ is true: we seek to prove that $(P\wedge Q) \Rightarrow R$ is true. In order to do this by standard methods of reasoning, we assume $P\wedge Q$ is true and seek to deduce $R$.

So, if $P\wedge Q$ then both $P$ and $Q$ are true. Since $P$ is true, $(*)$ tells us that $Q\Rightarrow R$ is true; since $Q$ is true, this tells us that $R$ is true, as required.

You also have to check the converse, but it's very similar and I'll leave it up to you.

Answer 2

Basically, both $P\to(Q\to R)$ and $(P\wedge Q)\to R$ tell you theexact same story: that $R$ will be true if $P$ and $Q$ are.

---

$P\to(Q\to R)$ states: $R$ if $Q$, if $P$.   From that we may infer $R$ when given both $P$ and $Q$.   Thus $(P\wedge Q)\to R$ is entailed by $P\to(Q\to R)$.

$(P\wedge Q)\to R)$ states: $R$ if both $P$ and $Q$.   From that we may infer that $R$ if $Q$, when given $P$.   Thus $P\to(Q\to R)$ is entailed by $(P\wedge Q)\to R$.

Thereby informally demonstrating a logical equivalence.   The formal proof follows the same outline; in natural deduction systems.

Answer 3

To prove $P\to(Q\to R)$, we assume $P$ and prove $Q\to R$ which we do by (additionally) assuming $Q$ and proving $R$. To prove $(P\land Q)\to R$ we assume $P\land Q$ and prove $R$, but assuming $P\land Q$ is the same as assuming both $P$ and $Q$. Both cases reduce to proving $R$ given we assume both $P$ and $Q$. Seeing that what it means to prove either of these statements is the same thing is (very likely) what your instructor was trying to get at.

This can be formally illustrated via LK/LJ (and beyond) or in other formal proof systems.

$$\dfrac{\dfrac{\mathrm{P}, \mathrm{Q}\vdash \mathrm{R}}{\mathrm{P}\vdash \mathrm{Q}\to{}\mathrm{R}}\rlap{({\to}R)}}{\vdash \mathrm{P}\to(\mathrm{Q}\to\mathrm{R})}\rlap{({\to}R)}\qquad\qquad\qquad\dfrac{\dfrac{\mathrm{P}, \mathrm{Q}\vdash \mathrm{R}}{\mathrm{P}\land\mathrm{Q}\vdash \mathrm{R}}\rlap{(\land L)}}{\vdash (\mathrm{P}\land\mathrm{Q})\to\mathrm{R}}\rlap{({\to}R)}$$

It's easy to show that the two rules used, ${\to}R$ and $\land L$, are invertible. That is, we can derive $\dfrac{\Gamma,P\vdash Q}{\Gamma\vdash P\to Q}$ and $\dfrac{\Gamma, P\land Q\vdash R}{\Gamma,P, Q\vdash R}$. In this way, we show that to derive either $\vdash P\to(Q\to R)$ or $\vdash (P\land Q)\to R$ is formally equivalent to deriving $P,Q\vdash R$. As alluded to by the broad range of logics (not just proof systems) where this holds, this is a very fundamental result. In the categorical semantics of logic, this equivalence would be written like $\mathcal{C}(P\otimes Q,R)\cong\mathcal{C}(P,Q\multimap R)$ natural in $P$, $Q$, and $R$ where $\mathcal C$ is a monoidally closed category. Indeed, this is typically taken as the very definition of $\multimap$ (which corresponds to $\to$ in a usual logic, while $\otimes$ corresponds to $\land$). This means that in a large variety of logics, including ones where truth tables make no sense, we would still expect these to be provably equivalent. This equivalence is (close to) what it means for a connective to be "implication".

Answer 4

$$P\Rightarrow (Q\Rightarrow R)\tag1$$ is equivalent to $$(P\wedge Q) \Rightarrow R.\tag2$$

I do not quite understand how to reason it out.

1. Assume that $(1)$ is true.

   Suppose that $(P\land Q)$ is true; then, in particular, $P$ is true; so, by assumption $(1),\:(Q\Rightarrow R)$ is true; so, by our initial supposition that $Q$ is true, $R$ is also true. Therefore, $(2)$ is true.

2. Assume that $(2)$ is true.

   Suppose that $P$ is true; further suppose that $Q$ is true; then, by assumption $(2),\,R$ is true. Therefore, $(1)$ is true.

Since $(1)$ and $(2)$ imply each other, they are equivalent sentences.