Where to  submit:  Create an account on https://gradescope.com using your bu .edu email address. You’ll find yourself already enrolled in CS 131 on gradescope. If not, use code DJ35ER to add yourself to the class.

What to submit: You will be submitting several files on gradescope: a .pdf file with your write up for written exercises 1-2 into gradescope assignment PS1  Written  Portion and several .py files into gradescope assignment PS1  Code  Portion.  We recommend that you have a folder on your system to keep all those files together; one folder for each homework assignment this semester; note that your final submission has to include all the  .py files (you can’t just add one file at a time, though you can test one file at a time at intermediate submissions).

You can create the .pdf file from typed or scanned-in handwritten work (see scanning instruc-  tions here https://help.gradescope.com/article/0chl25eed3-student-scan-mobile-device). The .py files should be created by Spyder (see the General Resources section on Piazza) or another  editor you use for Python. Filenames for .py files must match exactly, or else the autograder will  fail.

It will take time for you to learn Gradescope and set up your environment.  Do a test submis- sion to make sure you know how to do it.  You can replace your submission any time before the deadline at no penalty.

Make sure we can grade your work fairly: It is up to you if you want to submit handwritten or typed submissions. But it is your responsibility to:

1. write neatly so the graders don’t have to decipher handwriting

2. make your answer logically clear and easy to understand

3. map questions to pages correctly in Gradescope

4. list all of your collaborators, per rules on the syllabus. If you worked by yourself, please write “Collaborator: None” on the top of your assignment.

How to type up your work: We encourage (but do not you require) you to type up your work. Typing up your work instead of handwriting it makes it easier to edit and improve iteratively, resulting in higher quality solutions. You may use Microsoft Word, Google Docs, Apple Pages, or another word processor, but they are not great for editing mathematical content.  We encourage you to learn LATEX, which is a very powerful tool for writing text with math in it.  We provide information on getting started with LATEX on Piazza  (this link:  https://piazza.com/class_ profile/get_resource/l6yb1qx1t9e4o8/l7un3ftcygb4az).

How to work on this problem set: The best way to tackle the problem sets is to do them over time rather than once a week. You wouldn’t starve for six days and then attempt to consume your weekly calorie needs on the seventh. Similarly, don’t deprive your brain of thinking about CS 131 for six days and then attempt to solve the problem set on the seventh.

Labs help you start the homework. Every homework problem relates to something we covered; if unsure how to start, look through what we covered in the last few lectures.

We encourage you to collaborate with others on homework assignments, subject to the collabora- tion policy on the syllabus. Recall that as long as it satisfies the following conditions, collaboration on the homework assignments is permitted and will not reduce your grade:

1. Before discussing each homework problem with anyone else, you must give it an honest half- hour of serious thought.

2. You must write up your solutions completely on your own, without looking at other people’s write-ups. That means, in particular, that you should not write out a solution on the board, take a picture of it, and transcribe it.

3. In your solution to each problem, you must write the names of those with whom you discussed it.

We also encourage you to come to office hours, where you can work with others with the help of the course staff.

Here’s a picture that may offer you a way of thinking whenever you get stuck and would like to ask for help either on piazza or in office hours.

Problem 1.    (2 points) This problem is meant to help you make sure you can successfully pass an autograder test by submitting a correct file. Submit a file named p1 .py.The file should contain the single propositional formula

not  (a  and  b)  or  (a  and  not  c)  or  not  (not  b  and  c)

Problem 2.   (10 points, at 2.5 each) Let

•  s denote “Leo will study”;

• t denote “Peter will study”;

• p denote “Leo will pass the class”;

• q denote “Peter will pass the class”.

Write propositional formulas for the following propositions:

a)  At least one of these two people will pass the class. Submit a file named p2a .py.

b)  Leo will study or he will not pass the class. Submit a file named p2b .py.

c)  Either Leo or Peter, but not both, will pass the class. Submit a file named p2c .py.

d)  Both Leo and Peter will study but only one of them will pass the class.  Submit a file named p2d.py.

Problem 3.   (10 points) Consider the flowchart below (we got it from https://xkcd.com/1924/). As you can see, each box is assigned to a variable. The variable is “True”if and only if the answer to the question in the box is “yes”. You will be using these variables in your answers below.

Each result is represented by two bits.  Notice also how the first/leftmost bit of a result tells you whether the result is overall positive or negative, and the second/rightmost bit tells you how strongly it is positive or negative.

a)   (5 points) Find a propositional formula that is true if and only if the first bit is equal to 1. Submit a file named p3a .py.

b)  (5 points) Find a propositional formula that is true if and only if the second bit is equal to 1. Submit a file named p3b .py.

Problem 4.   (8 points) Four friends Anna, Benjamin, Christian, and Diana are making plans on what to do for the next weekend:  they have boiled it down to either getting food together at a new restaurant or going swimming. However, since Christian’s wrist injury has not entirely healed yet, the group decided to only go swimming if Christian feels better by the weekend and if the majority of Anna, Benjamin, and Diana want to go swimming.  Otherwise, they will go to the new restaurant.  Let the proposition c be True if Christian feels better by the weekend and False otherwise. Let propositions a, b, and d be True if Anna, Benjamin, and Diana, respectively, want to go swimming, and False otherwise. Write a propositional formula that is True if they will swim, and False if they will get food. Submit a file named p4 .py.

Problem 5.   (10 points, at 2 each) In this problem, individual propositions will no longer be single variables, but rather equalities and inequalities.  For example, a formula for“x is greater than 1 and at most 17 or is equal to 25”will look like

(x  >  1  and  x  <=  17)  or  x  ==  25

Note the following Python symbols for equalities and inequalities (pay particular attention to the fact that equality takes two equal signs):

English

Math   Python

Write propositional formulas for the following propositions:

a)  x is negative. Submit a file named p5a .py.

b)  x is positive or at most −100. Submit a file named p5b .py.

c)  Absolute value of x is at least 100 (do not use any kind of absolute value signs — first find a way to express this statement in terms of ≥ and ≤). Submit a file named p5c .py.

d)  x is 0 or 1. Submit a file named p5d .py.

e)  x is not 0 or 1. Submit a file named p5e .py.

Problem 6.    (16 points) In this problem, you will use the laws of propositional logic to prove equivalences and implications. Proofs via truth tables are not allowed. For each new proposition, explain what law (from Section 1.5 in the textbook) makes it equivalent to the previous proposition. You may combine some laws into a single line when it is very clear what you are doing (for exam- ple, you can apply associativity and commutativity together to rearrange order and add/remove parentheses).

a)   (8 points) The Junior Woodchucks are hosting a test in two weeks, for which they will award a brand new badge to all scouts who pass it.  In order to be fully prepared, Huey, Dewey, and Louie Duck decided to spend the entire weekend camping in a nearby forest, without any extra supplies aside from a tent and sleeping bags. Briefly after the three have left the house, Daisy says to Donald:  “f Huey will be determined enough to make it through the weekend, and Dewey, too, then Louie will be determined enough as well.”Donald responds:“If Louie will not be determined enough, but Dewey will be, then Huey won’t be determined enough, either.”Prove that their two statements are equivalent, Use variables H, D, and L, respectively.

b)   (8 points) Let W =  “I want food”, E =  “I eat”, and H =  “I am happy”.  Prove that the following three statements cannot be simultaneously true (i.e. conjunction of them is equivalent to false) using the laws of propositional logic.

1. If I want food, I eat

2. If I eat, I am happy

3. It is not true that if I want food, I am happy

Problem 7.   (15 points)

a)   (7 points) You have three children, named Ada, Grace, and Margaret (after three famous computer scientists, of course — try to find out which ones).  One day you find cookies missing  from the cookie jar.  You question them.  Ada says “If I did, then Grace did, too.”  Grace says “Either Margaret did it or I didn’t” (this is an inclusive or).  Margaret says  “If Ada didn’t do it, then I didn’t, either.”Represent whether each child is guilty by three variables,  A, G, M , respectively.  Prove that their statements are equivalent to saying “either we are all guilty, or we are all innocent.”

(1) Convert the conjunction of these children’s words into a propositional formula.

(2) Convert “either we are all guilty, or we are all innocent”into a propositional formula.

(3) Prove the propositional formulas in part 1 and 2 are equivalent via truth table by writing

out the truth table for each formula and observing that the last columns are the same.

b)   (8 points) You are sure that at least one of them is the thief (i.e., A ∨ G ∨ M must be true). Confused and unsure whom to punish, you tell them you will have to punish all three.  They tell you “It’s unfair, because not all of us are guilty” (i.e., ¬ (A V G V M) must be true). Prove, using rules of propositional logic that, unfortunately, at least one of your children is a liar. That is, prove that all their statements from the previous part

(G V M V A) ∨ (¬A V ¬G V ¬M) ,

when conjoined with the statements from this part

(A ∨ G ∨ M) V ¬ (A V G V M) ,

are a contradiction (i.e., are logically equivalent to F). Hint: It may help to remember that laws of propositional logic apply not just to individual variables, but also to compound propositions. Note: do this proof via laws of logic; a proof by a truth table will receive only partial credit.

Problem 8.    (10 points) At a conference, a famous computer scientist named Julia encounters three logicians, named Alan, John, and Kurt (try to figure out these four important historical references). She asks them “Is any of you thinking of getting dinner?” Use variables A, J, and K for whether Alan, John, and Kurt, respectively, are thinking about getting dinner.

a)   (2 points) Write down the propositional statement of Julia’s question.  The statement should be true if and only if the answer to Julia’s question is “yes”.

b)  (8 points) Alan answers Julia’s question with “maybe.”John hears Alan and also answers with “maybe.”Kurt hears them both and answers  “yes.”  Note that these answers are about Julia’s question, not about their own individual variables. Figure out the values of A, J, and K . Explain your reasoning in clear and concise prose.

Problem 9.   (19 points) Continuing with problem 3 from Lab 1, where we left off: you observed that Anna did not walk home the first time the walk light turned on. (Refer to the solution of Lab 1 problem 3 to see the state of the truth table, i.e. the rows that are impossible with the already given information.)