Prove while loop correctness using Hoare logic. Define the loop invariant and show…
- User
Prove while loop correctness using Hoare logic. Define the loop invariant and show precondition establishes it, body preserves it, and termination implies postcondition.
- Assistant
Outlining while loop correctness proof
The correctness proof uses a loop invariant I such that the precondition implies I, executing the loop body under I and the loop condition preserves I, and when the loop exits, I and the negation of the condition imply the postcondition. Total correctness adds termination via a decreasing variant. What Hoare logic gives you for a loop is not a “magic” rule but a recipe: you have to find a predicate (I) that is true every time control is at the top of the loop. The standard rule for partial correctness is [ \frac{{I\land B};C;{I}}{{I};\texttt{while};B;\texttt{do};C;{I\land\neg B}}, ] and it is used in context as follows. Suppose you want to prove ({P};\texttt{while};B;\texttt{do};C;{Q}). Choose an invariant (I) and establish the three side–conditions
- the precondition establishes the invariant: (P\Rightarrow I);
- the body preserves the invariant when the guard is true: ({I\land B};C;{I});
- when the loop exits, the invariant gives you the postcondition: (I\land\neg B\Rightarrow Q).
Then by the sequencing rule and the while–rule you can derive ({P};\texttt{while};B;\texttt{do};C;{Q}). The informal proof is by induction on the number of iterations: (i) (I) holds before the first test because of (P\Rightarrow I); (ii) if (I) holds at the top of an iteration and (B) is true, the body leaves (I) true; (iii) if an iteration ends with (B) false, then (I\land\neg B) holds, so (Q) holds. To upgrade this to total correctness you add a termination argument, e.g. a variant that decreases on each iteration, ensuring that the situation (I\land B) cannot persist forever.
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.