Predicate Logic

First order predicate, well formed formula of

predicate, quantifiers, Inference theory of predicate logic
Propositional Logic - Recap
A collection of declarative statements that has either a truth value "true” or
a truth value "false".

a) Boston is the capital of Massachusetts - True

b) Miami is the capital of Florida - False
c) 2 + 3 = 5 - True
d) 5 + 7 = 10 - False
e) x + 2 = 11 – Not a proposition
f) Answer this question - Not a proposition
Limitations of Propositional Logic
• Propositional logic can only represent the facts, which are either true
or false.
• PL is not sufficient to represent the complex sentences or natural
language statements.
• The propositional logic has very limited expressive power.
• Consider the following sentence, which we cannot represent using PL
logic.
"Some humans are intelligent", or
"All men are mortal."
Predicate Logic
• Predicate Logic is an extension to propositional logic.
• It is sufficiently expressive to represent the natural language
statements in a concise way.
• It is also known as First-order logic (FOL) or First-order predicate
logic.
 First-order logic (FOL)/Predicate Logic
• Models the world in terms of
Objects, which are things with individual identities
Properties of objects that distinguish them from other objects
Relations that hold among sets of objects
Functions, which are a subset of relations where there is only one “value” for
any given “input”
Examples: Objects: Students, lectures…
Relations: Brother-of, bigger than, outside..
Properties: blue, oval, even, large, ...
Functions: father-of, best-friend,
• It is a generalization of Propositional Logic that allows us to express
and infer arguments in infinite models
• Eg, Some birds can fly
All men are mortal
At least one student has course registered
Basic Elements in FOL
Atomic Sentences in FOL
• Atomic sentences are the most basic sentences of first-order logic.
• These sentences are formed from a predicate symbol followed by a
parenthesis with a sequence of terms.
• Atomic sentences are represented as Predicate (term1, term2, ......,
term n).
• Example: Ravi and Ajay are brothers - Brothers(Ravi, Ajay).
Chinky is a cat - cat (Chinky).
Complex sentences
• Complex sentences are made by combining atomic sentences using
connectives.
• We can use logical connectives to construct more complex sentences,
with the same syntax and semantics as in propositional calculus.
Brother (Richard, John) ∧ Brother (John, Richard)
King(Richard) ∨ King(John)
Quantifiers
• Quantifiers express properties of entire collections of objects
• A quantifier is a language element which generates quantification,
and quantification specifies the quantity of specimen in the universe
of discourse.
• These are the symbols that permit to determine or identify the range
and scope of the variable in the logical expression.
• First-order logic contains two standard quantifiers, called universal
and existential.
Universal quantification (∀)
• Expression of general rules in propositional logic
• “All kings are persons,” is written in first-order logic as
∀ x King(x) ⇒ Person(x)
“For all x, if x is a king, then x is a person.”
∀ is usually pronounced “For all ...”
Existential quantification (∃)
• Universal quantification makes statements about every object.
Similarly, we can make a statement about some
• There exists a 'x', For some 'x', For at least one 'x'
∃x: boys(x) ∧ intelligent(x)
There are some x where x is a boy who is intelligent

The main connective for universal quantifier ∀ is implication →

The main connective for existential quantifier ∃ is and ∧.
Properties of Quantifiers
• In universal quantifier, ∀x ∀y is similar to ∀y ∀x
• In Existential quantifier, ∃x ∃y is similar to ∃y ∃x
• ∃x ∀y is not similar to ∀y ∃x
Nested quantifiers
• Complex sentences are expressed using multiple quantifiers.
• eg: “Brothers are siblings” can be written as
∀ x ∀ y Brother (x, y) ⇒ Sibling(x, y)
• To say that siblinghood is a symmetric relationship, we can write
∀ x, y Sibling(x, y) ⇔ Sibling(y, x)
“Everybody loves somebody” means that for every person, there is
someone that person loves:
∀ x ∃ y Loves(x, y)
“There is someone who is loved by everyone,” we write:
∃ y ∀ x Loves(x, y)

The order of quantification is therefore very important

Examples
• All birds fly. In this question the predicate is "fly(bird)."
• And since there are all birds who fly so it will be represented
as follows:
∀x bird(x) →fly(x).
• Every man respects his parent.
• The predicate is "respect(x, y)," where x = man, and y = parent.
• Since there is every man so will use ∀, and it will be represented as
follows:
∀x man(x) → respects (x, parent).
• Some boys play cricket.
• The predicate is "play(x, y)," where x = boys, and y = game.
• Since there are some boys so we will use ∃, and it will be represented
as:

∃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.
• Since there are not all students, so we will use ∀ with negation, so
following representation for

¬∀ (x) [ student(x) → like(x, Mathematics) ∧ like(x, Science)]

Well-Formed Formulas

• A well-formed formula (wff) is a syntactically correct expression

according to the rules of the logical language. For example:
∀x(P(x) → Q(x))
is a wff if P and Q are predicates and the notation conforms to the
established grammar.
Unary predicate applied to
P(a)
constant

∀x P(x) Universal quantification over x

Existential quantification with

∃x (P(x) ∧ Q(x))
conjunction
De-Morgan’s law/Negating Quantifiers
Let “knows Python” with being all students in this class.

“There exists a student in this class who does not know Python”.
Let “thinks football is the best sport” with being all people.

“Everyone does not think football is the best sport”.

Inference in First-Order Logic

• Inference in First-Order Logic (FOL) involves deriving new facts or

statements from existing ones.
• This process is crucial for reasoning, knowledge representation, and
automating logical deductions.
Inference Rules
• Universal Generalization
• Universal Instantiation
• Existential Generalization
• Existential Instantiation
Universal Generalization

• Universal generalization is a valid inference rule that asserts if

premise P(c) holds true for any arbitrary element c within the
universe of discourse, we can conclude that x P(x) is also true.
• If premise P(c) holds true for any arbitrary element c in the discourse
universe we can arrive at the conclusion that x P(x).
• It can be represented as
• Let us say the given statement is like this
Loves(John, IceCream)
Loves(Mary, IceCream)
Loves(Sam, IceCream)
the FOL representation using inference rule is as below −
∀x Loves(x, IceCream)
if John, Mary, and Sam represent all entities
Universal Instantiation

• Universal Instantiation (UI) is an inference rule for First-Order Logic that

derives a particular instance from a universally quantified statement.
• If it is true for all items of a domain, then it has to be the case for any
specific element in the domain as well.
• According to the UI rule, we can infer any sentence P(c) by replacing every
object in the discourse universe with a ground term c (a constant within
domain x) from x P(x).
• It can be represented as
• Let us say the given statement be
"Everyone who teaches at a university has an advanced degree.“
∀x (Teaches(x, University) → HasAdvancedDegree (x))
• By applying Universal Instantiation (UI) inference rule we can infer
that for a specific professor, say Dr. Amrit
Teaches ([Link],University) → HasAdvancedDegree ([Link])
Existential Generalization

• Existential Introduction (EI), often referred to as Existential

Generalization (EG), is a valid inference rule in First-Order Logic.
• It allows us to introduce an existential quantifier when we can
confirm that a proposition holds true for at least one instance.
• "Mr. Raj works at Sharda"
WorksAt ([Link], Sharda)

• By applying the Existential Introduction (EI) inference rule, we can

generalize that "There exists someone who works at Sharda"
∃x (WorksAt (x, Sharda))
Existential Instantiation
• Existential Instantiation (EI) is a First-Order Logic inference rule that
allows for the replacement of an existentially quantified variable with
a new, arbitrary constant in order to represent an unknown but
existing entity.
• This rule indicates that from the formula x P(x), one can deduce P(c)
by introducing a new constant symbol c.
• Let us say the given statement is "Someone has published a research
paper."
∃ x (HasPublishedResearch(x))
• By applying the Existential Instantiation (EI) inference rule, we can
infer that for a specific researcher, say Dr. Arjun
HasPublishedResearch ([Link]).
Tutorial
1. Let P(x) be the predicate "x is divisible by 3" where x is an integer.
Determine the truth value of ∀x P(x) and ∃x P(x).
2. Let Q(x,y) be the predicate "x + y > 10" where x and y are real
numbers. Determine the truth value of ∀x ∃y Q(x, y).
3. Let R(x) be the predicate "x is a vowel" where x is a letter in the
English alphabet. Write the following statement using predicate
logic: "There is a vowel in the English alphabet.“
4. Let P(x) be the predicate "x² - 1 = 0" where x is a real number.
Determine the truth value of ∃x P(x).
5. Let Q(x,y) be the predicate "x < y" where x and y are integers. What
does ∀x ∃y Q(x,y) mean in words?
6. Let S(x) be the predicate "x is a mammal" and T(x) be "x can fly"
where x is an animal. How would you express "Some mammals can fly"
using predicate logic?
7. Let R(x,y) be the predicate "x + y = 10" where x and y are integers. Is
the statement ∀x ∀y R(x,y) true or false? Explain why.
8. Let S(x) be the predicate "x is a multiple of 5" where x is an integer.
Express the statement "There is no integer that is a multiple of 5" using
predicate logic.
9. Let T(x,y) be the predicate "x is taller than y" where x and y are
people. Express the statement "Nobody is taller than themselves" using
predicate logic.
10. Let P(x,y) be the predicate "x is the parent of y" where x and y are
people. Express "Everyone has a parent" using predicate logic.
Tutorial
1. Prove using natural deduction
Some animals are cats.
All cats are friendly.
Conclusion: Some animals are friendly.
2. Prove using natural deduction
All men are mortal.
Socrates is a man.
Conclusion: Socrates is mortal.
Given:
• Some animals are cats.
Formally: ∃x(Animal(x)∧Cat(x))
• All cats are friendly.
Formally: ∀x(Cat(x)→Friendly(x))
Goal:
• Prove: Some animals are friendly.
Formally: ∃x(Animal(x)∧Friendly(x))
1. ∃𝑥(𝐴𝑛𝑖𝑚𝑎𝑙(𝑥)∧𝐶𝑎𝑡(𝑥)) - Premise
2. ∀x(Cat(x)→Friendly(x)) - Premise
3. Animal(a) ∧ Cat(a) - Existential instantiation on 1
4. Animal (a) – Simplification rule on 3
5. Cat (a) - Simplification rule on 3
6. Cat(a)→Friendly(a) – Universal instantiation on 2
7. Friendly(a) - Modus Ponens 5 and 6
8. Animal(a)∧Friendly(a) - Conjunction rule on 4 and 7
9. ∃x(Animal(x)∧Friendly(x)) – Existential Generalization
Given:
• All men are mortal.
∀𝑥(𝑀an(𝑥)→Mortal(𝑥))
• Socrates is a man.
𝑀an(Soctrates)
Goal:
Prove : Socrates is mortal.
Mortal(Soctrates)
1. ∀x(Man(x)→Mortal(x)) Premise
2. 𝑀an(Soctrates) Premise
3. 𝑀an(Soctrates)→Mortal(Soctrates) Universal Instantiation from (1)
4. Mortal(Soctrates) Modus Ponens from (2) and (3)
• p → (q → r)
•p¬r
• Prove ¬ q
1. p → (q → r)
2. p
3. ¬ r
4. q → r - Modus Ponens 1 and 2
5. ¬ q – Modus Tollens 3 and 4
• Every person who loves all animals is an animal lover.
• John loves all animals
• If someone is an animal lover, then they care for animals.
• Prove that John cares for animals using Predicate logic
∀x([∀y(Animal(y)→Loves(x,y))]→AnimalLover(x))
∀y(Animal(y)→Loves(John,y))
∀x(AnimalLover(x)→∀y(Animal(y)→CaresFor(x,y)))

To Prove
∀y(Animal(y)→CaresFor(John,y))
1. ∀x([∀y(Animal(y)→Loves(x,y))]→AnimalLover(x)) – Premise
2. ∀y(Animal(y)→Loves(John,y)) - Premise
3. ∀x(AnimalLover(x)→∀y(Animal(y)→CaresFor(x,y))) - Premise
4. AnimalLover(John) Modus Ponens 1 and 2
5. AnimalLover(John)→∀y(Animal(y)→CaresFor(John,y)) -Universal
instantiation on 3
6. ∀y(Animal(y)→CaresFor(John,y)) – Modus Ponens 5 and 4