Information Technology Reference
In-Depth Information
Mathematical induction is not just for arithmetic. Consider a blocks-world setup of
colored blocks. Suppose there is a stack of red and green blocks with a red one on the
top and a green one on the bottom. Does this mean that there is a red block
directly
on
top of a green one? It can be proved that there must be, by mathematical induction:
Let
S
(
n
)
be the following statement:
If the top block is red and the bottom one is green and there are
n
interme-
diate blocks in between, then there is a red block directly on top of a green
one.
Then prove by mathematical induction that
S
(
)
is true for all
n
.
n
1.
Consider the case where
n
0. The top block of the stack is directly on the
bottom block, and so a red block is directly on a green block. So
S
=
(
)
is true.
0
2.
Prove that if
S
(
n
)
is true, then
S
(
n
+
)
is also true. Assume that for some arbi-
1
trary
n
,
S
blocks between the top
red and bottom green blocks. Consider the block just below the top one. There
are two cases for it:
a.
(
n
)
is true. Suppose there is a stack with
(
n
+
)
1
If that block is green, then there is a red block (namely, the top one) directly
on this green one.
b.
If that block is red, then there is a smaller stack, with this red block on the
top and the green one on the bottom. There are only
n
blocks between this
red one and the bottom one. Since
S
is assumed to be true, there must be
a red block directly on a green one in this smaller stack.
(
n
)
(
+
)
is true.
The connection between this style of reasoning and writing Prolog clauses for
the
above
predicate is this. The clauses must work properly no matter how many
intermediate blocks there are. Now let
S
Either way, there must be a red block directly on a green one, so
S
n
1
(
n
)
be the following statement:
The
predicate
above
(
x
,
y
)
will
work
correctly
when
x
is
above
y
with
n
intermediate blocks between them.
(
)
If it can be proved that
S
is true for all
n
, then the Prolog program for
above
will
work no matter how many blocks there are between the top and bottom ones. To get
there, write clauses for the
above
predicate that duplicate a proof by mathematical
induction:
1.
n
Write clauses to ensure that
S
(
)
is true.
0
