CISC102 Winter 2024

Discrete Math Portfolio

Due Date: Monday April 15th 11:59pm EST (Kingston Time) to GradeScope.

There are two parts to this assignment. This document is six pages long

Part 1: Topic Review

For each Unit taught this term, write a short summary of the topic. You should include relevant definitions, key information, and/or information on how to solve problems from this unit. A summary of all topics covered is provided at the end of this document. It is recommended you review your weekly check-ins.  Be sure to clearly highlight and discuss the topics within the unit you have mastered and those that you are still learning.

Requirements:

•  Between 250-600 words for each section

• Keywords from each section are written in bold

• Most definitions from the unit are present

• The summary is written in your own words

•  Must be written in LATEX(See Overleaf Template in onQ)

• Include helpful reminders that are particular to  YOU  (eg.  “I always mix up equivalence relations and partial orders, so I want to be sure to remember those properties”).

Sample Response for Part 1:

Topic: Set Theory (Unit 1)

A set is a mathematical model for a collection of different things. The members of a set are called elements; two sets are equal if they contain the exact same elements. Sets may be finite or infinite. They are unordered and typically do not contain duplicate elements. We say U is the set of all elements within some domain, and ∅ is the set that contains nothing. Common operations include the union, intersection, difference, and complement. For sets A and B, each is written:

• Union: A ∪ B denotes the set of all elements in A or B. This includes elements that are in both A and B.

• Intersection: A ∩ B denotes the set of all elements in both A and B.

• Set Difference: A\B denotes the set of all elements in A that are not in B.

• Complement: A denotes the set of all elements that are not in A.

• Subsets: A ⊆ B if all the elements of A are also in B. If A = B then A is a proper subset of B (denoted A ⊂ B.

Some helpful reminders: You can remember that ∩ is the iNtersection because it looks like an n, and ∪ is the Union because it looks like a u. Applying the rules to simplify can be tricky, so go slow and state every rule you apply. Using a Venn Diagram can help understand the operations on sets.

Part 2: Problem Solving

For each unit, some difficult problems are provided below.  Please write a full solution in LATEXto FIVE problems from each section.

SETS and LOGIC

1.   (a)  Find the power set of S = {∅, a{a,b}}

(b)  Find the power set of A × B where A = {a,b} and B = {{c}}

2.   (a)  Let A,B,C be sets such that |A| = x, |B| = y , |C| = z.  Determine exactly or state a range of values:

(i) |A ∪ B|      (ii) |C\(A ∪ B)|

3. NEW Use a truth table to prove or disprove the following equivalence: p → (q ∨ ¬r) ≡ ¬(p ∧ r) ∨ q

4.  Let A = {n ∈ Z | n ≡ 3 (mod 4)} and let B = {n ∈ Z | 4/n-7  ∈ Z}. Prove that A = B .

5.  Tommy Flanagan was telling you what he ate yesterday afternoon.  He tells you,  “I had either popcorn or raisins.  Also, if I had cucumber sandwiches, then I had soda.  But I didn’t drink soda or tea.”  Of course you know that Tommy is the worlds worst liar, and everything he says is false.  What did Tommy eat?  Justify your answer by writing all of Tommy’s statements using sentence variables (P,Q,R,S, T), taking their negations, and using these to deduce what Tommy actually ate.

6. Let B(x) represent that person x is in Book Club.  Let R(x,y) represent that person x has read book y.  Express each logical phrase in plain language, and each plain language statement in logical notation.

•  No person in book club has read every book

•  There is a book that no one in book club has read.

• ∀y ∃x such that (B(x) ∧ R(x,y))

• ∃x such that ∀y B(x) ∧ ¬R(x,y)

PROPERTIES OF INTEGERS

1.  Prove that is an integer for all values of k ∈ Z.  [Hint:  expand the expression].

2.  Prove that for any a,b,c ∈ Z that

ab + ac + bc ≤ a2 + b2 + c2

[Hint: consider (a − b)2 + (b − c)2  + (c − a)2]

3.  Prove or find a counter example: 5y2 + 5y + 1 is prime for all positive integers y.

4. Prove that gcd(a,b) =gcd(a − b,b).

5. Find gcd(420, 252, 240, 384).  [Hint: gcd(a,b,c,d) =gcd(gcd(a,b)gcd(c,d))].

6. Prove that 2/n−5 is even if and only if n ≡ 1 mod 4.

COUNTING

1.  A pizza store has 3 kinds of crust, 2 kinds of sauce, and 8 toppings.

(a)  How many pizzas can you make with 1 crust, 1 sauce, and three toppings?

(b)  How many pizzas can you make with 1 crust, 1 sauce, and any number of toppings?

2. You flip a coin 5 times in a row. Determine the counts for each of the following scenarios:

(a) You flip Heads at least once

(b) You never flip the same side twice in a row (eg. HHTHT is not allowed but HTHTH is acceptable).

(c) You flip heads an even number of times (note: zero is even).

3.   (a)  How many ways can you arrange the letters in abbcccdefg?

(b) What if the fg must be adjacent in either order?

(c) What if the a,d,e must appear in alphabetical order?  [Hint:  How can you modify an invalid string so that it becomes valid?]

4.  Prove that for any 5 points places on the unit square, at least one pair of points will be within a distance of 1/√2 from
from each other?  The Unit Square is a square in the cartesian plane with all side lengths equal to 1.  [hint:  divide the square into smaller squares with side length 2/1, then consider how far apart the corners are from each other].

5. Let A be a set with |A| = m, and B be a set with |B| = n where m < n. (a) How many functions are there f : A → B? (b) How many bijections are there f : A → B?

6.  Consider a map of a town called Queenston, where all streets intersect in a cartesian grid. Imagine you live at position (0,18) in the North West corner of the city.  Throughout the city, you have two best friends Boohoo and Gail. You also have an enemy, Smith.  These other students live at:  Boohoo (3, 16), Gail (20, 2), and Smith (15, 9).  Your university, King’s University at Queenston, is located in the farther corner from you in the South East at location (23, 0).  You have an e-bike that will only allow you to drive south or east.

How many routes can you take from home to school that pass through both of your best friends houses, but avoid your enemy?

RELATIONS

1.   (a)  Let a b if and only if ab  > 0.  Prove that    is  an  equivalence  relation on the real numbers.

(b)  Let aRb if and only if a|b.  Is R a partial order on the integers?  Prove or disprove.

2. Prove by induction that the following summation holds for all integers n ≥ 1

3.   (a)  If f, g : A → A are both bijections, prove that g ◦ f is also a bijection.

(b) Let A  =  {1, 2, 3, 4, 5}  and  B  =  {red, yellow, blue, green, purple}.    Prove  that  if f : A → B is one-to-one then f must also be onto.  [Hint:  Try a contradiction].

4. What are the equivalence classes of the following equivalence relations on the set Z\{0}?

(a)  aRb iff ab > 0

(b)  aRb iff a|b and b|a

(c)  aRb iff a − b is even

5.  Given the recurrence relation an  = 10an−1  − 31an−2 + 30an−3  with a0  = 3 and a1  = 6 and a2  = 6.  Prove using strong induction that the closed form is

an  = 3 · 3n − 5n + 2n

6.  Given the recurrence relation

an  = an−1  − an−2 + an−3 + 4n − 6

with initial conditions a1  = 1, a2  = 4, and a3  = 9,

(a)  Find a4 , a5 , a6 , a7

(b)  Conjecture a closed form.

(c)  Prove the closed form using strong induction.

Learning Outcomes for CISC102

•  Sets and Logic

◦ Simplify a set expression using set laws

◦ Determine the set resulting from set operations

◦ Use a Venn Diagram to Represent Set Operations

◦ Principle of Inclusion and Exclusion for Sets, apply this to set computations and proofs

◦ Understand the Power Set is a Set of Sets

◦ Determine the union or intersection of indexed sets

◦ Prove that two sets are equal

◦ Create a truth table to represent a logical expression

◦ Use predicates and quantifiers to express natural language, and be able to negate quantifiers

• Properties of Integers

◦ Apply the different proof techniques to proofs about even and odd numbers and divisibility: direct proof, contrapositive, contradiction, and biconditional proofs

◦ Prove theorems involving divisibility a | b, modular congruence a 三 b modn, absolute value |a|; apply appropriate proof techniques including biconditional, contradictions, contrapositive, and cases

◦ Understand prime numbers and greatest common divisors

◦ Apply Euclid’s Algorithm to determine the gcd of two integers, including the solutions to the equation ax + by = gcd(a,b)

•  Counting

◦ Prove the closed form of a summation using mathematical induction

◦ Given a counting scenario, determine if order matters or if there is replacement, then apply the correct counting technique of factorial n! , exponent nk , combination  (k(n)), permutation nPk

◦ Use the Principle of Inclusion and Exclusion for counting

◦ Understand the applications of counting we studied: selecting groups given require- ments  (eg.   committees or marbles), counting with indistinguishable elements  (eg. anagrams), lattice paths

•  Functions and Relations

◦ Explain the difference between a function and a relation

◦ Define a binary relation on a set A

◦ Understand the properties of relations, and that not every relation has every property

◦ Prove a given relation is an equivalence relation, a partial order, or neither

◦ Determine the reflexive or symmetric closure of a given relation

◦ Determine the inverse of a relation

◦ Draw the Hasse Diagram for a partial order

◦ Determine the equivalence classes for an equivalence relation

◦ Determine if a function is a bijection by checking if it is both 1-1 and onto.

◦ Find the inverse of abijecton (note: inverses can only exist if a function is a bijection)

◦ Prove the closed form of a Recurrence Relation using strong induction

◦ Given an application scenario, determine a recurrence relation by examining how to build an earlier iteration of the object

◦ Find the closed form of a first-order recurrence relation