Bsc. I.T.

Discrete Mathematics Syllabus

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 NoDetails
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
Year 2007
Download Here
Title Discrete Mathematics and its Applications
Authors Kenneth H. Rosen
Publisher Tata MCGraw Hill
Download Here
Title Discrete mathematical structures
Authors B Kolman RC Busby, S Ross
Publisher PHI
Download Here
Title Discrete structures
Authors Liu
Publisher Tata MCGraw Hill
Download Here