Difference between revisions of "MAT3003"

From Department of Mathematics at UTSA
Jump to navigation Jump to search
Line 1: Line 1:
Introduction to basic discrete structures.  
+
Introduction to the mathematics of discrete structures for computer science.  
  
 
'''Sample textbooks''':  
 
'''Sample textbooks''':  
Line 28: Line 28:
 
==Topics List==
 
==Topics List==
 
{| class="wikitable sortable"
 
{| class="wikitable sortable"
! Week !! Topic !! Sections from Pace's book !! MAT1313, or CS2233/2231, or instructor consent.
+
! Week !! Topic !! Sections from Pace's book !! !! Sections from Pace's book !! Prerequisites.
 
|-
 
|-
 
|  1   
 
|  1   
 
|| [[Propositional logic]]
 
|| [[Propositional logic]]
 
|| 2.1-2.4
 
|| 2.1-2.4
 +
||
 +
* Proofs
 +
* boolean models
 +
* connections between boolean models and proofs
 
|| MAT1313 or CS2233/2231, or equivalent.
 
|| MAT1313 or CS2233/2231, or equivalent.
 
|-
 
|-
 
|  2   
 
|  2   
 
|| [[Completeness and soundness]]
 
|| [[Completeness and soundness]]
|| 2.5-2.7.
+
|| 2.5
 +
|| Completeness and soundness of propositional logic
 
||  
 
||  
 
|-
 
|-
3-4    
+
5-6    
 
|| [[Predicate calculus]]
 
|| [[Predicate calculus]]
 
|| 3.1-3.5
 
|| 3.1-3.5
 +
||
 +
* Limits of propositional logic
 +
* free variables and substitution.
 
||  
 
||  
 
|-
 
|-
|  5-6    
+
|  5   
 
|| [[Sets and boolean algebras]]
 
|| [[Sets and boolean algebras]]
|| 4.1-4.8
+
|| 4.1-4.5
 
||  
 
||  
 +
* Set comprehension.
 +
* Finitary and general operations on sets.
 +
||
 +
|-
 +
|  6 
 +
|| [[Sets and boolean algebras]]
 +
|| 4.6
 +
|| Boolean algebras and boolean rings.
 +
||
 
|-
 
|-
|  7-8    
+
|  7   
 
|| [[Relations]]  
 
|| [[Relations]]  
|| 5.1-6.3
+
|| 5.1-5.7
 +
||
 +
* Relations and sets
 +
* Inverse of a relation and composition of relations
 +
* Beyond binary relations
 +
||
 +
|-
 +
|  8 
 +
|| [[Classifying Relations]]
 +
|| 6.1-6.3
 
||  
 
||  
 +
* Totality
 +
* Surjectivity
 +
* Injectivity
 +
* Functionality
 +
||
 
|-
 
|-
 
|  9-10   
 
|  9-10   
Line 59: Line 90:
 
|| 7.1-8.4
 
|| 7.1-8.4
 
||  
 
||  
 +
* Graphs
 +
* Semigroups
 +
* groups
 +
||
 
|-
 
|-
 
|  11-13   
 
|  11-13   
|| [[Mathematical models of computation]]  
+
|| [[Reasoning about programs]]  
 
|| 10.1-10.4
 
|| 10.1-10.4
 
||  
 
||  
 +
* Algorithms
 +
* Program semantics
 +
* Uncomputability
 +
||
 
|}
 
|}

Revision as of 16:34, 24 March 2023

Introduction to the mathematics of discrete structures for computer science.

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 here.


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. 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: 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.




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.
5 Sets and boolean algebras 4.1-4.5
  • Set comprehension.
  • Finitary and general operations on sets.
6 Sets and boolean algebras 4.6 Boolean algebras and boolean rings.
7 Relations 5.1-5.7
  • Relations and sets
  • Inverse of a relation and composition of relations
  • Beyond binary relations
8 Classifying Relations 6.1-6.3
  • Totality
  • Surjectivity
  • Injectivity
  • Functionality
9-10 Discrete structures 7.1-8.4
  • Graphs
  • Semigroups
  • groups
11-13 Reasoning about programs 10.1-10.4
  • Algorithms
  • Program semantics
  • Uncomputability