## 1. IntroductionIn the preceding chapters, we have seen how Herbrand Logic can be used to define arithmetic over finite sets (e.g., modular arithmetic) and arithmetic over infinite sets (e.g., natural number arithmetic). In each case, we started by fixing a language for the arithmetic we wanted to define. For example, we used the object constants 0, 1, 2, 3 for modular arithmetic with modulus 4. Unfortunately, Herbrand Logic does not allow us to state properties of arithmetic without knowing precisely how many objects are involved. This is problematic when we want to formalize properties of functions or relations that hold across universes of different sizes. For example, we might want to state the fact that addition is commutative whether we're considering finite arithmetic, arithmetic over the natural numbers, or arithmetic over the real numbers. Unfortunately, without having a fixed universe defined by the language, the material we have seen so far does not give rigorous meaning to the sentences we write. In this chapter, we consider a different logic that avoids this apparent limitation by allowing the universe of objects to vary independently of the space of ground terms in our language. The resulting logic is called First-Order Logic. In this chapter, we start by introducing the idea of a language-independent space of objects. Then we define a semantics that gives meaning to sentences without fixing in advance the space of objects. We also discuss how the limitation of a fixed universe can be circumvented without leaving the framework of Herbrand Logic. ## 2. ConceptualizationAs we shall see, the semantics of First-Order Logic is based on the notion of a The notion of an Not all knowledge-representation tasks require that we consider all the objects in the world; in some cases, only those objects in a particular set are relevant. For example, number theorists usually are concerned with the properties of numbers and usually are not concerned with physical objects such as resistors and transistors. Electrical engineers usually are concerned with resistors and transistors and usually are not concerned with buildings and bridges. The set of objects about which knowledge is being expressed is often called a As an example, consider the Blocks World scene in Figure 1. Most people looking at this figure interpret it as a configuration of toy blocks. Some people conceptualize the table on which the blocks are resting as an object as well; but, for simplicity, we ignore it here. The universe of discourse corresponding to this conceptualization is the set consisting of the five blocks in the scene.
Although in this example there are finitely many elements in our universe of discourse, this need not always be the case. It is common in mathematics, for example, to consider the set of all integers or the set of all real numbers or the set of all An interrelationship among the objects in a universe of discourse is called a In a spatial conceptualization of the Blocks World, there are numerous meaningful relations. For example, it makes sense to think about the One way of giving meaning to these intuitive notions in the context of a specific conceptualization of the world is to list the combinations of objects in the universe of discourse that satisfy each relation in the relational basis set. For example, the
The
The
The generality of relations can be determined by comparing their elements. Thus, the Logic allows us to capture the contents of such tables; and, more importantly, it allows us to assert relationships between these tables. For example, it allows us to say that, if one block is One thing that our tabular representation for relations makes clear is that, for a finite universe of discourse, there is an upper bound on the number of possible n-tuples. Every n-ary relation is a subset of these b
tuples. Therefore, an ^{n}n-ary relation must be one of at most 2^(b) possible sets.^{n}A Mathematically, a function can be viewed as a set of tuples of objects, one for each combination of possible arguments paired with the corresponding value. In other words, an
In an analogous way, a binary function can be treated as a ternary relation; a ternary function can be treated as a 4-ary relation; and so forth. Although the tabular representation for functions and relations is intuitively satisfying, it consumes a lot of space. Therefore, in what follows, we use a different way of encoding relational tables, viz. as sets of tuples, each tuple representing a single row of the corresponding table. As an example, consider the a, b], [b, c], [d, e]}
Since functions are relations, we could use the same representation. However, to emphasize the special properties of functions, we use a slight variation, viz. the use of an arrow in each tuple to emphasize the fact that the last element is the value of the function applied to the element or elements before the arrow. Using this notation, we can rewrite the functional table shown earlier as the set shown below. a→b, b→a, c→d, d→c, e→e}
Finally, before we get on with the details of First-Order Logic, it is worthwhile to make a few remarks about conceptualization. No matter how we choose to conceptualize the world, it is important to realize that there are other conceptualizations as well. Furthermore, there need not be any correspondence between the objects, functions, and relations in one conceptualization and the objects, functions, and relations in another. In some cases, changing one's conceptualization of the world can make it impossible to express certain kinds of knowledge. A famous example of this is the controversy in the field of physics between the view of light as a wave phenomenon and the view of light in terms of particles. Each conceptualization allowed physicists to explain different aspects of the behavior of light, but neither alone sufficed. Not until the two views were merged in modern quantum physics were the discrepancies resolved. In other cases, changing one's conceptualization can make it more difficult to express knowledge, without necessarily making it impossible. A good example of this, once again in the field of physics, is changing one's frame of reference. Given Aristotle's geocentric view of the universe, astronomers had great difficulty explaining the motions of the moon and other planets. The data were explained (with epicycles, etc.) in the Aristotelian conceptualization, although the explanation was extremely cumbersome. The switch to a heliocentric view quickly led to a more perspicuous theory. This raises the question of what makes one conceptualization more appropriate than another for knowledge formalization. Currently, there is no comprehensive answer to this question. However, there are a few issues that are especially noteworthy. One such issue is the Finally, there is the issue of We can remedy this deficiency by Note that, in this discussion, no attention has been paid to the question of whether the objects in one's conceptualization of the world really exist. We have adopted neither the standpoint of ## 3. SemanticsAn n is mapped into an n-ary function on the universe of discourse. Each relation constant with arity n is mapped into an n-ary relation on the universe of discourse.As an example, consider a First-Order language with object constants As our universe of discourse, we take the set consisting of the numbers 1, 2, and 3. Admittedly, this is a very abstract universe of discourse. It is also very small. This has the advantage that we can write out examples in their entirety. Of course, in practical situations, universes of discourse are likely to be more concrete and much larger. The equations shown below define one interpretation of our language in terms of this universe of discourse. As we did with Propositional Logic, we are using
Note that more than one object constant can refer to the same object. In this case, both A
A
The Given an interpretation For example, given the interpretation and the variable assignment presented above, we have the truth assignments shown below. The relational sentence r(z,a) is false since [2, 1] is not in r.^{i}
The conditions for truth of logical sentences in First-Order Logic are analogous to those for the truth of logical sentences in Propositional Logic. A negation ¬φ is true if and only if φ is false. A conjunction (φ ∧ ψ) is true if and only if both φ and ψ are true. A disjunction (φ ∨ ψ) is true if and only if φ is true or ψ is true (or both). An implication is true unless the antecedent is true and the consequent is false. A reduction is true unless the antecedent is true and the consequent is false. An equivalence is true if and only if the truth values of the two embedded sentences are the same. Intuitively, a universally quantified sentence is satisfied if and only if the embedded sentence is satisfied for all values of the quantified variable. Intuitively, an existentially quantified sentence is satisfied if and only if the embedded sentence is satisfied for some values of the quantified variable. Sadly, expressing this intuition rigorously is a little tricky. First, we need the notion of a A Suppose, for example, we had the variable assignment
The version
With this notation, we can formalize the semantics of quantified sentences as follows. An interpretation An interpretation A sentence is An interpretation ## 4. Blocks WorldLet's revisit the Blocks World example from section 6.5. The typical Blocks World scene from chapter 6 is shown again in Figure 1.
As in section 6.4, we adopt a vocabulary with five object constants. a, b, c, d, e}
Also as in chapter 6, let's consider the following literals that states whether the
Here we illustrate one of the main differences between First-Order Logic and Herbrand Logic. Under Herbrand Logic, the set of five object constants fixes the universe of five objects. As a result, the above set of sentences completely defines the arrangement of blocks. That is, there is exactly one Herbrand Logic truth assignment over the language {a,b,c,d,e, on} that satisfies the above set of sentences. In contrast, under First-Order Logic, the set of five object constants are simply five names that refer to objects in a universe but do not constrain the universe in any way. As a result, under First-Order Logic, the set of sentences is satisfied by more than one interpretation. That is, the set of sentences accurately describes more than one arrangement of blocks and does not specify which one. Here we look at several examples of interpretations that satisfy the sentences Σ. An interpretation corresponding to arrangement shown in figure 1.
Same five objects. Some objects have more than one name. (o
Three objects.
Eight objects. Each of the three interpretations corresponds to a different world of blocks. But they all share a common feature; all three worlds have at least three blocks arranged in a stack. In fact, all the interpretations that satisfy Σ share this common feature. Below are several example interpretations which do not satisfy set of sentences Σ.
∀ This interpretation does not satisfy Σ because
∀ This interpretation does not satisfy Σ because ¬ ## 5. ArithmeticIn the introduction to this chapter, we mentioned as motivation the desire to write down properties satisfied by a class of arithmetic structures without first fixing the space of objects. Here we consider several properties of addition. We then examine some interpretations that satisfy the properties and some interpretations that do not. Consider the language with the object constant 0, the function constant
Below are some examples of interpretations that satisfy Γ.
Modular arithmetic with modulus 2
Modular arithmetic with modulus 4
Addition over the natural numbers
Nonstandard arithmetic over two objects, where 1+1=1 Below are some examples of interpretations that do not satisfy Γ.
∀
∀ ## 6. PropertiesAlthough the semantics of Herbrand Logic and First-Order Logic are different, many of the key concepts of the two logics are the analogous. Notably, the concepts of validity, contingency, unsatisfiability, and so forth have essentially the same definitions in First-Order Logic as in Herbrand Logic. A sentence is ## 7. Logical EntailmentA set of First-Order Logic sentences Δ As with validity and contingency and satisfiability, this definition is essentially the same for First-Order Logic as for Propositional Logic and Herbrand Logic. |