Information Technology Reference
In-Depth Information
Although there are many different ways of looking at logic, the focus in this topic
is on logical entailment, which in turn depends on thinking about sentences as being
true or false. Before 1920 or so, it was typical to think of logic only in terms of
axioms
and
rules of inference
for moving in a correct way from premises to conclusions in argu-
ments or proofs. (This would be like studying the properties of back-chaining with no
mention of entailment.) Logicians at the time certainly had an intuitive understand-
ing of what it meant for a sentence to be true, and they felt confident that the rules
that they were using were correct (logically sound). But it was only in the late 1920s,
spurred by the mathematicians David Hilbert and Wilhelm Ackermann, that they
began to consider whether the rules they were using were really
sufficient
(logically
complete). In fact, before G odel proved his Incompleteness Theorem, he proved the
completeness of a certain set of axioms and rules of inference, as part of his doctoral
thesis.
Soon thereafter, the logician Alfred Tarski took on the topic of truth. He was the
first to present a mathematically rigorous definition of a sentence's being true accord-
ing to a precisely laid-out notion of
logical interpretation
. Logical entailment (or logical
consequence) could then be given a mathematical account: it held when a conclusion
was true in
all
interpretations where the premises were true. Tarski's work revolu-
tionized logic, and these days it is rare to see a textbook on symbolic logic that does
not present the two views of the subject: a syntactic side involving axioms and rules
of inference (sometimes called a
proof theory
), and a semantic side involving inter-
pretations and truth (sometimes called a
model theory
), with logical soundness and
completeness theorems relating the two.
The idea of restricting language to atomic and conditional sentences goes back
to the logician Alfred Horn, who, on a suggestion from Tarski, first examined the
properties of sentences like these in the early 1950s. They are usually called
Horn
clauses
in his honor, and I use them throughout the topic until chapter 11, when I
enlarge the representation language.
Exercises
Consider the knowledge base in figure 2.6 about the east-west subway stops in a
mythical city somewhere. Note that
left of
is used here to mean
directly
to the left of
(as it might appear on a subway map).
1.
Give an example of an atomic sentence that is not in the knowledge base in
figure 2.6 but that is entailed by it.
