Discrete Mathematics

Program Class: Certificate/ B.SC.

Year: First

Semester: Second

Subject: Computer Science

                                        Course Title: Discrete Mathematics

Course Learning Outcomes:

The main objectives of the course are to:

• Introduce concepts of mathematical logic for analysing propositions and proving theorems.

• Use sets for solving applied problems, and use the properties of set operations

• algebraically.

• Work with relations and investigate their properties.

• Investigate functions as relations and their properties.

• Introduce basic concepts of graphs, digraphs and trees.

Credits: 4

Core Compulsory

Max. Marks: –25+75

Min. Passing Marks: 33

Unit

Topics

I

Mathematical Logic: Propositional and Predicate Logic, Propositional Equivalences, Normal Forms, Predicates and Quantifies, Nested Quantifiers, Rules of Inference.

II

Set and Relations: Set Operations, Representations and Properties of Relations, Equivalence Relations, Partially Ordering.

III

Group Theory: Groups, Subgroups, Semi Groups, Product and Quotients of Algebraic Structures, Isomorphism, Homomorphism, Automorphism, Rings, Integral Domains, Fields, Applications of Group Theory

IV

Graph Theory: Simple Graph, Multigraph, Weighted Graph, Paths and Circuits, Shortest Path in Weighted Graphs, Eulerian Path and Circuits, Hamiltonian Path and Circuits, Planner Graph, Graph Coloring, Bipartite Graphs, Trees and Rooted Trees, Prefix Codes, Tree Traversals, Spanning Trees and Cut-Sets.

V

Boolean Algebra: Boolean Functions and its Representations, Simplification of Boolean Functions.