CMSI 585: Programming Language Foundations: Homework #1 Answers

Odd number test in: (Answers vary.)

Cube function in several languages. Best to use the exponentiation operator if the language has it; it will generally be ** but will sometimes be ^. Math.pow is or x*x*x are both okay if the language does not have the symbolic operator.

Notation or Language	Cube Function
Lambda Calculus	$(\lambda x.\,\textrm{power}\;x\;3)$ $\lambda x.\,\textrm{power}\;x\;3$ $\lambda x.\,x^3$
Lisp	`(LAMBDA (x) (expt x 3))`
Python	`lambda x: x ** 3`
JavaScript	`x => x ** 3`
Java	`x -> x * x * x`
Ruby	`->(x) {x ** 3}`
Clojure	`#(* % % %)`
Swift	`{ $0 * $0 * $0 }`
Rust	`\|x:f64\| {x.powi(3)}`
Kotlin	`{x: Double -> x * x * x}`
Go	`func(x float64)float64 {return x * x * x}`
Haskell	`\x -> x ^ 3`

Logic! Please note that the following answers are not unique.
1. Your best friend must help you out of every jam. $y$: you, $b$: best friend of, $Jxj$: $x$ is in jam $j$, $Hxyz$: $x$ helps $y$ achieve goal $z$. (Cool: $H$ is a second-order predicate, since it takes a formula as an argument.) $$\boxed{\forall j. Jyj \supset \mathscr{O}(H(by)y(\neg Jyj))}$$
2. It is not okay to lie. $Lx$: $x$ lies. $$\boxed{\forall x. \neg \mathscr{P}(Lx)}$$
3. You are allowed to not believe that everyone is telling the truth. $y$: you, $Tx$: $x$ is telling the truth. $$\boxed{\mathscr{P}\neg \mathscr{B}_y(\forall x. Tx)}$$
4. If you know what is on the test, you will probably get a good score. $y$: you, $t$: the test, $c$: contents-of, $Sxt$: $x$ scores well on $t$. $$\boxed{pr(Syt \mid \mathscr{K}_y(ct)) \gt 0.5}$$
5. Juliet once believed that Socrates was real, but no longer does. $j$: Juliet, $s$: Socrates, $Rx$: $x$ is real. $$\boxed{\mathbf{P}(\mathscr{B}_jRs) \land \neg \mathscr{B}_jRs}$$
6. Everyone who attended Lollapalooza in 2025 was more likely to have a good time if they took public transportation or carpooled. $Ape$: person $p$ attended event $e$, $z$: Lollapalooza 2025, $Gpe$: person $p$ had a good time at $e$, $Tpe$: person $p$ took public transportation to $e$, $Cpe$: person $p$ carpooled to $e$. $$\boxed{\forall p. Apz \supset pr(Gpz \mid Tpz \lor Cpz) > pr(Gpz \mid \neg(Tpz \lor Cpz))}$$
7. No one knows if Goldbach’s Conjecture is true. $g$: Goldbach’s Conjecture. $$\boxed{\neg \exists x. (\mathscr{K}_xg \lor \mathscr{K}_x\neg g)}$$ (That $\lor$ is important there!)
8. Tanya wrote her book about logic swiftly and eloquently. $Axy$: $x$ wrote $y$, $Lx$: $x$ is about logic, $Bx$: $x$ is a book, $SX$: $X$ was performed swiftly, $EX$: $X$ was performed eloquently, $t$: Tanya. $$\boxed{S(At(\iota b. Bb \land Lb \land Atb)) \land E(At(\iota b. Bb \land Lb \land Atb) )}$$ (It is tempting to invent a function such as $bx$ to mean “the book that $x$ wrote about logic,” but that’s probably too much!)
9. The set of all rational numbers less than $\sqrt{2}$ has no greatest element. $Rx$: $x$ is rational, $Lxy$: $x$ is less than $y$, $q$: $\sqrt{2}$. $$\boxed{\neg \exists y. (Ry \land Lyq) \land \forall x. (Rx \land Lxq) \supset Lxy}$$
10. Romeo doesn’t know that he is doomed. $r$: Romeo, $Dx$: $x$ is doomed. $$\boxed{\neg \mathscr{K}_r Dr}$$ (You could also do $Dr \land \neg \mathscr{K}_r Dr$ because English is ambiguous about whether Romeo is actually doomed or not. Generally, less is better, though.)
Substitutions!
1. $(P\,x)[x \mapsto y] \Longrightarrow \boxed{Py}$
2. $(P\,x)[x \mapsto f\,x] \Longrightarrow \boxed{P(fx)}$
3. $(\forall x. P\,x\,y)[x \mapsto y] \Longrightarrow \boxed{\forall x. Pxy}$ (no free $x$)
4. $(\forall y. P\,x\,y)[x \mapsto y] \Longrightarrow \boxed{\forall z. Pyz}$ (had to rename)
5. $(x \land \exists x. P\,x)[x \mapsto y] \Longrightarrow \boxed{y \land \exists x. Px}$
6. $(\forall x. \exists y. P\,x\,y)[x \mapsto y] \Longrightarrow \boxed{\forall x. \exists y. Pxy}$ (no free $x$)
7. $(\forall x. \exists y. P\,(f\,x\,y))[x \mapsto f\,y] \Longrightarrow \boxed{\forall x. \exists y. P(fxy)}$ (no free $x$)
8. $(\forall f. \exists y. P\,(f\,x\,y))[x \mapsto f\,y] \Longrightarrow \boxed{\forall g. \exists z. P(g(fy)z)}$ (had to rename both)
Write judgments for the following:
1. Truth is necessarily true. $$ \vdash \Box T $$
2. Assuming that Mercury is in retrograde, it is possible that you will have a bad day. $$ Rm \vdash \lozenge\mathbf{F}By $$
3. Something is good assuming not everything is bad. $$ \neg \forall x. Bx \vdash \exists x. Gx $$
4. Assuming $x$ has type integer and $y$ has type natural, then $\frac{x}{y+1}$ has type rational. $$ x\!:\textsf{int}, y\!:\textsf{nat} \vdash \frac{x}{y+1}\!:\textsf{rat} $$
The argument $$ \frac{\forall P.\,P \supset \lozenge \mathscr{K}P}{\Box \mathscr{K}P} $$ says: “You can infer, assuming all true propositions can possibly be known, that the proposition $P$ (whatever the heck that is) is necessarily known.” (Be careful here, the $P$ in the conclusion is free—we don’t know what it is. In particular, it is not universally quantified, so the entire argument is not Fitch’s Paradox of Knowability, even though the problem was phrased to look like it to keep you, and your AI assistant, on your toes.)

Three-valued logic truth table, falsity-avoidance:

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

To be honest, falsity avoidance really has nothing to do with truth tables, but rather with entailment. I was hoping you would call this out in your answer, but if you didn’t, that’s okay. Going over the answers is a great place to learn things.

Math!
1. $3 \uparrow \uparrow 2$
  $= 3 \uparrow 3$
  $= 3^3$
  $= \boxed{27}$
2. $2 \uparrow \uparrow \uparrow 3$
  $= 2 \uparrow \uparrow 2 \uparrow \uparrow 2$
  $= 2 \uparrow \uparrow 4$
  $= 2 \uparrow 2 \uparrow 2 \uparrow 2$ $= 2^{2^4} = 2^{16}$
  $= \boxed{65536}$
3. $790912853^{3892359} \;\mathtt{mod}\; 90277$
  $= \boxed{66207}$
  (Command line: python3 -c 'print(pow(790912853,3892359,90277))')
4. $(3 + 2i - 8k) \times (8i + 2j -k)$
  $= 24i+6j-3k+16i^2+4ij-2ik-64ki-16kj+8k^2$
  $= 24i+6j-3k-16+4k+2j-64j+16i-8$
  $= \boxed{-24 + 40i - 56j + k}$
5. $\log_8{2^{333333333}}$
  $= \log_8{2^{3 \cdot 111111111}}$
  $= \log_8{(2^3)^{111111111}}$
  $= \log_8{8^{111111111}}$
  $= \boxed{111111111}$
Graham’s Number is $g_{64}$ where $g_1 = 3 \uparrow \uparrow \uparrow \uparrow 3$ and $g_{n+1} = 3 \uparrow^{g_n} 3$ for $n \ge 1$. It starts sliding in at 1:09:21 in the ten-hour video.
Ordinals from the VSauce video: $0$, $1$, $2$, ... $\omega$, $\omega+1$, $\omega+2$, ..., $\omega \cdot 2$, ..., $\omega^2$, ..., $\omega^\omega$, $\omega^{\omega^\omega}$, ..., $\omega^{\omega^{\omega^{\textrm{⋰}}}}$, ... $\epsilon_0$, ... $\omega_1$, ..., $\omega_\omega$, ... $\omega_{\omega_\omega}$, ... $\omega_{\omega_{\omega_\ddots}}$, ...