Conjunctive normal form
= Conjunctive normal form
{title2=$\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>.