Difference between revisions of "MAT5423"

From Department of Mathematics at UTSA
Jump to navigation Jump to search
Line 33: Line 33:
 
|| [[Propositional logic]]
 
|| [[Propositional logic]]
 
|| 2.1-2.4
 
|| 2.1-2.4
|| Undergraduate real analysis.
+
|| MAT1313 or CS2233/2231 or equivalent.
 
|-
 
|-
3-4    
+
2    
 
|| [[Completeness and soundness]]
 
|| [[Completeness and soundness]]
 
|| 2.5-2.7.
 
|| 2.5-2.7.
 
||  
 
||  
 
|-
 
|-
|  4-5    
+
3-4   
 
|| [[Predicate calculus]]
 
|| [[Predicate calculus]]
 
|| 3.1-3.5
 
|| 3.1-3.5
 
||  
 
||  
 
|-
 
|-
|  6-7    
+
5-6   
 
|| [[Sets and boolean algebras]]
 
|| [[Sets and boolean algebras]]
 
|| 4.1-4.8
 
|| 4.1-4.8
 
||  
 
||  
 
|-
 
|-
|  8-9    
+
7-8   
 
|| [[Relations]]  
 
|| [[Relations]]  
 
|| 5.1-6.3
 
|| 5.1-6.3
 
||  
 
||  
 
|-
 
|-
|  10   
+
9-10   
 
|| [[Discrete structures]]  
 
|| [[Discrete structures]]  
 
|| 7.1-8.4
 
|| 7.1-8.4

Revision as of 17:31, 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. 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. 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 MAT1313, or CS2233/2231, or instructor consent.
1 Propositional logic 2.1-2.4 MAT1313 or CS2233/2231 or equivalent.
2 Completeness and soundness 2.5-2.7.
3-4 Predicate calculus 3.1-3.5
5-6 Sets and boolean algebras 4.1-4.8
7-8 Relations 5.1-6.3
9-10 Discrete structures 7.1-8.4
11-13 Mathematical models of computation 10.1-10.4