1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Unless you say the things you've learned and what you tried, beyond that you need to "use math", it's going to be difficult to get an answer that's actually going to help you get credit on your homework problem. (I think that suggestion 2 in the answer below is by far the easiest, but maybe that's not what your instructor is looking for.) $\endgroup$ – Louis Mar 26 '14 at 17:27
  • $\begingroup$ Which calculus are you using? $\endgroup$ – Raphael Mar 27 '14 at 15:13
  • $\begingroup$ Just to mention, this result is commonly referred to as shunting. Also, for the categorically inclined, it amounts to saying that $(\land Q)$ is left adjoint to $(Q \to)$ ;) $\endgroup$ – Musa Al-hassy Jun 28 '14 at 7:17
8
$\begingroup$
  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.

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Just to mention, this equivalence is commonly termed currying/uncurrying :) $\endgroup$ – Musa Al-hassy Jun 28 '14 at 7:12
  • 1
    $\begingroup$ And incorrectly so! It should be called Schönfinkeling. $\endgroup$ – Pseudonym Jun 29 '14 at 7:10
  • $\begingroup$ Yes, but sadly things tend to be associated with those who popularised them rather than those who conceived them; eg the case of Edison vs. Tesla. $\endgroup$ – Musa Al-hassy Jun 29 '14 at 15:42
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Yep, this is a valid proof, though should include the very first line for clarity. Perhaps this led the asker into a bit of a confusion. Otherwise, great. $\endgroup$ – Musa Al-hassy Jun 28 '14 at 7:14

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.