CS389R advice on HW
Sandip Ray
I got some queries regarding the level of detail necessary in
answering the proof exercises, and concerns that writing out all the
details is very time-consuming. I'm posting an answer to the group
since it can help everybody.
First, note that while it is critical to have the right intuition in
order to _come up_ with a proof, a beauty of formal logic is that none
of this intuition is necessary to _check_ the proof. Thus, for
writing a proof in homework you do not need to explain why you came up
with what, --- it's sufficient if what you came up with is legal.
Also, feel free to merge steps, as long as it's clear what the steps
mean.
For example, I'll be satisfied with the following steps for Problem
40. (I show this example, since we did it in class.)
Problem 40.
Prove
(equal (app (app a b) c) (app a (app b c)))
Proof by induction on a.
Base case:
(implies (not (consp a))
(equal (app (app a b) c) (app a (app b c))))
We simplify the conclusion taking hypothesis as given.
LHS = (app (app a b) c)
= [ Expanding inner app; given (not (consp a)) ]
(app b c)
RHS = (app a (app b c))
= [ Expanding outer app; given (not (consp a)) ]
(app b c)
= LHS
Induction Step:
(implies (and (consp a)
(equal (app (app (cdr a) b) c) (app (cdr a) (app b c))))
(equal (app (app a b) c) (app a (app b c))))
Again, we simplify the conclusion.
LHS = (app (app a b) c)
= [ Expanding inner app; given (consp a) ]
(app (cons (car a) (app (cdr a) b)) c)
= [Expanding outer app]
(cons (car a) (app (app (cdr a) b) c))
= [ Using induction hypothesis ]
(cons (car a) (app (cdr a) (app b c)))
RHS = (app a (app b c))
= [ Expanding outer app; given (consp a) ]
= (cons (car a) (app (cdr a) (app b c)))
= LHS
Q.E.D.
The point is, we only need to see that each of your steps can be
checked as legal symbol manipulation. Your intuition does not need to
be explained, intuition is just your guide in coming up with a proof.
After you've done a couple of problems, it will be fine if you merge
even the above steps, for example saying [Expansion, followed by
application of induction hypothesis.]
Examples of things that will probably not be acceptable are:
(1) If some lemma is necessary and you do not state and prove the lemma.
(2) If you're using induction and don't mention what the base and
induction steps are.
(3) You don't mention where you use the induction hypothesis in the
proof (if at all).
The above will not take too much of writing, so hopefully that reduces
your writing time.
Hope this helps.
-- Sandip