Discrete Mathematics and Probability Theory HW 1

CS 70 Discrete Mathematics and Probability Theory

HW 1
Sundry
Before you start your homework, write down your team. Who else did you work with on this
homework? List names and email addresses. (In case of homework party, you can also just describe
the group.) How did you work on this homework? Working in groups of 3-5 will earn credit for
your "Sundry" grade.
Please copy the following statement and sign next to it:
I certify that all solutions are entirely in my words and that I have not looked at another student’s
solutions. I have credited all external sources in this write up.
1 Always True or Always False?
Classify the following statements as being one of the following and justify your answers.
• True for all combinations of x and y (Tautology)
• False for all combinations of x and y (Contradiction)
• Neither
(a) x∧(x =⇒ y)∧(¬y)
(b) x =⇒ (x∨y)
(c) (x∨y)∨(x∨ ¬y)
(d) (x =⇒ y)∨(x =⇒ ¬y)
(e) (x∨y)∧(¬(x∧y))
(f) (x =⇒ y)∧(¬x =⇒ y)∧(¬y)
CS 70, Fall 2017, HW 1 1
2 Lewis Carroll
Here is an extract from Lewis Carroll’s treatise Symbolic Logic of 1896:
(I) No one, who is going to a party, ever fails to brush his or her hair.
(II) No one looks fascinating, if he or she is untidy.
(III) Opium-eaters have no self-command.
(IV) Everyone who has brushed his or her hair looks fascinating.
(V) No one wears kid gloves, unless he or she is going to a party.
(VI) A person is always untidy if he or she has no self-command.
(a) Write each of the above six sentences as a quantified proposition over the universe of all people.
You should use the following symbols for the various elementary propositions: P(x)for “x goes
to a party”, B(x) for “x has brushed his or her hair”, F(x) for “x looks fascinating”, U(x) for
“x is untidy”, O(x) for “x is an opium-eater”, N(x) for “x has no self-command”, and K(x) for
“x wears kid gloves”.
(b) Now rewrite each proposition equivalently using the contrapositive.
(c) You now have twelve propositions in total. What can you conclude from them about a person
who wears kid gloves? Explain clearly the implications you used to arrive at your conclusion.
3 Equivalences with Quantifiers
Evaluate whether the expressions on the left and right sides are equivalent in each part, and briefly
justify your answers.
(a) ∀x

(∃y Q(x, y)) ⇒ P(x)
?
∀x ∃y

Q(x, y) ⇒ P(x)
?
(b) ¬∃x ∀y

P(x, y) ⇒ ¬Q(x, y)
?
∀x

(∃y P(x, y))∧(∃y Q(x, y))?
(c) ∀x ∃y

P(x) ⇒ Q(x, y)
?
∀x

P(x) ⇒ (∃y Q(x, y))?
4 Karnaugh Maps
Below is the truth table for the boolean function
Y = (¬A∧ ¬B∧C)∨(¬A∧B∧ ¬C)∨(A∧ ¬B∧C)∨(A∧B∧C).
CS 70, Fall 2017,
A B C Y
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 1
In this question, we will explore a different way of representing a truth table, the Karnaugh map.
A Karnaugh map is just a grid-like representation of a truth table, but as we will see, the mode
of presentation can give more insight. The values inside the squares are copied from the output
column of the truth table, so there is one square in the map for every row in the truth table.
Around the edge of the Karnaugh map are the values of the input variables. Note that the sequence
of numbers across the top of the map is not in binary sequence, which would be 00, 01, 10, 11. It
is instead 00, 01, 11, 10, which is called Gray code sequence. Gray code sequence only changes
one binary bit as we go from one number to the next in the sequence. That means that adjacent
cells will only vary by one bit, or Boolean variable. In other words, cells sharing common Boolean
variables are adjacent.
For example, here is the Karnaugh map for Y:
00 01 11 10
0 0 1 0 1
1 0 1 1 0
𝐴
𝐵𝐶
The Karnaugh map provides a simple and straight-forward method of minimizing boolean expressions by visual inspection. The technique is to examine the Karnaugh map for any groups of
adjacent ones that occur, which can be combined to simplify the expression. Note that “adjacent”
here means in the modular sense, so adjacency wraps around the top/bottom and left/right of the
Karnaugh map; for example, the top-most cell of a column is adjacent to the bottom-most cell of
the column.
For example, the ones in the second column in the Karnaugh map above can be combined because
(¬A ∧ ¬B ∧C) ∨ (A ∧ ¬B ∧C) simplifies to (¬B ∧C). Applying this technique to the Karnaugh
map (illustrated below), we obtain the following simplified expression for Y:
Y = (¬B∧C)∨(A∧C)∨(¬A∧B∧ ¬C).
CS 70, Fall 2017, HW 1 3
00 01 11 10
0 0 1 0 1
1 0 1 1 0
𝐴
𝐵𝐶
(a) Write the truth table for the boolean function
Z = (¬A∧ ¬B∧ ¬C∧ ¬D)∨(¬A∧ ¬B∧C∧ ¬D)∨(A∧ ¬B∧ ¬C∧ ¬D)
∨(A∧ ¬B∧C∧ ¬D).
(b) Using your truth table, fill in the Karnaugh map for Z below.
00 01 11 10
00
01
11
10
𝐴𝐵
𝐶𝐷 (c) Using your Karnaugh map, write down a simplified expression for Z.
(d) Show that this simplification could also be found algebraically by factoring the expression for
Z.
5 Social Network
Suppose that p1, p2,..., pn denote n people where every two people are either friends or strangers.
Let Friends(x, y) be the predicate “x and y are friends”. Prove or provide a counterexample for the
following statements.
(a) For all cases with n = 5 people, there exists a group of 3 people that are either all friends or all
strangers. In mathematical notation we write this as:
∃(i, j, k) ∈ {1,2,...,5}
3
such that i < j < k and (Friends(pi
, pj)∧Friends(pj
, pk)
∧Friends(pi
, pk))∨(¬Friends(pi
, pj)∧ ¬Friends(pj
, pk)∧ ¬Friends(pi
, pk)).
(b) For all cases with n = 6 people, there exists a group of 3 people that are either all friends or all
strangers. In mathematical notation we write this as:
∃(i, j, k) ∈ {1,2,...,6}
3
such that i < j < k and (Friends(pi
, pj)∧Friends(pj
, pk)
∧Friends(pi
, pk))∨(¬Friends(pi
, pj)∧ ¬Friends(pj
, pk)∧ ¬Friends(pi
, pk)).
CS 70, Fall 2017, HW 1 4
6 Prove or Disprove
(a) ∀n ∈ N, if n is odd then n
2 +2n is odd.
(b) ∀x, y ∈ R, min(x, y) = (x+y−|x−y|)/2.
(c) ∀a,b ∈ R if a+b ≤ 10 then a ≤ 7 or b ≤ 3.
(d) ∀r ∈ R, if r is irrational then r +1 is irrational.
(e) ∀n ∈ N, 10n
2 n!.
CS 70, Fall 2017, HW 1 5