 (2 pts)
For the following Boolean formulas, write a truth table that shows
the value of the function for each possible combination of
assignments to the boolean variables X, Y and Z. Use 1 for true
and 0 for false. (NOTE: The NOT (¬) operator has a higher
precedence than the AND (∧) and OR (∨) operators.)

(X ∧ Y) ∨ (¬Y ∧ Z)

¬(X ∧ Y) ∧ Z

X ∨ (Y ∧ Z)

(X ∧ Z) ∨ (¬X ∧ ¬Y ∧ Z) ∨ (X ∧ Y ∧ ¬Z)
 (1 pt)

The boolean
expressions in problem 1 can be realized as an electric circuit. Such
circuits can be represented abstractly using logic gates (instead of
transistors). Draw how the first formula in problem 1 would be
realized as a computational circuit at the gate level of abstraction.
 Are any of the Boolean expression in problem 1
computationally equivalent? If so, which ones are equivalent? If not,
how do you know?
 (1 pt)
Let ABCD represent a 4bit binarycoded decimal number
as described in Homework 6. For example, the decimal digit
7 is represented in binarycoded decimal as 0111, so in
this case, A = 0, B = 1, C = 1, and D = 1.
A sevendegment display can be used to display each of the
ten decimal digits as shown below.
We can define a circuit abstractly below that requires
four Boolean inputs A, B, C, and D, and seven Boolean outputs
s_{1}, s_{2}, ..., s_{7}
to control each segment of the display:

Derive a Boolean formula for s_{4} that is
true (1) if and only if the middle segment is lit.
Your answer should be of the following form:
s_{4} = (________) ∨ (________) ∨ (________) ∨ ...
where each missing section is a boolean expression with all 4 input
variables that is true when ABCD represents a decimal digit that
results in the middle segment of the display being lit. To help you
get started,
the digit 2 (binary 0010) will light the middle segment, so the
first expression in the formula above would be
(¬A ∧ ¬B ∧ C ∧ ¬D)
since this formula would be true (1) if A = 0, B = 0, C = 1, and D = 0.
You will need to find all of the other missing expressions.
 (HARDER)
Simply the Boolean expression from part (a) using Boolean logic
laws into a formula with 4 terms that are combined using the
OR (∨) operator, each term containing only 3 Boolean variables each.
(HINT: You'll probably need to use the distributive law discussed in
class.)
 (1 pt)
In Ruby, there is another loop called an until loop
that runs until a particular condition is true. For example,
Consider the following code using a while loop:
i = 0
sum = 0
while i != 10 do
sum = sum + i
i = i + 1
end
We can also write this code equivalently using an until loop:
i = 0
sum = 0
until i == 10 do
sum = sum + i
i = i + 1
end
Use DeMorgan's Law to convert the following while loops
to equivalent until loops.

while (x > 15) && (y <= 110) do
...
end

while (a != 20)  (b == 11 && c < 42) do
...
end
 (1 pt)
A simpler adder is called a half adder which only adds 2 bits
(X and Y)
to produce a sum bit (S) and a carry_out (C) bit, as shown in the
following truth table:
X Y  C S

0 0  0 0
0 1  0 1
1 0  0 1
1 1  1 0
This adder can be represented abstractly using the following
diagram:

Give Boolean formulas for C and S as functions of X and Y.

(HARDER) Using two halfadders and one OR gate, show how to build
a fulladder as defined in class. Your picture should
have three inputs, X, Y, and Carry_In and two outputs,
S and Carry_Out.
 (1 pt) When a programmer writes a program in a highlevel language
(e.g. Ruby), the program must be translated to binary
machine language for the CPU
to execute it. There are two kinds of
programs that can be used to do this
translation: an interpreter or a compiler. Which do you think is faster
to run by a CPU: a program that is translated one instruction at a time
by an interpreter or a program that is translated in its entirety first
by a compiler? Why?
 (2 pts)
Write a MARS program that computes 2 raised to a positive integer
power. For this specific program, you will write it so it computes
2^{5}. You will need two words to hold data in "memory":
a data word for the exponent (5) and a data word to hold the result (start
this value with 1). To compute 2^{5}, just add the result
to itself 5 times. Your program should work for any positive
integer exponent, so don't just write 5 ADD instructions.
You will need to create a "loop" using MARS instructions.
Write this program by hand (or type it) in your homework
using the standard MARS assembler syntax as shown in class.
Then test your program in irb
using the MARSLab from RubyLabs. First, make a test machine with your
program using the make_test_machine function. Then use
the dump function to show how your program is represented in
"memory". Then repeat the following until the program halts:
execute the step function followed by the dump
instruction. Once you are done, copy all of the results from irb
into a text file and include this with your homework to show that you
have tested your solution.
 (1 pt)
Consider the following MARS program imp.txt:
start MOV 0, 1
end start
This is loaded into MARS as follows:
m = make_test_machine("imp.txt", 100)
What does this program do? Explain clearly.
(HINT: Look at your textbook!)