Midterm 1: Chapters 1 and 2

Chapter 1

Section 1.1: Propositional Logic

• What is a proposition?
• Truth tables (sorry!)
• Negations of propositions (¬p)
• Conjunctions (p ∧ q)
• Disjunctions (p ∨ q)
• Exclusive OR (p ⊕ q)
• Logic and Bit operations (1’s and 0’s)
• Conditionals
  • Conditional statements (p → q)
  • Contrapositive, converse, inverse
  • Biconditional statements (p ↔ q)

Section 1.2: Applications of Propositional Logic

• Translating English Sentences
• System specifications and consistency
• Logic Gates

Section 1.3: Propositional Equivalences

• Tautologies, contradictions, and contingencies
• Logical equivalences
• Laws (Tables 6 and 7).
  • Demorgan’s Laws
  • Finding new logical equivalences without using a truth table.
• Propositional Satisfiability

Section 1.4: Predicates and Quantifiers

• What is a predicate?
• Predicate functions
• Quantifiers
  • Universal and Existential
  • Uniqueness quantifier expressed with Universal/Existential
  • Negations (Demorgan’s Laws)
• Logical equivalences with quantifiers
• Expressing in English

Section 1.5 Nested Quantifiers

• Order of quantifiers
• Translating mathematical statements
• Translating nested quantifiers to English and vice versa.
• Negations of nested quantifiers.

Section 1.6 Rules of Inference

• Premises and valid arguments
• Rules of inference for propositional logic
  • Table 1
  • Modus Ponens, Modus Tollens, etc.
  • Resolution
  • Using these rules to build arguments.
  • Logical fallacies
• Rules of inference for quantifiers
  • Universal generalization/instantiation
  • Existential generalization/instantiation

Section 1.7: Introduction to proofs

• Theorems/Axioms/Postulates
• Proof strategies
  • Direct proofs
  • Proof by contraposition
  • Proof by contradiction
  • Vacuous and trivial proofs
• Disproving statements: Counterexamples

Chapter 2

Section 2.1: Sets

• What is a set?
• Roster notation and set-builder notation
• Sets of numbers and their notation (natural numbers, integers, positive integers)
• Empty sets
• Subsets, proper subsets, and equality
• Cardinality of a set.
• Power sets
• Cartesian products and n-tuples.
• Set notation and quantifiers.

Section 2.2: Set operations

• Union of two sets.
• Intersection of two sets and disjoint sets.
• Difference of two sets.
• The universal set U and the complement of a set.
• Table 1: Set Identities

Section 2.3: Functions

• What is a function (in the more abstract sense)?
• Domains, Codomains, Ranges
• One to One functions (injective)
• Onto functions (surjective)
• One to One Correspondence functions (bijective) and inverses.
• Composition of functions.
• Special functions: floor, ceiling, modulo.

Section 2.4: Sequences and Summations

• What is a sequence?
• What is a recurrence relation?
  • Initial conditions
  • Closed formulas of recurrence relations
  • Strategies for finding sequences.
• Summations
  • Summation notation with upper/lower limits
  • Infinite series
  • Formulas for calculating sum of terms
  • Double summations

Section 2.6: Linear Algebra

• What is a matrix?
  • m rows by n columns
  • Order of indices
• Adding/subtracting matrices
• Matrix multiplication
  • First row * first column, second row * second column, etc.
  • Identity matrix and inverses of square matrices.
  • Powers of square matrices.
• Zero-One matrices
  • Join/Meet
  • Boolean product