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 $E \mathrm{~T}{\mathrm{E}} \mathrm{X}$ you need will be covered in the first discussion section. Useful LaTeX commands: \emph, \phi, \backslashmathbb, \backslashsum, \frac, \backslashlog, \backslashin, \backslashsubseteq, \backslashneg, \land, \backslashlor, and \backslashoverline. Note: this problem assumes you are using $L A T E X$. If you are not, approximate what you see with some alternative tool, or write it by hand and scan it along the other three problems. (a) A truth assignment for an $n$-variable formula $\phi$ is a function $t$ from the variables appearing in $\phi$ to the set of boolean values $\mathbb{B}={0,1}$. There are $2^{n}$ possible truth assignments for an $n$-variable formula-a function that grows extremely rapidly. (b) The fact that $\sum{i=1}^{n} 2^{i}=2^{n+1}-1$ follows from the representation of numbers in binary.
(c) We can give multiple proofs that
$$
\sum_{k=1}^{n}=\frac{k(k+1)}{2}
$$
(d) Is it true that $1+1 / 2+1 / 3+\cdots+1 / n \in O(\log n) \subseteq O(n) ?$
(e) One of De Morgan’s laws says that $\neg(P \wedge Q)=\neg P \vee \neg Q$. But is it prettier to write it $\overline{P Q}=\bar{P} \vee \bar{Q}$ ?

A We write $P \rightarrow Q$ to mean $\neg P \vee Q$. Make truth tables for $A \rightarrow(B \rightarrow C)$ and for $(A \rightarrow B) \rightarrow C$. Are these formulas equivalent?

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; I just got carried away coloring. Edges that cross one another are distinct; you can’t go from one to another.)