(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
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.