Computer Science Canada

Help with Computer Science Assignment

Author:  xoxoxoxoxo [ Mon Sep 17, 2012 8:06 am ]
Post subject:  Help with Computer Science Assignment

I am a student in university currently enrolled in an advanced programming class. For an assignment, we were asked to prove that:
For all Nats x, for all Nats y, plus x y = add x y
Definitions:
plus x Z = x
plus x (S y) = S (plus x y)
add x Z = x
add x (S y) = add (S x) y

I started attempting to prove this by using the structural method (which is like mathematical induction). The base step (proving for y = Z) is easy, but I can't seem to get through the induction step:
We assume that for a Nat w, plus x w = add x w
We want to prove that plus x (S w) = add x (S w), so:
plus x (S w) = S (plus x w) [from definition of plus]
= S (add x w) [from inductive hypothesis]
= ???

Please help!

Author:  Dreadnought [ Mon Sep 17, 2012 7:06 pm ]
Post subject:  Re: Help with Computer Science Assignment

Ah, good ol' CS 145, I miss that class. I personally feel that that the first assignments are very important, thus I'm afraid I can't help you.

However, you're on the right track.

Don't worry too much about it. If you're still stumped talk to classmates or go see Prabhakar during office hours.


: