Class 5: CNF, Computing, Quantifiers

### Schedule

**Problem Set 2** is due **Friday at 6:29pm**.

**Challenge Problem Opportunity.**Find the shortest formula that is equivalent to XOR(

*a*,

*b*) using just NAND operations. Shortest means the minimum number of NAND operations. A convincing answer would include a proof that no shorter formula exists.

## Links

If you want to learn more about how to learn the logic implemented by a chip
and cryptosystems used in car immobolizers, see *Reverse-Engineering a
Cryptographic RFID
Tag* (Karsten
Nohl, David Evans, Starbug, and Henryk Plötz, *USENIX Security
Symposium* 2008), or this
video. Please don’t steal any
cars.

# Notes and Questions

**Definition: satisfiable.** A logical formula is *satisfiable* if there
is *some* way to make it **true**. That is, there is at least one
assignment of truth value to its variables that makes the forumla
true.

**Definition: conjunctive normal form (CNF).** A logical formula that is
written as a conjunction of *clauses*, where each clause is a
disjunction of *literals*, and each literal is either a variable or a
negation of a variable, is in *conjunctive normal form*. If each
clause has excatly three literals, it is called *three conjunctive
normal form* (3CNF).

$$ (a_1 \vee a_2 \vee \neg a_3) \wedge (a_1 \vee \neg a_2 \vee a_3) \wedge (\neg a_1 \vee a_2 \vee \neg a_3) \wedge (\neg a_1 \vee a_2 \vee a_3) $$

##

Show that every logical formula can be written in conjunctive normal form.
Also, show that if we only care about *satisfiability* we can always write it
in 3CNF form. Namely, for every CNF formula $F$, we can write a 3CNF formula
$G$ such that $F$ is satisfiable if and only if $G$ is satisfiable.

What is the maximum number of (different) clauses in a 3CNF formula involving 5 variables?

##

What is the maximum number of (different) clauses in a *satisfiable*
3CNF formula involving 5 variables?

##

What is the maximum number of (different) clauses in a *valid* 3CNF formula involving 5 variables?

##

## Logical Quantifiers

$\forall x \in S. P(x)$ means $P$ holds for *every* element of $S$.

$\exists x \in S. P(x)$ means $P$ holds for *at least one* element of $S$.

Define *valid* and *satisfiable* using logical quantifiers:

#

$\forall x \in S. P(x)$ is equivalent to $\neg(\exists x \in S. \qquad \qquad)$

###

Notation: $\textrm{pow}(S)$ denotes the *powerset* of $S$. The powerset
of a set is the set of all possible subsets of that S. So,
$\textrm{pow}(\mathbb{N})$ denotes all subsets of the natural numbers.

Notation: $A - B$ denotes the *difference* between two sets. It is the
elements of $A$, with every element of $B$ removed.

Notation: $\varnothing$ is the *empty set*. It is the set with no elements: ${ }$.

\begin{center} \Large

$$ \fillin S \in \textrm{pow}(\mathbb{N}) - { \varnothing } \ldotp \fillin m \in S\ldotp \fillin x \in S - {m}\ldotp m < x $$ \end{center}