Problem 1.   (20 Points, 5 each)

Are the following functions satisfiable? If the function is satisfiable, with a single line containing 4 comma-separated values, each of which is either 0 or 1, for x, y , z , v in this order. For example, you would submit:  1, 0, 1, 0.  If the function is not satisfiable, use the laws of boolean algebra to prove that the function is a contradiction.

a)  [5 Points] xy¯zy + y¯zx + yzv + xv

b)  [5 Points] (z + x)(y + v)(z + )

c)  [5 Points] xv(y + )( + )

d)  [5 Points] ( + y¯)( + v)(y + x)(xy)

Problem 2.   (30 Points, 15 each) For this problem, follow the format of proof on lab 3 problem 2.

a)  [15 points] Prove that A ∩ B = A ∪ B .

b)  [15 points] Prove that A − (B ∩ A) = A − B .

Problem 3.   (20 Points, 10 each)

For each of the following problems, prove that identity given is false by giving a counterexample.

a)  [10 points] (A ⊕ B ⊕ C) ∪ (A ∩ B ∩ C) = A ∪ B ∪ C

b)  [10 points] A ∩ ( ∪ B) = A ∪ (A ∩ )

Problem 4.   (30 Points, 6 each)

We have 3 time slots and 6 classes A,B,C,D,E,F . Each class must be scheduled exactly once, and the following class pairs cannot be scheduled together:

(A,B), (A,C), (A,E), (B,D), (C,E), (C,D), (D,F), (E,F).

For each class, there are three variables.  For example, for class A, there are a1,a2 and a3.  If a1=True this means that class A is scheduled in period 1. Write all your functions in the following parts in python. Note that for each part you can call functions from previous parts.

Place all the functions in a single python file named p4 .py. Use function names as specified in each part.

a)  [6 Points] Define a function s(x1,x2,x3) that outputs True if the class X is scheduled at least once. The first line in your code should be“def  s(x1,  x2,  x3):”. The second line should begin with an indentation. See example code posted from Sep 23rd lecture.

b)  [6 Points] Define a function n(x1,x2,x3) that outputs True if the class X is scheduled no more than once.

c)  [6 Points] Define a function ns(x1,x2,x3) that outputs True if the class X is scheduled exactly once.