cs2102: Discrete Math

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

Class 11: Induction Practice (Tue, 26 Sep 2017)

### Schedule

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

**Thursday’s Class** may include review for Exam 1. Before 6:59pm
Wednesday, send *uvacs2102staff@gmail.com* topics you would like to review:

- fewer than 10 total requests: class is not being sufficiently challenged and we should be doing more difficult material (except for the 10 requestors who get exam exemptions).
- exactly 10 total requests: all requestors get automatic exam exemptions, review requested topics.
- more than 10 requests implies we should spend Thursday’s class on reviewing requested topics, no exam exemptions.

### Exam 1

Exam 1 will be in class on Thursday, 5 October. You can get a good idea what to expect on Exam 1 by looking at the Practice Exam 1 (from last year’s class). We strongly encourage you to try to problems on your own, before looking at the posted solutions.

**Resources.** You will be permitted to use a *single paper page* of
notes that you prepare and bring to the exam. It is fine to
collaborate with others to prepare your notes. The page should be no
larger than a US Letter size page ($8.5 \times 11$ inches), and you
may write (or print) on both sides of the page. You may not use any
special devices (e.g., magnifying glasses) to read your page. No other
resources, other than your own brain, body, and writing instrument,
are permitted during the exam.

**Content.** The problems on the exam will cover material from Classes
1–11, Problem Sets 1–5 (including the provided solutions), and MCS
Chapters 1–5. Everything on the exam will be something you have seen
in at least two of these (Classes, Problem Sets, and MCS Book), and
most of the exam will be things you have seen in all three. If you
understand the problems on the problem sets and questions on the class
notes well enough to be able to answer similar questions, you should
do well on the exam.

The main topics the exam will cover include:

Propositions, axioms, and proofs (you should understand what each of these are and how to define them precisely)

Inference rules (how to determine and show if an inference rule is sound or unsound, how to correctly use inference rules in a proof)

Logical formula (how to interpret logical formulas and convert English statements into logic, determine the validity or satisfiability of a formula, and show equivalence or non-equivalence of two formulas)

Logical quantifiers (how to reason about logical formula using $\forall$ and $\exists$, including showing logical equivalence and implication)

Proof methods (you should be able to read and write proofs that use direct proof, contrapositive proof, and proof by contradiction)

Well ordering (you should be able to explain what it means for a set to be well ordered, determine if a given set and operator is well ordered, and be able to construct proofs using the well ordering principle and identify flaws in misuses of the well ordering principle)

Induction (you should understand mathematical induction and be able to construct proofs using induction and identify flaws in misuses of induction in proofs)

For most students, we believe the best way to prepare for the exam will be to (1) go over the problem sets and their solutions, and make sure you understand well any of the problems you did not get before; (2) go through the provided practice exam and try to solve all the problems on your own before reading the solutions; (3) go through the questions in the class notes and convince yourself you can answer them well; (4) re-read chapters of the book, solving the associated practice problems, especially for any sections on topics where you had difficulty on the problem sets. If you do #1 and #2 and understand well the problems on the practice exam, you should be confident you’ll do well on the exam; if you struggled on the problem sets, you would benefit from doing #3 and #4 as well.

## Induction Principle

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

- $P(0)$ is true, and
- $P(n) \implies P(n + 1)$ for all $n \in \mathbb{N}$,

then

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

**Prove:** For all sets $A$, $|pow(A)| = 2^|A|$.

**Prove:** The sum of the first $n$ positive integers is $\frac{n(n+1)}{2}$.

### Generalizing to Well-Ordered Sets

We can use Induction for any well-ordered set, where there is an operation (like ‘+ 1’) and a starting point (like ‘0’) that covers the whole set.

**Prove.** All non-empty finite subsets of $\mathbb{N}$ have a minimum element.

## Induction Practice

Take-Away Game: start with $n$ sticks; at each turn a player must remove 1, 2 or 3 sticks; player who takes the last stick wins.

Prove: for a Take-Away game with any initial number of sticks, $n$, either Player 1 has a winning strategy or Player 2 does.

Prove: Player 1 has a winning strategy for a Take-Away game with $n$ sticks, if \bigfillin. Otherwise, Player 2 has a winning strategy.

Problem Set 5 (Sat, 23 Sep 2017)

**Problem Set 5** [PDF] is now posted and
is due **Friday, 29 September at 6:29:00pm**. Please read the
collaboration policy carefully - unlike previous assignments the
*Students* → *Submissions* relation for this assignment may not be
injective.

Class 10: Set Cardinality, Induction (Thu, 21 Sep 2017)

### Schedule

This week you should finish reading MCS Chapter 4 (section 4.5) and Section 5.1. We will discuss Induction (Section 5.1) next class.

**Problem Set 4** is due **Friday at 6:29pm**. The
original version of Problem Set 4, Question 6, asked for a *function*,
when we really meant to ask for a *total function* (as we defined it
in class today, and the book defines it). The problem set is updated
now to specify this. If you already answered the original question,
you do not need to update your answer, just indicate clearly for which
questions the function you defined is partial. Sorry for the
confusion!

**Problem Set 5** (not yet posted) will be due Friday, 29 September.

**Exam 1** will be in-class on Thursday, 5 October. It will cover
Classes 1 - 11, Problem Sets 1 - 5, and MCS Chapters 1 - 5.

**Alternate definition:** The *cardinality* of the set
$$
N_k = { n | n \in \mathbb{N} \wedge n < k }
$$
is $k$. If there is a *bijection* between two sets, they have the same
cardinality.

#

If there is a *surjective relation* between $A$ and $B$ what do we know
about their cardinalities?

##

If there is a *surjective function* between $A$ and $B$ what do we know
about their cardinalities?

##

If there is a *total surjective function* between $A$ and $B$ what do we know
about their cardinalities?

##

If there is a *total surjective injective function* between $A$ and $B$
what do we know about their cardinalities?

##

What is the cardinality of $A \cup B$?

#

# Induction Principle

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

- $P(0)$ is true, and
- $P(n) \implies P(n + 1)$ for all $n \in \mathbb{N}$,

then

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

## Template for Induction Proofs

- State, “We prove by induction.”
- Define a predicate, $P(n)$. This is the
*induction hypothesis*. Our goal is to show that $P(n)$ is true for all $n \in \mathbb{N}$. - Prove $P(0)$ is true. (
*base case*or*basis step*.) - Prove that $P(n) \implies P(n + 1)$ for every $n \in \mathbb{N}$. (
*induction step*) - Conclude that $P(n)$ is true for all $n \in \mathbb{N}$ by induction.

How is the method of *proof by induction principle* similar to and different from *proof by well-ordering principle*?

# Power Sets

The **power set** of $A$ ($\textrm{pow}(A)$)is the set of all subsets of $A$:
$$
B \in \textrm{pow}(A) \iff B \subseteq A.
$$

Prove that the size of the power set of a set $S$ with $|S| = N$ is $2^N$ using induction. (We’ll do this in Class 11, but see how far you can get on your own.)

#

#

Problem Set 3 Comments (Wed, 20 Sep 2017)

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

Class 9: Relations, Finite Set Cardinality (Tue, 19 Sep 2017)

### Schedule

This week you should finish reading MCS Chapter 4 (section 4.5) and Section 5.1. We will discuss Induction (Section 5.1) next class.

**Problem Set 4** is due **Friday at 6:29pm**. The
original version of Problem Set 4, Question 6, asked for a *function*,
when we really meant to ask for a *total function* (as we defined it
in class today, and the book defines it). The problem set is updated
now to specify this. If you already answered the original question,
you do not need to update your answer, just indicate clearly for which
questions the function you defined is partial. Sorry for the
confusion!

**Problem Set 5** (not yet posted) will be due Friday, 29 September.

**Exam 1** will be in-class on Thursday, 5 October. It will cover
Classes 1 - 11, Problem Sets 1 - 5, and MCS Chapters 1 - 5.

## Total and Partial 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} $$

If the function is *total*, every element of the domain has one
associated codomain element; if the function is *partial*, there may be
elements of the domain that do not have an associated codomain element.

## Relation Relationships

Definition review: **binary relation**, $R$, consists of a domain set,
$A$, and a codomain set, $B$, and a subset of $A \times B$ called the
*graph* of $R$.

For each statement below, give the name and at least one example.

- A binary relation where no element of $A$ has more than one outgoing edge:

##

- A binary relation where every element of $A$ has exactly one outgoing edge:

##

- A binary relation where every element of $B$ has exactly one incoming edge:

##

- A binary relation where every element of $A$ has exactly one outgoing edge and every element of $B$ has exactly one incoming edge:

##

If there exists a *bijective* relation between $S$ and $T$ defined by the graph $G$ which of these *must* be true:

a. there exists some *injective* relation between $S$ and $T$.
b. there exists some *bijective* relation between $T$ and $S$.
c. there exists a *total* function, $f: S \rightarrow T$.
d. $S - T = \emptyset$.
e. the number of elements of $S$ is equal to the number of elements of $T$.
f. $G - (S \times T) = \emptyset$.
g. $(S \times T) - G = \emptyset$.
h. $(S \times T) - G \neq \emptyset$.

# Relation Practice

The *inverse* of a relation $R: A \rightarrow B, G \subseteq A \times B$ is defined by reversing all the arrows:
$$
R^{-1}: B \rightarrow A, G^{-1} \subseteq B \times A
$$

$$ (b, a) \in G^{-1} \iff \fillin\fillin\fillin\fillin $$

What does it mean if $R \equiv R^{-1}$?

# Set Cardinality

**Finite Cardinality.** The book’s definition is: ``If $A$ is a finite set, the *cardinality* of
$A$, written $|A|$, is the number of elements in $A$.”

Does this definition require adding a new fundamental set operation, or is it meaningful with just the set operations we have defined?

**Alternate definition:** The *cardinality* of the set $$ N_k = { n |
n \in \mathbb{N} \wedge n < k } $$ is $k$. (Next class, we’ll use
this to define the *cardinality* of any set. You should be able to
figure out how to do this on your own with what you know now.)

NAND/XOR Challenge Solved! (Sat, 16 Sep 2017)

Congratulations to Jake Smith for solving the NAND/XOR challenge from Class 5!

The minimum number of NAND gates needed to implement XOR is **5**.

His solution used a brute force search through all possible formulas using NANDs to test them for logical equivalence to XOR.

You can find the Python code he used to do the search here: https://github.com/ION28/CS2102_ChallengeProblemSolutions/blob/master/CP1_NAND_Brute_Force.py.

His write-up of the solution, including a list of all 200 ways to define XOR using 5 NAND operations is here: Solution (PDF)