Deck 3: Boolean Algebra and Digital Logic

Question 1

Construct a truth table for the following:
Reference of Example 3.7:

Answer 1

There are certain basic rules to be followed while performing logical operation. They are:
If x=0 then x' = 1.
Rules for sum:
i. If x=0 and y=0, then x+y = 0
ii. If x=0 and y=1, then x+y = 1
iii. If x=1 and y=0, then x+y = 1
iv. If x=1 and y=1, then x+y = 1
Rules for Product:
i. If x=0 and y=0, then x.y = 0
ii. If x=0 and y=1, then x.y = 0
iii. If x=1 and y=0, then x.y = 0
iv. If x=1 and y=1, then x.y = 1
(a) Let the expression F= The truth table for the above expression would be: (b) Let the expression F= The truth table for the above expression would be: (c) Let the expression F= The truth table for the above expression would be:

Question 2

Is the following true or false? Prove your answer.

Answer 2

This statement can be proved by using either truth table method or by using identities. Let us choose the first one,
So, according to the given expression let us draw the truth table for L.H.S. Now let us find the truth table for R.H.S. From the above tables, if we compare them, the expressions in LHS and RHS are equal. Hence the given statement is true.

Question 3

Simplify the following functional expressions using Boolean algebra and its identities. List the identity used at each step.

Answer 3

a)x(y+z)(x'+z')
=(xy+xz)(x'+z') Distributive Law
=xx'z+xyz'+xx'z+xzz' Distributive Law
=0 + xyz' + 0+ 0 Inverse Law
=xyz' Identity Law in OR form
b)xy+xyz+xy'z+x'y'z'
=xy(1+z)+xy'z+x'y'z' Distributive Law
=xy+xy'z+x'y'z' Null or idempotent Law
=xy+y'(xz+x'z') Distributive Law
=xy+y'((x+x')z) Distributive Law
=xy+y'z Inverse Law
c)xy'z+x(y+z')'+xy'z'
=xy'z+x(y'z'')+xy'z' Simplified expression
=xy'z+xy'z+xy'z' Double complement Law
=xy'z+xy'(z+z') Distributive Law
=xy'z+xy' Inverse Law
=xy'(z+1) Distributive Law
=xy' Null or dominant Law

Question 4

Draw the truth table and rewrite the expression below as the complemented sum of two products:

Question 5

How many control lines does a multiplexer have if it has 32 inputs?

Question 6

True or false: When a JK flip-flop is constructed from an SR flip-flop, and R = KQ.

Question 7

Write a simplified expression for the Boolean function defined by each of the following Kmaps:

Question 8

Why is an understanding of Boolean algebra important to computer scientists?

Question 9

Name the four basic logic gates.

Question 10

What kind of circuit selects binary information from one of many input lines and directs it to a single output line?

Question 11

How is a Mealy machine different from a Moore machine?

Question 12

Draw circuits to implement the parity generator and parity checker shown in Tables 3.10 and 3.11, respectively.

Question 13

Investigate the operation of the following circuit. Assume an initial state of 0000. Trace the outputs (the Q s) as the clock ticks and determine the purpose of the circuit. You must show the trace to complete your answer.

Question 14

Write a simplified expression for the Boolean function defined by each of the following Kmaps (leave in sum-of-products form):

Question 15

Construct a truth table for the following:

Question 16

Show that
a) Using truth tables
b) Using Boolean identities

Question 17

Simplify the following functional expressions using Boolean algebra and its identities. List the identity used at each step.

Question 18

Given the Boolean function,
a) Derive an algebraic expression for the complement of F. Express in sum-of-products form.
b) Show that
c) Show that

Question 19

Assume you have the following truth tables for functions
a) Express in sum-of-products form.
b) Simplify each function.
c) Draw one logic circuit to implement the above two functions.

Question 20

A Null-Lobur flip-flop (NL flip-flop) behaves as follows: If N = 0, the flip-flop does not change state. If N = 1, the next state of the flip-flop is equal to the value of L.
a) Derive the characteristic table for the NL flip-flop.
b) Show how an SR flip-flop can be converted to an NL flip-flop by adding gate(s) and inverter(s). (Hint: What values must S and R have so that the flip-flop will be set and reset at the proper time when N = 1? How can you prevent the flip-flop from changing state when N = 0?)

Question 21

Create the Kmaps and then simplify for the following functions (leave in sum-of-products form):

Question 22

Which Boolean operation is referred to as a Boolean product?

Question 23

What are the two universal gates described in this chapter? Why are these universal gates important?

Question 24

How are sequential circuits different from combinational circuits?

Question 25

What does an algorithmic state machine offer that is not provided by either a Moore or a Mealy machine?

Question 26

Assume you have the following truth tables for functions
a) Express in sum-of-products form.
b) Simplify each function.
c) Draw one logic circuit to implement the above two functions.

Question 27

A Mux-Not flip-flop (MN flip-flop) behaves as follows: If M = 1, the flip-flop complements the current state. If M = 0, the next state of the flip-flop is equal to the value of N.
a) Derive the characteristic table for the flip-flop.
b) Show how a JK flip-flop can be converted to an MN flip-flop by adding gate(s) and and inverter(s).

Question 28

Create the Kmaps and then simplify for the following functions (leave in sum-of-products form):

Question 29

Using DeMorgan's Law, write an expression for the complement of F if F ( x,y,z )

Question 30

Use only the first seven Boolean identities to prove the Absorption Laws.

Question 31

Using the basic identities of Boolean algebra, show that

Question 32

Given the function,
a) List the truth table for F.
b) Draw the logic diagram using the original Boolean expression.
c) Simplify the expression using Boolean algebra and identities.
d) List the truth table for your answer in part c.
e) Draw the logic diagram for the simplified expression in part c.

Question 33

Design a truth table for a combinational circuit that detects an error in the representation of a decimal digit encoded in BCD. (This circuit should output a 1 when the input is one of the six unused combinations for BCD code.)

Question 34

List the steps necessary to read a word from memory in the 4 3 3 memory circuit shown in Figure 3.32.
Reference of Figure 3.32:

Question 35

Given the following Kmap, show algebraically (using Boolean identities) how the four terms reduce to one term.

Question 36

Which Boolean operation is referred to as a Boolean sum?

Question 37

Describe the basic construction of a digital logic chip.

Question 38

What is the basic element of a sequential circuit?

Question 39

Construct the XOR operator using only AND, OR, and NOT gates.

Question 40

Simplify the function from exercise 44 and draw the logic circuit.

Question 41

Construct Moore and Mealy machines that complement their input.

Question 42

Write a simplified expression for the Boolean function defined by each of the following Kmaps:

Question 43

Using DeMorgan's Law, write an expression for the complement of F if F ( x,y,z )

Question 44

Show that
a) Using truth tables
b) Using Boolean identities

Question 45

Using the basic identities of Boolean algebra, show that

Question 46

Construct the XOR operator using only NAND gates.

Question 47

Describe how each of the following circuits works and indicate typical inputs and outputs. Also provide a carefully labeled "black box" diagram for each.
a) Decoder
b) Multiplexer

Question 48

Construct a Moore machine that counts modulo 5.

Question 49

Write a simplified expression for the Boolean function defined by each of the following Kmaps:

Question 50

Create truth tables for the Boolean operators OR, AND, and NOT.

Question 51

Describe the operation of a ripple-carry adder. Why are ripple-carry adders not used in most computers today?

Question 52

What do we mean when we say that a sequential circuit is edge triggered rather than level triggered?

Question 53

Draw a half-adder using only NAND gates.

Question 54

Little Susie is trying to train her new puppy. She is trying to figure out when the puppy should get a dog biscuit as a reward. She has concluded the following:
1. Give the puppy a biscuit if it sits and wiggles but does not bark.
2. Give the puppy a biscuit if it barks and wiggles but does not sit.
3. Give the puppy a biscuit if it sits but does not wiggle or bark.
4. Give the puppy a biscuit if it sits, wiggles, and barks.
5. Don't give the puppy a treat otherwise.
Use the following:
S: Sit (0 for not sitting; 1 for sitting)
W: Wiggles (0 for not wiggling; 1 for wiggling)
B: Barking (0 for not barking; 1 for barking)
F: Biscuit function (0, don't give the puppy a biscuit; 1, give the puppy a biscuit)
Construct a truth table and find the minimized Boolean function to implement the logic telling Susie when to give her dog a biscuit.

Question 55

Construct two parity checkers using a Moore machine for one and a Mealy machine for the other.

Question 56

Write a simplified expression for the Boolean function defined by each of the following Kmaps:

Question 57

Using DeMorgan's Law, write an expression for the complement of F if F ( w,x,y,z )

Question 58

Use any method to prove the following either true or false.

Question 59

Using the basic identities of Boolean algebra, show that

Question 60

Draw a full-adder using only NAND gates.

Question 61

Tyrone Shoelaces has invested a huge amount of money into the stock market and doesn't trust just anyone to give him buying and selling information. Before he will buy a certain stock, he must get input from three sources. His first source is Pain Webster, a famous stock broker. His second source is Meg A. Cash, a self-made millionaire in the stock market, and his third source is Madame LaZora, world-famous psychic. After several months of receiving advice from all three, he has come to the following conclusions:
a) Buy if Pain and Meg both say yes and the psychic says no.
b) Buy if the psychic says yes.
c) Don't buy otherwise.
Construct a truth table and find the minimized Boolean function to implement the logic telling Tyrone when to buy.

Question 62

Using the lemma that two FSMs are equivalent if and only if they produce the same output from the same input strings, show that Moore and Mealy machines are equivalent.

Question 63

Find the minimized Boolean expression for the functions defined by each of the following truth tables:

Question 64

What is the Boolean duality principle?

Question 65

What are the three methods we can use to express the logical behavior of Boolean functions?

Question 66

In the context of digital circuits, what is feedback?

Question 67

Design a circuit with three inputs x , y , and z representing the bits in a binary number, and three outputs ( a , b , and c ) also representing bits in a binary number. When the input is 0, 1, 6, or 7, the binary output will be the complement of the input. When the binary input is 2, 3, 4, or 5, the output is the input shifted left with rotate. (For example, outputs 110; outputs 001.) Show your truth table, all computations for simplification, and the final circuit.

Question 68

A very small company has hired you to install a security system. The brand of system that you install is priced by the number of bits encoded on the proximity cards that allow access to certain locations in a facility. Of course, this small company wants to use the fewest bits possible (spending the least amount of money possible) yet have all of its security needs met. The first thing you need to do is to determine how many bits each card requires. Next, you have to program card readers in each secured location so that they respond appropriately to a scanned card.
This company has four types of employees and five areas that they wish to restrict to certain employees. The employees and their restrictions are as follows:
a) The Big Boss needs access to the executive lounge and the executive washroom.
b) The Big Boss's secretary needs access to the supply closet, employee lounge, and executive lounge.
c) Computer room employees need access to the server room and the employee lounge.
d) The janitor needs access to all areas in the workplace.
Determine how each class of employee will be encoded on the cards and construct logic diagrams for the card readers in each of the five restricted areas.

Question 69

Using the convolutional code and Viterbi algorithm described in this chapter, assuming that the encoder and decoder always start in State 0, determine the following:
a) The output string generated for the input: 10010110.
b) In which state is the encoder after the sequence in part a is read?
c) Which bit is in error in the string, 11 01 10 11 11 11 10? What is the probable value of the string?

Question 70

Using DeMorgan's Law, write an expression for the complement of F if F ( x,y,z )

Question 71

Simplify the following functional expressions using Boolean algebra and its identities. List the identity used at each step.

Question 72

The truth table for a Boolean expression is shown below. Write the Boolean expression in sum-of-products form.

Question 73

Draw the combinational circuit that directly implements the Boolean expression:

Question 74

Complete the truth table for the following sequential circuit:

Question 75

Repeat question 65 to determine the following:
a) The output string generated for the input: 00101101.
b) In which state is the encoder after the sequence in part a is written?
c) Which bit is in error in the string, 00 01 10 11 00 11 00? What is the probable value of the string?
Reference of Exercise 65:
Using the convolutional code and Viterbi algorithm described in this chapter, assuming that the encoder and decoder always start in State 0, determine the following:
a) The output string generated for the input: 10010110.
b) In which state is the encoder after the sequence in part a is read?
c) Which bit is in error in the string, 11 01 10 11 11 11 10? What is the probable value of the string?

Question 76

Why is it important for Boolean expressions to be minimized in the design of digital circuits?

Question 77

What are the necessary steps one must take when designing a logic circuit from a description of the problem?

Question 78

How is a JK flip-flop related to an SR flip-flop?

Question 79

Draw the combinational circuit that directly implements the following Boolean expression:

Question 80

Complete the truth table for the following sequential circuit: