Unit 3: Logical reasoning and uncertainty
Artificial Intelligence notes · PTU syllabus (UGCC2521)
On this page
Unit summary
Intelligent systems must represent knowledge and reason with it — sometimes with certainty, sometimes not. This unit covers propositional and first-order logic, unification, forward and backward chaining, resolution, truth maintenance, planning (Blocks World and STRIPS), non-monotonic and probabilistic reasoning, and fuzzy sets.
After this unit you can
- Represent knowledge in propositional and first-order logic
- Apply unification, forward and backward chaining, and resolution
- Explain planning with STRIPS and the Blocks World
- Explain non-monotonic reasoning, probabilistic reasoning and fuzzy sets
PTU syllabus topics
- Propositional and first-order predicate logic
- unification and lifting
- forward/backward chaining
- resolution
- truth maintenance systems
- introduction to planning (Blocks World, STRIPS)
- non-monotonic reasoning
- probabilistic reasoning
- introduction to fuzzy set theory
Topic 1
Propositional and first-order logic
- Propositional logic uses statements (P, Q) and connectives (¬, ∧, ∨, →, ↔). It cannot express "all" or "some".
- First-order (predicate) logic adds objects, predicates, functions and quantifiers: ∀ (for all) and ∃ (there exists).
Example
"All students are hardworking": ∀x Student(x) → Hardworking(x). "Some students like AI": ∃x Student(x) ∧ Likes(x, AI).
Topic 2
Unification, chaining and resolution
- Unification finds a substitution that makes two expressions identical: Knows(John, x) and Knows(John, Mary) unify with {x/Mary}. Lifting applies inference rules to quantified sentences using unification.
Direction
Data-driven: from facts to conclusions
Goal-driven: from the goal back to facts
Starts with
Known facts
The query
Used in
Production systems, monitoring
Expert systems, Prolog
- Resolution proves a statement by contradiction: convert sentences to conjunctive normal form (CNF), add the negated goal, and resolve clauses until the empty clause appears.
- A truth maintenance system (TMS) tracks why each belief is held and retracts conclusions when their supporting facts change.
Example
Forward and backward chaining on the same rules: rules — Rain → WetGround, WetGround → Slippery; fact — Rain. Forward: from Rain derive WetGround, then Slippery. Backward: to prove Slippery, find a rule concluding it (needs WetGround), then one concluding WetGround (needs Rain), and Rain is a known fact — so Slippery is proved.
Exam tip
Resolution in four steps: (1) convert all sentences to CNF; (2) add the negation of what you want to prove; (3) resolve pairs of clauses with complementary literals; (4) when the empty clause appears, the original statement is proved.
Topic 3
Planning: Blocks World and STRIPS
Planning finds a sequence of actions to reach a goal. STRIPS represents each action with preconditions, an add list and a delete list.
Example
Action Stack(A, B) — preconditions: Holding(A), Clear(B); add: On(A, B), Clear(A), HandEmpty; delete: Holding(A), Clear(B).
The Blocks World (stacking blocks on a table with a robot hand) is the classic planning domain.
Topic 4
Non-monotonic and probabilistic reasoning
- Monotonic logic never withdraws conclusions; non-monotonic reasoning allows conclusions to be withdrawn when new information arrives ("Birds fly" — but not penguins). Default reasoning and circumscription are examples.
- Probabilistic reasoning handles uncertainty with probabilities. Bayes' theorem: P(H given E) = P(E given H) × P(H) / P(E). Bayesian networks represent dependencies among variables as a directed graph.
Example
Bayes' theorem in diagnosis: a disease affects 1% of people. A test detects it 90% of the time, but also shows positive for 5% of healthy people. P(positive) = 0.01 × 0.9 + 0.99 × 0.05 = 0.009 + 0.0495 = 0.0585. P(disease | positive) = 0.009 ÷ 0.0585 ≈ 0.15 — only about 15%, because the disease is rare. This is why probabilistic reasoning matters in medical AI.
Topic 5
Introduction to fuzzy set theory
Unlike a crisp set (0 or 1), membership varies from 0 to 1: 25°C may be 0.6 warm
In a classical (crisp) set, membership is 0 or 1. In a fuzzy set, membership is a degree between 0 and 1 — useful for vague ideas like "tall" or "hot".
Membership
0 or 1
Any value from 0 to 1
Example
Age ≥ 18 is adult
Height 175 cm is "tall" to degree 0.7
Used in
Classical logic
Washing machines, AC control, decision support
Example
Fuzzy set operations: if a room's membership in "warm" is μA = 0.7 and in "humid" is μB = 0.4, then warm or humid = max(0.7, 0.4) = 0.7, warm and humid = min(0.7, 0.4) = 0.4, and not warm = 1 − 0.7 = 0.3. A fuzzy air-conditioner uses such degrees to set the fan speed smoothly rather than just on or off.
Key terms
- First-order logic
- Logic with objects, predicates and quantifiers
- Unification
- Making two logical expressions identical by substitution
- Resolution
- An inference rule used for proof by contradiction
- STRIPS
- A planning representation with preconditions, add and delete lists
- Fuzzy set
- A set with degrees of membership between 0 and 1
Quick revision
- FOL adds ∀ and ∃ to propositional logic.
- Forward = data-driven; backward = goal-driven.
- Resolution: CNF + negated goal → empty clause.
- STRIPS: preconditions, add list, delete list.
- Fuzzy membership ∈ [0, 1].
Important exam questions
Practice questions written to the PTU exam pattern for this unit's syllabus: short answers (Section A style) and long answers (Sections B and C style).
Short-answer questions
- Q1.Differentiate between propositional and first-order logic.
- Q2.What is unification?
- Q3.Differentiate between forward and backward chaining.
- Q4.What is a truth maintenance system?
- Q5.What is non-monotonic reasoning?
- Q6.Define a fuzzy set.
Long-answer questions
- Q1.Convert given English sentences into first-order logic and prove a conclusion using resolution.
- Q2.Explain forward and backward chaining with examples.
- Q3.Explain planning using STRIPS with the Blocks World example.
- Q4.Explain probabilistic reasoning with Bayes' theorem and the basics of fuzzy set theory.
Stuck on this unit?
Message SBS on WhatsApp for help with Artificial Intelligence, or to ask about studying BCA at Synetic.
