Page 398 - Discrete Mathematics and Its Applications

Review Questions 377

Exercises

1. Prove that the program segment if x< 0 then
y := 1 y := −2|x|/x
else if x> 0 then
z := x + y
y := 2|x|/x
is correct with respect to the initial assertion x = 0 and
else if x = 0 then
the final assertion z = 1. y := 2
2. Verify that the program segment is correct with respect to the initial assertion T and the
if x< 0 then x := 0 final assertion y = 2.
7. Use a loop invariant to prove that the following program
is correct with respect to the initial assertion T and the
segment for computing the nth power, where n is a posi-
final assertion x ≥ 0.
tive integer, of a real number x is correct.
3. Verify that the program segment
power := 1
x := 2 i := 1
z := x + y while i ≤ n
if y> 0 then power := power ∗ x
z := z + 1 i := i + 1
else
∗ 8. Prove that the iterative program for finding f n given in
z := 0
Section 5.4 is correct.
is correct with respect to the initial assertion y = 3 and
9. Provide all the details in the proof of correctness given in
the final assertion z = 6.
Example 5.
4. Verify that the program segment
10. Suppose that both the conditional statement p 0 → p 1 and
if x< y then the program assertion p 1 {S}q are true. Show that p 0 {S}q
min := x also must be true.
else 11. Suppose that both the program assertion p{S}q 0 and
min := y the conditional statement q 0 → q 1 are true. Show that
is correct with respect to the initial assertion T and the p{S}q 1 also must be true.
final assertion (x ≤ y ∧ min = x) ∨ (x > y ∧ min = y). 12. This program computes quotients and remainders.
∗ 5. Devise a rule of inference for verification of partial cor- r := a
rectness of statements of the form q := 0
if condition 1 then while r ≥ d
S 1 r := r − d
else if condition 2 then q := q + 1
S 2 Verify that it is partially correct with respect to the ini-
. tial assertion “a and d are positive integers” and the final
.
. assertion “q and r are integers such that a = dq + r and
else
0 ≤ r< d.”
S n
13. Use a loop invariant to verify that the Euclidean algorithm
where S 1 ,S 2 ,...,S n are blocks.
(Algorithm 1 in Section 4.3) is partially correct with re-
6. Use the rule of inference developed in Exercise 5 to verify spect to the initial assertion “a and b are positive integers”
that the program and the final assertion “x = gcd(a, b).”
Key Terms and Results

TERMS the principle of mathematical induction: the statement
∀n P(n) is true if P(1) is true and ∀k[P(k) → P(k + 1)]
sequence: a function with domain that is a subset of the set of
integers is true.
basis step: the proof of P(1) in a proof by mathematical in-
2
geometricprogression: asequenceoftheform a,ar,ar ,..., duction of ∀nP (n)
where a and r are real numbers
inductive step: the proof of P(k) → P(k + 1) for all pos-
arithmetic progression: a sequence of the form a, a + d, itive integers k in a proof by mathematical induction of
a + 2d,..., where a and d are real numbers ∀nP (n)