Example Search Problem: SAT
We need to define problems and solutions
Propositional Satisfiability (SAT)
- Now present it as a logical problem
Problem is a list of clauses
- contains literals
- each literal a positive or negative variable
- literals are e.g. +A, -B, +C, ….
Solution is choice of true or false for each variable
- one choice per letter
- each clause to contain at least one of our choices
- I.e. +A matches A = true, -A matches A = false