First-Order Logic

Drawbacks of Propositional Logic

 Propositional logic is very simple and declarative, in which

knowledge and inference are separate, and inference is
entirely domain independent
 Propositional logic has lack of data structure in
programming.
 Propositional logic is not sufficient for complex or natural
language sentences.
 E.g. Some students in XYZ are intelligent
 Propositional logic has very limited expressive power
 E.g., cannot say "pits cause breezes in adjacent squares"
except by writing one sentence for each square
 First-Order Logic

 First-order logic is also known as Predicate logic or

 First-order predicate logic.
 First-order logic, like natural language has well defined
syntax and semantics.
 It assumes the world contains
 Objects: people, houses, numbers, colors, baseball
games, wars,
 Relations: can be unary relations (properties) like red,
bogus, prime. OR n-ary relations like brother of, boss of,
owns
 Functions: father of, best friend, one more than, plus,
 Any assertion can be referring to objects, properties,
relations...
 Examples of these assertions:
 “eight times three equals twenty four”
Objects: three, eight, twenty-four, times
equals. Relation: equals. Function: times.
 “Climate change caused the 6th mass
extinction in 2010.
Objects: climate change, 2010, mass extinction.
Relation: began. Properties: 6th
 Properties of First-Order Logic
 first-order logic has ability to represent facts about some
or all of the objects and relations.
 Represent laws and rules extracted from real world.
 Useful to multiple disciplines because of this: AI,
philosophy, mathematics...
 The assumptions (ontological commitment) of reality of
propositional logic and first-order logic differentiates them.
 Expressed through the nature of the formal models
regarding defined truth sentences.
 Propositional logic assumes facts hold or do not hold in the
real world.
 They can be “true” or “false”.
 First-order logic adds relations that hold or do not hold.
 More complicated than propositional logic.
 Logics can be differentiated by the states of
knowledge allowed regarding each fact (it's
epistemological commitments)
 In propositional and first-order logics, a
sentence represents a fact the agent
believes to be true, false, or had no idea
about.
 Three possible states:
true/false/unknown.
 Systems using probability theory allow for
a degree of belief: 0 (total disbelief) to 1
(total belief).
 Example: there's a 75% change there is
an enemy behind that door.
 A summary of logics:

 Like a physics student needs to be

comfortable with math, an AI student needs
to be comfortable with using some kind of
logical notation.
Syntax and Semantics of First-Order Logic
 For reference, first-order logic syntax in BNF:
Atomic Sentences

 Now, we make atomic sentences that state facts.

 Atomic sentences (aka atom): formed from a
predicate symbol optionally followed by a list of terms.
Example:
Brother(Richard, John)
 States: Richard is brother of John.
Complex Sentences

 Logical connectives can help build more complicated

stuff, using propositional calculus.
 Example of true sentences under previous example
interpretation:
¬Brother(LeftLeg(Richard), John)
Brother(Richard, John) ∧ Brother(John, Richard)
King(Richard) ∨ King(John)
¬King(Richard) ⇒ King(John)
 First-order logic models have:
 objects
 the domain of the model are it's set of
objects
 Must be non-empty
 The set of objects are aka domain
elements.
 Consider:
 Richard the Lionheart, king of England,
1189 → 1199.
 His younger brother, evil King John who ruled
1199 → 1215
 The left legs of Richard and John?
 A crown.
 A representation of the model:
 Objects can be related in many ways.
 A relation is a set of tuples of related objects.
 John and Richard are brothers, so here's the relation:
{<Richard, John>, <John, Richard>}
 The crown is on John's head:
<crown, John>
 Both are binary relations.
 Unary relations: person true for John and Richard.
 King true for John only (once Richard is dead).
 Some relations “are functions”.
 Each person has one left leg, so the model includes a unary
“left leg” function with maps:
<Richard> → Richard's left leg
<John> → John's left leg
 First-order logic models require total functions.
 A value must exist for every input tuple.
 Weird: the crown must have a left leg and so do all
the left legs.
 Semantics of FoL
 An Semantic of a FOL assigns a notation to all symbols.
 It also determines a domain that specifies the range of
the quantifiers.
 Each term is assigned an object, each predicate is
assigned a property of objects, and each sentence is
assigned a truth value.
 In this way, the FOL provides meaning to the terms, the
predicates, and formulas of the language.
 Interpretation in FOL
 Domain D be a nonempty set.
 Each constant is assigned an element of D.
 Each variable is assigned to subset of D.
 Each function 'f' of 'm' is defined on m arguments of D
and defines a mapping from Dm into D
Quantifiers

 Quantifiers allow for referring to entire collections of

objects.
 Two types: universal and existential.
Universal quantification ( ∀ )

 In first order logic, you can write “All

Kings are Persons” as:
∀x King(x) ⇒ Person(x)
 Read as:
“for all x, if x is a king, then x is a person”.
 x is called a variable.
 Lower-case by convention.
 is a term all by itself
 can be passed as an argument to a
function:
LeftLeg(x)
 A term without variables is known as a
ground term.
 The sentence ∀x P, where P is any logical
expression, says that P is true for every
object x.
 Extending the previous interpretation:

 Then, ∀x King(x) ⇒ Person(x) is true in

that original model if King(x) ⇒ Person(x)
is true under each of the above extended
interpretations.
 That universally quantified sentence is
equivalent to all this:

 King John is the only King, thus second

sentence is correct.
 Other sentences are true, but no claim made
about personification of legs, crowns, or even
King Richard. (None of these are kings).
 Now, an implication is true whenever it's
premise is false:

 So, allows assertion of a conclusion for a rule

just for objects whose premises are true and
nothing about false premises.
 A mistake: ∀x King(x) ∧ Person(x)
 Asserts things like:

 not what is wanted.

Existential quantification ( ∃ )

 Existential quantifiers make a statement about

a single object in the universe (without naming
it), unlike the universal quantifier.
 “King John has a crown on his head”:
∃x Crown(x) ∧ OnHead(x,John)
∃x is pronounced “There exists an x such that...”
or “For some x...”
 ∃ x P is true in a given model if P is true in at least one
extended interpretation that assigns x to a domain
element.
 At least one of the following is true:


Fifth assertion is true, so original existentially

quantified sentence is true in the model.
 ⇒ is a natural connective with ∀ AND ∧ is a
natural connective with ∃.
 ∧ with ∀ is a really strong statement, ⇒ with ∃
makes for weak one.
 Consider: ∃ x Crown(x) ⇒ OnHead(x,John) .
 Says at least one of these is true:

etc....
 An implication is true if premise AND
conclusion is true, or if the premise is false.
 If Richard the Lionhearted is not a crown, the
first assertion is true and the existential is
satisfied.
 Thus, existentially quantified implications
sentence are true whenever ANY object fails
on the premise.
 Not really useful at all.
 ∀ and ∃ obey De Morgan's Rules:
 Equality

 The equality symbol can signify two terms

refer to the same object:
Father(John) = Henry
 Determine truth by my checking both terms
refer to same object.
 Alternative Semantics

 It can also be used with negation to insist that two

terms are not the same object.
 To say that Richard has at least two brothers, we would
write
 ∃ x, y Brother(x, Richard ) ∧ Brother(y, Richard ) ∧¬(x =
y).
 The sentence ∃ x, y Brother (x, Richard ) ∧ Brother (y,
Richard ) does not have the intended meaning.
Using First-Order Logic
 Some examples of systematic representations
of some simple domains.
 Domains are some part of the world we want
to express some knowledge.
 Time to learn about TELL/ASK interface for
knowledge bases and learning to use this
language in knowledge bases.
Assertions and queries in first-order
logic
 Add sentences to a knowledge base using
TELL.
 Called assertions.
 Assertions John is a king, Richard is a person,
and all kings are persons:
TELL(KB, King(John))
TELL(KB, Person(Richard))
TELL(KB, ∀x King(x) ⇒ Person(x))
 Ask questions of the KB using ASK:
ASK(KB, King(John))
return true.
 Questions are called queries or goals.
 Queries logically entailed by the KB should be
answered affirmatively.
ASK(KB, Person(John))
should return true too.
 Can ask quantified queries:
ASK (KB, ∃x Person(x))
 Crude...like asking for the time and getting
answer “true”.
 How about asking about what makes
something true?
ASKVARS(KB, Person(x))
 Gives a “stream” of answers:
 {x/John}, {x/Richard}
 Called a substitution or binding list.
 Usually for KBs with all Horn clauses
 They bind variables to specific values
 Not in first-order logic, no binding of variables to
values
 The kinship domain

 Consider family relationships.

 Example facts:
 Elizabeth is mother of Charles
 Charles is father of William
 One's grandmother is the mother of one's
parent.
 Notes:
 Objects in the domain are people.
 Two unary predicates: male, female
 Kinship relations are binary predicates:
Parent, sibling, brother, sister, child,
daughter, son, spouse, wife, etc...
 Functions for mother and father, each
person has exactly one.
 Consider each function and predicate,
expressed in terms of other symbols:
 One's mother is one's female parent:
∀m,c Mother(c)=m ⇔ Female(m) ∧ Parent(m,c)
 One's father is one's male spouse:
∀w,h Husband(h,w) ⇔ Male(h) ∧ Spouse(h,w)
 Male and female are disjoint categories:
∀x Male(x) ⇔ ¬Female(x)
 Parent and child are inverse relations:
∀p,c Parent(p,c) ⇔ Child(c,p)
 A grandparent is a parent of one's parent:
∀g,c Grandparent(g,c) ⇔ ∃p Parent(g,p) ∧ Parent(p,c)
 The sentences are axioms in the domain.
 Provide basic factual information for deriving
useful conclusions.
 Also definitions, defining functions and
predicates in terms of other predicates.
 Kind of like how software packages are built
up by definitions of functions using library
functions.
 Some sentences are theorems. Theorems
are sentences entailed by axioms.
 Consider:
∀x,y Sibling(x,y) ⇔ Sibling(y,x)
 Asserts siblinghood is symmetric
 Is a theorem, following logically from axioms
that define siblinghood.
 Should return true.
 Theorems not required for a KB, but speed
things up.
 Not all axioms are definitions.
 Some provide general information about
certain predicates. No way to complete:
∀x Person(x) ⇔ …
 Can still use the Person predicate without
defining it. Partial specifications denoting
what all people have and what makes
something a person:
∀x Person(x) ⇒ ...
∀x ... ⇒ Person(x)
 Can be just facts:
Male(Jim), Spouse(Jim, Lauren)
 Numbers, sets, and lists

 The theory of natural numbers can be built

up from axioms.
 natural numbers are non-negative numbers.
 Required:
 a predicate that's true for natural numbers:
Natnum.
 one constant symbol: 0
 one function symbol: S (for successor)
 Peano axioms define addition and natural
numbers.
 Natural numbers have a recursive definition:
NatNum(0)
∀n NatNum(n) ⇒ NatNum(S(n))
 IOW:
 0 is a natural number.
 For every object n, if n is a natural number,
S(n) is one too.
 Therefore, natural numbers are 0, S(0),
S(S(0)), S(S(S(0))), etc.
 Further, some constraints on S are needed:
∀n 0 ≠ S(n)
∀m,n m ≠ n ⇒ S(m) ≠ S(n)
 Which allows defining addition in terms of S:
∀m NatNum(m) ⇒ + (0,m) = m .
∀m,n NatNum(m) ∧ NatNum(n) ⇒ + (S(m),n) = S(+(m,n))
 IOW:
 Adding 0 to any other natural number m gives us m itself.
 prefix notation used here instead of infix.
 Note: S(n) can also be written as n + 1, so the second
axiom can become:
∀m,n NatNum(m) ∧ NatNum(n) ⇒ (m + 1) + n = (m + n) + 1
(using infix notation)
 Once we have addition:
 multiplication can be defined as repeated
additions.
 exponentiation can be defined as repeated
multiplications
 and the others.
 So, the entire theory can be built up from one
constant, one function, one predicate, and four
axioms.
 sets are also important (in mathematics and reasoning).
 Needed: individual set representation, a way to add
elements to sets, taking the union and intersection of sets, set
membership, set or not
 Needed definitions:
 empty set: { }, a constant
 Set, a unary predicate, which is true of sets.
 Binary predicates:
 x∈s (x is a member of set s)
 s1 ⊆ s2 (s1 is a subset of s2
 Binary functions:
 s1 ∩ s2 (set intersection)
 s1 ∪ s2 (set union)
 {x|s} (adding element x to set s)
 Possible axioms:
 Sets are empty or made by adding something to
a set:
∀s Set(s) ⇔ (s={}) ∨ (∃x,s 2 Set(s 2 ) ∧ s={x|s 2 })
 Empty set has nothing added to it:
¬∃x,s {x|s}={}
 Adding an element to a set that already has it
does nothing:
∀x,s x∈s ⇔ s={x|s}
 Possible axioms (continued):
 Set members are elements adjoined to the
set:
∀x,s x∈s ⇔∃y,s2 (s={y|s2 } ∧ (x=y ∨ x∈s2))
 A set is a subset iff all of the set's members
are members of another set:
∀s1, s2 s1 ⊆ s2 ⇔ (∀x x∈s1 ⇒ x∈s2 )
 Two sets are equal if they're subsets of each
other:
∀s1 , s2 (s1 = s2 ) ⇔ (s1 ⊆ s2 ∧ s2 ⊆ s1 )
 Possible axioms (concluded):
 An object is an intersection of two sets iff it's
a member of both sets:
∀x, s1 , s2 x∈ (s1 ∩ s2 ) ⇔ (x∈s1 ∧ x∈s2 )
 An object is a union of two sets iff it's a
member of either set:
∀x, s1, s2 x∈(s1 ∪ s2 ) ⇔ (x∈s1 ∨ x∈ s2 )
 Lists are like sets, but lists can be ordered and
elements can be duplicated.
 Properties:
 Nil is the constant list with no elements.
 Cons, Append, First, and Rest are functions.
 Find is a predicate for lists as Member is for
sets.
 List? is a predicate that is true only of lists.
 Examples:
 Cons(x, Nil) is a list with one element, x: [x]
 A list of many elements is [A, B, C] is the
product of: Cons(A, Cons(B, Cons(C, nil)))