\dbox{{\bf Deliverable:} Submit your responses as a single PDF file on the collab site before {\bf 6:29:00pm} on {\bf Friday, 15 September}. The PDF you submit can be a scanned handwritten file (please check the scan is readable), or a typeset PDF file (e.g., generated by LaTeX).}

Directions

For maximum credit, your answers should be correct, clear, tasteful, well-written, and convincing. The problem (11) marked with $(\star)$ is challenging enough that it is not necessary to solve it well to get a ``green-star level” grade on this assignment (although we certainly hope you will try and some will succeed!)

Quantified Formulas

State if the the given (quantified) propositions are true or false. You should provide a brief argument supporting your answer (enough to convince a skeptical reader that your answer is correct and not just a guess!). Below, $\mathbb{N}$ represents the non-negative integers = ${0, 1, 2, \cdots }$.

1. $\forall x \in \mathbb{N} \ldotp \exists y \in \mathbb{N} \ldotp x = y + 1.$

2. $\forall x \in \mathbb{N}\ldotp \exists y \in \mathbb{N}\ldotp \exists b \in {0, 1}\ldotp x = 2y + b$.

3. $\forall F \in \textrm{CNF}\ldotp \exists G \in \textrm{DNF}\ldotp F \equiv G.$ The notation $F \equiv G$ denotes that $F$ and $G$ are logically equivalent. Also, CNF is the set of all CNF formulas and DNF is the set of all DNF formulas.

Negating Quantified Formulas

1. Write the negation of the quantified formula of problem 1: $$\forall x \in \mathbb{N} \ldotp \exists y \in \mathbb{N} \ldotp x = y + 1.$$ (Note that if the original proposition was true, you now get a false one, and vice versa.)

Conjunctive Normal Form

1. Write a logical formula in Conjuctive Normal Form that is equivalent to: $$(A \vee B) \implies C$$

2. Write a logical formula in 3CNF form that is equivalent to: $$ A \vee \overline{B} \vee C \vee (\overline{D} \wedge E)$$ Use as few clauses as possible.

3. A circuit can be converted to a SAT formula by assigning a variable label to each wire in the circuit, and using clauses to constrain the variable values according to the circuit’s logic. Consider a single \smallcaps{AND} gate circuit shown below with inputs labeled $a_1$ and $a_2$ and output labeled $x_1$. Logically, this means $x_1 = a_1 \wedge a_2$ (but we can’t have an equality constraint like this in a SAT formula). Write a 3CNF formula that represents the AND gate shown below.

\begin{center} \begin{circuitikz} \draw (0,2) nodeand port {} (myand.in 1) nodeabove left=.5cm {$a_1$} (myand.in 2) nodebelow left = .5cm {$a_2$} (myand.out) noderight = .1cm {$x_1$} (a) -| (myand.in 1) (b) -| (myand.in 2); \end{circuitikz} \end{center}

Logical Equivalences

Determine if the following statements are logically equivalent, and support your answer with a clear, convincing, and concise proof.

1. $Q \implies (P \implies R) \qquad \textrm{and} \qquad \neg P \vee \neg Q \vee R$

2. $Q \implies (P \implies R) \qquad \textrm{and} \qquad (Q \implies P) \implies R$

Satisfaction

The length of the 3CNF formula is the number of clauses, and no clause may be repeated. (The order of literals within a clause doesn’t matter, so the clauses $(x_1 \vee x_2 \vee x_3)$ and $(x_3 \vee x_1 \vee x_2)$ would count as the same clauses, but $(x_1 \vee x_2 \vee x_3)$ and $(\overline{x_1} \vee x_2 \vee x_3$ are different clauses.)

1. What is the length of the shortest unsatisfiable 3CNF formula involving 3 variables? (That is, each clause involves $x_1$, $x_2$, and $x_3$, and your goal is to show that there exists an unsatisfiable formula of length $l$, and any formula of length $< l$ is satisfiable.)

2. ($\star$) What is the maximum number of clauses in any satisfiable 3CNF formula using $v$ variables? An outstanding answer would include a convincing proof (hint: well-ordering principle!) that there exists a satisfiable formula with $v$ variables of $l$ clauses, but no satisfiable formula with $v$ variables and $l + 1$ clauses exist.