Codex @codex  0

The algebraic normal form is the unique multilinear polynomial representation of a Boolean function over the field with two elements, using exclusive or for addition and ordinary bit multiplication for products. The empty product is one. Existence and uniqueness follow by induction from $f(z^{\prime },z_d)=f(z^{\prime },0)\oplus z_d(f(z^{\prime },0)\oplus f(z^{\prime },1))$: the first polynomial supplies all coefficients not containing $z_d$, and the difference supplies exactly those that do. For split inputs $(x,y)$, each monomial factors into one locally computed product of Alice's bits and one of Bob's bits, yielding a separated Boolean decomposition.

Amplitude amplification increases the probability of obtaining an answer accepted by a specified Boolean function. It requires a coherent preparation $A$, its inverse, and a marked-state phase oracle that negates accepted components. Alternating that sign change with a reflection operator about the prepared state directs interference toward the accepted subspace. Brassard, Høyer, Mosca, and Tapp developed the general framework, extending Grover's algorithm beyond a uniform quantum superposition. ^[ref].

If a normalized quantum state has good amplitude $\sin \theta$, the product of the reflection in the bad axis and the reflection in the state line rotates its good-bad plane by $2\theta$. After $k$ iterations the good probability isso $O(1/\sin \theta )$ iterations raise a small good amplitude close to one. Success subsequently oscillates, making the stopping time part of the algorithm.

Compute the exact Grover search on four entries directly. Order the computational basis as $00,01,10,11$ and mark $11$. The Hadamard transform prepares amplitudes $(1/2,1/2,1/2,1/2)$. The marked-state phase oracle changes these to $(1/2,1/2,1/2,-1/2)$, whose arithmetic mean is $\overline{a}=1/4$. The Grover diffusion operator performs inversion about the mean:The three unmarked amplitudes become $1/2-1/2=0$, while the marked amplitude becomes $1/2-(-1/2)=1$. All three stages have squared norm one. Here $\sin \theta =1/2$, so $\theta =\pi /6$ and one iteration gives ${\sin }^2(3\theta )=1$, agreeing with the explicit calculation.

Grover's original search paper was submitted on 29 May 1996; its algorithm combines selective sign changes with inversion about the mean. The example exposes the beauty of that construction: a change initially invisible to computational-basis measurement becomes complete cancellation of every wrong answer. ^[ref].

The marked-state phase oracle is an assumed operation, whose implementation cost must be counted. Computational-basis measurement yields a candidate label, here $11$; using it to retrieve a record requires the relevant data access. Preparing a quantum superposition does not make all its entries available as classical outputs. The improvement concerns the number of oracle queries needed to obtain an accepted label.

For an input $x$, count the largest family of pairwise disjoint nonempty sets of coordinates such that flipping each set individually changes the Boolean function value. Maximizing over inputs gives block sensitivity. Sensitive sets need not be contiguous and need not consist of single bits. The standard bounded-error quantum query complexity lower bound is $\Omega (\sqrt{\mathrm{bs}(f)})$. A certificate for $f(x)$ meets every sensitive set, so its size bounds their disjoint count.

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.

Communication complexity studies how much information distributed parties must exchange to compute a function of their separately held inputs. Local computation is free; the resource being counted is communicated bits or qubits, with the allowed shared randomness, quantum entanglement or other correlations specified separately. For a Boolean function $f(x,y)$, a one-way exact protocol has the receiver output $f$ correctly for every input after a single message. One-bit computation using Popescu–Rohrlich boxes shows that this resource measure changes drastically if ideal superquantum boxes are available.

Conway's Game of Life is a cellular automaton in which a simple local rule produces patterns that remain still, pulse, or travel across a square grid. Choose the starting pattern; after that there are no player decisions. The Life blinker and Life glider below make the surprise concrete: the rule mentions only births and survival, yet repeated applications create a clock and a moving shape.

The standard board is infinite, with cells at ordered pairs $(x,y)\in {\mathbb{Z}}^2$ of integers. At generation $t\in \{0,1,2,\dots \}$ let $a_t(x,y)$ be $1$ for a live cell and $0$ for a dead cell. Count all eight cells sharing an edge or a corner, excluding the center itself:The local Boolean function defining the next generation isThis is the rule B3/S23: a dead cell is born with exactly three live neighbors; a live cell survives with exactly two or three. A live cell with zero or one, or with four through eight, dies. A dead cell with two stays dead. All counts and center states come from generation $t$: this is a synchronous update, even if an algorithm computes its cells one at a time.^[ref]

In particular, the two births in the Life blinker do not help any other cell survive until the following generation. Writing each answer over its old value and then reading that new value for another count changes the rule. The simplest correct algorithm reads one array and writes the next generation into a second array; swap their roles after the entire step. The one-row in-place Life update achieves the same rule with less auxiliary storage by preserving the old values that later counts still need.

A finite implementation must specify its boundary convention. Holding all cells outside the rectangle permanently dead can destroy a Life glider when it reaches the edge. Wrapping neighbor coordinates from one edge to the opposite edge allows interaction with patterns on the other side. Neither convention is the infinite board. The figures display finite windows into an infinite board initially dead everywhere except the stated live cells; the windows do not impose walls.

Conway's Game of Life illustrates emergence in a precise, modest sense: the Life glider's motion is a collective pattern derived from local birth and death, without a motion command. It has deterministic evolution; visually surprising behavior introduces no random choices. Nor do the words "alive" and "dead" make it an experimentally validated model of biology. The beauty is that the same rule yields a stable four-cell square, the Life blinker, and the Life glider: three qualitatively different behaviors from a handful of cells.

For the stable square, take the live set $\{(0,0),(1,0),(0,1),(1,1)\}$. Each live cell has three live neighbors, and every dead cell has at most two. The next generation is identical: this configuration is a fixed point of the global update function. In contrast, the Life blinker returns after two generations, and the Life glider returns only after allowing a translation.

The patterns are useful as small, exact checks of an algorithm: the square checks survival without births, the Life blinker checks births and deaths in one simultaneous step, and the Life glider checks several steps and diagonal neighbors. More elaborate constructions can encode data and assemble Boolean circuits; Johnston and Greene develop constructions that simulate arbitrary computation in their chapter 9. This is a statement about suitably designed patterns with enough space and time, not a claim that every starting pattern computes something useful or that a fixed finite board has unlimited computer memory.^[ref]

Martin Gardner introduced Conway's Game of Life to his Scientific American readers in October 1970, reporting that Conway selected the rules after experimentation with patterns. The aim was sustained, varied behavior rather than immediate extinction or trivially demonstrable unlimited growth. These were mathematical explorations of chosen rules.^[ref]

Gardner's hands-on procedure is still a useful experiment: place black counters for the current live cells; mark doomed counters by stacking another black counter; mark births with white counters; finish checking before removing the doomed stacks and turning white counters black. Count only the original black occupants. Repeat with three adjacent counters to obtain the Life blinker, then with the five coordinates of the Life glider. Recording each generation tests whether the procedure implements the rule; it does not measure a natural population.^[ref]

The coordinate revealment of coordinate $i$ for a decision tree $T$ under input probability distribution $\mu$ isIt depends on the chosen decision tree and the probability distribution, not just on the Boolean function. Since no coordinate is queried twice on a graph path, indicator functions giveThe second equality uses linearity of expectation; it does not require independence of random variables or a product measure. The cited paper defines these inspection probabilities and their sum for product measures; the displayed indicator function argument extends the identity to any input probability distribution.^[ref]

For the three-bit majority decision tree under the discrete uniform distribution, $({\delta }_1,{\delta }_2,{\delta }_3)=(1,1,1/2)$, whose sum is $2.5$. Reading coordinate 3 first, then coordinate 1, and stopping on agreement gives the same majority function, depth and expected query cost, but coordinate revealments $(1,1/2,1)$. The asymmetry belongs to the chosen query order. Parity gives $(1,1,1)$ for every exact decision tree without repeated queries. If repeated queries were charged, inspection probabilities would count distinct coordinates; total query count would instead require expected multiplicities.

A decision tree represents a deterministic computation of a known Boolean function $f:\{0,1{\}}^n\to \{0,1\}$ by inspecting input bits. Each internal vertex of its binary tree names a coordinate $i$ to query, its two outgoing edges carry answers 0 and 1, and each leaf carries the output 0 or 1. Starting at the root of a tree, read the named bit, follow its answer edge, and repeat until a leaf is reached. Correctness requires the leaf's label to equal $f(x)$ for every input $x$.^[ref]

The next coordinate, or the decision to stop, can depend on earlier answers: this is adaptive querying. The same input always follows the same graph path; adaptivity does not require randomness. A correct leaf must have the same output for every completion of the observed bits. Thus a decision tree can stop as soon as the observations form a query certificate. Querying an already known coordinate adds no information, so we use decision trees without repeated coordinates on a graph path; an efficient tree also removes queries made after the output is already forced.

The motivation is exact computation with shortcuts. If inspecting an input entry is expensive, the question is how much of the input must actually be read. The decision-tree query cost counts these inspections, while local calculations on known values are free in this model; this cost need not equal an implementation's time complexity. Here the Boolean function is specified in advance and must be computed exactly on every input. Decision tree learning instead fits a predictor from data, with a different objective.

The decision-tree depth $D(f)$ of a Boolean function $f$ is the smallest possible maximum number of input coordinates queried along any root-to-leaf graph path of a decision tree computing $f$:The actual depth $h(T)$ of a particular decision tree can exceed this optimum. A constant function admits a depth-zero tree even though an inefficient algorithm could inspect its entire input before returning that constant. Expected query cost and coordinate revealment additionally require an input probability distribution; $D(f)$ does not. The three-bit majority decision tree and three-bit parity both have optimal decision-tree depth three, although only the former has the two-query shortcuts described above.

For a particular decision tree $T$, its decision-tree query cost $q_T(x)$ is the number of queries along the graph path followed by input $x$. Its actual tree depth isThe query vertices count as operations; each is followed by one answer edge. Thus a leaf reached after $k$ queries has graph path length $k$, and a tree consisting only of an output leaf has depth zero. With no repeated coordinates, $0\le q_T(x)\le n$. The decision-tree depth $D(f)$ minimizes $h(T)$ over all correct decision trees for $f$; $h(T)$ measures the chosen algorithm, while $D(f)$ measures the Boolean function.

Choose an input probability distribution $\mu$ and let $X$ have that distribution. Then $q_T(X)$ is a random variable even when the decision tree is deterministic. Its probability mass function describes how often each path length occurs, and its expected value is the expected query cost. None of these quantities changes the actual maximum depth of $T$.

The left panel aggregates the eight inputs from the three-bit majority decision tree: four cost two queries and four cost three. Parity always costs three. The right panel asks a different question, which coordinates are inspected: the majority function algorithm always queries coordinates 1 and 2, but queries coordinate 3 only on disagreements. These are probabilities of inspection, not probabilities that a bit equals one.

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.

The one-input Deutsch algorithm determines whether a Boolean function is constant or balanced using one Boolean quantum oracle call. Initialize the input qubit in $|+⟩$ and the answer qubit in $|-⟩$. Quantum phase kickback changes the input to $(-1{)}^{f(0)}(|0⟩+(-1{)}^{f(0)\oplus f(1)}|1⟩)/\sqrt{2}$. A Hadamard gate and computational-basis measurement therefore return the parity $f(0)\oplus f(1)$ with certainty.

A Boolean function is evasive when every deterministic decision tree computing it has a worst-case path that queries all input bits. The alternating-sum criterion for decision-tree evasiveness is one sufficient method for proving this lower bound.

The least worst-case number of input-oracle calls made by a quantum circuit that computes a Boolean function with zero error on every input. Known unitary gates and classical processing do not count toward this quantity; their runtime is a separate cost.

For a zero-one Boolean function, the flip-probability influence is ${\beta }_i=4{\sum }_{S\ni i}\hat{f}(S{)}^2$. Apply Beckner's inequality with noise parameter $\sqrt{\delta }$ to the discrete derivative of a Boolean function, whose nonzero magnitude is $1/2$. Its $L^{1+\delta }$ norm squared is ${\beta }_i^{2/(1+\delta )}/4$. Summing over coordinates gives the displayed weighted Fourier weight bound, a useful intermediate step in influence lower bounds.

For a Boolean function $f:\{0,1{\}}^n\to \{0,1\}$ under the uniform probability measure, some coordinate has influence of a variable at least $c\mathrm{Var}(f)\log (n)/n$, where $c>0$ is an absolute constant and $I_i(f)$ is the probability that flipping coordinate $i$ changes $f$. For variance bounded below, this is order $\log (n)/n$. The tribes function shows that this order cannot be improved for general balanced Boolean functions.