MA1256 DISCRETE MATHEMATICS 3 1 0 100

AIM

To extend student’s mathematical maturity and ability to deal with abstraction and to introduce most of the basic terminologies used in computer science courses and application of ideas to solve practical problems.

OBJECTIVES

At the end of the course, students would

• Have knowledge of the concepts needed to test the logic of a program.

• Have gained knowledge which has application in expert system, in data base and a basic for the prolog language.

• Have an understanding in identifying patterns on many levels.

• Be aware of a class of functions which transform a finite set into another finite set which relates to input output functions in computer science.

• Be exposed to concepts and properties of algebraic structures such as semigroups, monoids and groups.

UNIT I PROPOSITIONAL CALCULUS 10 + 3

Propositions – Logical connectives – Compound propositions –

Conditional and biconditional propositions – Truth tables – Tautologies and contradictions – Contrapositive – Logical equivalences and implications – DeMorgan’s Laws - Normal forms – Principal conjunctive and disjunctive normal forms – Rules of inference – Arguments - Validity of arguments.

UNIT II PREDICATE CALCULUS 9 + 3

Predicates – Statement function – Variables – Free and bound variables – Quantifiers – Universe of discourse – Logical equivalences and implications for quantified statements – Theory of inference – The rules of universal specification and generalization – Validity of arguments.

UNIT III SET THEORY 10 + 3

Basic concepts – Notations – Subset – Algebra of sets – The power set – Ordered pairs and Cartesian product – Relations on sets –Types of relations and their properties – Relational matrix and the graph of a relation – Partitions – Equivalence relations – Partial ordering – Poset – Hasse diagram – Lattices and their properties – Sublattices – Boolean algebra – Homomorphism.

UNIT IV FUNCTIONS 7 + 3

Definitions of functions – Classification of functions –Type of functions - Examples – Composition of functions – Inverse functions – Binary and n-ary operations – Characteristic function of a set – Hashing functions – Recursive functions – Permutation functions.

UNIT V GROUPS 9 + 3

Algebraic systems – Definitions – Examples – Properties – Semigroups – Monoids – Homomorphism – Sub semigroups and Submonoids - Cosets and Lagrange’s theorem – Normal subgroups – Normal algebraic system with two binary operations - Codes and group codes – Basic notions of error correction - Error recovery in group codes.

TUTORIAL 15

TOTAL : 60

TEXT BOOKS

1. Trembly J.P and Manohar R, “Discrete Mathematical Structures with Applications to Computer Science”, Tata McGraw–Hill Pub. Co. Ltd, New Delhi, 2003.

2. Ralph. P. Grimaldi, “Discrete and Combinatorial Mathematics: An Applied Introduction”, Fourth Edition, Pearson Education Asia, Delhi, 2002.

REFERENCES

1. Bernard Kolman, Robert C. Busby, Sharan Cutler Ross, “Discrete Mathematical Structures”, Fourth Indian reprint, Pearson Education Pvt Ltd., New Delhi, 2003.

2. Kenneth H.Rosen, “Discrete Mathematics and its Applications”, Fifth Edition, Tata McGraw – Hill Pub. Co. Ltd., New Delhi, 2003.

3. Richard Johnsonbaugh, “Discrete Mathematics”, Fifth Edition, Pearson Education Asia, New Delhi, 2002.

AIM

To extend student’s mathematical maturity and ability to deal with abstraction and to introduce most of the basic terminologies used in computer science courses and application of ideas to solve practical problems.

OBJECTIVES

At the end of the course, students would

• Have knowledge of the concepts needed to test the logic of a program.

• Have gained knowledge which has application in expert system, in data base and a basic for the prolog language.

• Have an understanding in identifying patterns on many levels.

• Be aware of a class of functions which transform a finite set into another finite set which relates to input output functions in computer science.

• Be exposed to concepts and properties of algebraic structures such as semigroups, monoids and groups.

UNIT I PROPOSITIONAL CALCULUS 10 + 3

Propositions – Logical connectives – Compound propositions –

Conditional and biconditional propositions – Truth tables – Tautologies and contradictions – Contrapositive – Logical equivalences and implications – DeMorgan’s Laws - Normal forms – Principal conjunctive and disjunctive normal forms – Rules of inference – Arguments - Validity of arguments.

UNIT II PREDICATE CALCULUS 9 + 3

Predicates – Statement function – Variables – Free and bound variables – Quantifiers – Universe of discourse – Logical equivalences and implications for quantified statements – Theory of inference – The rules of universal specification and generalization – Validity of arguments.

UNIT III SET THEORY 10 + 3

Basic concepts – Notations – Subset – Algebra of sets – The power set – Ordered pairs and Cartesian product – Relations on sets –Types of relations and their properties – Relational matrix and the graph of a relation – Partitions – Equivalence relations – Partial ordering – Poset – Hasse diagram – Lattices and their properties – Sublattices – Boolean algebra – Homomorphism.

UNIT IV FUNCTIONS 7 + 3

Definitions of functions – Classification of functions –Type of functions - Examples – Composition of functions – Inverse functions – Binary and n-ary operations – Characteristic function of a set – Hashing functions – Recursive functions – Permutation functions.

UNIT V GROUPS 9 + 3

Algebraic systems – Definitions – Examples – Properties – Semigroups – Monoids – Homomorphism – Sub semigroups and Submonoids - Cosets and Lagrange’s theorem – Normal subgroups – Normal algebraic system with two binary operations - Codes and group codes – Basic notions of error correction - Error recovery in group codes.

TUTORIAL 15

TOTAL : 60

TEXT BOOKS

1. Trembly J.P and Manohar R, “Discrete Mathematical Structures with Applications to Computer Science”, Tata McGraw–Hill Pub. Co. Ltd, New Delhi, 2003.

2. Ralph. P. Grimaldi, “Discrete and Combinatorial Mathematics: An Applied Introduction”, Fourth Edition, Pearson Education Asia, Delhi, 2002.

REFERENCES

1. Bernard Kolman, Robert C. Busby, Sharan Cutler Ross, “Discrete Mathematical Structures”, Fourth Indian reprint, Pearson Education Pvt Ltd., New Delhi, 2003.

2. Kenneth H.Rosen, “Discrete Mathematics and its Applications”, Fifth Edition, Tata McGraw – Hill Pub. Co. Ltd., New Delhi, 2003.

3. Richard Johnsonbaugh, “Discrete Mathematics”, Fifth Edition, Pearson Education Asia, New Delhi, 2002.

EmoticonEmoticon