E15 fundamentals of digital systems - fall 2015 - homework

Question

E15: Fundamentals of Digital Systems - Fall 2015 - HOMEWORK 1

1. Write down boolean expressions for these two logic diagrams.

2. Draw logic diagrams to implement the following Boolean expressions.

a. Y = (A + B')(C' + D)

b. Y = A + B + B'(A + C')

3. Using only the axioms of Boolean Algebra from the handout, prove these two statements. Justify each step using the axioms.

a. x + (x' • y) = x + y

b. x • (x' + y) = x • y

4. A bit vector of length N is defined as a sequence of N boolean values. Denote by B^N the set of all possible bit vectors of length N. For example

B² = {00, 01, 10, 11}

We will define three operations on bit vectors by applying the familiar binary logic operations to their individual elements. In the C programming language, these are known as bitwise operators.

The two binary operators | and & are defined by applying the OR and AND operations on each bit, respectively. For example,

10 | 01 = 01 | 10 = 11

10&01 = 01&10 = 00

The unary operator _~ is defined by taking the bitwise complement of each element of the bit vector. For instance,

_~ (11) = 00

For any N ≥ 1, the set B^N, together with the three bitwise operators defined above, constitutes a valid Boolean Algebra.

a. Complete the tables below to show the results of the three operations in B². The examples from above have been filled in to get you started.

b. What is the identity element of B² with respect to the | operation? With respect to the & operation? In general, what would each element look like for an arbitrary value of N?

c. Compute the value of the following expression in B⁸:

10000001 | _~ (00110001 & 10011001)

5. For the function F given by this truth table:

x	y	z	F
0	0	0	1
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	1
1	0	1	1
1	1	0	0
1	1	1	0

a. Express F as a product of standard sums.

b. Express F as a sum of standard products.

c. Simplify the sum of products to give the expression with the fewest literals. Show your work.

d. Draw a logic diagram for the circuit implementing F based on your simplified expressions.