First Order Logic (FOL)
AIMA 8
CMPSC 442
Week 6, Meeting 17, Three Segments
Outline
● Desirable properties of First Order Logic (FOL)
● Syntax and Semantics of FOL
● Using FOL
2Outline, Wk 6, Mtg 17
First Order Logic (FOL)
AIMA 8
CMPSC 442
Week 6, Meeting 17, Segment 1 of 3: Desirable Properties of
FOL
Pros of Propositional Logic
In contrast to database languages or programming languages, PL is
☺ Declarative rather than procedural
☺ Supports partial information: disjunction, negation
☺ Compositional
○ Meaning of a complex statement is a function of the meanings of the parts
(atomic statements, operators)
☺ Meaning is context-independent
○ Contrasts with natural languages, where meaning is context dependent
4Properties of FOL
Cons of PL
☹ Meaning is context-independent
○ Contrasts with natural languages, where many expressions are context
dependent
○ PL cannot express much of the meaning natural languages convey
☹ Limitations on the expressivity of propositional logic:
○ Cannot state generic truths, only specific ones
■ Specific truth (fact): B
1,1
⇔ (P
1,2
∨ P
2,1
)
■ Generic truth: Squares adjacent to pits are breezy
5Properties of FOL
One View of Language and Cognition
● Sapir-Whorf hypothesis (1940s/1950s): the categories of a particular
language shape the perceptions of its speakers
○ We dissect nature along lines laid down by our native languages. The
categories and types that we isolate from the world of phenomena we do
not find there because they stare every observer in the face (Whorf,
Science and Linguistics, 1940)
6Properties of FOL
Another View of Language and Cognition
● Eleanor Rosch’s basic categories (1978): the categories humans utilize
derive from biological and informational constraints:
○ The perceived world comes as structured information rather than as
arbitrary or unpredictable attributes. Thus maximum information with least
cognitive effort is achieved if categories map the perceived world
structure as closely as possible.
7Properties of FOL
Logic versus Natural Language
● To express information is one of the functions of natural language
○ A logical formalism is a language to express truth-conditional meaning
■ More rigorous (rule-governed, consistent) than natural language
■ Most words have many meanings (semantic ambiguity)
○ Most sentences have multiple syntactic analyses (syntactic ambiguity)
○ Can characterize reasoning (inference) of various forms
● Language has many other functions besides to convey information
(which can be true of false)
○ Word choices can be a reflection of what group one identifies with
○ Saying one has an emotion is information, but the emotion itself is not
information (cannot evaluate the truth conditions of “sadness”)
8Properties of FOL
PL versus FOL Expressivity
A Logical Formalism Can be a Tool to Investigate Information in Language
● Propositional logic (PL) assumes the world contains statements
○ Atomic terms standing for statements
○ Operators to combine with atomic statements
● First-order logic (FOL) assumes the world contains
○ Objects: people, houses, numbers, colors, baseball games, . . .
○ Relations: red, round, prime, brother of, bigger than, part of, . . .
○ Functions: father of, best friend, one more than, plus, . . .
○ Quantification: all wumpuses smell bad, some squares are breezy
○ Statements about objects, relations, functions and their quantification
9Properties of FOL
Comparison of Various Logics
● Non-exhaustive list of logical languages and their ontological versus epistemological
commitments
10Properties of FOL
Correspondence of FOL and Natural Language
● FOL expressivity is closer than PL to natural language
○ Objects denote real-world entities, which can be referred to with noun phrases
○ Logical relations correspond to real-world relations, which can be expressed as
adjectives and verbs
● FOL statements are context independent and unambiguous, while natural
language phrases are context-dependent and ambiguous
○ Two FOL statements can have different forms and the identical semantic
interpretation
○ Natural language statements and meanings are many-to-many
○ Natural language meaning is broader than a way to encapsulate “knowledge”
(opinions/attitudes/social conventions/bias . . .)
11Properties of FOL
First Order Logic (FOL)
AIMA 8
CMPSC 442
Week 6, Meeting 17, Segment 2 of 3: Syntax and Semantics
of FOL
FOL Vocabulary
● Constants: Richard, John, 2, . . .
● Connectives: ¬ ∧∨⇒⇔
● Variables x, y, a, b,…
● Predicates: True/1, False/1, Person/1, >/2, give/3, sell/4. . .
○ Person(John)
○ KingOf(John, a)
● Equality (a special predicate)
● Functions: Sqrt, LeftLegOf, . . .
● Quantifiers: ∀, ∃
13Syntax and Semantics of FOL
FOL Expressions
● Terms
○ Constant
○ Variable
○ Function(Term, . . .)
● Atomic sentences
○ Predicate
○ Predicate(Term, . . .)
○ Term = Term
● Complex sentences
○ Atomic sentences combined with logical connectives
○ Sentences with quantification
14Syntax and Semantics of FOL
FOL Syntax in Backus Naur Form
15Syntax and Semantics of FOL
Truth in FOL
● Sentences are true with respect to a model and an interpretation
(grounding)
● A model contains objects (domain entities) and relations among them
● Interpretation specifies referents for
○ constant symbols → objects
○ predicate symbols → relations
○ function symbols → functional relations
● An atomic sentence (predicate(term1,…,termn)) is true iff the objects
referred to by term1,…,termn are in the relation referred to by predicate()
16Syntax and Semantics of FOL
Models for FOL
● Five objects
● Three unary relations (for
properties of objects)
○ Person
○ King
○ Crown
● Two binary relations
○ Brother
○ On_head
● One unary function
○ Left_leg
17Syntax and Semantics of FOL
Interpretations of FOL Sentences: Truth Evaluation
● Logical forms
○ Constants: Richard, John
○ Predicate: Brother(arg1, arg2)
○ Atomic sentence: Brother(Richard, John)
● Interpretations
○ Richard I (the Lionheart), b. 1157, d. 1199, King of England 1189-1199
○ John, b. 1166, d. 1216, King of England 1199-1216
○ Binary symmetric familial relation of brotherhood (at least one parent in common)
● Truth: True iff the model contains the objects Richard and John, and they are
related by brotherhood
18Syntax and Semantics of FOL
Universal Quantification
● ∀
● EG: Everyone in CMPSC 442 is smart – ∀x In(x, CMPSC 442) ⇒ Smart(x)
● ∀x P(x) is true in a model m iff P is true with x instantiated to each
object in the model
○ 5 individuals: Amy, Barry, Connie, David, Ellen
○ The universal quantification given above is equivalent to the conjunction:
In(Amy,CMPSC 442) ⇒ Smart(Amy))
∧ In(Barry,CMPSC 442) ⇒ Smart(Barry))
∧ In(Connie,CMPSC 442) ⇒ Smart(Connie))
∧ In(David,CMPSC 442) ⇒ Smart(David))
∧ In(Ellen,CMPSC 442) ⇒ Smart(Ellen))
19Syntax and Semantics of FOL
Existential Quantification
● ∃
● EG: Someone in CMPSC 442 is smart – ∃x In(x, CMPSC 442) ∧ Smart(x)
● ∃x P(x) is true in a model m iff P is true with x instantiated to at least
one object in the model
○ Given 5 individuals: Amy, Barry, Connie, David, Ellen
○ The existential quantification is equivalent to the disjunction:
(In(Amy,CMPSC 442) ∧ Smart(Amy))
∨ (In(Barry,CMPSC 442) ∧ Smart(Barry))
∨ (In(Connie,CMPSC 442) ∧ Smart(Connie))
∨ (In(David,CMPSC 442) ∧ Smart(David))
∨ (In(Ellen,CMPSC 442) ∧ Smart(Ellen))
20Syntax and Semantics of FOL
Tips about Quantifiers
● Typically, the connective in a universally quantified sentence is ⇒
○ Everyone in CMPSC 442 is smart: ∀x In(x, CMPSC 442) ⇒ Smart(x)
○ In contrast:
∀x In(x, CMPSC 442) ∧ Smart(x) means: Everyone is in CMPSC 442 and
everyone is smart
● Typically, the connective in an existentially quantified sentence is ∧
○ Someone in CMPSC 442 is smart: ∃x In(x, CMPSC 442) ∧ Smart(x)
○ In contrast:
∃x In(x, CMPSC 442) ⇒Smart(x) means: Anyone taking CMPSC 442 is
smart (possibly no one)
21Syntax and Semantics of FOL
Equality
● term
1
= term
2
is true under a given interpretation if and only if term
1
and
term
2
refer to the same object
● For example, the Sibling() predicate can be “defined” using the Parent()
predicate and inequality constraints
∀ x,y Sibling(x,y) ⇔ [¬ (x = y) ∧ ∃ m,f ¬(m = f) ∧ Parent(m,x) ∧
Parent(f,x) ∧ Parent(m,y) ∧ Parent(f,y)]
22Syntax and Semantics of FOL
Models in FOL
● Possible models for a fragment of FOL with two constant
symbols (R, J) and one binary relation
23Syntax and Semantics of FOL
Database Semantics
● DB semantics for a fragment of FOL with two constants (R, J), one binary
relation
○ Unique-names assumption: every constant refers to a distinct object (R ≠ J)
○ Closed world assumption: an atomic sentence not known to be true is false
○ Domain closure: bijective relation of domain elements to constant symbols
24Syntax and Semantics of FOL
First Order Logic (FOL)
AIMA 8
CMPSC 442
Week 6, Meeting 17, Segment 3 of 3: Using FOL
Assertions and Queries
● FOL statements (assertions) can be added to a KB
○ Same as in PL
○ TELL(KB, Brother(Richard,John))
● Two types of queries can be made
○ ASK(KB, saturated statement) returns true or false, depending on truth
evaluation of statement (must not have unbound variables)
○ ASKVARS(KB, unsaturated statement) returns bindings for the unbound
variables ∀, ∃
■ AskVars(KB, ∀x evil(x))
■ AskVars(KB, ∃x evil(x))
26Using FOL
Axioms versus Theorems
● Axioms (introduced in Chapter 7): Foundational statements taken as
given
● Theorems: entailed by the axioms
27Using FOL
The Kinship Domain
● Axioms (or definitions):
○ Brothers are siblings
∀x,y Brother(x,y) ⇔ Sibling(x,y)
○ Brother is symmetric
∀x,y Brother(x,y) ⇔ Brother(y,x)
● Theorems
○ Sibling is symmetric
∀x,y Sibling(x,y) ⇔ Sibling(y,x)
28Using FOL
The Peano Axioms: Defining the Natural Numbers
● Abbreviated version of the Peano Axioms (showing 6 of 9)
● Guiseppe Peano, 19th Century
29Using FOL
Scope of Peano Axioms
Define multiplication as repeated addition
Define exponentiation as repeated multiplication
Define division similarly
All of Number Theory is defined from:
● One constant (zero)
● One function (Successor)
● One predicate (+)
● Nine axioms
30Using FOL
FOL, the Wumpus World, and Time
● Time steps in percept sentences:
○ Percept([Stench, Breeze, Glitter, None, None]), 5)
● Actions: Turn(Right), Turn(Left), Forward, Shoot
● Choosing actions at a time (e.g., 5):
○ Query: AskVars(KB, ∃a BestAction(a, 5))
○ Response is a binding list: {a/Grab}
● Inferences: with time
● Reflex behavior: with time
31Using FOL
FOL, the Wumpus World, and Space
● The Environment
○ Represent each square as a pair of indices, e.g., [1, 2] and define
adjacency:
○ Represent location, e.g., of Agent, with At(Agent, s, t), and constrain all
objects to be at only one location at one time
32Using FOL
Interacting with a FOL KB
● Given a sentence S and a substitution σ
○ Sσ denotes the result of plugging σ into S
■ S = Spouses(x,y)
■ σ = {x/Michelle, y/Barack}
■ Sσ = Spouses(Michelle, Barack)
○ AskVars(KB, S) returns all σ such that KB ⊨ σ
33Using FOL
Querying the Wumpus World FOL KB
● Suppose a Wumpus-world agent is using an FOL KB and perceives a
smell and a breeze (but no glitter) at t = 5:
○ Tell(KB, Percept([Smell, Breeze, None, None,None],5))
● Does KB entail an action a at time t = 5
○ AskVars(KB, ∃a Action(a, 5))
{a/Shoot}
34Using FOL
Knowledge Engineering using FOL
1. Identify the task
2. Assemble the relevant knowledge
3. Decide on a vocabulary of predicates, functions, and constants
4. Encode general knowledge about the domain
5. Encode a description of the specific problem instance
6. Pose queries to the inference procedure and get answers
7. Debug the knowledge base
35Using FOL
Application: Simulate Electronic Circuit
● Task: Design one-bit full adder
● Simulate the circuit: confirm whether it adds properly
○ All that matters in the design are the connections between terminals
36Using FOL
Assemble the Relevant Knowledge: Gates
● Two AND gates
● One OR gate
● Two XOR gates
37Using FOL
Choose the Vocabulary for Connectivity, Signal Status
● Represent the gates by asserting the Gate() predicate of an object, and specify
its type: Gate(X
1
), Type(X
1
)=XOR
● Represent circuits and terminals similarly: Circuit(C
1
), Terminal(X
1
)
● Represent input and output terminals: In(1,X
1
), Out(1,X
1
)
● Constrain the number of input and output terminals of each circuit: Arity(c,i,j)
○ EG: ∀x, Gate(x)∧(Type(x)=AND)→Arity(x,2,1)
● Represent connectivity between pairs of gates: Connected(Out(1,X
1
),In(1,X
2
))
● Use a 2-valued function to indicate whether a signal is on or off: Signal(t) = x,
where x ∈ [0, 1]
38Using FOL
Encode Circuit Domain Knowledge (Axioms)
39Using FOL
Encode a Given Circuit Instance
40Using FOL
● Categorize the circuit and its gates:
● Describe the connections among gates:
Simulate: Pose Queries and Get Answers
41Using FOL
Summary, Page One
● Knowledge representation for a rational agent:
○ Declarative
○ Compositional
○ Expressive
○ Context-independent
○ Unambiguous
● Formal logics: differ in ontological and epistemological commitments
● First-order logic:
○ Builds on propositional logic
○ Objects and relations are semantic primitives
○ Syntax: constants, functions, predicates, equality, quantifiers
42Summary, Wk 6, Mtg 17 – 1
Summary, Page Two
● Model (possible world) for FOL:
○ A set of objects and relations among objects
○ An interpretation that maps:
■ Constants to objects
■ Predicates to relations among objects
■ Function symbols to functions on objects that return other objects
● Increased expressive power: sufficient to define Wumpus world, circuit boards
○ Early AI systems used FOL
○ Logic programming (restricted FOL) used for language interpretation, and
knowledge representation
43Summary, Wk 6, Mtg 17 – 2