3 of 15

Models in First-Order Logic

Objects / Terms:

R
J
crown
LeftLeg(R)
LeftLeg(J)

Relationships / Predicates:

Brother(R, J)
Brother(J, R)
OnHead(J, crown)

Person(R)
Person(J)
King(J)
Crown(crown)

4 of 15

Graph Representation of a Model

If you only have unary and binary predicates, a model m can be represented as a directed graph

Nodes are terms, labeled with constant symbols

Green labels

Directed edges are binary predicates, labeled with predicate symbols

Red labels next to edges

Unary predicates are additional node labels

Red labels next to nodes

5 of 15

Models in First-Order Logic

Objects (Constant Symbols)

Set of objects in a model is called domain of the model
Each object in the domain is called domain element

Domain is required to be non-empty i.e.

Every model must contain at least one object

Relationships

Tuples of objects

Order of objects in the tuple is important, since relationships are often asymmetric

Functions are represented as unary tuples

6 of 15

Models in First-Order Logic

A model m in first-order logic maps constant symbols to objects

m(alice) = o₁

m(bob) = o₂

m(robert) = o₂

m(arithmetic) = o₃

and maps predicate symbols to tuples of objects

m(Knows) = {(o₁, o₃) , (o₂, o₃) , . . . }

m(Student) = {(o₁)}

Formally, a first-order model m maps constant symbols to objects and predicate symbols to tuples of objects

7 of 15

Models in First-Order Logic

In First-Order Logic (FOL), just as in propositional logic, entailment and validity etc. are defined in terms of all possible models

Models in FOL however, can vary in:

How many objects they may contain - from one to infinity

How constant symbols map to objects

For example, two constant symbols can refer to the same object, and there can be objects which no constant symbols refer to.

Therefore, the number of first-order models is unbounded

Even if number of objects is restricted the number of combinations can be extremely large

Figure 8.2 has 137,506,194,466 models

This means we cannot check entailment by enumerating all models

8 of 15

Database Semantics

Fortunately, there are two restrictions we can make make to simplify things.

Unique names assumption: Each object has at most one constant symbol.

Domain closure: Each object has at least one constant symbol.

Together, they imply that there is a one-to-one relationship between constant symbols in syntax-land and objects in semantics-land.

9 of 15

Database Semantics

John and Bob are students.

Student(john) ∧ Student(bob)

Unique name assumption: Each object has at most one constant symbol.

This rules out w2

Domain closure: Each object has at least one constant symbol.

This rules out w3

Constant symbol ⇄ Object

10 of 15

Propositionalization

Use any PL inference algorithm for FOL logic

We are back to propositional logic, and we know how to do inference in propositional logic: either using model checking or by applying inference rules.

Propositionalization could be quite expensive and not the most efficient thing to do.

Now we look at inference rules which can make first-order inference much more efficient.

The key is to do everything implicitly and avoid propositionalization.

11 of 15

Propositionalization

If one-to-one mapping between constant symbols and objects (unique names and domain closure), first-order logic is syntactic sugar for propositional logic

Basically unrolls all the quantifiers into explicit conjunctions and disjunctions.

Knowledge base in first-order logic:
Student(alice) ∧ Student(bob)
∀x Student(x) → Person(x)
∃x Student(x) ∧ Creative(x)

Knowledge base in propositional logic:
Studentalice ∧ Studentbob
(Studentalice → Personalice) ∧ (Studentbob → Personbob) ∧

(Studentalice ∧ Creativealice) ∨ (Studentbob ∧ Creativebob)

12 of 15

Horn Clauses in Propositional Logic

Horn clause: Disjunction of literals of which at most one is positive

All goal clauses are horn clauses
All definite clauses are horn clauses

Note that P→Q is a horn clause since it is equivalent to ¬ P ∨ Q
Two subtypes:

Goal clause: Disjunction of literals with no positive literals
Definite clause: Disjunction of literals of which exactly one is positive

Clause	Goal	Definite	Horn
¬ P ∨ ¬ Q ∨ ¬ R
¬ P ∨ ¬ Q ∨ R
P ∨ Q ∨ R

13 of 15

Inference in First-order Logic

We will first talk about first-order logic restricted to Horn clauses, in which case a first-order version of modus ponens will be sound and complete.

We start by generalizing definite clauses from propositional logic to first-order logic.

The only difference with PL is that we now have universal quantifiers sitting at the beginning of the definite clause.

This makes sense since universal quantification is associated with implication, and one can check that if one propositionalizes a first-order definite clause, one obtains a set (conjunction) of multiple propositional definite clauses.

After that, we’ll see how resolution allows to handle all of first-order logic.

14 of 15

Definite clauses in First-order Logic

A definite clause in first-order logic has the following form:

∀x₁···∀x_n(a₁ ∧···∧ a_k) → b

for variables x₁, ... , x_n and atomic sentences a₁, ..., a_k, b (which contain those variables).

For example:

∀x ∀y ∀z (Student(x) ∧ Course(y) ∧ Topic (z) ∧ Takes(x, y) ∧ Covers(y, z)) → Knows(x, z)

Note: if we propositionalize, we get one sentence for each value to (x, y, z), e.g.,

( Student(Alice) ∧ Course(343) ∧ Topic(FOL)

∧ Takes(Alice, csc343) ∧ Covers(csc343, FOL)) → Knows(Alice, FOL)

15 of 15

Modus Ponens (FOL)

∀x₁··· ∀ x_n(a₁ ∧···∧a_k) → b , a₁,..., a_k
b

Setup:

Given P (Alice) and ∀x P (x) → Q(x).

Problem:

Can’t infer Q(Alice) because P(x) and P(Alice) don’t match!

Solution:

Substitution and Unification