Synetic College Logo
Unit 1 of 4 · M.Sc IT Sem 4

Unit 1: AI foundations and knowledge representation

Artificial Intelligence & Soft Computing notes · PTU syllabus (PGCA1926)

3 min read10 topics10 exam questions
On this page
  1. Unit summary
  2. Foundations of AI
  3. History of AI
  4. Problem formulation and search
  5. Toy problems
  6. Real-world problems
  7. Propositional logic and theorem proving
  8. Resolution in propositional logic
  9. Horn clauses and forward and backward chaining
  10. Forward and backward chaining, unification and resolution in FOL
  11. First-order logic and inference
  12. Key terms
  13. Quick revision
  14. Important questions

Unit summary

Artificial intelligence builds systems that solve problems and reason. This unit covers the foundations and history of AI, toy and real-world problems — Tic-Tac-Toe, Water Jug, 8-puzzle and 8-Queens — problem formulation and search, propositional logic and theorem proving, resolution, Horn clauses, forward and backward chaining, and first-order logic and inference.

After this unit you can

  • Explain the foundations and history of AI
  • Formulate toy and real-world problems as search problems
  • Prove theorems in propositional logic with resolution, Horn clauses and chaining
  • Represent knowledge and draw inferences in first-order logic

PTU syllabus topics

  • Foundations and history of AI
  • toy and real-world problems (Tic-Tac-Toe, Water Jug, 8-puzzle, 8-Queens)
  • problem formulation and search
  • propositional logic and theorem proving
  • resolution
  • Horn clauses
  • forward/backward chaining
  • first-order logic and inference
ProcessResolution theorem proving
  1. 1Convert sentences to clause form (CNF)
  2. 2Negate the goal and add it
  3. 3Resolve pairs of clauses
  4. 4Add the resolvents
  5. 5Empty clause found

    Goal is proved

1

Topic 1

Foundations of AI

Artificial Intelligence is the branch of computer science that builds systems able to perform tasks that normally need human intelligence — reasoning, learning, perception, language and decision-making.

FrameworkFour approaches to AI

  • Thinking humanly

    Cognitive modelling

  • Thinking rationally

    Laws of thought, logic

  • Acting humanly

    Turing test

  • Acting rationally

    Rational agents (the modern approach)

The Turing Test (1950): a machine is intelligent if a human interrogator cannot tell it apart from a human in conversation.

2

Topic 2

History of AI

ProcessMilestones in AI
  1. 1

    1943–1956

    McCulloch–Pitts neuron; Turing's test (1950); Dartmouth workshop names AI (1956)

  2. 2

    1956–1974

    Early enthusiasm: Logic Theorist, General Problem Solver, LISP, ELIZA

  3. 3

    1974–1980

    First AI winter as promises fail

  4. 4

    1980s

    Expert systems (MYCIN, XCON); backpropagation revived; second winter late in the decade

  5. 5

    1990s–2000s

    Probabilistic methods, machine learning; Deep Blue beats Kasparov (1997)

  6. 6

    2012 onward

    Deep learning (ImageNet), AlphaGo (2016), transformers (2017), large language models and generative AI

3

Topic 3

Problem formulation and search

A problem-solving agent decides what to do by searching for a sequence of actions that reaches a goal. A problem is defined by: initial state, actions, transition model, goal test and path cost.

Example

8-puzzle — states: tile arrangements; actions: move the blank up, down, left or right; goal: tiles in order; path cost: number of moves.

Key termsComponents of problem formulation
Initial state
Where the agent starts
Actions
Moves available in each state
Transition model
Result of each action
Goal test
Checks whether a state is a goal
Path cost
Sum of step costs
4

Topic 4

Toy problems

ComparisonToy problems
State representation
Notes

Tic-Tac-Toe

3 × 3 board of X, O or blank; players alternate

Adversarial; at most 9! move sequences; solved by minimax — perfect play draws

Water Jug

(x, y) litres in a 4-litre and a 3-litre jug; goal 2 litres in the 4-litre jug

Actions: fill, empty, pour; solution (0,0) → (0,3) → (3,0) → (3,3) → (4,2) → (0,2) → (2,0)

8-puzzle

3 × 3 board with tiles 1–8 and a blank; move the blank up, down, left, right

9!/2 = 181,440 reachable states; heuristics: misplaced tiles, Manhattan distance

8-Queens

Place 8 queens with no two attacking

92 solutions; incremental or complete-state formulation; CSP or local search

5

Topic 5

Real-world problems

  • Route finding (maps, airline travel), touring problems (travelling salesperson), VLSI layout, robot navigation, automatic assembly sequencing, protein design and timetabling are formulated the same way, with far larger state spaces and real costs.
6

Topic 6

Propositional logic and theorem proving

  • 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).

Key termsInference rules
Modus ponens
From P → Q and P, infer Q
Modus tollens
From P → Q and ¬Q, infer ¬P
And-elimination
From P ∧ Q, infer P
Resolution
From (P ∨ Q) and (¬Q ∨ R), infer (P ∨ R)
  • Theorem proving: show that a knowledge base KB entails α (KB ⊨ α) by model checking (truth tables) or by applying sound inference rules.
7

Topic 7

Resolution in propositional logic

ProcessResolution refutation
  1. 1Convert KB and ¬α to conjunctive normal form
  2. 2Pick two clauses with complementary literals
  3. 3Add their resolvent
  4. 4Repeat until the empty clause appears (α is proved) or no new clauses can be added

Example

KB: P → Q, Q → R, P. Prove R. Clauses: ¬P ∨ Q, ¬Q ∨ R, P, and ¬R. Resolve ¬Q ∨ R with ¬R → ¬Q; with ¬P ∨ Q → ¬P; with P → empty clause. Hence R follows.

8

Topic 8

Horn clauses and forward and backward chaining

  • A Horn clause has at most one positive literal; a definite clause has exactly one — e.g., (¬A ∨ ¬B ∨ C), written A ∧ B → C. Inference with Horn clauses is linear in the size of the KB.
9

Topic 9

Forward and backward chaining, unification and resolution in FOL

  • 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.
ComparisonForward vs backward chaining
Forward chaining
Backward chaining

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

Rules: Fever ∧ Rash → Measles; Measles → Isolate. Facts: Fever, Rash. Forward chaining derives Measles, then Isolate. Backward chaining from the goal Isolate asks for Measles, then Fever and Rash, which are facts.

10

Topic 10

First-order logic and inference

Key termsFOL inference
Universal instantiation
From ∀x P(x), infer P(a) for any constant a
Existential instantiation
From ∃x P(x), infer P(k) for a new constant k
Generalised modus ponens
Lifted modus ponens using unification
Skolemisation
Removing ∃ by introducing functions or constants before CNF conversion

Example

"All men are mortal; Socrates is a man": ∀x Man(x) → Mortal(x), Man(Socrates). Universal instantiation with x/Socrates and modus ponens give Mortal(Socrates).

Key terms

Problem formulation
Defining states, actions, transitions, goal and costs
Resolution
Inference rule combining clauses with complementary literals
Horn clause
Clause with at most one positive literal
Forward chaining
Data-driven inference from facts to conclusions
Unification
Finding substitutions that make expressions identical

Quick revision

  • Definitions of AI; Turing test; history milestones.
  • Problem formulation; Tic-Tac-Toe, Water Jug, 8-puzzle, 8-Queens; real-world problems.
  • Propositional logic, inference rules, entailment.
  • Resolution refutation; Horn clauses; forward and backward chaining.
  • FOL quantifiers, instantiation, unification, Skolemisation, resolution.

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

  1. Q1.What is the Turing test?
  2. Q2.State the components of problem formulation.
  3. Q3.Give a solution to the 4–3 water jug problem.
  4. Q4.What is a Horn clause?
  5. Q5.Distinguish forward and backward chaining.
  6. Q6.What is Skolemisation?

Long-answer questions

  1. Q1.Explain the foundations and history of AI.
  2. Q2.Formulate the 8-puzzle and 8-Queens problems as search problems.
  3. Q3.Explain resolution in propositional logic with an example.
  4. Q4.Explain inference in first-order logic with forward and backward chaining.

Stuck on this unit?

Message SBS on WhatsApp for help with Artificial Intelligence & Soft Computing, or to ask about studying M.Sc IT at Synetic.

WhatsApp us