A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
Hoare logic is a formal system for reasoning about the correctness of imperative programs using triples of the form {P} C {Q}, where P is a precondition, C is a command, and Q is a postcondition. The triple asserts that if P holds before executing C, and C terminates, then Q holds afterward (partial correctness). Hoare logic provides axioms and inference rules for each language construct (assignment, sequencing, conditionals, loops), enabling compositional proofs that a program meets its specification.
Hoare logic, introduced by Tony Hoare in 1969, provides a rigorous framework for proving that programs meet their specifications. The central object is the Hoare triple {P} C {Q}. P is a logical assertion (the precondition) describing what must be true before command C executes; Q (the postcondition) describes what will be true afterward. The triple is a partial correctness assertion: it only guarantees Q when C actually terminates. If C loops forever, the triple is vacuously satisfied regardless of Q.
The power of Hoare logic lies in its compositional proof rules — one rule per language construct. The assignment axiom {Q[x/E]} x := E {Q} works backward: to establish postcondition Q after assigning E to x, you need Q with E substituted for every occurrence of x to hold beforehand. The sequencing rule lets you chain triples: if {P} C1 {R} and {R} C2 {Q}, then {P} C1; C2 {Q}. The conditional rule splits on the branch condition: prove the then-branch under the condition and the else-branch under its negation. The while rule introduces a loop invariant I: if {I and B} body {I}, then {I} while B do body {I and not B}. Finding the right loop invariant is typically the hardest step in a Hoare logic proof.
The rule of consequence is the structural glue. It says: if you can prove {P} C {Q}, and P' implies P and Q implies Q', then {P'} C {Q'} holds. This lets you strengthen preconditions (assume more) and weaken postconditions (promise less), which is always sound. Without this rule, composing subproofs would be impractical because each step's postcondition would need to exactly match the next step's precondition.
A key subtlety is that Hoare logic as described only handles partial correctness — a non-terminating program satisfies any specification. To prove total correctness, you must additionally show termination, typically by exhibiting a variant (also called a ranking function): a natural-number-valued expression that decreases with each loop iteration and is bounded below, guaranteeing the loop must eventually exit. This extension connects Hoare logic to well-founded orderings and termination analysis.
Hoare logic provides the conceptual foundation for all subsequent work in program verification. Floyd-Hoare verification automates the process, weakest precondition calculus mechanizes the backward reasoning the assignment axiom uses, and separation logic extends the framework to handle heap-manipulating programs. Understanding Hoare triples and their proof rules is the entry point to the entire field of formal program verification.