Class 5: CNF, Computing, Quantifiers
Schedule
Problem Set 2 is due Friday at 6:29pm.
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}