Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

ECS 20:  Discrete Mathematics for Computer Science

HOMEWORK 1 - DUE MONDAY, JANUARY 22 AT 11:59PM

1. (a) Setup accounts on (i) Piazza, (ii) Gradescope, (iii) Overleaf, and (iv) zyBooks. (b) Create a first LaTeX file (or equivalent), get a pdf output from it, and admire its beauty. (c) Finally, indicate as your solution for Problem 1 the date when you finished doing all these things. Sooner is better. Note: this problem assumes you are using  Overleaf and the zyBook. If you are not, omit those parts.

2. Typeset (a)-(e) exactly as they appear below (apart from font size or the location of line breaks, which I don’t care about). All the LaTeX you need will be covered in the first discussion section. Useful LaTeX commands: /emph, /phi, /mathbb, /sum, /frac, /log, /in, /subseteq, /neg, /land, /lor, and /overline.  Note: this problem assumes you are using LaTeX. If you are not, approximate what you see with some alternative typesetter and scan it along the other three problems.

(a) A truth assignment for an n-variable formula ϕ is a function t from the variables appearing in ϕ to the set of boolean values B = {0, 1}.  There are 2n  possible truth assignments for an n-variable formula-a function that grows extremely rapidly.

(b) The fact that follows from the representation of numbers in binary.

(c) We can give multiple proofs that

(d) Is it true that 1 + 1/2 + 1/3 + ··· + 1/n e O(log n) ⊆ O(n) ?

(e) One of De Morgan’s laws says that 一(P V Q) = 一P Λ 一Q. But is it prettier to write it ?

3. Ava bicycles from Davis to Winters at 20mph.  She  arrives at Steady Eddy’s only to discover that it is closed. Dejected, she rides back at 15mph. What is her average speed over the entire trip?

4. How many paths are there from vertex A to vertex I such that, as one walks the indicated path, the letter-names of the vertices keep increasing?  For example, ABCFI is a valid path, but ADFGHI and ABCGFI are not.

(Note:  The color of an edge has no significance.   Edges  that  cross one another are distinct; you can’t go from one to another.)

5. We write P  →  Q  to  mean  ¬P ∨ Q.   Make  truth tables  for A  →  (B  →  C)  and  for (A → B) → C. Are these formulas equivalent?