CS 131 – Problem Set 2 – Part 2

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CS 131 – Problem Set 2 – Part 2

All problems in this problem set (except problems 2 and 4d) ask you to write Boolean formulas in Python syntax. You are allowed to use Python operators and, or, not, ^ (for XOR), and == (for equality, also know as XNOR).

Problem 1. (5 points) For the following Boolean function,

a) write a DNF then, convert it to a Python formula. Submit a file named p1a.py.

b) Also write a CNF, then convert it to a Python formula. Submit a file named p1b.py.

Problem 2. (10 points) You recently started working in VLSI company, and your first task is to construct a circuit that produces from input bits p, q, r the desired output ¯q(¯p+ ¯r) + ¯p(q + r). You can use OR gates, AND gates, and NOT gates, but you would like to use as few gates as possible.

a) Simplify the above Boolean function to be able to construct a Boolean function with 3 logical operators. That is, you should write a logically equivalent formula to the one above which uses only 3 instances of OR, AND, or NOT.

b) Draw the circuit for the simplified Boolean function which includes only 3 logic gates.

Problem 3. (10 points)

a) Write a DNF Boolean formula using variables x, y, and z that evaluates to 1 when number xyz is either a multiple of 5 or not a prime number but not both. Then, convert it to a Python formula. Submit a file named p3a.py.

b) Write a CNF Boolean formula using variables x, y, and z that evaluates to 1 when number xyz is either a multiple of 5 or not a prime number but not both. Then, convert it to a Python formula. Submit a file named p3b.py.

Note 1: You may need to provide a truth table.

Note 2: Number xyz is a binary number consists of three bits. 110 which equals 6 is an ex-ample for number xyz.

Problem 4. (10 points) This problem will be easy if you try to use your answers to problems 1, 2 and 4 in Problem set 2 – Part 1, and very hard otherwise. You are allowed to copy from the answers of those problems which are posted on Blackboard.

a) You have two three-bit numbers, a (consisting of three bits a2 a1 a0) and b (consisting of three bits b2 b1 b0). You also have a four-bit number s (consisting of four bits s3 s2 s1 s0). Write a Boolean formula that says “s is equal to a + b.” Submit a file named p4a.py.

Hint 1: The formula will be long, because it will be a conjunction of four separate formulas, one each for s0, s1, s2, and s3. Parentheses matter! Remember that you can break a long line in python by putting a “\”.

Hint 2: Careful with ==, because it has higher precedence than and and or. Thus, a == b or c is interpreted as (a == b) or c. If you want the other interpretation, write a == (b or c).

b) You have two four-bit numbers, s (consisting of four bits s3 s2 s1 s0) and t (consisting of four bits t3 t2 t1 t0). Write a Boolean formula that says “s is greater than t.” Submit a file named p4b.py.

c) You have four three-bit numbers, a, b, c, and d, and two four-bit numbers, s and t (please infer the variable names for individual bits by analogy to previous problems). Write a Boolean formula that says “a is less than c and b is less than d and t is equal to c + d.” Submit a file named p4c.py.

d) Consider the conjunction of the Boolean formulas in the previous three parts. Is it satisfiable? Explain why or why not.

Problem 5. (15 Points) Scheduling with constraints: We have 3 time slots and 6 classes A, B, C, D, E, F. 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. In each part, make sure that the names of your functions match the names of the functions that we are asking you to write. Note that for each part you can call functions from previous parts. There are two sets of test cases. The autograder on Gradescope will only reveal the results of one set of cases. You will not know the results of the other set of test cases. This is done to encourage you to test your own code.

Note: Place all the functions in a single python file and make sure to name your python file p5.py for the auto-grader to recognize and compile the file. Also, do not include any print statements or header documentation in the file. Use function names as required by each section.

a) 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)

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

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

d) Define a function c(x1,x2,x3,y1,y2,y3) that outputs True if two classes X and Y are scheduled in different time slots.

e) Define a function isValid(a1, a2, a3, b1, b2, b3, c1, c2, c3, d1, d2, d3, e1, e2, e3, f1, f2, f3) that outputs True if the schedule is valid for classes A,B,C,D,E, and F.