Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

CHAP. 15] BOOLEAN ALGEBRA 381

Fig. 15-14

15.11Truth Tables, Boolean Functions

Consider a logic circuitLwithn=3 input devicesA,B,Cand outputY, say

Y=A·B·C+A·B′·C+A′·B

Each assignment of a set of three bits to the inputsA,B,Cyields an output bit forY. All together there are
2 n= 23 =8 possible ways to assign bits to the inputs as follows:

000 , 001 , 010 , 011 , 100 , 101 , 110 , 111

The assumption is that the sequence of first bits is assigned toA, the sequence of second bits toB, and the
sequence of third bits toC. Thus the above set of inputs may be rewritten in the form

A= 00001111 ,B= 00110011 ,C= 01010101

We emphasize that these three 2n=8-bit sequences contain the eight possible combinations of the input bits.

Thetruth tableT =T (L)of the above circuitLconsists of the output sequenceYthat corresponds to the
input sequencesA,B,C. This truth tableTmay be expressed using fractional or relational notation, that is,
Tmay be written in the form

T(A,B,C)=Y or T (L)=[A, B, C;Y]

This form for the truth table forLis essentially the same as the truth table for a proposition discussed in Section 4.4.
The only difference is that here the values forA,B,C, andYare written horizontally, whereas in Section 4.4
they are written vertically.

ConsideralogiccircuitLwithninputdevices.TherearemanywaystoformninputsequencesA 1 ,A 2 ,...,An
so that they contain the 2ndifferent possible combinations of the input bits. (Note that each sequence must contain
2 nbits.) One assignment scheme is as follows:

A 1 : Assign 2n−^1 bits which are 0’s followed by 2n−^1 bits which are 1’s.

A 2 : Repeatedly assign 2n−^2 bits which are 0’s followed by 2n−^2 bits which are 1’s.

A 3 : Repeatedly assign 2n−^3 bits which are 0’s followed by 2n−^3 bits which are 1’s.

And so on. The sequences obtained in this way will be calledspecial sequences. Replacing 0 by 1 and 1 by 0 in
the special sequences yields the complements of the special sequences.

Remark: Assuming the input are the special sequences, we frequently do not need to distinguish between the
truth table

T (L)=[A 1 ,A 2 ,...,An;Y]

and the outputYitself.