|
|
| Line 1: |
Line 1: |
| − | Introduction to the mathematics of discrete structures with emphasis on structures for computer science.
| |
| | | | |
| | | | |
| | '''Catalog entry''' | | '''Catalog entry''' |
| | | | |
| − | ''Prerequisite'': Algebra and Number Systems (MAT 1313), or Discrete Mathematical Structures (CS 2233/2231), or instructor consent. | + | ''Prerequisite'': Combinatorics and Probability [[MAT2313]], or Applied Graph Theory [[MAT4323]], or instructor consent. |
| | | | |
| | ''Contents'': | | ''Contents'': |
| − | (1) Propositional logic: Axioms and Rules of Inference. Limitations of propositional logic: Informal introduction to quantifiers and syllogisms.
| + | Partially ordered sets, maximum/maximal and minimum/minimal elements. Well-ordered sets. Maximality principlies (Zorn's lemma, Well-ordering principle, Hausdorff maximality lemma). Boolean algebras and the Stone representation theorem. Generalizations of the Stone representation theorem. |
| − | (2) Predicate Logic: Existential and universal quantification, free variables and substitutions. Discussion of the various axiomatic systems for first-order logic (including axioms and rules of inference). The power and the limitations of axiomatic systems for logic: Informal discussion of the completeness and incompleteness theorems.
| |
| − | (3) Sets and boolean algebras: Operations on sets. Correspondence between finitary set operations and propositional logic. Correspondence between infinitary operations and quantifiers. The power and limitations of the language of set theory: Informal discussion of the set-theoretic paradoxes and the need for axiomatic systems for set theory.
| |
| − | (4) Relations: Special relations: Equivalence relations, partially ordered sets, maximum/minimum, maximal/minimal elements, least upper bounds and greatest lower bounds, totally ordered sets.
| |
| − | (5) Functions: Operations of functions, direct image and inverse image.
| |
| − | (6) Well-ordered sets: Correspondence between well-ordering relations and induction. Correspondence between well-ordering relations and choice functions.
| |
| − | (7) Introduction to computability. Classical models of computation (recursive functions, and Turing models). Limitations of computation (the Halting Problem, fast-growing functions). Contemporary models of computation.
| |
| − | | |
| − | | |
| − | '''Sample textbooks''': | |
| − | | |
| − | [1] Gordon Pace, ''Mathematics of Discrete Structures foe Computer Science'', Springer, 2012
| |
| − | | |
| − | [2] Vladlen Koltun, ''Discrete Structures Lecture Notes, Stanford University'', 2008. Freely available [https://web.stanford.edu/class/cs103x/cs103x-notes.pdf here.]
| |
| − | | |
| − | | |
| − | | |
| − | | |
| − | | |
| − | | |
| − | | |
| − | ==Topics List==
| |
| − | {| class="wikitable sortable"
| |
| − | ! Week !! Topic !! Sections from Pace's book !! !! Sections from Pace's book !! Prerequisites.
| |
| − | |-
| |
| − | | 1
| |
| − | || [[Propositional logic]]
| |
| − | || 2.1-2.4
| |
| − | ||
| |
| − | * Proofs
| |
| − | * boolean models
| |
| − | * connections between boolean models and proofs
| |
| − | || MAT1313 or CS2233/2231, or equivalent.
| |
| − | |-
| |
| − | | 2
| |
| − | || [[Completeness and soundness]]
| |
| − | || 2.5
| |
| − | ||
| |
| − | * Completeness and soundness of propositional logic
| |
| − | ||
| |
| − | |-
| |
| − | | 5-6
| |
| − | || [[Predicate calculus]]
| |
| − | || 3.1-3.5
| |
| − | ||
| |
| − | * Limits of propositional logic
| |
| − | * free variables and substitution.
| |
| − | ||
| |
| − | |-
| |
| − | | 7
| |
| − | || [[Sets and boolean algebras]]
| |
| − | || 4.1-4.5
| |
| − | ||
| |
| − | * Set comprehension.
| |
| − | * Finitary and general operations on sets.
| |
| − | ||
| |
| − | |-
| |
| − | | 8
| |
| − | || [[Sets and boolean algebras]]
| |
| − | || 4.6
| |
| − | ||
| |
| − | * Boolean algebras and boolean rings.
| |
| − | ||
| |
| − | |-
| |
| − | | 9
| |
| − | || [[Relations]]
| |
| − | || 5.1-5.7
| |
| − | ||
| |
| − | * Relations and sets
| |
| − | * Inverse of a relation and composition of relations
| |
| − | * Beyond binary relations
| |
| − | ||
| |
| − | |-
| |
| − | | 10
| |
| − | || [[Classifying Relations]]
| |
| − | || 6.1-6.3
| |
| − | ||
| |
| − | * Totality
| |
| − | * Surjectivity
| |
| − | * Injectivity
| |
| − | * Functionality
| |
| − | ||
| |
| − | |-
| |
| − | | 11-12
| |
| − | || [[Discrete structures]]
| |
| − | || 7.1-8.4
| |
| − | ||
| |
| − | * Graphs
| |
| − | * Semigroups
| |
| − | * groups
| |
| − | ||
| |
| − | |-
| |
| − | | 13-14
| |
| − | || [[Reasoning about programs]]
| |
| − | || 10.1-10.4
| |
| − | ||
| |
| − | * Algorithms
| |
| − | * Program semantics
| |
| − | * Uncomputability
| |
| − | ||
| |
| − | |}
| |
Catalog entry
Prerequisite: Combinatorics and Probability MAT2313, or Applied Graph Theory MAT4323, or instructor consent.
Contents:
Partially ordered sets, maximum/maximal and minimum/minimal elements. Well-ordered sets. Maximality principlies (Zorn's lemma, Well-ordering principle, Hausdorff maximality lemma). Boolean algebras and the Stone representation theorem. Generalizations of the Stone representation theorem.
