DISCRETE MATHEMATICS

Course Code: PCCST205

Course Objectives: 1. To equip students with the ability to analyze and solve problems using discrete mathematical techniques. 2. To give a deeper understanding of mathematical logic, set theory, and proof techniques such as direct proofs, proof by contradiction, and mathematical induction.

SYLLABUS

1. Sets, Functions, and Relations Sets and Subsets, Venn Diagrams, Set Operations, Set Identities, Generalized Unions and Intersections, The Principle of Inclusion-Exclusion (Basic and Generalized versions), and applications. Function definition, Injections, Surjections and Bijections, Inverse Functions, and Compositions of Functions, Cardinality of Sets, Cantor diagonalization argument Relations and Their Properties, Composition of relations, n-ary Relations, Representing Relations Using Matrices, Equivalence Relations, Equivalence Classes, Partial Orderings, Hasse Diagrams, Maximal and Minimal Elements, Lattices
2. Mathematical logic and proofs Propositional Logic, Applications of Propositional Logic, Propositional Equivalences, Predicates and Quantifiers, Nested Quantifiers, Rules of Inference Introduction to Proofs, Methods of Proving Theorems – Direct proof, Indirect proof (Proof by Contraposition), Proof by Contradiction, Proof by counter examples, The Pigeonhole Principle.
3. Induction and Recurrences Mathematical Induction, Weak and Strong induction Recursive (Inductive) definitions and recurrence relations, Modeling with Recurrence Relations, Solving Linear Recurrence Relations (homogeneous and nonhomogeneous), Generating Functions, Using Generating Functions to Solve Recurrence Relations.
4. Group theory
   Groups – Definition, Examples, and Elementary Properties, Abelian group, Permutation group, Subgroup, Homomorphisms, Isomorphisms, and Cyclic Groups, Cosets and Lagrange’s Theorem