Final_Exam_Study_Guide

Final Exam Study Guide

Sections 1.1-5

1. Determine Truth Values

   • Evaluate compound propositions: ¬p, p ∧ q, p ∨ q, p → q.

2. Forming Statements

   • Create converse, contrapositive, and inverse of the conditional statement p → q.

3. Logical Equivalences

   • Understand and apply the following:

     • De Morgan’s Laws:

       • ¬(p ∧ q) ≡ ¬p ∨ ¬q

       • ¬(p ∨ q) ≡ ¬p ∧ ¬q

     • Conditional-Disjunction: p → q ≡ ¬p ∨ q

     • Double Negation Law: ¬(¬p) ≡ p

     • Negation Laws:

       • p ∨ ¬p ≡ T

       • p ∧ ¬p ≡ F

     • Identity Laws:

       • p ∧ T ≡ p

       • p ∨ F ≡ p

     • Domination Laws:

       • p ∨ T ≡ T

       • p ∧ F ≡ F

     • Contrapositive: p → q ≡ ¬q → ¬p

4. Evaluating Quantifications

   • Determine truth value of universal (∀x, P(x)) and existential (∃x, P(x)) quantifications across different domains (finite, restricted, infinite).

5. Precedence of Quantifiers and Logical Operators

   • Order: (∀, ∃), ¬, ∧, ∨, →, ←→

6. Negation of Quantified Expressions

   • Find the negation of expressions with quantifiers.

7. Translation Between Languages

   • Translate from English to logical expressions and vice versa.

8. Nested Quantifiers

   • Understand statements with nested quantifiers; know how to negate them and provide counterexamples if necessary.

/

/

Textbook Exercises for Review

• Section 1.1: 11, 15, 25, 29

• Section 1.3: 7, 9, 13, 15

• Section 1.4: 1, 9, 13, 17, 25, 27, 33, 35, 37

• Section 1.5: 1, 9, 19, 31, 37, 39

Sections 2.1-3

1. Understanding Set Notations

   • Difference between: ∈ (element of), ⊆ (subset of), ⊂ (proper subset).

2. Describing Sets

   • Use roster method and set builder method to describe sets.

3. Special Sets

   • Know sets like ∅ (empty set), U (universal set), A (any set), P(A) (power set), A × B (Cartesian product).

4. Finding Size of a Set

   • Determine the cardinality of sets.

5. Set Operators and Identities

   • Apply:

     • Identity Laws: A ∩ U = A, A ∪ ∅ = A

     • Domination Laws: A ∪ U = U, A ∩ ∅ = ∅

     • Complementation Law: A^c = A'

     • De Morgan’s Laws: A ∩ B = A ∪ B', A ∪ B = A' ∩ B'

     • Complement Laws: A ∪ A = U, A ∩ A = ∅

     • Set Difference: A − B = A ∩ B'

Textbook Exercises for Review

• Section 2.1: 7, 11, 13, 21, 25, 29, 37, 45, 47

• Section 2.2: 3, 16, 17, 21, 27

Sections 1.7-8: Proof Techniques

1. Direct Proof

   • Assume p is true, use rules of inference to show q must also be true.

2. Proof by Contraposition

   • Start with ¬q, show ¬p must follow using axioms, definitions, and theorems.

3. Proof by Contradiction

   • Assume p ∧ ¬q is true, derive a false statement using axioms and definitions.

4. Proof by Cases

   • Examine a limited number of cases to prove a statement.

5. Existence Proof

   • Show that ∃xP(x) is true by finding a specific element a such that P(a) holds (constructive) or by other means (non-constructive).

Textbook Exercises for Review

• Section 1.7: 1, 13, 19

• Section 1.8: Examples 1, 3 in subsection 1.8.2 on pages 97 and 98

Sections 5.1-3: Induction and Recursion

1. Regular Induction

   • Basis step: Show it holds for n=1 (or base case), establish inductive hypothesis, complete inductive step using the hypothesis.

2. Strong Induction

   • Basis cases: Establish multiple base cases hold true; use the inductive hypothesis to show subsequent cases.

3. Recursive Sequences

   • Identify terms in recursively defined sequences.

Textbook Exercises for Review

• Section 5.1: 3, 5, 10

• Section 5.2: 3, 5

• Section 5.3: 3, 15

Sections 6.1, 6.3-6.5: Counting Outcomes

1. Counting Principles

   • Analyze the task: consistency of candidates, order of selection, selection repetitions, distinguishability of objects.

   • Sometimes count the universe and subtract unwanted objects (complements).

2. Principle of Inclusion-Exclusion

   • To count elements in A ∪ B: |A ∪ B| = |A| + |B| − |A ∩ B|.

3. Binomial Theorem

   • Apply the theorem for counting combinations: (x + y)ⁿ = Σ from k=0 to n (n choose k) x^(n-k) y^k.

Textbook Exercises for Review

• Section 6.1: 7, 10, 11, 25, 27, 33, 43

• Section 6.3: 11, 15, 21, 26, 29, 35

• Section 6.4: 6, 9

• Section 6.5: 5, 6, 7, 13, 15, 32, 33

Sections 10.1-6: Graph Theory

1. Types of Graphs

   • Understand definitions of graphs, vertices, and edges.

2. Degree of a Vertex

   • Count edges connected to a vertex (loops count twice).

3. Handshaking Theorem

   • Total degree of all vertices is twice the number of edges: 2m = Σ deg(v).

4. Adjacency Matrix

   • Use matrix representation for undirected and directed graphs, noting properties and features.

5. Paths and Circuits

   • Define and differentiate between paths and circuits; identify simple paths.

6. Euler Paths and Circuits

   • Criteria for Euler circuits and paths using vertex degree.

7. Hamilton Circuits

   • Definition. Use to solve the traveling salesman problem.

Textbook Exercises for Review

• Section 10.2: Example 3 on page 686

• Section 10.3: 5, 7, 16

• Section 10.5: 1, 3, 4, 5, 31, 33, 35

• Section 10.6: 25

Sections 11.1-5: Trees

1. Tree Definitions

   • Definitions of trees, internal vertices, leaves, m-ary trees, and full m-ary trees.

2. Vertices and Edges

   • Relationship between vertices and edges in trees: A tree with n vertices has n−1 edges.

3. Tree Traversal

   • Preorder, postorder, and inorder traversal methods.

4. Expression Forms

   • Write and evaluate prefix, postfix, and infix expressions.

5. Kruskal’s Algorithm

   • Use to find a minimum spanning tree and its weight.

Textbook Exercises for Review

• Section 11.1: 17, 19

• Section 11.3: 7, 10, 13, 16, 23

• Section 11.5: Example 3 on page 838