---
title: "The Synthesis of Two-Terminal Switching Circuits"
authors:
  - "Claude E. Shannon"
year: 1949
venue: "Bell System Technical Journal"
arxiv: null
doi: "10.1002/j.1538-7305.1949.tb03624.x"
source: "https://doi.org/10.1002/j.1538-7305.1949.tb03624.x"
topics:
  - switching-theory
  - circuit-complexity
  - shannon
seed_rank: 557
seed_batch: "foundations-greats-2026-08-13"
reviewed: "2026-08-13"
pool: "systems"
relevance_score: 8
lineage: foundations-of-computing
cites:
  - title: "A Symbolic Analysis of Relay and Switching Circuits"
    url: "https://doi.org/10.1109/T-AIEE.1938.5057767"
    year: 1938
    arxiv: null
    doi: "10.1109/T-AIEE.1938.5057767"
see:
  - "552-a-symbolic-analysis-of-relay-and-switching-circuits"
---

# The Synthesis of Two-Terminal Switching Circuits

## One-sentence takeaway

Shannon proves almost all Boolean functions need exponentially many contacts and gives constructive upper bounds for two-terminal networks.

## Why it matters here

This is circuit complexity before the name existed: gate-count lower bounds for the same Boolean surfaces the engine later compiles into shaders and ECS filters.

## Key ideas

- A random n-variable function almost surely requires on the order of \(2^n/n\) contacts; most functions are hard.
- Explicit series-parallel and bridge constructions give matching-order upper bounds for the worst case.
- Two-terminal (one-input, one-output) networks are the object of study, continuing the 1938 relay algebra.
- Disjunctive and conjunctive decompositions, and contact sharing, are the synthesis toolkit.
- The paper is the quantitative sequel to the qualitative Boolean-relay identification.

## Caveats

## Links

- DOI: [10.1002/j.1538-7305.1949.tb03624.x](https://doi.org/10.1002/j.1538-7305.1949.tb03624.x)
- URL: https://doi.org/10.1002/j.1538-7305.1949.tb03624.x