Discrete Mathematics

Course Code: CSE 2101

Year: 2 Semester: 1 Credits: 3


Propositional and Predicate Calculus: Statements and Compound statements, conjunction, disjunction,
negation propositions and truth-tables, tautologies and contradictions logical equivalence, algebra of
propositions, conditionals, and bi-conditionals, logical implications, theory of inference of prepositional
calculus, predicates, statement functions, variables and quantifiers predicate formulas, free and bound
variables, theory of inference for the predicate calculus. Theory of Sets: Basic concepts sets and elements,
Venn diagram set operations algebra of sets duality classes of sets, power set. Introduction to Principles of
mathematical induction. Functions: Basic concept, graph of functions, one to one, onto functions.
Relations: Basic concepts, pictorial representation of relations inverse relations, compositor relations,
partitions properties of relations. Counting: Functions and counting, permutations and combinations, sum
rule principle, product rule principle, permutation, combination, pigeonhole principle, inclusion-exclusion
principle, Pascal triangle, ordered and unordered partitions. Posets and Lattice: Partial ordered sets,
lattices, bounded lattices distributed lattices.Integers. Definition and proof by induction. Functions on finite
sets. Divisibility. Eucildean algorithm. Exclusion inclusion principle. Euler's Function. Binomial
coefficients. Designs, t-designs. Permutation. Modular arithmetic and Euler's theorem. Examples and use of
recurrence relations and generating functions in counting problems. Graphs, Trees, Digraphs, Networks
and flows: graphs and their isomorphism. Valencey. Paths and cycles. Trees. Colouring the vertices of a
graph. Counting the leaves on a rooted tree. Spanning trees and the MST Problems. Bipartite graphs and
matching problems. Transversals for families of finite sets. Diagraphs, Networks and flows. The max -flow
and min-cut theorem. Finite Geometries: Cryptology and coding theory, Review of the theory of the finite