cs2102: Discrete Math

Problem Set 4 (Sat, 16 Sep 2017)

**Problem Set 4** [PDF] is now posted and
is due **Friday, 22 September at 6:29:00pm**.

Class 8: Sequences, Relations, Functions (Thu, 14 Sep 2017)

### Schedule

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

# Sequences

A **sequence** is a mathematical datatype that bears similarities to sets. A sequence $S$ also contains some elements, but we usually refer to them as *components*. There are two major differences between sets and sequences:

Components of a sequence are

**ordered**. There is either $0$, or $1$ or $2$, or … $n$ components, when the sequence if*finite*or it could be an infinite sequence that has an $i$‘th component for any non-zero natural number $i$.Different components of a sequence could be equal. For example $(a,b,a)$ has $a$ repeating, and this is a different sequence compared to $(a,b,b)$ even though they both have 3 componetns. If we interprete them as

*sets*, then they will be equal sets with $2$ elements each.

# Cartesian Product

We can use set products to get new sets whose elements are sequences. Cartesian product is a very useful way of doing it.

**Set Products.** A *Cartesian product* of sets $S_1, S_2, \cdots, S_n$
is a set consisting of all possible sequences of $n$ elements where the
$i$\textsuperscript{th} element is chosen from $S_i$.

$$ S_1 \times S_2 \times \cdots \times S_n = { (s_1, s_2, \cdots, s_n) | s_i \in S_i } $$

How many elements are in $A \times B$?

# Relations and Binary Relations

A *relation* between some elements from set $A$ and some elements from set $B$ could be represented by putting all such pairs $(a,b)$ in a set $P$. As you can see, this way, $P$ would be a subset of the cartesian product $A \times B$, namely $P \subseteq A \times B$. More formally we have the following definition.

A **binary relation**, $P$, is defined with respect to a *domain* set, $A$, and a
*codomain* set, $B$, and it holds that $P$ is $P \subseteq A \times B$. When we draw $P$ by connecting elements of $A$ to $B$ based on their membership in $P$, we call this the *graph* of
$R$.

The notion of relations could be generalized to having relations
between elements coming from multiple sets $A,B,C$, and we can also
talk about relations of the form $P \subseteq A \times B \times C$,
but the binary relation remains a very important data type as it
allows us to define *functions*.

# Functions

The concept of a function $F$ models is a special form of a binary
relation $R$ between $A$ and $B$ where for every element $a \in A$
there is *at most one* element in $b \in B$ that is in relation with
$a$ (i.e. $(a,b) \in R$). More formally, we use a direct new notation
just reserved for working with functions.

A **function** is a mathematical datatype that associates
elements from one set, called the *domain*, with elements from another
set, called a *codomain*.

$$ f: \textrm{\em domain} \rightarrow \textrm{\em codomain} $$

**Defining a function.** To define a function, we need to describe how
elements in the domain are associated with elements in the codomain.

#

What are the (sensible) domains and codomains of each function below:

$$ f(n) ::= |n| \qquad \qquad f(x) ::= x^2 \qquad\qquad f(n) ::= n + 1 \qquad\qquad f(a, b) ::= a / b $$

$$ f(x) ::= \sqrt{x} \qquad \qquad \qquad f(S) ::= \textrm{minimum}_{<}(S) $$

Problem Set 2 Comments (Wed, 13 Sep 2017)

The Problem Set 2 solutions and comments are now posted in collab: PDF

Class 7: Sets (Tue, 12 Sep 2017)

### Schedule

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

# Notes and Questions

What is a *data type*? What are the differences between a *mathematical
data type* and a data type in your favorite programming language?

#

A **set** is an unordered colection of objects. A set is defined by its
membership operation: $x \in S$ is true if $x$ is in the set $S$. When $x$ is not in $S$ we write it as $x \notin S$. A set has only *one* copy of each element. Namely, there is no repetition in elements of a set. Also, a set $A$ could be a member o another set $B$, denoted by $A \in B$. Note that members of $A$ are not necessarily members of $B$ unless they are explicitly put in $B$ directly.

## Set Operations

Subset: $\subseteq$ (note that this does not mean *strict subset*)
$$A \subseteq B \iff \forall x \in A. \fillin \in \fillin.$$

Set Equality: $=$ $$A = B \iff A \fillin B \wedge B \fillin A.$$

Set Union: $\cup$ $$\forall x. x \in A \cup B \iff x \in A \fillin x \in B.$$

Set Intersection: $\cap$ $$\forall x. x \in A \cap B \iff x \in A \fillin x \in B.$$

Set Difference: $-$ $$\forall x. x \in A - B \iff x \in A \wedge x \notin B.$$

Set Complement: $\overline{S}$ $$ \forall x \in D. x \in \overline{A} \iff x \notin A.$$

($D$ is the ``domain of discourse”, the universe of all objects under discussion.)

### Russell’s Paradox

$$ S_{R} = \textrm{ the set of all sets that are not members of themselves} $$

Is $S*{R} \in S*{R}$?

What is the source of this paradox? Note that in this question, we are implicitly assuming that $S*{R}$ is a set, but we have never “constructed” this set properly to use it. Namely, here we are implicitly assuming that there is already a “set of all sets” $S*{all}$ from which we remove those sets like $T$ for which $T \in T$. By removing all such $T$ from $S_{all}$ we get the set $S_R$.

### Using Quantifiers More Carefully

Note that in some of the propositions that we used to define the set operations (such as union, intersection, etc.) above, we wrote quantified $x$ without saying which set it is from. For example $\forall x. [\dots]$. It is much preferred to always say what $x$ is belonging to when we quantify over $x$. The reason is to avoid traps like that of Russell’s paradox! This should not worry us in this class, as we will always work with well-defined *universes* that include all the elements of the sets that we work with. Therefore, we can always assume implicitly that $x \in U$ (for a well defined set universe $U$) even if not explicitly mentioned.

#

### Set Practice

Here are some practice problems involving sets. We won’t go through these in class, but you should ask questions about any are unclear. (At least a few of these will be on Exam 1.)

- Define $A \subset B$ (strict subset).

#

- Prove $A \cup B \equiv B \cup A$.

#

- Prove $A - B = \emptyset \iff A \subseteq B$.

#

- Prove $A = B \iff (\forall a \in A \ldotp a \in B) \wedge (\forall b \in B \ldotp b \in A).$

Problem Set 3 (Fri, 8 Sep 2017)

**Problem Set 3** [PDF] is now posted and
is due **Friday, 15 September at 6:29:00pm**.

Class 6: Quantifiers and More (Thu, 7 Sep 2017)

### Schedule

Everyone should have received their graded PS1 by now. Please read the comments posted in collab.

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

You should finish reading MCS Chapter 3 by Tuesday (12 September).

## Links

If you believe real computing systems have the property that the values you read from memory will match what you wrote there, see:

Sudhakar Govindavajhala and Andrew W. Appel. *Using Memory Errors to Attack a Virtual Machine*, IEEE Symposium on Security and Privacy 2003.

Bianca Schroeder, Eduardo Pinheiro, Wolf-Dietrich Weber. *DRAM Errors
in the Wild: A Large-Scale Field
Study*. SIGMETRICS 2009.

Kaveh Razavi, Ben Gras, Erik Bosman, Bart Preneel, Cristiano Giuffrida
and Herbert Bos. *Flip Feng Shui: Hammering a Needle in the Software
Stack*. USENIX
Security 2016.

Yuan Xiao, Xiaokuan Zhang, Yinqian Zhang, and Radu Teodorescu. *One Bit Flips, One Cloud Flops: Cross-VM Row Hammer Attacks and Privilege Escalation*, USENIX Security 2016.

Sahand Saba’s *Understanding SAT by Implementing a Simple SAT Solver in
Python* [Code with Dave’s modifications: https://github.com/evansuva/simple-sat]

Millennium Problems on Clay institute’s
website. Whether or not we can

solve the *satisfiability* of a given CNF or 3CNF formula in polynomial time,
is the P vs. NP question in this list.

# Programs and Proofs

What does it mean to *test* a computing system? What does it mean for a computing system to *always behave correctly*?

Can a mathematical proof guarantee a real computing system will behave correctly?

# Minima

The *minimum* of a set with respect to some comparator operator is the
element which is “less than” (according to that comparator) every
other element: $m \in S$ is the *minimum* of $S$ if and only if
$\forall x \in S - { m } . m \prec x$.

$$ \forall S \in \textrm{pow}(\mathbb{N}) - { \varnothing } \ldotp \exists m \in S\ldotp \forall x \in S - {m}\ldotp m < x $$

# Formulas, Propositions, and Inference Rules

$P \implies Q$ is a *formula*.

$\forall P \in { T, F } . \forall Q \in { T, F } . P \implies Q$ is a *proposition*.

$\infer{Q}{P}$ is an *inference rule*.

A *formula* is *satisfiable* if there is some way to make it true.

$P \implies Q$ is satisfiable:

$\exists P \in { T, F } . \exists Q \in {T, F } . P \implies Q$

We can show a formula is satisfiable by giving *one* choice for the
variable assignments that makes it true. For example, $P = T$, $Q =
T$.

A *formula* is *valid* if there is no way to make it false.

$P \implies Q$ is *not* valid:

$\forall P \in { T, F } . \forall Q \in {T, F } . P \implies Q$

This proposition is false, we can chose $P = T$, $Q = F$.

An *inference rule* is sound if it never leads to a false conclusion. An inference rule
$\infer{Q}{P}$ is sound if and only if the formula
$P \implies Q$ is valid. So, this way, we can find out whether an inference rule is sound or not, by checking out whether the corresponding formula is valid or not.

# Negating Quantifiers

What is the negation of $\forall x \in S . P(x)$?

What is the negation of $\exists x \in S . P(x)$?

# Satisfiability

**Definition.** A formula is in *SAT* if it is in CNF form and it is
satisfiable.

**Definition.** A formula is in *3SAT* if it is in 3CNF form and it is
satisfiable.

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

\begin{center} \tiny \begin{math} (x*{48} \vee x*{4} \vee \overline{x*{9}})
\wedge (\overline{x*{44}} \vee x*{50} \vee \overline{x*{37}}) \wedge
(\overline{x*{8}} \vee \overline{x*{1}} \vee x*{28}) \wedge (x*{21} \vee
x*{27} \vee \overline{x*{32}}) \wedge (x*{17} \vee x*{29} \vee
\overline{x*{30}}) \wedge (x*{30} \vee x*{24} \vee x*{37}) \wedge
(\overline{x*{22}} \vee \overline{x*{27}} \vee \overline{x*{44}}) \wedge
(x*{8} \vee \overline{x*{25}} \vee \overline{x*{24}}) \wedge
(\overline{x*{44}} \vee x*{50} \vee x*{14}) \wedge (x*{45} \vee x*{15} \vee
x*{37}) \wedge (\overline{x*{16}} \vee x*{14} \vee \overline{x*{36}}) \wedge
(\overline{x*{33}} \vee x*{5} \vee x*{26}) \wedge (x*{18} \vee
\overline{x*{7}} \vee \overline{x*{24}}) \wedge (x*{31} \vee x*{38} \vee
x*{28}) \wedge (x*{31} \vee \overline{x*{33}} \vee \overline{x*{8}}) \wedge
(x*{49} \vee x*{7} \vee \overline{x*{6}}) \wedge (x*{34} \vee
\overline{x*{8}} \vee x*{46}) \wedge (x*{4} \vee \overline{x*{5}} \vee
\overline{x*{35}}) \wedge (x*{43} \vee x*{27} \vee x*{39}) \wedge
(\overline{x*{46}} \vee \overline{x*{40}} \vee \overline{x*{27}}) \wedge
(\overline{x*{25}} \vee x*{14} \vee \overline{x*{49}}) \wedge (x*{38} \vee
x*{5} \vee x*{15}) \wedge (x*{9} \vee x*{14} \vee \overline{x*{19}}) \wedge
(x*{45} \vee \overline{x*{42}} \vee \overline{x*{39}}) \wedge (x*{34} \vee
\overline{x*{22}} \vee \overline{x*{28}}) \wedge (\overline{x*{20}} \vee
x*{15} \vee \overline{x*{8}}) \wedge (\overline{x*{44}} \vee
\overline{x*{10}} \vee \overline{x*{9}}) \wedge (x*{22} \vee
\overline{x*{31}} \vee x*{14}) \wedge (\overline{x*{9}} \vee
\overline{x*{42}} \vee \overline{x*{15}}) \wedge (\overline{x*{40}} \vee
x*{12} \vee \overline{x*{32}}) \wedge (\overline{x*{20}} \vee
\overline{x*{6}} \vee \overline{x*{15}}) \wedge (\overline{x*{37}} \vee
x*{39} \vee \overline{x*{23}}) \wedge (\overline{x*{3}} \vee
\overline{x*{40}} \vee \overline{x*{32}}) \wedge (\overline{x*{4}} \vee
\overline{x*{25}} \vee x*{7}) \wedge (\overline{x*{20}} \vee
\overline{x*{36}} \vee \overline{x*{37}}) \wedge (\overline{x*{40}} \vee
\overline{x*{35}} \vee x*{39}) \wedge (\overline{x*{43}} \vee
\overline{x*{40}} \vee \overline{x*{7}}) \wedge (x*{34} \vee x*{44} \vee
x*{26}) \wedge (x*{13} \vee x*{27} \vee x*{28}) \wedge (x*{12} \vee
\overline{x*{36}} \vee x*{7}) \wedge (\overline{x*{16}} \vee x*{9} \vee
\overline{x*{24}}) \wedge (\overline{x*{48}} \vee x*{14} \vee x*{28}) \wedge
(x*{16} \vee x*{4} \vee x*{40}) \wedge (\overline{x*{25}} \vee x*{15} \vee
x*{37}) \wedge (x*{47} \vee \overline{x*{26}} \vee \overline{x*{23}}) \wedge
(x*{4} \vee \overline{x*{13}} \vee x*{36}) \wedge (x*{48} \vee
\overline{x*{13}} \vee \overline{x*{37}}) \wedge (x*{4} \vee x*{35} \vee
\overline{x*{27}}) \wedge (\overline{x*{22}} \vee x*{47} \vee x*{26}) \wedge
(\overline{x*{22}} \vee \overline{x*{46}} \vee x*{27}) \wedge
(\overline{x*{20}} \vee x*{49} \vee x*{11}) \wedge (x*{42} \vee
\overline{x*{10}} \vee x*{28}) \wedge (\overline{x*{45}} \vee x*{28} \vee
\overline{x*{37}}) \wedge (x*{14} \vee \overline{x*{32}} \vee
\overline{x*{23}}) \wedge (x*{22} \vee x*{14} \vee x*{23}) \wedge
(\overline{x*{17}} \vee \overline{x*{46}} \vee \overline{x*{7}}) \wedge
(\overline{x*{31}} \vee x*{46} \vee \overline{x*{50}}) \wedge (x*{34} \vee
\overline{x*{41}} \vee x*{43}) \wedge (x*{17} \vee \overline{x*{9}} \vee
x*{15}) \wedge (x*{46} \vee x*{14} \vee \overline{x*{12}}) \wedge
(\overline{x*{20}} \vee x*{12} \vee x*{14}) \wedge (x*{41} \vee x*{42} \vee
\overline{x*{15}}) \wedge (x*{48} \vee x*{46} \vee \overline{x*{36}}) \wedge
(\overline{x*{22}} \vee \overline{x*{4}} \vee \overline{x*{49}}) \wedge
(x*{22} \vee x*{12} \vee \overline{x*{42}}) \wedge (x*{13} \vee
\overline{x*{38}} \vee x*{39}) \wedge (x*{48} \vee \overline{x*{16}} \vee
\overline{x*{27}}) \wedge (x*{17} \vee \overline{x*{18}} \vee
\overline{x*{26}}) \wedge (x*{48} \vee \overline{x*{40}} \vee
\overline{x*{35}}) \wedge (\overline{x*{43}} \vee \overline{x*{40}} \vee
\overline{x*{49}}) \wedge (x*{29} \vee x*{11} \vee \overline{x*{32}}) \wedge
(x*{33} \vee \overline{x*{17}} \vee x*{39}) \wedge (\overline{x*{25}} \vee
\overline{x*{9}} \vee \overline{x*{6}}) \wedge (x*{40} \vee \overline{x*{50}}
\vee x*{19}) \wedge (x*{8} \vee x*{10} \vee \overline{x*{27}}) \wedge (x*{5}
\vee x*{9} \vee \overline{x*{26}}) \wedge (x*{45} \vee \overline{x*{38}} \vee
\overline{x*{27}}) \wedge (\overline{x*{4}} \vee \overline{x*{40}} \vee
\overline{x*{42}}) \wedge (x*{21} \vee x*{50} \vee x*{12}) \wedge
(\overline{x*{8}} \vee \overline{x*{14}} \vee \overline{x*{42}}) \wedge
(\overline{x*{17}} \vee x*{47} \vee \overline{x*{27}}) \wedge (x*{49} \vee
\overline{x*{12}} \vee \overline{x*{6}}) \wedge (x*{27} \vee x*{49} \vee
\overline{x*{32}}) \wedge (\overline{x*{29}} \vee \overline{x*{12}} \vee
\overline{x*{26}}) \wedge (x*{48} \vee \overline{x*{2}} \vee x*{6}) \wedge
(x*{16} \vee x*{36} \vee x*{49}) \wedge (x*{33} \vee \overline{x*{12}} \vee
\overline{x*{26}}) \wedge (\overline{x*{33}} \vee x*{29} \vee x*{49}) \wedge
(\overline{x*{48}} \vee x*{2} \vee x*{19}) \wedge (x*{25} \vee x*{36} \vee
x*{49}) \wedge (x*{21} \vee x*{40} \vee \overline{x*{14}}) \wedge
(\overline{x*{34}} \vee \overline{x*{44}} \vee \overline{x*{6}}) \wedge
(x*{48} \vee \overline{x*{50}} \vee \overline{x*{1}}) \wedge (x*{5} \vee
\overline{x*{12}} \vee x*{7}) \wedge (x*{21} \vee \overline{x*{35}} \vee
\overline{x*{27}}) \wedge (\overline{x*{22}} \vee \overline{x*{16}} \vee
\overline{x*{14}}) \wedge (\overline{x*{13}} \vee \overline{x*{35}} \vee
\overline{x*{12}}) \wedge (\overline{x*{4}} \vee \overline{x*{35}} \vee
\overline{x*{42}}) \wedge (\overline{x*{50}} \vee \overline{x*{40}} \vee
x*{7}) \wedge (x*{25} \vee x*{47} \vee \overline{x*{12}}) \end{math}
\end{center}

## Converting Truth Tables to DNF

\begin{tabular}{cc|cc}
$P$ & $Q$ & $P \implies Q$ & $P \oplus Q$ \ \hline
\T & \T & \T & \F

\T & \F & \F & \T

\F & \T & \T & \T

\F & \F & \T & \F

\end{tabular}

The output of the operator is \T\ if and only if the inputs do match *one row* where the output is \T. So, to get a DNF we can go over all the rows where hte output is \T, and for each write a clause that means we *are* in that row. Then we OR all such (conjunctive) clauses. For example, for $P \oplus Q$ we get

$$(P \wedge \neg Q) \vee (\neg P \wedge Q)$$

## Converting Truth Tables to CNF

\begin{tabular}{cc|cc}
$P$ & $Q$ & $P \implies Q$ & $P \oplus Q$ \ \hline
\T & \T & \T & \F

\T & \F & \F & \T

\F & \T & \T & \T

\F & \F & \T & \F

\end{tabular}

The output of the operator is \T\ if and only if the inputs do not match *any row* where the output is \F. So, to get a CNF we can go over all the rows where hte output is \F, and for each write a clause that means we are *not* in that row. Then we AND all such clauses. For example, for $P \oplus Q$ we get

$$(\neg P \vee \neg Q) \wedge (P \vee Q)$$

## The related 3CNF formulation

When we are only interested to know whether or not a given formula is satisfiable, we can write a 3CNF that is satisfiable iff the original formula is. In order to do that, we first write an equivalent CNF, and then convert it to a 3CNF (which is not necessarily equivalent, but only guarantees to preserve the *satisfiability* feature) as follow. For each clause with less than 3 literals such as $(A \lor \neg B)$ we add a dummy variable $C$ (only for this clause) and interprete the $(A \lor \neg B)$ as a formula over all of $A,B,C$ and write a CNF for them (which happens to be 3CNF!). For longer clauses such as
$(A \lor B \lor C \lor D)$ we do another trick of breaking them into smaller parts using new dummy variables as follows $(A \lor B \lor \neg X) \wedge (\neg X \lor C \lor D).$

Problem Set 1 Comments (Wed, 6 Sep 2017)

The Problem Set 1 comments are now posted in collab: PDF

Class 5: CNF, Computing, Quantifiers (Tue, 5 Sep 2017)

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

Problem Set 2 (Fri, 1 Sep 2017)

**Problem Set 2** [PDF] is now posted and
is due **Friday, 8 September at 6:29:00pm**.

Additional Resources (Thu, 31 Aug 2017)

I’ve added a page, Resources, with links to some suggested resources beyond the course materials. If you find other useful resources, please post them in slack and we’ll add them to this list.