Functional completeness
= Functional completeness
{wiki}
A <set> of <Boolean functions> is functionally complete if <function composition> using those operations can express every positive-arity <Boolean function>. The <NAND gate> alone suffices: tie its inputs to obtain <negation>, negate its output to obtain <logical conjunction>, and apply <De Morgan's laws> to obtain <logical disjunction>; then use <disjunctive normal form>.