Switching circuit theory is the mathematical study of the properties of networks of idealized switches. Such networks may be strictly
combinational logic
In automata theory, combinational logic (also referred to as time-independent logic or combinatorial logic) is a type of digital logic which is implemented by Boolean circuits, where the output is a pure function of the present input only. This i ...
, in which their output state is only a function of the present state of their inputs; or may also contain
sequential elements, where the present state depends on the present state and past states; in that sense, sequential circuits are said to include "memory" of past states. An important class of sequential circuits are
state machine
A finite-state machine (FSM) or finite-state automaton (FSA, plural: ''automata''), finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number o ...
s. Switching circuit theory is applicable to the design of telephone systems, computers, and similar systems. Switching circuit theory provided the mathematical foundations and tools for
digital system
Digital electronics is a field of electronics involving the study of digital signals and the engineering of devices that use or produce them. This is in contrast to analog electronics and analog signals.
Digital electronic circuits are usually ...
design in almost all areas of modern technology.
In an 1886 letter,
Charles Sanders Peirce
Charles Sanders Peirce ( ; September 10, 1839 – April 19, 1914) was an American philosopher, logician, mathematician and scientist who is sometimes known as "the father of pragmatism".
Educated as a chemist and employed as a scientist for t ...
described how logical operations could be carried out by electrical switching circuits.
During 1880–1881 he showed that
NOR gates alone (or alternatively
NAND gates alone) can be used to reproduce the functions of all the other
logic gate
A logic gate is an idealized or physical device implementing a Boolean function, a logical operation performed on one or more binary inputs that produces a single binary output. Depending on the context, the term may refer to an ideal logic gate, ...
s, but this work remained unpublished until 1933.
The first published proof was by
Henry M. Sheffer in 1913, so the NAND logical operation is sometimes called
Sheffer stroke
In Boolean functions and propositional calculus, the Sheffer stroke denotes a logical operation that is equivalent to the logical negation, negation of the logical conjunction, conjunction operation, expressed in ordinary language as "not both". ...
; the
logical NOR is sometimes called ''Peirce's arrow''.
Consequently, these gates are sometimes called ''universal logic gates''.
In 1898, Martin Boda described a switching theory for
signalling block system
Signalling block systems enable the safe and efficient operation of railways by preventing collisions between trains. The basic principle is that a track is broken up into a series of sections or "blocks". Only one train may occupy a block at a ...
s.
Eventually,
vacuum tube
A vacuum tube, electron tube, valve (British usage), or tube (North America), is a device that controls electric current flow in a high vacuum between electrodes to which an electric voltage, potential difference has been applied.
The type kn ...
s replaced relays for logic operations.
Lee De Forest
Lee de Forest (August 26, 1873 – June 30, 1961) was an American inventor and a fundamentally important early pioneer in electronics. He invented the first electronic device for controlling current flow; the three-element "Audion" triode va ...
's modification, in 1907, of the
Fleming valve
The Fleming valve, also called the Fleming oscillation valve, was a thermionic valve or vacuum tube invented in 1904 by English physicist John Ambrose Fleming as a detector for early radio receivers used in electromagnetic wireless telegraphy. ...
can be used as a logic gate.
Ludwig Wittgenstein
Ludwig Josef Johann Wittgenstein ( ; ; 26 April 1889 – 29 April 1951) was an Austrian-British philosopher who worked primarily in logic, the philosophy of mathematics, the philosophy of mind, and the philosophy of language. He is considere ...
introduced a version of the 16-row
truth table
A truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, boolean functions, and propositional calculus—which sets out the functional values of logical expressions on each of their functional argumen ...
as proposition 5.101 of ''
Tractatus Logico-Philosophicus
The ''Tractatus Logico-Philosophicus'' (widely abbreviated and cited as TLP) is a book-length philosophical work by the Austrian philosopher Ludwig Wittgenstein which deals with the relationship between language and reality and aims to define the ...
'' (1921).
Walther Bothe
Walther Wilhelm Georg Bothe (; 8 January 1891 – 8 February 1957) was a German nuclear physicist, who shared the Nobel Prize in Physics in 1954 with Max Born.
In 1913, he joined the newly created Laboratory for Radioactivity at the Reich Physi ...
, inventor of the
coincidence circuit In physics and electrical engineering, a coincidence circuit or coincidence gate is an electronic device with one output and two (or more) inputs. The output activates only when the circuit receives signals within a time window accepted as ''at the ...
, got part of the 1954
Nobel Prize
The Nobel Prizes ( ; sv, Nobelpriset ; no, Nobelprisen ) are five separate prizes that, according to Alfred Nobel's will of 1895, are awarded to "those who, during the preceding year, have conferred the greatest benefit to humankind." Alfr ...
in physics, for the first modern electronic AND gate in 1924.
Konrad Zuse
Konrad Ernst Otto Zuse (; 22 June 1910 – 18 December 1995) was a German civil engineer, pioneering computer scientist, inventor and businessman. His greatest achievement was the world's first programmable computer; the functional program-c ...
designed and built electromechanical logic gates for his computer
Z1 (from 1935 to 1938).
From 1934 to 1936,
NEC
is a Japanese multinational information technology and electronics corporation, headquartered in Minato, Tokyo. The company was known as the Nippon Electric Company, Limited, before rebranding in 1983 as NEC. It provides IT and network soluti ...
engineer
Akira Nakashima
Akira Nakashima (中嶋 章 or 中島 章, also written as ''Nakashima Akira'', ''Nakasima Akira'' or ''Nakajima Akira'', 5 January 1908 – 29 October 1970) was a Japanese electrical engineer of the NEC.
He got a bachelor's degree in electri ...
,
Claude Shannon
Claude Elwood Shannon (April 30, 1916 – February 24, 2001) was an American people, American mathematician, electrical engineering, electrical engineer, and cryptography, cryptographer known as a "father of information theory".
As a 21-year-o ...
and
Victor Shestakov
Victor Ivanovich Shestakov (Russian: ) (1907–1987) was a Russians, Russian/Soviet Union, Soviet logician and theoretician of electrical engineering. In 1935 he discovered the possible interpretation of Boolean algebra (logic), Boolean algebra of ...
published a series of papers showing that the
two-valued Boolean algebra, which they discovered independently, can describe the operation of switching circuits.
Ideal switches are considered as having only two exclusive states, for example, open or closed. In some analysis, the state of a switch can be considered to have no influence on the output of the system and is designated as a "don't care" state. In complex networks it is necessary to also account for the finite switching time of physical switches; where two or more different paths in a network may affect the output, these delays may result in a
"logic hazard" or "
race condition
A race condition or race hazard is the condition of an electronics, software, or other system where the system's substantive behavior is dependent on the sequence or timing of other uncontrollable events. It becomes a bug when one or more of t ...
" where the output state changes due to the different propagation times through the network.
See also
*
Circuit switching
Circuit switching is a method of implementing a telecommunications network in which two network nodes establish a dedicated communications channel ( circuit) through the network before the nodes may communicate. The circuit guarantees the full b ...
*
Message switching In telecommunications, message switching involves messages routed in their entirety, one hop at a time. It evolved from circuit switching and was the precursor of packet switching.
History
Western Union operated a message switching system, Plan ...
*
Packet switching
In telecommunications, packet switching is a method of grouping Data (computing), data into ''network packet, packets'' that are transmitted over a digital Telecommunications network, network. Packets are made of a header (computing), header and ...
*
Fast packet switching In telecommunications, fast packet switching is a variant of packet switching that increases the throughput by eliminating overhead associated with flow control and error correction functions, which are either offloaded to upper layer networking p ...
*
Network switching subsystem
Network switching subsystem (NSS) (or GSM core network) is the component of a GSM system that carries out call out and mobility management functions for mobile phones roaming on the network of base stations. It is owned and deployed by mobi ...
*
5ESS Switching System
*
Number One Electronic Switching System
The Number One Electronic Switching System (1ESS) was the first large-scale stored program control (SPC) telephone exchange or electronic switching system in the Bell System. It was manufactured by Western Electric and first placed into servi ...
*
Boolean circuit
In computational complexity theory and circuit complexity, a Boolean circuit is a mathematical model for combinational digital logic circuits. A formal language can be decided by a family of Boolean circuits, one circuit for each possible input ...
*
C-element
In digital computing, the Muller C-element (C-gate, hysteresis flip-flop, coincident flip-flop, or two-hand safety circuit) is a small binary logic circuit widely used in design of asynchronous circuits and systems. It outputs 0 when all in ...
*
Circuit complexity
In theoretical computer science, circuit complexity is a branch of computational complexity theory in which Boolean functions are classified according to the size or depth of the Boolean circuits that compute them. A related notion is the circui ...
*
Circuit minimization
Logic optimization is a process of finding an equivalent representation of the specified logic circuit under one or more specified constraints. This process is a part of a logic synthesis applied in digital electronics and integrated circuit de ...
*
Karnaugh map
The Karnaugh map (KM or K-map) is a method of simplifying Boolean algebra expressions. Maurice Karnaugh introduced it in 1953 as a refinement of Edward W. Veitch's 1952 Veitch chart, which was a rediscovery of Allan Marquand's 1881 ''logica ...
*
Logic design
In computer engineering, logic synthesis is a process by which an abstract specification of desired circuit behavior, typically at register transfer level (RTL), is turned into a design implementation in terms of logic gates, typically by a comp ...
*
Logic gate
A logic gate is an idealized or physical device implementing a Boolean function, a logical operation performed on one or more binary inputs that produces a single binary output. Depending on the context, the term may refer to an ideal logic gate, ...
*
Logic in computer science
Logic in computer science covers the overlap between the field of logic and that of computer science. The topic can essentially be divided into three main areas:
* Theoretical foundations and analysis
* Use of computer technology to aid logicians ...
*
Nonblocking minimal spanning switch
A nonblocking minimal spanning switch is a device that can connect N inputs to N outputs in any combination. The most familiar use of switches of this type is in a telephone exchange. The term "non-blocking" means that if it is not defective, i ...
*
Programmable logic controller
A programmable logic controller (PLC) or programmable controller is an industrial computer that has been ruggedized and adapted for the control of manufacturing processes, such as assembly lines, machines, robotic devices, or any activity tha ...
– computer software mimics relay circuits for industrial applications
*
Quine–McCluskey algorithm
The Quine–McCluskey algorithm (QMC), also known as the method of prime implicants, is a method used for minimization of Boolean functions that was developed by Willard V. Quine in 1952 and extended by Edward J. McCluskey in 1956. As a gener ...
*
Relay
A relay
Electromechanical relay schematic showing a control coil, four pairs of normally open and one pair of normally closed contacts
An automotive-style miniature relay with the dust cover taken off
A relay is an electrically operated switch ...
– an early kind of logic device
*
Switching lemma In computational complexity theory, Håstad's switching lemma is a key tool for proving lower bounds on the size of constant-depth Boolean circuits.
Using the switching lemma, showed that Boolean circuits of depth ''k'' in which only AND, OR, and N ...
*
Unate function A unate function is a type of boolean function which has monotonic properties.
They have been studied extensively in switching theory.
A function f(x_1,x_2,\ldots,x_n) is said to be positive unate in x_i
if for all possible values of x_j, j\neq i
...
References
Further reading
*
(2+xx+556+2 pages)
* (xviii+686 pages)
* (188 pages)
* (4+60 pages)
* (xviii+212 pages)
{{Digital electronics
Circuit complexity
Digital circuits
Digital electronics