Discrete Mathematics

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

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