Mathematical logic is used to state correctness properties and to prove that a program or algorithm has these properties. Fortunately, the logic needed in this book is not very complex, and consists of the propositional calculus (which is reviewed in this appendix) and its extension to temporal logic (Chapter 4). Variables in concurrent algorithms typically take on a small number of values, so that the number of different states in a computation is finite and relatively small. If a complicated calculation is required, it is abstracted away. For example, a concurrent algorithm may calculate heat flow over a surface by dividing up the surface into many cells, computing the heat flow in each and then composing the results. The concurrent algorithm will not concern itself with the calculations using real numbers, but only with the division of the calculation into tasks, and the synchronization and communications among the tasks.
For more on mathematical logic in the context of computer science, see my textbook [9].
We assume the existence of an unbounded set of atomic propositions {p, q, r, . .. }, one unary operator ¬ (not), and four binary operators, ∨ (disjunction, or), ∧ (conjunction, and), → (implication) and ↔ (equivalence). A formula of the propositional calculus is constructed inductively as the smallest set such that an atomic proposition is a formula, and if f and g are formulas, then so are (¬ f), (f ∨ g), (f ∧ g), (f → g) and (f ↔ g).
As with expressions in programming languages, parentheses can be omitted by assigning a precedence to each operator: ¬ has the highest precedence, followed in descending order by ∧, ∨, → and ↔. We can further omit parentheses since it follows from the definition of the semantics of formulas that all the binary operators are associative except for →. Therefore, the meaning of the formula (p ∨ q) ∧ r is the same as that of p ∨ (q ∨ r), and it can be written p ∨ q ∨ r. However, p → q → r must be written as (p → q) → r or p → (q → r), because the meanings of the two formulas are different.
Here are some examples of formulas of the propositional calculus:
p, p → (q → p), (¬ p → ¬ q) ↔ (q → p), (p ∨ q) → (p ∧ q), p → ¬ p.
The semantics of a formula is obtained by defining a function v, called an assignment, that maps the set of atomic propositions into {T, F } (or {true, false}). Given an assignment, it can be inductively extended to an interpretation of a formula (which we will also denote by v) using the following rules:
A | v(A1) | v(A2) | v(A) |
|---|---|---|---|
¬ A1 | T | F | |
¬ A1 | F | T | |
A1 ∨ A2 | F | F | F |
A1 ∨ A2 | otherwise | T | |
A1 ∧ A2 | T | T | T |
A1 ∧ A2 | otherwise | F | |
A1 → A2 | T | F | F |
A1 → A2 | otherwise | T | |
A1 ↔ A2 | v(A1) = v(A2) | T | |
A1 ↔ A2 | v(A1) ≠ v(A2) | F | |
A formula f is said to be true in an interpretation v if v (f) = T and false if v(f) = F. Under the assignment v (p) = T, v (q) = F, the formula p → (q → p) is true, as can be seen by inductively checking the interpretation using the above table: v(q → p) = T since v(q) = F and v(p) = T, from which it follows that v(p → (q → p)) = T. On the other hand, the formula (p ∨ q) → (p ∧ q) is false in the same interpretation, since v(p ∨ q) = T and v(p ∧ q) = F, which is precisely the one case in which the implication is false.
A formula f is satisfiable if it is true in some interpretation, and it is valid if it is true in all interpretations. Similar definitions can be given in terms of falsehood: A formula f is unsatisfiable if it is false in all interpretations, and it is falsifiable if it is false in some interpretation. The two sets of definitions are dual: f is satisfiable if and only if ¬ f is falsifiable, and f is valid if and only if ¬ f is unsatisfiable. It is easy to show that a formula is satisfiable or falsifiable since you only have to come up with one interpretation in which the formula is true or false, respectively; it is difficult to show that a formula is valid or unsatisfiable since you have to check all interpretations.
We have already shown that (p ∨ q) → (p ∧ q) is not valid (falsifiable) by finding an assignment in which it is false. We leave it to the reader to check that p → (q → p) is valid, while (p ∨ q) → (p ∧ q), though not valid, is satisfiable.
Two formulas are logically equivalent to each other if their values are the same under all interpretations. Logical equivalence is important, because logically equivalent formulas can be substituted for one another. This is often done implicitly, just as we replace the arithmetic expression 1 + 3 by the expression 2 + 2 without explicit justification.
The two formulas p → q and ¬ p ∨ q are logically equivalent because they are both false in any interpretation in which v(p) = T, v(q) = F, and are both true under all other interpretations. Other important equivalences are deMorgan’s laws: ¬ (p ∧ q) is logically equivalent to ¬ p ∨ ¬ q and ¬(p ∨ q) is logically equivalent to ¬ p ∧ ¬ q. For a more complete list, see [9, Section 2.4].
The concept of proof by numerical induction should be familiar from mathematics. Suppose that we want to prove that a formula F (n) containing a variable n is true for all possible values of n in the non-negative integers. There are two steps to the proof:
Prove F (0). This is called the base case.
Assume that F (m) is true for all m ≤ n and prove F (n + 1). This is called the inductive step and the assumption F (m) for m ≤ n is called the inductive hypothesis.
If these are proved, we can conclude that F (n) is true for all values of n. This form of induction is called generalized induction, because we assume F (m) for all numbers m less than n + 1 and not just for n.
Let us use generalized induction to prove the formula F (n): if n is a positive even number, then it is the sum of two odd numbers:
We need to prove two base cases: F (1) is trivially true because 1 is not even, and F (2) is true because 2 = 1 + 1.
Let us assume the inductive hypothesis F (m) for m ≤ n and prove F (n + 1). The proof is divided into two cases:
n + 1 is odd. In this case, the proof is trivial because the antecedent is false.
n + 1 is even and n + 1 > 2. But n − 1 is also even and n − 1 ≥ 2, so by the inductive hypothesis, there are two odd numbers 2i + 1 and 2j + 1 such that n − 1 = (2i + 1) + (2j + 1). A bit of arithmetic gives us:
n + 1 = (n − 1) + 2 = (2i + 1) + (2j + 1) + 2 = (2i + 1) + (2(j + 1) + 1),
showing that n + 1 is also the sum of two odd numbers.
Computational induction is used to prove programs; the induction is on the states of a computation rather than on natural numbers, but the concept is similar because the states are also arranged in an increasing sequence.
Frequently, we will want to prove invariants, which are formulas that are valid in every state of a computation. These will be proved using induction on the computation: the base case is to show that the formula is true in the initial step; the inductive step is to show that if the formula is assumed to be true in a state, it remains true in any successor state.
f is valid if and only if ¬ f is unsatisfiable, so in order to show that f is valid, search for an interpretation that satisfies ¬ f. If you find one, f is falsifiable, that is, it is not valid; if not, ¬ f is unsatisfiable, so f is valid. In mathematical logic, this dual approach is used in important techniques for proving validity: semantic tableaux, analytic tableaux and resolution.
The advantage of this method is that the search can be systematic and efficient, so that it can be mechanized by a computer program. Software systems called model checkers combine a (concurrent) program together with the negation of a logical formula expressing a correctness property, and then search for a satisfying scenario. If one is found, the correctness property does not hold, and the scenario produced by the model checker is a falsifying interpretation. If an exhaustive search turns up no such scenario, the program is correct.
The more classical approach to showing that a formula is valid is to prove it. We assume that certain formulas, called axioms, are valid, and that certain rules can be used to infer new true formulas from existing ones. A proof is a sequence of formulas, each one of which is either an axiom, or a formula that can be inferred from previous formulas using a rule. A formula has been proved if it is the last formula in a proof sequence. For a proof system to be useful it must be sound and preferably complete: a proof system is sound if every formula it proves is valid and it is complete if every valid formula can be proved. There is an axiom system for propositional LTL that is sound and complete (see [9, Section 12.2]).
Many correctness properties can be expressed as implications p → q. An examination of the table on page 322 shows that the only way that p → q can be false is if v(p) = T and v(q) = F. This is somewhat counterintuitive, because it means, for example, that the formula
(1 + 1 = 3) → (1 + 1 = 2)
is true. This definition, called material implication, is the one that is used in mathematics.
Suppose that p → q is true in a state and that we want to prove that it remains true in any successor state. We need only concern ourselves with: (a) states in which v(p) = v(q) = T, but “suddenly” in the next state v(q) becomes false while v(p) remains true, and (b) states in which v(p) = v(q) = F, but “suddenly” in the next state v(p) becomes true while v(q) remains false. If we can show that neither of these situations can occur, the inductive step has been proved.[1]
If the correctness claim is an implication of the form “the computation is at statement p3 implies that flag = 1,” the entire verification is reduced to two claims:
(a) any statement of process p leading to the control pointer pointing to p3 cannot be taken if flag = 1 is false or if the statement leads to a state in which flag = 1 becomes or remains true, and (b) if the control pointer of process p is at statement p3, then no other process can falsify flag = 1.
Psychologists have investigated the difficulties of reasoning with material implication using Wason selection tasks. Suppose that the following four cards are placed before you:
On one side of each card is written the current location of the computation (denoted p3 if the control pointer is at statement p3 and similarly for p5), and on the other side the value of flag. What is the smallest set of cards that you need to turn over to check that they all describe true instances of the claim “if the computation is at statement p3, then flag = 1”? The answer is that you need to turn over the first card (to ensure that the true antecedent is associated with a true consequent on the other side of the card) and the fourth card (to ensure that the false consequent is associated with a false antecedent on the other side of the card). If the antecedent is false (the second card), it doesn’t matter what the consequent is, and if the consequent is true (the third card), it doesn’t matter what the antecedent is.
Let us assume that a program P contains only one read statement as its first statement, and one write statement as its last statement:
read(x1,x2,. . . ,xM), . . . , write(y1,y2,. . . ,yN).
There are two definitions of correctness of P. Informally, they are:
Partial correctness. If P halts, the answer is “correct.”
Total correctness. P does halt and with the answer is “correct.”
These concepts can be formalized mathematically. We use the notation 
and 
to denote sequences of (mathematical) variables that contain the values of the (program) variables (x1,x2,. . . ,xM) and (y1,y2,. . . ,yN), and similarly for sequences of values ā and 
. Let 
be a logical formula with free variables called the precondition, and 
be a logical formula with free variables , called the postcondition.
Program P is partially correct with respect to 
and 
if and only if for all values of ā:
if A (ā) is true,
and ā are the input values read into
(x1,x2,. . . ,xM),and
Pterminates writing out the values(y1,y2,. . . ,yN),then
is true.
Total correctness
Program P is totally correct with respect to and if and only if for all values of ā:
if
and ā are the input values read into
(x1,x2,. . . ,xM),then
Pterminates writing out the values(y1,y2,. . . ,yN),and
Consider the following program, and take a few minutes to try to understand what the program does before reading on:
The program is partially correct with respect to A (x1 , x2) defined as true and B(x1 , x2 , y1 , y2) defined as
(x1 = x2 · y1 + y2) ∧ (0 ≤ y2 < x2).
The program computes the result and the remainder of dividing the integer x1 by the integer x2. It does this by counting down from x1 in the variable y3, adding one to the remainder y2 on each execution of the loop body. When the remainder would become equal to the divisor x2, it is zeroed out and the result y1 is incremented.
It is true that if zero or a negative number is read into x2, then the program will not terminate, but termination is not required for partial correctness; the only requirement is that if the program terminates, then the postcondition holds. On the other hand, the program is totally correct with respect to the precondition A (x1 , x2) defined as (x1 ≥ 0) ∧ (x2 > 0) and the same postcondition.
This emphasizes that it is always wrong to speak of a program as being correct. A program can only be correct with respect to its specification, here its pre- and postconditions.
The problem with the concepts of partial and total correctness is that they are appropriate only for programs that terminate. While there are concurrent programs that terminate (such as scientific simulations that use parallelism to compute the behavior of complex systems), most concurrent programs (such as operating systems and real-time controllers) are designed to be non-terminating. The term reactive is often used to emphasize that the program is designed to repeatedly react to external stimuli (such clicking a button on a mouse) or to repeatedly sample an external sensor. If one of these systems ever does terminate, we say that the computer has “crashed” and consider it a bug! A new definition of correctness is needed for concurrent programs.
Most of the proof of the algorithm for integer division can be mechanically carried out by SPARK [5]. Listing B.1 shows the algorithm written in the SPARK language, which is a subset of Ada augmented with annotations. (Some of the variable names have been changed for clarity.) The annotation derives, together with the mode declarations in and out of the parameters, is used for checking information flow. derives states that the values of Q and R that are returned from the procedure are obtained from the values of X1 and X2 that enter the procedure.
The proof annotations are the precondition pre that states that the dividend X1 is non-negative and that the divisor X2 is positive, and the postcondition post that states the relation among the variables required for the correctness of integer division. The assert annotation specifies what must be true upon entering the while loop, namely that the division relation hold as long as the value of N is added to Q*X2+R. Clearly, when leaving the loop, the value of N will be zero and the relation will hold among the variables that are the parameters of the procedure.
Example B.1. A SPARK program for integer division
1 −−# main_program; 2 procedure Divide(X1, X2: in Integer; Q, R: out Integer) 3 −−# derives Q, R from X1, X2; 4 −−# pre (X1 >=0) and (X2 >0); 5 −−# post (X1=Q*X2+R) and (X2 >R) and (R>=0); 6 is 7 N: Integer; 8 begin 9 Q := 0; R := 0; N := X1; 10 while N /= 0 11 −−# assert (X1=Q*X2+R+N) and (X2 >R) and (R>=0); 12 loop 13 if R+1 = X2 then 14 Q := Q + 1; R := 0; 15 else 16 R := R + 1; 17 end if; 18 N := N − 1; 19 end loop; 20 end Divide;
When SPARK is run, it verifies the information flow and then generates four verification conditions that must be proved in order to prove the partial correctness of the procedure. A verification condition is a formula that describes the execution of a program along a path in the program. The four conditions are:
From the precondition at the beginning of the procedure until the assertion:
(X1 ≥ 0) ∧ (X2 > 0) → (X1 = Q · X2 + R + N) ∧ (X2 > R) ∧ (R ≥ 0).
From the assertion until the postcondition at the end of the procedure (using the knowledge that the while loop terminates, so N = 0):
(X1 = Q · X2 + R + N) ∧ (X2 > R) ∧ (R ≥ 0) ∧ (N = 0) → (X1 = Q · X2 + R) ∧ (X2 > R) ∧ (R ≥ 0).
From the assertion, around the loop via the then branch, and back to the assertion (using the knowledge that the condition of the if statement is true):
(X1 = Q · X2 + R + N) ∧ (X2 > R) ∧ (R ≥ 0) ∧ (R + 1 = X2) → (X1 = Q′ · X2 + R′ + N′) ∧ (X2 > R′) ∧ (R′ ≥ 0).
The primed variables indicate denote the new values of the variables after executing the assignments in the loop body.
From the assertion, around the loop via the else branch, and back to the assertion (using the knowledge that the condition of the if statement is false):
(X1 = Q · X2 + R + N) ∧ (X2 > R) ∧ (R ≥ 0) ∧ (R + 1 ≠ X2) → (X1 = Q′ · X2 + R′ + N′) ∧ (X2 > R′) ∧ (R′ ≥ 0).
The simplifier tool of SPARK can reduce the first three formulas to true. It does this by substituting the expressions for the variables in the assignment statements, and then simplifying the formulas using elementary knowledge of arithmetic. For example, substituting the initial values into the first formula gives:
(X1 ≥ 0) ∧ (X2 > 0) → (X1 = 0 · X2 + X1) ∧ (X2 > 0) ∧ (0 ≥ 0).
It does not take much knowledge of arithmetic to conclude that the formula is true.
The condition that goes through the else branch cannot be proved by the simplifier. Substituting Q for Q′, R +1 for R′ and N −1 for N, the formula that must be proved is:
(X1 = Q · X2 + R + N) ∧ (X2 > R) ∧ (R ≥ 0) ∧ (R + 1 ≠ X2) → (X1 = Q · X2 + R + 1 + N − 1) ∧ (X2 > R + 1) ∧ (R + 1 ≥ 0).
The first subformulas on either side of the implication are equivalent, so this reduces to:
(X2 > R) ∧ (R ≥ 0) ∧ (R + 1 ≠ X2) → (X2 > R + 1) ∧ (R + 1 ≥ 0).
But this is easy for us to prove. By the properties of arithmetic, if X2 > R then X2 = R + k for k ≥ 1. From the antecedent we know that R + 1 ≠ X2, so k >1, proving that X2 > R + 1. Finally, from R ≥ 0, it is trivial that R + 1 ≥ 0.
Another component of SPARK, the proof checker, can be used to partially automate the proof of verification conditions such as this one that the simplifier cannot perform.
[1] It is also possible that v(p) = F and v(q) = T, but “suddenly” v(p) becomes true and v (q) becomes false.