Learning Objectives

With this assignment you will demonstrate:

• Your ability to write a simple function in a new programming language
• The ability to work with formal logic
• An understanding of some metalogical concepts
• The ability to work with mathematical operators you don’t see in high school

Readings and Videos

Please:

• Review the course notes for Computer Science Foundations. The Study of Programming Languages, Theories of Computer Science, Logic, and Math Foundations.
• Watch all of the embedded videos in the course notes listed above. Also, follow a few of the links on those pages that interest you.

Optionally you can scan through these slides by Gabriel Robins, though his notation is different from mine, and for fun read Who can name the bigger number by Scott Aaronson.

Submission Instructions

Submit your work in a single beautiful PDF uploaded to BrightSpace. Please do not submit photos of handwritten answers; you need to take pride in your work. Take the time to learn LaTeX. Graduate-level computer science work pretty much demands it.

You may use Generative AI for this assignment. However, you must clean up its output when it does not align with the notation and terminology used in this course. Also please remove all of the silly sycophantic and other silly language it might generate. Your job is to turn in professional, polished work that reflects your understanding.

On the PDF, include your name along with the list of which of the assigned readings were done. For each reading, mark it skimmed, read, or did-not-do. Then include answers to the following:

1. On the course notes page entitled “The Study of Programming Languages” we saw a function written in several programming languages. Write this function in a language not on this list.
2. In the Theories of Computer Science lecture we saw how to express the odd-number test in Lambda Calculus notation, Lisp, Python, JavaScript, Java, Ruby, Clojure, Swift, and Rust. Show how, in each of these notations or languages, to express a function to cube a number. Add Kotlin, Go, and Haskell. (Research may be required.)
3. Translate the following sentences into logical notation.
   1. Your best friend must help you out of every jam.
   2. It is not okay to lie.
   3. You are allowed to not believe that everyone is telling the truth.
   4. If you know what is on the test, you will probably get a good score.
   5. Juliet once believed that Socrates was real, but no longer does.
   6. Everyone who attended Lollapalooza in 2025 was more likely to have a good time if they took public transportation or carpooled.
   7. No one knows if Goldbach’s Conjecture is true.
   8. Tanya wrote her book about logic swiftly and eloquently.
   9. The set of all rational numbers less than $\sqrt{2}$ has no greatest element.
   10. Romeo doesn’t know that he is doomed.
4. Evaluate each of the following. As always, be careful about parentheses and variable renaming:
   1. $(P\,x)[x \mapsto y]$
   2. $(P\,x)[x \mapsto f\,x]$
   3. $(\forall x. P\,x\,y)[x \mapsto y]$
   4. $(\forall y. P\,x\,y)[x \mapsto y]$
   5. $(x \land \exists x. P\,x)[x \mapsto y]$
   6. $(\forall x. \exists y. P\,x\,y)[x \mapsto y]$
   7. $(\forall x. \exists y. P\,(f\,x\,y))[x \mapsto f\,y]$
   8. $(\forall f. \exists y. P\,(f\,x\,y))[x \mapsto f\,y]$
5. Write judgments for the following:
   1. Truth is necessarily true.
   2. Assuming that Mercury is in retrograde, it is possible that you will have a bad day.
   3. Something is good assuming not everything is bad.
   4. Assuming $x$ has type integer and $y$ has type natural, then $\frac{x}{y+1}$ has type rational.
6. What is this logical argument stating, in plain English? $$ \frac{\forall P.\,P \supset \lozenge \mathscr{K}P}{\Box \mathscr{K}P} $$
7. Complete the following truth table for a three-valued logic, assuming your goal is falsity-avoidance.

   $A$	$B$	$\;\;\neg A\;\;$	$\;\;\neg B\;\;$	$A \land B$	$A \lor B$	$A \supset B$	$A \equiv B$
   true	true
   true	false
   true	other
   false	true
   false	false
   false	other
   other	true
   other	false
   other	other

8. Simplify each of the following as much as possible without introducing any roundoff errors. Your simplified expressions must still be exact:
   1. $3 \uparrow \uparrow 2$
   2. $2 \uparrow \uparrow \uparrow 3$
   3. $790912853^{3892359} \;\mathtt{mod}\; 90277$
   4. $(3 + 2i - 8k) \times (8i + 2j -k)$       (quaternion multiplication)
   5. $\log_8{2^{333333333}}$
9. What is Graham’s number and at what timestamp can you find it in the 10 hour video on the Math Foundations page?
10. List the ordinals from the Vsauce video in “increasing order”.