Discrete Mathematical Structures Book

by V.B.L. Chaurasia, Amber Srivastava

Contents:
1. Sets and Set Theory
Introduction, Sets, Representation of a Set, Russel Paradox, Principle of Extension, Different Types of Sets, Equal Sets, Subsets, Null Set or Empty Set or Void Set, Finite Set, Infinite Set, Cardinality of A Finite Set, Set of Sets, Singleton Set or Singlet, Universal Set, Complement of a Set, Properties of Complementary Operation, Set S–T (Difference of Two Sets), Symmetric Difference of Two Sets, Power Set, Recursive Definition of A Set, Disjoint Sets, Comparable Sets, Non–Comparable Set, Important Sets of Numbers, Venn Diagrams, Algebra of Sets, Union Operation, Properties of Union Operation, Intersection Operation, Properties of Intersection Operation, Distributive Properties, Duality, Principle of Duality, Partitions, Addition Principle, Illustrative Examples, Exercise 1.1, Answer Key.

2. Functions
Concept of a Function, Functions (or Mapping), f-image, f–set, Function as a Set of Ordered Pairs, Representation by a Diagram, Domain, Co–Domain and Range of a Function, Constant Function, Identity Function, Equal Functions, Sum and Product of Functions, Special Functions, Polynomial Function, Exponential Function, Logarithmic Functions, Absolute Value Function, Floor Function or Greatest Integer Function, Ceiling Function, Mod Functions, Div Functions, Characteristic Function, Properties of Functions, Diagrammatic Representation of Different Kinds of Mappings, Inclusion Mapping, Cardinally Equivalent Sets, Inverse of a Function (Inverse Mapping), Product of Mappings or Composite of Functions, Properties of Composite of Functions, Cardinality of an Infinite Set, Countable and Uncountable Sets, The Pigeonhole Principle, The Generalized Pigeonhole Principle, Exercise 2.1, Answer Key.

3. Relations
Introduction, Boolean Matrix, Join and Meet of Boolean Matrices, Product of Boolean Matrices, Properties of Boolean Matrices, Ordered Pairs, Cartesian Product of Sets, Relations, Domain and Range, Relation in a Set, Empty Relation, Universal Relation, Identity Relation, Inverse Relation, R–Relative Set of an Element x, Graph of a Relation, Adjacency Matrix of a Relation, Representing Relations using Digraphs, Binary Relation, Properties of Relations, Connectivity Relation, Closure of Relations, Transitive Closure: Warshall’s Algorithm, Equivalence Relation, Congruency Relation Modulo System, Addition Modulo m, Multiplication Modulo m, Equivalence Classes, Properties of Equivalence Classes, Partition of a Set, Product of Equivalence Relations, Number of Partitions of a Finite Set, Illustrative Examples, Exercise 3.1, Partial Order Relation, Comparability, Total Order Relation or Linear Order Relation, Digraph of a POSET, Hasse Diagram, Illustrative Examples, Exercise 3.2, Answer Key.

4. Language of Logic
Introduction, Statement or Proposition, Propositional Variables, Logical Connectives and Compound Statements, Negation, Conjunction, Disjunction, Conditional Statement (or Implication), Converse and Contrapositive, Biconditional Statement, Tautology, Contradiction and Contingency, Logical Equivalence, Operations For Propositions, Predicates and Quantifiers, Properties of Quantifiers, Illustrative Examples, Exercise 4.1, Duality Law, Normal Forms, Some Basic Terms Related to Normal Form, Disjunctive Normal Form (DNF), Conjunctive Normal Form (CNF), Principal Disjunctive Normal Form (PDNF), Principal Conjunctive Normal Form (PCNF), To Obtain PCNF From PDNF and Vice-Versa, Arguments, Validity of Arguments using Truth Tables, Proof of Correctness of Arguments using the Theory of Inference, Rules of Inference For Statement Calculus, Rules of Inference For Quantified Statements, Illustrative Examples, Exercise 4.2, Answer Key.

5. Techniques of Proving Theorems
Introduction, Methods of Proof of an Implication, Vacuous Proof, Trivial Proof, Direct Proof, Indirect Proof or Proof by Contrapositive, Proof by Exhausting Cases, Proof by Contradiction, Existence Proof: Constructive and Nonconstructive, Constructive Proof, Nonconstructive Proof, Proof by Counter Example, The Division Algorithm, Divisibility Properties, Prime Numbers and Composite Numbers, Principle of Mathematical Induction, Second Principle of Mathematical Induction (or Complete Induction), The Fundamental Theorem of Arithmetic, Illustrative Examples, Exercise 5.1, Algorithm Correctness, Loop Invariants, Partial Correctness of Searching and Sorting Algorithms, Searching Algorithms, Sorting Algorithms, Exercise 5.2.

6. Graph Theory
Introduction, Graph G = (V, E), Directed Graph G = (V, E), Undirected Graph, Mixed Graph, Isolated Vertex, Null Graph, Self Loop, Initial and Terminal Vertices, Parallel Edges or Multiple Edges, Simple Graph, Finite and Infinite Graph, Order of a Graph, Size of a Graph, Adjacent Edges and Adjacent Vertices, Matrix Representation of Graphs, Incidence Matrix, Degree of a Vertex, Pendant Vertex, Even and Odd Vertices, Degree of a Vertex in a Directed Graph, Degree Sequence of a Graph...

510 pages, Paperback