代写CS 131 – Problem Set 1调试Python程序

日期：2024-05-24 05:31

CS 131 – Problem Set 1

Where  to  submit:  All assignments should be submitted through https://gradescope.com. You’ll find yourself already enrolled in CS 131 on gradescope.  It will take time for you to learn Gradescope and set up your environment. Do a test submission to make sure you know how to do it. You can replace your submission any time before the deadline at no penalty.

What to submit: You will be submitting several files on gradescope:  a  .pdf file with your hand- written answers for written exercises into gradescope assignments called Written  Portion and several .py files into gradescope assignments called Code  Portion.  Note that your final submission for the code portion 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).  We recommend that you have a folder on your computer to keep all your files together; one folder for each homework assignment this semester.

Written Portion: The written portion of each problem set must be hand-written. See scanning in-  structions https://help.gradescope.com/article/0chl25eed3-student-scan-mobile-device. 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.  Required action:  At the top of each problem you submit, write either the text  “Sources consulted:  none” or a list of all sources consulted other than lecture notes and course staff. Examples of things that should be listed if consulted:  name of a classmate, name of a tutor, name of a friend, name of a website, name of a textbook etc.  One point will be deducted from every problem for which this list is omitted.

Code Portion: The .py files can be created by Spyder (https://www.anaconda.com/products/ distribution), IDLE (https://www.python.org/downloads/) or any other Python editors.

Problem 1.   (5 points) Demonstrate that the following two propositional formulas are equivalent by making a truth table for each and comparing the rightmost columns.

(a ∨ ¬b ∨ c) ∧ (a ∨ b ∨ ¬c) ∧ (¬a ∨ b ∨ ¬c)                                          (1)

and

(¬a ∧ ¬b ∧ ¬c) ∨ (¬a ∧ b ∧ c) ∨ (a ∧ ¬b ∧ ¬c) ∨ (a ∧ b ∧ ¬c) ∨ (a ∧ b ∧ c)                    (2)

Note that order of rows is important:  be sure your ordering of F and T values for a, b, and c is the same in both tables. We start the first table for you, and give you columns for both.

a     b      c     (a ∨ ¬b ∨ c)     (a ∨ b ∨ ¬c)     (¬a ∨ b ∨ ¬c)   Result 1   

F    F    F            T                  T                     T                  T

F    F    T                                   fill in the rest

F    T    F  

F    T    T 

T    F    F  

T    F    T 

T    T    F  

T    T    T 

a    b     c    (¬a ∧ ¬b ∧ ¬c)     (¬a ∧ b ∧ c)     (a ∧ ¬b ∧ ¬c)     (a ∧ b ∧ ¬c)     (a ∧ b ∧ c)   Result 2   

fill in the rest

Problem 2.   (5 points) Let

.  s denote “Leo will study”;

. t denote “Vahid will study”;

. p denote “Leo will pass the class”;

.  q denote “Vahid will pass the class” .

Write a propositional formula for “Both Leo and Vahid will study but only one of them will pass the class.” Implement your proposition in Python syntax using only operators and, or, not and parentheses. Submit a file named p2.py

Problem 3.   (5 points) Alice, Bob, Chloe, and David are friends trying to decide whether to go on a hike or go to a movie next weekend. Alice is recovering from an ankle injury. They will hike if Alice’s ankle is well by the weekend, and the majority of Bob, Chloe, and David want to hike; otherwise, they will go to a movie.  Let the predicate  a be True if Alice’s ankle is well and False otherwise. Let predicates b, c, and d be True if Bob, Chloe, and David, respectively, prefer to hike, and False otherwise. Write a propositional formula that is True if they will hike, and False if they will go to a movie.  Implement your proposition in Python syntax using only operators  and, or, not and parentheses. Submit a file named p3.py

Problem 4.   (10 points) 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

equal to	=	==
not equal to		!=
greater than	>	>
less that	<	<
at least (or “greater than or equal to”)	≥	>=
at most (or “less than or equal to”)	≤	<=
Write propositional formulas for the following propositions.

a) x is positive or at most −100. Implement your proposition in Python syntax using only operators and, or, not, parentheses and the operators mentioned in the above table.  Submit a file named p4a.py

b)  x is not 0 or 1.  Implement your proposition in Python syntax using only operators and, or, not, parentheses and the operators mentioned in the above table. Submit a file named p4b.py

Problem 5.    (5 points) You make the following flowchart for when you drop your food on the floor which shows when you should/should not eat that food.

 

Let the proposition a be True if somebody see you and False otherwise.  Let the proposition b be True if it was your boss/lover/parent and False otherwise.  Let the proposition c be True if the food was cheap and False otherwise.  Let proposition d be True if you can cut off the dirty part, and False otherwise.  Write a propositional formula that is True if you should eat the food,  and False otherwise.  Implement your proposition in Python syntax using only operators and, or, not and parentheses. Submit a file named p5.py

Problem 6.   (10 points) Prove the following problems using the laws of propositional logic (not truth tables). And then, implement your proof in Python using the following notations.

 

You must submit your handwritten proof in the written portion and two files named p6a.py, p6b.py, in the code portion.

a) （ (P → Q) ∨ (P → R)）→（P → (Q ∨ R)）is a tautology.

Hint:  To prove using the laws of propositional logic, you must start with the entire proposi- tion and find all equivalencies of that proposition (by applying the laws of propositional logic) to reach to a proposition which is always True.

b)  ¬（(P → Q) ∨ (Q → R)）is a contradiction.

Hint:  To prove using the laws of propositional logic, you must start with the entire proposi- tion and find all equivalencies of that proposition (by applying the laws of propositional logic) to reach to a proposition which is always False.

Problem 7.   (15 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.”

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

b)  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 ∧ G ∧ M) must be true).   Prove that,  unfortunately, at least one of your children is a liar.  That is, prove that all their statements from the previous part, taken together with the statements from this part, are a contradiction  (i.e., are logically equivalent to F).  You can start with whatever you proved in the previous step.  Hint:  It  may help to remember that laws of propositional logic apply not just to individual variables, but also to compound propositions.

Problem 8.    (30 points) Three children — Anna, Bj¨orn, and Cathy — are playing in the mud. They are honest, logical, can see each other’s faces, but cannot see their own. Let A, B, and C be propositional variables that represent whether the face of Anna, Bj¨orn, and Cathy, respectively, is muddy.

The children  are told,  by  their parents,  that  they must  come home if their faces  are muddy. They are quite obedient; however, if they have any plausible doubt about whether their faces are muddy, they will stay and play, because they are children, after all.  Thus, every child, as soon as he or she can conclude definitively that his/her face is muddy, will go home to wash it.  But if a definitive conclusion cannot be made, the child will stay and play.  And, of course, pointing out that someone’s face is muddy is against their honor system.

There is a traffic light, and children must wait for the walk sign before they go home.

An honest adult named David, who does not know the honor system, comes up to the children, says “At least one of you has a muddy face,” and leaves.  You are too far to see the children’s faces, but you know the rules, hear what David is saying, and you can see the children and the traffic light.

a)  Write down the proposition (with variables A, B, and C) that represents David’s statement.

b)  You observe that Anna does not walk home the first time the walk sign turns on after David’s statement. What propositional formula using variables B and C must be true? Explain why.

c)  You observe that Bj¨orn and Cathy also do not walk home the first time the walk sign turns on. Think about what can you conclude about A and C, and about A and B, similarly to the previous part (2c from lab). Since now you have three conclusions that must all be true (two from this part and one from the previous), combine all three of them into a single propositional formula that you know must be true.

d)   Note that the  children can make the same conclusions as you do, because they observe the same as you do (even more, in fact).  Thus, after the first light cycle, they all know that the formula from the previous part must be true.  The second time the walk sign turns on, you observe that Anna again does not  walk home.  What propositional formula using variables  B and C must be true now?  Remember that Anna walks home if she is sure her face is muddy, and does not walk home if she sees that there’s some way for the formula from the previous part to be true even if her face is not muddy. Explain your answer.

e)  Suppose the second time the walk sign turns on, you observe that in fact no child walks home. What propositional formula using variables A, B, and C must be true now? Justify your answer

f)   Given the observations of the previous part, which child(ren) will walk home the third time walk sign turns on and why? Explain your answer.

Problem 9.   (5 points) Explain whether each of the following arguments is valid or not.  For the valid arguments, which rule of inference is used?  For the invalid arguments, explain why they are invalid.

a)  Henri will either go for a run or go for a swim. Henri won’t go for a run. Therefore, he will go for a swim.

b)   Carl is a mathematician.  If Carl is a mathematician, then he is mortal.  Therefore,  Carl is mortal.

c)  Alan will decipher the code.  Therefore, Alan will decipher the code or he will have a cup of tea.

Problem 10.   (10 points) Use the rules of inference and 2-column proof format (valid argument approach) to prove validity of the following arguments.  Note that you must not use any of the laws of propositional logic.  It means that you should only use rules of inference.  Also, the following two rules of inference called Contrapositive and Conditional Simplification respectively can be used.

A → B

∴ ¬B → ¬A

A → B ∧ C

∴ A → B

Note that the above rules can be proved by the laws of propositional logic.

q → (p ∧ r)

s → r

r → q       

∴ s → p

¬r → ¬s

¬p → u

¬t → ¬r

u → s

t → q      

∴ ¬p → q