Math 299 – Spring 2021: Training Workouts

Welcome to Math 299.  I will post assignments and announcements here throughout the semester.  Check back frequently.  Below are links to some resources we will be using in the course.

• Download and install Dropbox on your laptop and send me the email address you used for your Dropbox account if you haven’t done so already.
• Read the course syllabus (see below).  Let me know if you have any questions.
• Read Problem #1 on the 2021 Prove it! admissions test and then play the Scrambler! Product Catalog game until you figure out how to reliably beat any goal on all three machines (Juggler, Frogger, Whirligig). You do not have to answer parts (a)-(f) of the question or hand in anything, but you should try figure out a strategy that is guaranteed to beat all three machines no matter what goal comes up when you select “New Goal”. I will ask you in class how to solve each machine. Virtual prize cookies may be awarded.

• 0.For each assignment that you hand in in Dropbox, make a folder called “Assignement #n”, where n is the Assignment number I have posted here. So for this assignment, put it in a subfolder of our shared Dropbox folder called “Assignment #1” and put your documents in there. All assignments must be handed in prior to class on the day they are due. Be sure to name your files as explained in the syllabus below.
• 1. Answer Problem #5 at the end of Chapter 1 in the lecture notes. Type up your answer (you can use any editor for this assignment) and save your file to Dropbox as described above.
• 2. Try to figure out how to consistently beat Trix Game.  This is another example of a Toy Proof system. I’ll ask for volunteers in class. Cookies may be awarded.

• Reminder: For each assignment that you hand in in Dropbox, make a folder called “Assignement #n”, where n is the Assignment number I have posted here. So for this assignment, put it in a subfolder of our shared Dropbox folder called “Assignment #2” and put your documents in there. All assignments must be handed in prior to class on the day they are due. Be sure to name your files as explained in the syllabus below.
• 1. Prove each of the following Circle-Dot theorems. You must use the Toy Proof software to ensure that your proofs are correct. Prove them using the software, and then print that web page to a PDF document and place that pdf document in your Dropbox homework folder with the appropriate file name. If you put one pdf for each problem below, name the files so I know which one is which.
  • Thm H $\bullet\bigcirc\bullet$
  • Thm J  $\bigcirc\bigcirc\bigcirc$
  • Thm M  $\bigcirc\bigcirc\bullet\bullet\bullet$
  • Thm R  $\bullet\bigcirc\bullet\bigcirc\bullet\bigcirc$
• 2. (Bonus) Can you explain why every circle-dot expression can be proven in the Circle-Dot toy system, or if not, determine with certainty exactly those expressions which can? Write up your answer in a pdf document (using whatever editor you like for now) and put it in the same Dropbox folder with this assignment.
• 3. Download and install Lurch 0.8. Install it on the computer that you use to do your homework where you have our shared Dropbox folder.

• 1. Answer questions 2.1, 2.2, and 2.3 in the lecture notes. You can type up your answers using any editor or write them by hand on paper. Either way scan or print your document to a pdf and put it in the appropriate folder in Dropbox.

• 0. Memorize the rules inference for Propositional Logic in Section 4.2 of the lecture notes (in your Dropbox folder).  We will have a quiz in class on Tuesday where you will be asked to recall them entirely from memory. (Memorize the template forms in the second table.)
• 1. Type up a Formal proof of each of the following statements. You can only use the rules of Propositional Logic discussed in class. To do that, start your new document by using the Lurch menu File > Choose Topic.. > Logic > Propositional Logic > Blank Document. For each theorem, first state the theorem, then give a proof of it directly below it as I did in the examples in class. Number each statement in the proof, and give a reason for every statement (except Assumptions, which need no reason).  Use the auto-numbered list in the Lurch to number the lines – don’t type the line numbers by hand. Be sure to give the line numbers for the statements used as the premises (i.e. inputs) immediately after the reason.  Use the TAB key to indent your assumptions, and also to line up your reasons in a separate column.  Do all of your work in Lurch.  You do not have to use Lurch to check your work on this assignment, but you can if you want to.  If you have questions, just let me know. Put your assignment in Dropbox in a folder for Assignment 4. Save it as a .lurch file (not a pdf) so I can type in it and leave comments and grades.
  • a. $Q \Rightarrow Q \text{ and } Q$
  • b. $Q \Rightarrow Q \text{ or } P$
  • c. $Q \Rightarrow (P \Rightarrow Q)$
  • d. $P \Leftrightarrow \neg\neg P$
  • e. $\neg ( \neg P \text{ and } P )$

• 0. Memorize the rules inference for Propositional Logic in Section 4.2 of the lecture notes (in your Dropbox folder). We may have a quiz in class on Thusday where you will be asked to recall them entirely from memory. (Memorize the template forms in the second table.)
• 1. Prove each of the following tautologies. Type up your formal proofs in Lurch.  Use the formal style we used in class – numbered lines, one statement per line, and a reason and premises stated for each line that needs one.  You can only use the rules of propositional logic and the copy rule.  Start your new document by using the Lurch menu File > Choose Topic.. > Logic > Propositional Logic > Blank Document. No other rules and no other theorems.  Put your files in your Dropbox folder in a subfolder named “Assignment 5” and name your files “Assignment 5 – firstname.lurch”.
• • a. Easy warm up: $R \Rightarrow (Q \Rightarrow (P \text{ or } Q))$
  • b. Anything follows from a contradiction:  $\rightarrow\leftarrow \Rightarrow P$
  • c. Associativity of ‘or’: $(P \text{ or } Q) \text{ or } R \Leftrightarrow P \text{ or } (Q \text{ or } R)$
  • d. DeMorgan’s Law 2: $\neg (P \text{ and } Q) \Rightarrow \neg P \text{ or } \neg Q$

• 1. Prove each of the following tautologies. Type up your formal proofs in Lurch.  Use the formal style we used in class – numbered lines, one statement per line, and a reason and premises stated for each line that needs one.  You can only use the rules of propositional logic and the copy rule.  Start your new document by using the Lurch menu File > Choose Topic.. > Logic > Propositional Logic > Blank Document. No other rules and no other theorems.  Put your files in your Dropbox folder in a subfolder named “Assignment 6” and name your files “Assignment 6 – firstname.lurch”. Since Lurch may bog down if you ask it to check this many proofs in one document, you can make more than one Lurch document, with the filename indicating which problem(s) it contains and put them all in the Assignment 6 folder.
• • a. Easy peasy:  $P \text{ and } Q \Leftrightarrow Q \text{ and } P $
  • b. An or- warm up:  $P \text{ or } Q \Rightarrow Q \text{ or } P $
  • c. Excluded middle:  $P \text{ or } \neg P$
  • d. Alternate definition of implies:  $P \Rightarrow Q \Leftrightarrow \neg P \text{ or } Q $
  • e. Distributivity of ‘or’ over ‘and’:  $P \text{ or } (Q \text{ and } R) \Leftrightarrow (P \text{ or } Q) \text{ and } (P \text{ or } R) $
  • f. Alternate OR- rule:  $(P \text{ or } Q) \text{ and } \neg P \Rightarrow Q$
• 2. Memorize the rules inference for Propositional Logic in Section 4.2 of the lecture notes. We may have a quiz in class on Tuesday where you will be asked to recall them entirely from memory. (Memorize the template forms in the second table.)

• 1. Memorize the rules for quantifiers ($\forall$, $\exists$) in Template form from the lecture notes for a possible quiz in class on Thursday.
• 2. Prove each of the following theorems. Type up your formal proofs in Lurch.  Use the formal style we have been using – numbered lines, one statement per line, and a reason and premises stated for each line that needs one.  You can only use the rules of propositional logic and predicate logic (no other rules and no other theorems even if they are available in Lurch).  You should use the rules from Logic > Predicate Logic > Blank Document topic in your lurch file (select it from the File>Choose Topic menu and check the both boxes at the bottom of the dialog before clicking the OK button). Put your files in your Dropbox folder in a subfolder called ‘Assignment 7’.
• • a. Existence warmup: $(\exists x,Q(x))\Rightarrow (\exists x,P(x)\Rightarrow Q(x)).$
  • b. Mini-DeMorgan’s Law: $(\forall x,\neg P(x)) \Rightarrow (\neg \exists y, P(y))$

Midterm Exam Fun!

In your Dropbox folder there is a new subfolder named, ‘midterm’ and in that subfolder there is a file named Midterm Exam.lurch. Make a backup copy of that file to start, and name that copy Firstname midterm.lurch where you replace Firstname with your first name.

Open that file in Lurch and answer all of the questions. You should type all of your answers in Lurch. You do not have to bubble anything, but you can if you want to. If your Lurch file starts to get too large you can make several copies of the file and put one or more proofs in each file. Clearly name the files so I know which problems are in which files. You should only use the rules from Logic > Predicate Logic with Equality > Blank Document topic in your lurch file (select it from the File> Choose Topic menu and check the both boxes at the bottom of the dialog before clicking the OK button) if you make a new file. Put all of your files in your Dropbox folder in the ‘midterm’ subfolder.

The exam is due in Dropbox on Thursday, March 11, 2021 at 6:00pm Eastern (i.e., at the start of class). You can (and should) do all of your work in the Dropbox folder as drafts. I won’t grade anything before it is due.

As this is a take-home midterm, no collaboration is allowed on this assignment. You must all complete it individually without discussing it with anyone else (including each other, tutors, and other instructors). You cannot use any internet resources, discuss the problems online on Discord servers, chat rooms, Stack Exchange, email, text, Facebook, or any other form of communication. You cannot look up proofs or definitions or other math facts online, or use any resources other than those in our course. Any cheating on the midterm will result in failing the entire course, not just the midterm exam itself.

You can use our lecture notes, my handwritten lecture notes from class, Lurch, and any previous examples and homework assignments from this semester that are in the Dropbox folder that you are currently sharing with me. You can also ask me anything you want, and I will decide if I want to answer it.

It is a long exam, so I suggest you start working on it now. Enjoy!