Contents

1.  Language of Logic

Objectives, Introduction, Statement or Proposition, Logical Connectives and Compound Statements, Tautology, Contradiction and Contingency, Logical Equivalence, Predicates and Quantifiers, Duality Law, Normal Forms, Arguments, Validity of Arguments using Truth Tables, Proof of Correctness of Arguments, llustrative Examples, Exercise, Answer Key.

2.  Techniques of Proving Theorems

Objectives, 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, Proof by Counter Example, The Division Algorithm, Divisibility Properties, Principle of Mathematical Induction, Second Principle of Mathematical Induction, The Fundamental Theorem of Arithmetic, Algorithm Correctness, Loop Invariants, Partial Correctness of Searching and Sorting Algorithms, Exercise.

3.  Graph Theory

Objectives, 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, Regular Graph, n–Regular Graph, The Size of n–Regular (s, t) Graph, Sub Graphs, Disjoint subGraphs, Induced Subgraph, Subgraph Ge, Connected Graphs and Disconnected Graphs, Distance and Diameter in a Graph, Complete Graph, Cycles, Wheels, Bipartite Graphs, Complete Bipartite Graphs, Weighted Graphs, Union of Simple Graphs, Intersection of Two Graphs, Ring–Sum of Two Graphs, Complementary Graph, Product of Two Graphs, Difference of Two Graphs, Decomposition of a Graph, Fusion of Vertices, Disjoint Graphs, Isomorphic Graphs, Self Complementary Graphs 3.43, Component of a Graph OR Maximal,Cut Sets, Bridge, Edge Connectivity, Vertex Connectivity, Separable Graph, Cut Vertex, Walk, Open Walk, Closed Walk, Length of Walk, Trai, Path, Circuit, Cycles, Euler Line (Chain), Euler Graph, Unicursal Line, Hamilton Path, Hamilton Graph, Certain Basic Rules Pertaining to, Certain Results of Importance, Complete Digraph, Planar Graph, Non–Planar Graph, Regions of a Graph, Properties of Region, Degree of Region, Euler’s Formula, Polyhedral Graph, Homeomorphic Graph , Kuratowski’s Two Graphs, Dual Graph, Chromatic Number, Welch–Powell Algorithm for Finding, Maximum Vertex Degree of the Graph, Chromatic Polynomial, Chromatic Polynomial for some Graphs, Exercise, Answer Key.

4.  Trees

Objectives, Introduction, Tree, Degenerate Tree (or Trivial Tree), Leaf (or Terminal Node or Pendant Vertex), Branch Node (or an Internal Node), Certain Properties of Trees, Minimally Connected Graph, Pendant Vertices in a Tree, Distance between Two Vertices, Eccentricity of a Vertex, Centre of a Graph, Radius of Tree, Diameter of Tree, Forest, Rooted Tree, Subtree, m-Ary Tree and Full M-Ary Tree, Ordered Rooted Tree, Binary Tree, Binary Rooted Tree, Height of Binary Tree, Complete Binary Tree, Path Length of Binary Tree, Balanced Rooted Tree, Spanning Tree, Methods for Finding Spanning Tree, Complexity of a Graph, Spanning Tree in Weighted Graph, Minimal Spanning Tree, Method for Finding Minimal Spanning Tree, Distance between Two Spanning Trees, Rank and Nullity, Exercise.

5.  Sets and Set Theory

Objectives, Introduction, Sets, Representation of a Set, Russel Paradox, Principle of Extension, Different Types of Sets, Properties of Subsets, Proper Subset, 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, Duality, Partitions, Addition Principle, Illustrative Examples, Exercise, Answer Key.

6.  Functions

Objectives, 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, 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, Cardinality of an Infinite Set, Countable and Uncountable Sets, The Pigonhole Principle, The Generalized Pigeonhole Principle, Exercise, Answer Key.

7.  Relations               

Objectives, Introduction, Boolean Matrix, 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, Partial Order Relation, Comparability, Total Order Relation or Linear Order Relation, Digraph of a POSET, Hasse Diagram, Illustrative Examples, Exercise, Answer Key.

P.  Papers