Mathematical Foundations for Computing

Mathematical Foundations for Computing is the study of the essential mathematical structures and concepts that form the theoretical bedrock of computer science. This fundamental area equips students with the formal language and analytical tools necessary to describe, analyze, and solve computational problems. Key topics typically include discrete mathematics, formal logic, set theory, graph theory, and probability, which are directly applied to reason about the correctness and efficiency of algorithms, design complex data structures, understand the limits of computation, and model computational systems.

  1. Foundations of Logic and Proofs
    1. Propositional Logic
      1. Propositions
        1. Definition of a Proposition
          1. Propositional Variables
            1. Well-Formed Formulas
              1. Atomic and Compound Propositions
              2. Logical Connectives
                1. Negation
                  1. Conjunction
                    1. Disjunction
                      1. Exclusive Or
                        1. Implication
                          1. Biconditional
                            1. Precedence of Logical Operators
                            2. Truth Tables
                              1. Constructing Truth Tables
                                1. Evaluating Compound Propositions
                                  1. Truth Table Analysis
                                  2. Logical Equivalence
                                    1. Definition of Logical Equivalence
                                      1. Tautology
                                        1. Contradiction
                                          1. Contingency
                                            1. De Morgan's Laws
                                              1. Distributive Laws
                                                1. Associative Laws
                                                  1. Commutative Laws
                                                    1. Double Negation Law
                                                      1. Absorption Laws
                                                        1. Identity Laws
                                                          1. Domination Laws
                                                          2. Conditional Statements
                                                            1. Definition of Conditional Statements
                                                              1. Converse
                                                                1. Contrapositive
                                                                  1. Inverse
                                                                    1. Truth Table Analysis of Conditionals
                                                                      1. Necessary and Sufficient Conditions
                                                                      2. Arguments and Validity
                                                                        1. Structure of Arguments
                                                                          1. Valid and Invalid Arguments
                                                                            1. Identifying Premises and Conclusions
                                                                              1. Logical Fallacies
                                                                                1. Sound Arguments
                                                                              2. Predicate Logic
                                                                                1. Predicates and Variables
                                                                                  1. Definition of Predicates
                                                                                    1. Free and Bound Variables
                                                                                      1. Predicate Symbols
                                                                                      2. The Universe of Discourse
                                                                                        1. Restricting the Domain
                                                                                          1. Specifying the Universe
                                                                                            1. Domain-Dependent Truth Values
                                                                                            2. Quantifiers
                                                                                              1. Universal Quantifier
                                                                                                1. Existential Quantifier
                                                                                                  1. Expressing Statements with Quantifiers
                                                                                                    1. Multiple Variables
                                                                                                    2. Binding Variables
                                                                                                      1. Scope of Quantifiers
                                                                                                        1. Nested Quantifiers
                                                                                                          1. Variable Substitution
                                                                                                          2. Negating Quantified Statements
                                                                                                            1. Rules for Negation
                                                                                                              1. Negation of Universal Statements
                                                                                                                1. Negation of Existential Statements
                                                                                                                  1. De Morgan's Laws for Quantifiers
                                                                                                                  2. Nested Quantifiers
                                                                                                                    1. Order of Quantifiers
                                                                                                                      1. Translating English Statements to Logic
                                                                                                                        1. Quantifier Equivalences
                                                                                                                      2. Rules of Inference
                                                                                                                        1. For Propositional Logic
                                                                                                                          1. Modus Ponens
                                                                                                                            1. Modus Tollens
                                                                                                                              1. Hypothetical Syllogism
                                                                                                                                1. Disjunctive Syllogism
                                                                                                                                  1. Addition
                                                                                                                                    1. Simplification
                                                                                                                                      1. Conjunction
                                                                                                                                        1. Resolution
                                                                                                                                        2. For Quantified Statements
                                                                                                                                          1. Universal Instantiation
                                                                                                                                            1. Universal Generalization
                                                                                                                                              1. Existential Instantiation
                                                                                                                                                1. Existential Generalization
                                                                                                                                                  1. Combining Rules of Inference
                                                                                                                                                2. Introduction to Proof Techniques
                                                                                                                                                  1. Formal and Informal Proofs
                                                                                                                                                    1. Structure of Formal Proofs
                                                                                                                                                      1. Informal Reasoning
                                                                                                                                                        1. Proof Strategies
                                                                                                                                                        2. Trivial and Vacuous Proofs
                                                                                                                                                          1. Trivial Proofs
                                                                                                                                                            1. Vacuous Proofs
                                                                                                                                                              1. When to Use Each Method
                                                                                                                                                              2. Direct Proofs
                                                                                                                                                                1. Constructing Direct Proofs
                                                                                                                                                                  1. Examples of Direct Proofs
                                                                                                                                                                    1. Proof Structure
                                                                                                                                                                    2. Proof by Contraposition
                                                                                                                                                                      1. Structure of Contrapositive Proofs
                                                                                                                                                                        1. Examples of Contraposition
                                                                                                                                                                          1. Relationship to Direct Proof
                                                                                                                                                                          2. Proof by Contradiction
                                                                                                                                                                            1. Structure of Contradiction Proofs
                                                                                                                                                                              1. Identifying Contradictions
                                                                                                                                                                                1. Reductio ad Absurdum
                                                                                                                                                                                2. Proof by Cases
                                                                                                                                                                                  1. Exhaustive Case Analysis
                                                                                                                                                                                    1. Disjoint Cases
                                                                                                                                                                                      1. Overlapping Cases
                                                                                                                                                                                      2. Existence and Uniqueness Proofs
                                                                                                                                                                                        1. Proving Existence
                                                                                                                                                                                          1. Proving Uniqueness
                                                                                                                                                                                            1. Combined Existence and Uniqueness Proofs
                                                                                                                                                                                              1. Constructive vs Non-constructive Proofs

                                                                                                                                                                                          Go to top

                                                                                                                                                                                          Next

                                                                                                                                                                                          2. Basic Structures: Sets, Functions, and Relations