Simplify the product of sums to give the expression with

Question

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

1) Convert these decimal numbers to binary using either of the methods we discussed in class. Show your work.

a. 53

b. 27

c. 119

2) Compute the decimal values of these binary numbers (you don't need to show your work).

a. 10010

b. 11111111

c. 1010

3) Write down Boolean expressions for these two logic diagrams:

4) Draw logic diagrams to implement the following Boolean expressions:

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

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

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

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

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

6) 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 product of sums to give the expression with the fewest literals. Show your work.

d. Draw a gate diagram for the circuit implementing F, based on your simplified expression.

7) Simplify the following Boolean functions using three-variable K-maps:

a. F(x, y, z) = Σ(0, 1, 6, 7)

b. F(x, y, z) = Σ(0, 1, 3, 4, 5)

c. F(x, y, z) = Σ(1, 3, 5, 7)

d. F(x, y, z) = Σ(1, 4, 5, 6, 7)

8) A bit vector of length N is defined as a sequence of N Boolean values. Denote by BN 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 operations | and & are defined on bit vectors 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 operations |, &, and _~, constitutes a valid Boolean Algebra. Let's investigate some aspects of this.

a. Fill in the tables below showing the results of the 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 identity element look like for an arbitrary N? (Below, we denote these in boldface as 0 and 1 to distinguish them from the single bit variants.)

c. Sketch a proof that the axioms of Boolean Algebra also hold in B^N for N ≥ 1. You don't need to prove it formally, just write a few sentences. To remind you, the axioms are:

i. Closure: X|Y ∈ B^N, and X & Y ∈ B^N

ii. Identity: X|0 = X, and X & 1 = X

iii. Commutative property: X|Y = Y|X, and X & Y = Y & X

iv. Distributive property: X & (Y|Z) = (X & Y)|(X & Z), and X|(Y&Z) = (X|Y) & (X | Z)

v. Complement: X|_~X = 1, and X & _~X = 0

vi. Cardinality: B^N has at least two elements.

d. Prove the following or provide a counterexample: For all X, Y in B^N,

X|(_~X & Y) = X|Y

e. Prove the following or provide a counterexample: For all X, Y in B^N,

_~(X|Y) = X & Y

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

10000001 | _~ (00110001 & 10011001)