(This section is sure to be ugly in the ASCII version of this document. For a pretty .dvi or .ps presentation of the underlying .tex file, go through my web site.)

Given an ** alphabet**
(of ** variables** , ** constants** , **n**-ary
** relation symbols** , ** functors** ,
** quantifiers** , and the familiar ** truth-functional
connectives** () one uses
standard ** formation rules** (e.g., if and are well-formed
formulas, then is a wff as well) to build ``atomic"
formulas, and then more complicated ``molecular" formulas. Sets of these
formulas (say ), given certain ** rules of inference** (e.g., modus
ponens: from and infer to ), can
lead to individual formulas (say ); such a situation is expressed
by meta-expressions like . First-order logic, like
all ** logical systems**, includes a semantic side which systematically
provides meaning for formulas involved. In first-order logic, formulas
are said to be true (or false) on an ** interpretation**, often written
as . (This is often
read, `` satisfies, or models,
.") For example, the formula might mean,
on the standard interpretation
for arithmetic, that for every natural number
**n**, there is a natural number **m** such that **m > n**. In this case,
the domain of is ** N**, the natural numbers, and **G** is
the binary relation , i.e., **>** is
a set of ordered pairs where and **i** is
greater than **j**.

In order to concretize things a bit,
consider an expert system designed to play the role of a
guidance counselor in advising a high school student about which colleges
to apply to (I have such a system under development at Rensselaer). Suppose
that we want a rule in such a system which says ``If a student has
low SATs, and a low GPA, then none of the top twenty-five national universities
ought to be applied to by this student." Assume that we have
the following interpreted predicates: **Sx** iff **x** is a student,
for **x** has low SATs, for **x**
has a low GPA, **Tx** for **x** is a top twenty-five national university,
**Axy** for **x** ought to apply to **y**. Then the rule in question, in first-order
logic, becomes

Let's suppose, in addition, that Steve is a student denoted by the constant
**s** in the system, and that he, alas, has low SATs and a low GPA. Assume
also that **v** is a constant denoting Vanderbilt University (which happens
to be a top twenty-five national university according the U.S. News' annual
rankings). These facts are represented in the system
by

and

Let's label these three facts, in the order in which they were presented, (1), (2), and (3). Our expert system, based as it is on first-order logic, can verify

that is, it can deduce that Steve ought not to apply to Vanderbilt.

Tue Apr 2 13:34:44 EST 1996