Note:  Solo only -- you may not work in teams on this assignment.

Also note:  You must submit your homework by email, and it must be received by 8:15am on the due date.
 

Date Assigned:	Wed Sep-6
Date Due:	Thu Sep-7 by 8:15am

0.a.  Begin reading Brookshear 1.1 (finish reading it tomorrow).

0.b.  Review the online slides as necessary -- they contain most of the information presented in class (which does not, for the most part, appear in Brookshear).

1.  Give the truth table for the following functions:

a.   x nand ~y

Hint:  You may want to include columns for ~y and for (x and ~y).  These are helper columns, as they are not actually required to solve the problem (and so are optional).  But they may help you compute other columns (both more quickly and more correctly).  So perhaps you might want to set your truth table up as follows:

        x     y        ~y     x and ~y        x nand ~y
        0        0
        0        1
        1        0
        1        1

b.   q xor ~r

c.   x nand (y nor ~x)

Hint:  Here, you might want to include (y nor ~x)  and even  x and (y nor ~x)  in your helper columns.

2.a.b.c:  Express each function in problem 1 in Disjunctive Normal Form (DNF).

Hint:  add one last column to each truth table, the "Conjuncts" column, which represents just that row.  Remember only to include rows which have a true value (that is, a 1 in the final column).  Then, the conjunct for that row is just the values of x and y for that row AND'ed together.  So if x is 0 and y is 1, the conjunct is x and ~y.  Then, once you have all the conjuncts, to compute the DNF you just OR all the conjuncts together.  That is, you say:  "This function is true if this row is true, or if this row is true, or...".

3.  Some functions are called degenerate because they do not compute anything interesting (in a mathematical sense), and usually just ignore their inputs altogether.  The function z xor z is such a function.  Write the truth table for this function (note that it is a unary function -- it just takes one variable, in this case z), and then note very briefly why this is a degenerate function.

Hint:  Since this is a unary function, your truth table will not include two variables, and will look as such:

z        z xor z
0
1

4.  Extra Credit (not required):  Prove that Nor(x,y) is a logical basis.

Hint:  Using the fact that And,Not is a logical basis, just prove that each of those functions can be expressed using only Nor.  Also, be sure to note that Not is unary (takes only one argument). So:  Every logical function can be expressed using only Nor.  How about that!

See Course Home Page.