Page 60 - Discrete Mathematics and Its Applications

1.4 Predicates and Quantifiers 39

EXAMPLE 4 Let A(c, n) denote the statement “Computer c is connected to network n,” where c is a variable
representing a computer and n is a variable representing a network. Suppose that the computer
MATH1 is connected to network CAMPUS2, but not to network CAMPUS1. What are the
values of A(MATH1, CAMPUS1) and A(MATH1, CAMPUS2)?

Solution: Because MATH1 is not connected to the CAMPUS1 network, we see that A(MATH1,
CAMPUS1) is false. However, because MATH1 is connected to the CAMPUS2 network, we
see that A(MATH1, CAMPUS2) is true. ▲

`
Similarly, we can let R(x, y, z) denote the statement ‘x + y = z.”When values are assigned
to the variables x, y, and z, this statement has a truth value.
EXAMPLE 5 What are the truth values of the propositions R(1, 2, 3) and R(0, 0, 1)?

Solution: The proposition R(1, 2, 3) is obtained by setting x = 1, y = 2, and z = 3inthe
statement R(x, y, z). We see that R(1, 2, 3) is the statement “1 + 2 = 3,” which is true. Also
note that R(0, 0, 1), which is the statement “0 + 0 = 1,” is false. ▲

In general, a statement involving the n variables x 1 ,x 2 ,...,x n can be denoted by

P(x 1 ,x 2 ,...,x n ).

A statement of the form P(x 1 ,x 2 ,...,x n ) is the value of the propositional function P at the
n-tuple (x 1 ,x 2 ,...,x n ), and P is also called an n-place predicate or a n-ary predicate.
Propositional functions occur in computer programs, as Example 6 demonstrates.
EXAMPLE 6 Consider the statement

if x> 0 then x := x + 1.

When this statement is encountered in a program, the value of the variable x at that point in the
execution of the program is inserted into P(x), which is “x> 0.” If P(x) is true for this value
of x, the assignment statement x := x + 1 is executed, so the value of x is increased by 1. If
P(x) is false for this value of x, the assignment statement is not executed, so the value of x is
not changed. ▲

PRECONDITIONS AND POSTCONDITIONS Predicates are also used to establish the
correctness of computer programs, that is, to show that computer programs always produce the
desired output when given valid input. (Note that unless the correctness of a computer program
is established, no amount of testing can show that it produces the desired output for all input
values, unless every input value is tested.) The statements that describe valid input are known
as preconditions and the conditions that the output should satisfy when the program has run
are known as postconditions. As Example 7 illustrates, we use predicates to describe both
preconditions and postconditions. We will study this process in greater detail in Section 5.5.

EXAMPLE 7 Consider the following program, designed to interchange the values of two variables x and y.

temp := x
x:=y
y := temp

Find predicates that we can use as the precondition and the postcondition to verify the correctness
of this program. Then explain how to use them to verify that for all valid input the program does
what is intended.