Realization of All 16 Switching Functions of Two Variables Requires 18 Contacts Case 320878; MM-53-1400-40
Murray Hill, N. J. Bell Telephone Laboratories, Incorporated November 17, 1953. [1-cover sheet], [1]-4 leaves + 1 plate leaf containing two figures. Mimeographed typescript. Stapled upper left. 10 7/8 x 8 3/8 inches. Plate slightly larger at 11 x 8 1/2 inches. Memorandum signed in type on last page "C. E. Shannon" with "Att: BA359949" on the last line. The plate is yellowed with purple (?) ink, with "BA-359949" printed upper right. Lower right in plate leaf is "C.E.S. DTA, Nov. 18, 1953" On the rear of the plate is inked stamp consisting of 4 concentric circles, and "PRINTED MAR. 25, 1954 MURRAY HILL" Filing Subject is "Switching Theory" Very Good. Wraps. [28641]
"The following theorem is proved: A necessary and sufficient number of contacts to simultaneously realize all 16 switching functions of two variables is 18." (abstract)
This paper optimizes a 1949 paper that used 20 contacts instead of the 18 proved here. Credit was given to an M.I.T. Switching Course student who discovered the circuit shown in Fig. 1. The paper further provides proof it cannot be done any more efficiently. These optimizations were important because they provided a theoretical "best case" for engineers looking to build physical machines with the least number of components.
PROVENANCE: The personal files of Claude E. Shannon (unmarked). The only copy in Shannon's files.
REFERENCES:
Sloane and Wyner, "Claude Elwood Shannon Collected Papers," #83
ITEM SOLD