S3U

Science / Programming basics / Graduate / sce70

Programming Basics: Derive a Weakest Precondition

Reason backward through assignments rather than relying only on examples.

All worksheets
5 questions0m 0s

Prerequisites

Sequential program semantics, mathematical induction, logic and reasoning with unbounded integers.

Learn the skill

Use mathematical integers and sequential assignments: SET x TO x + 2; SET y TO 3 * x. Desired final condition is y >= 12. A weakest precondition is the least restrictive condition on the initial state guaranteeing that outcome. Substitute assigned expressions backward in reverse execution order.

Worked example

First replace y by 3x to obtain 3x >= 12, so the intermediate x >= 4. Then replace x by x + 2 to obtain initial x + 2 >= 4, hence initial x >= 2. These finite assignments always terminate in this model.

To guarantee final y at least twelve after x becomes x plus two and y becomes three times x, first require intermediate x at least four, then initial x at least two.
To guarantee final y at least twelve after x becomes x plus two and y becomes three times x, first require intermediate x at least four, then initial x at least two.
Question 1 What is the weakest condition on the initial x?
Question 2 Starting with x = 2, what is the final y?
Question 3 Starting with x = 1, what is the final y?
Question 4 Does requiring initial x >= 4 guarantee the result?
Question 5 For a loop, what is needed beyond partial correctness to claim total correctness?

Further inquiry

Derive the weakest precondition by substitution, prove both sufficiency and minimality, and distinguish it from stronger sufficient conditions. Extend the discussion to a loop: explain why a partial-correctness invariant alone does not establish termination, and give a decreasing integer variant for a suitable example.

Review criteria

  • State the execution model and the domain of every input.
  • Justify each implication, update order and boundary case rather than only checking examples.
  • Distinguish correctness on termination from an argument that termination occurs.