Discrete Mathematics

# cs2102: Discrete Math

Problem Set 7 (Fri, 20 Oct 2017)

Problem Set 7 [PDF] is now posted and is due Friday, 27 Oct at 6:29:00pm. Please read the collaboration policy carefully.

Class 16: Structural Induction (Thu, 19 Oct 2017)

### Schedule

Problem Set 6 is due tomorrow at 6:29pm. Make sure to read the corrected version of Problem 7.

# Lists

Definition. A list is an ordered sequence of objects. A list is either the empty list ($\lambda$), or the result of $\text{prepend}(e, l)$ for some object $e$ and list $l$.

\begin{equation} \begin{split} \text{\em first}(\text{prepend}(e, l)) &= e \ \text{\em rest}(\text{prepend}(e, l)) &= l \ \text{\em empty}(\text{prepend}(e, l)) &= \text{\bf False} \ \text{\em empty}(\text{\bf null}) &= \text{\bf True} \ \end{split} \end{equation}

Definition. The length of a list, $p$, is: \begin{equation} \begin{split} \begin{cases} 0 & \text{if}\ p\ \text{is \bf null} \ \text{\em length}(q) + 1 & \text{otherwise}\ p = \text{\em prepend}(e, q)\ \text{for some object}\ e\ \text{and some list}\ q \ \end{cases} \end{split} \end{equation}

def list_length(l):
if list_empty(l):
return 0
else:
return 1 + list_length(list_rest(l))



Prove: for all lists, $p$, list_length(p) returns the length of the list $p$.

## Concatenation

Definition. The concatenation of two lists, $p = (p_1, p_2, \cdots, p_n)$ and $q = (q_1, q_2, \cdots, q_m)$ is $$(p_1, p_2, \cdots, p_n, q_1, q_2, \cdots, q_m).$$

Provide a constructuve definition of concatenation.

Note that $\text{prepend}(p,q)$ is not a good idea for two reasons. If we use this definition, then the first element of the constructed list will be the object (list) $p$ (as a whole) rather than the first element $p_1$ of the list $p$. Also, if we want to only define lists of specific objects, for example integers, we can still use the same recursive/constructive definition of lists by substituting “object” with “integer”, but in that case $\text{prepend}(p,q)$ will not even well defined, as it can only accept integers as first input.

#

## Structural Induction

To prove proposition $P(x)$ for element $x \in D$ where $D$ is a recursively-constructed data type, we do two things:

1. Show $P(x)$ is true for all $x \in D$ that are defined using base cases.
2. Show that if $P(y)$ is true for element $y$ and $x$ is constructed from $y$ using any “construct case” rules, then $P(x)$ is true as well.

## Comparing Various forms of Induction

\begin{center} \begin{tabular}{lccc} & {\bf Regular Induction} & {\bf Invariant Principle} & {\bf Structural Induction} \ \hline Works on: & natural numbers & state machines & data types \ To prove $P(\cdot)$ & {\em for all natural numbers} & {\em for all reachable states} & {\em for all data type objects} \ Prove {\bf base case(s)} & $P(0)$ & $P(q_0)$ & $P(\text{base object(s)})$ \ and {\bf inductive step} & $\forall m \in \mathbb{N} \ldotp$ & $\forall (q, r) \in G \ldotp$ & $\forall s \in \text{\em Type} \ldotp$ \ & $P(m) \implies P(m+1)$ & $P(q) \implies P®$ & $P(s) \implies P(t)$ \ & & & $\quad \forall t\ \text{constructable from}\ s$ \ \end{tabular} \end{center}

# ##

Prove. For any two lists, $p$ and $q$, $\text{length}(p + q) = \text{length}(p) + \text{length}(q)$.

#

Class 15: Recursive Data Types (Tue, 17 Oct 2017)

### Schedule

You should read MCS Chapter 7 this week.

Problem Set 6 is due 20 October (Friday) at 6:29pm.

Python code from class and list definitions: pairs.py

# Proving Correctness

def slow_power(a, b):
y = 1
z = b
while z > 0:
y = y * a
z = z - 1
return y


We model the Python program with a state machine:

$S ::= \mathbb{N} \times \mathbb{N}$
$G ::= { (y, z) \rightarrow (y \cdot a, z - 1) \, | \, \forall y, z \in \mathbb{N}^{+}}$
$q_0 ::= (1, b)$

It is important to remember this is a model. It does not capture many important aspects of execution of a real Python program. In particular, it only models inputs in $\mathbb{N}$, when the actual inputs could be other types in PYthon. It also assume all math opderations work mathematically, not Pythonically.

To prove partial correctness, we show $P(q = (y, z)) := y = a^{b-z}$ is a preserved invariant. Then, we show that it holds in state $q_0$. Finally, we show that in all final states, $y = a^b$.

Invariant is Preserved: We need to show that $\forall q \in S . \forall t \in S . (q, t) \in G \implies P(q) \implies P(t)$.

1. $q = (y, z)$. $P(q = (y, z))$: $y = a^{b-z}$.
2. If there is an edge from $q$ to $t$, that means $t = (y \cdot a, z-1)$ and $z \ge 1$ since this is the only edge from $q$ in $G$.
3. We show $P(t = (y \cdot a, z-1))$ holds by multiplying both sides of $P(q)$ by $a$: $$ya = (a^{b -z}) \cdot a = a^{b - z + 1} = a ^{b - (z - 1)}.$$

Invariant holds in $q_0$: $q_0 = (1, b)$. So, we need to show $P(q_0 = (1, b))$: $1 = a^{b - b}$. This holds since $a^{0} = 1$.

Final states: All states where $z \ge 1$ have an outgoing edge, but no states where $z = 0$ do. So, the final states are all of the form $(\alpha, 0)$. If a final state is reachable from $q_0$, the invariant must hold since we proved it is preserve. Hence, in the final state $(\alpha, 0)$ we know $\alpha = a^{b}$.

This proves partial correctness: if the program terminates, it terminates in a state where the property ($y = a^b$ is satisfied). To prove total correctness we also need to know the execution eventually reaches a final state.

We prove this by showing that from any initial state $q_0 = (1, b)$, the machine will reach a final state $q_f = (y, 0)$ in $b$ steps. The proof in class used the Well Ordering Principle. You could also prove this using regular Induction.

# Pairs

What is the difference between scalar data and compound data structures?

Definition. A $\text{\em Pair}$ is a datatype that supports these three operations:
\begin{quote} $\text{\em make_pair}: \text{\em Object} \times \text{\em Object} \rightarrow \text{\em Pair}$\ $\text{\em pair_first}: \text{\em Pair} \rightarrow \text{\em Object}$\
$\text{\em pair_last}: \text{\em Pair} \rightarrow \text{\em Object}$\
\end{quote} where, for any objects $a$ and $b$, $\text{\em pair_first}(\text{\em make_pair}(a, b)) = a$ and $\text{\em pair_last}(\text{\em make_pair}(a, b)) = b$.

def make_pair(a, b):
def selector(which):
if which:
return a
else:
return b
return selector

def pair_first(p):
return p(True)

def pair_last(p):
return p(False)


# Lists

Definition (1). A List is either (1) a Pair where the second part of the pair is a List, or (2) the empty list.

Definition (2). A List is a ordered sequence of objects.

Class 14: Invariant Principle (Thu, 12 Oct 2017)

### Schedule

Problem Set 6 is due 20 October (Friday) at 6:29pm.

Exam 1 was returned Tuesday. If you did not pick yours up yet, you can get it after class today. We will start charging exponentially-increasing storage fees for inexcusably unclaimed exams starting after Prof. Mahmoody’s office hours Monday.

## State Machines (review from Class 13)

A state machine, $M = (S, G: S \times S, q_0 \in S)$, is a binary relation (called a transition relation) on a set (both the domain and codomain are the same set). One state, denoted $q_0$, is designated as the start state.

An execution of a state machine $M = (S, G \subseteq S \times S, q_0 \in S)$ is a (possibly infinite) sequence of states, $(x_0, x_1, \cdots, x_n)$ where (1) $x_0 = q_0$ (it begins with the start state), and (2) $\forall i \in {0, 1, \ldots, n - 1} \ldotp (xi, x{i + 1}) \in G$ (if $q$ and $r$ are consecutive states in the sequence, then there is an edge $q \rightarrow r$ in $G$).

A state $q$ is reachable if it appears in some execution.

A preserved invariant of a state machine $M = (S, G \subseteq S \times S, q_0 \in S)$ is a predicate, $P$, on states, such that whenever $P(q)$ is true of a state $q$, and $q \rightarrow r \in G$, then $P®$ is true.

### Bishop State Machine

$S = { (\fillin ) \, | \, r, c \in \mathbb{N} }$ $G = { (r, c) \rightarrow (r’, c’) \, | \, r, c \in \mathbb{N} \wedge (\exists d \in \mathbb{N}^{+} \textrm{ such that } r’ = r \fillin d \wedge r’ \ge 0 \wedge c’ = c \fillin d \wedge c’ \ge 0 }$ $q_0 = (0, 2)$

What states are reachable?

#

### Progress” Machine

$S = { (x, d) \, | \, x \in \mathbb{Z}, d \in { \mathrm{\bf F}, \mathrm{\bf B}} }$ $G = { (x, \mathrm{\bf F}) \rightarrow (x + 1, \mathrm{\bf B}) \, | \, x \in \mathbb{Z} } \cup { (x, \mathrm{\bf B}) \rightarrow (x - 2, \mathrm{\bf F}) \, | \, x \in \mathbb{Z} }$ $q_0 = (0, \mathrm{\bf F})$

Which states are reachable?

## Preserved Invariants

A predicate $P(q)$ is a preserved invariant of machine $M = (S, G \subseteq S \times S, q_0 \in S)$ if: $$\forall q \in S \ldotp (P(q) \wedge (q \rightarrow r) \in G) \implies P®$$

What are some preserved invariants for the (original) Bishop State Machine?

Invariant Principle. If a preserved invariant of a state machine is true for the start state, it is true for all reachable states.

To show $P(q)$ for machine $M = (S, G \subseteq S \times S, q_0 \in S)$ all $q \in S$, show:

1. Base case: $P(\fillin)$
2. $\forall s \in S \ldotp \fillin \implies \fillin$

Prove that the original Bishop State Machine never reaches a square where $r + c$ is odd.

# Slow Exponentiation

def slow_power(a, b):
y = 1
z = b
while z > 0:
y = y * a
z = z - 1
return y


$S ::= \mathbb{N} \times \mathbb{N}$ $G ::= { (y, z) \rightarrow (y \cdot a, z - 1) \, | \, \forall y, z \in \mathbb{N}^{+}}$ $q_0 ::= (1, b)$

Prove slow_power(a, b) = $a^b$.

#

# Fast Exponentiation

This is the algorithm from Section 6.3.1 written as Python code:

def power(a, b):
x = a
y = 1
z = b
while z > 0:
r = z % 2 # remainder of z / 2
z = z // 2 # quotient of z / 2
if r == 1:
y = x * y
x = x * x
return y


Problem Set 6 (Thu, 12 Oct 2017)

Problem Set 6 [PDF] is now posted and is due Friday, 20 Oct at 6:29:00pm. Please read the collaboration policy carefully.

Class 13: State Machines (Tue, 10 Oct 2017)

### Schedule

There is no Problem Set due this week. Problem Set 6 will be posted soon and due next Friday (October 20) at 6:29pm.

Exam 1 was returned in class today. Please read the solutions posted in collab: Exam 1 Comments. If you didn’t pick up Exam 1 in class today, you can get it at Dave’s office hours tomorrow, or before or after class on Thursday.

## State Machines

A state machine is a binary relation (called a transition relation) on a set (both the domain and codomain are the same set). One state is designated as the start state.

$$M = (S, G: S \times S, q_0 \in S)$$

What does it mean if $G$ is total?

##

What does it mean if $G$ is not a function?

##

Parity Counter. Describe a state machine that determines if the number of steps is even.

#

Unbounded Counter. Describe a state machine that counts the number of steps.

#

How well do state machines model real computers? What kind of transition relation does the state machine modeling your computer have?

## State Machine Execution

An execution of a state machine $M = (S, G \subseteq S \times S, q_0 \in S)$ is a (possibly infinite) sequence of states, $(x_0, x_1, \cdots, x_n)$ where:

1. $x_0 = q_0$ (it begins with the start state), and
2. $\forall i \in {0, 1, \ldots, n - 1} \ldotp (xi, x{i + 1}) \in G$ (if $q$ and $r$ are consecutive states in the sequence, then there is an edge $q \rightarrow r$ in $G$)

A state $q$ is reachable if it appears in some execution. (That is, there is a sequence of transitions starting from $q_0$, following edges in $G$, that ends with $q$.)

$$M_1 = (S = \mathbb{N}, G = {(x, y) | y = x^2 }, q_0 = 1)$$ $$M_2 = (S = \mathbb{N}, G = {(x, y) | \exists k \in \mathbb{N} \ldotp y = kx }, q_0 = 1)$$

Which states are reachable for $M_1$ and $M_2$?

#

Fall Break Office Hours (Sun, 1 Oct 2017)

The office hours schedule for next week will be different from normal because of “Fall Break” and the Exam (as usual, all will be in Rice 436 except the professors’ as noted):

#### Monday (2 Oct)

Sarah Meng, 4:30-6:00pm

#### Tuesday (3 Oct)

Nate Olsen, 10-11:30am
Michael Woon, 11am-12:30pm
Henry Spece, 3:30-5pm

#### Wednesday (4 Oct)

Colin Harfst, 9:30am-12:30pm
Anna Wu, noon-1:30pm
Michael Woon, 12:30-2:00pm
David Evans (Rice 507), 2:30-3:30pm
Bhuvanesh Murali, 3-5pm
Helen Simecek, 3:30-5pm
Yasasvini Puligundle, 5-6pm
Xueying Bai, 6-7pm
Fan Feng, 7-8:30pm
Nate Olsen, 7:30-9:00pm

#### Thursday (5 Oct)

Amar Singh, 9am-10:30
Xiao Zhang, 10-11am
Prashant Gorthi, 11am-noon

No office hours Thursday afternnon and evening. The normal office hours schedule will resume on Monday, 9 October.

Problem Set 5 Comments (Sun, 1 Oct 2017)

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

Class 12: Review (Thu, 28 Sep 2017)

### Schedule

Problem Set 5 is due Friday at 6:29pm.

See Class 11 Notes for information and preparation advice for Exam 1, which will be in class next Thursday, 5 October.

## Strong Induction Principle

Let $P$ be a predicated on $\mathbb{N}$. If

• $P(0)$ is true, and
• $(\forall m \in \mathbb{N}, m \le n . P(n)) \implies P(n + 1)$ for all $n \in \mathbb{N}$,

then

• $P(m)$ is true for all $m \in \mathbb{N}$.

As an inference rule:

$$\infer{\forall m \in \mathbb{N} . P(m)}{P(0), \forall n \in \mathbb{N} . (P(0) \vee P(1) \wedge \cdots \wedge P(n)) \implies P(n + 1)}$$

With arbitrary basis, $b \in \mathbb{N}$:

$$\infer{\forall m \in { b, b+1, b+2, \ldots } . P(m)}{P(b), \forall n \in \mathbb{N} . (P(b) \vee P(b + 1) \wedge \cdots \wedge P(n)) \implies P(n + 1)}$$

Show that strong induction is not actually stronger than regular induction. (Hint: if the predicate for strong induction is $P(m)$, explain how to construct a predicate, $P’(m)$, that works with regular induction.)

##

### Example Strong Induction Proof

Theorem: Every number, $n \in \mathbb{N}, n \geq 4$ can be written as $\alpha \cdot 2 + \beta \cdot 5$ where $\alpha, \beta \in \mathbb{N}$.

Proof by Strong Induction:

1. First we need to define the predicate: $$P(n) := \exists \alpha, \beta \in \mathbb{N} . n = \alpha \cdot 2 + \beta \cdot 5$$.

2. Basis: we are proving for all $n > 3$:

$P(4)$: $\alpha = 2, \beta = 0$ gives $4 = 2 \cdot 2 + 0 \cdot 5$. $P(5)$: $\alpha = 0, \beta = 1$ gives $5 = 0 \cdot 2 + 1 \cdot 5$.

3. Induction step: $\forall n \in {6, \ldots }$

By strong induction, assume $P(m)$ is true for all $m \in { 4, 5, 6, \ldots, m}$.

Show $P(m + 1)$: Since $P(m - 1)$ is true (by the \emph{strong} induction hypothesis), we know $\exists \alpha, \beta \in \mathbb{N} . m - 1 = \alpha \cdot 2 + \beta \cdot 5$. We can show $P(m + 1)$ since $m + 1 = (\alpha + 1) \cdot 2 + \beta \cdot 5$.

## Proof by Contra-Positive (Review)

Recall: $P \implies Q$ is equivalent to $\neg Q \implies \neg P$. (If you are shaky on this, prove it to yourself using a truth table.)

Typical use: where the negation of the proposition is easier to reason about than the original proposition (e.g., irrational is a complex property to describe, but rational (NOT irrational) is a simple one. So to prove that If $r$ is irrational then $\sqrt{r}$ is also irrational” we can prove the contrapositive which is “if $\sqrt{r}$” is rational, then $r$ is also rational$which is quite straightforward. ## Proof by Contradiction (Review) To prove$P$, show$\neg P \implies False$. Example: Proving the$\mathbb{Z}$is not well ordered. Goal: proving the proposition$G$saying $\mathbb{Z}$has no minimum”. 1. To prove by contradiction, assume$\neg G$(that is,$\mathbb{Z}$does have a minimum). 2. Then,$\exists m \in \mathbb{Z}$that is the minimum of$\mathbb{Z}$. 3. But, this leads to a contradiction:$m - 1 \in \mathbb{Z}$and$m - 1 < m$. So, even though the number$m$was said to be the minimum of$\mathbb{Z}$, it is in fact not the minimum. 4. Thus, we have a contradiction, so something must be wrong. All our logical inferences after step 1 are correct, so the assumption we made in step 1 must be invalid. If$\neg G$is invalid,$G$must be true. Typical use: when the statment we want to prove has universal quantifier. for example,$\forall x \in \mathbb{Z}. P(x)$. Note that the statment that$\mathbb{Z}$has \emph{no} minimum, when written formally, uses a universal quantifier (make sure to double check it). Then, instead of arguing that for all$x \in A$,$P(x)$holds, we assume (for sake of contradiction) that there exists one$x$for which$\neg(P(x))$(note that this is indeed the negated statement) from which we get a contradiction. # Binary Relation Properties When we draw the graph of binary relations, the Domain (input" set) has outgoing edges. Codomain (output” set) has incoming edges. So when we use the compact notation referring to different properties of binary relations, keep in mind that the words in-out” refer to the edge (not the input/output sets). The properties about outgoing edges are function ($\le 1 out$) and total ($\ge 1$out). Adding elements to the codomain cannot effect these properties. The properties about incoming edges are surjection ($\ge 1$in) and injection ($\le 1$in). Adding elements to the domain cannot effect these properties. When we say the any relation with property$X$(e.g.,$\ge 1$out) about the relations \emph{must} also have propety$Y$. It means that property$X$implies$Y$logically (about relations). In case the answer is “no” (i.e. that property$X$does not imply$Y$) all we have to find is one relation$R$that satisfies property$X$but not property$Y$. If the answer is `yes’ we need to show that for all$R$, if property$X$holds, so does$Y\$. So doing so might need more work.

If an edge is added to the graph of a relation, which properties might be impacted?

If an edge is removed to the graph of a relation, which properties might be impacted?

If an element is removed from the domain of a relation, which properties might be impacted?

If an element is removed from the codomain of a relation, which properties might be impacted?

Problem Set 4 Comments (Wed, 27 Sep 2017)

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