section-algebra-of-circuits.ipynb

Kernel:

%%html
<link href="http://mathbook.pugetsound.edu/beta/mathbook-content.css" rel="stylesheet" type="text/css" />
<link href="https://aimath.org/mathbook/mathbook-add-on.css" rel="stylesheet" type="text/css" />
<style>.subtitle {font-size:medium; display:block}</style>
<link href="https://fonts.googleapis.com/css?family=Open+Sans:400,400italic,600,600italic" rel="stylesheet" type="text/css" />
<link href="https://fonts.googleapis.com/css?family=Inconsolata:400,700&subset=latin,latin-ext" rel="stylesheet" type="text/css" /><!-- Hide this cell. -->
<script>
var cell = $(".container .cell").eq(0), ia = cell.find(".input_area")
if (cell.find(".toggle-button").length == 0) {
ia.after(
    $('<button class="toggle-button">Toggle hidden code</button>').click(
        function (){ ia.toggle() }
        )
    )
ia.hide()
}
</script>

Important: to view this notebook properly you will need to execute the cell above, which assumes you have an Internet connection. It should already be selected, or place your cursor anywhere above to select. Then press the "Run" button in the menu bar above (the right-pointing arrowhead), or press Shift-Enter on your keyboard.

ParseError: KaTeX parse error: \newcommand{\lt} attempting to redefine \lt; use \renewcommand

Section19.3The Algebra of Electrical Circuits

¶

The usefulness of Boolean algebras has become increasingly apparent over the past several decades with the development of the modern computer. The circuit design of computer chips can be expressed in terms of Boolean algebras. In this section we will develop the Boolean algebra of electrical circuits and switches; however, these results can easily be generalized to the design of integrated computer circuitry.

A is a device, located at some point in an electrical circuit, that controls the flow of current through the circuit. Each switch has two possible states: it can be , and not allow the passage of current through the circuit, or a it can be , and allow the passage of current. These states are mutually exclusive. We require that every switch be in one state or the other—a switch cannot be open and closed at the same time. Also, if one switch is always in the same state as another, we will denote both by the same letter; that is, two switches that are both labeled with the same letter $a$ will always be open at the same time and closed at the same time.

Given two switches, we can construct two fundamental types of circuits. Two switches $a$ and $b$ are in if they make up a circuit of the type that is illustrated in Figure 19.25. Current can pass between the terminals $A$ and $B$ in a series circuit only if both of the switches $a$ and $b$ are closed. We will denote this combination of switches by $a \wedge b\text{.}$ Two switches $a$ and $b$ are in if they form a circuit of the type that appears in Figure 19.26. In the case of a parallel circuit, current can pass between $A$ and $B$ if either one of the switches is closed. We denote a parallel combination of circuits $a$ and $b$ by $a \vee b\text{.}$

Figure19.25$a \wedge b$

Figure19.26$a \vee b$

We can build more complicated electrical circuits out of series and parallel circuits by replacing any switch in the circuit with one of these two fundamental types of circuits. Circuits constructed in this manner are called .

We will consider two circuits equivalent if they act the same. That is, if we set the switches in equivalent circuits exactly the same we will obtain the same result. For example, in a series circuit $a \wedge b$ is exactly the same as $b \wedge a\text{.}$ Notice that this is exactly the commutative law for Boolean algebras. In fact, the set of all series-parallel circuits forms a Boolean algebra under the operations of $\vee$ and $\wedge\text{.}$ We can use diagrams to verify the different axioms of a Boolean algebra. The distributive law, $a \wedge ( b \vee c ) = (a \wedge b ) \vee ( a \wedge c )\text{,}$ is illustrated in Figure 19.27. If $a$ is a switch, then $a'$ is the switch that is always open when $a$ is closed and always closed when $a$ is open. A circuit that is always closed is $I$ in our algebra; a circuit that is always open is $O\text{.}$ The laws for $a \wedge a' = O$ and $a \vee a' = I$ are shown in Figure 19.28.

Figure19.27$a \wedge ( b \vee c ) = (a \wedge b ) \vee ( a \wedge c )$

Figure19.28$a \wedge a' = O$ and $a \vee a' = I$

Example19.29

Every Boolean expression represents a switching circuit. For example, given the expression $(a \vee b) \wedge (a \vee b') \wedge (a \vee b)\text{,}$ we can construct the circuit in Figure 19.32.

Theorem19.30

The set of all circuits is a Boolean algebra.

We leave as an exercise the proof of this theorem for the Boolean algebra axioms not yet verified. We can now apply the techniques of Boolean algebras to switching theory.

Example19.31

Given a complex circuit, we can now apply the techniques of Boolean algebra to reduce it to a simpler one. Consider the circuit in Figure 19.32. Since

$$\begin{align*} (a \vee b) \wedge (a \vee b') \wedge (a \vee b) & = (a \vee b) \wedge (a \vee b) \wedge (a \vee b')\\ & = (a \vee b) \wedge (a \vee b')\\ & = a \vee ( b \wedge b')\\ & = a \vee O\\ & = a, \end{align*}$$

we can replace the more complicated circuit with a circuit containing the single switch $a$ and achieve the same function.

Figure19.32$(a \vee b) \wedge (a \vee b') \wedge (a \vee b)$

SubsectionHistorical Note

¶

George Boole (1815–1864) was the first person to study lattices. In 1847, he published The Investigation of the Laws of Thought, a book in which he used lattices to formalize logic and the calculus of propositions. Boole believed that mathematics was the study of form rather than of content; that is, he was not so much concerned with what he was calculating as with how he was calculating it. Boole's work was carried on by his friend Augustus De Morgan (1806–1871). De Morgan observed that the principle of duality often held in set theory, as is illustrated by De Morgan's laws for set theory. He believed, as did Boole, that mathematics was the study of symbols and abstract operations.

Set theory and logic were further advanced by such mathematicians as Alfred North Whitehead (1861–1947), Bertrand Russell (1872–1970), and David Hilbert (1862–1943). In Principia Mathematica, Whitehead and Russell attempted to show the connection between mathematics and logic by the deduction of the natural number system from the rules of formal logic. If the natural numbers could be determined from logic itself, then so could much of the rest of existing mathematics. Hilbert attempted to build up mathematics by using symbolic logic in a way that would prove the consistency of mathematics. His approach was dealt a mortal blow by Kurt Gödel (1906–1978), who proved that there will always be “undecidable” problems in any sufficiently rich axiomatic system; that is, that in any mathematical system of any consequence, there will always be statements that can never be proven either true or false.

As often occurs, this basic research in pure mathematics later became indispensable in a wide variety of applications. Boolean algebras and logic have become essential in the design of the large-scale integrated circuitry found on today's computer chips. Sociologists have used lattices and Boolean algebras to model social hierarchies; biologists have used them to describe biosystems.