CS 370 - Spring 2005
Introduction to Digital Design
Instructor: Carl Ebeling

Homework Set 1
DUE: April 8, 2005, Start of class

Collaboration Policy:

Unless otherwise noted, you may collaborate with other CSE370 students on the homework assignments. Do not look at homework or exam solutions from previous years. You must spend at least 15 minutes working on a problem before seeking assistance. Collaboration means that you may discuss the problems and make notes during the discussion, but you may not look at other student’s work when writing up your homework. Your homework represents your own work—the homework must show that you understand the material and have worked as an individual on every problem. You may not divide up the task of doing the problem sets in the interpretation of collaboration. You may discuss lecture material with anyone.

Late Homework Policy:

The weekly assignments are due at the beginning of class. Assignments handed in during or immediately after class will incur a 10% penalty. We will penalize your assignment 10% per day for each additional day late.

Please show all of your work. Your solutions must be legible…we will not spend time trying to decipher poorly written assignments.

1. (12 pts) Convert the following decimal numbers to binary, octal and hexadecimal:
(a) 27
(b) 735
(c) 1.125
(d) 123.2

2. (12 pts) Find the 1's complement and the 2's complement of each of the following binary numbers (use 8-bit numbers):
(a) 01001010
(b) 01001011
(c) 11010001
(d) 0
(e) 11111111
(f)  10000000

3. (4 pts) Convert the following numbers to decimal (assume that all numbers are unsigned):
(a) 100101110112
(b) 75318
(c) 7B1C16
(d) 10101.10112

4. (12 pts) A.14

5. (6 pts)  Prove the three simplification theorems (p.43 Th. 9-11) using perfect induction.

6. (8 pts) Text 2.2: a, c

7. (6 pts) Text 2.9

8. (6 pts) Text 2.11

9. (8 pts) Text 2.17: c, d

10. (8 pts)  Show that an n-input OR gate can be replaced by n-1 2-input OR gates.  Can the same be done for NAND gates?  Justify your answer.

11. (8 pts) The following truth table represents a logic function. A, B, and C are inputs, and Out is the output.
Write the truth table as a Boolean expression. Draw the circuit that implements this function using ANDs, ORs and inverters.

 A B C Out 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 1

12. (10 pts) A self-dual logic function is a function F such that F = FD .  Which of the following functions are self-dual?  Support your answer.
(a) F = x
(b) F = x y' + x' y
(c) F = Majority function.  (With an odd number of inputs, more than half are 1.)