|
Introduction: Variables, The Language of Sets, The Language of
Relations and Function
Set Theory: Definitions and the Element Method of Proof, Properties
of Sets, Disproofs, Algebraic Proofs, Boolean Algebras, Russell’s
Paradox and the Halting Problem.
The Logic of Compound Statements: Logical Form and Logical
Equivalence, Conditional Statements, Valid and Invalid Arguments
12
II Quantified Statements: Predicates and Quantified Statements,
Statements with Multiple Quantifiers, Arguments with Quantified
Statements
Elementary Number Theory and Methods of Proof: Introduction to
Direct Proofs, Rational Numbers, Divisibility, Division into Cases and
the Quotient-Remainder Theorem, Floor and Ceiling, Indirect
Argument: Contradiction and Contraposition, Two Classical Theorems,
Applications in algorithms.
12
III Sequences, Mathematical Induction, and Recursion: Sequences,
Mathematical Induction, Strong Mathematical Induction and the Well-
Ordering Principle for the Integers, Correctness of algorithms, defining
sequences recursively, solving recurrence relations by iteration, Second
order linear homogenous recurrence relations with constant
coefficients. general recursive definitions and structural induction.
Functions: Functions Defined on General Sets, One-to-One and Onto,
Inverse Functions, Composition of Functions, Cardinality with
Applications to Computability
12
IV Relations: Relations on Sets, Reflexivity, Symmetry, and Transitivity,
Equivalence Relations, Partial Order Relations
Graphs and Trees: Definitions and Basic Properties, Trails, Paths, and
Circuits, Matrix Representations of Graphs, Isomorphism’s of Graphs,
Trees, Rooted Trees, Isomorphism’s of Graphs, Spanning trees and
shortest paths.
12
V Counting and Probability: Introduction, Possibility Trees and the
Multiplication Rule, Possibility Trees and the Multiplication Rule,
Counting Elements of Disjoint Sets: The Addition Rule, The
Pigeonhole Principle, Counting Subsets of a Set: Combinations, r-
Combinations with Repetition Allowed, Probability Axioms and
Expected Value, Conditional Probability, Bayes’ Formula, and
Independent Events.
12
22 | P a g e
Books and References:
Sr. No. Title Author/s Publisher Edition Year
1. Discrete Mathematics with
Applications
Sussana S. Epp Cengage
Learning
4
th 2010
2. Discrete Mathematics,
Schaum’s Outlines Series
Seymour
Lipschutz, Marc
Lipson
Tata
MCGraw
Hill
2007
3. Discrete Mathematics and
its Applications
Kenneth H. Rosen Tata
MCGraw
Hill
4. Discrete mathematical
structures
B Kolman RC
Busby, S Ross
PHI
5. Discrete structures Liu Tata
MCGraw