Discrete Mathematical Structures, As per AICTE

Y N Singh

ISBN: 9788126511952

364 pages

INR 699

Description

The purpose of the subject Discrete Mathematical Structures is to develop the understanding of theoretical foundations of Computer Science. The emphasis is given on the applications of discrete structures in computer science. Discrete structures include important material from areas such as Set Theory, Proving Methods, Algebraic Structures, Logic, Graphs, Trees, Recurrences and Combinatorics.

Chapter 1 Set Theory

1.1 Introduction

1.2 Empty Set

1.3 Size of Sets and Cardinals

1.4 Venn Diagram

1.5 Subsets

1.6 Combinations of Sets

1.7 Multisets

1.8 Ordered Pairs

1.9 Set Identities

 

Chapter 2 Relations

2.1 Introduction

2.2 Properties of Relations

2.3 Representation of Relations

2.4 Composite Relations

2.5 Order of Relations

 

Chapter 3 Functions

3.1 Introduction

3.2 Classification of Functions

3.3 Operations on Functions

3.4 Recursively Defined Functions

 

Chapter 4 Natural Numbers

4.1 Introduction

4.2 Mathematical Induction

4.3 Induction Examples

4.4 Variants of Induction

 

Chapter 5 Algebraic Structures

5.1 Introduction

5.2 Groups

5.3 Subgroups and Order

5.4 Cyclic Groups

5.5 Cosets

5.6 Normal Subgroups

5.7 Permutation and Symmetric Groups

5.8 Group Homomorphisms

5.9 Rings

5.10 Fields

5.11 Integers Modulo n

 

Chapter 6 Lattices

6.1 Introduction

6.2 Partial Order Sets

6.3 Preorder

6.4 Combinations of Partial Order Sets

6.5 Hasse Diagram

6.6 Bounds

6.7 Lattices

6.8 Properties of Lattices

6.9 Morphisms of Lattices

 

Chapter 7 Boolean Algebra

7.1 Introduction

7.2 Boolean Operators and Precedence

7.3 Axiomatics of Boolean Algebra

7.4 Theorems of Boolean Algebra

7.5 Boolean Expressions and Functions

7.6 Algebraic Manipulation of Boolean Expressions

7.7 Simplification of Boolean Functions

7.8 Logic Gates

7.9 Digital Circuits and Boolean Algebra

7.10 Combinational Circuits

7.11 Sequential Circuits

 

Chapter 8 Propositional Logic

8.1 Introduction

8.2 Sentences

8.3 Statements

8.4 Propositional Logic

8.5 Theory of Inference

8.6 Natural Deduction

8.7 Predicate Logic

 

Chapter 9 Trees

9.1 Binary Trees

9.2 Binary Tree Representation

9.3 Binary Tree Traversal

9.4 Evaluation of Binary Expression Trees

9.5 Binary Search Trees

 

Chapter 10 Graphs

10.1 Paths and Cycles

10.2 Connectivity

10.3 Subgraph

10.4 Contraction and Minors

10.5 Degree of a Vertex

10.6 Regular Graph

10.7 Representation of Graphs

10.8 Bipartite Graphs

10.9 Planar Graphs

10.10 Isomorphism and Homeomorphism of Graphs

10.11 Multigraph

10.12 Euler Paths

10.13 Hamiltonian Paths

10.14 Graph Coloring

 

Chapter 11 Recurrence Relations

11.1 Linear Recurrences

11.2 Inhomogeneous Recurrences

11.3 Growth of Functions

11.4 Recurrences from Algorithms

 

Chapter 12 Generating Functions

12.1 Generation Functions

12.2 Generating Functions for Recurrences

12.3 Operations on Generating Functions

12.4 Generating Functions and Combinatorics

12.5 Useful Power Series

 

Chapter 13 Combinatorics

13.1 Counting Techniques

13.2 Pigeonhole Principle

13.3 Pólya's Counting Theory

 

Exercises