Problem 1.   (12 points, 2 per subproblem)

Evaluate the following logical expressions with x = y = 1 and with w = z = 0.  (This problem was taken from zyBooks, problem 2.1.1).

a)  xyzw

b)  xy + z(w + z)

c)  zyx(1 + w)

d)  xyz + zw

e)  (z + y)(w + x)

f)  xy + (x + w + yz)

Problem 2.   (8 points, 2 per subproblem)

Use the laws of Boolean algebra to prove that the two Boolean expression in each pair are equivalent.  For part D, there are two ways you can prove that these expressions are equal.  One is to try and reduce one into the other.  The other is to try and reduce both expressions into the same form. (This problem was taken from zyBooks, problem 2.1.3a-d.)

a)  xy + xy = x

b)  x + xy = x

c)  x(y + x) = x

d)  xy + zx = (x + y)(z + x)

Problem 3.   (16 points)

For each of the formulas below, state whether it is in CNF, DNF, both, or neither. If it’s not in CNF, make a truth table for the formula, and write down a CNF expression for it.  If it’s not in DNF, make a truth table and write down a DNF expression for it.  (This problem can also be found on zyBooks, problem 2.3.2)

a)  xyz + xz

b)  yxzw

c)  y(x + z)(y + z)(x + y + z)

d)  x + y + z

Problem 4.   (8 points, 4 per subproblem)

a)  Write a DNF formula in Python using variables x, y, and z that evaluates to 1 if and only if the three variables all have the same value. Submit a file named p4a .py.

b)  Write a CNF formula in Python using variables x, y, and z that evaluates to 1 if and only if the three variables all have the same value. Submit a file named p4b .py.

Problem 5.   (12 points)

Let a4 a3 a2 a1 a0  be an 5-bit binary number. Write a boolean formula in propositional logic (not boolean algebra) that evaluates to true if either an odd number of bits of this number is 1 or it is a non-zero even number but not both, and false otherwise.

Requirement:  Your final answer should only use  OR, AND, inverters (¬) or XOR  (⊕).  Any other answers should be reduced to the requested format.  You may not need to use all of the allowed operators in your answer.

Problem 6.   (22 points)

Continuing from problem 3 from lab 2: Batman still needs your help! You have figured out the Boolean expression of the Riddler’s last message - now you need to figure out where you need to go to stop him from causing any damage!

a)  (8 points) Simplify the Boolean expression that contains both of the Riddler’s messages in order to get more concise information about the Riddler’s intentions.

Hint1: You are asked to use Boolean expression to avoid difficulties of propositional logic such as writing the rules. You can treat Boolean expressions as Algebraic equations.  So, in your compu- tations use = instead of ≡ . Also, do not forget that 0 + p = p, 0 · p = 0, 1 · p = p and 1 + p = 1. Here, p is a Boolean variable, 1 means TRUE and 0 means FALSE.

Hint2:  Your final answer should be equivalent to  “The Riddler will set fire to bank and rob the orphanage and will NOT BOTH set fire to the orphanage and robs the bank”.  Your job is figuring out how.

b)   (4 points) Using your result from part a and the fact that the Riddler’s final message is true, which location must be set on fire?  Which location must be robbed?  Explain your reasoning in English.

c)   (4 points) Now that you’ve worked out the truth, which of the two original messages told the truth and which one is a lie?

d)  (6 points) Having cracked the riddle, Batman heads out in his Batmobile to stop the robbery. As you’re about to celebrate you get a call from Batman while he’s en route to the robbery: