Why Do AND and OR Logic Gates Lose Information Entropy?

Standard irreversible logic gates like AND and OR inherently lose information entropy because they map multiple distinct input states to a single output state, making it impossible to reconstruct the original inputs from the output alone. In classical computing, this many-to-one mapping reduces the number of distinguishable states in a system, which directly decreases Shannon entropy and forces the erasure of at least one bit of information per operation. According to Landauer's principle, this logical irreversibility also carries a fundamental physical consequence: erasing information in a physical system necessarily dissipates heat into the surrounding environment.

Many-to-One Mapping and Logical Irreversibility

A logic gate is considered reversible if there is a one-to-one correspondence (a bijection) between its input states and its output states. For example, a single-input NOT gate is reversible because an output of \(0\) uniquely implies an input of \(1\), and an output of \(1\) uniquely implies an input of \(0\).

In contrast, standard two-input gates such as AND and OR take two input bits and produce only one output bit. Because there are \(2^2 = 4\) possible input combinations—\((0,0)\), \((0,1)\), \((1,0)\), and \((1,1)\)—and only \(2^1 = 2\) possible output values (\(0\) and \(1\)), these gates must perform a many-to-one mapping.

For an AND gate:

• An output of \(1\) uniquely identifies the input \((1,1)\).
• An output of \(0\) could have originated from \((0,0)\), \((0,1)\), or \((1,0)\).

For an OR gate:

• An output of \(0\) uniquely identifies the input \((0,0)\).
• An output of \(1\) could have originated from \((0,1)\), \((1,0)\), or \((1,1)\).

Once the output is produced and the inputs are discarded, the gate provides no way to distinguish between the three collapsed input states. That lost distinction is lost information.

Quantifying the Loss with Shannon Entropy

In information theory, the uncertainty or information content of a discrete random variable \(X\) with possible outcomes \(x_i\) and probabilities \(P(x_i)\) is measured by Shannon entropy, \(H(X)\):

\[H(X) = -\sum_{i} P(x_i) \log_2 P(x_i)\]

Suppose the two inputs \(A\) and \(B\) to an AND gate are independent and uniformly distributed, so each of the four input pairs \((A, B)\) occurs with probability \(\frac{1}{4}\). The input entropy is:

\[H(A, B) = -4 \left(\frac{1}{4} \log_2 \frac{1}{4}\right) = 2 \text{ bits}\]

After passing through the AND gate, the output \(Y\) is \(1\) with probability \(\frac{1}{4}\) and \(0\) with probability \(\frac{3}{4}\). The output entropy is:

\[H(Y) = -\left(\frac{1}{4} \log_2 \frac{1}{4} + \frac{3}{4} \log_2 \frac{3}{4}\right) \approx 0.811 \text{ bits}\]

The information entropy lost during the operation is the difference between the input and output entropies:

\[\Delta H = H(A, B) - H(Y) \approx 2 - 0.811 = 1.189 \text{ bits}\]

For an OR gate with uniform inputs, the output probabilities are swapped (\(P(Y=1) = \frac{3}{4}\) and \(P(Y=0) = \frac{1}{4}\)), yielding the exact same entropy loss of approximately \(1.189\) bits.

Physical Consequences and Landauer's Principle

Information is not purely abstract; in any physical computer, bits are stored in physical degrees of freedom such as voltages, magnetic orientations, or charge states. By the second law of thermodynamics, the total entropy of a closed physical system cannot decrease.

When a logically irreversible gate like AND or OR compresses four possible input states into two possible output states, the phase-space volume associated with the computation shrinks. To preserve the total entropy of the universe, the lost information entropy must be transferred into non-computational degrees of freedom—specifically, as thermal energy dissipated into the environment.

Landauer's principle formalizes this lower bound: erasing one bit of information at temperature \(T\) requires dissipating at least

\[E_{\text{min}} = k_B T \ln 2\]

of heat, where \(k_B\) is the Boltzmann constant. While modern silicon transistors dissipate far more energy than this theoretical minimum due to resistance and switching inefficiencies, Landauer's limit establishes that irreversible gates like AND and OR have a fundamental thermodynamic cost rooted directly in their loss of information entropy.