M325K DISCRETE MATHEMATICS

Prerequisite:

M408D with a grade of at least C, or consent of instructor. This is a first course that

emphasizes understanding and creating proofs. Therefore, it provides a transition from

the problem-solving approach of calculus to the entirely rigorous approach of advanced

courses such as M365C or M373K. The number of topics required for coverage has been

kept modest so as to allow adequate time for students to develop theorem-proving skills:

Introductory combinatorics: counting principles, permutations with and without

repetitions, combinations and distributions.

Course Topics:

Fundamentals of logic:

truth tables, symbolic logic, elementary set theory, laws of set theory, Venn diagrams.

Functions:

relations, functions and their properties, Stirling numbers of the second kind, pigeonhole

principle.

Relations:

relation algebra, matrix representation of relations, directed graphs and relations, partial

orders, Hasse diagrams, lattices, equivalence relations, partitions.

Introductory graph theory:

Euler paths and cycles, planar graphs, Hamilton paths and cycles.