Information Technology Reference
In-Depth Information
=
1.
Write a clause to handle the
n
0
case. In the example, this means writing a
clause for the case where
x
is above
y
by virtue of being directly on
y
:
above(X,Y) :- on(X,Y).
2.
Write a clause to handle the
case, on the assumption that the
n
case is
already taken care of. In the example, this means writing a clause for
above
when there are
(
n
+
1
)
blocks between the top and bottom blocks, assuming that
above
already works properly when there are only
n
blocks between the top and
bottom blocks.
Suppose
x
is above
y
with
(
n
+
1
)
(
+
)
blocks between them. Then there must be a
z
such that
x
is directly on
z
, and
z
is above
y
, with
n
blocks between them. That
means that
above
(
n
1
)
will work properly. So the clause
above(X,Y) :- on(X,Z), above(Z,Y).
z
,
y
will work despite the fact that
above
occurs in both the head and the body.
This explains the two clauses that are used in the program in figure 4.2 . But why does
this two-step recipe work? The answer is
mathematical induction
. It is not necessary to
understand mathematical induction to write Prolog programs, but it does provide
justification for what is done.
∗
4.4 Mathematical induction
Mathematical induction is a technique for proving that something is true for all natu-
ral numbers, 0, 1, 2, . . .. The something to be proved is usually expressed as a statement
of English that contains a variable, say
n
, such as, “The sum of the natural numbers
up to
n
is equal to one half of
n
times
(
n
+
1
)
.” Let
S
(
n
)
denote this statement. So
S
is the English statement, “The sum of the natural numbers up to 3 is one half of 3
times 4.”
S
(
3
)
(
3
)
is true, since the sum of the natural numbers up to 3 is 6 (
0
+
1
+
2
+
3
),
(
)
and one half of 3 times 4 is also 6. Similarly, the statement
S
7
is true, since the sum
+
+
+
+
+
+
+
is 28 (
0
1
2
3
4
5
6
7
), and one half of 7 times 8 is also 28. What one
(
)
would like to do is to
prove
that
S
is true for every natural number
n
.
Mathematical induction works in the following way. To prove that for all
n
,
S
n
(
)
n
is
true, it is sufficient to do two things:
1.
Prove that
S
(
)
is true.
0
2.
Prove that for any natural number
n
,if
S
(
n
)
is true, then
S
(
n
+
)
is also true.
1
