SAT

• Given: Set of variables V = {v1,...,vn}

Set of clauses C over V

• Wanted: Assignment V ? {T,F}

such that every clause in C holds.

• Example: V = {v1, v2}

C = {v1 ? v2, v1 ? v2, v1 ? v2}

• Solution: v1 ? T, v2 ? T,

Previous slide

Next slide

Back to first slide

View graphic version