Proving Equivalences

15th December 2009

These are lecture notes from my Computer Science course, not a general reference for "Proving Equivalences"

We are asking the question How can we establish whether two functional expressions are equivalent (interchangeable)?

You can’t just test across a few results/arguments; there may be an infinite number of possible arguments.

Instead, you can use maths style proving like natural induction.

However a caveat to bear in mind; beware when doing integer division and shifting around dividers. For example this causes problems when doing integer division:

m / d + n / d  =  (m + n) / d

There is a similar law which does hold for + and /:

m / d + n = (m + n * d) / d
(+n).(/d) = (/d).(+n x d)

The second line states ‘adding n after dividing by d is the same as dividing by d after adding n and multiplying by d.

Never forget the undefined case when you are proving equivalence

Comments