# 13.7: A Brief Introduction to Switching Theory and Logic Design

- Page ID
- 80563

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)

( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)

\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)

\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)

\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)

\( \newcommand{\Span}{\mathrm{span}}\)

\( \newcommand{\id}{\mathrm{id}}\)

\( \newcommand{\Span}{\mathrm{span}}\)

\( \newcommand{\kernel}{\mathrm{null}\,}\)

\( \newcommand{\range}{\mathrm{range}\,}\)

\( \newcommand{\RealPart}{\mathrm{Re}}\)

\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)

\( \newcommand{\Argument}{\mathrm{Arg}}\)

\( \newcommand{\norm}[1]{\| #1 \|}\)

\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)

\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)

\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)

\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)

\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vectorC}[1]{\textbf{#1}} \)

\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)

\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)

\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)The electronics involved in these switches take into account whether we are negating a switch or not. For electromagnetic switches, a magnet is used to control whether the switch is open or closed. The magnets themselves may be controlled by simple ON/OFF switches. There are two types of electromagnetic switches. One is normally open (OFF) when the magnet is not activated, but activating the magnet will close the circuit and the switch is then ON. A separate type of switch corresponds with a negated switch. For that type, the switch is closed when the magnet is not activated, and when the magnet is activated, the switch opens. We won't be overly concerned with the details of these switches or the electronics corresponding to logical gates. We will simply assume they are available to plug into a circuit. For simplicity, we use the inversion symbol on a variable that labels a switch to indicate that it is a switch of the second type, as in Figure \(\PageIndex{3}\).

Note \(\PageIndex{1}\)

Standby power generators that many people have in their homes use a transfer switch to connect the generator to the home power system. This switch is open (OFF) if there is power coming from the normal municipal power supply. It stays OFF because a magnet is keeping it open. When power is lost, the magnet is no longer activated, and the switch closes and is ON. So the transfer switch is a normally ON switch.

The standard notation used for Boolean algebra operations in switching theory and logic design is \(+\) for join, instead of \(\lor \text{;}\) and \(\cdot \) for meet, instead of \(\land \text{.}\) Complementation is the same in both notational systems, denoted with an overline.

The expression \(x_1 \cdot x_2\) represents the situation in which a series of two switches appears in sequence as in Figure \(\PageIndex{4}\). In order for current to flow through the circuit, both switches must be ON; that is, they must both have the value 1. Similarly, a pair of parallel switches, as in Figure \(\PageIndex{5}\), is described algebraically by \(x_1 + x_2\text{.}\) Here, current flows through this part of the circuit as long as at least on of the switches is ON.

All laws and concepts developed previously for Boolean algebras hold. The only change is purely notational. We make the change in this section solely to introduce the reader to another frequently used system of notation.

Many of the laws of Boolean algebra can be visualized thought switching theory. For example, the distributive law of meet over join is expressed as

\begin{equation*} x_1 \cdot \left(x_2+ x_3\right) = x_1 \cdot x_2+x_1 \cdot x_3. \end{equation*}

The switching circuit analogue of the above statement is that the circuits in the two images below are equivalent. In circuit (b), the presence of two \(x_1\)'s might represent two electromagnetic switches controlled by the same magnet.

The circuits in a computer are now composed of large quantities of gates, which serve the same purpose as switches, but can be miniaturized to a great degree. For example, the OR gate, usually drawn as in Figure \(\PageIndex{8}\) implements the logical OR function. This happens electronically, but is equivalent to Figure \(\PageIndex{5}\). The AND gate, which is equivalent to two sequential switches is shown in Figure \(\PageIndex{8}\).

The complementation process is represented in a gate diagram by an inverter, as pictured in Figure \(\PageIndex{10}\).

When drawing more complex circuits, multiple AND's or OR's are sometimes depicted using a more general gate drawing. For example if we want to depict an OR gate with three inputs that is ON as long as at least one input is ON, we would draw it as in Figure \(\PageIndex{11}\), although this would really be two binary gates, as in Figure \(\PageIndex{12}\). Both diagrams are realizing the boolean expression \(x_1 + x_2 + x_3\text{.}\) Strictly speaking, the gates in Figure \(\PageIndex{12}\) represent \((x_1 + x_2 )+ x_3\text{,}\) but the associative law for join tells us that the grouping doesn't matter.

In Figure \(\PageIndex{13}\), we show a few other commonly used gates, XOR, NAND, and NOR, which correspond to the boolean exressions \(x_1 \oplus x_2\text{,}\) \(\overline{x_1 \cdot x_2}\text{,}\) and \(\overline{x_1 + x_2}\text{,}\) respectively.

Let's start with a logic circuit and see how the laws of boolean algebra can help us simplify it.

Example \(\PageIndex{1}\): Simplification of a Circuit

Consider the circuit in Figure \(\PageIndex{14}\). As usual, we assume that three inputs enter on the left and the output exits on the right.

If we trace the inputs through the gates we see that this circuit realizes the boolean function

\begin{equation*} f\left(x_1, x_2, x_3 \right)=x_1 \cdot \overline{x_2}\cdot \left(\left( x_1 + x_2\right) + \left(x_1 + x_3\right)\right). \end{equation*}

We simplify the boolean expression that defines \(f\text{,}\) simplifying the circuit in so doing. You should be able to identify the laws of Boolean algebra that are used in each of the steps. See Exercise \(\PageIndex{1}\).

\begin{equation*} \begin{split} x_1 \cdot \overline{x_2}\cdot \left(\left( x_1 + x_2\right) + \left(x_1 + x_3\right)\right) & = x_1 \cdot \overline{x_2}\cdot \left(x_1+ x_2 + x_3\right)\\ & = x_1 \cdot \overline{x_2} \cdot x_1 + x_1 \cdot \overline{x_2} \cdot x_2 + x_1 \cdot \overline{x_2} \cdot x_3 \\ &= x_1\cdot \overline{x_2} + 0 \cdot x_1 + x_3 \cdot x_1 \cdot \overline{x_2}\\ &=x_1 \cdot \overline{x_2} + x_3 \cdot x_1 \cdot \overline{x_2} \\ &= x_1 \cdot \overline{x_2} \cdot \left(1 + x_3\right)\\ &= x_1 \cdot \overline{x_2} \end{split} \end{equation*}

Therefore, \(f\left(x_1, x_2, x_3\right)=x_1 \cdot \overline{x_2}\text{,}\) which can be realized with the much simpler circuit in Figure \(\PageIndex{15}\), without using the input \(x_3\text{.}\)

Next, we start with a table of desired outputs based on three bits of input and design an efficient circuit to realize this output.

Example \(\PageIndex{2}\)

Consider the following table of desired outputs for the three input bits \(x_1, x_2, x_3\text{.}\)

Table \(\PageIndex{1}\): Desired output table

\(x_1\) |
\(x_2\) |
\(x_3\) |
\(f(x_1,\:x_2,\:x_3)\) |
---|---|---|---|

\(0\) | \(0\) | \(0\) | \(0\) |

\(0\) | \(0\) | \(1\) | \(1\) |

\(0\) | \(1\) | \(0\) | \(0\) |

\(0\) | \(1\) | \(1\) | \(0\) |

\(1\) | \(0\) | \(0\) | \(1\) |

\(1\) | \(0\) | \(1\) | \(1\) |

\(1\) | \(1\) | \(0\) | \(0\) |

\(1\) | \(1\) | \(1\) | \(0\) |

The first step is to write the Minterm Normal Form, Definition 13.6.3, of \(f\text{.}\) Since we are working with the two value Boolean algebra, \(B_2\text{,}\) the constants in each minterm are either 0 or 1, and we simply list the minterms that have a 1. These correspond with the rows of the table above that have an output of 1. We will then attempt to simplify the expression as much as possible.

\begin{equation*} \begin{split} f\left(x_1, x_2, x_3\right)&= (\overline{x_1} \cdot \overline{x_2} \cdot x_3) + (x_1 \cdot \overline{x_2} \cdot \overline{x_3})+(x_1 \cdot \overline{x_2} \cdot x_3)\\ &= \overline{x_2} \cdot( (\overline{x_1} \cdot x_3) + (x_1 \cdot \overline{x_3})+(x_1 \cdot x_3))\\ &= \overline{x_2} \cdot( (\overline{x_1} \cdot x_3) + x_1 \cdot (\overline{x_3}+ x_3))\\ &= \overline{x_2} \cdot ((\overline{x_1} \cdot x_3) + x_1)\\ \end{split} \end{equation*}

Therefore we can realize our table with the boolean function \(f\left(x_1, x_2, x_3\right)=\overline{x_2} \cdot ((\overline{x_1} \cdot x_3) + x_1)\text{.}\) A circuit diagram for this function is Figure \(\PageIndex{16}\). But is this the simplest circuit that realizes the table? See Exercise \(\PageIndex{3}\).

## 13.7.1: Exercises

Exercise \(\PageIndex{1}\)

List the laws of boolean algebra that justify the steps in the simplification of the boolean function \(f\left(x_1, x_2, x_3\right)\) in Example \(\PageIndex{1}\). Some steps use more than one law.

**Answer**-
- Associative, commutative, and idempotent laws.
- Distributive law.
- Idempotent and complement laws.
- Null and identity laws
- Distributive law.
- Null and identity laws.

Exercise \(\PageIndex{2}\)

Write the following Boolean expression in the notation of logic design.

\begin{equation*} \left(x_1\land \overline{x_2}\right)\lor \left(x_1\land x_2\right)\lor \left(\overline{x_1}\land x_2\right). \end{equation*}

**Answer**-
\begin{equation*} (x_1\cdot \overline{x_2})+(x_1\cdot x_2)+(\overline{x_1} \cdot x_2). \end{equation*}

Exercise \(\PageIndex{3}\)

Find a further simplification of the boolean function in Example \(\PageIndex{2}\), and draw the corresponding gate diagram for the circuit that it realizes.

**Answer**-
A simpler boolean expression for the function is \(\overline{x_2} \cdot (x_1 + x_3)\text{.}\)

Exercise \(\PageIndex{4}\)

Consider the switching circuit in Figure \(\PageIndex{18}\).

- Draw the corresponding gate diagram for this circuit.
- Construct a table of outputs for each of the eight inputs to this circuit.
- Determine the minterm normal of the Boolean function based on the table.
- Simplify the circuit as much as possible.

Exercise \(\PageIndex{5}\)

Consider the circuit in Figure \(\PageIndex{19}\).

- Trace the inputs though this circuit and determine the Boolean function that it realizes.
- Construct a table of outputs for each of the eight inputs to this circuit.
- Find the minterm normal form of \(f\text{.}\)
- Draw the circuit based on the minterm normal form.
- Simplify the circuit algebraically and draw the resulting circuit.

Exercise \(\PageIndex{6}\)

Consider the Boolean function \(f\left(x_1, x_2, x_3, x_4\right)=x_1 + \left(x_2 \cdot \left(\overline{x_1} + x_4\right) + x_3 \cdot \left(\overline{x_2} + \overline{x_4}\right)\right).\)

- Simplify \(f\) algebraically.
- Draw the gate diagram based on the simplified version of \(f\text{.}\)

Exercise \(\PageIndex{7}\)

Draw a logic circuit using only AND, OR and NOT gates that realizes an XOR gate.

Exercise \(\PageIndex{8}\)

Draw a logic circuit using only AND, OR and NOT gates that realizes the Boolean function on three variables that returns 1 if the majority of inputs are 1 and 0 otherwise.