CS 70 Discrete Mathematics and Probability Theory Fall 2021
Due: Friday 9/3, 10:00 PM Grace period until Friday 9/3, 11:59 PM
Before you start writing your final homework submission, state briefly how you worked on it. Who else did you work with? List names and email addresses. (In case of homework party, you can just describe the group.)
1 Administrivia
Make sure you are on the course Piazza (for Q&A) and Gradescope (for submitting home- works, including this one). Find and familiarize yourself with the course website. What is its homepage’s URL?
Read the policies page on the course website.
(i) What is the breakdown of how your grade is calculated?
(ii) What is the grade breakdown for the “no-homework” option?
(iii) What is the attendance policy for discussions?
(iv) When are vitamins released and when are they due?
(v) How many “drops” do you get for vitamins? For homework? (Hint: it’s the same number) (vi) What percentage score is needed to earn full credit on a homework or vitamin?
Course Policies
Go to the course website and read the course policies carefully. Leave a followup on Piazza if you have any questions. Are the following situations violations of course policy? Write “Yes” or “No”, and a short explanation for each.
(a) Alice and Bob work on a problem in a study group. They write up a solution together and submit it, noting on their submissions that they wrote up their homework answers together.
(b) Carol goes to a homework party and listens to Dan describe his approach to a problem on the board, taking notes in the process. She writes up her homework submission from her notes, crediting Dan.
CS 70, Fall 2021, HW 1 1
(c) Erin comes across a proof that is part of a homework problem while studying course material. She reads it and then, after she has understood it, writes her own solution using the same approach. She submits the homework with a citation to the website.
(d) Frank is having trouble with his homework and asks Grace for help. Grace lets Frank look at her written solution. Frank copies it onto his notebook and uses the copy to write and submit his homework, crediting Grace.
(e) Heidi has completed her homework using LATEX. Her friend Irene has been working on a homework problem for hours, and asks Heidi for help. Heidi sends Irene her PDF solution, and Irene uses it to write her own solution with a citation to Heidi.
(f) Joefoundhomeworksolutionsbeforetheywereofficiallyreleased,andeverytimehegotstuck, he looked at the solutions for a hint. He then cited the solutions as part of his submission.
3 Use of is incredibly useful for Q&A in such a large-scale class. We will use Piazza for all important announcements. You should check it frequently. We also highly encourage you to use Piazza to ask questions and answer questions from your fellow students.
(a) Read the section of the course policies and explain what is wrong with the following hypothetical student question: “Can someone explain the proof of Theorem XYZ to me?” (Assume Theorem XYZ is a complicated concept.)
(b) When are the weekly posts released? Are they required reading?
(c) If you have a question or concern not directly related to the course content, where should you direct it?
4 Discussion Assignment
Please confirm that you have signed up for one of the discussion section at https://tinyurl. com/cs70fa21-signup. What is the name of your GSI and the time of your discussion sec- tion?
5 Remote Course Option
Although this class is designated to be in-person, we are facilitating remote exams for those who are not physically at Berkeley. We ask everyone to fill out this form.
(a) Do you acknowledge that the above form is binding, and you will not be able to change your decision except in rare extenuating circumstances (i.e., you’re out sick with COVID the day of the exam)?
(b) What is the secret phrase?
CS 70, Fall 2021, HW 1 2
6 Academic Integrity
Please write or type out the following pledge in print, and sign it.
I pledge to uphold the university’s honor code: to act with honesty, integrity, and respect for others, including their work. By signing, I ensure that all written homework I submit will be in my own words, that I will acknowledge any collaboration or help received, and that I will neither give nor receive help on any examinations.
7 Propositional Practice
In parts (a)-(c), convert the English sentences into propositional logic. In parts (d)-(f), convert the propositions into English. In part (f), let P(a) represent the proposition that a is prime.
(a) There is one and only one real solution to the equation x2 = 0.
(b) Between any two distinct rational numbers, there is another rational number.
(c) If the square of an integer is greater than 4, that integer is greater than 2 or it is less than -2. (d) (∀x∈R)(x∈C)
(e) (∀x,y ∈ Z)(x2 −y2 ̸= 10)
(f)(∀x∈N)[(x>1)=⇒ (∃a,b∈N)((a+b=2x)∧P(a)∧P(b))] 8 Implication
Which of the following assertions are true no matter what proposition Q represents? For any false assertion, state a counterexample (i.e. come up with a statement Q(x,y) that would make the implication false). For any true assertion, give a brief explanation for why it is true.
(a) ∃x∃yQ(x,y) =⇒ ∃y∃xQ(x,y). (b) ∀x∃yQ(x,y) =⇒ ∃y∀xQ(x,y). (c) ∃x∀yQ(x,y) =⇒ ∀y∃xQ(x,y). (d) ∃x∃yQ(x,y) =⇒ ∀y∃xQ(x,y).
9 Logical Equivalence?
Decide whether each of the following logical equivalences is correct and justify your answer. (a) ∀xP(x)∧Q(x) ≡ ∀xP(x)∧∀xQ(x)
CS 70, Fall 2021, HW 1 3
(b) ∀xP(x)∨Q(x) ≡ ∀xP(x)∨∀xQ(x)
(c) ∃xP(x)∨Q(x) ≡ ∃xP(x)∨∃xQ(x)
(d) ∃xP(x)∧Q(x) ≡ ∃xP(x)∧∃xQ(x)
10 Preserving Set Operations
Forafunction f,definetheimageofasetX tobetheset f(X)={y|y= f(x)forsomex∈X}. DefinetheinverseimageorpreimageofasetY tobetheset f−1(Y)={x| f(x)∈Y}. Provethe following statements, in which A and B are sets. By doing so, you will show that inverse images preserve set operations, but images typically do not.
Recall: ForsetsX andY,X =Y ifandonlyifX ⊆Y andY ⊆X. ToprovethatX ⊆Y,itissufficient toshowthat(∀x)((x∈X) =⇒ (x∈Y)).
(a) (b) (c) (d)
f−1(A∩B) = f−1(A)∩ f−1(B).
f−1(A\B) = f−1(A)\ f−1(B). f(A∩B)⊆f(A)∩f(B),andgiveanexamplewhereequalitydoesnothold. f(A\B)⊇f(A)\f(B),andgiveanexamplewhereequalitydoesnothold.
Prove that if for any two integers x and y, if 10 does not divide xy, then 10 does not divide x and 10 does not divide y. In notation: (∀x,y ∈ Z) (10 xy) =⇒ ((10 x) ∧ (10 y)). What proof technique did you use?
Prove or disprove the contrapositive. Prove or disprove the converse.
Rationals and Irrationals
Prove that the product of a non-zero rational number and an irrational number is irrational.
CS 70, Fall 2021, HW 1 4