DISCRETE MATHEMATICS

Paper Code: 
GBCA 301
Credits: 
06
Periods/week: 
06
Max. Marks: 
100.00
Objective: 

This module is designed to acquaint students with the basic concepts of matrices and determinants, coordinate geometry, relations and graphs.

18.00
Unit I: 
Set Theory

Set Theory: Definition of Sets, Venn Diagrams, complements, Cartesian products, power sets, counting principle, cardinality and countability (Countable and Uncountable sets), proofs of some general identities on sets, Permutations and Combinations, Pigeonhole Principle, Principles of Inclusion-Exclusion, Mathematical induction, Recurrence relation.

18.00
Unit II: 
Propositional logic

Propositional logic: Proposition logic, basic logic, logical connectives, truth tables, tautologies, contradiction, normal forms (conjunctive and disjunctive), modus ponens and modus tollens, validity, predicate logic, universal and existential quantification. Notion of proof: proof by implication, converse, inverse, contrapositive, negation, and contradiction, direct proof, proof by using truth table, proof by counter example.

 

18.00
Unit III: 
Ordered Relations & Structures

Ordered Relations & Structures: Partially orderd sets, external elements of partially ordered sets, Lattices & Boolean Algebra: Relation to partial ordering, lattices, Hasse Diagram,  Axiomatic definition of Boolean algebra as algebraic structures with two operations basic results truth values and truth tables, the algebra of propositional functions, Boolean algebra of truth values, Applications (Switching Circuit, Gate Circuit).

18.00
Unit IV: 
Relation & Diagraphs

Relation & Diagraphs: Product sets & Partitions, Relations & diagraphs, paths in relation & diagraphs, properties of relations, Equivalence relations, manipulation of relations.

Trees:  Introduction, labeled trees, m-ary trees, undirected trees, properties of tree, Trees, Binary trees, Binary search trees and traversals, Spanning tree, Minimal spanning tree (Prim’s algorithm).

18.00
Unit V: 
Graphs Theory

Graphs Theory: Introduction to graphs, Graph terminology, Representing Graphs and Graph Isomorphism, Connectivity. Directed and undirected graphs and their matrix representations, reachability, Chains, Circuits, Eulers paths and cycles, Hamiltonian paths and cycles, Minima's Path Application(Flow charts and state transition Graphs, Algorithm for determining cycle and minimal paths), Graph coloring, shortest path algorithm (Djikstras algorithm).

ESSENTIAL READINGS: 
  1. Bernard Kolmann, Robert C. Busby and Sharon Ross, “Discrete Mathematical Structures”, Third edition, PHI, 1997.
  2. Kenneth G. Rosen: “Discrete Mathematics and Its Applications”, McGRAW‐Hill International Edition, Mathematics Series.  
  3. S. Lipschutz, Marc Lars Lipson, “Discrete Mathematics”, McGRAW‐HILL International Editions, Schaum’s Series. 
REFERENCES: 
  1. Alan Doerr, Kenneth Levaseur, “Applied Discrete Structures for Computer Sciences”, Galgotia Publications Pvt. Ltd. 
  2. G.N. Purohit, “Graph Theory”, Jaipur Publishing House.
  3. Babu Ram: “Discrete Mathematics and Its Applications”, Vinayaka Publications.  
  4. C.L. Liu, “Discrete Mathematics and Its Applications”, McGRAW‐Hill International Edition, Mathematics Series.  
  5. Trembley, “Discrete Mathematics and Its Applications”, Tata McGRAW‐Hill. 
Academic Year: 
2016-17
  • Printer-friendly version