Exercise 8.LetCbe the program computing the greatest common divisor ofaandbof Exercise 7. Prove the following partial correctness formula:

We adopt the notation of Exercise 7 concerning the labelling of

C.

Solution.We present the proof in the Hoare partial correctness calculus, in linear style. As loop invariant we choose the formula .

Exercise 9.LetCbe the program of Exercise 4. Construct a proof for the partial correctness formula

We make use of the labels defined for

Cin Exercise 4. Again, we give the proof in a linear form, for invariant we choose the formula .

C = Z:=1;

while do

if odd(Y) then

Y:=Y-1; Z:=Z* X

else

Y:= Y div 2; X:=X* X

fi

od

We introduce the following labels.

We prove the partial correctness assertion by giving a correct proof outline for it. We introduce , as invariant.

Solution.

Z:=1;

while do

if odd(Y) then

Y:=Y-1;

Z:=Z* X

else

Y:= Y div 2;

X:=X*X

fi

od

Additionally, in order to ensure that we obtained a correct proof outline, we need to prove the relations

where, as usual, denotes the fact that the sets of states represented by

Pis a subset of the states whereQhold. All the above relations are trivial arithmetical facts.

Exercise 11.Let the base set of the underlying interpretation be words over an alphabet . LetC = Y:=;

Z:=X;

while do

Y=f(Z)Y;

Z:=t(Z)

od,

where is the head, is the tail of a non-empty word

X, otherwise both of them are the empty word. Let denote the reverse ofw. We construct a correct proof outline for the partial correctness assertion . For this purpose, we use the invariant .

Solution.

Y:=;

Z:=X;

while do

Y=f(Z)Y;

Z:=t(Z)

od

In order to complete the proof, we have to prove the implications

but they are trivially valid.

C = Y:=;

Z:=X;

while do

if f(Z)=f(t(Z))

then Y=Yf(Z)

else

Y=Yf(Z)f(Z)

fi

Z:=t(Z)

od

Prove the correctness of the formula , where is obtained from

wby incrementing by one the lengths of the character sequences consisting of the same character. For example, let , then . We apply as loop invariant the formula .

Solution.

Y:=;

Z:=X;

while do

if f(Z)=f(t(Z))

then Y=Yf(Z)

else

Y=Yf(Z)f(Z)

fi

Z:=t(Z)

od

To complete the proof we must prove the following implications:

Among these implications the first and the last one are trivial, though the precise verification of the second and third one would need a proof by induction on the lengths of the words involved. In such cases, we omit the rigorous proofs of the statements formulated in the interpretation, we just rely on our intuition to estimate whether a certain assertion in the

C = Y:=;

Z:=X;

while do

if f(Y)=f(Z)

then Z=t(Z)

else

Y=Yf(Z)

fi

od

Prove the correctness of the formula , where is obtained from

wby substituting every sequence of identical elements by one specimen of that element. For example, let , then . The reverse operator is defined as before. We apply as loop invariant the formula .

Solution.

Y:=;

Z:=X;

while do

if f(Y)=f(Z) then

Z=t(Z)

else

Y=Yf(Z)

fi

od

The proof becomes complete if we check the validity of the implications below:

C = X:=1;

Y:=n;

while do

X:=X*Y;

Y:=Y-2

od

Prove the correctness of the formula , where

Solution.We give a proof in derivation tree form now. We choose as invariant. We construct the tree step by step, proceeding from the simpler to the more compound one. First of all, we prove , where is the body of the while loop.

Let denote the above proof tree. Then

is what we required. Applying the while rule, we acquire the proof tree that follows

If denotes the proof tree obtained as above and stands for the proof tree below

then

is the proof tree searched for. The reader may have the impression that presenting a proof in a deduction tree form might be impose a more exhaustive task on the person constructing the proof than a proof in linear style. It seems indeed that this is the case, that’s why we prefer proofs written in linear style or in the form of a proof outline. In what follows, proofs will be presented in linear form proofs or as proof outlines in most of the cases.

C = Y:=0;

while do

Y:=Y+1

od;

Y:=Y-1

Prove , where denotes the greatest integer not greater than

rfor a non-negative real numberr.

Solution.We present the proof of the partial correctness assertion in the form of a proof outline, providing at the same time a detailed verification of the validity of the proof outline. Let us choose as loop invariant. Our first aim is to support with a valid proof outline the assertion .

Let

be labels for

C, let us denote the proof outlines corresponding to the formula by for some formulasP,Qand commandW. Thus, let stand for the proof outline obtained as the last row of the above derivation. Then we have

Denoting the last proof outline as , we acquire

which is what was desired.

Solution.We prove the partial correctness formula by presenting a valid proof outline for it. Let us choose as loop invariant. Let

be labels for

C.

Let denote the proof outline obtained in the final line of the derivation tree. Then we have

and

where and . Finally, since yields , which is equivalent to , we have

which completes the proof.

C = X:=2;

Y:=1

while do

if Xn then

Y:=Y+1

else

skip

fi

X:=X+1

od;

Prove the validity of , where is the number of the divisors of

n.

Solution.We present a valid proof outline for the demonstration of the partial correctness formula. Let denote the number of divisors ofnless thanm, that is,

We choose as an invariant for the while loop.

X:=2;

Y:=1

while do

if Xn then

Y:=Y+1

else

skip

fi

X:=X+1

od;

To complete the proof, it remains to justify the implications as follows.

All of the above relations represent straightforward arithmetical facts.

Exercise 18.Finding loop invariants is the non-trivial part of proving partial correctness. The next example illustrates a situation like this, where the loop invariant might need a little ingenuity to find. LetC = X:=n;

P:=2;

Y:=0;

while do

if PX then

X:=X div P;

Y:=Y+1

else

P:=P+1

fi

od

Prove the validity of , where denotes the integer division of

abyb, and is the number of the prime divisors ofnwith multiplicity.

Solution.We have to find a suitable invariant reflecting precisely the operation of the while loop. Let , where should denote the least proper divisor ofm. Observe that is always prime. Then we can construct the following proof outline

X:=n;

P:=2;

Y:=0;

while do

if PX then

X:=X div P;

Y:=Y+1

else

P:=P+1

fi

od

Again, to complete the proof we have to check the validity of the implications below.

They are all straightforward arithmetical relations with the possible exception of the second and third ones, the justifications of which relies on the fact of

Pbeing the minimal proper divisor ofn, which is just the minimal prime divisor ofn. Hence, , if , and , if . All the other relations follow easily.