First Order Logic in AI
Dr. Naveen Saini
Assistant Professor
Department of Information Technology
Indian Institute of Information Technology Allahabad
Uttar Pardesh
1
nsaini@iiita.ac.in https://sites.google.com/view/nsaini
Contents
• More on Representation
• Syntax and Semantics of First-Order Logic
• Using First Order Logic
• Knowledge Engineering in First-Order
Logic
2
Propositional logic
• Logical constants: true, false
• Propositional symbols: P, Q, S, ... (atomic
sentences)
• Wrapping parentheses: ( … )
• Sentences are combined by connectives:
...and [conjunction]
...or [disjunction]
...implies [implication / conditional]
..is equivalent [biconditional]
...not [negation]
• Literal: atomic sentence or negated atomic sentence
Examples of PL sentences
• P means “It is hot.”
• Q means “It is humid.”
• R means “It is raining.”
• (P Q) R
“If it is hot and humid, then it is raining”
• QP
“If it is humid, then it is hot”
Limitations of propositional logic
• So far we studied propositional logic
• Some English statements are hard to model in propositional
logic:
– “If your roommate is wet because of rain, your roommate must not
be carrying any umbrella”
• Pathetic attempt at modeling this:
– RoommateWetBecauseOfRain =>
(NOT(RoommateCarryingUmbrella0) AND
NOT(RoommateCarryingUmbrella1) AND
NOT(RoommateCarryingUmbrella2) AND …)
Problems with propositional logic
• No notion of objects
• No notion of relations among objects
• RoommateCarryingUmbrella0 is instructive to us,
suggesting
– there is an object we call Roommate,
– there is an object we call Umbrella0,
– there is a relationship Carrying between these two objects
• Formally, none of this meaning is there
– Might as well have replaced RoommateCarryingUmbrella0 by P
First-Order Logic
• also known as Predicate logic or First-order
predicate logic.
• Much more powerful the propositional (Boolean)
logic
– Greater expressive power than propositional logic
– Allows for facts, objects, and relations
7
Elements of first-order logic
• Objects: can give these names such as Umbrella0, Person0,
John, Earth, …
• Relations: Carrying(., .), IsAnUmbrella(.)
– Carrying(Person0, Umbrella0), IsUmbrella(Umbrella0)
– Relations with one object = unary relations
– Relations with more objects = n-any relations
• Functions: Roommate(.)
– Roommate(Person0)
• Equality: Roommate(Person0) = Person1
Pros of First-Order Logic
• First-Order Logic assumes that the world
contains:
– Objects
• E.g. people, houses, numbers, theories, colors, football
games, wars, centuries, …
– Relations
• E.g. red, round, prime, bogus, multistoried, brother of, bigger
than, inside, part of, has color, occurred after, owns, comes
between, …
– Functions
• E.g. father of, best friend, third quarter of, one more than,
beginning of, …
9
Logics in General
Language Ontological Epistemological
Commitment Commitment
Propositional Logic Facts True / False /
Unknown
First-Order Logic Fact, objects, relations True / False /
Unknown
Temporal Logic Facts, objects, True / False /
relations, times Unknown
Probability Theory Facts Degree of belief
[0,1]
Fuzzy Logic Degree of truth Known interval value
[0,1]
10
Two main parts of FOL
• As a natural language, first-order logic
also has two main parts:
– Syntax
– Semantics
11
Syntax of First-Order Logic
• Constants 2, A,1,John,cat,…
• Predicates Brother, Father, >, …
• Functions Sqrt, LeftArmOf, …
• Variables x, y, a, b, …
• Connectives ¬
• Equality ==
• Quantifiers $"
12
Components of First-Order Logic
• Term
– Constant, e.g. Red
– Function of constant, e.g. Color(Block1)
• Atomic Sentence
– represent atomic sentences as Predicate (term1,
term2, ......, term n).
– Predicate relating objects (no variable)
• John and Richard are brothers: => Brother (John, Richard)
• Married (Mother(John), Father(John))
• Complex Sentences
– Atomic sentences + logical connectives
• Brother (John, Richard) Brother (John, Father(John))
13
Components of First-Order Logic
• Quantifiers
– These are the symbols that permit to determine or
identify the range and scope of the variable in the
logical expression.
– Two quantifiers:
• Universal Quantifier, (for all, everyone, everything)
• Existential quantifier, (for some, at least one).
• Universal quantifier “for all” "
– The expression is true for every possible value of the
variable
• Existential quantifier “there exists” $
– The expression is true for at least one value of the
variable 14
Components of First-Order Logic
• Universal quantifier “for all” "
– The expression is true for every possible value of the
variable
– If x is a variable, then ∀x is read as:
• For all x
• For each x
• For every x
– Example:
• All man drink coffee
• ∀x man(x) -> drink(x, coffee)
15
Components of First-Order Logic
• Existential quantifier “there exists” $
– The expression is true for at least one value of the
variable
– If x is a variable, then existential quantifier will be ∃x or
∃(x). And it will be read as:
• There exists a 'x.'
• For some 'x.'
• For at least one 'x.‘
– Example:
• Some boys are intelligent.
16
Some Examples of FOL using Quantifiers
• All birds fly.
– ∀x bird(x) →fly(x)
• Every man respects his parent.
– the predicate is "respect(x, y)," where x=man, and y= parent.
– ∀x man(x) → respects (x, parent)
• Some boys play cricket.
– the predicate is "play(x, y),“where x= boys, and y= game
– ∃x boys(x) → play(x, cricket).
• Not all students like both Mathematics and Science.
– the predicate is "like(x, y)," where x= student, and y= subject.
– ¬∀ (x) [ student(x) → like(x, Mathematics) ∧ like(x, Science)].
17
Semantics in PL – Some Informal Definitions
• Given the truth values of all symbols in a sentence, it can be
“evaluated” to determine its truth value (True or False)
• A valid sentence or tautology is a sentence that is True under all
interpretations, no matter what the world is actually like or how the
semantics are defined (example: “It’s raining or it’s not raining”)
• An inconsistent sentence or contradiction is a sentence that is
False under all interpretations (the world is never like what it
describes, as in “It’s raining and it’s not raining”)
• P entails Q, written P ⊧ Q, means that whenever P is True, so is Q;
in other words, all models of P are also models of Q
Interpretations
• In propositional logic, truth values are assigned to the
atoms of a formula in order to evaluate the truth value
of the formula
• An assignment is a function
v : P → {T,F}
v assigns a truth value to any atom in a given formula (P
is the set of all propositional letters, i.e. atoms)
Suppose F denotes the set of all propositional formulas.
We can extend an assignment v to a function
v : F → {T,F}
which assigns the truth value v(A) to any formula A in F.
v is called an interpretation.
Interpretations (cont’)
• Example:
– Suppose v is an assignment for which
v(p) = F, v(q) = T. [here, p and q are
formulas]
– If A = (¬p → q) ↔ (p V q), what is v(A)?
Solution:
v(A) = v((¬p → q) ↔ (p V q))
= v(¬p → q) ↔ v(p V q)
= (v(¬p) → v(q)) ↔ (v(p) V v(q))
= (¬v(p) → v(q)) ↔ (v(p) V v(q))
= (¬F → T) ↔ (F V T)
= (T → T) ↔ (F V T)
= T↔T
= T
Models and Satisfiability
• A propositional formula A is satisfiable iff v(A) = T in some
interpretation v; such an interpretation is called a model for A.
– A is unsatisfiable (or, contradictory) if it is false in every interpretation
• A set of formulas U = {A1,A2,…,An} is satisfiable iff there exists an
interpretation v such that v(A1) = v(A2) =…= v(An) = T; such an
interpretation is called a model of U.
– U is unsatisfiable if no such interpretation exists
• Relevant properties:
– If U is satisfiable, then so is U − {Ai} for any i = 1, 2,…, n
– If U is satisfiable and B is valid, then U U {B} is also satisfiable
– If U is unsatisfiable and B is any formula, U U {B} is also unsatisfiable
– If U is unsatisfiable and some Ai is valid, then U − {Ai} is also unsatisfiable
Truth in First-Order Logic
• Sentences are true with respect to a model and an
interpretation
• Model contains >= 1 object (domain elements) 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
22
First-Order Logic Example
23
Examples
• Everyone likes McDonalds
– "x, likes(x, McDonalds)
• Someone likes McDonalds
– $x, likes(x, McDonalds)
• All children like McDonalds
– "x, child(x) likes(x, McDonalds)
• Everyone likes McDonalds unless they are allergic to it
– "x, likes(x, McDonalds) allergic(x, McDonalds)
– "x, allergic (x, McDonalds) likes(x, McDonalds)
24
Properties of Quantifiers
• "x "y is the same as "y "x
• $x $y is the same as $y $x
• $x "y is not the same as "y $x
– $x "y Loves(x, y)
• “There is a person who loves everyone in the
world”
– "y $x Loves(x, y)
• “Everyone in the world is loved by at least one
person”
25
Nesting Quantifiers
• Everyone likes some kind of food
"y $x, food(x) likes(y, x)
• There is a kind of food that everyone likes
$x "y, food(x) likes(y, x)
• Someone likes all kinds of food
$y "x, food(x) likes(y, x)
• Every food has someone who likes it
"x $y, food(x) likes(y, x)
26
Examples
• Quantifier Duality
– Not everyone like McDonalds
("x, likes(x, McDonalds))
$x, likes(x, McDonalds)
– No one likes McDonalds
"x, likes(x, McDonalds)
($x, likes(x, McDonalds))
27
Fun with Sentences
• Brothers are siblings
"x,y Brother(x,y) Sibling(x, y)
• Sibling is “symmetric”
"x,y Sibling(x,y) Sibling(y, x)
28
Other Comments About
Quantification
• To say “everyone likes McDonalds”, the following is too
broad!
– "x, likes(x, McDonalds)
• We mean: Every one (who is a human) likes McDonalds
– "x, person(x) likes(x, McDonalds)
• Essentially, the left side of the rule declares the class of
the variable x
• Constraints like this are often called “domain constraints”
29
Equality
• We allow the usual infix = operator
– Father(John) = Henry
– "x,y sibling(x, y) (x=y)
• The equality symbol can also be used with
negation to represent that two terms are not the
same objects.
– Example: ￢(x=y) which is equivalent to x ≠y.
30
Knowledge Engineering in First-order logic
• The process of constructing a knowledge-base in first-
order logic is called as knowledge- engineering.
• In knowledge-engineering, someone who
investigates a particular domain, learns important
concept of that domain, and generates a formal
representation of the objects, is known as knowledge
engineer.
31
Review --- Knowledge engineering in 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
Knowledge Engineering in First-order
logic: The electronic circuits domain
One-bit full adder
Possible queries:
-does the circuit function properly?
-what gates are connected to the first input terminal?
-what would happen if one of the gates is broken? and
so on
The electronic circuits domain
1. Identify the task
– Does the circuit actually add properly?
2. Assemble the relevant knowledge
– Composed of wires and gates; Types of gates (AND, OR,
XOR, NOT)
– Irrelevant: size, shape, color, cost of gates
3. Decide on a vocabulary
Type(X1) = XOR (function)
Type(X1, XOR) (binary predicate)
XOR(X1) (unary predicate)
The electronic circuits domain
4. Encode general knowledge of the domain
– "t1,t2 Connected(t1, t2) Signal(t1) = Signal(t2)
– "t Signal(t) = 1 Signal(t) = 0
– 1≠0
– "t1,t2 Connected(t1, t2) Connected(t2, t1)
– "g Type(g) = OR Signal(Out(1,g)) = 1 $n Signal(In(n,g)) = 1
– "g Type(g) = AND Signal(Out(1,g)) = 0 $n Signal(In(n,g)) = 0
– "g Type(g) = XOR Signal(Out(1,g)) = 1 Signal(In(1,g)) ≠
Signal(In(2,g))
– "g Type(g) = NOT Signal(Out(1,g)) ≠ Signal(In(1,g))
The electronic circuits domain
5. Encode the specific problem instance
Type(X1) = XOR Type(X2) = XOR
Type(A1) = AND Type(A2) = AND
Type(O1) = OR
Connected(Out(1,X1),In(1,X2)) Connected(In(1,C1),In(1,X1))
Connected(Out(1,X1),In(2,A2)) Connected(In(1,C1),In(1,A1))
Connected(Out(1,A2),In(1,O1)) Connected(In(2,C1),In(2,X1))
Connected(Out(1,A1),In(2,O1)) Connected(In(2,C1),In(2,A1))
Connected(Out(1,X2),Out(1,C1)) Connected(In(3,C1),In(2,X2))
Connected(Out(1,O1),Out(2,C1)) Connected(In(3,C1),In(1,A2))
The electronic circuits domain
6. Pose queries to the inference procedure
What are the possible sets of values of all the terminals for the adder
circuit?
$i1,i2,i3,o1,o2 Signal(In(1,C1)) = i1 Signal(In(2,C1)) = i2 Signal(In(3,C1)) = i3
Signal(Out(1,C1)) = o1 Signal(Out(2,C1)) = o2
7. Debug the knowledge base
May have omitted assertions like 1 ≠ 0
Summary
• First-order logic:
– Much more expressive than propositional logic
– Allows objects and relations as semantic primitives
– Universal and existential quantifiers
– syntax: constants, functions, predicates, equality,
quantifiers
• Knowledge engineering using FOL
– Capturing domain knowledge in logical form
References
• https://www.cpp.edu/~ftang/courses/CS420/not
es/FOL.pdf
• https://www.ics.uci.edu/~rickl/courses/cs-171/0-
ihler-2016-fq/Lectures/Lathrop/cs-171-14-FOL-
Knowledge-Engineering_smr16.pdf
39
Thank You!!!
Any Queries:
nsaini@iiita.ac.in
40
