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:

- Show $P(x)$ is true for all $x \in D$ that are defined using base cases.
- 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**.

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

- $q = (y, z)$. $P(q = (y, z))$: $y = a^{b-z}$.
- 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$.
- 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 (x*i, 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:

- Base case: $P(\fillin)$
- $\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:

- $x_0 = q_0$ (it begins with the start state), and
- $\forall i \in {0, 1, \ldots, n - 1} \ldotp (x
*i, 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)

Mohammad Mahmoody (Rice 511), 10:45-11:45am

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:

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

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

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”.

To prove by contradiction, assume $\neg G$ (that is, $\mathbb{Z}$ does have a minimum).

Then, $\exists m \in \mathbb{Z}$ that is the minimum of $\mathbb{Z}$.

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.

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