How can I prove $P \rightarrow (Q \rightarrow R)$ is equivalent to $(P \wedge Q) \rightarrow R$

Question

I'm a freshman CS student at my university and i'm struggling with understanding my professor through his thick accent. I've asked him to explain the proof for this multiple times and still have trouble comprehending what he's trying to tell me.

The question is:

Prove that: $P\rightarrow(Q\rightarrow R)$ is equivalent to $(P \wedge Q) \rightarrow R$

He wants us to prove it using math and goes on to tell me that $P \rightarrow (Q \rightarrow R) = \neg P \vee (\neg Q \vee R)$

From that point on, I was completely lost and unable to follow along.

Answer 1

1. You could just construct the truth tables for the two formulas: there are only three variables, so the tables are only eight lines.

2. Use de Morgan's laws, distributivity and so on to rearrange one formula into the other.

3. Use similar techniques to show that $[P\rightarrow (Q\rightarrow R)] \leftrightarrow [(P\wedge Q)\to R]$ is equivalent to true.

4. Use similar techniques to show that $[P\rightarrow (Q\rightarrow R)] \leftrightarrow \neg[(P\wedge Q)\rightarrow R]$ is equivalent to false.

5. Use one of the various propositional proof systems to accomplish one of 2–4, though that sort of thing will probably come up later in your course.

Answer 2

A very useful fact (especially for this problem) is that the following two expressions are logically equivalent $$ A\rightarrow B\quad\text{and}\quad \neg A\lor B $$ Then you could show that the two expressions you're given are equivalent, like this:

1. From $P\rightarrow (Q\rightarrow R)$, replace the right implication by its equivalent and then replace the left implication. You'll get something we'll call Exp 1.
2. From $(P\land Q)\rightarrow R$, replace the implication by its equivalent and then use deMorgan's law. You'll get something we'll call Exp 2.

Lo and behold, you'll find that Exp 1 and Exp 2 are the same, so you're done. It's worth noting that you were lucky in this problem: it's not always that simple.

Answer 3

There have been two good answers as to how you might prove it, depending on the logical system. But it might also help to think about exactly why it must be true.

Suppose you have a mathematical function $f : A\times B \rightarrow C$. That is, it takes an element of type $A$ and an element of type $B$, then it returns an element of type $C$.

Now consider a function $f' : A \rightarrow (B \rightarrow C)$. This is a function that takes an element of type $A$ and returns a function. This function, in turn, takes an element of type $B$ and returns an element of type $C$.

Can you see that these are, in a sense, equivalent? You might call the first function by passing a pair $f(a,b)$ and the second one by passing an element, then passing an element to the function returned, like $(f'(a))(b)$. Either way, you get an element of $C$ by passing in an element of $A$ and an element of $B$.

So the types $A \times B \rightarrow C$ and $A \rightarrow (B \rightarrow C)$ are isomorphic. For every function of one type, there is a function of the other type which does the same thing. Using set exponent notation makes this even more obvious: it's saying that $C^{A \times B}$ is isomorphic to $(C^B)^A$.

It may not be obvious what this has to do with logic, but actually the connection is extremely deep and completely rigorous. If you're interested, look up the Curry-Howard correspondence, or Curry-Howard isomorphism.

Answer 4

Though you are two steps from the solution:

¬P∨(¬Q∨R)

is also (associativity)

(¬P∨¬Q)∨R

is also (De Morgan's law)

¬(P∧Q)∨R

is also (definition of →)

P∧Q→R