Due Friday, January 24 at 1:00 PM Pacific
This second problem set explores mathematical logic and dives deeper into formal mathematical proofs. We've chosen the questions here to help you get a more nuanced understanding for what first-order logic statements mean (and, importantly, what they don't mean) and to give you a chance to practice your proofwriting. By the time you've completed this problem set, we hope that you have a much better grasp of mathematical logic and how it can help improve your proofwriting structure.
Before attempting this problem set, we recommend that you do the following:
- Familiarize yourself with the online Truth Table Tool and play around with it a bit to get a feel for the propositional connectives.
- Read the online Guide to Negations and Guide to First-Order Translations.
- Read the First-Order Translation Checklist to get a better sense for common errors in first-order logic translations and how to avoid them.
Good luck, and have fun!
Starter Files
Here are the starter files for the problems you'll submit electronically:
Unpack the files somewhere convenient and open up the bundled project.
If you would like to type your solutions in $\LaTeX$, you may want to download this template file where you can place your answers:
General Advice
- First, read through the index of problems below to get an idea of time management for this assignment.
- Next, glance through all the questions before you start working. This not only ensures you won't be caught off guard as you reach later problems, but also gives your brain a chance to start working on some of these as a background process while you do other things.
- If you get stuck, consider moving on to another problem for a while! Changing things up is a great way to get out of a rut, make new connections between concepts, and spark creative insights!
- If you realize you don't have the requisite knowledge to complete a problem, take a step back from it and review the relevant lecture materials. Skipping lecture and trying to extract the relevant tidbits for each problem will lead to a more frustrating experience than engaging fully with a lecture and approaching the problem sets afterward.
Problem Index
Part 1: Logical Expressions in English and in Code
This section contains seven problems (six autograded and one short-response (very-short-response) question that is written / manually graded). We recommend you aim to complete Q1-Q4 by Sunday evening and Q5-Q7 by Monday evening. If you run into trouble, read through the resources linked in the pset introduction above.
- Q1: Interpersonal Dynamics
- Q2: Propositional Completeness
- Q3: Executable Logic
- Q4: First-Order Negations
- Q5: This, But Not That
- Q6: Translating into Logic
- Q7: All the Everys and Alls
Part 2: Proof Writing
This section contains three problems (all written / manually graded). These rely on the knowledge and understanding you honed above in Q1 through Q7, as well as proof techniques you have already explored. We recommend reading these all at once and then working on these and getting help by Thursday evening. We have a loose outline for that below, but recommend that you jump around and iterate on all of these instead of letting yourself get blocked by any one of them.
- Q8: Yablo's Paradox (complete by Tuesday evening?)
- Q9: Square and Triangular Numbers (complete by Wednesday evening?)
- Q10: Tournament Champions (complete by Thursday evening?)
Optional Fun Problem
This is an optional fun problem! Click through for more details.
- Optional Fun Problem: Insufficient Connectives