Hoare Logic and Proving a Program Meets Its Specification
A triple states what holds before a fragment runs and what holds after. Rules compose triples along the structure of the program, loops need an invariant that a person supplies, and the leftover verification conditions are what a solver is handed.
What a learner can do afterwards
- Prove a short straight-line fragment correct by composing triples
- Supply a loop invariant and show it is preserved and strong enough at exit
- Say why a tool computes the weakest precondition rather than the strongest postcondition
1 · Read
A Hoare triple says what holds before a fragment runs and what holds after, with the code in the middle. Rules compose triples along the shape of the program, so you prove a short straight-line fragment by chaining one triple after another.
Loops need something extra: an invariant that you supply yourself. It must hold before the loop, stay preserved by each pass, and be strong enough that, together with the loop ending, it implies what you want after.
Take two assignments in a row. Prove the first triple, feed its ending claim as the start of the second, and chain them. The composed triple now covers both lines, which is how straight-line code is proved.
Proving by hand leaves small checks called verification conditions, and a solver discharges those. Tools work backwards with the weakest precondition rather than forwards with the strongest postcondition, because going backwards keeps the goal in view.
Chain triples along the code, guard loops with an invariant you supply, and let the solver close the small gaps.
2 · Watch
Take it off screen
Where it sits
Learn first
This opens up
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.