cs2102
Discrete Mathematics
This is a preserved file from cs2102 Fall 2016. An updated version may exist at https://uvacs2102.github.io/

Problem Set 2

\dbox{{\bf Deliverable:} Submit your responses as a single PDF file on the collab site before {\bf 6:29pm} on {\bf Friday, 9 September}. The PDF you submit can be a scanned handwritten file (please check the scan is readable), or a typeset PDF file (e.g., generated by LaTeX or Word).}

Deliverable: Submit your responses as a single PDF file on the collab site before 6:29pm on Friday, 9 September. The PDF you submit can be a scanned handwritten file (please check the scan is readable), or a typeset PDF file (e.g., generated by LaTeX or Word).

Collaboration Policy - Read Carefully

For this assignment, you should work in groups of one to three students, so long as the total number of siblings the members of your group have is divisible by three. Note that this means that someone with, say, one sibling, should not work alone, but either needs to find a teammate with two (or 5 or 8, etc.) siblings, or two teammates whose sibling counts sum to the right number. If you have half-siblings, you can decide to count them as either 0, ½, or 1.

If you work with teammates, you should submit one assignment that represents your collective best work with all of your names and UVA ids on it. Everyone on a team should understand everything you turn in for the assignment well enough to be able to produce it completely on your own. You are encouraged to use the #teaming channel to find suitable teammates. You should make a legitimate effort to form a team that satisfies the collaboration policy, but if you cannot find suitable teammates, it is definitely better to submit an assignment on your own than to not do the assignment!

You may discuss the assignment with anyone you want and get help from others, so long as it is help in the spirit of learning how to do things yourself not getting answers you don’t understand.

Remember to follow the course pledge you read and signed at the beginning of the semester. For this assignment, you may consult any outside resources you want, including books, papers, web sites and people. You may consult an outside person (e.g., another friend who is a CS major but is not in this class) who is not a member of the course staff, but that person cannot type anything in for you and all work must remain your own and outside sources should never give you specific answers to problem set questions. If you use resources other than the class materials, lectures and course staff, you should document this clearly on your submission.

You are strongly encouraged to start early and take advantage of the scheduled office hours for this course.

Preparation

This problem set focuses on Chapter 2 and Chapter 3 (through 3.5) of the MCS book, and Class 3 and Class 4.

Download PDF for Problems.

Your response should be submitted as a single PDF file using collab: submission link

Directions

Solve all 12 problems on the next two pages. For full credit, your answers should be correct, clear, well-written, and convincing.

(Un)Well-Ordered Sets

For each of these question, answer if the given set and comparator is well-ordered. Support your answer with a brief, but clear and convincing, argument.

  1. The empty set; $<$.

  2. The set of integers less than 2102; $>$.

  3. The set of positive rational numbers with lowest terms, $\frac{p}{q}$ where $q < 2102$; $<$.

  4. The set of positive rational numbers; to compare two rational numbers, $a$, $b$, write them as fractions in lowest terms (which we know exist because of the well-ordering principle on the integers!), $a = \frac{p_a}{q_a}$, $b = \frac{p_b}{q_b}$. Then, $a \prec b$ iff $p_a q_b < p_b q_a$.

Well-Ordering Principle Proofs (and Non-Proofs)

  1. MCS Problem 2.2 (explain clearly which proof step is invalid and why).

  2. (Similar to Problem 2.6) The “Exponential Losses” Casino has chips with value \$1, \$2, \$4, \$8, \$16, \ldots, \$2$^{k}$, but has a rule that bettors may not use more than one of the same value of chip to make any bet. Prove that all integer bets from \$1 to \$2$^{k + 1} - 1$ can be made.

  3. MCS Problem 2.17.

Logical Operators

  1. How many 3-input, 1-output Boolean operators are there? Support your answer with a convincing, concise justification.

  2. Show that is it possible to implement the 3-input Boolean operator, \smallcaps{parity}, defined below, using only the 2-input FTFF operator and \smallcaps{NOT}. \begin{center} \begin{tabular}{ccc|c} $P$ & $Q$ & $R$ & \smallcaps{parity}$(P, Q, R)$ \ \hline \T & \T & \T & \T
    \T & \T & \F & \F
    \T & \F & \T & \F \
    \T & \F & \F & \T
    \F & \T & \T & \F
    \F & \T & \F & \T
    \F & \F & \T & \T \
    \F & \F & \F & \F
    \end{tabular} \end{center} (Note that there are easy, clear ways to do this, and painful, tedious ways. Try to find an easy, clear way, before spending a lot of effort on a painful, tedious way!)

Logical Formulas

  1. Write the following natural language statement (from the Eighth Amendment to the US Constitution) as a logical formula. Your goal is to produce a simple and clear statement whose meaning matches what you believe is the intent of the natural language statements. If there are logical ambiguities in the statement, explain them.

Excessive bail shall not be required, nor excessive fines imposed, nor cruel and unusual punishments inflicted.

Logical Equivalences

  1. Determine if the following statements are logically equivalent, and support your answer with a clear proof.

$$ Q \implies (P \implies R) \qquad \textrm{and} \qquad (Q \implies P) \implies R $$

  1. Given the following statements, prove $S$: $$ Q,\quad \neg P,\quad L \implies P,\quad Q \implies M,\quad \neg(\neg Q \vee P) \implies \neg R,\quad (\neg L \wedge M) \implies S \vee R $$