Discrete Mathematics

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:

  1. 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$.

  2. 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.)

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

#

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

#

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

#

  1. 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).

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]

SAT Competition 2017

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)$$

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.

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.