= Boolean formula
{c}
A <Boolean formula> is a finite expression built from <Boolean variables> and <Boolean operations>, equivalently a <propositional formula> with two-valued semantics. A <Boolean valuation> determines its <truth value>. In $(x\lor y)\land\neg x$, <logical negation> acts only on $x$, and the outer <logical conjunction> combines $x\lor y$ with $\neg x$. Occurrences of the same <Boolean variable> share one <truth value>. The <Boolean satisfiability problem> asks whether some <Boolean valuation> makes the <Boolean formula> true.
Back to article page
