Buch, Englisch, 552 Seiten, Format (B × H): 183 mm x 239 mm, Gewicht: 794 g
Buch, Englisch, 552 Seiten, Format (B × H): 183 mm x 239 mm, Gewicht: 794 g
ISBN: 978-0-19-806543-2
Verlag: Hurst & Co.
Discrete Mathematics is designed to serve as a textbook for undergraduate engineering students of computer science and postgraduate students of computer applications. The book would also prove useful to post graduate students of mathematics. The book seeks to provide a thorough understanding of the subject and present its practical applications to computer science.
Beginning with an overview of basic concepts like Sets, Relation and Functions, and Matrices, the book delves into core concepts of discrete mathematics like Combinatorics, Logic and Truth Tables, Groups, Order Relation and Lattices, Boolean Algebra, Trees, and Graphs. Special emphasis is also laid on certain advanced topics like Complexity and Formal Language and Automata. Algorithms and programmes have been used wherever required to illustrate the applications.
Written in a simple, student-friendly style, the book provides numerous solved examples and chapter end exercises to help students apply the mathematical tools to computer-related concepts.
Zielgruppe
Primary: B.Tech (CSE, IT), BCA, MCA
Autoren/Hrsg.
Fachgebiete
Weitere Infos & Material
CHAPTER 1: SET RELATION FUNCTION
1.1: INTRODUCTION
1.2: SETS
1.2.1: Representation of a Set
1.2.2: Sets of Special Status
1.2.3: Universal Set and Empty Set
1.2.4: Subsets
1.2.5: Power set
1.2.6: Cardinality of a Set
1.3: ORDERED PAIRS
1.3.1: Cartesian Product of Sets
1.3.2: Properties of Cartesian Product
1.4: VENN DIAGRAMS
1.5: OPERATIONS ON SETS
1.5.1: Union of Sets
1.5.2: Intersections of Set
1.5.3: Complements
1.5.4: Symmetric Difference
1.6: COUNTABLE AND UNCOUNTABLE SETS
1.7: ALGEBRA OF SETS
1.8: MULTISET
1.8.1: Operations on Multisets
1.9: FUZZY SET
1.9.1: Operations on Fuzzy Set
1.10: GROWTH OF FUNCTION
1.11: COMPUTER REPRESENTATION OF SETS
1.12: INTRODUCTION
1.13: BINARY RELATION
1.14: CLASSIFICATION OF RELATIONS
1.14.1: Reflexive Relation
1.14.2: Symmetric Relation
1.14.3: Antisymmetric Relation
1.14.4: Transitive Relation
1.14.5: Equivalence Relation
1.14.6: Associative Relation
1.15: COMPOSITION OF RELATIONS
1.16: INVERSE OF A RELATION
1.17: REPRESENTATION OF RELATIONS ON A SET
1.18: CLOSURE OPERATION ON RELATIONS
1.18.1: Reflexive Closure
1.18.2: Symmetric Closure
1.19: MATRIX REPRESENTATION OF RELATION
1.20: DIGRAPHS
1.20.1: Transitive Closure
1.20.2: Warshall's Algorithm
1.21: PARTIAL ORDERING RELATION
1.22: n-ARY RELATIONS AND THEIR APPLICATIONS
1.23: RELATIONAL MODEL FOR DATABASES
1.24: INTRODUCTION
1.25: ADDITION AND MULTIPLICATION OF FUNCTIONS
1.26: CLASSIFICATION OF FUNCTIONS
1.26.1: One-to-one (Injective) Function
1.26.2: Onto (Surjective) Functions
1.26.3: One-to-one, Onto (Bijective) Function
1.26.4: Identity Function
1.26.5: Constant Function
1.27: COMPOSITION OF FUNCTION
1.27.1: Associativity of Composition of Functions
1.28: INVERSE FUNCTION
1.28.1: Invertible Function
1.28.2: Image of a Subset
1.29: HASH FUNCTION
1.30: RECURSIVELY DEFINED FUNCTIONS
1.31: SOME SPECIAL FUNCTIONS
1.31.1: Floor and Ceiling Functions
1.31.2: Integer and Absolute Value Functions
1.31.3: Remainder Function
1.32: FUNCTIONS OF COMPUTER SCIENCE
1.32.1: Partial and Total Functions
1.32.2: Primitive Recursive Function
1.32.3: Ackermann Function
1.33: THE INCLUSION-EXCLUSION PRINCIPLE
1.33.1: Applications of Inclusion - Exclusion Principle
1.34: SEQUENCE AND SUMMATION
1.34.1: Sequence
1.34.2: Summation
Summary
Exercise 1
CHAPTER 2 COMBINATORICS
2.1: INTRODUCTION
2.2: BASIC PRINCIPLES OF COUNTING
2.2.1: Multiplication Principle (The Principles of Sequential Counting)
2.2.2: Addition Rule ( The Principle of Disjunctive Counting)
2.3: FACTORIAL NOTATION
2.4: BINOMIAL THEOREM
2.4.1: Pascal's Triangle
2.4.2: Multinomial Theorem
2.5: PERMUTATIONS (Arrangements of Objects)
2.5.1: Permutations with Repetitions
2.5.2: Circular Permutations
2.6: COMBINATIONS (Selection of Objects)
2.6.1: Combinations of n Different Objects
2.6.2: Combinations with Repetitions
2.7: DISCRETE PROBABILITY
2.7.1: Terminology (Basic Concepts)
2.8: FINITE PROBABILITY SPACES
2.9: PROBABILITY OF AN EVENT
2.9.1: Axioms of Probability
2.9.2: Odds in favour and Odds against an Event
2.9.3.: Addition Principle
2.10: CONDITIONAL PROBABILITY
2.10.1: Multiplication Rule
2.11: INDEPENDENT REPEATED TRIALS, BINOMIAL DISTRIBUTION
2.11.1: Repeated Trials with Two Outcomes, Bernoulli Trials
2.12: RANDOM VARIABLES
2.12.1: Probability Distribution of a Random Variable
2.12.2: Expectation of a Random Variable
2.12.3: Variance and Standard Deviation of a Random Variable
2.12.4: Binomial Distribution
2.13: RECURSION
2.13.1: Recursively Defined Sequences
2.13.2: Recursive Definitions
2.13.3: Recursively Defined Sets
2.13.4: Recursively Defined Functions
2.14: RECURENCE RELATION
2.14.1: Order and Degree of Recurrence Relation
2.14.2: Linear Homogenous and Non-homogeneous Recurrence Relations
2.14.3: Solution of Linear Recurrence Relation with Constant Coefficients
2.14.4: Homogenous Solution
2.14.5: Particular Solution
2.15: GENERATING FUNCTIONS
2.16: COUNTING (COMBINATORIAL) METHOD
2.17: THE PIGEONHOLE PRINCPLE
2.17.1: Generalized Pigeonhole Principle
Summary
Exercise 2
CHAPTER 3 MATHEMATICAL LOGIC
3.1: INTRODUCTION
3.2: STATEMENT (PROPOSITIONS)
3.3: LAWS OF FORMAL LOGIC
3.3.1: Law of Contradiction
3.3.2: Law of Intermediate Exclusion
3.4: BASIC SET OF LOGICAL OPERATORS /OPERATIONS
3.4.1: Conjunction (AND, )
3.4.2: Disjunction (OR, )
3.4.3: Negation (NOT, ~ )
3.5: PROPOSITIONS AND TRUTH TABLES
3.5.1: Connectives
3.5.2: Compound Propositions
3.5.3: Conditional Statement
3.5.4: Converse, Contrapositive, and Inverse
3.5.5: Biconditional Statement
3.6: ALGEBRA OF PROPOSITIONS
3.7: PROPOSITIONAL FUNCTIONS
3.8: TAUTOLOGIES AND CONTRADICTIONS
3.9: LOGICAL EQUIVALENCE
3.9.1: De Morgan Laws
3.10: LOGICAL IMPLICATION
3.11: NORMAL FORMS
3.11.1: Disjunctive Normal Form (dnf)
3.11.2: Conjunctive Normal Form (cnf)
3.12: ARGUMENTS
3.13: RULES OF INFERENCE
3.13.1: Law of Detachment (or Modus Pones)
3.13.2: Law of Contraposition (Modus tollens)
3.13.3: Disjunctive Syllogism
3.13.4: Hypothetical Syllogism
3.14: WELL FORMED FORMULAE
3.15: PREDICATE CALCULUS
3.16: QUANTIFIER
3.16.1: Universal Quantifier
3.16.2: Existential Quantifier
3.17: INTRODUCTION TO PROOFS
3.17.1: Brief Status of Terminology
3.17.2: Methods of Proof
3.17.3: Direct Proof
3.17.4: Consistency
3.17.5: Method of Proof by Contraposition
3.17.6: Proof by Contradiction (reduction ad absurdum)
3.17.7: Proof by Mathematical Induction
3.17.8: Proof by Cases
Summary
Exercise 3
CHAPTER 4 ALGEBRAIC STRUCTURE
4.1: INTRODUCTION
4.2: BINARY OPERATIONS
4.2.1: Properties of Binary Operations
4.3: GROUPS
4.3.1: Abelian Group
4.3.2: Properties of Groups
4.3.3: Products and Quotients of Groups
4.4: SEMIGROUPS
4.4.1: Isomorphism and Homomorphism
4.4.2: Products and Quotients of Semigroups
4.5: SUBGROUP
4.6: CYCLIC GROUP
4.7: PERMUTATION GROUPS
4.7.1: Equality of Permutations
4.7.2: Permutation Identity
4.7.3: Composition of Permutations (or, Product of Permutations)
4.7.4: Inverse Permutation
4.7.5: Cyclic Permutations
4.7.6: Transposition
4.7.7: Even and Odd Permutations
4.8: SYMMETRIC GROUP
4.9: COSETS
4.9.1: Properties of Cosets
4.10: NORMAL SUBGROUP
4.11: LAGRANGE'S THEOREM
4.12: GROUP CODES
4.12.1: Coding of Binary Information
4.12.2: Parity and Generator Matrices
4.12.3: Decoding and Error Correction
4.13: ALGEBRAIC SYSTEMS WITH TWO BINARY OPERATIONS
4.13.1: Rings
4.13.2: Elementary Properties of a Ring
4.13.3: Special kinds of Rings
4.13.4: Integral Domain
4.13.5: Field
4.14: SUBRING
4.14.1: Ideal
4.14.2: Quotient Ring
4.14.3: Morphisms of Rings
4.14.4: Properties of Homomorphism of Ring
Summary
Exercise 4
Chapter 5 MATRIX ALGEBRA
5.1: INTRODUCTION
5.2: DEFINITION OF A MATRIX
5.3: TYPES OF MATRICES
5.3.1: Rectangular and Square Matrices
5.3.2: Row matrix or a row vector
5.3.3: Column matrix or a column vector
5.3.4: Zero or Null matrix
5.3.5: Diagonal elements of a matrix
5.3.6: Diagonal matrix
5.3.7: Scalar matrix
5.3.8: Unit Matrix or Identity Matrix
5.3.9: Comparable Matrices
5.3.10: Equal Matrices
5.3.11: Upper Triangular Matrix
5.3.12: Lower Triangular Matrix
5.4: OPERATIONS ON MATRICES
5.4.1: Addition of Matrices
5.4.2: Subtraction of Matrices
5.4.3: Scalar Multiple of a Matrix
5.4.4: Multiplication of Matrices
5.4.5: Properties of Matrix Multiplication
5.4.6: Positive Integral Powers of Matrices
5.4.7: Sub Matrix
5.4.8: Partition of Matrices
5.5: RELATED MATRICES
5.5.1: Transpose of a Matrix
5.5.2: Symmetric and Skew-Symmetric Matrix
5.5.3: Complex Matrices
5.5.4: Conjugate of a Matrix
5.5.5: Conjugate Transpose of a Matrix
5.5.6: Hermitian and Skew-Hermitian Matrices
5.6: DETERMINANT OF A MATRIX
5.6.1: Minor and Co-factor
5.6.2: Expansion of the determinant ( )
5.6.3: Difference between a Matrix and a Determinant
5.7: TYPICAL SQUARE MATRICES
5.7.1: Orthogonal Matrix
5.7.2: Unitary Matrix
5.7.3: Involutory Matrix
5.7.4: Idempotent Matrix
5.7.5: Nilpotent Matrix
5.8: ADJOINT AND INVERSE OF A MATRIX
5.8.1: Singular and Non-singular Matrices
5.8.2: Adjoint of a Square Matrix
5.8.3: Properties of Adjoint of a Matrix
5.9: INVERSE OF A MATRIX
5.9.1: Properties of Inverse of a Matrix
5.10: RANK OF A MATRIX
5.10.1: Elementary transformations (operations) of a matrix
5.11: BOOLEAN MATRIX OR A ZERO-ONE MATRIX
5.11.1: Operations on Zero-one Matrices
5.11.2: Boolean product of matrices
5.11.3: Echelon Matrix (Row Reduced Echelon Form)
5.11.4: Normal form of a Matrix
5.11.5: Procedure of reduction of a matrix A to its normal form
5.12: SOLUTION OF LINEAR AL GEBRAIC EQUATIONS
5.12.1: Linear Homogenous Equations (Ax = 0)
5.12.2: Linear Non-homogenous Equations (Ax = b)
5.12.3: Consistent and Inconsistent Equations
5.13: EIGEN VALUES AND EIGEN VECTORS
5.13.1: Determination of Eigen values and Eigen vectors
5.13.2: Linear Transformations
5.13.3: Properties of Eigen values and Eigen vectors
5.14: CAYLEY - HAMILTON THOREM
5.14.1: Inverse of the Matrix
Summary
Exercise 5
Chapter 6 ORDER RELATION AND LATTICE
6.1: INTRODUCTION
6.2: PARTIALLY ORDERED SET
6.2.1: Comparability of Elements
6.2.2: Linearly ordered set
6.3: HASSE DIAGRAM
6.3.1: Topological Sorting
6.3.2: Chain
6.3.3: Antichain
6.4: ISOMORPHISM
6.4.1: Isomorphic Ordered Sets
6.5: LEXICOGRAPHIC ORDERING
6.6: EXTREMAL ELEMENTS OF POSETS
6.6.1: Maximal Element
6.6.2: Minimal Element
6.6.3: Greatest and Least Elements
6.6.4: Upper and Lower Bounds
6.6.5: Least Upper Bound (Supremum)
6.6.6: Greatest Lower Bound (Infimum)
6.7: WELL-ORDERED SET
6.8: CONSISTENT ENUMERATIONS
6.9: LATTICES
6.9.1: Principle of Duality
6.9.2: Isotonocity Property
6.10: SUB LATTICES
6.11: DIRECT PRODUCT OF LATTICES
6.12: SOME SPECIAL CLASS OF LATTICES
6.12.1: Complete Lattice
6.12.2: Bounded Lattice
6.12.3: Properties of Bounded Lattice
6.12.4: Distributive Lattice
6.12.5: Modular Lattice
6.12.6: Complemented Lattices
6.12.7: Isomorphic Lattices
6.12.8: Join-irreducible
6.12.9: Meet-irreducible
6.13: LATTICE HOMOMORPHISM
Summary
Exercise 6
CHAPTER-7 BOOLEAN ALGEBRA
7.1: INTRODUCTION
7.2: LAWS ON BOOLEAN ALGEBRA
7.3: TRUTH TABLES ON BOOLEAN OPERATIONS
7.4: UNIQUE FEATURES OF BOOLEAN ALGEBRA
7.5: MINTERM AND MAXTERM
7.5.1: Boolean Expression in Sum of Products(SOP) and Product of
7.5.2: Sums(POS) Form or Normal Form
7.6: BOOLEAN FUNCTION
7.7: SWITICHING NETWORK FROM BOOLEAN EXPRESSION USING LOGIC GATES
7.8: KARNAUGH MAP
7.8.1: Rules used by K-map for simplification
7.8.2: Labeling of K-map Squares
Summary
Exercise 7
CHAPTER-8 COMPLEXITY
8.1: INTRODUCTION
8.2: ALGORITHM
8.2.1.: Basic Criteria of Algorithm
8.3.: DATA STRUCTURE
8.3.1.: Operations on Data Structure
8.3.2.: Categorizations of Data structure
8.3.2.1.: Array as Non-primitive Data Structure
8.3.2.2: Structure as Non-primitive Data Structure
8.3.3: Abstract Data Type
8.3.4: Linear and Non-linear Data Structure
8.4.: COMPLEXITY
8.4.1.: Idea on Complexity Function of any Algorithm
8.4.2: Asymptote and Its Behavior
8.4.3.: Why Asymptotic Notations to Express Inexact Running Time ?
8.4.4.: Counting Strategy for Operations in Algorithm
8.4.5: Discussion on Order of Complexity
8.4.6: Mathematical Definitions of Some Useful Asymptotic Notations
8.4.6.1.: Big oh
8.4.6.2.: Big Omega
8.4.6.3: Theta
8.4.6.4.: Little Oh and Little Omega
8.4.7.: Standard Cases
8.4.8.: Some Properties of Time Complexity Functions
8.4.9: Complexity of Recursive Procedures
8.4.10: Solving Recurrence Relation T(n) = aT(n/b) +f(n) , a ? 1 , b > 0
8.4.11.: Comparison of Complexity
8.5.: SEARCHING AND SORTING
8.5.1.: Searching
8.5.1.1: Linear Search
8.5.1.2.: Binary Search
8.5.2.: Sorting
8.5.2.1.: Merge Sorting
8.5.2.2.: Bubble Sorting
Summary
Exercise 8
CHAPTER -9 GRAPH
9.1.: INTRODUCTION
9.2: GRAPH AND BASIC TERMINOLOGIES
9.3.: TYPES OF GRAPH
9.4: SUB-GRAPH AND ISOMORPHIC GRAPH
9.5: OPERATIONS ON GRAPH
9.6.: REPRESENTATION OF GRAPH
9.6.1.: Matrix Representation
9.6.2.: Adjacency List Representation
9.6.3.: Advantages and Disadvantages of Matrix and Linked list representations
9.6.4: Incidence Matrix Representation of Graph
9.7.: GRAPH ALGORITHMS
9.7.1.: BFS
9.7.2: DFS
9.7.3: Single Source Shortest Path Problem, Dijkstra's Algorithm
9.8: EULER GRAPH FLEURY'S ALGORITHM
9.8.1: Some Useful Results on Euler Graph
9.9: HAMILTONIAN GRAPH
9.9.1: Useful Hints on Hamiltonian circuit
9.10: PLANAR GRAPH
9.11: COLOURING OF GRAPH
9.12: COMPONENT
9.13.: CUT VERTEX
9.14.: FLOW NETWORK
9.14.1: Ford-Fulkerson Algorithm
Summary
Exercise 9
CHAPTER -10 TREE
10.1.: INTRODUCTION
10.2.: TREE
10.2.1.: Common Terminologies on Tree
10.2.2.: Labeled Tree
10.2.3: Some Diagrams of Directed and Undirected Trees
10.2.4: Summary of the Basic Properties of Tree
10.2.5: m-ary Tree, Complete Binary Tree, Full Binary Tree
10.2.6.: Why skewed tree are considered as binary tree?
10.3.: SOME IMPORTANT RESULTS ON TREE
10.4.: SEQUENTIAL REPRESENTATION OF BINARY TREE
10.5.: OPERATIONS ON TREE
10.5.1.: Tree Traversal
10.5.2: More Discussions on Tree Traversals
10.5.3: Construction of unique Binary Tree when Pre-order and In-order
10.5.4: Traversal Sequences are given
10.5.5.: Algorithm to Construct Unique Binary Tree using Pre-order and In-order Sequences
10.6.: BINARY SEARCH TREE (BST)
10.6.1: Linked List Representation of Binary Tree
10.6.2.: Construction of Binary Search Tree
10.6.3. Useful Results from Binary Search Tree:
10.7.: RECURSIVE PROCEDURE FOR BINARY TREE TRAVERSAL
10.7.1.: Analysis of Time Complexities for Some Operations on Binary Tree
10.8.: PREDECESSOR AND SUCCESSOR NODE
10.9.: EXPRESSION TREE
10.10.: AVL TREE
10.11.: SPANNING TREE
10.11.1: Minimum Spanning Tree(MST), Prim's and Kruskal's algorithm
10.12.: GENERAL TREE
10.12.1.: Conversion of General Tree to Binary Tree
10.12.2.: Pre- order Traversal for General Tree
10.13.: SOME IMPORTANT APPLICATIONS OF TREE
Summary
Exercise 10
CHAPTER-11 FORMAL LANGUAGE AND AUTOMATA
11.1: INTRODUCTION
11. 2: MATHEMATICAL PRELIMINARIES
11. 3: AUTOMATA
11.3.1: Basic Categories of Automata
11.3.1.1.: State Transition Graph
11.3.2: Finite Automaton and Its Types
11.3.2.1: Deterministic Finite Automaton(DFA)
11.3.2.2: Non-deterministic Finite Automaton(NDFA)
11.3.3: Importance of NDFA
11.3.4: Graphical Notations Used in this Chapter in Drawing Finite Automata
11.3.5: Discussion on Designing of Some Basic FA's
11.3.6: Some Basic Tips to Design FA
11.3.7: Conversion Strategy from NDFA to DFA
11.3.8: Finite Automaton with Output
11.3.8.1: Transformation of Moore m/c to Mealy m/c
11.3.8.2: Transformation of Mealy m/c to Moore m/c
11.4: REGULAR EXPRESSION
11.4.1: Minimization of FA
11.4.2: Brief Discussion to Derive R.Es
11.4.3: Solved Problems on R.E.
11. 4. 4: The Identities on Regular Expression
11. 4. 5: Rules for Constructing NDFA from Regular Expression
11. 4. 6: Tips to Get Quick Answer of Some Special Problems on FA and R.E.
11.4.7: Pumping Lemma for Regular Language
11. 4. 8: Applications of Finite Automata and Regular Expression
11.5: GRAMMAR
11. 5. 1: Formal Defination of Grammar
11. 5. 2: The Chomsky Hierarchy
11. 5. 3: Derivation(Parsing)
11. 5. 4: Parsing Techniques
11. 5. 5: Ambiguous Grammar
11. 5. 5.1: Demerits of Ambiguous Grammar
11. 5. 5.2: Making Disambiguous Grammar
11. 6: PUSHDOWN AUTOMATON (PDA)
11.6.1: Types of PDA
11. 7: TURING MACHINE (TM)
11.7.1: Improvement in TM
11.7.2: Variations of TMs
11.7.3: Halting Problem
11.7.4: Turing Acceptable Language
11.7.5: Properties of Recursive and Recursively Enumerable Languages
11.7.6: Church Thesis
11.8: POST CORRESPONDENCE PROBLEM(PCP)
11.9: CLASSES OF PROBLEMS
11.10: WHAT IS CELLULAR AUTOMATA ?
11.11: FUZZY SETS AND LOGIC
11.12: RUSSELL'S PARADOX
11.12.1: History of the paradox
Summary
Exercise 11
Appendix 1
References
