Logic provides a way to talk about
truth and correctness in a rigourous way,so that we can prove things, rather than
make intelligent guesses and just hope they are correct.
The ancient Greeks loved to hang around on the
stoa ,
sip some wine, and debate.But at the end of the day, they wanted to sit back and
decide who had won the argument.When Socrates
claims that one statement
follows from another, is it actually so?Shouldn't there be some set of rules to officially determine
when an argument is correct?Thus began the formal study of logic.
The three fundamental studies were the
Trivium grammar (words), logic (reasoning), and rhetoric (effective communication).These allowed study of the
Quadrivium arithmetic (patterns in number),geometry (patterns in space),
music (patterns in tone), andastronomy (patterns in time).
All together, these subjects comprise
the seven liberal arts .
These issues are of course still with us today.
And while it might be difficult to codify real-worldarguments about (say) gun-control laws,
programs
can be
fully formalized, and correctness can be specified.We'll look at three examples where formal proofs are applicable:
playing a simple game, WaterWorld;
checking a program for type errors;
circuit verification.
Many other areas of computer science routinely involve proofs, although
we won't explore them here.Manufacturing robots first prove that they can twist and move to
where they need to go before doing so, in order to avoid crashing intowhat they're building.
When programming a collection of client and server computers,we usually want to prove that the manner in which they communicate guarantees
that no clients are always ignored.Optimizing compilers prove that, within your program, some faster piece of
code behaves the same as and can replace what you wrote.With software systems controlling more and more life-critical applications,
it's important to be able to
prove that a program always does what it claims.
Waterworld
Consider a game called WaterWorld, where each location is either
empty sea or contains a pirate.When you enter a location, you must
correctly anticipate whether or not it contains pirates.
If you correctly anticipate open sea, you are able to enter and
determine how many of the (up to 3) adjacent locations containa pirate.
If you correctly anticipate a pirate, the location
is tagged as dangerous, and you gather no further information.
Furthermore, there are really two types of moves:
guesses, and assertions.If you make an assertion, then even if you happen to be correct but
it is possible you could have been wrong, then it is an error.Also, it is an error if you make a guess about a location
if it is actually possible to assert a location's contents.The interesting fact about these types of games is that while
sometimes guesses are necessary (when?),surprisingly often an assertion can be made.
