**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^{n}. The 2^{n}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)