[Haskell-cafe] Propositional logic question

Dave Tapley dukedave at gmail.com
Mon Jun 25 15:41:56 EDT 2007


Hopefully this is just about on topic enough..
(Oh and it's not home work, I just can't bring myself to let it go!)

Taken from "Simon Thompson: Type Theory and Functional Programming"

Section 1.1
Exercise 1.3

Question: Give a proof of (A => (B => C)) => ((A /\ B) => C).

Now I can easily perform (and verify, it's given earlier in the
section) the proof of implication with the terms flipped around:
((A /\ B) => C) => (A => (B => C))
Thus:

[A]2  [B]1
----------- (/\ I)      [(A /\ B) => C]3
  A /\ B
---------------------------------------- (=> E)
                   C
                 --------- (=> I) 1
                 B => C
                 ------------------ (=> I) 2
                 A => (B => C)
                 --------------------------- (=> I) 3
                 ((A /\ B) => C) => (A => (B => C))


My problem arrives finding a solution to the exercise question, my
approach is to basically run the above proof backwards.
Thus:

A => (B => C)     A
--------------------- (=> E)     B
      B => C
--------------------- (=> E)
           C

Now at this point I thought "aha, I can use (=> I) to introduce (A /\
B)" and get:

--------------------- (=> I) 1
    (A /\ B) => C

But here I am only entitled to discharge (A /\ B) in the preceding
proof and not A and B on their own.
What proof which would allow me to discharge my assumptions A and B?

I can see in my head how it makes perfect sense, but can't jiggle a
way to do it using only the given derivations.

Many thanks,
Dave


More information about the Haskell-Cafe mailing list