bits.

FREE CONTRIBUTION CHRONOLOGY · 1937

Logic becomes circuit

Why can an algebraic expression become a physical switching network?

The historical question

Shannon mapped relay networks to Boolean algebra, allowing designers to prove that circuits were equivalent, simplify them symbolically, and then rebuild a cheaper mechanism.

A physical system becomes designable when an abstract algebra preserves exactly the behavior engineers need to compose.

An ideal-switch model

Represent a closed switch by true and an open switch by false. Two ideal switches in series conduct only when both are closed, corresponding to AND. Parallel branches conduct when either branch is closed, corresponding to OR. This abstraction preserves a useful property, connectivity, while ignoring transient behavior and physical component details.

Consider branches AB and A¬B in parallel. Algebra gives AB OR A¬B = A(B OR ¬B) = A. The network’s stable truth table therefore matches a single A-controlled path. Verify the four combinations of A and B: both implementations conduct exactly when A is true. The identity tells a designer what can be simplified under the model.

A physical circuit introduces further obligations. Switches take time, contacts can bounce, and a logical complement may require a distinct arrangement. Two logically equivalent networks can differ in delay, power, or transient glitches. Shannon’s contribution supports systematic analysis through a model, not the claim that physical behavior and algebra are literally identical in every respect. Correct engineering names which properties the abstraction preserves and which require another analysis.

What the evidence does not establish

Boolean equivalence preserves logic but hides timing, noise, energy, fan-out, and manufacturing variation.

Reconstruction exercise

Simplify (A AND B) OR (A AND NOT B), then explain why matching stable truth tables does not prove equal propagation delay.

Worked solution

Factor A to obtain A AND (B OR NOT B), which simplifies to A. The truth table covers stable input-output relationships; it has no time coordinate. Gate or relay count, topology, and device delays affect propagation. A timed model or measurement is needed to compare those behaviors. This is an example of a valid proof with a deliberately limited claim.

Test the limits and transfer the idea

1. Timing trace · allow 30 minutes

A stable truth table hides a transient pulse

An idealized circuit computes F=(A AND B) OR ((NOT A) AND C). Let B=C=1 and let A fall from 1 to 0 at time 0. Each AND and OR gate has a transport delay of 1 ns; NOT has delay 3 ns. Before time 0 the circuit is stable. Trace both AND outputs and F. Show why adding the consensus term B AND C preserves the stable Boolean function while preventing this particular low pulse under the stated model.

Get a starting hint

The old conducting path can disappear before the new path appears.

Compare your reasoning with the worked solution

A AND B falls at 1 ns. NOT A rises at 3 ns, so its AND with C rises at 4 ns. The OR therefore sees both inputs low from 1 to 4 ns, and F falls at 2 ns then rises at 5 ns: a three-nanosecond low pulse. The stable function should remain one because B=C=1. Adding BC keeps one OR input high through this transition. The term is Boolean-redundant: if B=C=1, either A or NOT A already makes an existing branch true; otherwise BC is zero. Thus algebraic redundancy can improve this timing property. The construction uses a stipulated transport-delay model, not Shannon's original hardware, and does not prove freedom from every hazard, load effect or manufacturing variation.

Check your reasoning

  • Finds AND transitions at 1 and 4 ns and output pulse from 2 to 5.
  • Proves consensus-term Boolean redundancy.
  • Limits the hazard claim to the stated transition and model.

2. Truth-table proof and boundary · allow 30 minutes

Prove a full-adder bit without proving a whole chip

A one-bit adder has inputs A,B,Cin. Define Sum=A XOR B XOR Cin and Cout=(A AND B) OR (Cin AND (A XOR B)). Verify all eight inputs and show that A+B+Cin=Sum+2Cout as ordinary integers. Then explain two extra obligations before chaining 32 such cells into a reliable physical adder. Distinguish this teaching construction from the historical claim established by Shannon's switching paper.

Get a starting hint

Group inputs by the number of ones, but also verify the particular carry expression.

Compare your reasoning with the worked solution

For inputs 000,001,010,011,100,101,110,111, the (Sum,Cout) pairs are (0,0),(1,0),(1,0),(0,1),(1,0),(0,1),(0,1),(1,1). They represent totals 0,1,1,2,1,2,2,3. Cout is true when both A and B are one or exactly one is one and Cin is one, matching the at-least-two condition. A chain additionally needs carry propagation to settle before sampling and electrical interfaces that preserve valid levels under load and noise. The final carry and signed-overflow interpretation also require an architectural contract. Shannon's primary work supports symbolic analysis of switching networks; the modern 32-bit physical design requires device, timing and verification evidence beyond a Boolean identity.

Check your reasoning

  • Checks all eight cases and the arithmetic identity.
  • Explains the carry expression rather than relying only on a table.
  • Identifies timing and electrical obligations beyond Boolean correctness.

Check your understanding

What does the Boolean equivalence establish?

  • Equal energy consumption
  • Equal physical construction
  • Equal stable logical outputs under the model
Explanation

Factor A to obtain A AND (B OR NOT B), which simplifies to A. The truth table covers stable input-output relationships; it has no time coordinate. Gate or relay count, topology, and device delays affect propagation. A timed model or measurement is needed to compare those behaviors. This is an example of a valid proof with a deliberately limited claim.

Sources and further reading