## Discrete Mathematics

**Course Code: **CSE 2101

**Year:** 2 **Semester:** 1 **Credits:** 3

**Description:**

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

fields

**References:**

N/A