= Boolean literal
{c}
{title2=$u\text{ or }\neg u$}
= Literal
{synonym}
A <Boolean literal> is a <Boolean variable> $u$ or its <logical negation> $\neg u$. The two <Boolean literals> have opposite <truth values>: a <Boolean valuation> $v$ gives $v(\neg u)=1-v(u)$ when false and true are encoded as zero and one. Thus $u=0$ makes the positive <Boolean literal> $u$ false and the negative <Boolean literal> $\neg u$ true. A <Boolean clause> combines <Boolean literals>, and a <Boolean-pair colouring gadget> represents a <Boolean variable> and its <logical negation> by two <vertices> with opposite Boolean colours.
Back to article page
