# Discrete Mathematics

Math 245
Fall 2002
Meeting: MWF, 12:00-13:00.
SS-1401
San Diego State University

Professor: Mike O'Sullivan
Email: m.osullivan@math.sdsu.edu
Office: Bus. Adm./Math Building #217, ext. 594-6697
Office Hours: MWF: 13:00-14:00, MW 18:45-19:30.
Other times: by appointment or good fortune (I will normally be in my office and available).

## Text

S. Epp, Discrete Mathematics with Applications, 2nd Ed.

## Course Description

Discrete mathematics is an exciting and rapidly growing area of mathematics which has important applications in computer science and in many high technology areas. For example, "secure" internet communication, efficient storage of data (e.g. jpeg) and robust communication networks are developed using techniques from discrete mathematics.

This course serves two main populations, students from mathematics and students from computer science. The course also has two distinct goals: one is to teach the basics of set theory, logic, combinatorics and graph theory. The other is to convey concepts essential to mathematics: absolute clarity and precision in definitions and statements of fact, and rigorous methods for establishing that a statement is true.

## Schedule

Here is a rough idea of the amount of time I expect to spend on each topic, and the order in which we will cover them. I am also open to suggestions if the class would like to spend more time on certain topics or cover items not listed here. A day by day schedule (see above) will be maintained to keep you informed of upcoming and past lectures.

 SECTIONS TOPICS TIME §1.1-4 Logic and logical arguments. 4 classes §2.1-3 Predicates and quantifiers. 3 classes §3.1-7 Proofs: direct, by counterexample, by indirect argument. 6 classes Some number theory. §5.1-3 Sets: subsets, union, intersection. 4 classes Venn diagrams. Algebra of set operations. Cartesian product, power set. §10.1-3,5 Relations. Reflexive, symmetric and transitive relations. 6 classes Equivalence relations. Partially ordered sets §7.1,3,4,5 Functions: one-to-one and onto functions. 4 classes Invertible functions. The pigeonhole principle. Composition of functions. §4.1-4 Sequences, mathematical induction 6 classes §8.1-3 Recursively defined sequences: 4 classes Finding explicit formulas, establishing the formulas by induction. §6.1-7 Combinatorics: Counting and the multiplication rule. 6 classes Permutations and combinations.