Difference between revisions of "MAT5423"
Jose.iovino (talk | contribs) |
Jose.iovino (talk | contribs) |
||
| Line 10: | Line 10: | ||
'''Catalog entry''' | '''Catalog entry''' | ||
| − | Prerequisite: Algebra and Number Systems (MAT 1313), or Discrete Mathematical Structures (CS 2233/2231), or instructor consent. | + | ''Prerequisite'': Algebra and Number Systems (MAT 1313), or Discrete Mathematical Structures (CS 2233/2231), or instructor consent. |
| − | Contents: | + | ''Contents'': |
| − | Propositional logic: Axioms and Rules of Inference. Boolean Algebras. Limitations of propositional logic: Informal introduction to quantifiers and syllogisms. | + | (1) Propositional logic: Axioms and Rules of Inference. Boolean Algebras. Limitations of propositional logic: Informal introduction to quantifiers and syllogisms. |
| − | 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. | + | (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. |
| − | Sets: 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. | + | (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. |
| − | Relations: Properties of relations. Special relations: Equivalence relations, partially ordered sets, totally ordered sets. | + | (4) Relations: Properties of relations. Special relations: Equivalence relations, partially ordered sets, totally ordered sets. |
| − | Functions: Operations of functions, direct image and inverse image. | + | (5) Functions: Operations of functions, direct image and inverse image. |
| − | Well-ordered sets: Correspondence between well-ordering relations and induction. Correspondence between well-ordering relations and choice functions. | + | (6) Well-ordered sets: Correspondence between well-ordering relations and induction. Correspondence between well-ordering relations and choice functions. |
| − | Introduction to computability. Classical models of computation (recursive functions, and Turing models). Limitations of computation (the Halting Problem, the busy beaver problem, fast-growing functions). Contemporary models of computation. | + | (7) Introduction to computability. Classical models of computation (recursive functions, and Turing models). Limitations of computation (the Halting Problem, the busy beaver problem, fast-growing functions). Contemporary models of computation. |
Revision as of 15:45, 18 March 2023
Introduction to basic discrete structures.
Sample textbooks:
[1] Gordon Pace, Mathematics of Discrete Structures foe Computer Science, Springer, 2012
[2] Vladlen Koltun, Discrete Structures Lecture Notes, Stanford University, 2008.link
Catalog entry
Prerequisite: Algebra and Number Systems (MAT 1313), or Discrete Mathematical Structures (CS 2233/2231), or instructor consent.
Contents: (1) Propositional logic: Axioms and Rules of Inference. Boolean Algebras. Limitations of propositional logic: Informal introduction to quantifiers and syllogisms. (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: Properties of relations. Special relations: Equivalence relations, partially ordered sets, 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, the busy beaver problem, fast-growing functions). Contemporary models of computation.
Topics List
| Week | Topic | Sections from Pace's book | Calculus 2 |
|---|---|---|---|
| 1 | Propositional logic | 2.1-2.4 | Undergraduate real analysis. |
| 3-4 | Completeness and soundness | 2.5-2.7. | |
| 4-5 | Predicate calculus | 3.1-3.5 | |
| 6-7 | Sets and boolean algebras | 4.1-4.8 | |
| 8 | Relations | 5.1-6.3 | |
| 9-10 | Discrete structures | 7.1-8.4 | |
| 10-16 | Models of computation | 10.1-10.4 |
