Bsc. I.T. - Discrete Mathematics
Bsc. I.T.

### Discrete Mathematics Syllabus

 Unit Details I Introduction: Variables, The Language of Sets, The Language of Relations and Function Set Theory: Definitions and the Element Method of Proof, Properties of Sets, Disproofs, Algebraic Proofs, Boolean Algebras, Russell’s Paradox and the Halting Problem. The Logic of Compound Statements: Logical Form and Logical Equivalence, Conditional Statements, Valid and Invalid Arguments II Quantified Statements: Predicates and Quantified Statements, Statements with Multiple Quantifiers, Arguments with Quantified Statements Elementary Number Theory and Methods of Proof: Introduction to Direct Proofs, Rational Numbers, Divisibility, Division into Cases and the Quotient-Remainder Theorem, Floor and Ceiling, Indirect Argument: Contradiction and Contraposition, Two Classical Theorems, Applications in algorithms. III Sequences, Mathematical Induction, and Recursion: Sequences, Mathematical Induction, Strong Mathematical Induction and the Well-Ordering Principle for the Integers, Correctness of algorithms, defining sequences recursively, solving recurrence relations by iteration, Second order linear homogenous recurrence relations with constant coefficients. general recursive definitions and structural induction. Functions: Functions Defined on General Sets, One-to-One and Onto, Inverse Functions, Composition of Functions, Cardinality with Applications to Computability IV Relations: Relations on Sets, Reflexivity, Symmetry, and Transitivity, Equivalence Relations, Partial Order Relations Graphs and Trees: Definitions and Basic Properties, Trails, Paths, and Circuits, Matrix Representations of Graphs, Isomorphism’s of Graphs, Trees, Rooted Trees, Isomorphism’s of Graphs, Spanning trees and shortest paths. V Counting and Probability: Introduction, Possibility Trees and the Multiplication Rule, Possibility Trees and the Multiplication Rule, Counting Elements of Disjoint Sets: The Addition Rule, The Pigeonhole Principle, Counting Subsets of a Set: Combinations, r-Combinations with Repetition Allowed, Probability Axioms and Expected Value, Conditional Probability, Bayes’ Formula, and Independent Events.

### Discrete Mathematics Practicals

 Practical No Details 1 Set Theory a Inclusion Exclusion principle. b Power Sets c Mathematical Induction 2 Functions and Algorithms a Recursively defined functions b Cardinality c Polynomial evaluation c Greatest Common Divisor 3 Counting a Sum rule principle b Product rule principle c Factorial d Binomial coefficients e Permutations f Permutations with repetitions g Combinations h Combinations with repetitions i Ordered partitions j Unordered partitions 4 Probability Theory a Sample space and events b Finite probability spaces c Equiprobable spaces d Addition Principle e Conditional Probability f Multiplication theorem for conditional probability g Independent events h Repeated trials with two outcomes 5 Graph Theory a Paths and connectivity b Minimum spanning tree c Isomorphism 6 Directed Graphs a Adjacency matrix b Path matrix 7 Properties of integers a Division algorithm b Primes c Euclidean algorithm d Fundamental theorem of arithmetic e Congruence relation f Linear congruence equation 8 Algebraic Systems a Properties of operations b Roots of polynomials 9 Boolean Algebra a Basic definitions in Boolean Algebra b Boolean algebra as lattices 10 Recurrence relations a Linear homogeneous recurrence relations with constant coefficients b Solving linear homogeneous recurrence relations with constant coefficients c Solving general homogeneous linear recurrence relations

### Discrete Mathematics Reference Books

 Title Discrete Mathematics with Applications Authors Sussana S. Epp Publisher Cengage Learning Edition 4th Year 2010 Download Here
 Title Discrete Mathematics, Schaum’s Outlines Series Authors Seymour Lipschutz, Marc Lipson Publisher Tata MCGraw Hill Edition Year 2007 Download Here
 Title Discrete Mathematics and its Applications Authors Kenneth H. Rosen Publisher Tata MCGraw Hill Edition Year Download Here
 Title Discrete mathematical structures Authors B Kolman RC Busby, S Ross Publisher PHI Edition Year Download Here
 Title Discrete structures Authors Liu Publisher Tata MCGraw Hill Edition Year Download Here