Reasoning in AI: Propositional and Predicate Logic – Detailed Notes
1. Propositional Logic
Definition: Propositional logic is a branch of logic that deals with
propositions (statements that are either true or false) and their logical
relationships using connectives.
Syntax: - Propositions: Symbols like P, Q, R representing statements. -
Connectives: AND (∧), OR (∨), NOT (¬), IMPLIES (→), IF AND ONLY IF (↔). -
Well-Formed Formulas (WFFs): Valid combinations of propositions and
connectives.
Semantics: - Assigning truth values (True/False) to propositions. -
Interpretation defines the truth value of compound statements based on
connectives.
Example: - P: “It is raining.” - Q: “The ground is wet.” - Formula: P → Q (If it
is raining, then the ground is wet.)
2. Atomic vs Compound Propositions
Atomic Proposition: A simple statement with no logical connectives.
Example: P: “It is sunny.”
Compound Proposition: Formed by combining atomic propositions
using connectives. Example: P ∧ Q: “It is sunny and warm.”
S.N
Aspect Atomic Proposition Compound Proposition
o
A simple statement Formed by combining two or
1 Definition that cannot be broken more atomic propositions using
down. logical connectives.
Complex, consists of multiple
2 Complexity Simple, indivisible.
propositions.
Does not contain Contains connectives like ∧, ∨, →,
3 Connectives
logical connectives. ¬, ↔.
Has a definite truth Truth value depends on the truth
4 Truth Value
value (True or False). values of its components.
P ∧ Q: “It is raining and it is
5 Example P: “It is raining.”
cold.”
S.N
Aspect Atomic Proposition Compound Proposition
o
Cannot be decomposed
Decompositi Can be decomposed into simpler
6 into simpler
on atomic propositions.
propositions.
Forms the building Represents more complex
7 Role in Logic blocks of logical statements derived from atomic
expressions. propositions.
Used to represent compound
Use in Used as basic facts or
8 conditions, rules, and logical
Reasoning premises.
deductions.
3. Logical Connectives in Propositional Logic
Connecti Symb Truth
ve ol Definition Table
AND ∧ True if both operands are PQ
true
TT
TF
FT
FF
OR ∨ True if at least one operand …
is true
NOT ¬ Negates the truth value …
IMPLIES → False only if P is true and Q …
false
IFF ↔ True if both have same truth …
value
(Full truth tables included in document.)
4. Tautology, Contradiction, Contingency
Tautology: Always true. Example: P ∨ ¬P
Contradiction: Always false. Example: P ∧ ¬P
Contingency: Sometimes true, sometimes false. Example: P ∧ Q
1. Tautology
Definition: A propositional formula that is always true, no matter
what truth values are assigned to its atomic propositions.
Truth Table: All rows evaluate to True (T).
Example:
o Formula: P∨¬PP \vee \neg PP∨¬P
o Meaning: “P is true or P is not true” → always true.
Use in AI: Tautologies are used to simplify reasoning and verify
logical validity.
2. Contradiction
Definition: A propositional formula that is always false, regardless of
the truth values of its atomic propositions.
Truth Table: All rows evaluate to False (F).
Example:
o Formula: P∧¬PP \wedge \neg PP∧¬P
o Meaning: “P is true and P is not true” → impossible, always false.
Use in AI: Contradictions help in detecting inconsistencies in
knowledge bases.
3. Contingency
Definition: A propositional formula that is sometimes true and
sometimes false, depending on the truth values of its components.
Truth Table: Contains both True and False values.
Example:
o Formula: P∨QP \vee QP∨Q
o Meaning: “P or Q” → True if at least one is true; False if both are
false.
Use in AI: Contingencies represent real-world conditions that are
not always certain or impossible.
5. Predicate Logic
Definition: Extends propositional logic with predicates and quantifiers to
express statements about objects.
Difference from Propositional Logic: - Propositional logic: Deals with
whole statements. - Predicate logic: Deals with objects and their properties.
Example: Human(Socrates) ∧ Mortal(Socrates)
6. Quantifiers in Predicate Logic
Universal Quantifier (∀): All objects satisfy predicate. Example:
∀x(Human(x) → Mortal(x))
Existential Quantifier (∃): Some objects satisfy predicate. Example:
∃x(Student(x) ∧ Intelligent(x))
7. Converting English Sentences into Predicate Logic
a) “All humans are mortal.” → ∀x(Human(x) → Mortal(x))
b) “Some students are intelligent.” → ∃x(Student(x) ∧ Intelligent(x))
Predicate logic extends propositional logic by allowing statements about
objects, their properties, and relationships.
While propositional logic only handles entire statements as true or
false, predicate logic allows reasoning about the internal structure
of statements.
This is useful in AI for representing knowledge, reasoning, and
problem-solving.
Predicates: Represent properties or relationships of objects.
Example: Human(x) → “x is a human”
Loves(x, y) → “x loves y”
Constants: Represent specific objects.
Example: Socrates, John
Variables: Represent unspecified objects.
Example: x, y
Quantifiers: Specify the scope of variables.
Universal Quantifier (∀): “For all” → ∀x
Existential Quantifier (∃): “There exists” → ∃x
Steps to Convert English Sentences into Predicate Logic
1. Identify the objects and entities in the sentence.
2. Identify the properties or relations among the objects
(predicates).
→ choose quantifier (∀ or ∃).
3. Determine whether the statement refers to all or some objects
4. Write the logical expression using predicates, variables, constants,
and quantifiers.
“Every father has a child.”
Objects: fathers and children
Relationship: HasChild(x, y)
Expression:
∀x (Father(x)→∃y HasChild(x,y))\forall x \, (Father(x) \rightarrow \exists y \,
HasChild(x, y))∀x(Father(x)→∃yHasChild(x,y))
Explanation: For every x, if x is a father, then there exists some y such that
x has y as a child.
8. Resolution Principle in Logic
Definition: A method to infer new clauses by eliminating a variable
that appears positively in one clause and negatively in another.
Example: From (P ∨ Q) and (¬P ∨ R), infer (Q ∨ R)
9. Resolution in Propositional Logic
Step-by-step Example: 1. Given: P ∨ Q, ¬P ∨ R 2. Identify complementary
literals: P and ¬P 3. Resolve: Q ∨ R
10. Resolution in Predicate Logic
Example: - Clauses: Human(x) ∨ Mortal(x), ¬Human(Socrates) - Unify x with
Socrates → Infer Mortal(Socrates)
11. Clause Form and Conjunctive Normal Form (CNF)
Clause Form: Expression as a set of clauses (disjunctions of literals)
CNF: Conjunction of disjunctions (AND of ORs)
12. Convert (P → Q) ∧ (¬Q ∨ R) into Clause Form
1. P → Q ≡ ¬P ∨ Q
2. Formula: (¬P ∨ Q) ∧ (¬Q ∨ R) → Clause Form: {¬P ∨ Q, ¬Q ∨ R}
13. Unification in AI
Definition: Process of making two logical expressions identical by
finding appropriate substitutions.
Role: Essential for applying resolution in predicate logic.
Example: P(x, y) and P(a, b) → Unifier {x/a, y/b}
1. Definition
Unification is a process in AI and logic programming that makes two
logical expressions identical by finding a set of substitutions for
their variables.
It is a key operation in automated reasoning, especially in
predicate logic.
The substitutions found are used to match patterns in reasoning
processes like resolution.
2. Role in AI
Unification is crucial for:
1. Predicate Logic Reasoning: Allows general rules to be applied to
specific facts.
o Example: If you know Parent(x, y) and Parent(John, Mary),
unification allows you to match x → John, y → Mary.
2. Automated Theorem Proving: Helps infer new knowledge by
combining clauses.
3. Logic Programming (Prolog): Unification is the core mechanism that
allows Prolog to match queries to facts and rules.
3. How Unification Works
1. Identify expressions to unify: Two predicates or terms.
2. Find variables and constants: Determine which parts need
substitution.
3. Substitute variables consistently: Replace variables with terms or
constants to make expressions identical.
4. Check for conflict: If a variable needs to be replaced with two
different constants, unification fails.
4. Types of Unification
Simple Unification: Only variable-to-constant or variable-to-variable
substitution.
Compound Term Unification: Handles functions and nested terms.
5. Example of Unification
Example 1 – Simple:
Expressions: P(x, a) and P(b, a)
Find substitution: {x → b}
After substitution: P(b, a) = P(b, a) ✅
Example 2 – Compound Terms:
Expressions: Loves(John, y) and Loves(x, Mary)
Substitutions: {x → John, y → Mary}
Result: Loves(John, Mary) = Loves(John, Mary) ✅
Example 3 – Failure:
Expressions: P(x) and P(f(x))
Substitution: Would require x → f(x), which leads to infinite regression
→ unification fails
14. Most General Unifier (MGU)
Definition: The simplest substitution that makes two expressions
identical.
Example: P(x, y) and P(a, y) → MGU: {x/a}
The simplest substitution that unifies two expressions without
adding unnecessary constraints.
Ensures maximum flexibility for further reasoning.
Example:
Expressions: Knows(x, y) and Knows(John, y)
MGU: {x → John}
Notes: Leaves y unchanged → allows further unifications if needed.
7. Steps to Perform Unification
1. Compare two expressions symbol by symbol.
2. If symbols are identical, move to next.
3. If one is a variable, substitute it with the other symbol.
4. If both are variables, substitute one with the other.
5. If conflict arises (different constants), unification fails.
6. Apply substitutions recursively for compound terms.
8. Applications in AI
Automated Theorem Proving: Unification is used to match premises
and apply resolution.
Logic Programming (Prolog): Resolves queries by unifying goals
with facts and rules.
Expert Systems: Helps match rules to facts dynamically.
Natural Language Processing: Pattern matching in parsing
sentences or semantic analysis.