# 1. Some vacuous set theory (20 points)

Prove or disprove each of the following statements. Assume that the universal quantifiers range over all sets.

## 1.1. Solution

1. Disproof: consider the empty set itself; by definition, no x is an element of the empty set, so in particular the empty set is not an element of itself. It follows that

which is logically equivalent to

2. Proof: Use the definition of subset to expand

as

latex error! exitcode was 1 (signal 0), transscript follows: This is pdfTeX, Version 3.1415926-2.5-1.40.14 (TeX Live 2013) entering extended mode (./latex_813dccf52b5544f3a26f5080442b12a4a2bdcde8_p.tex LaTeX2e <2011/06/27> Babel <3.9f> and hyphenation patterns for 78 languages loaded. (/usr/local/texlive/2013/texmf-dist/tex/latex/base/article.cls Document Class: article 2007/10/19 v1.4h Standard LaTeX document class (/usr/local/texlive/2013/texmf-dist/tex/latex/base/size12.clo)) (/usr/local/texlive/2013/texmf-dist/tex/latex/base/inputenc.sty (/usr/local/texlive/2013/texmf-dist/tex/latex/base/utf8.def (/usr/local/texlive/2013/texmf-dist/tex/latex/base/t1enc.dfu) (/usr/local/texlive/2013/texmf-dist/tex/latex/base/ot1enc.dfu) (/usr/local/texlive/2013/texmf-dist/tex/latex/base/omsenc.dfu))) No file latex_813dccf52b5544f3a26f5080442b12a4a2bdcde8_p.aux. ! Missing $ inserted. <inserted text> $ l.8 \end{document} [1] (./latex_813dccf52b5544f3a26f5080442b12a4a2bdcde8_p.aux) ) (see the transcript file for additional information) Output written on latex_813dccf52b5544f3a26f5080442b12a4a2bdcde8_p.dvi (1 page, 336 bytes). Transcript written on latex_813dccf52b5544f3a26f5080442b12a4a2bdcde8_p.log.

But no set y is in the empty set, so the implication is vacuously true.

# 2. A gambling problem (20 points)

The game of *duality* involves choosing four digits independently and uniformly at random from the range 0, 1, 2, ... 9. You win the game if the sequence of digits you choose contains exactly two distinct digits: 0220, 9199, and 6464 are all winning sequences, but 7777 and 6096 are not. What is the probability of winning this game?

## 2.1. Solution

There are several ways to count the winning combinations. All basically involve noticing (a) that there are 10*9 = 90 different ways to choose the two digits, and that there are 7 distinct patterns the digits can appear in. To see the second part, observe that once the first digit has been fixed, there are 7 choices for whether the others are equal to it or not, obtained by taking the 2^{3}=8 possibilities and excluding the one all-equal case. This gives 10*9*7 = 630 winning combinations, out of 10^{4} total sequences, for a probability of 630/10^{4} = 0.063 (or 6.3%).

# 3. A recurrence (20 points)

Find a closed-form expression for a_{n} as a function of n, where

Hint: use generating functions *or* guess the correct solution and prove that it works by an induction argument.

## 3.1. Solution

The solution is a_{n} = 2^{n+1}-1. This can easily be verified by induction by computing a_{0} = 2^{0+1}-1 = 2-1 = 1 and a_{n+1} = 2a_{n} + 1 = 2(2^{n+1}-1)+1 = 2^{(n+1)+1} - 2 + 1 = 2^{(n+1)+1} - 1.

Alternatively, using generating functions, let F generate the sequence {a_{n}}; then F = 2zF + 1/(1-z). Solving this for F gives

where the numerators in the partial fraction expansion are obtained by the usual trick of multiplying by one of the factors in the denominator and then setting z to make it equal to zero. Recalling that 1/(1-z) generates the sequence {`1} and 1/(1-2z) generates {2`^{n}}, we get

a

_{n}= 2(2^{n}) - 1 = 2^{n+1}- 1.

# 4. Logical equivalence (20 points)

Prove that p => (q \/ r) ≡ (p => q) \/ (p => r). You may use either logical equivalences or a truth table.

## 4.1. Solution

The truth table method is easier to remember but logical equivalences are quicker:

(p => q) \/ (p => r)

≡ (¬p \/ q) \/ (¬p \/ r)

≡ ¬p \/ q \/ r

≡ p => (q \/ r).