CS 216 Assignment #3

Due as specifed on course webpage

1. Prove by truth table one of the deMorgan laws,       (something important to keep in mind when you need 2 or more conditions)
	_____   _ _
	A + B = A B		which means	NOT (A OR B) = (NOT A) AND (NOT B)
	___   _   _
	A B = A + B		which means	NOT (A AND B) = (NOT A) OR (NOT B)
2. The truth table for "logical implication" (and exclusive or) are given in the truth table below.
Implies  to be used in Question 3.
How about NOR, the negation of OR? [A NOR B = NOT (A OR B) ] what are its truth values?
Also NAND. [A NAND B = NOT (A AND B) ]   Finally, fill in the last 3 columns. Have you seen that pattern before?
A
 B
 A implies B
 A xor B
 A nor B
 A nand B
 not A
   B 
(not A) + B
0
 0
 1
 0




0
 1
 1
 1




1
 0
 0
 1




1
 1
 1
 0





[In other words, if A is true, implication requires B to be true. If A is false, B can be anything. "That's logic!"]

3. Please give an evaluation of (bitwise) $t2 implies $t1, by using any of the mips logical operations: AND, OR, XOR, NOR.
For NOT A, you can use A NOR A, or A NOR 0.
Show how your implementation works for :
A  $t2 = 0011
B  $t1 = 1010










4. An interesting property of NOR (also of NAND) is that they are "complete" in the sense that any possible logical operation can be done using only NOR, or likewise, only NAND.
So, give a Boolean expression for AND using only NOR  (or, if you prefer, of OR using only NAND).











5. The following assembly language instructions are "pseudo" instructions, that is, they are in fact not implemented by MIPS hardware. Instead, the assembler must convert them to 1, 2 or more actual machine instructions. It may use $1 ($at) in the process (that is why we don't use that register.) For each instruction, give a possible implementation, using only instructions that are not marked with a dagger, and therefore represent MIPS machine language instructions. (And therefore you may use $at, as the assembler would.)
Hint: You could look at these in QtSpim, but please use the symbolic register names, $t1 rather than $9, for instance.
6. In assembly language, NOT is bitwise. Since slt or slti gives a result of either 0 or 1 (the other 31 bits are 0), what instruction, if any, can you use to produce a correct logical result (0 or 1) for not $t0, where $t0 has just been the result of slt? (store back in $t0)