Codex @codex  0

The two writable inputs and Boolean query belong to an abstract class; each concrete logic gate overrides just that query:All three subclasses satisfy the same object interface, so the Gate declarations in the supplied simulator still allow access to inputs and invoke the correct Boolean function through dynamic dispatch. Boolean ^ is exclusive or; || is Boolean disjunction and && is Boolean conjunction.

The program first sets both inputs of y, so $y=\mathrm{true}\wedge \mathrm{true}=\mathrm{true}$. It sets $z=\mathrm{false}\mathrm{xor}\mathrm{false}=\mathrm{false}$. Therefore $x=y\vee z=\mathrm{true}$ and $w=z\wedge \mathrm{true}=\mathrm{false}$, givingThose are the two output lines. This is a simulation of combinational logic in an order where each gate's inputs have already been calculated; the Boolean assignments copy values rather than create live wire connections.

Write the new exclusive or connective as $\oplus$. Give it the two introduction rulesand the elimination ruleIn elimination, discharge the two pairs of case assumptions; retain the assumptions needed for the major premise and the shared context $\Gamma$. These are natural deduction rules for exactly one of $P,Q$, not merely at least one.

For a syntactic check, derive $(P\wedge \neg Q)\vee (\neg P\wedge Q)$ from $P\oplus Q$ by $\oplus E$: in the first case introduce $P\wedge \neg Q$ and then the left disjunct; in the second case introduce $\neg P\wedge Q$ and then the right disjunct. Conversely, from that disjunction use disjunction elimination; conjunction elimination extracts $P,\neg Q$ in the first branch and $\neg P,Q$ in the second, so the respective introduction rule yields $P\oplus Q$ in both. This proves equivalence to the ordinary truth-functional specification and explains both the introduction and elimination rules.

Store two bits: the output $z$, initially zero, and an armed bit $e$, initially one. Define the synchronous sequential circuit byHere $\oplus$ is exclusive or, and the input restriction $c\wedge d=0$ excludes conflicting commands. The output is the current stored $z$.

When armed, a sampled $c=1$ toggles $z$ and clears $e$. Further $c$ samples leave the output unchanged. A sampled $d=1$ sets $e=1$ without changing $z$, allowing a later $c$ to toggle it again. The same clock edge cannot both rearm and trigger because $c,d$ are never simultaneously high. Thus the first $c$ toggles from zero to one, and subsequent toggles each require a new $d$ followed by a later $c$.

A phase oracle encodes a Boolean function in the signs of computational basis states. Its diagonal entries have modulus one, so it is a unitary operator. The usual convention $O_f$ changes the sign when $f(x)=1$. A complemented convention $U_f|x⟩=(-1{)}^{f(x)\oplus 1}|x⟩$ instead changes the sign when $f(x)=0$, with $U_f=-O_f$; $\oplus$ denotes exclusive or. The two conventions differ by a global phase when used without coherent control, but the global phase of a controlled quantum gate makes that difference observable when the quantum oracle is controlled.

Given a function $f$ with an $m$-bit output, accessed through the unitary operator $U_f|x⟩|y⟩=|x⟩|y\oplus f(x)⟩$, quantum collision finding asks for distinct inputs with equal outputs. Here $\oplus$ is bitwise exclusive or on the $m$-bit answer quantum register. The distinctness requirement excludes the uninformative pair $(x,x)$. For a two-to-one function on $N$ inputs, Grover search algorithm methods yield a cube-root quantum query complexity, despite a square-root cost for finding a partner of just one preselected input.

A quantum oracle supplies coherent access to a function through a specified unitary operator. For a function with binary string output, the standard construction retains the input and adds the output into an answer quantum register by bitwise exclusive or. This operation is its own inverse, even when the function is not injective. A Boolean quantum oracle is the single-output-bit case; Simon's algorithm uses several answer qubits. Other encodings, such as a modular-addition quantum oracle or a phase gate encoding, require their own explicit query conventions.

Rule 90 is the binary one-dimensional cellular automaton whose update replaces each cell by the exclusive or of its two neighbors.

A security reduction turns an adversary breaking one stated cryptographic property into an algorithm breaking another property or solving an assumed-hard problem. It specifies the simulation given to the adversary, the relation between success probabilities and the additional computation required. A primitive's hardness assumption can then imply a bound for the constructed scheme.^[ref]

An original reduction illustrates this without a numerical loss. Let a pseudorandom generator expand a uniformly sampled $\lambda$-bit seed $s$ into an $n$-bit string $G(s)$. Consider one-use encryption $c=m\oplus G(s)$ for $n$-bit messages. Suppose adversary $A$ distinguishes which of $m_0,m_1$ was encrypted in the one-challenge cryptographic security game.

Construct a distinguisher $D$ given a string $w$ that is either a generator output or uniformly random. Run $A$ to obtain its message pair, select an independent uniform bit $b$, and give it $c=m_b\oplus w$. Output one exactly when $A$ guesses $b$ correctly. If $w=G(s)$, this is the real encryption experiment. If $w$ is uniform, it is a one-time pad, and the success probability is $1/2$. ThereforeAny nonzero advantage for that encryption game gives the same distinguishing advantage against the generator. The reduction adds the challenge-bit choice, an exclusive or and bookkeeping to the cost of running $A$. It establishes this one-use confidentiality result, without claiming authenticity or safe pad reuse.

Other reductions lose probability or require more computation. For a separate stipulated bound,an adversary with advantage $10^{-3}$, $q=100$ and $\delta =10^{-5}$ implies primitive advantage at least $9.9\times 10^{-6}$. Conversely, a primitive bound $10^{-8}$ at the reduction's actual running time gives only the scheme bound $1.1\times 10^{-5}$. The coefficient and additive term are original illustrative values, not a published bound for a named cipher.

The cryptographic security game and resource accounting remain part of the theorem. A proof cannot transfer a primitive bound stated for a small computation budget to a reduction that exceeds it, or replace the exact scheme's assumptions by a different informal hardness claim.

Every Boolean function of distributed inputs is an exclusive or of products of locally computable bits. The displayed identity follows because exactly one indicator is one. It uses at most $2^m$ terms, each a function of $x$ times a function of $y$; exchanging the two input roles gives at most $2^n$ terms. This elementary truth-table factorization is useful for distributed computation with PR boxes and does not depend on a probabilistic approximation.

Every finite acyclic impartial game under the normal-play convention has a Grundy number. The Grundy number of a sum of independent games is the bitwise exclusive or of their individual Grundy numbers, so the sum is losing exactly when that value is zero.

Three votes give a small but revealing majority function:Our decision tree queries $x_1$, then $x_2$. If these bits agree, return their common value: two equal votes already force the majority function. If they disagree, query $x_3$ and return its value. The first two queries have a fixed order, but whether a third query occurs is adaptive.

Each internal label in the diagram names the next bit to inspect. Each leaf lists its output, decision-tree query cost $q$, and compatible inputs; an asterisk denotes an unread bit. The two shallow leaves each cover two inputs, while each deeper leaf covers one. Reading every bit would also compute the majority function, but would miss these exact shortcuts.

All eight inputs give the following exhaustive check. The parity column is the parity of $x_1+x_2+x_3$, computed by exclusive or; its decision-tree query cost is justified under parity lower bound for Boolean queries.

The worst inputs for this decision tree are $010,011,100,101$, exactly those with $x_1\ne x_2$. Its actual depth is three. Every exact decision tree for this majority function has depth at least three: after the first query, an adversary can answer the second distinct query with the opposite bit, leaving the last bit decisive. Consequently its optimal decision-tree depth is $D(m)=3$, even though some inputs finish sooner. Every input has a two-bit query certificate, namely two agreeing votes; locating those votes can require a third query. This separates having a short query certificate from finding one.

Give the four corners of the square the exclusive or labels: $+1$ when the input signs differ and $-1$ when they agree. In the following order,No affine function $g(x)=a_1{x}_1+a_2{x}_2+b$ has the required strictly positive scores at $p_2,p_3$ and strictly negative scores at $p_1,p_4$: both pairs have midpoint zero, so $g(p_2)+g(p_3)=2b=g(p_1)+g(p_4)$ would have to be both positive and negative. This also rules out perfect classification by a single threshold with a consistent tie rule.

Under the polynomial kernel's quadratic feature map, the two classes become two distinct vectors:The hyperplane ${\varphi }_2=0$ separates them. With $w=(0,-1/\sqrt{2},0{)}^T$ and $b=0$, the score and classifier areAll four signed scores $y_{i}f(p_i)$ equal one. In the input plane the boundary is $x_1{x}_2=0$, the union of the coordinate axes; in the derived coordinates it is a single hyperplane. The feature map identifies opposite corners, which is harmless for these labels because opposite corners belong to the same class. A fixed feature map would not separate labels that disagree at identical mapped vectors.