• ES Español
• EN English

5.9. Discrete Structures (Mandatory)

5.9.1. Justification ↑ Back to top

Discrete structures provide the theoretical foundation for computer science. This course introduces the essential mathematical tools used to model computational problems, including logic, set theory, and functions. Understanding these concepts is critical for developing rigorous reasoning skills and for the subsequent study of algorithms, databases, and formal languages.

5.9.2. Generales Goals ↑ Back to top

1. Understand the principles of mathematical logic and proof techniques.
2. Perform operations with sets, functions, and relations.
3. Apply basic counting techniques and recurrence relations to problems.
4. Develop the ability to think abstractly and solve problems formally.

5.9.3. Contribution to Outcomes ↑ Back to top

AG-C07) Computing Knowledge: Applies knowledge of mathematics, science, and computing. (Usage)

AG-C12) Applies computer science theory and software development fundamentals to produce computer-based solutions. (Usage)

5.9.4. Content ↑ Back to top

5.9.4.1. Discrete Mathematics (12 hours) [Skills AG-C07,AG-C12] ↑ Back to top

Bibliography: (Rosen, 2019; Lehman et al., 2018)

Topics

1. Logic: propositional and predicate logic, quantifiers, proofs
2. Sets: operations, cardinality, power sets, Cartesian products
3. Relations: properties, equivalence relations, partial orders
4. Functions: injective, surjective, bijective, composition, inverse
5. Advanced logic: proof systems, completeness, decidability
6. Advanced set theory: infinite sets, Cantor's diagonal argument

Learning Outcomes

1. Explain propositional and predicate logic [Explain]
2. Construct simple logical proofs [Apply]
3. Define basic set operations and relations [Explain]
4. Define properties of relations [Explain]
5. Define types of functions [Explain]

5.9.4.2. Discrete Mathematics (12 hours) [Skills AG-C07,AG-C12] ↑ Back to top

Bibliography: (Rosen, 2019; Velleman, 2019)

Topics

1. Logic: propositional and predicate logic, quantifiers, proofs
2. Advanced logic: proof systems, completeness, decidability
3. Advanced set theory: infinite sets, Cantor's diagonal argument
4. Advanced relations: closures, lattices
5. Advanced functions: recursive functions, computability

Learning Outcomes

1. Construct simple logical proofs [Apply]
2. Explain concepts of infinite sets and cardinality [Explain]
3. Apply closure operations to relations [Apply]
4. Determine if a relation is an equivalence relation [Apply]

5.9.4.3. Discrete Mathematics (12 hours) [Skills AG-C07,AG-C12] ↑ Back to top

Bibliography: (Rosen, 2019; Scheinerman, 2012)

Topics

1. Relations: properties, equivalence relations, partial orders
2. Functions: injective, surjective, bijective, composition, inverse
3. Graphs: definitions, paths, cycles, trees, connectivity
4. Advanced graph theory: planarity, coloring, networks

Learning Outcomes

1. Determine if a relation is an equivalence relation [Apply]
2. Compose functions and find inverses [Apply]
3. Define basic graph concepts [Explain]
4. Solve basic graph problems [Apply]
5. Analyze advanced graph properties [Evaluate]

5.9.4.4. Discrete Mathematics (12 hours) [Skills AG-C07,AG-C12] ↑ Back to top

Bibliography: (Rosen, 2019; Grimaldi, 2003)

Topics

1. Counting: permutations, combinations, binomial theorem
2. Advanced counting: generating functions, inclusion-exclusion
3. Recurrence relations: solving simple recurrences
4. Advanced recurrence: generating functions, asymptotic behavior

Learning Outcomes

1. Explain permutations and combinations [Explain]
2. Apply counting techniques to solve problems [Apply]
3. Define recurrence relations [Explain]
4. Solve simple recurrence relations [Apply]
5. Develop generating functions for counting problems [Create]

5.9.5. Bibliography ↑ Back to top

Rosen, K. H. (2019). Discrete Mathematics and Its Applications. McGraw-Hill Education, 8th edition.

Lehman, E., Leighton, F. T., and Meyer, A. R. (2018). Mathematics for Computer Science. MIT OpenCourseWare.

Velleman, D. J. (2019). How to Prove It: A Structured Approach. Cambridge University Press, 3rd edition.

Scheinerman, E. A. (2012). Mathematics: A Discrete Introduction. Cengage Learning, 3rd edition.

Grimaldi, R. P. (2003). Discrete and Combinatorial Mathematics: An Applied Introduction. Pearson, 5th edition.