AI - Lecture - First Order Logic or Predicate Logic

---

AI - Lecture - First Order Logic

Sources:

• Slides
• Chapter 8 from book: Artificial Intelligence A modern Approach 4ed.

---

Before reading this, recall the Wumpus World example and his rules because it will be often referenced there.

We have seen Propositional logic and

Limitations of propositional logic

Propositional logic is useful but it has important limitations

Limited expressive power:

• Atomic sentences are treated as indivisible symbols
• The internal structure of facts cannot be represented
• For example consider proprositional logic can represent: ManSocrates, MortalSocrates but not naturally Man(Socrates), Mortal(Socrates).

If for example i want to reason that Socrates is an individual and an human being, and since he is a human being and so mortal, i cannot use propositional logic in an efficient way, because i have to express every possible cases introducing so many symbols.

No variables or quantifiers

• It cannot express general rules as “All humans are mortal” without listing every individual separately

This is a problem of expressivity but also computational power, the more you introduce the more complex the algorithm becomes.

Lack of conciseness

• Many similar facts require many different propositional symbols
• Example: must all be represented separately.

These limitations motivate first-order logic.

From Propositional to Predicate logic

Propositional logic treats atomic sentences as indivisible symbols.

Predicate logic represents the internal structure of facts:

• Man(Socrates)
• Prime(5)
• Adjacent(Room1, Room2)

It introduces:

• objects e.g. Socrates, Room1
• predicates e.g. Man(x), Prime(x)
• relations e.g., Adjacent(x,y)
• functions e.g. FatherOf(x), Sum(x,y)
• quantifiers e.g. ,

This allows general statements such as: or

Predicate logic is more expressive and more concise than propositional logic.

---

Link to original

The most important benefit of predicate logic or propositional logic is that it can represent concisely much more.

Representation revised

Programming languages such like C, Java or Python are the larget known class of formal languages in common use. Data structures within programs can be used to represent facts i.e World[2,2] <- Pit is a natural way to assert that there is a pit in .

However programming language lack a general mechanism for deriving facts from other facts, since each update to a data structure is done by a domain-specific procedure whose details are derived by a programmer from their knowledge domain.

Another drawback is the lack of expressiveness required to directly handle partial information e.g. “There is pit in [2,2] OR [3,1]” or “If the wumpus is in [2,2] then he is not in [2,1]”.

Propositional logic is a declarative language because its semantics is based on a truth relation between sentences and possible worlds. It also has sufficient expressive power to deal with partial information, using disjunction and negation.

Propositional logic has a third property that is desirable in representation languages, namely, compositionality. In a compositional positional language, the meaning of a sentence is a function of the meaning of its parts. Example: the meaning of is related to the meaning of and .

However, propositional logic, as a factored representation, lacks the expressive power to concisely describe an environment with many objects.

For example, we were forced to write a separate rule about breezes and pits for each square, such as:

While in english it would be much more simple: “Squares adjacent to pits are breezy”.

Analogy

• Propositional logic resembles declarative programming languages
• First Order Logic resembles Object-oriented programming languages because of objects and their relationships

However in practice they are different things

Combining the best of formal and natural languages

When we look at the syntax of natural language, the most obvious elements are:

• noun phrases that refer to objects (e.g. squares, pits, wumpuses).
• verb, verb phrases, adjectives and adverbs refer to relations among objects (is breezy, is adjacent to, shoots)
• some of these relations are functions in which there is only one “value” for a given input.

Relations can be:

• unary or properties such as red, round, bous, prime and so on…
• n-ary such as brother of, bigger than, inside, part of and so on…

The language of first-order logic is built around objects and relations.

Ontological committment The primary difference between propositional and first-order logic lies in the ontological committment made by each language. While propositional logic assumes that each proposition symbol can be only true or false, first-order logic assumes more.

In first-order logic the world consists of objects with certain relations among them that do or do not hold.

Figure 8.1 shows ontological formal languages and their ontological and epistemological committmens:

The ontological committement is powerful in domains like the wumpus world where every proposition has clear boundaries i.e. a square either does or does not have a pit. However in other situations like real world, many propositions have vague boundaries like “Is Vienna a large city?” or “Is that person tall?” it depends on who you ask, so the answer may be “kind of”. For this problem a proposed solution is Fuzzy logic that makes ontological committment that propositions have a degree of truth between 0 and 1.

Epistological committment A logic can also be characterized by its epistemological commitments i.e. the possible states of knowledge that it allows with respect to each fact. In both propositional and first-order logic, a sentence represents a fact and the agent either believes the sentence to be true, believes it to be false, or has no opinion.

Systems using probability theory, on the other hand, can have any degree of belief, or subjective likelihood, ranging from 0 (total disbelief) to 1 (total belief). (See Bayesian Networks).

Syntax and Semantics of First-Order Logic

Recall from previous lecture that the models of a logical language are the formal structures that constitute the possible worlds under consideration. Each model links the vocabulary of the logical sentences to elements of the possible world, so that the truth of any sentence can be determined.

Domain and Basic syntactic elements

Models for first-order logic are much more interesting. We can talk of a domain of a model defined as the set of objects or domain elements it contains. The domain is required to be nonemtpy so each possible world must contain atleast one object.

The basic syntactic elements of first-order logic are the symbols that stand for objects, relations, and functions:

• constant symbols which stand for objects
• predicate symbols which stand for relations
• function symbols which stand for functions.

Every model must provide information required to determine if any given sentence is true or false. Thus, each model must also include in addition an interpretation that specify exactly which objects, relations and functions are referred to by the constant, predicate and function symbols.

Terms

A term is a logical expression that refers to an object. Constant symbols are terms, but it is not always convenient to have a distinct symbol to name every object. For example in english we might say “King John’s left leg” rather than giving a name to his leg. This is also what function symbols are for; we might use LeftLeg(John).

An example of function symbols build “on the fly” are the lambda functions in Python.

The formal semantics of terms is straightforward. Consider a term :

• the function symbol refers to some function in the model , while
• the argument refer to objects in the domain (call them ); and
• the term as a whole refers to the object that is the value of the function applied to domain.

Atomic Sentences and Complex Sentences

An atomic sentence is formed from a predicate symbol optionally followed by a parenthesized list of terms, such as:

• Brother(Richard, John)

This states that Richard the Lionheart is the brother of King John.

Atomic sentences can have complex terms as arguments: Married(Father(Richard), Mother(John)) states that Richard the Lionheart’s father is married to King John’s mother (again, under a suitable interpretation).

An atomic sentence is true in a given model if the relation referred to by the predicate symbol holds among the objects referred to by the arguments.

We can use logical connectives to construct more complex sentences, with the same syntax and semantics as in propositional calculus. For example:

or

Quantifiers

Quantifiers let us express properties of entire collections of objects rather than enumerating the objects by name.

Universal quantification

Universal quantification (for all): for example “All kings are person” can be simply expressed with this quantifier as: . The symbol x is called a variable in this context. A term without variables is called a ground term.

The sentence where is any logical sentence, says that is true for every object . More precisely is true if is true in all possible extended interpretation constructed from the interpretation given in the model, where each extended interpretation specifies a domain element to which x refers.

Consider the following model: We can extend the interpretation in five ways:

• Richard the Lionheart
• King John
• Richard’s left leg
• John’s left leg
• the crown

The universally quantified sentence is true in the original model if the sentence is true under each of the five extended interpretations.

Richard the Lionheart is a king Richard the Lionheart is a person. King John is a king King John is a person. Richard’s left leg is a king Richard’s left leg is a person. John’s left leg is a king John’s left leg is a person. The crown is a king the crown is a person.

In our model King John is the only king, so the second sentence assert that he is a person. However what about the others e.g. the crown?

In fact, the other four assertions are true in the model, but make no claim whatsoever about the personhood qualifications of legs, crowns, or indeed Richard. This is because none of these objects is a king.

Consider the truth table: The implication is true whenever its premise is false, regardless of the truth of the conclusion. For example, let the =the crown is a king, and crown is a person. Using only the truth table (false,false) we see that is true.

Thus, by asserting the universally quantified sentence, which is equivalent to asserting a whole list of individual implications, we end up asserting the conclusion of the rule just for those objects for which the premise is true and saying nothing at all about those objects for which the premise is false.

Thus, the truth-table definition of turns out to be perfect for writing general rules with universal quantifiers.

Common Mistake for quantifiers A common mistake is to use conjunction instead of implication. The sentence:

would be equivalent to asserting:

• Richard the Lionheart is a king Richard the Lionheart is a person,
• King John is a kingKing John is a person,
• Richard’s left leg is a king Richard’s left leg is a person,

and so on. Obviously, this does not capture what we want.

Existential quantification

Universal quantification makes statements about every object. Similarly, we can make a statement about some object without naming it, by using an existential quantifier. To say for example that King John has a crown on his head, we write:

is pronunces as “there exists an such that …” or “For some …”

Intuitively, the sentence is true for atleast one object . More precisely, is true in a given model if is true in at least one extended interpretation that assigns to a domain element.

That is, at least one of the following is true:

• Richard the Lionheart is a king Richard the Lionheart is a person.
• King John is a king King John is a person.
• Richard’s left leg is a king Richard’s left leg is a person.
• John’s left leg is a king John’s left leg is a person.
• The crown is a king the crown is a person.

The fifth assertion is true in the model, so the original existentially quantified sentence is true in the model. Notice that, by our definition, the sentence would also be true in a model in which King John was wearing two crowns.

As appears to be the natural connective to use with , then is the natural connective to use with . Also, using as the main connective with led to an overly strong statement, while using with usually leads to a very weak statement.

The following sentence:

on the surface might look like a reasonable rendition of our sentence, however applying the semantics we see that the sentence says that at least one of the following assertions is true:

• Richard the Lionheart is a crown Richard the Lionheart is on John’s head;
• King John is a crown King John is on John’s head;
• Richard’s left leg is a crown Richard’s left leg is on John’s head;

and so on.

As saw before in the truth table, an implication is true if it both premises and conclusion are true, or if its premise is false; so if Richard the Lionheart is not a crown, then the first assertion is true and the existential is satisfied.

So, an existentially quantified implication sentence is true whenever any object fails to satisfy the premise; hence such sentences really do not say much at all.

In general, propositions where “all” refers to all domain elements that satisfy some condition must be represented using an implication

Nested quantifiers

For example “Brothers are siblings” can be expressed as:

or equivalently

Mixtures are also possible for example, “Everybody love somebody”

The order of quantification is therefore very important:

• means that everyone has a particular property i.e. the property that they love someone
• says that someone in the world has a particular property that they love someone.

Connections between forall and exists

The two quantifiers are actually intimately connected with each other, through negation.

Asserting that everyone dislikes parsnips is the same as asserting there does not exist someone who likes them, and vice versa:

Or “Everyone likes ice cream” means no there is no one does not likes ice cream:

Since is a conjunction and is a disjunction it is no surprise that they obey De Morgan’s rules:

Equality

First-order logic includes one more way to make atomic sentences, other than using a predicate and terms as described earlier. We can use the equality symbol to signify that two terms refer to the same object. For example:

says that the object referred to by Father(John) and the object referred to by Henry are the same.

Because an interpretation fixes the referent of any term, determining the truth of an equality sentence is simply a matter of seeing that the referents of the two terms are the same object.

Database semantics

If we would like to express that “Richard has two brothers, John and Geoffrey”, we could write:

However, that wouldn’t capture completely the state of the affairs:

• This sentence is true only if Richard has 1 brother, so we need to add
• The sentence doesn’t rule out models in which Richard has many more brothers beside John and Geoffrey

Thus, the correct translation of “Richard’s brothers are John and Geoffrey” is as follows:

which is much more cumbersone.

Can we devise a semantics that allows a more straightforward logical sentence? One proposal that is very popular in database systems works as follows:

• unique-names assumption: assume that every constant symbol refer to a distinct object
• closed-world assumption: assume that atomic sentences not known to be true are in fact false
• domain closure: each model contains no more domain elements than those named by the constant symbols.

Under the resulting semantics, equation does indeed state that Richard has exactly two brothers, John and Geoffrey.

This is called database semantics, that is also used in logic programming systems.

Using First-Order Logic

In knowledge representation a domain is just some part of the world about which we wish to express some knowledge. For now we consider first-order knowledge bases and the TELL/ASK interface.

See Knowledge-based agents for more explanation on the TELL/ASK interface.

in first-order logic, when you use TELL to add information to a knowledge base, you are asserting a fact. For example we can assert that John is a king, Richard is a person, and all kings are personas:

So by ASKing a question, for example it will return true.

We define the function for getting the truth value of a variable i.e.

would yields a stream of answers.

In this case there will be two answers: and . Such an answer is called a substitution or binding list.

is usually reserved for knowledge bases consisting solely of Horn clauses, because in such knowledge bases every way of making the query true will bind the variables to specific values.

That is not the case with first-order logic; in a KB that has been told only that there is no single binding to that makes the query true, even though the query is in fact true.

The kinship domain

The first example we consider is the domain of family relationships, or kinship. This domain includes facts like “Elizabeth is the mother of Charles”.

The object in this domain are people. Unary predicates include Male and Female, among others. Kinship relations—parenthood, brotherhood, marriage, and so on—are represented by binary predicates: Parent, Sibling, Brother, Sister, Child, Daughter, Son, Spouse, Wife, Husband, Grandparent, Grandchild, Cousin, Aunt, and Uncle. We use functions for Mother and Father, because every person has exactly one of each of these, biologically.

We can go through each function and predicate, writing down what we know in terms of the other symbols. For example, one’s mother is one’s parent who is female:

Or for example one’s husband is one’s male spouse:

Each of these sentences can be viewed as an axiom of the kinship domain.

These can be seen also as definitions; they have the form:

The axioms define the Mother function and the Husband predicate in term of other predicates.

Our definitions “bottom out” at a basic set of predicates (Child, Female, etc.) in terms of which the others are ultimately defined.

Not all logical sentences about a domain are axioms. Some are theorems—that is, they are entailed by the axioms. For example, consider the assertion that siblinghood is symmetric:

It is a theorem that follows logically from the axiom that defines siblinghood.

If we ASK the knowledge base this sentence, it should return true.

• From a purely logical point of view the KB should not contains theorems since they do not increase the set of conclusions that follows from the knowledge bases.
• From a practical point of view, theorems are essential to reduce the computational cost of deriving new sentences.
  • Without them, a reasoning system has to start from first principles every time, rather like a physicist having to rederive the rules of calculus for every new problem.

Not all axioms are definitions, some provide more general information about certain predicates. Indeed, some predicates have no complete definition because we do not know enough to characterize them fully.

For example, there is no obvious definitive way to complete the sentence:

Fortunately, first-order logic allows us to make use of the Person predicate without completely defining it. Instead, we can write partial specifications of properties that every person has and properties that make something a person:

Axioms can also be “just plain facts,” such as Male(Jim) and Spouse(Jim,Laura).

If all goes well, the answers to these questions will then be theorems that follow from the axioms.

Recap: Definitions, Axioms and Theorems

• Definitions are rules that introduce a new predicate using existing ones. Note it does not add facts to KB but only gives meaning.
• Axioms are assumptions about the domain. Definitions depend on axioms, because once you expand a definition, you are left with axioms expressed only in primitive predicates.
• Theorems are sentences that become true because they are entailed by the axioms.

The wumpus world

Some propositional logic axioms for the wumpus world were given in this lecture.

The first order axioms in this section are much more concise, capturing in a natural way exactly what we want to say.

Recall that the wumpus agent receives a percept vector with five elements. The corresponding first-order sentence stored in the knowledge base must include both the percept and the time at which it occurred; otherwise, the agent will get confused about when it saw what.

We use integers for time steps. A typical percept sentence would be:

Here, Percept is a binary predicate, and Stench and so on are constants placed in a list.

The actions in the wumpus world can be represented by logical terms like , , , , , .

To determine which is best, the agent program executes the query:

which return a binding list such as . The agent program can then return Grab as the action to take.

The raw percept data implies certain facts about the current state. For example:

and so on. These rules exhibit a trivial form of the reasoning process called perception. (Computer Vision).

Simple “reflex” behavior can also be implemented by quantified implication sentences. For example, we have:

Given the percept and rules from the preceding paragraphs, this would yield the desired conclusion that is Grab is the right thing to do.

We represented agent input and output, now let’s represent the environment itself. Let us begin with objects. Obvious candidates are squares, pits, and the wumpus.

Squares can be adjacent, so we can define it as:

We can use a unary predicate that is true of squares containing pits instead of naming each square. Finally, since there is exactly one wumpus, a constant Wumpus is just as good as a unary predicate (and perhaps more dignified from the wumpus’s viewpoint).

The agent’s location changes over time, so we write to mean that the agent is at square at time .

We can fix the wumpus to a specific location forever with:

We can then say that objects can be at only one location at a time:

If the agent is at a square and perceives a breeze, then that square is breezy:

It is useful to know that a square is breezy because we know that the pits cannot move about.

Having discovered which places are not breezy and not smelly, the agent can deduce where the pits are (and where the wumpus is).

For the geographical layout of the world, first-order logic requires only one axiom:

Similarly, in first-order logic we can quantify over time, so we need just one successor-state axiom for each predicate, rather than a different copy for each time step. For example:

Knowledge Engineering in First-Order Logic

This section describes the general process of knowledge-base construction— a process called knowledge engineering.

A knowledge engineer is someone who investigates a particular domain, learns what concepts are important in that domain, and creates a formal representation of the objects and relations in the domain.

The approach we take is suitable for developing special-purpose knowledge bases whose domain is carefully circumscribed and whose range of queries is known in advance.

The knowledge engineering process

Knowledge engineering projects vary widely in content, scope, and difficulty, but all such projects include the following steps:

1. Identify the questions: the knowledge engineer must delineate the range of questions that the knowledge base will support and the kinds of facts that will be available for each specific problem instance. For example, does the wumpus knowledge base need to be able to choose actions, or is it required only to answer questions about the contents of the environment? Will the sensor facts include the current location? This step is analogous to the PEAS process for designing agents
2. Assemble relevant knowledge: the knowledge engineer might already be an expert in the domain, or might need to work with real experts to extract what they know, a process called knowledge acquisition. At this stage, the knowledge is not represented formally. The idea is to understand the scope of the knowledge base, as determined by the task, and to understand how the domain actually works. For real domains, the issue of relevance can be quite difficult—for example, a system for simulating VLSI designs might or might not need to take into account stray capacitances and skin effects.
3. Decide on a vocabulary of predicates, functions and constants: that is, translate the important domain-level concepts into logic-level names. For example, should pits be represented by objects or by a unary predicate on squares? Should the agent’s orientation be a function or a predicate? Should the wumpus’s location depend on time? Once the choices have been made, the result is a vocabulary that is known as the ontology of the domain. The ontology determines what kinds of things exist, but does not determine their specific properties and interrelationships.
4. Encode general knowledge about the domain. The knowledge engineer writes down the axioms for all the vocabulary terms. This pins down (to the extent possible) the meaning of the terms, enabling the expert to check the content. Often, this step reveals misconceptions or gaps in the vocabulary that must be fixed by returning to step 3 and iterating through the process.
5. Encode a description of the problem instance If the ontology is well thought out, this step is easy. It involves writing simple atomic sentences about instances of concepts that are already part of the ontology. For a logical agent, problem instances are supplied by the sensors, whereas a “disembodied” knowledge base is given sentences in the same way that traditional programs are given input data.
6. Pose queries to the inference procedure and get answers. We can let the inference procedure operate on the axioms and problem-specific facts to derive the facts we are interested in knowing. Thus, we avoid the need for writing an application-specific solution algorithm.
7. Debug and evaluate the knowledge base. More precisely, the answers will be correct for the knowledge base as written, assuming that the inference procedure is sound, but they will not be the ones that the user is expecting. For example, if an axiom is missing, some queries will not be answerable from the knowledge base. A considerable debugging process could ensue. Missing axioms or axioms that are too weak can be easily identified by noticing places where the chain of reasoning stops unexpectedly.

When you get to the point where there are no obvious errors in your knowledge base, it is tempting to declare success. But unless there are obviously no errors, it is better to formally evaluate your system by running it on a test suite of queries and measuring how many you get right. Without objective measurement, it is too easy to convince yourself that the job is done.