cs2102: Discrete Math

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)

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:

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