switching circuit theory
{{Use dmy dates|date=October 2022|cs1-dates=y}}
{{use list-defined references|date=September 2022}}
Switching circuit theory is the mathematical study of the properties of networks of idealized switches. Such networks may be strictly combinational logic, 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 machines. 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 design in almost all areas of modern technology.
In an 1886 letter, Charles Sanders Peirce 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 gates, 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; 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 systems.
Eventually, vacuum tubes replaced relays for logic operations. Lee De Forest's modification, in 1907, of the Fleming valve can be used as a logic gate. Ludwig Wittgenstein introduced a version of the 16-row truth table as proposition 5.101 of Tractatus Logico-Philosophicus (1921). Walther Bothe, inventor of the coincidence circuit, got part of the 1954 Nobel Prize in physics, for the first modern electronic AND gate in 1924. Konrad Zuse designed and built electromechanical logic gates for his computer Z1 (from 1935 to 1938).
The theory was independently established through the works of NEC engineer Akira Nakashima in Japan, Claude Shannon in the United States, and Victor Shestakov in the Soviet Union. The three published a series of papers showing that the two-valued Boolean algebra, can describe the operation of switching circuits. However, Shannon's work has largely overshadowed the other two, and despite some scholars arguing the similarities of Nakashima's work to Shannon's, their approaches and theoretical frameworks were markedly different.{{Cite journal |last=Kawanishi |first=Toma |date=2019 |title=Prehistory of Switching Theory in Japan: Akira Nakashima and His Relay-circuit Theory |url=https://www.jstage.jst.go.jp/article/historiascientiarum/29/1/29_136/_article |journal=Historia Scientiarum |series=Second Series |volume=29 |issue=1 |pages=136–162 |doi=10.34336/historiascientiarum.29.1_136}} Also implausible is that Shestakov's influenced the other two due to the language barriers and the relative obscurity of his work abroad. Furthermore, Shannon and Shestakov defended their theses the same year in 1938,{{Cite book |last=Moisil |first=GR. C. |author-link=Grigore Moisil |url=https://books.google.com/books?id=tn7iBQAAQBAJ&dq=claude+shannon+shestakov&pg=PA17 |title=The Algebraic Theory of Switching Circuits |publisher=Pergamon Press |year=1969 |isbn=9781483160764 |pages=12, 17 |language=en}} and Shestakov did not publish until 1941.
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" where the output state changes due to the different propagation times through the network.
See also
- Circuit switching
- Message switching
- Packet switching
- Fast packet switching
- Network switching subsystem
- 5ESS Switching System
- Number One Electronic Switching System
- Boolean circuit
- C-element
- Circuit complexity
- Circuit minimization
- Karnaugh map
- Logic design
- Logic gate
- Logic in computer science
- Nonblocking minimal spanning switch
- Programmable logic controller – computer software mimics relay circuits for industrial applications
- Quine–McCluskey algorithm
- Relay – an early kind of logic device
- Switching lemma
- Unate function
References
{{reflist|refs=
{{cite book |author-last=Peirce |author-first=Charles Sanders |author-link=Charles Sanders Peirce |chapter=Letter, Peirce to A. Marquand |orig-date=1886 |title=Writings of Charles S. Peirce |volume=5 |date=1993 |pages=421–423}} See also: {{cite journal |author-first=Arthur Walter |author-last=Burks |author-link=Arthur Walter Burks |title=Review: Charles S. Peirce, The new elements of mathematics |type=review |journal=Bulletin of the American Mathematical Society |volume=84 |number=5 |date=1978 |pages=913–918 [917] |doi=10.1090/S0002-9904-1978-14533-9 |url=http://projecteuclid.org/DPubS/Repository/1.0/Disseminate?view=body&id=pdf_1&handle=euclid.bams/1183541145|doi-access=free }}
{{cite book |author-last=Peirce |author-first=Charles Sanders |author-link=Charles Sanders Peirce |type=manuscript |orig-date=Winter of 1880–1881 |chapter=A Boolian Algebra with One Constant |date=1933 |title=Collected Papers |volume=4 |at=paragraphs 12–20}} Reprinted in {{cite book |title=Writings of Charles S. Peirce |id=ark:/13960/t11p5r61f |date=1989 |edition=reprint |volume=4 |pages=218–221 |isbn=9780253372017 |url=https://archive.org/details/writingsofcharle0002peir/page/218}} See also: {{cite book |author-last=Roberts |author-first=Don D. |date=2009 |title=The Existential Graphs of Charles S. Peirce |page=131}}
{{cite book |author-first1=Hans |author-last1=Kleine Büning |author-first2=Theodor |author-last2=Lettmann |title=Propositional logic: deduction and algorithms |url=https://books.google.com/books?id=3oJE9yczr3EC&pg=PA2 |date=1999 |publisher=Cambridge University Press |isbn=978-0-521-63017-7 |page=2}}
{{cite book |author-first=John |author-last=Bird |title=Engineering mathematics |url=https://books.google.com/books?id=1-fBmsEBNUoC&pg=PA532 |date=2007 |publisher=Newnes |isbn=978-0-7506-8555-9 |page=532}}
{{cite journal |title=History of Research on Switching Theory in Japan |author-first=Akihiko [彰彦] |author-last=Yamada [山田] |journal=IEEJ Transactions on Fundamentals and Materials |volume=124 |date=2004 |issue=8 |pages=720–726 |publisher=Institute of Electrical Engineers of Japan |doi=10.1541/ieejfms.124.720 |bibcode=2004IJTFM.124..720Y |doi-access=free |url=https://www.jstage.jst.go.jp/article/ieejfms/124/8/124_8_720/_article |access-date=2022-10-26 |url-status=live |archive-url=https://web.archive.org/web/20220710005644/https://www.jstage.jst.go.jp/article/ieejfms/124/8/124_8_720/_pdf/-char/en |archive-date=2022-07-10}}
{{cite web |title=Switching Theory/Relay Circuit Network Theory/Theory of Logical Mathematics |date=2012 |work=IPSJ Computer Museum |publisher=Information Processing Society of Japan |url=http://museum.ipsj.or.jp/en/computer/dawn/0002.html |access-date=2021-03-28 |url-status=live |archive-url=https://web.archive.org/web/20210322042200/http://museum.ipsj.or.jp/en/computer/dawn/0002.html |archive-date=2021-03-22}}
{{cite book |editor-first1=Radomir S. |editor-last1=Stanković |editor-link1=:de:Radomir S. Stanković |editor-first2=Jaakko Tapio |editor-last2=Astola |editor-link2=:fi:Jaakko Tapio Astola |date=2008 |isbn=978-952-15-1980-2 |issn=1456-2774 |volume=40 |issue=2 |url=http://ticsp.cs.tut.fi/reports/reprint-nakashima-rr.pdf |title=Reprints from the Early Days of Information Sciences: TICSP Series on the Contributions of Akira Nakashima to Switching Theory |series=Tampere International Center for Signal Processing (TICSP) Series |location=Tampere University of Technology, Tampere, Finland |url-status=dead |archive-url=https://web.archive.org/web/20210308002559/http://ticsp.cs.tut.fi/reports/reprint-nakashima-rr.pdf |archive-date=2021-03-08}} (3+207+1 pages) [https://web.archive.org/web/20221026175726/http://ciitlab.elfak.ni.ac.rs/predavanja/09_Nakashima.mp4 10:00 min]
{{cite journal |title=Theory of Relay Circuit Composition |author-first=Akira |author-last=Nakashima |author-link=Akira Nakashima |journal=Nippon Electrical Communication Engineering |number=3 |date=May 1936 |pages=197–226}} (NB. Translation of an article which originally appeared in Japanese in the Journal of the Institute of Telegraph and Telephone Engineers of Japan (JITTEJ) September 1935, 150 731–752.)
{{cite journal |author-last=Shannon |author-first=Claude Elwood |author-link=Claude Elwood Shannon |title=A Symbolic Analysis of Relay and Switching Circuits |journal=Transactions of the American Institute of Electrical Engineers |publisher=American Institute of Electrical Engineers (AIEE) |date=1938 |volume=57 |issue=12 |doi=10.1109/T-AIEE.1938.5057767 |s2cid=51638483 |hdl=1721.1/11173 |hdl-access=free |pages=713–723}} (NB. Based on Shannon's master thesis of the same title at Massachusetts Institute of Technology in 1937.)
{{cite book |script-title=ru:Некоторые математические методы кон-струирования и упрощения двухполюсных электрических схем класса А |language=ru |trans-title=Some mathematical methods for the construction and simplification of two-terminal electrical networks of class A |author-first=Victor Ivanovich [Виктор Иванович] |author-last=Shestakov [Шестаков] |author-link=Victor Ivanovich Shestakov |type=PhD thesis |publisher=Lomonosov State University |date=1938}}
{{cite book |title=Introduction to the Methodology of Switching Circuits |chapter=Reference Notations to Chapter 1 |author-first=George Jiří |author-last=Klir |author-link=George Jiří Klir |edition=1 |date=May 1972 |lccn=72-181095 |isbn=0-442-24463-0 |id=C4463-000-3 |publisher=Litton Educational Publishing, Inc. / D. van Nostrand Company |location=Binghamton, New York, USA |page=19 |quote-page=19 |quote=Although the possibility of establishing a switching theory was recognized by M. Boda{{citeref|Boda|1898|A}} as early as in the 19th century, the first important works on this subject were published by A. Nakashima{{citeref|Nakashima|1936|B}} and C. E. Shannon{{citeref|Shannon|1938|C}} shortly before World War II.}} (xvi+573+1 pages)
}}
Further reading
- {{cite book |title=The Design of Switching Circuits |author-first1=William |author-last1=Keister |author-first2=Alistair E. |author-last2=Ritchie |author-first3=Seth H. |author-last3=Washburn |date=1951 |edition=1 |publisher=D. Van Nostrand Company, Inc. |series=The Bell Telephone Laboratories Series |page=[https://archive.org/details/TheDesignOfSwitchingCircuits/page/n170 147] |url=https://archive.org/details/TheDesignOfSwitchingCircuits |access-date=2020-05-09 |url-status=live |archive-url=https://web.archive.org/web/20200509143306/https://archive.org/details/TheDesignOfSwitchingCircuits/page/n537/mode/2up |archive-date=2020-05-09}} [https://archive.org/details/TheDesignOfSwitchingCircuits] (2+xx+556+2 pages)
- {{cite book |title=Switching Circuits and Logical Design |author-first=Samuel Hawks |author-last=Caldwell |author-link=Samuel Hawks Caldwell |version=5th printing September 1963 |date=1958-12-01 |orig-date=February 1958 |edition=1st |publisher=John Wiley & Sons Inc. |publication-place=New York, USA |location=Watertown, Massachusetts, USA |isbn=0-47112969-0 |lccn=58-7896}} (xviii+686 pages)
- {{cite book |title=A Survey of Literature on Function Decomposition |chapter=6. Historical Overview of the Research on Decomposition |version=Version IV |author-first1=Marek A. |author-last1=Perkowski |author-first2=Stanislaw |author-last2=Grygiel |publisher=Functional Decomposition Group, Department of Electrical Engineering, Portland University, Portland, Oregon, USA |date=1995-11-20 |citeseerx=10.1.1.64.1129 |url=http://web.cecs.pdx.edu/~mperkows/=PUBLICATIONS/PER/G1995/survey.pdf |access-date=2021-03-28 |url-status=live |archive-url=https://web.archive.org/web/20210328181709/http://web.cecs.pdx.edu/~mperkows/=PUBLICATIONS/PER/G1995/survey.pdf |archive-date=2021-03-28}} (188 pages)
- {{cite web |title=Publications in the First Twenty Years of Switching Theory and Logic Design |author-first1=Radomir S. |author-last1=Stanković |author-link1=:de:Radomir S. Stanković |author-first2=Tsutomu |author-last2=Sasao |author-first3=Jaakko Tapio |author-last3=Astola |author-link3=:fi:Jaakko Tapio Astola |series=Tampere International Center for Signal Processing (TICSP) Series |id=#14 |issn=1456-2774 |location=Tampere University of Technology / TTKK, Monistamo, Finland |date=August 2001 |s2cid=62319288 |url=http://ticsp.cs.tut.fi/images/a/a5/Stari-radovi-report.pdf |access-date=2021-03-28 |url-status=dead |archive-url=https://web.archive.org/web/20170809064702/http://ticsp.cs.tut.fi/images/a/a5/Stari-radovi-report.pdf |archive-date=2017-08-09}} (4+60 pages)
- {{cite book |title=From Boolean Logic to Switching Circuits and Automata: Towards Modern Information Technology |author-first1=Radomir S. |author-last1=Stanković |author-link1=:de:Radomir S. Stanković |author-first2=Jaakko Tapio |author-last2=Astola |author-link2=:fi:Jaakko Tapio Astola |series=Studies in Computational Intelligence |volume=335 |date=2011 |edition=1 |publisher=Springer-Verlag |location=Niš, Serbia & Tampere, Finland |publication-place=Berlin & Heidelberg, Germany |isbn=978-3-642-11681-0 |doi=10.1007/978-3-642-11682-7 |issn=1860-949X |lccn=2011921126 |url=https://books.google.com/books?id=ZuHwCAAAQBAJ |access-date=2022-10-25}} (xviii+212 pages)
{{Digital electronics}}