Binary information is represented in digital computers by physical quantities called signals.

Electrical signals such as voltages exist throughout the computer in either one of two recognizable states.

For example, a particular digital computer may employ a signal of 3 volts to represent binary 1 and 0.5 volt to represent binary 0.

The input terminals of digital circuits accept binary signals of 3 and 0.5 volts and the circuits respond at the output terminals with signals of 3 and 0.5 volts to represent binary input and output corresponding to 1 and 0, respectively.

The manipulation of binary information is done by logic circuits called gates. Gates are blocks of hardware that produce signals of binary 1 or 0 when input logic requirements are satisfied.

The names, graphic symbols, algebraic functions, and truth tables of eight logic gates are listed below

Boolean algebra is an algebra that deals with binary variables and logic operations.

The variables are designated by letters such as A, B, x, and y. The three basic logic operations are AND, OR, and complement.

The purpose of Boolean algebra is to facilitate the analysis and design of digital circuits. It provides a convenient tool to:

Express in algebraic form a truth table relationship between binary variables.

Express in algebraic form the input-output relationship of logic diagrams.

Find simpler circuits for the same function.

A Boolean function specified by a truth table can be expressed algebraically in many different ways. By manipulating a Boolean expression according to Boolean algebra rules, one may obtain a simpler expression that will require fewer gates

DeMorgan's theorem is very important in dealing with NOR and NAND gates. It states that a NOR gate that performs the (x + y)' function is equivalent to the function x'y'. Similarly, a NAND function can be expressed by either (xy)' or (x' + y'). For this reason the NOR and NAND gates have two distinct graphic symbols, as shown below.

The complement of a function F when expressed in a truth table is obtained by interchanging 1's and 0's in the values of F in the truth table.

\( (x_1 + x_2 + ... x_n)' = (x_1'x_2'x_3'....x_n') \)

\( (x_1'x_2'x_3'....x_n') = (x_1 + x_2 + ... x_n)' \)

The complement expression is obtained by interchanging AND and OR operations and complementing each individual variable

The complexity of the logic diagram that implements a Boolean function is related directly to the complexity of the algebraic expression from which the function is implemented.

The expression may be simplified using the basic relations of Boolean algebra. However, this procedure is sometimes difficult because it lacks specific rules for predicting each succeeding step in the manipulative process.

The map (Karnaugh map or K-map) method provides a simple, straightforward procedure for simplifying Boolean expressions

Each combination of the variables in a truth table is called a minterm.

The information contained in a truth table may be expressed in compact form by listing the decimal equivalent of those minterms that produce a 1 for the function.

For example, the truth table of Fig. above can be expressed as follows: F(x, y, z) = Σ (1, 4, 5, 6, 7)

The letters in parentheses list the binary variables in the order that they appear in the truth table.

The symbol Σ stands for the sum of the min terms that follow in parentheses. The min terms that produce 1 for the function are listed in their decimal equivalent.

The minterms missing from the list are the ones that produce 0 for the function.

The map is a diagram made up of squares, with each square representing one minterm. The squares corresponding to minterms that produce 1 for the function are marked by a 1 and the others are marked by a 0 or are left empty.

By recognizing various patterns and combining squares marked by 1's in the map, it is possible to derive alternative algebraic expressions for the function, from which the most convenient may be selected.

The maps for functions of two, three, and four variables are shown in Fig. below.

The number of squares in a map of n variables is 2ⁿ. The 2ⁿ minterms are listed by an equivalent decimal number for easy reference.

The minterm numbers are assigned in an orderly arrangement such that adjacent squares represent minterms that differ by only one variable.

The variable names are listed across both sides of the diagonal line in the corner of the map.

The 0's and 1' s marked along each row and each column designate the value of the variables.

Each variable under brackets contains half of the squares in the map where that variable appears unprimed.

The variable appears with a prime (complemented) in the remaining half of the squares.

The minterm represented by a square is determined from the binary assignments of the variables along the left and top edges in the map.

For example, minterm 5 in the three-variable map is 101 in binary, which may be obtained from the 1 in the second row concatenated with the 01 of the second column.

This min term represents a value for the binary variables A, B, and C, with A and C being unprimed and B being primed (i.e., AB 'C).

Minterms of adjacent squares in the map are identical except for one variable, which appears complemented in one square and uncomplemented in the adjacent square.

According to this definition of adjacency, the squares at the extreme ends of the same horizontal row are also to be considered adjacent.

The same applies to the top and bottom squares of a column. As a result, the four corner squares of a map must also be considered to be adjacent.

In the first example we will simplify the Boolean function F(A, B, C) = Σ (3, 4, 6, 7)

The three-variable map for this function is shown in Fig. below.

There are four squares marked with 1's, one for each minterm that produces 1 for the function.

These squares belong to minterms 3, 4, 6, and 7 and are recognized. Two adjacent squares are combined in the third column.

This column belongs to both B and C and produces the term BC.

The remaining two squares with 1's in the two comers of the second row are adjacent and belong to row A and the two columns of C', so they produce the term AC'.

The simplified algebraic expression for the function is the OR of the two terms: F = BC + AC'

The second example simplifies the following Boolean function: F(A, B, C) = Σ (0, 2, 4, 5, 6)

The five min terms are marked with 1' s in the corresponding squares of the three-variable map shown in Fig. below.

The four squares in the first and fourth columns are adjacent and represent the term C'.

The remaining square marked with a 1 belongs to min term 5 and can be combined with the square of min term 4 to produce the term AB ' .

The simplified function is F = C'+AB'

The third example needs a four-variable map. F(A, B, C, D) = Σ(0, 1, 2, 6, 8, 9, 10)

The area in the map covered by this four-variable function consists of the squares marked with 1's in Fig. below.

The function contains 1's in the four comers that, when taken as a group, give the term B'D'.

This is possible because these four squares are adjacent when the map is considered with top and bottom or left and right edges touching.

The two 1's on the left of the top row are combined with the two 1's on the left of the bottom row to give the term B'C'.

The remaining 1 in the square of minterm 6 is combined with minterm 2 to give the term A 'CD'. The simplified function is F = B'D' + B'C' + A 'CD'

The product terms are AND terms and the sum denotes the ORing of these terms.

It is sometimes convenient to obtain the algebraic expression for the function in a product-of-sums form.

The sums are OR terms and the product denotes the ANDing of these terms. With a minor modification, a product-of-sums form can be obtained from a map.

The procedure for obtaining a product-of-sums expression follows from the basic properties of Boolean algebra.

The 1's in the map represent the minterms that produce 1 for the function. The squares not marked by 1 represent the min terms that produce 0 for the function.

If we mark the empty squares with 0's and combine them into groups of adjacent squares, we obtain the complement of the function, F'.

Taking the complement of F' produces an expression for F in product-of-sums form. The best way to show this is by example.

We wish to simplify the following Boolean function in both sum-of-products form and product-of-sums form: F(A, B, C, D) = Σ (0, 1, 2, 5, 8, 9, 10)

The 1' s marked in the map of Fig. below represent the min terms that produce a 1 for the function.

The squares marked with 0's represent the min terms not included in F and therefore denote the complement of F.

Combining the squares with 1's gives the simplified function in sum-of-products form: F = B 'D' + B 'C' + A'C'D

If the squares marked with 0' s are combined, as shown in the diagram, we obtain the simplified complemented function: F' = AB +CD + BD'

Taking the complement of F', we obtain the simplified function in product-of-sums form: F = (A' + B ')(C' + D')(B ' + D)

The logic diagrams of the two simplified expressions are shown in Fig. below The sum-of-products expression is implemented with a group of AND gates, one for each AND term. The outputs of the AND gates are connected to the inputs of a single OR gate. The same function is implemented in product-of-sums form with a group of OR gates, one for each OR AND term.

The outputs of the OR gates are connected to the inputs of a single gate. In each case it is assumed that the input variables are directly available in their complement, so inverters are not included.

The pattern established in Fig. below is the general form by which any Boolean function is implemented when expressed in one of the standard forms. AND gates are connected to a single OR gate when in sum-of-products form. OR gates are connected to a single AND gate when in product-of-sums form.

There are occasions when it does not matter if the function produces 0 or 1 for a given minterm. Since the function may be either 0 or 1, we say that we don't care what the function output is to be for this min term.

Min terms that may produce either 0 or 1 for the function are said to be don't-care conditions and are marked with an x in the map.

These don't-care conditions can be used to provide further simplification of the algebraic expression.

When choosing adjacent squares for the function in the map, the x 's may be assumed to be either 0 or 1, whichever gives the simplest expression. In addition, an x need not be used at all if it does not contribute to the simplification of the function.

In each case, the choice depends only on the simplification that can be achieved. As an example, consider the following Boolean function together with the don't-care mmterms: F(A, B, C) = Σ (0, 2, 6) d(A, B, C) = Σ (1, 3, 5)

The minterms listed with F produce a 1 for the function. The don't-care minterms listed with d may produce either a 0 or a 1 for the function. The remaining minterms, 4 and 7, produce a O for the function. The map is shown in Fig. below.

The minterms of F are marked with l's, those of d are marked with x 's, and the remaining squares are marked with 0's. The l's and x's are combined in any convenient manner so as to enclose the maximum number of adjacent squares.

It is not necessary to include all or any of the x 's, but all the l's must be included.

By including the don't-care minterms 1 and 3 with the l's in the first row we obtain the term A ' .

The remaining 1 for min term 6 is combined with min term 2 to obtain the term BC'. The simplified expression is F = A' + BC'

Note that don't-care min term 5 was not included because it does not contribute to the simplification of the expression

The function is determined completely once the x 's are assigned to the 1's or O's in the map.

Thus the expression F = A'+ BC' represents the Boolean function F(A, B, C) = Σ (0, 1, 2, 3, 6)