1 of 22

Quiz #1 �Review Session

Anisha Palaparthi and Ethan Sawyer

2/13/23

2 of 22

Topics

Pigeonhole Principle (Basic and Extended)
Propositional Logic
Proofs / Proof Strategies
Sets
Functions (Injectivity, Surjectivity, Bijective)

3 of 22

Pigeonhole Principle

Basic PHP

???

Extended PHP

???

4 of 22

Pigeonhole Principle

Basic PHP

If I have k+1 pigeons and k holes, then there must be AT LEAST 2 pigeons in AT LEAST 2 holes

Extended PHP

If I have n pigeons and k holes and n > k (but n is not evenly divisible into k), then…

If pigeons are distributed across all holes evenly, then each hole has at least n/k pigeons
**AT LEAST 1 hole has AT LEAST n/k + 1 pigeons**

Remember to always state “By Pigeonhole Principle, …” whenever you’d like to use PHP!

5 of 22

Pigeonhole Practice Problems

Dave’s Hot Yoga class has 25 members, and meets 8 times a day. Every single member comes once per day, and it’s up to them which of the 8 daily classes they go to.

Each member of the class has to wear one of Hot-Yoga-Dave’s approved shirt colors: Red, Blue, or Green.

Prove that at least 1 of the daily classes will have at least 2 people wearing the same shirt color.

Problem #2

Problem #1

25 members = pigeons, 8 classes = holes → ate least one class has at least 4 members (extended PHP)�4 members in a class = pigeons, 3 colors = holes → at least 2 members of the class are wearing the same color (basic PHP)
After grabbing 7 socks, worst case scenario, I have grabbed a sock of each color. Thus, after grabbing one more sock, it has to match up with one of the previous socks so after grabbing 8 socks I am guaranteed to have a pair. For the second part, after grabbing 21 objects, it is possible that I have grabbed 3 items for each color and hence have gotten no sets yet. But the 22nd thing I grab must complete one of these 7 sets so after 22 items, I am guaranteed to have a matching set.
By Pigeonhole, there exists one row with at least two rooks, so they must threaten each other (8 rows = holes, 9 rooks = pigeons)

6 of 22

Pigeonhole Practice Problems

How many cards do you have to draw out of a standard deck of 52 in order to guarantee that you get at least three of the same suit?

7 of 22

Propositional Logic

Truth Tables - best way to check your answer!
A Note “If p, then q”

p ⇒ q
p implies q
q if p
q when p
q follows from p
q is necessary for p
p is sufficient for q
p only if q
q unless ¬p

4 Forms of an Implication

Normal: p ⇒ q
Converse: ??
Inverse: ??
Contrapositive: ??

(try to fill these in, and check your answers below)
**NORMAL = CONTRAPOSITIVE

8 of 22

Rules of Inference vs Equivalence

Rules of Inference - only go in 1 direction

ONLY use this with premise/conclusion proofs, or be prepared to do 2 proofs (one each direction)

Propositional Equivalences - Free to use whenever (for = or -> proofs)

9 of 22

Propositional Logic Problems

Rewrite

As

10 of 22

Propositional Logic Problems

Put

Into CNF (conjunctive normal form)

Show this is a tautology

11 of 22

Proofs and Proof Strategies

Proof by…

12 of 22

Proofs and Proof Strategies

Proof by…

Contradiction
Cases
Contrapositive
Direct
(Disproof) Counterexample

13 of 22

Proofs Problems

Prove that if 2ⁿ - 1 is prime, then n itself is prime.
Prove sqrt(3) is irrational
Prove: Suppose x, y ∈ R. If y^3 + yx^2 ≤ x^3 + xy^2, then y ≤ x
Prove: If r and s are rational numbers, then r+s is rational

#2 proved in discussion/lecture

01) (contrapositive) n is composite → 2n − 1 is composite.

Because n is a composite, n can be written as n = ab where a, b > 1.

Then, 2n − 1 = 2ab − 1 = (2a − 1)((2a)b−1 + (2a)b−2 + . . . + 2a + 1)

(this formula should be given as a hint to this problem - you do NOT need to know this equation). Therefore, 2n − 1 is composite. Original

implication is proved

3) Proving by contrapositive,

Suppose it is not true that y ≤ x, so y > x. Then y − x > 0. Multiply

both sides of y − x > 0 by the positive value x^2 + y^2

(y − x)(x^2 + y^2

) > 0*(x^2 + y^2)

Yx^2 + y^3 − x^3 − xy^2 > 0

Y^3 + yx^2 > x^3 + xy^2

Therefore, since, y^3 + yx^2 > x^3 + xy^2, so it is not true that y^3 + yx^2 ≤ x^3 + xy^2

4) Prove: If r and s are rational numbers, then r+s is rational

r and s are rational numbers, so for some integers m, n, p, q:

r = m/n, s = p/q

r = mq/nq, s = pn/nq

r + s = (mp + pn)/nq

So, r + s is one integer (mp+pn) divided by another integer (nq).

That is, r + s is rational

14 of 22

Proofs Problems

Prove that in any group of 7 people there is a person who knows an even number of people in the group.

You may assume that if a person A "knows" a person B, then person B also "knows" person A.

.

Proof by contradiction:

Assume there is no person who knows an even number of people.

Thus, all 7 people have an odd number of acquaintances.

If, for each person, we count the number of acquaintances, and then look at the total count, we see it is the sum of 7 odd numbers, which itself must be odd.

Now consider finding this total a different way: Notice that two people being acquaintances contributes 2 to the total we just found. (i.e., If person A knows person B, then person B also knows person A.) But then, being the sum of a bunch of 2's, the total in question must be even.

The total can't be both odd and even, so we have our desired contradiction.

Consequently, our assumption must be rejected, and its opposite must be true: there is a person who knows an even number of people.

QED.

15 of 22

Sets

Intersection: all elements that are in both sets A AND B
Union: all elements that are in either set A OR B
Complement: The set of all elements in the universe that are not in the set

16 of 22

Sets Problems

Prove that

A – (B ∩ C) = (A – B) ∪ (A - C)

17 of 22

Answers to Practice Problem

18 of 22

Sets Problems

Let A be the set of all prime numbers less than 20.

Let B be the set of all integers between -20 and 20 which are divisible by 2.

Let C be the set of all natural numbers.

Find:

a) A ∪ B

b) B ∩ C

c) A ∪ B ∪ C

19 of 22

Functions

Review Concept

20 of 22

Functions Problems

For each of the following functions, determine whether it is injective, surjective, both (a bijection), or neither. Then, prove or disprove that it is injective, and prove or disprove that it is surjective.

(a) f: R→R, f(x)=x^2

(b) f: N→R, f(x)=x

(c) f: Z+ × Z+ → Q+, f(x, y) =x/y , where A+ = {x ∈ A : x > 0} for all sets A.

(d) f: P(Z)→P(N), f(A) = A∩N

(e) f: P(Z)→P(Z), f(A) = Z−A

(a) f: R→R, f(x)=x^2

Not injective, not surjective

Not injective: (-1)^2 and 1^2 both produce the same output, even though they are different inputs.

Not surjective: x^2 ≠ -1 No input will get you -1 as an answer

(b) f: N→R, f(x)=x

Injective, not surjective

√a= √b, a=b, proves injection

Not surjective: √x will never produce -1 as an answer� � (c) f: Z+ × Z+ → Q+, f(x, y) =x/y , where A+ = {x ∈ A : x > 0} for all sets A.

Not injective, surjective

f(2,2) = 1, f(3,3) = 1. Since different inputs produce the same output, this cannot be injective

The function is the definition of a positive rational number: any rational number x/y can be produced by f(x,y), therefore it must be surjective.

(d) f: P(Z)→P(N), f(A) = A∩N

Not injective, surjective

f({0,3}) = {0}, f({0,5}) = {0}. Since different inputs produce the same output, this cannot be injective

For all N, f({a}) = a, therefore this must be surjective because any output can be produced� � (e) f: P(Z)→P(Z), f(A) = Z−A

Bijective

Z - A = Z - B, A = B, therefore this must be injective

For all Z, f({a}) = Z - {a}, therefore this must be surjective because any output can be produced

21 of 22

Functions Problems

For each of the following functions, determine whether it is injective, surjective, both (a bijection), or neither. Then, prove or disprove that it is injective, and prove or disprove that it is surjective.

(a) f : Z → Z, x → x

(b) f : R→R, x → sin(x)

(c) For a finite set A with |A| > 1, � f : P(A) → {0,...,|A|}, S → |S|

(a) f : Z → Z, x → x - Bijective

Explanation: Recall that a bijective function means that every element in the codomain has exactly one associated element in the domain (none have 2 or more, and none have zero). We can see that here. Every integer in the codomain is associated with an integer in the domain. Namely, it is associated with the same number. Thus, nothing in the codomain is ”missed,” and nothing is hit twice, since there is no way for two different integers in this function to have the same output, since they just output themselves. Thus, it is bijective

(b) f :R→R, x→sin(x) - Neither

Explanation: Recall that in order for a function to be injective/one-to-one, each value in the codomain must be only reachable by at most one element in the domain. In other words, we can’t get the same value with different inputs. Unfortunately, this isn’t the case. For example, sin(2π) = sin(0) = 0. Recall that in order for a function to be surjective/onto, all the elements in the codomain have to be colored. The problem says that the codomain is R. Unfortunately, this function misses a bunch of the reals. For example, there is no value for x such that sin(x) = 42. As such, the function is neither onto nor one- to-one.

(c) For a finite set A with |A| > 1, f : P(A) → {0,...,|A|}, S → |S| - Surjective

Explanation: The problem, in simple words, is mapping each element in the power set with its cardinality. Since the power set will contain an element of each cardinality, it needs to be surjective, since nothing in the codomain will be missed, since each of the numbers will have a corresponding set. The function is not injective, since any set greater than cardinality 1 will have at least 2 elements in the powerset of cardinality 1, mapping them both to the same element in the codomain.

22 of 22

Good Luck!

Believe in yourself, don’t stress, and you’ll do great!