Instructions

You must complete all of these steps to receive credit.

1. Download the AT3 template.

2. Rename the file <firstname>_<lastname>_AT3.tex, filling in <firstname> and <lastname> with your first and last names, respectively.

3. Fill in the sections marked TODO (removing the TODO markings) as directed in the assignment.

4. Ask at least three questions about this assignment or feedback in general (filling in the sections marked TODO).

5. Submit both your source file, <firstname>_<lastname>_AT3.tex, and the compiled pdf <firstname>_<lastname>_AT3.pdf to this google form by 2019-10-25 End of Day.

Help

• Check out the Reference section below.
• For more help with $\mathrm{\LaTeX}$, here is the $\mathrm{\LaTeX}$ Resources Page.
• If you’re still having trouble, feel free to contact me at sristic[at]seas[dot]upenn[dot]edu. Be sure to start the subject line with “BOOTS:”

Reference

NOTE: We are using two notations for functions for this assignment, both the math-like infix symbol notation (as in $1 + 2$) and the lambda-like function notation (as in $\mathrm{add}\ 1\ 2$) with spaces instead of parentheses and commas for the entirety of the problem. Note that we will not at all use the function notation with parentheses (as in $f(x)$).

We are dealing with variables $p,q,\ldots$ which can take what are called boolean values, that is, either the value $\mathrm{true}$ or the value $\mathrm{false}$.

We can define functions on booleans, like $\mathrm{not}$, which, when given a value $\mathrm{true}$ returns $\mathrm{false}$ (so that $\mathrm{not\ true = false}$) and vice versa. There is a standard set of functions on booleans $p$ and $q$:

• $\mathrm{not}\ p$,
  • also notated $\lnot p$ (LaTeXed with \lnot (logical not))
• $\mathrm{and}\ p\ q$,
  • also notated $p \land q$ (LaTeXed with \land)
• $\mathrm{or}\ p\ q$, the non-exclusive or (true if at least one of $p$ and $q$ are true),
  • also notated $p \lor q$ (LaTeXed with \lor)
• $\mathrm{xor}\ p\ q$, the exclusive or (true if exactly one of $p$ and $q$ are true)
  • also notated $p \oplus q$ (LaTeXed with \oplus)
• $\mathrm{implies}\ p\ q$,
  • also notated $p \to q$ (LaTeXed with \to or \rightarrow)
• $\mathrm{nand}\ p\ q$,
  • also notated $p \barwedge q$ (LaTeXed with \barwedge)

The definitions of these functions are given in the following truth table, using $0$ for false and $1$ for true.

$$\begin{align*} \begin{array}{cc|cccc} \hline p & q & \lnot p & p \land q & p \lor q & p \oplus q & p \to q & p \barwedge q \\ \hline 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 & 1 & 0 & 1 \\ 1 & 1 & 0 & 1 & 1 & 0 & 1 & 0 \\ \hline \end{array} \end{align*}$$

There are 16 different possible boolean functions of two variables (why?). It turns out that the $\mathrm{nand}$ function is enough to define any other boolean function. That is, it is possible to write any boolean function of $p$ and $q$ as an expression using only $p$, $q$, and $\mathrm{nand}$ (and parentheses).

Assignment

Complete all points to the best of your ability. If you get stuck and have tried everything you can think of to get unstuck, explain your thinking, demonstrate effort and time. I’m not looking for a correct solution; I’m looking for your thought process.

1. Convert this expression from math-like function notation (where $f(x, y)$), to the lambda-like function notation (where $f\ x\ y$). Give both the minimally—e.g., $f\ x\ y\ z$—and fully—e.g., $(((f\ x)\ y)\ z)$— parenthesized forms.

   $$\begin{align*} e &= g(h(j,k),a,f(f(x, y)), x) \end{align*}$$

   This is a follow-up from AT2 problem 1, where there is an example solution.

2. Show that $\mathrm{nand}\ (\mathrm{nand}\ p\ p)\ p$ is $\mathrm{true}$ for all possible values of $p$.

3. Write definitions for:

   $$\begin{align*} 1)&& \mathrm{not}\ p &= \lnot p \\ 2)&& \mathrm{or}\ p\ q &= p \lor q \\ 3)&& \mathrm{xor}\ p\ q &= p \oplus q \\ 4)&& \mathrm{implies}\ p\ q &= p \to q \end{align*}$$

   Using only the $\operatorname{nand}$ function. Write your answers in both the lambda-like notation (with “$\operatorname{nand}$”) and the math-like notation (with “$\barwedge$” (LaTeXed with \barwedge)).

   For example, the function $\mathrm{and}$ written with $\mathrm{nand}$ is

   $$\newcommand{\nand}{\mathrm{nand}} \mathrm{and}\ p\ q = p \land q = \boxed{ \nand\ (\nand\ p\ q)\ (\nand\ p\ q) } = \boxed{(p \barwedge q) \barwedge (p \barwedge q)}$$

   with $\mathrm{\LaTeX}$ code

    \mathrm{and}\ p\ q = p \land q
    = \boxed{ \nand\ (\nand\ p\ q)\ (\nand\ p\ q) }
    = \boxed{(p \barwedge q) \barwedge (p \barwedge q)}