This article includes a list of general references, but it lacks sufficient corresponding inline citations .(November 2014) |
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. [1]
In an 1886 letter, Charles Sanders Peirce described how logical operations could be carried out by electrical switching circuits. [2] 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. [3] 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. [4] Consequently, these gates are sometimes called universal logic gates. [5]
In 1898, Martin Boda described a switching theory for signalling block systems. [6] [7]
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, [8] Claude Shannon in the United States, [9] and Victor Shestakov in the Soviet Union. [10] The three published a series of papers showing that the two-valued Boolean algebra, can describe the operation of switching circuits. [7] [11] [12] [13] [1] 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. [14] Also implausible is that Shestakov's influenced the other two due to the language barriers and the relative obscurity of his work abroad. [14]
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.
The bit is the most basic unit of information in computing and digital communications. The name is a portmanteau of binary digit. The bit represents a logical state with one of two possible values. These values are most commonly represented as either "1" or "0", but other representations such as true/false, yes/no, on/off, or +/− are also widely used.
Claude Elwood Shannon was an American mathematician, electrical engineer, computer scientist and cryptographer known as the "father of information theory" and as the "father of the Information Age". Shannon was the first to describe the Boolean gates that are essential to all digital electronic circuits, and also created the first machine learning device. He is credited alongside George Boole for laying the foundations of the Information Age.
A logic gate is a device that performs 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, one that has, for instance, zero rise time and unlimited fan-out, or it may refer to a non-ideal physical device.
George BooleJnr was a largely self-taught English mathematician, philosopher, and logician, most of whose short career was spent as the first professor of mathematics at Queen's College, Cork in Ireland. He worked in the fields of differential equations and algebraic logic, and is best known as the author of The Laws of Thought (1854) which contains Boolean algebra. Boolean logic is credited with laying the foundations for the Information Age alongside the work of Claude Shannon.
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 which work primarily with analog signals. Despite the name, digital electronics designs includes important analog design considerations.
This article presents a detailed timeline of events in the history of computing software and hardware: from prehistory until 1949. For narratives explaining the overall developments, see History of computing.
In automata theory, combinational logic is a type of digital logic that is implemented by Boolean circuits, where the output is a pure function of the present input only. This is in contrast to sequential logic, in which the output depends not only on the present input but also on the history of the input. In other words, sequential logic has memory while combinational logic does not.
Exclusive or, exclusive disjunction, exclusive alternation, logical non-equivalence, or logical inequality is a logical operator whose negation is the logical biconditional. With two inputs, XOR is true if and only if the inputs differ. With multiple inputs, XOR is true if and only if the number of true inputs is odd.
In Boolean logic, logical NOR, non-disjunction, or joint denial is a truth-functional operator which produces a result that is the negation of logical or. That is, a sentence of the form (p NOR q) is true precisely when neither p nor q is true—i.e. when both p and q are false. It is logically equivalent to and , where the symbol signifies logical negation, signifies OR, and signifies AND.
The history of computing is longer than the history of computing hardware and modern computing technology and includes the history of methods intended for pen and paper or for chalk and slate, with or without the aid of tables.
In mathematics, a Boolean function is a function whose arguments and result assume values from a two-element set. Alternative names are switching function, used especially in older computer science literature, and truth function, used in logic. Boolean functions are the subject of Boolean algebra and switching theory.
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 computer program called a synthesis tool. Common examples of this process include synthesis of designs specified in hardware description languages, including VHDL and Verilog. Some synthesis tools generate bitstreams for programmable logic devices such as PALs or FPGAs, while others target the creation of ASICs. Logic synthesis is one step in circuit design in the electronic design automation, the others are place and route and verification and validation.
Kaarlo Jaakko Juhani Hintikka was a Finnish philosopher and logician. Hintikka is regarded as the founder of formal epistemic logic and of game semantics for logic.
"A Symbolic Analysis of Relay and Switching Circuits" is the title of a master's thesis written by computer science pioneer Claude E. Shannon while attending the Massachusetts Institute of Technology (MIT) in 1937. In his thesis, Shannon, a dual degree graduate of the University of Michigan, proved that Boolean algebra could be used to simplify the arrangement of the relays that were the building blocks of the electromechanical automatic telephone exchanges of the day. Shannon went on to prove that it should also be possible to use arrangements of relays to solve Boolean algebra problems.
The history of computer science began long before the modern discipline of computer science, usually appearing in forms like mathematics or physics. Developments in previous centuries alluded to the discipline that we now know as computer science. This progression, from mechanical inventions and mathematical theories towards modern computer concepts and machines, led to the development of a major academic field, massive technological advancement across the Western world, and the basis of a massive worldwide trade and culture.
Victor Ivanovich Shestakov (1907–1987) was a Russian/Soviet logician and theoretician of electrical engineering. In 1935 he discovered the possible interpretation of Boolean algebra of logic in electro-mechanical relay circuits. He graduated from Moscow State University (1934) and worked there in the General Physics Department almost until his death.
The following timeline tables list the discoveries and inventions in the history of electrical and electronic engineering.
The timeline of music technology provides the major dates in the history of electric music technologies inventions from the 1800s to the early 1900s and electronic and digital music technologies from 1874 and electric music technologies to the 2010s.
In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values true and false, usually denoted 1 and 0, whereas in elementary algebra the values of the variables are numbers. Second, Boolean algebra uses logical operators such as conjunction (and) denoted as ∧, disjunction (or) denoted as ∨, and the negation (not) denoted as ¬. Elementary algebra, on the other hand, uses arithmetic operators such as addition, multiplication, subtraction, and division. Boolean algebra is therefore a formal way of describing logical operations, in the same way that elementary algebra describes numerical operations.
Akira Nakashima was a Japanese electrical engineer of the NEC.
{{cite book}}
: CS1 maint: location missing publisher (link) (3+207+1 pages) 10:00 min {{cite book}}
: |work=
ignored (help) See also: Burks, Arthur Walter (1978). "Review: Charles S. Peirce, The new elements of mathematics". Bulletin of the American Mathematical Society (review). 84 (5): 913–918 [917]. doi: 10.1090/S0002-9904-1978-14533-9 .{{cite book}}
: |work=
ignored (help) Reprinted in Writings of Charles S. Peirce. Vol. 4 (reprint ed.). 1989. pp. 218–221. ISBN 9780253372017. ark:/13960/t11p5r61f. See also: Roberts, Don D. (2009). The Existential Graphs of Charles S. Peirce. p. 131.Although the possibility of establishing a switching theory was recognized by M. Boda [A] as early as in the 19th century, the first important works on this subject were published by A. Nakashima [B] and C. E. Shannon [C] shortly before World War II.(xvi+573+1 pages)
{{cite book}}
: CS1 maint: location missing publisher (link) (8 pages)