Propositional Logic and
First Order Logic
Propositional logic
Propositional Logic (PL), also known as Boolean Logic, is the simplest form of logic in Artificial Intelligence (AI). It deals with
statements (propositions) that can be either true (T) or false (F).
Propositional logic
Propositional Logic (PL), also known as Boolean Logic, is the simplest form of logic in Artificial Intelligence (AI). It deals with
statements (propositions) that can be either true (T) or false (F).
Propositional logic
Propositional logic
Applications of Propositional Logic in AI
• Automated Reasoning – Used in theorem proving & decision-making.
Artificial Intelligence Planning – Helps AI make logical decisions.
Expert Systems – AI systems use logic to infer conclusions.
Digital Circuit Design – Used in logic gates (AND, OR, NOT).
Limitations of Propositional Logic
• ❌ Cannot express complex relationships (e.g., "All humans are
mortal").
❌ Cannot handle variables or quantifiers (handled by First-Order
Logic).
First Order Logic
First-Order Logic (FOL), also called Predicate Logic, is a formal system used in Artificial Intelligence (AI) to
represent knowledge and reason about it. It extends Propositional Logic by introducing quantifiers, predicates,
and variables, making it more expressive.
Key Components of First-Order Logic
1. Constants – Represent objects in the domain (e.g., John, Apple).
2. Variables – Represent general entities (e.g., x, y).
3. Predicates – Define properties or relationships between objects (e.g., Loves(John, Mary) means John loves
Mary).
4. Functions – Map objects to other objects (e.g., Mother(John) gives John's mother).
5. Quantifiers
o Universal Quantifier ( ∀ ): "For all"
Example: ∀x Loves(x, Mother(x)) → Everyone loves their mother.
o Existential Quantifier ( ∃ ): "There exists"
Example: ∃x Loves(John, x) → There exists someone whom John loves.
First Order Logic
Why is FOL Important in AI?
More expressive than Propositional Logic.
Used in knowledge representation and automated reasoning.
Forms the foundation of Expert Systems, Natural Language Processing, and Semantic Web.
Enables AI to infer new facts from existing ones.
Example of FOL in AI
Knowledge Base:
1. ∀x (Human(x) → Mortal(x)) (All humans are mortal)
2. Human(Socrates) (Socrates is a human)
Inference:
From (1) and (2), we can conclude:
Mortal(Socrates) (Socrates is mortal)
Unification
1. Unification in AI
Unification is a fundamental process in First-Order Logic (FOL) that helps in matching logical expressions by finding
a substitution of variables. It is widely used in automated reasoning, theorem proving, and natural language
processing
Algorithm:
Unification Algorithm Steps
1. Compare the predicates (they must be the same).
2. Match the arguments one by one:
o If both are constants, they must be equal.
o If one is a variable, replace it with the other term.
o If both are variables, they are interchangeable.
Apply the substitution.
Unification
1. Unification in AI
Unification is a fundamental process in First-Order Logic (FOL) that helps in matching logical expressions by finding
a substitution of variables. It is widely used in automated reasoning, theorem proving, and natural language
processing
2. Example of Unification
🔹 Example 1:
Consider these two predicates:
1. Knows(John, x)
2. Knows(John, Mary)
To unify these, we need to substitute x = Mary.
• ✅ Unified Result: Knows(John, Mary)
Unification
🔹 Example 2:
1. Loves(x, Rose)
2. Loves(Romeo, y)
To unify these, we substitute:
x = Romeo
y = Rose
• ✅ Unified Result: Loves(Romeo, Rose)
Unification
🔹 Example 3:
UNIFY (Knows(John, x), Knows(y, Mother(y)))
• The first term has Knows(John, x)
• The second term has Knows(y, Mother(y))
For unification:
1. The predicate Knows is the same in both.
2. John and y must be unified → Set y = John.
3. x and Mother(y) must be unified → Since we substituted y = John, this becomes x = Mother(John).
When unification fails?
How to recover from ‘failed
unification’
By Standardizing the variable ie. by changing or renaming one variable.
Before Standardization
After Standardization
problems
Answers
problems
problems
Scenario question
1.In a social network, we want to check if two individuals are friends. Suppose a database entry records
friendships using the format Friend(person1, person2). Given an unknown friendship Friend(x, y), can we
determine if it matches the friendship Friend(Alice, Bob)? What values should x and y take to unify these two
facts?
2. A university maintains a record of which professor teaches which subject in the format Teaches(Prof,
Subject). If a query is made to find the professor and subject using Teaches(Prof, Subject), and we have a record
Teaches(Dr.Smith, AI), can we determine who is the professor and what subject they teach? What substitutions
are needed?
problems
