Intelligent Systems
Predicate Logic
Outline

Motivation

Technical Solution

Syntax

Semantics

Inference

Illustration by Larger Example

Extensions

Summary

References
MOTIVATION
Propositional logic is not expressive enough

Suppose we want to capture the knowledge that
Anyone standing in the rain will get wet.
and then use this knowledge. For example, suppose we also learn that
Jan is standing in the rain.

We'd like to conclude that Jan will get wet. But each of these sentences would just be a represented by some proposition, say P, Q and R . What relationship is there between these propositions? We can say
P /\ Q → R
Then, given P /\ Q , we could indeed conclude R . But now, suppose we were told
Pat is standing in the rain.
Propositional logic is not expressive enough (cont’)

We'd like to be able to conclude that Pat will get wet, but nothing we have stated so far will help us do this

The problem is that we aren't able to represent any of the details of these propositions

It's the internal structure of these propositions that make the reasoning valid.

But in propositional calculus we don't have anything else to talk about besides propositions!
⇒ A more expressive logic is needed
⇒ Predicate logic (occasionally referred to as Firstorder logic (FOL) )
TECHNICAL SOLUTIONS
SYNTAX
Objects in Predicate Logic

Constants

Names of specific objects

E.g. doreen, gord, william, 32

Functions

Map objects to objects

E.g. father(doreen), age(gord), max(23,44)

Variables

For statements about unidentified objects or general statements

E.g. x, y, z, …
Terms

Terms represent objects

The set of terms is inductively defined by the following rules:

Constants: Any constant is a term

Variables: Any variable is a term

Functions: Any expression f(t1,…,tn) of n arguments (where each argument is a term and f is a function of arity n ) is a term

Terms without variables are called ground terms

Examples:

c

f(c)

g(x,x)

g(f(c), g(x,x))
Predicate Symbols and Signatures

Predicate symbols represent relations between zero or more objects

The number of objects define a predicate‘s aritiy

Examples:

Likes(george, kate)

Likes(x,x)

Likes(joe, kate, susy)

Friends (father_of(david), father_of(andrew))

Signature: A signature is a collection of constants, function symbols and predicate symbols with specified arities
Connectives

FOL formulas are joined together by logical operators to form more complex formulas (just like in propositional logic)

The basic logical operators are the same as in propositional logic as well:

Negation: ¬p („it is not the case that p“)

Conjunction: p ∧ q („p and q“)

Disjunction: p ∨ q („p or q“)

Implication: p → q („p implies q“ or “q if p“)

Equivalence: p ↔ q („p if and only if q“)
Quantifiers

Two quantifiers: Universal (∀) and Existential (∃)

Allow us to express properties of collections of objects instead of enumerating objects by name

Apply to sentence containing variable

Universal ∀: true for all substitutions for the variable

“for all”: ∀

Existential ∃: true for at least one substitution for the variable

“there exists”: ∃

Examples:

∃ x: Mother(art) = x

∀ x ∀ y: Mother(x) = Mother(y) → Sibling(x,y)

∃ y ∃ x: Mother(y) = x
Formulas

The set of formulas is inductively defined by the following rules:

Preciate symbols : If P is an nary predicate symbol and t1,…,tn are terms then P(t1,…,tn) is a formula.

Negation : If φ is a formula, then ¬φ is a formula

Binary connectives : If φ and ψ are formulas, then (φ → ψ) is a formula. Same for other binary logical connectives.

Quantifiers : If φ is a formula and x is a variable, then ∀xφ and ∃xφ are formulas.

Atomic formulas are formulas obtained only using the first rule

Example: If f is a unary function symbol, P a unary predicate symbol, and Q a ternary predicate symbol, then the following is a formula:
∀x∀y(P(f(x)) → ¬(P(x)) → Q(f(y), x, x)))

Formulas

Any occurrence a variable in a formulate not in the scope of a quantifier is said to be a free occurrence

Otherwise it is called a bound occurrence

Thus, if x is a free variable in φ it is bound in ∀xφ and ∃xφ

A formula with no free variables is called a closed formula

Example: x and y are bound variables, z is a free variable
∀x∀y(P(f(x)) → ¬(P(x)) → Q(f(y), x, z)))
BNF for FOL Sentences

S := <sentence>

<sentence> := <atomicsentence>
 <sentence> <connective> <sentence>
 <quantifier> <variable> ,... <sentence>
 ¬ <sentence>
 ( <sentence> )

<atomicsentence> := <predicate> ( <term> , ... )

<term> := <function> ( <term> , ... )
 <constant>
 <variable>

<connective> := ∧  v  →  ↔

<quantifier> := ∃  ∀

<constant> := “c"  “x1"  “john"  ...

<variable> := "a"  "x"  "s"  ...

<predicate> := “before"  “hasColor"  “raining"  ...

<function> := “mother"  “leftLegOf"  ...
TECHNICAL SOLUTIONS
Semantics
Semantics

Interpretations

Models and Satisfiability

Logical Consequence (Entailment)
Semantics – Overview

Interpretation – Maps symbols of the formal language (predicates, functions, variables, constants) onto objects, relations, and functions of the “world” (formally: Domain, relational Structure, or Universe)

Valuation – Assigns domain objects to variables

The Valuation function can be used for describing value assignments and constraints in case of nested quantifiers.

The Valuation function otherwise determines the satisfaction of a formula only in case of open formulae.

Constructive Semantics – Determines the semantics of complex expressions inductively, starting with basic expressions
Interpretation
Domain, relational Structure, Universe
D finite set of Objects d ^{ 1}, d ^{ 2}, ... , d ^{ n }
R,... Relations over D R ⊆ D ^{ n }
F,... Functions over D F: D ^{ n } → D
Basic Interpretation Mapping
constant I [c] = d Object
function I [f] = F Function
predicate I [P] = R Relation
Valuation V
variable V(x) = d ∈ D
Next, determine the semantics for complex terms and formulae constructively, based on the basic interpretation mapping and the valuation function above.
Interpretation (cont’)
Terms with variables
I [f(t_{1},...,t_{n})) = I [f] (I [t_{1}],..., I [t_{n}]) = F(I [t_{1}],..., I [t_{n}]) ∈D
where I[t_{i}] = V(t_{i}) if t_{i} is a variable
Atomic Formula
I [P(t_{1},...,t_{n})] true if (I [t_{1}],..., I [t_{n}]) ∈ I [P] = R
Negated Formula
I [¬α] true if I [α] is not true
Complex Formula
I[α∨β] true if I [α] or I [β] true
I [α∧β] true if I [α] and I [β] true
I [α→β] if I [α] not true or I [β] true
Interpretation (cont’)
Quantified Formula (relative to Valuation function)
I [∃x:α]  true if α is true with V’(x)=d for some d∈D where V’ is otherwise identical to the prior V. 
I [∀x:α]  true if α is true with V’(x)=d for all d∈D and where V’ is otherwise identical to the prior V. 
Note: ∀x∃y: α is different from ∃y∀x: α
In the first case ∀x∃y:α , we go through all value assignments V'(x), and for each value assignment V'(x) of x, we have to find a suitable value V'(y) for y.
In the second case ∃y∀x:α, we have to find one value V'(y) for y, such that all value assignments V'(x) make α true.
Models and Satisfiability
Given is an interpretation I into a domain D with a valuation V, and a formula φ .
We say that:
φ is satisfied in this interpretation or
this interpretation is a model of φ iff
I[φ] is true.
That means the interpretation function I into the domain D (with valuation V) makes the formula φ true.
Logical Consequence (Entailment)
Given a set of formulae Φ and a formula α .
α is a logical consequence of Φ iff
α is true in every model in which Φ is true.
Notation:
Φ ⊧ α
That means that for every model (interpretation into a domain) in which Φ is true, α must also be true.
TECHNICAL SOLUTIONS
Inference
Entailment and Derivation

Entailment: KB ⊧ Q

Entailment is a relation that is concerned with the semantics of statements

Q is entailed by KB (a set of premises or assumptions) if and only if there is no logically possible world in which Q is false while all the premises in KB are true

Stated positively: Q is entailed by KB if and only if the conclusion is true in every possible world in which all the premises in KB are true

Provability: KB ⊢ Q

Provability is a syntactic relation

We can derive Q from KB if there is a proof consisting of a sequence of valid inference steps starting from the premises in KB and resulting in Q
Important Properties for Inference

Soundness: If KB ⊢ Q then KB ⊧ Q

If Q is derived from a set of sentences KB using a set of inference rules, then Q is entailed by KB

Hence, inference produces only real entailments, or any sentence that follows deductively from the premises is valid

Only sentences that logically follow will be derived

Completeness: If KB ⊧ Q then KB ⊢ Q

If Q is entailed by a set of sentences KB, then Q can also be derived from KB using the rules of inference

Hence, inference produces all entailments, or all valid senteces can be proved from the premises

All the sentences that logically follow can be derived
Inference rules for Predicate Logic

Inference rules for propositional logic apply to propositional logic as well

Modus Ponens, Modus tollens etc.

New (sound) inference rules for use with quantifiers:

Modus Ponens, Modus Tollens

Universal elimination

Existential elimination

Existential introduction

Generalized Modus Ponens (GMP)
Modus Ponens and Modus Tollens

Modus Ponens (Law of Detachment )

Based on claiming 1.) that P is true, and 2.) the implication P → Q , we can conclude that Q is true.

If P, then Q. P, therefore, Q

Example:
RegularlyAttends(joe, lecture),
RegularlyAttends(joe, lecture) → Pass(joe, lecture)
Allow us to conclude:
Pass(joe, lecture)
Modus Ponens and Modus Tollens

Modus Tollens (Denying the consequent)

We again make two claims. 1.) The implication P → Q, and 2.) that Q is false. We can conclude that P is false as well.

If P , then Q . ¬Q Therefore, ¬P

Example:

Detects(alarm, intruder) → GoesOff(alarm),

¬GoesOff(alarm)

Allows us to conclude:

¬Detects(alarm, intruder)
Universal and Existential elimination

Universal elimination

If ∀x P(x) is true, then P(c) is true, where c is any constant in the domain of x

Variable symbol can be replaced by any ground term

Example:

∀x RegularlyAttends(x, lecture) → Pass(x, lecture)

Allow us to conclude (assuming Joe is in the domain of x):

RegularlyAttends(joe, lecture) → Pass(joe, lecture)
Universal and Existential elimination

Existential elimination

From ∃x P(x) infer P(c)

Note that the variable is replaced by a brandnew constant not occurring in this or any other sentence in the KB

Also known as skolemization; constant is a skolem constant

In other words, we don’t want to accidentally draw other inferences by introducing the constant

Convenient to use this to reason about the unknown object, rather than constantly manipulating the existential quantifier

Example:

∃x Pass(x)

Allows us to conclude:

Pass(someStudent) , where someStudent is a new constant
Existential Introduction

If P(c) is true, then ∃x P(x) is inferred.

The inverse of existential elimination

All instances of the given constant symbol are replaced by the new variable symbol

Note that the variable symbol cannot already exist anywhere in the expression

Example:

Eats(Ziggy, IceCream)

∃x Eats(Ziggy,x)
Generalized Modus Ponens (GMP)

Apply modus ponens reasoning to generalized rules

Combines UniversalElimination, and Modus Ponens

E.g, from P(c) and Q(c) and ∀ x (P(x) ∧ Q(x)) → R(x) derive R(c)

GMP requires substitutions for variable symbols

subst(θ, α) denotes the result of applying a set of substitutions defined by θ to the sentence α

A substitution list θ = {v_{1}/t_{1}, v_{2}/t_{2}, ..., v_{n}/t_{n}} means to replace all occurrences of variable symbol v_{i} by term t_{i}

Substitutions are made in lefttoright order in the list

subst ({x/IceCream, y/Ziggy}, eats(y,x)) = eats (Ziggy, IceCream)
Generalized Modus Ponens (GMP)
 General definition: Given
 atomic sentences P_{1}, P_{2}, ..., P_{N}
 implication sentence (Q_{1} ∧ Q_{2} ∧ ... ∧ Q_{N}) → R
 Q_{1}, ..., Q_{N} and R are atomic sentences
 substitution subst(θ, P_{i}) = subst(θ, Q_{i}) for i=1,...,N
 Derive new sentence: subst( θ , R)
 GMP is usually written formally as following:
Generalized Modus Ponens (GMP)  Example
 A clause is a disjunction of literals
 Example: C_{1} ∨ … ∨ C_{n}
 A definite clause is a clause containing exactly one positive literal
 Example: ¬C_{1} ∨ … ∨ ¬C_{n} ∨ H
 GMP is used with a collection of definite clauses
 Example:

Person(John) , Rich(x), ( Person(x) ∧ Rich(x) → Popular(x))

Popular(John)

With the substitution θ = {x/John,y/John} , and

Rich θ = Popular θ
Completeness & Decidability (1)

Completeness : If a knowledgebase KB entails a statement S , we can prove S

Gödel Completeness Theorem : There exists a complete proof system for FOL

KB ⊨ Q ↔ KB ⊢ Q

Gödel proved that there exists a complete proof system for FOL.

Gödel did not come up with such a concrete proof system.

Robinson’s Completeness Theorem : Resolution is such a concrete complete proof system for FOL
Completeness & Decidability (2)

FOL is only semidecidable : If a conclusion follows from premises, then a complete proof system (like resolution) will find a proof.

If there’s a proof, we’ll halt with it (eventually)

However, If there is no proof (i.e. a statement does not follow from a set of premises), the attempt to prove it may never halt

From a practical point of view this is problematic

We cannot distinguish between the nonexistence of a proof or the failure of an implementation to simply find a proof in reasonable time.

Theoretical completeness of an inference procedure does not make a difference in this cases

Does a proof simply take too long or will the computation never halt anyway?
ILLUSTRATION BY LARGER EXAMPLE
Knowledge engineering in FOL

Consider the following english text:
“Anyone passing his Intelligent System exam and winning the lottery is happy. But any student who studies for an exam or is lucky can pass all his exams. John did not study but John is lucky. Anyone who is lucky wins the lottery. Mary did not win the lottery, however Mary passed her IS exam. Gary won the lottery. Gary, John, and Mary are all students.„
 Is John happy?
 Is Mary happy? Is she lucky?
 Did every student pass the IS exam?
Formalization in FOL

Identify the task

Knowledge to be captured, questions to be answered


Assemble the relevant knowledge

Relavant: Relation between exams, lottery jackpots, passing of an exam information about individuals, etc.

Irrelevant: Dates of exams, teacher of the exam, amount of money in the lottery pot, etc


Decide on a vocabulary

Predicates

Constants symbols

E.g. Win(x, Lottery) or Win(x, y) ∧ Lottery(y)?

Formalization in FOL (cont’)

Encode general knowledge of the domain

Anyone passing the IS exams and winning the lottery is happy
∀x Pass(x, IS) ∧ Win(x, Lottery) ⇒ Happy(x)

Any student who studies or is lucky can pass all his exams
∀x ∀y Student(x) ∧ Exam(y) ∧ (StudiesFor(x, y) ∨ Lucky(x)) ⇒ Pass(x,y)

Anyone who is lucky wins the lottery
∀x Lucky(x) ⇒ Win(x, Lottery)

Formalization in FOL (cont’)

Encode the specific problem instance

John did not study, but John is lucky
¬Study(John) ∧ Lucky(John)

Mary did not win the lottery, however Mary passed her IS exam ¬ Win(Mary, Lottery)
Pass(Mary,IS)

Gary won the lottery
Win(Gary, Lottery)

Gary, John, and Mary are all students
Student(Gary), Student(John), Student(Mary)

Formalization in FOL (cont’)
6. Pose queries to the inference procedure
 Is John happy?
 Is Mary happy? Is she lucky?
 Did every student pass the IS exam?

Specific inference procedures (e.g. Resolution ) can be used to systematically answer those queries (see next lecture)
Happy(John) ?
Happy(Mary), Lucky(Mary)?
∃x Student(x) ∧ Pass(x, IS) ?
EXTENSIONS
Extensions

Ordinary firstorder interpretations have a single domain of discourse over which all quantifiers range; manysorted firstorder logic allows variables to have different sorts , which have different domains

The characteristic feature of firstorder logic is that individuals can be quantified, but not predicates; secondorder logic extends firstorder logic by adding the latter type of quantification
Extensions (cont’)

Intuitionistic firstorder logic uses intuitionistic rather than classical propositional calculus; for example, ¬¬φ need not be equivalent to φ

Infinitary logic allows infinitely long sentences; for example, one may allow a conjunction or disjunction of infinitely many formulas, or quantification over infinitely many variables

Firstorder modal logic has extra modal operators with meanings which can be characterised informally as, for example "it is necessary that φ" and "it is possible that φ“
SUMMARY
Summary

Predicate logic differentiates from propositional logic by its use of quantifiers

Each interpretation of predicate logic includes a domain of discourse over which the quantifiers range.

There are many deductive systems for predicate logic that are sound (only deriving correct results) and complete (able to derive any logically valid implication)

The logical consequence relation in predicate logic is only semidecidable

This lecture focused on three core aspects of the predicate logic: Syntax, Semantics, and Inference
REFERENCES
References

Mandatory Reading:

M. Fitting: FirstOrder Logic and Automated Theorem Proving, 1996 SpringerVerlag New York (Chapter 5)

Further Reading:

Michael Huth and Mark Ryan, Logic in Computer Science(second edition) , 2004, Cambridge University Press

http://plato.stanford.edu/entries/modeltheory/

Wikipedia links:

http://en.wikipedia.org/wiki/Firstorder_logic
Questions?