As I mentioned, I'll be posting drafts of various sections of my book here on the blog. This is a rough draft of the introduction to a chapter on logic. I would be extremely greatful for comments, critiques, and corrections.
I'm a big science fiction fan. In fact, my whole family is pretty
much a gaggle of sci-fi geeks. When I was growing up, every
Saturday at 6pm was Star Trek time, when a local channel show
re-runs of the original series. When Saturday came around, we
always made sure we were home by 6, and we'd all gather in front of
the TV to watch Trek. But there's one one thing about Star Trek for
which I'll never forgive Gene Roddenberry or Star Trek:
"Logic". As in, Mr. Spock saying "But that would
not be logical.".
The reason that this bugs me so much is because it's taught a
huge number of people that "logical" means the same
thing as "reasonable". Almost every time I hear anyone
say that something is logical, they don't mean that it's logical -
in fact, they mean something almost exactly opposite - that it
seems correct based on intuition and common sense.
If you're being strict about the definition, then saying that
something is logical by itself is an almost meaningless
statement. Because what it means for some statement to be
logical is really that that statement is inferable
from a set of axioms in some formal reasoning system. If you don't
know what formal system, and you don't know what axioms, then the
statement that something is logical is absolutely meaningless. And
even if you do know what system and what axioms you're talking
about, the things that people often call "logical" are
not things that are actually inferable from the axioms.
Logic, in the sense that we generally talk about it, isn't
really one thing. Logic is a name for the general family of formal
proof systems with inference rules. There are many logics, and a
statement that is a valid inference (meaning that it is logical)
in one system may not be valid in another. To give you a very
simple example, think about a statement like "The house on the corner
is red". Most people would say that it's logical
that that statement is either true or false: after all, either the house
is red, or the house isn't red. In fact, most
people would agree that the statement "Either the house is red, or it
isn't red" must be true.
In the most common logic, called predicate
logic, that's absolutely correct. The original
statement is either true or false; the statement with an "or" in
it must be true. But in another common logic, called
intuitionistic logic, that's not
true. In intuitionistic logic, there are three possible truth
values: something can be true (which means that there is a proof
that it is true); something can be false (which means that there
is a proof that it is false); and something can be unknown so far
(which means that there's no proof either way).
In addition to having different ways of defining what's true
or provable, different logics can describe different things. Our
good old familiar predicate logic is awful at describing things
involving time - there's really no good particularly good way in
predicate logic to say "I'm always hungry at 6pm". But
there are other logics, called temporal
logics which are designed specifically for making
statements about time. We'll look at temporal logics later. For
now, we'll stick with simple familiar logics.
So What is Logic?
A logic is a formal symbolic system, which consists of:
- A set of atoms, which are the objects
that the logic can reason about.
- A set of rules describing how you can form statements
in the logic (the syntax of the logic).
- A system of inference rules
for mechanically discovering
new true statements using known true statements.
- A model which describes how the atoms and predicates
in the logic map onto a real, consistent set of objects and properties.
The key part of that definition is the
mechanical nature of inference. What logic does is
provide a completely mechanical system for determining the truth
or falsehood of a statement given a set of known truths. In
logic, you don't need to know what something means in order to
determine if it's true!. As long as the logic has a
valid model, you don't need to know what the model is to
be able to do valid reasoning in that logic.
The easiest way to get a sense of how that can possibly work
is to use an example. We'll start with one simple logic, and show
how it can be used in a mechanical fashion to deduce true statements
- without knowing what those statements mean. For now, we won't even
really define the logic formally, but instead just rely on intuition.
Most arguments that we hear day to day are based informally on a logic
called predicate logic; to be more specific, they're
mostly first order predicate logic.
In predicate logic, we've got a collection of objects which we
can reason about, which we usually call
atoms. To say anything about objects, we use
predicates. Predicates are statements that assert some property
about on object, or some relationship between objects. For
example, if I had a pet dog named Joe, we could make statements
about him like
which would say "Joe is a dog.". Or we could form statements about
Likes("Joe", is a logical way of saying "Joe
We can also form general statements. For example, if Joe likes
all other dogs, we can say that in logic:
Dog(x) ⇒ Likes("Joe", x)
upside down "A" stands for "for all"; the statement
says "For all x, if x is a dog, then Joe likes x."
Where things get interesting is the inference rules. Inference
rules describe how to perform reasoning in the logic - which is another
way of saying that they describe how the logic can allow you to figure
out what's true or false, based on reasoning starting from an initial
set of given facts.
Inference rules are usually written as sequents,
which we'll get to in another section; for now, we'll
stick with informal descriptions.
The simplest inference rules allow you to just manipulate
simple statements. For example, if you know
A ∧ is true, then you know
Another group of inference rules combine similar
statements to derive new facts. For example, the most famous rule
of logic is called modus ponens: if you know
that the statement
P ⇒ Q is true,
and you also know that
P is true, then you
can infer that
Q must be true.
More interesting rules allow you to do things like work from
the general to the specific: if you know that
∀, and "A" is an atom, then you can
Yet other rules allow you to transform statements. For example,
if you know that
∃x : P(x), then
you can infer that
With the rules we've looked at so far, we can build an example of
what I meant by totally mechanical inference.
Let's suppose we have a bunch of atoms, "a",
"b", "c", ..., and two predicates, P
We know a few simple facts:
∀x, y, z: P(x,y) ∧ P(y,z)
What can we infer using this? Using a general-to-specific
inference, we can say
"b") ∧ P("a", "b")
⇒ Q("a", "c")
Then, we can combine
P("b", to infer
P("a", "b") ∧. (Remember, we're
being totally mechanical, so if we want to use the implication, we
need to exactly match its left-hand side, so we need to do an
inference to get the "and" statement.)
Finally, we can now use modus ponens to infer
have no idea what the atoms a, b, and c are; we have
no idea what the predicates P and Q mean. But we've been able to
infer true statements.
So what do the statements mean? That depends on the model. For a given set of symbolic statements, you can use more than one model - so long as each model is valid, the meanings of the inferences will be valid in all models assigned to the statements. (We'll talk more about models in section ...) In this case, we could use several different models; I'll show two examples:
- "a" could be 1, "b" could be 2,
and "c" could be 3, with P(x,y) meaning "x is
1 plus y", and Q(x,y) meaning "x is 2 plus y".
Then we would have used the fact that 2 is 1+1 and 3 is 1+2 to infer
that 3 is 2+1.,/p>
- "a" could be my father, Irving;
"b" could be me, and "c" could be my
son Aaron, with P(x,y) meaning "x is the father of
y" and Q(x,y) meaning "x is the grandfather of
y". Then we would have used the fact that Irving is my
father, and I am Aaron's father to infer that Irving is