Chapter 1 - Foundations: Logic and Proofs

1.1 Propositional Logic
Proposition
Truth Table(2^n)

Connectives
Negation
Conjunction
Disjunction
Implication

Converse
Inverse
Contrapositive(equivalent)

Operator Precedence

1.2 Applications of Propositional Logic
System Specifications
Consistent
Contradiction

Solving Logic Puzzles

1.3
Logical Equivalence

Tautology
Contradiction
Contingency

De Morgan's Law
Disjunctive Normal Form

Boolean Logic Laws
Identity
Domination
Idempotent
Double Negation
Commutative
Associative
Distributive
De Morgan's
Absorption
Negation

Propositional Satisfiability
Satisfiable
Unsatisfiable
Solution
Solving Satisfiability Problems(w/o truth table)

1.4 Predicates and Quantifiers
Predicate Logic
Predicate
Propositional Function P(x)

Preconditions - Valid Input
Postconditions - Valid Outputs

Quantifiers
Quantification
All, some, many, none, few

Domain of Discourse

Universal Quantifier(For All)
Counterexample
Existentital Quantifier(There exists)
Uniqueness Quantifier

Quantifier Precedence
Binding Variables

Logical Equivalence Involving Quantifiers
Negating Quantified Expressions(De Morgan's)

Translating from English
Quantifiers in System Specifications

1.5 Nested Quantifiers
Quantification as Loops
Order of Quantifiers
Scope

Multiplicative Inverse

Translating to/from English

Negating Nested Quantifiers

1.6 Rules of Inference
Argument
Premise
Valid
Fallacies
Conclusion

Argument Forms
Modus ponens(law of detachment)
Modus tollens
Hypothetical syllogism
Disjunctive syllogism
Addition
Simplification
Conjunction
Resolution

Building Arguments

Common Fallacies
Fallacy of affirming the conclusion
Fallacy of denying the hypothesis

Universal Instantiation
Universal Generalization
Existential Instantiation
Existential Generalization

Combining rules of inference for propositions and quantified statements

1.7 Introduction to Proofs
Informal Proofs

Proof
Theorem
Axioms(Postulates)
Lemma
Corollary
Conjecture
Omitting Quantifiers

Methods of Proving Theorems
Direct Proof
Parity
Proof by Contraposition
Indirect Proof
Proof by Contradiction
Proof of Equivalence
Counterexamples

Common Mistakes in Proofs
Vacuous and Trivial Proofs
"begging the question"
"circular reasoning"

Definitions:
Integer
Even
Odd
Perfect square
Sum of all integers less than n
Rational number

General Proof Strategy

Readability(compassion)

1.8 Proof Methods and Strategy
Exhaustive Proof
Proof by Cases

Leveraging Proof by Cases
Without Loss of Generality
Common Errors with Exhaustive Proofs and Proof by Cases

Existence Proofs
Witness
Constructive
Non-constructive

Uniqueness Proofs

Proof Strategies
Forward and backward reasoning
Adapting Existing Proofs
Looking for Counterexamples

Tiling Problems

Definitions:
Perfect Power
Arithmetic Mean
Metric Mean
Fermat's Theorem

Chapter 2 Basic Structures: Sets, Functions, Sequences, Sums, and Matrices

2.1

2.2

2.3

2.4

2.5

2.6

Chapter 5

5.1

5.2