Mar 20, 2023
 HELP 2015-2016 Undergraduate Academic Catalog [ARCHIVED CATALOG] Print-Friendly Page (opens a new window)

# MA 2310 - Discrete Mathematics I

3 lecture hours 0 lab hours 3 credits
Course Description
This course provides an introduction to discrete mathematics as it applies to computer science. Topics include sets, logic, relations, functions, recursion, Boolean algebra, and graph theory. (prereq: MA 127  or equivalent, sophomore standing)
Course Learning Outcomes
Upon successful completion of this course, the student will be able to:
• Illustrate by examples the basic terminology of functions, relations, and sets
• Illustrate by examples, both discrete and continuous, the operations associated with sets, functions, and relations
• Apply functions and relations to problems in computer science
• Manipulate formal methods of symbolic propositional and predicate logic
• Demonstrate knowledge of formal logic proofs and logical reasoning through solving problems
• Illustrate by example the basic terminology of graph theory
• Apply logic to determine the validity of a formal argument
• Identify a relation; specifically, a partial order, equivalence relation, or total order
• Identify a function; specifically, surjective, injective, and bijective functions
• Illustrate by examples tracing Euler and Hamiltonian paths
• Construct minimum spanning trees and adjacency matrices for graphs

Prerequisites by Topic
• Basic concepts of college algebra
• Basic concepts of set theory

Course Topics
• Course introduction (1 class)
• Propositional logic: normal forms (conjunctive and disjunctive) (2 classes)
• Propositional logic: Validity (1 class)
• Fundamental structures: Functions (surjections, injections, inverses, composition) (2 classes)
• Fundamental structures: Relations (reflexivity, symmetry, transitivity, equivalence relations (1 class
• Fundamental structures: Discrete versus continuous functions and relations (1 class)
• Fundamental structures: Sets (Venn diagrams, complements, Cartesian products, power sets) (2 classes)
• Fundamental structures: Cardinality and countability (1 class)
• Boolean algebra: Boolean values, standard operations, de Morgan’s laws (1 class)
• Predicate logic: Universal and existential quantification (1 class)
• Predicate logic: Modus ponens and modus tollens (1 class)
• Predicate logic: Limitations of predicate logic (1 class)
• Recurrence relations: Basic formulae (1 class)
• Recurrence relations: Elementary solution techniques (1 class)
• Graphs: Fundamental definitions (1 class)
• Graphs: Directed and undirected graphs (1 class)
• Graphs: Spanning trees (1 class)
• Graphs: Shortest path (1 class)
• Graphs: Euler and Hamiltonian cycles (1 class)
• Graphs: Traversal strategies (1 class)
• Review and exams (4 classes)

Coordinator
Chunping Xie