Discrete Mathematics

# 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:

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 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 StudentsSubmissions 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 1. State, “We prove by induction.” 2. 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}$. 3. Prove$P(0)$is true. (base case or basis step.) 4. Prove that$P(n) \implies P(n + 1)$for every$n \in \mathbb{N}$. (induction step) 5. 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: 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)$$