Conjunctive normal form (${\bigwedge }_i{\bigvee }_j{\ell }_{ij}$)

A Boolean formula is in conjunctive normal form when it is a conjunction of Boolean clauses. It is true precisely when every clause is true; an empty conjunction is true. 3-SAT restricts each clause to at most three Boolean literals.