Chapter 2
Boolean Algebra and Digital Logic
Exercise
2.1.	Refer to Example 2.1, if the Sales Manager is also authorized to sign a cheque and the conditions for validity of the cheque remain unchanged, find the truth table for the validity of a cheque.
2.2.	Find the truth table of the following expressions:
i.	F =  + (  )
ii.	F = 
iii.	F = 
2.3.	Draw the logic circuit diagrams for the functions in exercise 2.2.
2.4.	Given the logic circuit in Figure 2.5, find the logical expression of function F.
2.5.	Prove by truth table the followings:
i.	
ii.	
iii.	
iv.	
v.	 
vi.	
	 =  
vii.	
viii.	(A +  + C) (A +  + ) ( + B + C) ( +  + C) 
	=  +  +  + 
2.6.	Prove by Boolean Algebraic theorems the expressions in exercise 2.5.

2.7.	From the following truth tables, find the expressions for the functions in both standard sum of products and standard product of sums forms.
i.
Inputs	Functions	
A	B	C	P	Q	
0	0	0	0	1	
0	0	1	0	1	
0	1	0	0	0	
0	1	1	1	0	
1	0	0	0	1	
1	0	1	1	1	
1	1	0	0	0	
1	1	1	1	1	
ii.
Inputs	Functions	
A	B	C	D	X	Y	Z	
0	0	0	0	0	1	0	
0	0	0	1	1	0	1	
0	0	1	0	0	0	1	
0	0	1	1	0	0	0	
0	1	0	0	0	1	0	
0	1	0	1	1	0	1	
0	1	1	0	0	1	1	
0	1	1	1	0	0	0	
1	0	0	0	1	1	0	
1	0	0	1	0	1	0	
1	0	1	0	1	0	0	
1	0	1	1	0	1	0	
1	1	0	0	1	0	1	
1	1	0	1	0	0	0	
1	1	1	0	0	1	1	
1	1	1	1	0	0	1	
2.8.	Find the simplified expressions in both sum of products and product of sums forms using Boolean Algebraic theorems for the functions P, Q, X, Y, and Z in exercise 2.7.
2.9.	Simplify the following expressions to sum of products form using Boolean Algebraic theorems:
i.	
ii.	
iii.	

2.10.	Simplify the following expressions to product of sums from using Boolean Algebraic theorems:
i.	    
ii.	
iii.	
2.11.	Use Karnaugh-map to find the simplified expressions of functions P, Q, X, Y, and Z, in exercise 2.7, in both sum of products and product of sums form.  Draw the logic circuits for the simplified functions.
2.12.	Simplify the following expressions to sum of products form using Karnaugh-map method.  Synthesis the logic circuit for the functions with NAND gates only.
i.	F(A, B, C) = S (0, 2, 3, 6)
ii.	F(A, B, C, D) = S (1, 3, 7, 12, 13,14, 15)
iii.	F(A, B, C, D) = S (2, 3, 4, 6, 7,11, 15)
iv.	F(A, B, C, D) = S (6, 7, 9, 11, 13, 14, 15)
2.13.	Simplify the following expressions to product of sums form using Karnaugh-map method. Synthesis the logic circuit for the functions with NOR gates only.
i.	F(A, B, C) = P (1, 2, 3, 5)
ii.	F(A, B, C, D) = P (0, 1, 3, 4, 7, 8, 12, 15)
iii.	F(A, B, C, D) = P (0, 2, 4, 8, 10, 12, 14)
iv.	F(A, B, C, D) = P (1, 4, 5, 10, 12, 13, 14)
2.14.	Use combinational circuit to solve the problem in exercise 2.1.
2.15.	The English subject in a school consists of four parts: Essay, Comprehension, Grammar and Oral.  A student passes the English subject if the student
i.	passes all four parts; or
ii.	passes Oral and any other two parts; or
iii.	passes Essay and any other two parts; or
iv.	passes Essay and Oral.
	Use four variables (A, B, C, D) to represent the four parts of the English subject respectively, i.e. A represents Essay and a logic 1 represents pass in Essay while a logic 0 represents fail in Essay.  Find the function, P, in terms of the four variables, that represents whether a student passes the subject.  Use a combinational circuit to solve the problem.
Review Exercise
2.16	Prove by truth table the De Morgan's Theorems.
2.17	Prove the following expressions by truth table:

i.	(A + ) (B + ) = AB + 
ii.	(A + B) (A + C) = A + BC

2.18	Prove by Boolean Algebra theorem the following:

i.	 +  +  + ABCD = AB
ii.	B + C = ( A + B + C) ( + B + C) ( + B + )
iii.	 +  +  =  +  +  +  + 
iv.	D (+B+C+) (A+B++) = (D +  + ) ( + BD + AC)

2.19	Simplify the following expressions to sum of products form using Boolean Algebraic theorems: 

i.	F =  +  +  + 
ii.	F = 	
iii.	F = BD + AD + ABD + ABC + D
iv.	F = BD + BCD + BC + ABC + B
v.	F = 	
vi.	F = (B + C) ( + ) (A + )
vii.	F = (A +  + C) (AB + C)
viii.	F = (BC + )(CD + )
ix.	F = (A + B + C) (+  + C) (A +  + )
x.	F = 
xi.	F = 

2.20	(i).	Prove by truth table method the following logic expressions:
a.	(A + ) (B + ) = AB + 
b.	A (B + C) = AB + AC	

(ii).	Use the result of (i) or other Boolean Algebra theorems, simplify the function F, in sum of products form.
F = (A + B + C) (B +  + ) (+ B + C) ( +  + )

2.21	Simplify the following logical expressions in sum of products form using Karnaugh-map methods:

i.	F(X, Y, Z) = S(2, 3, 4, 6)
ii.	F(A, B, C, D) = S(7, 8, 9, 11, 13, 15)	
iii.	F(A, B, C, D) = S(0, 2, 4, 6, 7, 14, 15)
iv.	F(A, B, C, D) = S(1, 3, 4, 6, 9, 11)
v.	F(A, B, C, D) = S(4, 5, 10, 11, 12, 13)

2.22	Simplify the following logical expressions in  product of sums form using Karnaugh-map methods:

i.	F(A, B, C, D) = P(3, 5, 7, 11, 14, 15)
ii.	F(A, B, C, D) = P(0, 2, 3, 4, 6, 7, 9, 10, 11, )
2.23	(a)	Given the truth table:

A	B	C	X	
0	0	0	0	
0	0	1	1	
0	1	0	0	
0	1	1	0	
1	0	0	0	
1	0	1	1	
1	1	0	1	
1	1	1	1	
		Find the simplified product of sums expression of X in terms of input variables A, B, and C using the Karnaugh map method.
	(b)	Draw the logic circuit diagram of X using NOR gates only.

2.24	(i)	Given the truth table of functions, X and Y, below:

A	B	C	Y	X	
0	0	0	0	0	
0	0	1	1	0	
0	1	0	0	1	
0	1	1	1	1	
1	0	0	1	0	
1	0	1	1	0	
1	1	0	0	1	
1	1	1	1	0	

	Simplify the function, X and Y, in terms of input variables, A, B, and C by using Karnaugh Map method.  Write down the simplified boolean expression of X in sum of products form, the simplified boolean expression of Y in product of sums form.

	(ii)	Find the logic expression of X so that it can be synthesised by NAND gates only and draw the circuit diagram using only NAND gates.

	(iii).	Find the logic expression of Y so that it can be synthesised by NOR gates only and draw the circuit diagram using only NOR gates.
2.25	(i)	Given the truth table:

A	B	C	X	
0	0	0	0	
0	0	1	1	
0	1	0	1	
0	1	1	1	
1	0	0	0	
1	0	1	0	
1	1	0	0	
1	1	1	1	
		Find the simplified sum of products expression of X in terms of input variables A, B, and C using the Karnaugh map method.
	(ii)	Draw the logic circuit diagram of X using NAND gates only.

2.26	From the following truth tables, use Karnaugh-map to find the simplest expressions for the functions in both sum of products and product of sums forms.

A	B	C	D	X	
0	0	0	0	1	
0	0	0	1	0	
0	0	1	0	0	
0	0	1	1	0	
0	1	0	0	1	
0	1	0	1	0	
0	1	1	0	1	
0	1	1	1	0	
1	0	0	0	1	
1	0	0	1	1	
1	0	1	0	0	
1	0	1	1	1	
1	1	0	0	0	
1	1	0	1	0	
1	1	1	0	1	
1	1	1	1	0	

	Draw the logic circuit diagram of the function using NAND gates only.

2.27	The truth table given below defines the state of each of three lamps R, A, and G when connected to a 4-stage binary counter W X Y Z via a decoding network.

W	X	Y	Z	R	A	G	
0	0	0	0	1	0	0	
0	0	0	1	1	0	0	
0	0	1	0	1	0	0	
0	0	1	1	1	0	0	
0	1	0	0	1	0	0	
0	1	0	1	1	0	0	
0	1	1	0	1	0	0	
0	1	1	1	1	1	0	
1	0	0	0	0	0	1	
1	0	0	1	0	0	1	
1	0	1	0	0	0	1	
1	0	1	1	0	0	1	
1	1	0	0	0	0	1	
1	1	0	1	0	0	1	
1	1	1	0	0	0	1	
1	1	1	1	0	1	0	
(a)	Deduce the boolean expressions for R, A, and G in terms of W, X, Y, Z.
(b)	Indicate how the decoder may be implemented using the minimum number of logic gates.  Assume all types of gates are available.

2.28	Given a schematic diagram as shown in Figure 2.21, answer the following questions.

Figure 2.21.	

(a)	i.	Write down the boolean expression of X.
ii.	Obtain a truth table for this logic diagram.
iii.	State one logic gate whose function is identical  to this circuit.

(b)	i.	Simplify the following boolean function in product of sums form, by means of a four variable Karnaugh-map.

	F(A,B,C,D) = S(2, 3, 4, 5, 6, 7, 10, 11, 14, 15)

ii.	From part (i), draw a logic diagram with
	1.	OR-AND-NOT gates,
	2.	NAND gates only (proof is required).

2.29	(a)	State De Morgan’s theorems.

(b)	Simplify the following boolean expression:
F = 

(c)	Apply De Morgan’s theorem to implement the circuit for F in (b) by NAND gates only.

2.30	(a)	i. 	Prove by truth table the following:

	(A + B)(A + C) = A + BC

ii. 	Prove by Boolean algebra theorems the following:

	= 

iii. 	Simplify the following expression in sum of product form using the result of (i) above or other Boolean Algebra theorems:

	F = 

(b)	The truth table below defines the output functions, X and Y, of a decoder circuit which is connected to four input sources A, B, C, D.
A	B	C	D	X	Y	
0	0	0	0	1	1	
0	0	0	1	1	0	
0	0	1	0	1	0	
0	0	1	1	1	1	
0	1	0	0	0	1	
0	1	0	1	0	0	
0	1	1	0	0	0	
0	1	1	1	0	1	
1	0	0	0	0	1	
1	0	0	1	1	0	
1	0	1	0	0	0	
1	0	1	1	1	1	
1	1	0	0	0	1	
1	1	0	1	0	0	
1	1	1	0	1	0	
1	1	1	1	1	1	

(i)	Use the Karnaugh-map method, find the simplified function of X and Y respectively in sum of product form.
(ii)	Draw the decoder circuit using NAND gates only.

2.31	Simplify the following boolean functions using Boolean Algebraic theorems.

(a)	i.	
	ii.	(A + B) (A + C)
	iii.	
 (b)	A combinational circuit has three inputs, C1, C2, and C2.  the specification describing the output is as follows:

	Output P is high when any two control inputs or all three inputs are high.

i.	Deduce the truth table and write down the boolean expression of this network.
ii.	Hence, or otherwise, simplify the boolean expression obtained in (i).
iii.	Suggest one implication of this circuit.

2.32	(a).	Draw the symbols and give the truth tables of the following logic gates:
i.	AND
ii.	OR
iii.	NOT

	(b).	Prove by truth table the following logic expressions:

i.	 = 
ii.	 = A + B

(c).	Prove by Boolean Algebra theorem the following:

 = AB

(d).	Use the result of (b) or otherwise, simplify the following expression using Boolean Algebra theorems.

2.33	(a).	Given the truth table of a function, X, below:

A	B	C	X	
0	0	0	1	
0	0	1	0	
0	1	0	1	
0	1	1	0	
1	0	0	1	
1	0	1	1	
1	1	0	1	
1	1	1	0	

	Simplify the function, X, in terms of input variables, A, B, and C by using Karnaugh Map method.  Write down the simplified boolean expression in product of sum form.

(b).	Find the logic expression of X so that it can be synthesised by NAND gates only.  Draw the logic circuit diagram of X using only NAND gates.
2.34	(a)	Prove by Boolean Algebra theorem the followings:

i.	 = 
ii.	 = 

(b)	Given the truth table of the function X below:

A	B	C	X	
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	

	Find the simplified function of X in sum of product form.  Draw the logic circuit diagram of X using NAND gates only.

2.35	(a)	Four sensors A, B, C, and D are located on the corners of a square in a clockwise manner and sensor A is installed on the top left corner.  An alarm condition exists when two adjacent sensors are simultaneously high.  Design the logic by using Karnaugh map.

	(b)	Simplify the answer by Boolean Algebraic theorems and draw the final answer using AND and OR gates.	

2.36	(a)	Simplify the following boolean expression:

F = 

	(b)	Draw your answer using NOR gate only.

	(c)	Prove your answer by truth table.

2.37	(a)	State De Morgan's theorems.

	(b)	Prove by truth table method the following logic expressions:
i.	(A + ) (B + ) = AB + 
ii.	(A + B) (A + C) = A + BC

(c)	Prove by Boolean Algebraic theorem the following:

  + +  + ABCD  + +  
= 

(d)	Use the result of (b) and other Boolean Algebraic theorems, simplify the function F, in sum of products form.

F =  

2.38	(a).	Given the logic circuit in Figure 2.22, find the simplified circuit for function F, using AND, OR and NOT gates.

Figure 2.22.	

	(b).	Given the truth table:

A	B	C	output function
X	
0	0	0	1	
0	0	1	0	
0	1	0	0	
0	1	1	0	
1	0	0	1	
1	0	1	0	
1	1	0	1	
1	1	1	0	

	Find the simplified expression in sum of products form for the function X in terms of input variables A, B, C using the Karnaugh map method.

	(c).	Draw the logic circuit diagram of X using logic gate symbols.