Limitations of Propositional Logic
Propositional logic works with declarative statements that are either true or
false. However, it has major limitations.
Problems
• It cannot represent relationships between objects
• It cannot express general rules efficiently
• It becomes impractical for large domains
Example 1:
“The sky is hot.”
Propositional logic can only say whether this statement is true or false, but it
cannot describe why (relationship between sun and heat).
Example 2:
“All students in a class like mathematics.”
Propositional logic would require writing separate statements for every
student, which is inefficient.
Introduction to First-Order Logic (FOL)
To overcome these limits, AI uses First-Order Logic (FOL), also called
Predicate Logic.
FOL extends propositional logic by adding:
• Variables
• Quantifiers
• Predicates
• Functions
This allows AI to represent objects, relationships, and general
statements more effectively.
First-Order Logic in Artificial Intelligence
Unlike propositional logic (which only handles whole statements), FOL allows
us to:
• Describe properties of objects
• Represent relationships between objects
• Express general rules
• Handle quantified statements like “all” and “some”
This makes FOL much more powerful for AI knowledge representation.
Key Components of First-Order Logic
1. Constants
Constants represent specific objects in the domain.
Examples:
Krish, Bob, Apple, 5, India
2. Variables
Variables represent any object in a domain.
Examples:
x, y, z
If the domain is students, x can represent any student.
3. Predicates
Predicates describe properties of objects or relationships between
objects.
Examples:
Father(John, Robert) → shows relationship
Likes(Ali, Math) → shows property
4. Functions
Functions map objects to a single value.
Examples:
Age(Ali) = 20
add(x, y)
LeftLegOf(Person)
5. Quantifiers
Quantifiers specify how many objects satisfy a condition.
• Universal Quantifier (∀) → “for all”
• Existential Quantifier (∃) → “there exists”
∀x Likes(x, Math)
Examples:
“All students like Mathematics.”
∃x Likes(x, Math)
“There exists at least one student who likes Mathematics.”
6. Logical Connectives
Used to combine logical statements.
∧ (AND), ∨ (OR), ¬ (NOT), → (IMPLIES), ↔ (IFF)
Examples:
Example statement:
CompletesTraining(x) → EligibleForPromotion(x)
Logical Components Summary Table
Compone
Examples
nt
Constants 1, Apple, Bob, India
Variables x, y, z
Predicates Father, Teacher, Likes
Age(x), sqrt(x),
Functions
add(x,y)
∀ (for all), ∃ (there
Quantifiers
exists)
∧, ∨, ¬, →, ↔
Connectiv
es
Syntax and Semantics of First-Order Logic
Syntax
Syntax defines the structure or rules for writing valid logical expressions
using symbols.
It specifies how constants, variables, predicates, functions, quantifiers, and
connectives are arranged.
Semantics
Semantics defines the meaning of those expressions by interpreting them in
a real-world domain.
• Syntax = Form
• Semantics = Meaning
Example of Syntax & Semantics
Statement:
“Every customer who makes a purchase receives an invoice.”
FOL Representation:
∀x [(Customer(x) ∧ Purchases(x, Product)) → ReceivesInvoice(x)]
Here:
• Syntax → Correct symbolic structure
• Semantics → Meaning: all customers who buy something get invoices
Quantifiers in First-Order Logic (FOL)
Quantifiers specify how many objects in a domain satisfy a given condition.
They help express general and existence-based statements logically.
Types of Quantifiers
1. Universal Quantifier (∀) — “For All”
The universal quantifier states that a condition holds for every object in the
domain.
∀x P(x) → “For all x, P(x) is true”
Form:
Example Statement:
“All employees in a company must follow the rules.”
∀x [Employee(x) → FollowsRules(x)]
FOL Representation:
Meaning: For every person x, if x is an employee, then x follows rules.
2. Existential Quantifier (∃) — “There Exists”
The existential quantifier states that at least one object satisfies the
condition.
∃x P(x) → “There exists an x such that P(x) is true”
Form:
Example Statement:
“There is at least one employee who received a promotion.”
∃x [Employee(x) ∧ ReceivedPromotion(x)]
FOL Representation:
Meaning: There exists some employee who received a promotion.
Sentences in First-Order Logic
FOL sentences represent facts and relationships and are divided into two
types:
1. Atomic Sentences
An atomic sentence is the simplest type of logical statement.
Structure:
Predicate(argument₁, argument₂, …)
• Predicate → property or relationship
• Arguments → constants or variables
• No logical connectives used
Example:
Teacher(John, Mathematics)
Meaning: John teaches Mathematics.
2. Complex Sentences
Complex sentences are formed by combining atomic sentences using logical
connectives and quantifiers.
∧ (AND), ∨ (OR), ¬ (NOT), → (IMPLIES), ↔ (IFF)
Connectives used:
Examples:
1. ∃y [Teacher(y) ∧ Teaches(y, Math)]
→ There exists a teacher who teaches Math.
2. ∀x [Customer(x) → Buys(x, Course)]
→ All customers buy courses.
3. ∃y [Employee(y) ∧ WorksFor(y, Company)]
→ Some employee works for the company.
Free and Bound Variables in FOL
Variables can be free or bound depending on whether a quantifier controls
them.
1. Free Variable
A free variable is not controlled by any quantifier.
Its value is unspecified.
Example Statement:
“y is the price of a product.”
FOL Form:
Price(y)
Here, y is free because no quantifier defines it.
2. Bound Variable
A bound variable is controlled by a quantifier and its scope is limited.
Example Statement:
“There exists a product whose price is less than $10.”
∃y PriceLessThan10(y)
FOL Form:
Here, y is bound by the existential quantifier.
Challenges and Limitations of First-Order Logic
1. Difficulty Handling Uncertainty
FOL only supports true/false values and cannot handle probabilities well.
2. High Computational Cost
Logical inference becomes slow with large knowledge bases.
3. Limited Expressiveness
Fuzzy concepts like “most”, “usually”, “approximately” are hard to represent.
4. Rigid Rule Structure
Rules must be explicitly defined, making systems less flexible.
5. Common-Sense Reasoning Problems
FOL struggles with assumptions, exceptions, and incomplete information.
Extensions and Notations in First-Order Logic (FOL)
1. Extensions of First-Order Logic
First-Order Logic is powerful, but some complex AI problems require richer
systems. Extensions improve its expressive ability.
a) Higher-Order Logic (HOL)
Allows quantification over predicates and functions (not just objects).
∀x Human(x) → Mortal(x)
FOL:
∀P [Property(P) → Useful(P)]
HOL:
(Quantifying over properties)
Use: Mathematical reasoning, formal verification.
b) Modal Logic
Adds concepts of possibility and necessity.
Symbols:
□P → P is necessarily true
◇P → P is possibly true
Example:
□(Sun rises in the east) → Always true
Use: AI planning, belief systems.
c) Temporal Logic
Represents time-based knowledge.
Examples:
P will be true
P has always been true
P is true until Q happens
Use: Robotics, scheduling, automated planning.
d) Fuzzy Logic
Handles partial truth (values between 0 and 1).
Example:
Hot(Weather) = 0.7
(Not fully hot, not fully cold)
Use: Control systems, decision-making AI.
e) Description Logic
Used for structured knowledge representation.
Use: Semantic web, ontologies, medical AI systems.
2. Common Notations in First-Order Logic
a) Logical Connectives
Symb
Meaning
ol
¬P NOT P
P ∧ Q P AND Q
P ∨ Q P OR Q
P → Q If P then Q
P if and only
P↔Q
if Q
b) Quantifiers
Symb
Meaning
ol
∀x For all x
∃x
There
exists x
c) Equality and Inequality
Symb
Meaning
ol
= Equal to
Not equal
≠
to
Example:
x = y → x and y are same object
d) Set Membership
Symb
Meaning
ol
∈ Belongs to set
∉
Does not
belong
x ∈ Students
Example:
e) Predicate Notation
PredicateName(argument₁, argument₂, …)
Examples:
Loves(Ali, Sara)
GreaterThan(x, y)
f) Function Notation
FunctionName(argument)
Examples:
Age(Ali)
FatherOf(John)
g) Operator Precedence (Highest → Lowest)
1. Parentheses
2. Negation (¬)
3. AND (∧)
4. OR (∨)
5. Implication (→)
6. Biconditional (↔)
Why Extensions Matter in AI
Basic FOL cannot handle:
• Uncertainty
• Time-based reasoning
• Beliefs and possibilities
• Vague concepts
Extensions help AI systems reason more like humans.