When you write a comment such as "this function wants a sorted array" or "it returns an index between 0 and len-1", you are already writing a specification, but in a sentence that no tool can check. Formal logic is the notation that makes those sentences exact: a precondition P says what you assume before, a postcondition Q says what you guarantee after, and the Hoare triple {P} C {Q} ties them to the code C: if you start from a state in which P is true and run C to the end, you get a state in which Q is true. To prove it without trying all the inputs you need three tools, which this article builds with executable programs: invariants for loops, the weakest precondition to compute backwards what is required, the rank function for termination.
Connectives and quantifiers
Propositional logic works with statements that are true or false, for example x > 5, and combines them with five connectives. First-order logic adds the quantifiers to talk about collections of objects without listing them.
P ∧ Q(and): true if both are. It is the&&of anif.P ∨ Q(or): true if at least one is.¬P(not): true if P is false.P → Q(if... then): false only when P is true and Q is false.P ↔ Q(if and only if): true when they have the same value.∀x ∈ L: P(x)(for all): P holds for all the elements of L;∃x ∈ L: P(x)(there exists): P holds for at least one.
The connective that surprises is implication, because with P false it comes out true in every case. Think of the rule "if it rains, I take the umbrella": you break it only on the days when it rains and you do not take it, while on sunny days the rule is respected whatever you do. The preconditions of functions work like this: if P is false, the triple says nothing. The program below prints the truth table of implication and checks four laws on all the assignments, then verifies the negation of the quantifiers on all 16 possible predicates over a domain of 4 elements.
from itertools import product
def implies(p, q):
return (not p) or q
print("P Q P->Q")
for p, q in product([True, False], repeat=2):
print(f"{p!s:<6} {q!s:<6} {implies(p, q)}")
# Equivalences checked on all truth assignments
checks = {
"P->Q == (not P) or Q": lambda p, q: implies(p, q) == ((not p) or q),
"P->Q == (not Q)->(not P)": lambda p, q: implies(p, q) == implies(not q, not p),
"not(P and Q) == (not P) or (not Q)": lambda p, q: (not (p and q)) == ((not p) or (not q)),
"P->Q == Q->P": lambda p, q: implies(p, q) == implies(q, p),
}
print()
for name, f in checks.items():
outcome = all(f(p, q) for p, q in product([True, False], repeat=2))
print(f"{name}: {outcome}")
# Negation of quantifiers: domain of 4 elements, every possible predicate
# (a predicate is a true/false choice for each element: 2**4 = 16).
domain = [0, 1, 2, 3]
n_ok = 0
n_tot = 0
for values in product([True, False], repeat=len(domain)):
P = dict(zip(domain, values))
n_tot += 1
a = not all(P[x] for x in domain) # not forall x. P(x)
b = any(not P[x] for x in domain) # exists x. not P(x)
c = not any(P[x] for x in domain) # not exists x. P(x)
d = all(not P[x] for x in domain) # forall x. not P(x)
n_ok += (a == b) and (c == d)
print(f"\nPredicates checked: {n_tot}; negation of quantifiers valid in {n_ok}")
# The typical confusion: 'not all' is NOT 'none'
P = dict(zip(domain, (True, True, False, True)))
print("not all:", not all(P.values()), "| none:", not any(P.values()))
# Output:
# P Q P->Q
# True True True
# True False False
# False True True
# False False True
#
# P->Q == (not P) or Q: True
# P->Q == (not Q)->(not P): True
# not(P and Q) == (not P) or (not Q): True
# P->Q == Q->P: False
#
# Predicates checked: 16; negation of quantifiers valid in 16
# not all: True | none: False
The first three laws come out True: implication is equivalent to ¬P ∨ Q and to its contrapositive ¬Q → ¬P, and the first De Morgan law holds. The fourth, P → Q == Q → P, comes out False: swapping hypothesis and conclusion changes the meaning, and it is the most common reasoning error. On the negation of the quantifiers the count is 16 out of 16: "not all" is equivalent to "there exists one that does not", and "none" is something else. The last line shows it on an example: if a single element out of four does not satisfy the property, "not all satisfy" is true and "none satisfies" is false. This equivalence is the tool of debugging: to refute "all the elements are positive" it is enough to find one element that is not.
The Hoare triple, checked on a finite domain
In his 1969 paper Hoare writes the triple in the form P {Q} R, with the program Q in curly braces, and reads it like this: if the assertion P is true before the execution of the program Q, then R will be true on its completion. Here I use the notation {P} C {Q}, which is just another graphical convention. Note the "on its completion": it is partial correctness, which says nothing if the program does not terminate. Total correctness adds termination and is the subject of the section on the rank function.
The classic case is binary search: P is "the list is sorted in non-decreasing order", Q is "the result is -1 and the target is not in the list, or it is the index of an element equal to the target". The program that follows encodes P and Q as Python functions and tries the search on all the sorted lists of length 0 to 5 with values from 0 to 3, for each target from -1 to 4. Alongside the correct version there are two versions with a single wrong character, to see how an error shows up in the triple.
from itertools import combinations_with_replacement
def pre(A):
"""P: the list is sorted in non-decreasing order."""
return all(A[i] <= A[i + 1] for i in range(len(A) - 1))
def post(A, target, r):
"""Q: r is -1 and target is not in A, or A[r] == target."""
if r == -1:
return target not in A
return 0 <= r < len(A) and A[r] == target
def search(A, target):
left, right = 0, len(A) - 1
rank = right - left + 1 # rank function: elements still in play
while left <= right:
mid = (left + right) // 2
if A[mid] == target:
return mid
if A[mid] < target:
left = mid + 1
else:
right = mid - 1
new = right - left + 1
assert 0 <= new < rank, f"the rank does not decrease: {rank} -> {new}"
rank = new
return -1
def search_bug_a(A, target): # 'left = mid' instead of 'mid + 1'
left, right = 0, len(A) - 1
rank = right - left + 1
while left <= right:
mid = (left + right) // 2
if A[mid] == target:
return mid
if A[mid] < target:
left = mid
else:
right = mid - 1
new = right - left + 1
assert 0 <= new < rank, f"the rank does not decrease: {rank} -> {new}"
rank = new
return -1
def search_bug_b(A, target): # 'left < right' instead of '<='
left, right = 0, len(A) - 1
while left < right:
mid = (left + right) // 2
if A[mid] == target:
return mid
if A[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
def check(f):
"""Try f on all sorted lists of length 0..5 with values 0..3."""
n_cases, first_error = 0, None
for n in range(6):
for A in combinations_with_replacement(range(4), n):
A = list(A)
assert pre(A)
for target in range(-1, 5):
n_cases += 1
try:
r = f(A, target)
ok = post(A, target, r)
reason = f"result {r}"
except AssertionError as e:
ok, reason = False, str(e)
if not ok and first_error is None:
first_error = (A, target, reason)
return n_cases, first_error
for name, f in (("correct", search), ("bug_a", search_bug_a), ("bug_b", search_bug_b)):
n, error = check(f)
print(f"{name}: {n} cases, first counterexample: {error}")
print("\nRank on the case A=[1,3,5,7,9], target=7:")
A, left, right = [1, 3, 5, 7, 9], 0, 4
while left <= right:
mid = (left + right) // 2
print(f" rank={right - left + 1} [{left},{right}] A[{mid}]={A[mid]}")
if A[mid] == 7:
break
left, right = (mid + 1, right) if A[mid] < 7 else (left, mid - 1)
# Output:
# correct: 756 cases, first counterexample: None
# bug_a: 756 cases, first counterexample: ([0], 1, 'the rank does not decrease: 1 -> 1')
# bug_b: 756 cases, first counterexample: ([0], 0, 'result -1')
#
# Rank on the case A=[1,3,5,7,9], target=7:
# rank=5 [0,4] A[2]=5
# rank=2 [3,4] A[3]=7
The cases are 756: the sorted lists of length n with 4 values are C(n+3, 3), that is 1, 4, 10, 20, 35, 56 for n from 0 to 5, and the sum 126 multiplied by the 6 targets gives 756. The correct version passes all the cases. With left = mid in place of left = mid + 1 the loop cannot terminate: on the list [0] with target 1 the interval stays unchanged, and the assertion on the rank reports it. With left < right in place of left <= right the loop terminates but gets the postcondition wrong: on [0] with target 0 it returns -1. They are two failures of a different nature, and the triple tells them apart: the second violates Q, the first violates termination.
A check on 756 cases is not a proof: it covers lists of length at most 5 and values between 0 and 3. It does give useful information quickly, though, because errors of this kind almost always show up on small inputs, like here the one-element list. The complete proof is made with the tools of the following sections, which hold for any list.
Loop invariants: how to find them
A loop invariant is a property that holds on entering the loop (initialization), stays true after each iteration if it was true before (maintenance) and, on exit, together with the loop-exit condition implies the postcondition (conclusion). Maintenance is an inductive step: it is what reduces to a finite check the verification of any number of iterations. It is not a "value that does not change": it is a property that stays true while the variables change.
How to find it: start from the postcondition and replace the end-of-loop constant with the loop variable. For the maximum of a list the postcondition is m == max(A); the loop runs the index i from 1 to len(A), so the invariant is m == max(A[:i]): the maximum of the part already seen. On entry i = 1 and m = A[0], which is the maximum of A[:1]; on exit i = len(A) and the invariant coincides with the postcondition. The program checks the invariant with an assert at every iteration, and includes a wrong invariant (m == A[0], too strong) to show what happens.
def maximum(A):
"""P: A non-empty. Invariant: m == max(A[:i])."""
m = A[0]
i = 1
assert m == max(A[:i]) # initialization
while i < len(A):
if A[i] > m:
m = A[i]
i += 1
assert m == max(A[:i]) # maintenance
return m # at loop exit i == len(A): m == max(A)
def maximum_wrong(A):
"""Invariant too strong: m == A[0] stays true only until m is updated."""
m = A[0]
for i in range(1, len(A)):
if A[i] > m:
m = A[i]
assert m == A[0], f"invariant broken at i={i}"
return m
print("maximum([3, 9, 2, 9, 4]) =", maximum([3, 9, 2, 9, 4]))
try:
maximum_wrong([3, 9, 2])
except AssertionError as e:
print("maximum_wrong([3, 9, 2]):", e)
# Output:
# maximum([3, 9, 2, 9, 4]) = 9
# maximum_wrong([3, 9, 2]): invariant broken at i=1
The first line prints 9, the true maximum, and the assertions on the invariant do not fire. In the second, the wrong invariant breaks at i=1, because A[1] = 9 updates m to 9 while A[0] is 3. An invariant has to hold in every iteration, not only at the beginning, and it must also be strong enough to imply Q on exit: m == A[0] is not. Remember that these assert statements are checks on concrete inputs: they are tests dressed up as a proof. The proof is the inductive argument written above. Python, moreover, does not execute assert statements when the interpreter starts with the -O option, as the documentation of the language describes:
assert 1 + 1 == 3, "arithmetic is broken"
print("I got past the assert")
# Last line of the output in the two modes:
# python3 -I assert_o.py -> AssertionError: arithmetic is broken
# python3 -I -O assert_o.py -> I got past the assert
With -O the assertion line disappears and the program prints the next line. This is why contracts that must never be ignored have to be written with an explicit check and an exception, not with assert; the assertion remains the right tool for documenting and checking during testing.
Dijkstra's weakest precondition
Given a command C and a postcondition Q, what is the least restrictive precondition, that is the weakest, that guarantees Q? Dijkstra calls it wp(C, Q) and, in the note EWD 472 (which has the same title as his 1975 paper on guarded commands), defines it as the weakest precondition such that the execution of C terminates properly, leaving the system in a state that satisfies Q. The rules needed here are three.
- Assignment:
wp(x := E, Q)is Q with E in place of every occurrence of x (the same rule is axiom D0 of Hoare's paper). - Sequence:
wp(S1; S2, Q) = wp(S1, wp(S2, Q)), computed from right to left. - Choice with two branches:
wp(if B then S1 else S2, Q)is "if B thenwp(S1, Q), otherwisewp(S2, Q)"; it is the case with guardsBand¬Bof Dijkstra's rule for the alternative.
With an example: for x := x + 1 and Q equal to x > 5 it is enough to substitute, and you get x + 1 > 5, that is x > 4. If x > 4 holds before the instruction, x > 5 holds after; a stronger precondition such as x > 10 works but excludes useful inputs. Computing wp backwards and comparing it with the precondition you have is how verification tools check a triple. The program that follows implements the three rules as three classes, compares wp with the real execution on a swap program, and applies the same computation to the absolute value with two arithmetics: unbounded integers and 16-bit integers with wraparound.
class Assign:
"""x := E. wp(x := E, Q) = Q with E in place of x."""
def __init__(self, var, expr):
self.var, self.expr = var, expr
def run(self, s):
return {**s, self.var: self.expr(s)}
def wp(self, Q):
return lambda s: Q(self.run(s))
class Seq:
"""S1; S2. wp(S1; S2, Q) = wp(S1, wp(S2, Q))."""
def __init__(self, a, b):
self.a, self.b = a, b
def run(self, s):
return self.b.run(self.a.run(s))
def wp(self, Q):
return self.a.wp(self.b.wp(Q))
class If:
"""if C then S1 else S2: wp = (C -> wp(S1,Q)) and (not C -> wp(S2,Q))."""
def __init__(self, cond, a, b):
self.cond, self.a, self.b = cond, a, b
def run(self, s):
return self.a.run(s) if self.cond(s) else self.b.run(s)
def wp(self, Q):
return lambda s: self.a.wp(Q)(s) if self.cond(s) else self.b.wp(Q)(s)
# 1. wp(x := x + 1, x > 5) is x > 4: comparison on 201 values of x
inc = Assign("x", lambda s: s["x"] + 1)
wp1 = inc.wp(lambda s: s["x"] > 5)
print("wp(x := x+1, x>5) coincides with x>4:",
all(wp1({"x": x}) == (x > 4) for x in range(-100, 101)))
# 2. Swap with a temporary variable, postcondition with "ghost" values X, Y
swap = Seq(Assign("t", lambda s: s["x"]),
Seq(Assign("x", lambda s: s["y"]),
Assign("y", lambda s: s["t"])))
Q = lambda s: s["x"] == s["Y"] and s["y"] == s["X"]
P = lambda s: s["x"] == s["X"] and s["y"] == s["Y"]
states = [{"x": a, "y": b, "t": 0, "X": a, "Y": b} for a in range(-5, 6) for b in range(-5, 6)]
print("swap: P implies wp(swap, Q) on", len(states), "states:",
all(swap.wp(Q)(s) for s in states if P(s)))
print("swap: wp(Q) coincides with Q after the run:",
all(swap.wp(Q)(s) == Q(swap.run(s)) for s in states))
# 3. Absolute value: same triple, two semantics of arithmetic
def w16(v):
return (v + 32768) % 65536 - 32768
def absolute_value(neg):
return If(lambda s: s["x"] < 0,
Assign("x", lambda s: neg(s["x"])),
Assign("x", lambda s: s["x"]))
Q_non_neg = lambda s: s["x"] >= 0
for name, neg in (("unbounded integers", lambda v: -v), ("16 bits, modulo", lambda v: w16(-v))):
wp = absolute_value(neg).wp(Q_non_neg)
failed = [x for x in range(-32768, 32768) if not wp({"x": x})]
print(f"abs with {name}: states where wp(x >= 0) is false: {failed}")
# Output:
# wp(x := x+1, x>5) coincides with x>4: True
# swap: P implies wp(swap, Q) on 121 states: True
# swap: wp(Q) coincides with Q after the run: True
# abs with unbounded integers: states where wp(x >= 0) is false: []
# abs with 16 bits, modulo: states where wp(x >= 0) is false: [-32768]
The first line confirms x > 4 on 201 values. The two lines on the swap say that, for all 121 test states, the precondition implies wp and that wp(Q) coincides with Q evaluated after the execution: the second equality is a real check of the sequence and assignment rules against the interpreter. The last part is the most instructive. The absolute value satisfies x >= 0 with unbounded integers, but with 16 bits and wraparound it fails for a single state, -32768, whose wrapped opposite is still -32768. Same triple, different arithmetic, different result: it is the "modulo" reading of the Ariane 501 case that you find in the first article, and the reason why the semantics of arithmetic has to be written in the specification.
Termination and the rank function
Proving that a loop terminates requires a rank function: an expression over the state that stays a non-negative integer and strictly decreases at every iteration. A non-negative integer cannot decrease forever, so the loop stops. In binary search the rank is right - left + 1, the number of elements still in play, and it is exactly what the assertion assert 0 <= new < rank checks in the search program. On the list [1, 3, 5, 7, 9] with target 7 the rank goes from 5 to 2 and at the second iteration the element is found; with left = mid the rank does not decrease and the assertion reports it.
Total correctness is therefore partial correctness plus termination. Dijkstra, in the same note, introduces an integer function t defined on the state and the weakest precondition that guarantees that the execution of a statement terminates while decreasing t by at least 1: it is the same idea as the rank function, written in his notation. In practice, when a function "seems" to terminate but you do not have the rank, write it down: if you cannot exhibit a quantity that decreases, you have often found the corner case in which the loop does not end.
Exercises
1. For the loop fact = 1; for i in range(1, n + 1): fact *= i write an invariant that implies fact == n! on exit.
Solution
At the start of every iteration with index i, fact == (i - 1)! holds. On entry i = 1 and fact = 1 = 0!; after fact *= i it holds i!, that is ((i + 1) - 1)! for the next iteration; on exit i = n + 1 and therefore fact == n!. A check with assert for n from 0 to 7 passes.
2. Write the negation of "all the elements of the list are ≥ 0" and an example that makes it true.
Solution
The negation is "there exists an element less than 0": for the list [3, -1, 2] it is true, because -1 < 0. It is not "no element is ≥ 0", which for that list is false.
3. Compute wp(y := 2*y + 1, y > 9) over the integers.
Solution
You substitute: 2*y + 1 > 9, that is y > 4. A check on y from -100 to 100 confirms that the two conditions coincide.
Frequently asked questions
What is a Hoare triple, in one line?
It is the statement that, if P is true before running the program C and C terminates, then Q is true after. Hoare writes it P {Q} R in the 1969 paper; the notation {P} C {Q} is equivalent.
Why is a too-strong invariant an error?
Because it has to stay true at every iteration: in the program, m == A[0] holds at the start and breaks when m is updated. The right invariant describes the part already processed (m == max(A[:i])), not the initial value.
Is first-order logic enough to specify everything?
No. It describes properties of a state, not of sequences of states over time. To say "sooner or later it happens" or "it never happens" you need temporal logic, the subject of the fourth article.
What you can do now
You can read and write preconditions, postconditions and quantifiers in exact notation, and you can say that the negation of "for all" is "there exists one that does not". You can check a Hoare triple on a finite domain with a program, tell an error on the postcondition from one on termination, derive the invariant of a loop from the postcondition and compute a weakest precondition for assignments, sequences and choices. The next step is to model the behaviour of a system with finite state automata.
This is the second article of the Formal Methods series. The previous one is When to invest in formal methods; the next one is Finite state machines and automata.
The last article in the series, Petri Nets: structure, markings, reachability, liveness and safety, closes the path with a model that is an alternative to the state machine.
Sources
- C. A. R. Hoare, An axiomatic basis for computer programming, Communications of the ACM 12(10), 1969, pp. 576-580 - copy hosted by a university course, pages 577-578 read (the
P {Q} Rnotation and its reading, assignment axiom D0, rules of consequence, composition and iteration, Table II); consulted on 2026-11-13 - E. W. Dijkstra, Guarded commands, non-determinacy and formal derivation of programs (EWD 472), transcription from the Dijkstra Archive - technical note linked to the 1975 paper (Communications of the ACM 18(8), pp. 453-457; DOI verified only in the metadata on Crossref): read the definition of
wp, the examples for the empty statement, assignment and sequence, the definition for the alternative and the passage on the decreasing integer function; consulted on 2026-11-13 - Python documentation, The assert statement - page read: equivalence with
if __debug__and no code generated with the-Ooption; consulted on 2026-11-13
Programs run with Python 3.14.4 (python3 -I), twice each with identical output. The case counts (756, 16, 201, 121) come from the programs above; the number 756 has a second, closed-form count in the text.
Article published 2026-10-03, graduate level.
Commenti
Caricamento commenti...
Sign in to comment