Digital Electronics: Supplement to Engs 31 / CoSc 56

Two binary codes are called logically adjacent if they differ in only one bit. In the multiplexer example, the binary codes for the third and fourth rows of the full truth table, "010" and "011" are logically adjacent. Two product terms are logically adjacent if they differ only by inverting one variable, e.g., \(\overline{S} A \overline{B}\) and \(\overline{S} A B\text{.}\) The value of \(B\) is irrelevant, since \(y\) is TRUE whether \(B\) is 0 or 1, and the sum \(\overline{S} A \overline{B} + \overline{S} A B\) simplifies to \(\overline{S}A\text{.}\) Likewise, the binary codes for the sixth and eight rows, "101" and "111", are logically adjacent, differing only in the \(A\) bit. Their sum of products simplifies, \(S \overline{A} B + SAB = SB\text{.}\)

Discovering and exploiting logical adjacency is the key to logic minimization. However, it rapidly becomes unwieldy for even moderate-sized truth tables, as this next example shows. In the \(x > y\) function you designed in Checkpoint 1.3.4, the truth table was:

Observe that if \(x = 00\text{,}\) then \(g\) will be zero regardless of the value of \(y\text{.}\) We may compress all of the rows with \(x = 00\text{,}\) as shown below. Again, the dashes indicate that we don’t care what the values of those inputs are.

Likewise, if \(x=01\) and \(y_1=1\text{,}\) then \(g\) will be zero regardless of \(y_0\text{,}\) and another pair of rows can be compressed:

Compressing the remainder of the rows is left as an exercise.

As the exercise showed, some logical adjacencies are harder to spot from a truth table than others. It gets even harder as the number of variables increases. There is a better way.