Combinational Logic

Representations of logic functions

Previously, we looked at three simple logic functions: \(\tt AND\), \(\tt OR\), and \(\tt NOT\).

Boolean algebra

The first way we represented the simple logic functions was as an equation. Because the variables in these equations, \(A\), \(B\), and \(X\) were all elements of \(\mathbb{Z}_2\), they are said to be boolean variables, for George Boole.

When we combine boolean variables into one or more equations and then try to solve or simplify the equations, we perform algebra on them. So this method of manipulating logic functions is called boolean algebra.

Truth tables

The second way we represented the simple logic functions was in a truth table. This approach is more long-winded than the boolean algebra approach, but has the benefit of simplicity.

Circuit diagrams

There is a third way to represent logic: as circuits. Fig. 1 shows how the \(\tt AND\), \(\tt OR\) and \(\tt NOT\) logic functions can be represented diagrammatically.

Fig. 1 \(\tt AND\), \(\tt OR\), and \(\tt NOT\) functions as circuit elements.

Combining logic functions

Logic circuit elements can be combined by simply connecting outputs of one to the input of another.

For example, the half-adder is characterized by the truth table

Table 4 The half-adder operation.

\(A\)	\(B\)		\(S\)	\(C\)
0	0		0	0
0	1		1	0
1	0		1	0
1	1		0	1

or by the boolean algebra expressions

\[ S = A \oplus B \]

and

\[ C = AB \]

where \(S\) is the sum of the two input bits and \(C\) is the carry.

This may be drawn as in Fig. 2.

Fig. 2 The half adder circuit using the \(\tt XOR\) (exclusive-or) gate and an \(\tt AND\) gate.