cs2102
Discrete Mathematics
This is a preserved file from cs2102 Fall 2016. An updated version may exist at https://uvacs2102.github.io/

Problem Set 3

\dbox{{\bf Deliverable:} Submit your responses as a single PDF file on the collab site before {\bf 6:29pm} on {\bf Friday, 16 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 or Word).}

Deliverable: Submit your responses as a single PDF file on the collab site before 6:29pm on Friday, 16 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 or Word).

Collaboration Policy - Read Carefully

For this assignment, you should work in groups of one to four students of your choice. The only constraint on teams for PS3 is that you may not work with anyone with you you worked on both PS1 and PS2 (that is, the intersection of the sets of teammates you had for PS1, PS2, and PS3 should be empty).

The rest of the collaboration policy is identical to what it was on PS2, and is not repeated here.

Preparation

This problem set focuses on Chapter 3 (especially 3.4-3.6) of the MCS book, and Class 5 and Class 6 (which include some material not in Chapter 3).

Download PDF for Problems.

Your response should be submitted as a single PDF file using collab.

Directions

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

Quantified Formulas

For each pair of logical formula given, state if the the formula is valid and if it is satisfiable. You should provide a brief argument supporting your answer (enough to convince a reader you are not just guessing!), but do not need to provide a thorough proof.

$\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 \forall y \in \mathbb{N} \ldotp \exists z \in \mathbb{N}\ldotp z = x + y$.

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

  4. $\forall F \in \textrm{CNF}\ldotp \exists G \in \textrm{3CNF}\ldotp F \equiv G.$ (This means $F$ and $G$ are logically equivalent.)

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.

\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}

SAT Solving

For each of the formula, either (1) give a satisfying assignment, or (2) state that it is not satisfiable. (If you follow a smart strategy, these can be solved by hand without a lot of tedious effort. But, you are welcome to use SAT solving programs to solve them, including the simple-sat solver from Class 6.)

  1. $(x_1 \vee x_2 \vee \overline{x_3}) \wedge (x_1 \vee \overline{x_2} \vee x_3) \wedge (x_1 \vee \overline{x_2} \vee \overline{x_3}) \wedge (x_1 \vee x_2 \vee \overline{x_4}) \wedge (x_1 \vee \overline{x_2} \vee x_4)$

  2. $(x1 \vee x2 \vee x3) \wedge (x1 \vee x2 \vee \overline{x3}) \wedge (x1 \vee \overline{x2} \vee x3) \wedge (x1 \vee \overline{x2} \vee \overline{x3}) \wedge
    (\overline{x1} \vee x2 \vee x3) \wedge (\overline{x1} \vee x2 \vee \overline{x3}) \wedge (\overline{x1} \vee \overline{x2} \vee x3) \wedge (\overline{x1} \vee \overline{x2} \vee \overline{x3})$

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 length of the longest 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 length $l$, but no satisfiable formula with $v$ variables of length $l + 1$.