Edit: I’ve just read this (pdf) and found it really helpful explaining some of the concepts I’ve been wrestling with
I’m working my way through The Haskell Road to Logic, Maths and Programming to try and get a better understanding of functional programming and all the things that that entails.
Sadly, I’m hitting problems. The programming problems I’m okay with, I can run the code and see if the result is was I expect it to be. But I’m struggling with the proof-based exercises. I can contact the authors here but I don’t want to get a list of all the answers – mostly because I’ll know I’ll start cheating if I have them! So I’m stuck trying to work out if what I’ve done is correct.
That’s where this blog comes in, maybe I’ll get some comments from people telling me what I’m doing wrong…
Exercise: 3.5.1 (Page 83)
Show that from P <=> Q it follows that (P => R) <=> (Q => R)
Major edit alert!
After lots of reading and help I’ve reached a conclusion. There’s an easier way to write proofs using actual sentances! Also, for this first exercise there are two ways to do it, the first which is what I originally tried to say (but got wrong) and a second which Kim-Ee Yeoh helped me reach in the comments.
My Way
We are given P <=> Q, so we know that this is True. For this to be True the following two statements must also be True.
- P => Q
- P <= Q
For these two statements to be True, P and Q must also be True.
Because we know that P and Q are True, we can take these as new givens and use the Reduction Rule on both sides of the <=> in the statement we’re asked to prove. So;
- P => R becomes R (using the Reduction Rule and our knowledge that P is True)
- Q => R becomes R (using the Reduction Rule and our knowledge that Q is True)
Now I’m a bit stuck, now I have to prove R <=> R and the only thing that tells me that this is True is my intuition, which can rarely be trusted. I can break it into two peices (as above for the oriignal given) and prove R => R and R <= R, which should leave me concluding that R is True. Right?
Kim-Ee Yeoh’s Way
Part 1: Copied from the comments below
Assume Q => P and P => R. We want to show Q=>R. It suffices to show that if Q is true, R must also be true. So let’s assume Q is true. Then Q=>P forces P to be true. In turn P=>R forces R to be true. Done.
Part 2: All my own mess
Assume P => Q and Q => R. We want to show P => R. It suffices to show that if P is True, R must also be True. So let’s assume P is True. Then P => Q forces Q to be True. In turn Q => R forces R to be True. Done.
Part 3: Mess continuation, a step to far?
The above two sub-proofs mean we can rewrite the original statement to be proved as True <=> True, which again boils down to True.
Now I’m sure I’ve got something wrong, because it seems too easy. Also, writing out these two approaches one after the other makes me think that they are basically the same, is that a correct thinking?
Exercise: 3.5.2 (Page 83)
Show that from P <=> Q it follows that (R => P) <=> (R => Q)
We are given P <=> Q, so we know that this is True. For this to be True the following two statements must also be True.
- P => Q
- P <= Q
For these two statements to be True, P and Q must also be True.
Because we know that P and Q are True, we can take these as new givens and use the Reduction Rule on both sides of the <=> in the statement we’re asked to prove. So;
- R => P becomes R => T
- R => Q becomes R => T
Looking at the Truth Table for =>, ? => True is always True, so the original statement we need to prove can be rewritten as True <=> True, which again boils down to plain old “True”.
I guess what I’m trying to say is, given my lack of confidence in this area, can someone who knows more than me about this stuff help me work out if I’m doing it right? A thousand “Thank You”s in advance.
Edit: I must say a big thank you to Kim-Ee Yeoh for the comments he left, I found them really useful!
Posted by Tom 