Chapter 2
Boolean Algebra and Digital Logic
Objectives
At the end of this chapter, you should be able to:
1.	Remember the basic logic functions and define a logic problem with a truth table;
2.	Formulate a logical expression for a logic problem from the truth table;
3.	Apply Boolean Algebraic theorems to simplify a logical expression;
4.	Use Karnaugh-map to simplify logical expressions;
5.	Use logic gates to synthesis a logical circuit for a logical expression;
6.	Use single type of logic gates to synthesis a circuit; and
7.	Solve a practical problem with combinational logic circuits.
References

1.	Theodore F. Bogart Jr., “Introduction to Digital Circuits,” McGraw-Hill Publishing Company.

2.	M. Morris Mano, “Digital Design,” 2nd ed., Prentice Hall International, Inc.

3.	Tokheim, “Digital Electronics,” 4th ed., McGraw-Hill Publishing Company.

1. Introduction
	Consider the problem of installing two switches in a bedroom to control the lamp in the room.  Each switch can be switched into one of the two positions, close or open.  The lamp will be lightened when the two switches are at the same position and will be off if the two switches are at the different position.
	In this example, each switch can only be at one of the two positions and the lamp can only be either on or off.  There are only two possible values for each of the components, switches and lamp.  They are two-value elements. The system can be implemented by a logic circuit with two values being represented by the binary values 1 or 0.  To analyze further, we can think of the switches to be variables and the lamp a function of the two switches because the value of the lamp changes if the values of the switches change.
	Boolean Algebra is an effective method to analyze the logic problems.  Each variable in Boolean Algebra can be one of the two binary values and is called a boolean variable or a logic variable.  Together with the basic operators used in the Boolean Algebra, a logic function can be expressed mathematically and manipulated.  Eventually, the logic function can be implemented by a practical digital logic circuit with the inputs and output being the variables and the function respectively.
2. Truth Table 
	A truth table is used to describe a logic function.  In the truth table, all possible conditions, based on the different combinations of values of the independent logic variables, are listed.  The above problem of using two switches to control the lamp in a room can be summarized in Table 2.1.

Switch A	Switch B	Lamp	
off	off	on	
off	on	off	
on	off	off	
on	on	on	
Table 2.1
	If we use 1 to represent the on state for switches and the lamp, and 0 to represent the off state, Table 2.1 can be transformed into the truth table in Table 2.2.

Switch A	Switch B	Lamp	
0	0	1	
0	1	0	
1	0	0	
1	1	1	
Table 2.2
	There are four rows in the table.  Each row represents a possible condition.  The value of the lamp is a function of the two switches.  Therefore, the two switches are independent variables.  The values of each variable may be either 1 or 0.  There are four combinations all together.  The truth table shows the values of the lamp under each of the  different conditions.
	
Example 2.1
	A cheque issued by a company requires valid signatures from authorized persons.  Three persons in Make Profit Trading Company are authorized to sign a cheque.  They are the director, the general manager, and the chief accountant.  However, for a valid signatures of a cheque, at least two signatures must appear.  Make use of the truth table to show the validity of the cheque.
Solution:
	We can use variable A, B, C to represent the appearance of the signatures of the director, the general manager, and the chief accountant respectively.  If any one signs the cheque, the value of the corresponding variable is defined as 1; otherwise, the value is 0.  Similarly, the validity of the cheque is represented by a function variable, V.  Its value is 1 if the cheque is valid and 0 if not.
	Table 2.3 is the truth table to show in which conditions the cheque is valid.
A	B	C	V	
0	0	0	0	
0	0	1	0	
0	1	0	0	
0	1	1	1	
1	0	0	0	
1	0	1	1	
1	1	0	1	
1	1	1	1	
Table 2.3
	
	In general, for n independent variables, there are total 2n combinations.  Notice that in the table, the values of A, B, and C, if viewed as 3-digit binary numbers, are in sequence from 0 to 7.  It is a good practice to list all possible combinations of values of the independent variable in binary sequence.  It will not lead to mistakes in finding all the combinations.
2.3 Logical expressions
	A logic function can also be expressed by a logical expression. A logic function is an expression consisting of the different independent logic variables connected by the logical operators.
	There are three basic operators in the Boolean Algebra, NOT, AND, and OR. NOT operates on a single operand, it is a unary operator.  AND and OR are binary operators, i.e. they operate on two operands. Their symbols used in an expression are '', '', and '+' for NOT, AND, and OR respectively.   In addition, there are three more binary operators used in Boolean Algebra.  They are NAND, NOR, and XOR.  Their symbols and functions are summarized in Table 2.4.

Input	Function		Input	Functions and their expression symbols	
Variable	and symbol		Variables	AND	OR	NAND	NOR	XOR	
A	 (NOT)		A	B	A    B	A + B			AB	
1	0		0	0	0	0	1	1	0	
0	1		0	1	0	1	1	0	1	
			1	0	0	1	1	0	1	
			1	1	1	1	0	0	0	
Table 2.4
	The unary operator, NOT, negates the value of the operand.  If the value of the operand, A, is 1,  (NOT A) is 0 and vice versa.
	The operator AND operates on two operands, A and B.  The result of AB (A AND B) is 1 only if both A and B are 1; otherwise, it is 0.  Note that the operator '' is usually ignored in an expression, i.e. AB is equivalent to AB.
	The result of A+B (A OR B) is 1 if either A or B is 1.  It is 0 only if both A and B are 0.  The OR operator is referred as the inclusive OR because it regards the situation that A and B are both 1 as the qualified condition, either A or B is 1.  The OR does imply the inclusion, therefore, it is not necessary to specify the inclusive property.  On the other hand, the XOR, exclusive OR operator specifically excludes the situation when both A and B are 1.  AB is 1 only if A is 1 or B is 1 but not both.  It will be 0 if both A and B are 1 or 0.
	The NAND is in fact the combination of NOT and AND operations.  It takes two steps.  First the operands A and B are ANDed.  Then the result is NOTed.  One can see that, in the Table 2.4, the results of AND and NAND are complemented.  Similarly, NOR operation combines NOT and OR operations.
	The binary operators AND, OR, NAND, NOR, and XOR can be extended to operate on three or more operands.  For example, given three independent variables A, B, and C, the result of ABC is 1 only when all the values of A, B, and C are 1 while the result of A+B+C is 1 if any one of A, B, and C is 1. The functions of NAND and NOR are simply the complement of AND and OR respectively.  Table 2.5 gives the truth table of the functions of AND and OR for three independent variables.

A	B	C	ABC	A+B+C	
0	0	0	0	0	
0	0	1	0	1	
0	1	0	0	1	
0	1	1	0	1	
1	0	0	0	1	
1	0	1	0	1	
1	1	0	0	1	
1	1	1	1	1	
Table 2.5
	In fact, the truth Table 2.5 is obtained by applying the binary operations.  First, the values of AB being evaluated then the intermediate result being ANDed with C will give the result of ABC.  Similarly, the result of A+B+C is obtained by applying OR operations twice.  Using this method, the binary operators, AND, OR, NAND, NOR, and XOR, can be extended to any number of operands.
	A logical expression will look like:
F(A,B,C) = ()  ()	(Exp. 2.1)
It is similar to an algebraic expression.  Different logic variables are connected with logical operators.  The value of  F can be found by giving specific values to the variables.  For example,
F(0,0,0)	= 	()  ()
	=	()  ()
	=	1   1
	=	0
	
Example 2.2
Find the truth table for the expression Exp. 2.1
Solution:
	For three independent variables, there are eight different combinations of input values.  One can use the truth table to list all the different values of F for various combinations of A, B, and C. Table 2.6 shows the procedures.  It requires to break down the function F into the basic functions, i.e. NOT, AND, OR, etc., and evaluate these functions in steps.  In Table 2.6, the first three columns list the values of the three independent variables under different conditions.  Columns 4, 5, and 6 are the complements of the variables A, B, and C respectively.  Column 7 shows the values of the expression .  The values are obtained by applying AND function to the column 4 and 2.  Similarly, the values of the expression  are found and listed in column 8.  Then, the complement of  are evaluated in column 9.  The values in column 10 and 11 are found by applying the OR function to column 7 with 9, and 1 with 5, respectively.  Finally, the values in column 10 and 11 are exclusive-ORed to give the values of F (column 12) for each combination of A, B and C.

1	2	3	4	5	6	7	8	9	10	11	12	
A	B	C									F	
0	0	0	1	1	1	0	0	1	1	1	0	
0	0	1	1	1	0	0	0	1	1	1	0	
0	1	0	1	0	1	1	1	0	1	0	1	
0	1	1	1	0	0	1	0	1	1	0	1	
1	0	0	0	1	1	0	0	1	1	1	0	
1	0	1	0	1	0	0	0	1	1	1	0	
1	1	0	0	0	1	0	1	0	0	1	1	
1	1	1	0	0	0	0	0	1	1	1	0	
Table 2.6
2.4. Logic gates and logic circuits
	As mentioned in section 2.1, a logic function can be implemented by a logic circuit.  The inputs of the circuit are the independent logic variables and the output of the circuit is the logic function.  Figure 2.1 shows a block diagram of a logic circuit which consists of three inputs, A, B, C,  and an output, F.

Figure 2.1 Block diagram of a logic circuit.	
	The basic components in a logic circuit is the logic gates.  There are five basic logic gates: AND, OR, NOT, NAND, and NOR gates and one extended logic gate, Exclusive OR gate.  Each of them performs the specific function as named.  The circuit symbols of these logic gates are given in Figure 2.2.

Figure 2.2.  Circuit symbols of logic gates.	
	Note that the symbols given in Figure 2.2 are used for two input variables (one only for NOT gate).  To facilitate more input operands, extra terminals to the logic gates can be added.

Example 2.3
Find the logic circuit for the function in Exp.2.1 
Solution: 
The logic circuit is given in Figure 2.3.
	
Figure 2.3.	
Example 2.4
Given the following logic circuit, find the logical expression of function F.

Figure 2.4.	
Solution: 
	From the circuit above, we have:
G1 = 
G2 = 
G3 = ABD
G4 = 
G5 = G3  G4
G6 = 
F	= G7
Substituting all above to the function, we have:
F	= G1 + G6
	=  + 
	=  + 
	=  + 
2.5. Theorems
	Because the purpose of a logic circuit is to implement a logic function, the cost and physical size of the circuit depends on the complexity of the logic function.  It is, therefore, necessary to simplify the logic function as much as possible.  The theorems in Table 2.7, can be used to simplify the logic functions.
	In Table 2.7, A, B, and C, are logic variables, while 0 and 1 are constants.  These theorems may be proved by truth table method.  The method makes use of the truth table to show that the values of two (or more) functions to be proved equal, are identical for all possible conditions.  Table 2.8 demonstrates the proof of the first six theorems using the truth table method.

	Theorems	Names	
1.			
2.			
2.			
4.			
5.			
6.			
7.		Double negation	
8.		Universal true	
9.		Universal false	
10.		Commutative law	
11.		Commutative law	
12.			
12.			
14.		Distributive law	
15.		Distributive law	
16.		Associative law	
17.	ABC = (AB)C = A (BC)	Associative law	
18.		De Morgan’s law	
19		De Morgan’s law	
Table 2.7
1	2	3	4	5	6	7	8	9	
A	0	1	A+0	A.1	A+1	A.0	A+A	A.A	
0	0	1	0	0	1	0	0	0	
1	0	1	1	1	1	0	1	1	
Table 2.8
	In Table 2.8, the first column lists all possible values of A, which can be either 0 or 1.  0 and 1 are constants, so they have only one value as in column 2 and 2.  Following the rules of each logical operation, the values in each cell can be evaluated.  For example, the values in column 4 are found by ORing the values of A and the value 0 in each row.  ORing a 0 with 0 gives a 0 while a 1 ORed a 0 gives a 1.  As a result, values in column 4 is exactly the same as the values of A in column 1.  Therefore, we can say that the expression A+0 is equal to A because they are identical for all possible conditions, i.e. both A is 1 and A is 0.

1	2	3	4	5	
A					
0	1	0	1	0	
1	0	1	1	0	
Table 2.9
	Proofs of theorems 7 to 9 are given in Table 2.9.  Column 1 lists all possible values of A, i.e. 0 and 1.  Therefore, values of  is 1 and 0 respectively, as in column 2.   applies NOT function to .  Therefore, its values are 0 and 1 respectively.  Comparing the values in column 1 and 3, we find that they are the same.  So we can conclude that is in fact the same as A.  Since the function NOT is applied twice to the variable A, theorem 7 is called as double negation.
	Results in column 4 are obtained by applying function OR to the values in column 1 and 2 which gives 1 at all time.  Therefore, the value of  + A is always 1.  Similarly, applying function AND to the values in column 1 and 2 will result in 0 under all possible conditions, as in column 5.  Since logic 1 refers to true and logic 0 refers to false, theorems 8 and 9 are referred as universal true and universal false respectively.
	Theorem 10 and 11 are sometimes referred as the commutative laws.  Their proofs are given in  Table 2.10.  Results in columns 3 and 4 are direct results of AND operation defined in Table 2.4.  Similarly, results in columns 5 and 6 are direct results of OR operation.
1	2	3	4	5	6	
A	B	A . B	B . A	A + B	B + A	
0	0	0	0	0	0	
0	1	0	0	1	1	
1	0	0	0	1	1	
1	1	1	1	1	1	
Table 2.10
	Table 2.11 shows the proof of the theorem 12 and 12.  Column 5 lists the different values of A + AB which is the same as that of A.  Therefore, it is said to be equivalent to A.  Values in column 7 and 8 are identical in all possible situations.  So the two expressions are equal.

1	2	3	4	5	6	7	8	
A	B		AB	A + AB	B	A + B	A + B	
0	0	1	0	0	0	0	0	
0	1	1	0	0	1	1	1	
1	0	0	0	1	0	1	1	
1	1	0	1	1	0	1	1	
Table 2.11
	Theorems 14 and 15 are referred as distributive laws.  Their proofs are given in Table 2.12 and Table 2.13, respectively.

1	2	3	4	5	6	7	8	
A	B	C	AB	AC	AB + AC	B + C	A (B + C)	
0	0	0	0	0	0	0	0	
0	0	1	0	0	0	1	0	
0	1	0	0	0	0	1	0	
0	1	1	0	0	0	1	0	
1	0	0	0	0	0	0	0	
1	0	1	0	1	1	1	1	
1	1	0	1	0	1	1	1	
1	1	1	1	1	1	1	1	
Table 2.12
1	2	3	4	5	6	7	8	
A	B	C	A + B	A + C	(A + B)(A + C)	BC	A + BC	
0	0	0	0	0	0	0	0	
0	0	1	0	1	0	0	0	
0	1	0	1	0	0	0	0	
0	1	1	1	1	1	1	1	
1	0	0	1	1	1	0	1	
1	0	1	1	1	1	0	1	
1	1	0	1	1	1	0	1	
1	1	1	1	1	1	1	1	
Table 2.13
	Theorem 16 and 17 are called the associative law.  They state that the OR and AND operations are both left and right associative, i.e. the order of the consecutive OR or AND operations does not affect the result.  Their proofs are given in Table 2.14 and Table 2.15 respectively.

1	2	3	4	5	6	7	
A	B	C	A + B	(A + B) + C	B + C	A + (B + C)	
0	0	0	0	0	0	0	
0	0	1	0	1	1	1	
0	1	0	1	1	1	1	
0	1	1	1	1	1	1	
1	0	0	1	1	0	1	
1	0	1	1	1	1	1	
1	1	0	1	1	1	1	
1	1	1	1	1	1	1	
Table 2.14

1	2	3	4	5	6	7	
A	B	C	A  B	(A  B)  C	B  C	A  (B  C)	
0	0	0	0	0	0	0	
0	0	1	0	0	0	0	
0	1	0	0	0	0	0	
0	1	1	0	0	1	0	
1	0	0	0	0	0	0	
1	0	1	0	0	0	0	
1	1	0	1	0	0	0	
1	1	1	1	1	1	1	
Table 2.15
	Finally, the theorems 18 and 19 are called De Morgan's law.  They state that the NAND / NOR functions can be implemented by OR / AND functions respectively after applying the NOT function to the operands.  The proof is given in Table 2.16.

1	2	3	4	5	6	7	8	
	B				.		+	
0	0	1	1	1	1	1	1	
0	1	1	0	0	0	1	1	
1	0	0	1	0	0	1	1	
1	1	0	0	0	0	0	0	
Table 2.16
	These theorems are well known and can be used to simplify other boolean expressions.
	
Example 2.5
Using the Boolean Algebraic theorems, prove 
	(A + B)(+ C) = AC + 

Solution:
	L.H.S. 	=  + AC +  + BC	(Theorem14)
		= AC +  + BC	(Theorem 9)
		= AC +  + BC(A + )	(Theorem 8)
		= AC +  + ABC + 
		= AC(1 + B) + (1 + C)	(Theorem 12)
		= AC + 
		= R.H.S.
Example 2.6
Using the Boolean Algebraic theorems, prove 
	A +  = A + B
Solution:
	L.H.S.	= A + 
		= 
		=  . 	(Theorem 18)
		=  . ( + )	(Theorem 19)
		= .A + .	(Theorem 7,14)
		= 0 + .	(Theorem 9)
		= .	(Theorem 1)
	L.H.S.	= A + B	(Theorem 19)
		= R.H.S.

Example 2.7
Using both the truth table and Boolean Algebraic theorems, prove 

Solution:
i. Prove by Boolean Algebraic theorems:
	 +  +  +  +  + 
	=  +  + 
	=  +  + 
	=  +  + ( + )
	= ( + ) + ( + )
	=  + 
	=  + 
	= 
	ii. Prove by truth table method:
A	B	C	D		L.H.S.	B+D	R.H.S.	
0	0	0	0	1	0	0	0	
0	0	0	1	1	1	1	1	
0	0	1	0	1	0	0	0	
0	0	1	1	1	1	1	1	
0	1	0	0	1	1	1	1	
0	1	0	1	1	1	1	1	
0	1	1	0	1	1	1	1	
0	1	1	1	1	1	1	1	
 1	0	0	0	0	0	0	0	
1	0	0	1	0	0	1	0	
1	0	1	0	0	0	0	0	
1	0	1	1	0	0	1	0	
1	1	0	0	0	0	1	0	
1	1	0	1	0	0	1	0	
1	1	1	0	0	0	1	0	
1	1	1	1	0	0	1	0	

2.6. Standard Forms
	A function expressed in a truth table has to be transformed to a logical expression before it can be manipulated or simplified.  It is only possible to transform a function to one of the two standard forms: standard sum of products or standard product of sums form.
2.6.1 Sum of products form 
	Since we use the dot () to represent the operator AND, which is the same as multiplication in algebra, several expressions being ANDed together is called a product.  Similarly, because the plus (+) is used to represent the operator OR, several expressions being ORed together is called a sum.  An expression in sum of products form consists of several products ORed together.  The followings are some examples:
F(A, B, C, D) =  +  +  + B	(Exp.2.2)
F(A, B, C) =  +  +  + 	(Exp.2.3)
	Each product in the expression is a term.  The function F will become 1 if any one of the term in the expression is 1.  In other words, at least one term in the expression must be 1 to make F equal to 1, i.e. this is the minimum requirement for F being 1.  Therefore, each term in the expression is called a minterm.  The sum of products form is also called the minterm form.
	The expression (Exp.2.2) differs from the equation (Exp.2.3) in a way that each term in expression (Exp.2.3) contains all independent variables, either complemented or not.  Because of this, Exp. 2.3 is a standard sum of products form.  Each term in a standard sum of products form actually represents a row in the truth table.  For example, the term  corresponds to the truth table where A = 1, B = 0, and C = 0 and the value of F being 1.  In other words, the corresponding standard minterm of a row can be obtained by examining the values of each variable.  If the value of a variable is 1, the variable is taken; otherwise, the complement of the variable is included in the term.  Table 2.17 shows the truth table for three variables together with the corresponding standard minterms of each row.
	For the reason that each standard minterm represents a row in a truth table, a function represented by the truth table can be expressed in an expression in standard sum of products form.  The method is to OR all standard minterms in the corresponding rows in the truth table the function values being 1.  

A	B	C	Corresponding minterms	
0	0	0		
0	0	1		
0	1	0		
0	1	1		
1	0	0		
1	0	1		
1	1	0		
1	1	1		
Table 2.17
	
Example 2.8
Find the logical expression of F in Table 2.18 in standard sum of products form.

A	B	C	F	Corresponding minterms	
0	0	0	1		
0	0	1	1		
0	1	0	0		
0	1	1	0		
1	0	0	0		
1	0	1	1		
1	1	0	0		
1	1	1	1		
Table 2.18
Solution:
From the lookup table in Table 2.17, the function, F, in Table 2.18 can be expressed as:
F =  +  +  + 	(Exp. 2.4)
	
	Since the rows in the truth table can be numbered based on its binary values, the standard minterms, corresponding to each row, can also be numbered in the same way.  Therefore, sometimes, the expression in (Exp. 2.4) can be written as:
F(A, B, C) = S(0, 1, 5, 7)	(Exp. 2.5)
	The symbol, S (Sigma), which usually represents a sum, indicates the expression (Exp. 2.5) being the sum (OR) of the 0th, 1st, 5th, and 7th standard minterms.
2.6.2 Product of sums form 
	An expression in product of sums form consists of several sums ANDed together.  The followings are some examples:
F(A, B, C, D) = (A + B + ) ( + C + D) ( + C) 	(Exp. 2.6)
F(A, B, C) = (A + B + C) () ()	(Exp. 2.7)
	In both (Exp. 2.6) and (Exp. 2.7), each term is a sum (result of OR operation) of several variables.  The function, F, will be 1 only if all the terms are equal to 1.  Thus, this is a maximum requirement for F being 1.  Therefore, each term in the product of sums form is called a maxterm and the product of sums form is sometimes called maxterm form.

A	B	C	Corresponding maxterms	
0	0	0		
0	0	1		
0	1	0		
0	1	1		
1	0	0		
1	0	1		
1	1	0		
1	1	1		
Table 2.19
	Similar to the standard sum of products form, a standard product of sums form requires each term in the expression to include all variables.  Therefore, (Exp. 2.6) is not a standard form while (Exp. 2.7) is.  Again, each standard maxterm represents a row in the truth table.  However, the formation of a standard maxterm is different from that of a standard minterm.  The rule is to include the variable if its value is 0.  Should the value of the variable be 1, the complement of the variable is included instead.  Table 2.19 lists the corresponding standard maxterms of each row in a truth table.
	Finding the expression of the function in standard product of sums form is actually an application of the De Morgan’s theorem.
	Consider the function F in Table 2.18, if expressed in sum of products form, is:
F 	= 	 +  +  + 	(Exp. 2.4)
Now, if we apply negation to both sides of the above expression, we will get:
 	= 	
Then, we apply the De Morgan’s theorem:

 	= 	 .  .  . 
	=	(A + B + C) (A + B + ) ( + B + ) ( +  + )
	(Exp. 2.8)
The expression Exp. 2.8 is in standard product of sums form.  However, the corresponding terms in the expression, term 0, 1, 5, and 7 being all 1 will make  to be 1, i.e. F being 0.  Therefore, in order to obtain the correct expression of F, the standard maxterms to be selected have to be those corresponding to the rows in the truth table such that the value of F being 0.
F	=	(A +  + C) (A +  + ) ( + B + C) ( +  + C)
	(Exp. 2.9)
	It can be proved that the expressions Exp. 2.9 and Exp.2.4 are equivalent.  The proof is left as an exercise at the end of this chapter.
	Similar to the sum of products expressions, a product of sums expression can be expressed as a list of row numbers:
F	=	P (2, 3, 4, 6)	(Exp. 2.10)

Example 2.9
Find the logical expression of F in Table 2.20 in standard product of sums form.

A	B	C	F	Corresponding maxterms	
0	0	0	0		
0	0	1	1		
0	1	0	0		
0	1	1	1		
1	0	0	0		
1	0	1	0		
1	1	0	1		
1	1	1	1		
Table 2.20
Solution:
From the lookup table in Table 2.19, the function, F, in Table 2.20 can be expressed as:
F	=	(A + B + C) (A +  + C) ( + B + C) ( + B + )
	
	Having found the expression of a function in either sum of products or product of sums form, the next step is to simplify the expression to its simplest form, using the Boolean Algebraic theorems, before it is synthesised with logic gates.
2.7. Karnaugh Map
2.7.1 Introduction
	Having obtained an expression of a function, it can be implemented by the logic gates.  For example, the function F, in Table 2.17 can be implemented as in Figure 2.5.  Note that the circuits in Figure 2.5a and that in Figure 2.5b are different.  However, they serve the same function.  The circuit in Figure 2.5a is the implementation of the function in standard sum of product form (Exp. 2.4) while the circuit in Figure 2.5b is the implementation of the function in standard product of sum form (Exp. 2.9).
	Both circuits in Figure 2.5 produce the required output as desired.  However, they are not usually used in real life.  The reason for this is that they are not the simplest circuit.  Consider the expression 2.4:
F =  +  +  + 
In fact, it can be simplified to 
F =  + 	(Exp. 2.11)

a.

b.	
Figure 2.5	

	Now, if we implement the circuit using the expression 2.11, the circuit will be as in Figure 2.6.

Figure 2.6	
	Because the expression Exp. 2.11 is equivalent to the expression Exp. 2.4, the circuit in Figure 2.6 is also equivalent to the circuit in Figure 2.5a.  Obviously, the circuit in Figure 2.6 is much simpler.
	In practice, it is usually required to find the simplest expression before a circuit is synthesized.  It is easily understood that the simplest circuit requires minimum components to perform the same function.  Therefore, the cost is also minimized.  However, it is not easy to say that an expression reaches its simplest form.  For example, is Exp. 2.4 the simplest?  If  an expression is manipulated using the Boolean Algebra theorems, it requires experience to determine whether a simplest expression is obtained.  Therefore, another method, called Karnaugh-map, is usually adopted.  Correctly using the Karnaugh-map may help in finding the simplest minterm or maxterm form of an expression.

2.7.2 The Karnaugh map
	A Karnaugh-map (or K-map) is a representation of the truth table.  Each Karnaugh-map consists of several cells linked together.  The number of cells is equal to the number of rows in a truth table, i.e. 2n for n independent variables.  Therefore, for different number of variables, there are different Karnaugh-maps.  The Karnaugh-maps for 2, 3, and 4 variables are shown in Figure 2.7.

a. Karnaugh-map for 2 variables.	b. Karnaugh-map for 3 variables.	
	
c. Karnaugh-map for 4 variables.	
Figure 2.7.  Karnaugh-maps.	
	The binary numbers shown in the corner of each cell represent the corresponding rows in the truth table.  For example, the cell marked with binary number 110, in Figure 2.7b, represents the row 110 in the truth table where the values of A, B, and C are 1, 1, and 0, respectively.  Same as the truth table, for each variable, say A, the values of the variable in half of the cells are 1 and in the other half are 0.  If we partition the cells into regions, we can say that half of the cells in the region that the values of A is 1, or simply in region A.  The other half of the cells in the region that the values of A is 0, or in region .  As in Figure 2.7b, the cells marked with binary numbers, 100, 101, 110, 111 are in the region A while the cells numbered 000, 001, 010, 011 are in the region .  Similarly, we can partition the cells into two regions according to the values of each other variable.  Each cell is within n regions for n different variables.  For example, the cell numbered 110 in Figure 2.7b, is within the regions A, B, and .
	Another property of the Karnaugh-map is that the cells in the Karnaugh-map are organized in a way that each cell is adjacent to n cells where n is the number of independent variables.  Two cells are said to be adjacent to each other if there is only one difference in the values of independent variables presented by the two cells.  For example, the cell numbered 110 in Figure 2.7b, is adjacent to the cells numbered 010, 100, and 111 respectively.  This particular property helps a lot in finding the simplest expression of a function.
	Because of the definition of adjacency, readers may find other Karnaugh-maps that may not appear the same as in Figure 2.7.  There are different methods to find a Karnaugh-map.  Experienced users of Karnaugh-map may even develop their own styles.  However, for beginners, we introduce the following methods to find a correct Karnaugh-map very easily.
2.7.2.1 Karnaugh map for 2 variables
	The number of cells in a Karnaugh-map for two variables is 22, i.e. 4, as in Figure 2.8a.

Figure 2.8	

	Next, the values of A are assigned to the cells as in Figure 2.8b.  The two cells in the left-hand side are inside the region A; while the cells in the right-hand side are inside the region .
	Finally, the values of B are assigned to the cells (Figure 2.8c).  The two cells on the top (with values 11 and 01) are inside the region B.  The cells on the bottom (with values 10 and 00) are inside the region .
	The binary numbers in the corner of each cell represents the corresponding rows in the truth table.

2.7.2.2 Karnaugh map for 3 variables
	There are 23, i.e. 8, cells in a Karnaugh-map for three variables as in Figure 2.9a.

Figure 2.9	
	As in Figure 2.9b, The values of A are assigned so that the four cells on the left are inside the region A and the other inside the region .  Then, the values of B are assigned as in Figure 2.9c.  This makes the cells on the top be inside the region B and those on the bottom inside the region .  Finally, the values of C are assigned to the celled.  The four cells in the middle are inside the region C and the four cells on the two sides are inside the region .
2.7.2.3 Karnaugh map for 4 variables

	
	
Figure 2.10	
	The number of cells in the Karnaugh-map for four variables is 24, i.e. 16, as in Figure 2.10a.  The next step is to assign values of A to the cells (Figure 2.10b).  Then, the assignment of the values of B, C, and D (Figure 2.10c, 2.10d, and 2.10e respectively) are followed.
	The region A occupies the eight cells on the left and region  on the right.  The eight cells on the top are inside region B and the bottom eight inside region .  The region C is the two columns in the middle while the region  is the columns on two sides.  The two rows in the middle is inside region D.  The top and bottom rows are inside region .
2.7.2.4 Transferring the function values
	Because a Karnaugh-map represents a truth table of a function and each cell in a Karnaugh-map represents a row in the truth table,  the last step to complete the Karnaugh-map is to transfer the function values into the map as in Figure 2.11.

Figure 2.11	
	Having completed the Karnaugh-map, we can start looking for the simplest logical expression for the function.
2.7.3 Grouping the cells in a Karnaugh-map
	From a truth table, we can obtain an expression in standard sum of products form by looking at the rows where the values of the function being 1.  If we look at those rows where the values of the functions being 0, we can get an expression in standard product of sums form.
	Similarly, using Karnaugh-map to find the expression in sum of products form, we need all the cells that the value of the function is 1.  Correctly grouping these cells, we can get the simplest expression in sum of products form.  If we group all the cells in a Karnaugh-map that the value of the function is 0, the resultant expression is in product of sums form.  The following rules govern the grouping of the cells:

i.	Only adjacent cells can be grouped together.
ii.	The number of cells to be grouped must be a power of 2, i.e. 1, 2, 4, 8, etc.
iii.	While not violating the rules above, include as many cells in a group as possible.
iv.	Cells can be included in more than one group in order to fulfill rule (iii) above.  However, number of groups must be minimized.
v	All cells containing the specific value, i.e. 1 or 0, must be grouped.
	Figures 2.12 and 2.13 show several examples of cell grouping.  Those in the left-hand side are incorrect grouping while those in the right-hand side are correct groupings.

		

		
		
a. Incorrect grouping.	b. Correct grouping.	
Figure 2.12. Groupings in 3-variable Karnaugh map.	

		

		
a. Incorrect grouping.	b. Correct grouping.	
Figure 2.13. Groupings in 4-variable Karnaugh map.	
2.7.4 Obtaining the expression
	Once all the 1’s or 0’s are correctly grouped, the simplest expression can be found by converting each group of cells to a minterm or maxterm, respectively.  In the Karnaugh-map, each group represents either a minterm or maxterm depending on the values of the function in the group.  
	Recall that the Karnaugh map can be split into two regions for each variable.  Each minterm or maxterm is found by checking whether a group is within a region for each variable.
	For the group representing a minterm, the region variable is included if the group is within the region of the variable.  However, for the group representing a maxterm, the complement of the region variable is included if the group is within the region of the variable.  In both cases, if a group is across both regions, either complemented or not, of a variable, the variable will not appear in the term.

Figure 2.14	

	Consider the example in Figure 2.14.  A group consists of two cells of which the values of the function are 1.  This group represents a minterm.  The variables in the minterm are determined as follows:

i.	For variable A, the group is within region A, so A is included in the term;
ii.	For variable B, the group is within region , so is included in the term;
iii.	For variable C, the group across both regions C and , therefore, neither C nor  is included;
iv.	For variable D, the group is within region D, so D is included in the term.
	As a result, the group represents the term .

Figure 2.15	
	Similarly, the maxterm represented by the group in Figure 2.15 is found by:

i.	For variable A, the group is within region A, so  is included in the term;
ii.	For variable B, the group is within region , so B is included in the term;
iii.	For variable C, the group across both regions C and , therefore, neither C nor  is included;
iv.	For variable D, the group is within region D, so  is included in the term.
	Because a maxterm is expected, the term represented by the group is ().
	Notice that a term will consists of three variables if the group consists of two cells.  If four cells are grouped together, the term represented by the group will have only two variables.  In general, a term represented by a group of 2n cells will consist of only (N-n) variables where N is the total number of variables.
	A complete expression is found by adding (OR) all the minterms or multiplying (AND) all the maxterms represented by the groups of cells.  The simplicity of the expression is guaranteed if the cells are grouped correctly.
	
Example 2.10
The truth table of a function F is given below.  Find the simplified expression of F.
A	B	C	D	F	
0	0	0	0	0	
0	0	0	1	0	
0	0	1	0	1	
0	0	1	1	1	
0	1	0	0	0	
0	1	0	1	0	
0	1	1	0	0	
0	1	1	1	1	
1	0	0	0	0	
1	0	0	1	0	
1	0	1	0	1	
1	0	1	1	1	
1	1	0	0	0	
1	1	0	1	1	
1	1	1	0	0	
1	1	1	1	1	
Solution:
Because F is a function of four independent variables, a Karnaugh map for four variables is required.  Figure 2.16 shows the completed Karnaugh maps with grouping 1’s (Figure 2.16a) and 0’s (Figure 2.16b).

a. Grouping all 1’s.	b. Grouping all 0’s.	
Figure 2.16	
The expression obtained from Figure 2.16a is a simplified sum of products expression while the one obtained from Figure 2.16b is in product of sums form.
From Figure 2.16a, we get:
F	=	ABD + CD + 	(Exp. 2.12)
From Figure 2.16b, we get:
F	=	  	(Exp. 2.13)
Since not a specific form of expression is required, both expressions satisfy the requirement.
2.8 Synthesis of logic circuits
2.8.1 Two-level Synthesis
	Having found the simplest expression of a function, a logic circuit can be synthesized according to the expression.  Taking the expressions Exp. 2.12 and Exp. 2.13 as examples, each product is synthesized by an AND gate and each sum by an OR gate.  The circuit corresponding to expressions Exp. 2.12 and Exp. 2.13 are given in Figure 2.17a and 2.17b respectively.

a.	
	
b.	
Figure 2.17.	
	In Figure 2.17a, we can see that each minterm is synthesized by an AND gate.  The outputs of all the AND gates are connected to the inputs of the OR gate which adds all the products.  On the other hand, in Figure 2.17b, each maxterm is synthesized by an OR gate.  The outputs of the OR gates are multiplied to form an product at the output of the AND gate.  Ignoring the preceding NOT gates, there are two levels of logic gates.

2.8.2 Using single type of logic gates
	Note that in Figure 2.17, three types of logic gates, NOT, AND, and OR gates, are used.  In most cases, only single type of logic gates are used.  Because producing large quantity of a single type of gates can reduce the costs.
	NAND gates are usually used for this purpose and it is called universal gates because proper use of NAND gates can simulate the functions of NOT, AND, and OR gates.  NOR gates also serve the same functions.  However, the use of NOR gates is less popular.
	An expression in sum of products form can be rearranged so as only NAND functions are involved.  On the other hand, an expression consists of only NOR functions can be rearranged from the expression in product of sums form.
	Taking the expressions Exp. 2.12 and Exp. 2.13 as examples, 
F	=	ABD + CD + 	(Exp. 2.14)
can be rearranged as:
F	=	
	=		(Exp. 2.15)
There are three terms, F(W, X, Y) = , operated by a NAND function in Exp. 2.15.  In addition, each of the three terms are results of NAND function.  Only NAND function is involved.  As a result, the expression in Exp. 2.15 can be synthesized by NAND gates only as in Figure 2.18a.

a.

b.	
Figure 2.18.	
	Similarly, the expression Exp. 2.13 can be rearranged as:
F	=	  
	=	
	=		(Exp. 2.16)
	The functions in the expression Exp. 2.16 are NOR only.  Therefore, the expression can be synthesized by NOR gates only as in Figure 2.18b.

2.9 Problem Solving
	In conclusion, using Boolean Algebra to solve a problem involves the following procedures:
i.	Define the problem, i.e. identifying the boolean variables and function, and define logic values for different conditions;
ii.	Use a truth table to list the function values for all possible conditions;
iii.	Find the simplified expression of the function using either Boolean Algebraic theorems or Karnaugh-map method;
iv.	With the simplified expression, use logic gates to synthesis a logic circuit.
	In this Chapter, we have only dealt with the logic functions with concrete values for each condition, i.e. the functions only depend on the boolean variables.  Since different combinations of the values of the boolean variables determine the value of the function, the circuits obtained from such functions are called Combinational Logic Circuits.
	
Example 2.11
Use combinational logic circuit to solve the problem given in Example 2.1.
Solution:
We follow the steps given above, the first and second steps are given in Example 2.1.  The following is the truth table found:

A	B	C	V	
0	0	0	0	
0	0	1	0	
0	1	0	0	
0	1	1	1	
1	0	0	0	
1	0	1	1	
1	1	0	1	
1	1	1	1	
Table 2.21	
The expression of V in standard sum of products form is:
V =  +  +  + ABC
The simplified expression of V can either be found by Karnaugh-map or Boolean Algebraic theorems:
 
	V =  +  +  + ABC
=  ( + ABC) + 
( + ABC) + 
( + ABC)
=   BC + AC + AB	
(a) Karnaugh-map method.	(b) Boolean algebraic theorems.	
which is:
V = AB + BC + AC	(Exp. 2.17) 
The expression in Exp. 2.17 can be synthesised by three AND gates and one OR gate as in Figure 2.19(a).
If we rearrange the expression Exp. 2.17, we have:
V	= AB + BC + AC
 	= 
	= 	(Exp. 2.18) 
Using the expression in Exp. 2.18, the circuit can be synthesised by NAND gates only as in Figure 2.19(b).

		
(a) using AND-OR gates.	(b) using NAND gates only.	
Figure 2.19. Combinational circuit of function V.