An assignment is a setting of the variables to true and false, for example (u→TRUE, v→FALSE). Once all of the variables are assigned a truth value, the formula itself has a truth value. The assignment (u→TRUE, v→FALSE) makes the formula above false. A satisfying assignment is an assignment that makes the formula true. For the formula above, the assignment (u→TRUE, v→TRUE) is satisfying. If a formula has a satisfying assignment we say the formula is satisfiable.
SAT is the set of satisfiable formula. The formula above is in SAT. This formula is not.
CNF-SAT is the set of satisfiable CNF formulas. k-CNF-SAT or k-SAT is the set of satisfiable formulas in k-CNF.
Cook and Levin independently showed that SAT is NP-complete. The problem remains NP-complete if we restrict to CNF-SAT or even 3-SAT.
Next lesson we will show that CNF-SAT is NP-complete.