CSE 16, Applied Discrete Mathematics Midterm 3

CSE 16 Applied Discrete Mathematics - Midterm 3 Study Notes

General Exam Guidelines

Instructor: Kyle Miller
Format: Answer questions in provided spaces; if you run out of room, continue on a blank page and indicate the new page.
Time: 3 hours for completion.
Reference Sheet: Included at the end of the exam (removable).
Restrictions: No phones, calculators, computers, or outside references. Clarifications may be requested from course staff.
Evaluation Criteria: Correctness, clarity, completeness, and precision of responses. Use complete sentences.
Advice: If stuck, move to the next problem.
Affirmation of Original Work: Submission signifies that the work is the student’s own and that the rules have been followed.

Exam Structure

Content Coverage: 50–70% of the final exam is based on “Midterm 3” (covering weeks 7–10), with the remainder reviewing weeks 1–6.
Final Exam Composition: Two-thirds of points from midterm and question bank materials; remaining one-third aligned with the question banks.
Modification of Questions: Expect slight alterations in questions for clarity, points allocation, wording improvement, simplification, or reordering.

True/False Questions

Understanding Mathematical Definitions
- True or False statements and expected answers:
  - (a) The definition of 2 divides n is that n/2 ∈ Z.
  - Answer: True
  - (b) The definition of 2 divides n is that 2 ≠ 0 and k ∈ Z such that n = 2k.
  - Answer: False
  - (c) If two textbooks use the same mathematical terminology, it is safe to assume the terminology uses equivalent definitions.
  - Answer: False
  - (d) An author can give non-standard mathematical definitions for pre-existing terminology if they so choose.
  - Answer: True
  - (e) Mathematical definitions must reflect a pre-existing intuitive concept to be valid.
  - Answer: False
  - (f) Giving a mathematical definition creates a new formal concept.
  - Answer: True
  - (g) Understanding a given mathematical definition requires insight beyond its literal logical meaning.
  - Answer: True
  - (h) Strictly speaking, understanding a given mathematical definition only requires memorizing the logical meaning of the definition.
  - Answer: False
  - (i) To write formal proofs about a mathematical definition, sometimes it is necessary to appeal to an intuitive understanding.
  - Answer: True
  - (j) To write formal proofs about a mathematical definition, unfolding the definition is always sufficient.
  - Answer: False
  - (k) There are proof techniques in English proofs that cannot be represented by rules of inference proofs.
  - Answer: True
  - (l) An English proof is correct if it is written in enough detail that you can see how to “compile it” into a correct rules of inference proof.
  - Answer: True
  - (m) Humpty Dumpty's quote about word usage could be speaking of mathematical definitions.
  - Answer: True

Induction and Proof Techniques

Principles of Induction
- True or False statements concerning the principle of induction:
  - (a) The principle of induction can only be accepted on faith.
  - Answer: False
  - (b) The principle of induction is a direct consequence of the natural numbers being those numbers you can count to, starting from zero.
  - Answer: True
  - (c) You can prove ∀n ∈ Z P(n) by induction, and you only need the inductive step since there is no base case.
  - Answer: False
  - (d) If you remove the base case from the principle of induction, it is invalid — which means you can prove false propositions with it.
  - Answer: True
  - (e) The proposition being proved is false if it uses the principle of induction but forgets the base case.
  - Answer: True
  - (f) If I set up dominoes close enough to guarantee that each will knock down the next, then eventually all the dominoes will fall down.
  - Answer: True
  - (g) There is a well-defined function f: N → R with a recursive rule f(n) = f(n + 1) + f(n + 2).
  - Answer: False
  - (h) The function f: N → R defined with f(0) = 1 and f(n) = 2f(n − 1) + 1 for n ≥ 1 is well-defined since the rules only use f applied to smaller inputs.
  - Answer: True
  - (i) According to lecture, strong induction must have a base case.
  - Answer: True
  - (j) The intuition for strong induction is that the proof recursively applies the theorem being proved on only smaller inputs.
  - Answer: True
  - (k) Every subset of N has a least element.
  - Answer: False
  - (l) Every nonempty subset of N has a least element.
  - Answer: True
  - (m) Every nonempty subset of N has a greatest element.
  - Answer: False
  - (n) Induction, strong induction, and the well-ordering principle are all logically equivalent.
  - Answer: True
  - (o) Strong induction lets you prove more things than weak induction can.
  - Answer: False
  - (p) Every recursively defined set has a principle of induction.
  - Answer: True

Set Theory and Functions

True/False Statements about Functions and Sets
- Consider the following statements, determining their truth:
  - (a) If f: X → Y is injective and |X| = |Y| then f is surjective.
  - Answer: True
  - (b) If f: X → Y is surjective and |X| = |Y| then f is injective.
  - Answer: True
  - (c) If f: X → Y is a function and |X| = |Y| then f is surjective.
  - Answer: False
  - (d) If f: X → Y is a function and |X| = |Y| then f is injective.
  - Answer: False
  - (e) If f: X → Y is bijective then |X| = |Y|.
  - Answer: True
  - (f) If f: X → Y is a function and |X| = |Y| then f is bijective.
  - Answer: False
  - (g) If |X| ≥ |Y| then there exists a bijective function f: X → Y.
  - Answer: False
  - (h) If |X| ≤ |Y| then there exists a bijective function f: X → Y.
  - Answer: False
  - (i) If |X| = |Y| then there exists a bijective function f: X → Y.
  - Answer: True

Set Cardinalities and Proofs

Properties of Finite Sets
- Statements regarding cardinalities of sets:
  - (a) |∅| = 0.
  - Answer: True
  - (b) |{∅}| = 0.
  - Answer: False
  - (c) |{∅}| = 1.
  - Answer: True
  - (d) |{{∅}}| = 2.
  - Answer: False
  - (e) |P(∅)| = 0.
  - Answer: False
  - (f) |P({∅})| = 1.
  - Answer: False
  - (g) For all finite sets X, |X| = 0 if and only if X = ∅.
  - Answer: True
  - (h) For all finite sets X and Y, |X ∪ Y| = |X| + |Y|.
  - Answer: False
  - (i) There exists finite sets X and Y such that |X ∪ Y| = |X| + |Y|.
  - Answer: True

Functions and Bijections

Set of Functions and Bijections
- Constants defined for finite sets X and Y, where k ∈ N:
  - A = |X|
  - B = |X||Y|
  - C = |Y||X|
  - D = k|X|
  - E = |X|k
  - F = P(|X|, k)
  - G = P(|X|, |Y|)
  - H = P(|Y|, |X|)
  - I = {|X| race k}
  - J = 2^{|X|}
- Tasks within this section consist of finding cardinalities for specific sets, determining bijections, or writing injective functions.

Proof by Induction

Inductive Proof Tasks
- Tasks demanding proofs by induction:
  - (a) Prove for all n ∈ N: extstyleinom{n}{k} = rac{n!}{k!(n - k)!}
  - (b) Recursive sequences defining proofs. Each section typically includes statements to establish showings of inequalities and formulae.

Combinatorial Problems

Combinatorial Counting Tasks
- Example problems focusing on enumeration, such as the allocation of items among groups, evaluating combinations and permutations, etc.
- Tasks may involve defining unique methods for the distribution of items and providing numeric expressions for total counts.

Reference Sheets

Laws of Propositional and Predicate Logic (Reference)

Idempotent Law:
- p \/ p ext{ is equivalent to } p
- p \land p ext{ is equivalent to } p
Associative Law:
- (p \/ q) \/ r \text{ is equivalent to } p \/ (q \/ r)
- (p \land q) \land r \text{ is equivalent to } p \land (q \land r)
Commutative Law:
- p\/q \text{ is equivalent to } q\/p
Distributive Law:
- p\/ (q \land r) \text{ is equivalent to } (p\/q) \land (p\/r)

Functions and Identities

Additional Rules (Reference)

Combinatorial Identities:
- n! = egin{cases}1 & ext{if } n = 0 \ n(n - 1)! & ext{if } n > 0 \ ext{Combinatorial Functions} \ P(n, r) = rac{n!}{(n - r)!}
- Binomial Theorem:
  - (x + y)^n = inom{n}{k}x^{n-k}y^k

Summary of Relation Definitions

Key Properties of Relations

Reflexive: orall x ext{ in } R: xRx
Antireflexive: orall x ext{ in } R:
eg(xRx)
Symmetric: orall x,y ext{ in } R: (xRy)
ightarrow (yRx)
Antisymmetric: orall x,y ext{ in } R: (xRy ext{ and } yRx)
ightarrow (x = y)
Transitive: orall x,y,z ext{ in } R: (xRy ext{ and } yRz)
ightarrow (xRz)

The study notes contain several types of questions and tasks. Many of the questions, specifically in sections 1, 2, 3, and 4 (True/False questions regarding mathematical definitions, principles of induction, functions, and sets, and set cardinalities), already have their answers explicitly stated as "True" or "False" within the note itself.

For tasks like those mentioned in section 6, "Inductive Proof Tasks," where you are asked to prove a statement (e.g., proving for all n \in \mathbb{N}: \binom{n}{k} = \frac{n!}{k!(n - k)!}), you would typically follow these steps for an inductive proof:

Base Case: Show that the statement P(n) is true for the smallest value of n (often n=0 or n=1). For binomial coefficients, you might start with a specific n and k, or demonstrate it holds for the smallest general case.
Inductive Hypothesis: Assume that the statement P(k) is true for some arbitrary integer k \geq \text{base case}. Sometimes, for strong induction, you assume P(i) is true for all i from the base case up to k.
Inductive Step: Prove that if P(k) is true (from your hypothesis), then P(k+1) must also be true. This step involves using algebraic manipulation, definitions, and your inductive hypothesis to transform the expression for P(k+1) into a form that demonstrates its truth based on P(k).

For combinatorial problems, as hinted in section 7, "Combinatorial Counting Tasks," the "how to solve" depends heavily on the specific problem. Generally, these involve:

Identifying the type of arrangement: Is it a permutation (order matters) or a combination (order does not matter)? Are repetitions allowed?
Applying relevant formulas: Such as permutations (P(n, r) = \frac{n!}{(n - r)!}), combinations (\binom{n}{k} = \frac{n!}{k!(n - k)!}), or using the Multiplication Principle, Addition Principle, or Principle of Inclusion-Exclusion.
Breaking down complex problems: Decomposing the problem into smaller, manageable parts and then combining the results.