cs2102
Discrete Mathematics

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, 8 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, 8 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 (similar to Problem Set 1)

Remember to follow the course pledge you read and signed at the beginning of the semester. For this assignment, you may discuss the problems and work on solutions with anyone you want (including other students in this class), but you must write your own solutions and understand and be able to explain all work you submit on your own. To confirm your own understanding, after discussing the problems with others, you should attempt to write your solutions on your own without consulting any notes from group work sessions. If you get stuck, you may visit notes from the group work sessions, but should make sure you understand things well enough to produce it on your own. You may also use any external resources you want, with the exception of solutions and comments from last year’s offering of this course. Since the staff and students benefit from being able to both reuse problems from previous years, and from being able to provide detailed solutions to students, it is important that students do not abuse these materials even if it is easy to find them. Using solutions from last year’s course would be detrimental to your learning in this course, and is considered an honor violation.

If you use resources other than the class materials, lectures and course staff, you should document this and mention it clearly on your submission. For everyone other than the course staff you work with, you should credit them clearly on your assignment, and should find out something interesting about their favorite book (you shouldn’t include this in your submission, though, especially if they share something private with you).

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.4) 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.

Directions

Solve all 10 problems that follow. For full credit, your answers should be correct, clear, well-written, and convincing.

(Updated: 4 Sept 2017 - reworded question 2 to avoid use of $\prec$.)

(Un)Well-Ordered Sets

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

  1. The empty set; $<$.

  2. The set of integers less than 2102, and the comparator is $>$ (namely, $a$ is ordered before $b$ if and only if $a > b$).

  3. The set of positive rational numbers with lowest terms, $\frac{p}{q}$ where $q < 2102$, under the order imposed by $<$.

  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}{q}$, $b = \frac{r}{s}$. Then, we announce $a \prec b$ if and only if $2^p 8^q < 2^r 8^s$. (Hint: does this even define an ordering?)

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.

Logical Operators

  1. MCS Problem 3.9.

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

Logical Formulas

  1. For the following formula, specify whether it is valid, satisfiable, both valid and satisfiable, or neither valid nor satisfiable: $$((P \rightarrow Q) \land (Q \rightarrow P)) \lor (P \oplus Q)$$ where $\oplus$ denotes XOR. Support your answer with a clear and convincing argument.

  2. 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.