46.

[Top] [Next] [Prev]

Exercises

1.(Gate Logic) Draw schematics for the following functions in terms of AND, OR, and inverter gates. X (Y + Z)

X Y + X Z


W (X + Y Z)

2. (Gate Logic) Draw the schematics for the following functions using NOR gates and inverters only:

3. (Gate Logic) Draw the schematics for the following functions using NAND gates and inverters only:

4.(Gate Logic) Draw switch networks for the XOR and XNOR Boolean operators.
5.(Gate Logic) Design a hall light circuit to the following speci-\xde ca-tion. There is a switch at either end of a hall that controls a single light. If the light is off, changing the position of either switch causes the light to turn on. Similarly, if the light is on, changing the position of either switch causes the light to turn off. Write your assumptions, derive a truth table, and describe how to implement this function in terms of logic gates or switching networks.
6.(Laws and Theorems of Boolean Algebra) Use switching diagrams to demonstrate the validity of the following simplification theorems:

X + X Y = X

7.(Laws and Theorems of Boolean Algebra) Prove the following simpli\xde cation theorems using the \xde rst eight laws of Boolean -algebra:

X (X + Y) = X

8.(Laws and Theorems of Boolean Algebra) Verify that OR and AND are duals of each other.

NOR and NAND are duals of each other.
XNOR and XOR are duals of each other.
XNOR is the complement of XOR:

9.(Laws and Theorems of Boolean Algebra) Prove, using truth tables, that

10. (Laws and Theorems of Boolean Algebra) Use DeMorgan's theorem to compute the complement of the following Boolean expressions:

A (B + CD)

11.(Laws and Theorems of Boolean Algebra) Form the complement of the following functions:

(A,B,C,D) =
(A,B,C,D) =

12.(Laws and Theorems of Boolean Algebra) Using Boolean algebra, verify that the schematic of Figure Ex2.12 implements an XOR function.

13.(Boolean Simpli\xde cation) Simplify the following functions using the theorems of Boolean algebra. Write the particular law or theorem you are using in each step. For each simpli\xde ed function you derive, how many literals does it have?

(X,Y) =
(X,Y) =
(X,Y,Z) =
(X,Y,Z) =
(W,X,Y,Z) =

14.(Boolean Simpli\xde cation) Consider the function (A,B,C,D) = . Draw its schematic using AND, OR, and inverter gates. Using Boolean algebra, put the function into its minimized form and draw the resulting schematic.
15.(Canonical Forms) Consider the function (A,B,C,D) = S m(0,1,2,7,8,9,10,15).

Write this as a Boolean expression in canonical min-term form.
Rewrite the expression in canonical maxterm form.
Write the complement of in "little m" notation and as a canonical min-term expression.
Write the complement of in "big M" notation and as a canonical maxterm expression.

16.(Canonical Forms and Boolean Simpli\xde cation) Given the following function in product of sums form, not necessarily minimized:

F(W,X,Y,Z) = 

Express the function in the canonical sum of products form. Use "little m" notation.
Reexpress the function in minimized sum of products form.
Express in minimized sum of products form.
Reexpress in minimized product of sums form.

17.(Boolean Simplification) Using K-maps, find the following:

Minimum sum of products form for the function and its complement given in Exercise 2.15.
Minimum product of sums form for the function and its complement given in Exercise 2.15.

18.(Boolean Simplification) Use Karnaugh maps (K-maps) to simplify the following functions in sum of products form. How many literals appear in your minimized solutions?

(X,Y,Z) = P M(0,1,6,7)
(W,X,Y,Z) = P M(1,3,7,9,11,15)
(V,W,X,Y,Z) = P M(0,4,18,19,22,23,25,29)
(A,B,C,D) = S m(0,2,4,6)
(A,B,C,D) = S m(0,1,4,5,12,13)
(A,B,C,D,E) = S m(0,4,18,19,22,23,25,29)
(A,B,C,D,E,F) = S m(3,7,12,14,15,19,23,27,28,29,31,35,39,44,
45,46,48,49,50,52,53,55,56,57,59).

19.(Boolean Simplification) Determine the minimized realization of the following functions in the sum of products form:

(W,X,Y,Z) = S m(0,2,8,9) + S d(1,3)
(W,X,Y,Z) = S m(1,7,11,13) + S d(0,5,10,15)
(V,W,X,Y,Z) = S m(2,8,9,10,13,15,16,18,19,23) + S d(3,11,17,22)
(V,W,X,Y,Z) = S m(0,1,2,9,13,16,18,24,25) + S d(8,10,17,19)

20.(Boolean Simplification) Use the K-map method to \xde nd the minimized product of sums expressions for the following Boolean functions:

(A,B,C) = A Ý B Ý C
(A,B,C) = AB + BC + AC
(A,B,C,D) = S m(1,3,5,7,9) + S d(6,12,13)
(A,B,C,D) = P M(0,1,6,7)
(A,B,C,D) = S m(0,2,4,6)

21.(Positive and Negative Logic) Show the following:

A positive logic AND is equivalent to a negative logic OR.
A positive logic NOR is equivalent to a negative logic NAND.
A positive logic XOR is equivalent to a negative logic XNOR.
A positive logic XNOR is equivalent to a negative logic XOR.

22.(Quine-McCluskey Method) Use the Quine-McCluskey method to \xde nd the minimum equivalent forms for the following Boolean expressions.

(X,Y,Z) = S m(2,3,4,5)
(A,B,C,D) = S m(0,1,4,5,12,13)

23.(Quine-McCluskey Method) Given the function F(A,B,C,D) = S m(1,5,7,8,9,13,15) + d(4,14), find the minimum sum of products form using the Quine-McCluskey method. Show your process of deriving the prime implicants. Include the implication chart from which your minimum sum of products form is derived.
24.(Karnaugh Map Method) There may be more than one true minimum equivalent form for a given Boolean expression. Demonstrate this by drawing a four-variable K-map that has two different minimized forms for the same Boolean expression, each with the same number of terms and literals.
25.(Karnaugh Map Method) Using a four-variable K-map, fill it with 1's and 0's to find a function that illustrates the following points. Write the expressions for each of the requested forms and count the number of terms and literals for each one:

The minimized sum of products and product of sums forms have the same number of terms and literals.
The minimized sum of products form has fewer terms and literals than the minimized product of sums form.
The minimized product of sums form has fewer terms and literals than the minimized sum of products form.

26.(Combinational Logic Design) Consider a five-input Boolean function that is asserted whenever exactly two of its inputs are asserted.

Construct its truth table.
What is the function in sum of products form, using "little m" notation?
What is the function in product of sums form, using "big M" notation?
Use the Karnaugh map method to simplify the function in sum of products form.

27.(Combinational Logic Design) In this chapter, we've examined the BCD increment by 1 function. Now consider a binary increment by 1 function defined over the 4-bit binary numbers 0000 through 1111.

Fill in the truth table for the function.
Fill in the four 4-variable K-maps, and \xde nd the minimized sum of products for each output function.
Repeat the process for the minimized product of sums form. Which leads to the simpler implementation in terms of the number of literals?

28.(Combinational Logic Design) In this chapter, we've examined a 2-bit binary adder circuit. Now consider a 2-bit binary subtractor, de\xde ned as follows. The inputs A, B and C, D form the two 2-bit numbers N1 and N2. The circuit will form the difference N1 - N2 on the output bits F (most signi\xde cant) and G (least signi\xde cant). Assume that the circuit never sees an input combination in which N1 is less than N2. The output bits are don't cares in these cases.

Fill in the four-variable truth table for F and G.
Fill in the K-map for the minimum sum of products expression for the functions F and G.
Repeat to find the minimum product of sums expression for F and G.

29.(Combinational Logic Design) Consider a four-input function that outputs a 1 whenever an odd number of its inputs are 1.

Fill in the truth table for the function.
Fill in the K-map to \xde nd the minimum sum of products expression for the function. What is it? Can the function be minimized using the K-map method?
Can you think of a more economical way to implement this function if XOR gates are allowed? (Warning: It will be very tedious to try to simplify this function using Boolean algebra, so think about the question first!)

30.(Combinational Logic Design) Design a combinational circuit with three data inputs D2, D1, D0, two control inputs C1, C0, and two outputs R1, R0. R1 and R0 should be the remainder after dividing the binary number formed from D2, D1, D0 by the number formed by C1, C0. For example, if D2, D1, D0 = 111 and C1, C0 = 10, then R1, R0 = 01 (that is, the remainder of 7 divided by 2 is 1). Note that division by zero will never be requested.

Fill in truth tables for the combinational logic functions R1 and R0.
Derive minimized sum of product realizations of these functions using the Karnaugh map method.
Draw a circuit schematic that implements R1 and R0 using NAND gates only. You may assume any fan-in gates that you need.

---

[Top] [Next] [Prev]
This file last updated on 06/26/96 at 21:04:10.
[e-mail];