Difference between revisions of "MAT5423"

From Department of Mathematics at UTSA
Jump to navigation Jump to search
(Created page with "Introduction to basic discrete structures. Sample textbooks: [1] Gordon Pace, ''Mathematics of Discrete Structures foe Computer Science'', Springer, 2012 [2] Vladlen Koltu...")
 
Line 5: Line 5:
 
[1] Gordon Pace, ''Mathematics of Discrete Structures foe Computer Science'', Springer, 2012
 
[1] Gordon Pace, ''Mathematics of Discrete Structures foe Computer Science'', Springer, 2012
 
[2] Vladlen Koltun, ''Discrete Structures Lecture Notes, Stanford University'', 2008.[https://web.stanford.edu/class/cs103x/cs103x-notes.pdf link]
 
[2] Vladlen Koltun, ''Discrete Structures Lecture Notes, Stanford University'', 2008.[https://web.stanford.edu/class/cs103x/cs103x-notes.pdf link]
 +
 +
 +
Catalog entry
 +
 +
Prerequisite: Algebra and Number Systems (MAT 1313), or Discrete Mathematical Structures (CS 2233/2231), or instructor consent.
 +
 +
Contents:
 +
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.
 +
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.
 +
Relations: Properties of relations. Special relations: Equivalence relations, partially ordered sets, totally ordered sets.
 +
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.
 +
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==
 
==Topics List==
 
{| class="wikitable sortable"
 
{| class="wikitable sortable"
−
! Week !! Topic !! Sections from Pace's book !! Prerequisites
+
! Week !! Topic !! Sections from Pace's book !! Calculus 2
 
|-
 
|-
−
|  1-2    
+
|  1   
 
|| [[Propositional logic]]
 
|| [[Propositional logic]]
 
|| 2.1-2.4
 
|| 2.1-2.4
Line 22: Line 40:
 
|-
 
|-
 
|  4-5   
 
|  4-5   
−
|| [[Lebesgue measurable sets]]
+
|| [[Predicate calculus]]
−
|| 2.1-2.7
+
|| 3.1-3.5
 
||  
 
||  
 
|-
 
|-
−
|  7-9    
+
|  6-7   
−
|| [[Lebesgue measurable sets]]
+
|| [[Sets and boolean algebras]]
−
|| 2.1-2.7
+
|| 4.1-4.8
 
||  
 
||  
 
|-
 
|-
−
|  10-12    
+
|  8    
−
|| [[Lebesgue integration]]  
+
|| [[Relations]]  
−
|| 4.1-4.6
+
|| 5.1-6.3
 
||  
 
||  
 +
|-
 +
|  9-10 
 +
|| [[Discrete structures]]
 +
|| Graphs, trees, networks, and data
 +
|| 7.1-8.4
 +
|-
 +
|  10-16 
 +
|| [[Models of computation]]
 +
|| Graphs, trees, networks, and data
 +
|| 7.1-8.4
 
|}
 
|}

Revision as of 14:43, 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: 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. 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. Relations: Properties of relations. Special relations: Equivalence relations, partially ordered sets, totally ordered sets. 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. 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 Graphs, trees, networks, and data 7.1-8.4
10-16 Models of computation Graphs, trees, networks, and data 7.1-8.4
Retrieved from "https://mathresearch.utsa.edu/wiki/index.php?title=MAT5423&oldid=4820"