MCA-102 Mathematical Foundation of Computer Science:

UNIT-I

Sets, Relations and Functions:

Sets, Subsets, Power sets, Complement, Union and Intersection, Demorgan’s law Cartesian products,

Relations, relational matrices, properties of relations, equivalence relation, functions ,Injection, Surjection

and Bijective mapping, Composition of functions, the characteristic functions and Mathematical

induction.

UNIT-II

Proportions & Lattices :

Proposition & prepositional functions, Logical connections Truth-values and Truth Table, the algebra of

prepositional functions-the algebra of truth values-Applications (switching circuits, Basic Computer

Components).

Partial order set, Hasse diagrams, upper bounds, lower bounds, Maximal and minimal element, first and

last element, Lattices, sub lattices, Isotonicity , distributive inequality, Lattice homomorphism, lattice

isomorphism ,complete lattice ,complemented lattice distribution lattice .

UNIT-III

Groups and Fields:

Group axioms ,permutation group, sub group, co-sets, normal subgroup, semi group, Lagrange theorem,

fields, minimal polynomials, reducible polynomials, primitive polynomial, polynomial roots, applications.

UNIT-IV

Graphs:

Finite graphs, incidence and degree, isomorphism, sub graphs and union of graphs, connectedness, walk,

paths, and circuits Eulerian graphs ,tree properties of trees, pendant vertices in tree, center of tree

,spanning trees and cut vertices, binary tree ,matrix representation of graph, incidence and adjacency

matrix and their properties, applications of graphs in computer science.

UNIT-V

Discrete Numeric function and Recurrence relation:

Introduction to discrete numeric functions and generating functions introduction to recurrence relations

and recursive algorithms, linear recurrence relations with constant coefficients, homogeneous solutions,

particular solutions and total solutions

BOOKS:

1. J.P.Trembley & R.P.Manohar “Discrete Mathematical Structure with applications to Computer

Science”.

2. Kenneth H. Rosen-203 “Discrete Math & its Applications” 5th ed.

3. K.A. Ross and C.R.B. Writht “Discrete Mathematics “.

4. Bernard Kolman & Robert C. Busby “Discrete Mathematical Structures for Computer Science”.

--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------