SAT

• A boolean variable takes a value that is either true or false
• A literal is a variable or its negation
• You can AND or OR variables
• A clause is a disjunction of literals
• A boolean formula can be written in several forms but CNF is the most common $x\vee y\vee \bar{z}\wedge (x\vee \bar{y})$

An assignment of true or false to each variable needs to be made so that every clause that contains a literal that is true.