Constraints and logic

Constraint satisfaction with backtracking, MRV, forward checking and AC-3, then propositional logic, model checking, SAT solving, chaining and unification.

About 6 hours of study

Learning objectives

Lessons

  1. 1

    Constraint satisfaction problems Intermediate

    Describe problems as variables, domains and constraints, then solve them with backtracking search. Make the search much faster with the minimum-remaining-values heuristic and forward checking, on map colouring and Sudoku.

  2. 2

    Constraint propagation and AC-3 Advanced

    Shrink domains before and during search by removing values that cannot be part of any solution. Learn arc consistency, run the AC-3 algorithm, and see what propagation can and cannot decide on its own.

  3. 3

    Propositional logic Intermediate

    Represent facts as logical sentences, give them meaning with truth tables, and decide whether a conclusion follows from a knowledge base by checking every model. Learn validity, satisfiability and the classic equivalences.

  4. 4

    Inference: chaining, resolution and unification Advanced

    Derive new facts from rules without listing every model. Use forward chaining and backward chaining with if-then rules, prove things by resolution, and match patterns with variables using unification, the step towards first-order logic.

Module practice

Module quiz

1. Which variable does the MRV heuristic choose next?
2. When is A -> B false?
3. What does an empty domain after AC-3 mean?
4. What does KB ⊨ α mean?
5. Which method starts from the facts and derives everything that follows?
6. What do f(X, a) and f(b, Y) unify to?

‹ Local search and gamesReasoning under uncertainty ›