SYLLABUS

DISCRETE MATHEMATICS

Four credits

COURSE OBJECTIVES

To introduce the students to the Fundamentals of Logic, the Counting Principles, Relation, Recurrence Relations, Graphs and Trees, Boolean Algebras and Boolean Functions.

PREREQUISITES

- None

DETAILED COURSE OUTLINE

1. Fundamentals of Logic

1.1 Basic Connectives and Truth Tables. Bit Operations

1.2 Logical Equivalence and The Laws of Logics.

1.3 Predicates and Quantifiers.

1.4 Methods of Proofs.

1.5 Sets

1.6 Set Operations

1.7 Functions.

2. Counting Principles

2.1. The Basics of Counting

2.2. The Pigeon-Hole Principle

2.3. Permutations and Combinations.

2.4. Binomial Coefficients.

2.1 Generalized Permutations and Combinations.

3. Relations

3.1. Relations and Their Properties

3.2. n-ary Relations and Their Applications

3.3. Matrix Representation of a Relation

3.4. Equivalent Relations. Congruences. Arithmetic Operations on Zn

3.5. Partial Orderings. Hasse Diagram.

4. Recursion

4.1 Recursive Definitions

4.2 Recurrence Relations.

4.3 Solving Recurrence Relations

5. Graphs and Trees

5.1. Fundamental Concepts

5.2. Representing Graphs and Graph Isomorphisms.

5.3. Euler Paths and Circuits

5.4. Introduction to Trees

5.5. Applications of Trees

6. Boolean Algebra

6.1 Boolean Algebras and Boolean Functions: Truth Tables

6.2 The Normal Disjunctive Form.

6.3 Gate Networks. Gate Network Design and Minimal Disjunctive Forms

6.4 Karnaugh maps and Application to Find Minimal Disjunctive Forms

COURSE MATERIALS

1. Nguyen Huu Anh, Discrete Mathematics, The Education Publishing House, 2003.

2. K. Rosen, McGraw-Hill, Discrete Mathematics and its Applications,

Fifth Edition, 2003.

3. R.P. Grimaldi, Discrete and Combinatorial Mathematics, Addision-Wesley, 2004.

4. J. Velu, Methodes Mathematiques de l’ Informatique, Dunod, Paris, 1989.

5. K. Ross, Discrete Mathematics, 1976.