3.2: Boolean Algebra

3.2.1 Terminology

It is possible to process logic concepts using arithmetic and algebra concepts. To do so the following arithmetic definitions are needed. The first table defines addition the second defines multiplication and the third defines complement.

Figure \(\PageIndex{1}\) Boolean Functions

Checkpoint \(\PageIndex{2}\)

Compare these three operations to the logical operations \(\neg\), \(\vee\), and \(\wedge\).

Functions can be defined using boolean algebra as well. Consider the examples in Table \(\PageIndex{3}\).

Table \(\PageIndex{3}\) Boolean functions

\(x\)	\(y\)	\(f_{1}(x,y)=x+y\)	\(f_{2}(x,y)=xy\)	\(f_{3}(x,y)=x+x\)	\(f_4(x,y)=\overline{x}+y\)
0	0	0	0	0	1
0	1	1	0	0	1
1	0	1	0	1	0
1	1	1	1	1	1

Practice

Checkpoint \(\PageIndex{4}\)

Evaluate the following boolean functions.

1. \(\displaystyle f_1(x,y)=1+x\)
2. \(\displaystyle f_2(x,y)=\overline{xy}\)
3. \(\displaystyle f_3(x,y)=\overline{x}+\overline{y}\)
4. \(\displaystyle f_4(x,y)=xy+y\)

Checkpoint \(\PageIndex{5}\)

A boolean function with two inputs, such as those above, has four input/output pairs. How many different boolean functions of two variables (inputs) exist? How many for a boolean function of three variables?

Checkpoint \(\PageIndex{6}\)

Is the representation of a boolean function unique? This means for each of the functions counted above is there only one expression that produces that result?

Checkpoint \(\PageIndex{7}\)

Find a function with the same input/output pattern as if \(x\) then \(y\).

Checkpoint \(\PageIndex{8}\)

Figure out the value for \(f(x)=\overbrace{x+x+x+\ldots}^{\shortstack{n}}\) for all integers \(n\).

Representation

Terminology

In complicated statements such as those that arise in complicated circuits, it is possible to optimize some statements by finding equivalent sets of operations. Boolean function equivalence can be used for this purpose.

First we will consider how to represent arbitrary boolean combinations as boolean functions. First, consider the expression in \(x\), \(y\), and \(z\) with the value 1 when \(x = y = 1\) and \(z=0\). Because boolean multiplication is only 1 when all factors are one, this expression can be written as \(xy\overline{z}\). Likewise an expression that is 1 when \(x = y = z = 0\) is \(\overline{x}\overline{y}\overline{z}\).

Next consider a function \(f(x,y,z)\) defined by the following input/output table.

Table \(\PageIndex{9}\) Simplifying a boolean algebra

x	0	0	0	0	1	1	1	1
y	0	0	1	1	0	0	1	1
z	0	1	0	1	0	1	0	1
f(x,y,z)	1	0	0	0	0	0	1	0

Note that this function ff is 1 exactly when one of the two expressions above (\(xy\overline{z}\) and \(\overline{x}\overline{y}\overline{z}\)) is one. Because \(u+v\) is 1 when either is one, \(f(x,y,z)= (xy\overline{z} + \overline{x}\overline{y}\overline{z})\) is one way to represent this function.

While the mechanism presented above can be used to produce a boolean function or equivalent circuit for any desired combination of inputs and outputs, it does not necessarily produce the most efficient solution. The following example demonstrates how a boolean function can be simplified using the table of identities in Table \(\PageIndex{10}\)

Table \(\PageIndex{10}\) Boolean Identities

\(x+x\)	=	\(x\)
\(x \cdot x\)	=	\(x\)
\(x+0\)	=	\(x\)
\(x+1\)	=	\(1\)
\(x+\overline{x}\)	=	\(1\)
\(x\overline{x}\)	=	\(0\)
\(x \cdot 0\)	=	\(0\)
\(x \cdot 1\)	=	\(x\)
\(x+y\)	=	\(y+x\)
\(xy\)	=	\(yx\)
\(x+(y+z)\)	=	\((x+y)+z\)
\(x(yz)\)	=	\((xy)z\)
\(x(y+z)\)	=	\(xy+xz\)
\(x+yz\)	=	\((x+y)(x+z)\)
\(x+xy\)	=	\(x\)
\(x(x+y)\)	=	\(x\)
\(\overline{x+y}\)	=	\(\overline{x} \cdot \overline{y}\)
\(\overline{xy}\)	=	\(\overline{x} + \overline{y}\)

The following example demonstrates one way to simplify this boolean function.

\begin{align*}
f(x,y) & = & x\overline{y} + xy + y\overline{x}\\
& = & x\overline{y} + yx + y\overline{x}\\
& = & x\overline{y} + y \cdot (x+\overline{x})\\
& = & x\overline{y} + y \cdot 1\\
& = & x\overline{y}+y\\
& = & y+x\overline{y}\\
& = & (y+x)(y+\overline{y})\\
& = & (y+x) \cdot 1\\
& = & y+x.
\end{align*}

Practice

Checkpoint \(\PageIndex{11}\)

Find an expression that is 1 when \(x=z=1\) and \(y=0\). Use the technique above.

Checkpoint \(\PageIndex{12}\)

Find a representation of the boolean function in Table \(\PageIndex{13}\)

Table \(\PageIndex{13}\) Inputs and Outputs for Boolean Function

x	0	0	0	0	1	1	1	1
y	0	0	1	1	0	0	1	1
z	0	1	0	1	0	1	0	1
f(x,y,z)	0	1	0	1	1	0	0	0

Checkpoint \(\PageIndex{14}\)

Remember that boolean functions can be represented as logic statements (and/or/negate) which can be represented as electrical circuits. Design the electrical circuit needed for a light with two switches using the following steps. Note the following supposes that the light is off when both switches are turned down (typical off).

1. Using 0 for down and 1 for up, determine which combinations of up and down results in the light being off (0) and on (1).
2. Write a boolean function for this using the technique above.
3. Convert this boolean function into a logic statement (using \(\neg\), \(\vee\), and \(\wedge\)).
4. Convert this boolean function into a circuit diagram.

Checkpoint \(\PageIndex{15}\)

Reduce the boolean function \(f(x,y,z)=xy\overline{z}+x\overline{y}\overline{z}+\overline{x}y\overline{z}\).