Difference between revisions of "MAT3003"

From Department of Mathematics at UTSA
Jump to navigation Jump to search
Line 7: Line 7:
  
 
''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. Measure algebras and representation of measures.
−
(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''':  
 
'''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.]
 
[2] Vladlen Koltun, ''Discrete Structures Lecture Notes, Stanford University'', 2008. Freely available [https://web.stanford.edu/class/cs103x/cs103x-notes.pdf here.]

Revision as of 15:59, 21 January 2025

Introduction to the mathematics of discrete structures with emphasis on structures for computer science.


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. Measure algebras and representation of measures.


Sample textbooks:


[2] Vladlen Koltun, Discrete Structures Lecture Notes, Stanford University, 2008. Freely available here.




Topics List

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
  • Binary operations
  • Semigroups
  • groups
13-14 Reasoning about programs 10.1-10.4
  • Algorithms
  • Program semantics
  • Uncomputability
Retrieved from "https://mathresearch.utsa.edu/wiki/index.php?title=MAT3003&oldid=5294"