cs2102: Discrete Math

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.

Class 4: Logical Operators and Formulas (Thu, 31 Aug 2017)

### Schedule

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

Next week, we will cover the rest of Chapter 3 (Satisfiability and Quantifiers).

## Links

Scott Brown, *The Life and Work of Augustus De Morgan*. Applied Probability 2006.

Ada’s Correspondence with De Morgan (Clay Mathematics Institute)

# Notes and Questions

## Well-Ordering Principle Proof

**Odd Summation.** (Problem 2.12) Prove that for all $n > 0$, the sum of the first $n$ odd numbers is $n^2$.

Class 3: Well-Ordering Principle (Tue, 29 Aug 2017)

### Schedule

This week, you should read MCS Chapter 2 and MCS Chapter 3 (at least through the end of Section 3.4).

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

Office hours started Monday afternoon. See the course calendar for the full office hours schedule.

## Links

*The Well-Ordering Theorem: one of the Greatest Mathematical Controversies of All Time*, Kathryn Mann.

# Notes and Questions

What properties must a sensible ordering function have?

**Definition.** A set is *ordered* with respect to an ordering
relation (e.g., $<$), if two things hold. (1) Every pair of inequal
elements $a,b$ in $A$ either satisfy $a<b$ or $b<a$. (2) for every
three elements $a$, $b$, and $c$, $a < b$ and $b < c$ imply that $a <
c$ (this is called *transitivity*).

**Definition.** An ordered set,with respect to an ordering
relation (e.g., $<$), is *well-ordered* if all of its non-empty subsets has a minimum
element.

Which of these are well-ordered?

- The set of non-negative integers, comparator $<$.
- The set of integers, comparator $<$.
- The set of integers, comparator $|a| < |b|$.
- The set of integers, comparator if |a| = |b|: $a < b$, else: $|a| < |b|$.
- The set of national soccer teams, comparator winning games.

Prove the set of positive rationals is *not* well-ordered under $<$.

#

Provide a comparison function that can be used to well-order the positive rationals.

### Template for Well-Ordering Proofs (Section 2.2)

To prove that $P(n)$ is true for all $n \in \mathbb{N}$:

- Define the set of counterexamples, $C ::= { n \in \mathbb{N} | NOT(P(n)) }$.
- Assume for contradiction that $C$ is ______________.
- By the well-ordering principle, there must be __________________ , $m \in C$.
- Reach a contradiction (this is the creative part!). One way to reach a contradiction would be to show $P(m)$. Another way is to show there must be an element $m’ \in C$ where $m’ < m$.
- Conclude that $C$ must be empty, hence there are no counter-examples and $P(n)$ always holds.

**Example: Betable Numbers.** A number is *betable* if it can be
produced using some combination of \$2 and \$5 chips. Prove that all
integer values greater than \$3 are betable.