Boolean operation ($f:\{0,1{\}}^n\to \{0,1\}$)

A Boolean operation is a Boolean function taking truth values encoded as bits: $0$ means false and $1$ means true. These operations supply the concrete two-valued interpretation of a Boolean algebra. A Boolean valuation fixes the inputs; a truth table lists every possible input. With two input bits there are four rows.

The basic logical connectives are logical conjunction (AND, $P\wedge Q$, both true), logical disjunction (OR, $P\vee Q$, at least one true), exclusive or (XOR, $P\oplus Q$, exactly one true), and logical negation (NOT, $\neg P$, the opposite value). OR is inclusive: it accepts the case where both inputs are true.^[ref]

For an original program-condition example, let $P$ mean “the backup is recent” and $Q$ mean “the backup is verified”. A rule requiring a recent, verified backup uses logical conjunction; one accepting either qualification uses logical disjunction. A rule flagging a mismatch between the two qualifications uses exclusive or. A recent, verified backup gives $(P,Q)=(1,1)$: AND and OR accept it, while XOR does not flag it. The last row of the truth table makes this difference explicit.

The same small Boolean operations build larger tests and Boolean circuits. In a programming language, the value of a condition and the procedure for evaluating it both matter. For Boolean operands, Python's and, or, and not implement these logical connectives. Evaluation proceeds from the left; and skips its right operand if the left is false, and or skips it if the left is true. More generally, and and or return an operand, whereas not returns a Boolean.^[ref]

For example, the Python condition denominator != 0 and numerator / denominator > 2 avoids division by zero because the logical conjunction's second test is evaluated only when the first succeeds. Reversing the tests preserves the abstract truth table for defined operands but can raise a division-by-zero error handled through exception handling. A rewrite involving a side effect must also preserve the needed evaluation behavior.

Events turn Boolean operations into operations on sets. For a die with sample space $U=\{1,2,3,4,5,6\}$, let $A=\{2,4,6\}$ be the event “even outcome” and $B=\{4,5,6\}$ the event “outcome at least four”. At outcome $u$, use the indicator functions $P=1_A(u)$ and $Q=1_B(u)$. ThenThus logical conjunction becomes set intersection, logical disjunction becomes set union, exclusive or becomes symmetric difference, and logical negation becomes the complement of a set within $U$. Outcome four satisfies both events, so inclusive logical disjunction includes it and exclusive or excludes it. If the die is fair, these four events have probabilities $1/3$, $2/3$, $1/3$, and $1/2$, respectively. No assumption of independent events is needed for the set identities; indeed $A$ and $B$ here are not independent, since $1/3\ne (1/2)(1/2)$.

Exclusive or returns one exactly when its two input bits differ. Its truth table gives $0\oplus 0=0$, $0\oplus 1=1$, $1\oplus 0=1$, and $1\oplus 1=0$. The identitiesexpress exclusive or using logical conjunction, logical disjunction, and logical negation. The first expression accepts at least one input and then excludes both; the second explicitly lists the two accepted input pairs.

For numerical bits, exclusive or is addition in modular arithmetic modulo two:The binary operation is commutative and associative, because addition modulo two has those properties. It satisfies $x\oplus 0=x$, $x\oplus 1=\neg x$, and $x\oplus x=0$. These identities explain why a bit can be toggled and restored with the same operation.

On binary strings of equal length, bitwise exclusive or applies the one-bit rule separately at each position. For example,A bit mask of $0110$ toggles exactly the middle two bits. Applying the mask twice restores the original binary string: each selected bit changes twice, and each unselected bit stays fixed. This positional operation is distinct from taking the exclusive or of the overall truth values of two integers.

For bits $x_1,\dots ,x_n$, repeated exclusive or computes the parity of the number of ones:An induction proves this: the first bit gives its own parity, and appending a zero preserves it while appending a one changes it. The binary string $10110$ has three ones, so its parity bit is one. Append that parity bit to obtain $101101$, whose six bits have even parity. Flipping the second bit produces $111101$ and changes the combined exclusive or to one, detecting an error. Flipping the third bit as well produces $110101$, with four ones and combined exclusive or zero: an even number of flips can escape this check.

For three inputs, repeated exclusive or means an odd number of true inputs, rather than exactly one: $1\oplus 1\oplus 1=1$. The “exactly one” description applies to the two-input exclusive or. This distinction matters when translating a requirement that exactly one option be selected into a program condition.

Logical negation exchanges zero and one: $\neg 0=1$ and $\neg 1=0$. For a numerical bit $x$, this is $1-x$; applying logical negation twice restores $x$. It acts on the entire propositional formula in its scope. Parentheses therefore matter: $\neg (P\vee Q)$ says that neither condition holds, while $(\neg P)\vee Q$ also accepts every case where $Q$ holds. At $(P,Q)=(1,1)$ their values are zero and one.

On a set, logical negation becomes taking a complement in a fixed universal set. In Boolean operations on events, “not even” selects $\{1,3,5\}$. “Not both even and at least four” selects $\{1,2,3,5\}$; it does not require both qualifications to fail. De Morgan's laws make the scope of these compound negations precise.

De Morgan's laws exchange logical conjunction and logical disjunction when a logical negation moves across them:Here $\equiv$ denotes logical equivalence: the two propositional formulas agree under every Boolean valuation.^[ref]

A complete verification uses the four rows of a truth table. In input order $(0,0),(0,1),(1,0),(1,1)$, both sides of the first logical equivalence have output sequence $(1,1,1,0)$; both sides of the second have $(1,0,0,0)$. A proof in words is equally short: failure of “both” means at least one failure, whereas failure of “at least one” means both fail. The differing middle rows explain why simply pushing logical negation inward without changing AND to OR is wrong.

For the events in Boolean operations on events, the corresponding set identities areOne can prove these identities by checking an arbitrary set element $u\in U$: its two membership truth values obey De Morgan's laws. The same reasoning works for any two subsets of a common universal set.

For a nested program test, let $R$ mean “backup recent”, $V$ mean “backup verified”, and $O$ mean “manual override authorized”. Rejecting when neither an acceptable backup nor an override is present givesThe transformed condition reads “backup stale or unverified, and no override”. Apply the second of De Morgan's laws at the outside, then the first at the inner logical conjunction. For $(R,V,O)=(1,0,0)$ it rejects; changing only $O$ to one makes it accept. With Boolean operands in Python, not ((recent and verified) or override) and ((not recent) or (not verified)) and (not override) have the same result and inspect the operands in the same order, with the same skipped operands.

For a Boolean function $f$ of $n$ input bits, define its De Morgan dual by complementing every input, applying $f$, and complementing the output:

De Morgan's laws say that the De Morgan dual of logical conjunction is logical disjunction, and conversely. The constant zero Boolean function becomes constant one. This is different from merely negating the output: for AND, output logical negation gives one at $(0,0)$, whereas the De Morgan dual gives zero there.

Taking the De Morgan dual twice restores the original Boolean function:Here each input is complemented twice as well. For a Boolean formula built from AND, OR, NOT and constants, its De Morgan dual can therefore be obtained by exchanging AND with OR and zero with one throughout, leaving input names and NOT in place. A structural induction proves the rule: it holds for an input and each constant, De Morgan's laws handle the two binary logical connectives, and double logical negation handles NOT. This symmetry lets one translate a complex test systematically instead of guessing where its failures occur.