CS 70 Discrete Mathematics and Probability Theory
Fall 2021 HW 1
Due: Friday 9/3, 10:00 PM
Grace period until Friday 9/3, 11:59 PM
Sundry
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
(a) 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?
(b) 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?
2 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) Joe found homework solutions before they were officially released, and every time he got stuck,
he looked at the solutions for a hint. He then cited the solutions as part of his submission.
3 Use of Piazza
Piazza 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 Piazza Etiquette 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
https://tinyurl.com/cs70fa21-signup
https://tinyurl.com/cs70fa21-signup
https://forms.gle/Uqz6BpSfXfhdifsS6
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 6= 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) ∀x
(
P(x)∧Q(x)
)
≡ ∀x P(x)∧∀x Q(x)
CS 70, Fall 2021, HW 1 3
(b) ∀x
(
P(x)∨Q(x)
)
≡ ∀x P(x)∨∀x Q(x)
(c) ∃x
(
P(x)∨Q(x)
)
≡ ∃x P(x)∨∃x Q(x)
(d) ∃x
(
P(x)∧Q(x)
)
≡ ∃x P(x)∧∃x Q(x)
10 Preserving Set Operations
For a function f , define the image of a set X to be the set f (X) = {y | y = f (x) for some x ∈ X}.
Define the inverse image or preimage of a set Y to be the set f−1(Y ) = {x | f (x) ∈ Y}. Prove the
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: For sets X and Y , X =Y if and only if X ⊆Y and Y ⊆ X. To prove that X ⊆Y , it is sufficient
to show that (∀x) ((x ∈ X) =⇒ (x ∈ Y )).
(a) f−1(A∩B) = f−1(A)∩ f−1(B).
(b) f−1(A\B) = f−1(A)\ f−1(B).
(c) f (A∩B)⊆ f (A)∩ f (B), and give an example where equality does not hold.
(d) f (A\B)⊇ f (A)\ f (B), and give an example where equality does not hold.
11 Proof by?
(a) 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?
(b) Prove or disprove the contrapositive.
(c) Prove or disprove the converse.
12 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
Administrivia
Course Policies
Use of Piazza
Discussion Assignment
Remote Course Option
Academic Integrity
Propositional Practice
Implication
Logical Equivalence?
Preserving Set Operations
Proof by?
Rationals and Irrationals