top of page

Descrete Mathematics

Course Outline


I. Introduction to Discrete Mathematics
A. Definitions, Scope and Importance of Discrete Mathematics
B. Introduction to Mathematical Logic
C. Propositions and Logical Operations
D. Truth Tables
E. Logical Equivalences and Quantifiers

II. Sets, Relations and Functions
A. Basics of Sets
    1. Definitions
    2. Operations on Sets
B. Relations
    1. Definition and Properties
    2. Representing Relations
    3. Closures
C. Functions
    1. Definition and Properties
    2. Injective, Surjective, and Bijective Functions
    3. Inverse and Compositions of Functions

III. Combinatorics
A. Counting Principles
    1. Fundamental Principles of Counting
    2. Permutations and Combinations
B. Binomial Coefficients
C. Inclusion-Exclusion Principle
D. Pigeonhole Principle
E. Recurrence Relations and Generating Functions

IV. Graph Theory
A. Basics of Graphs
    1. Definitions and Terminology
    2. Types of Graphs
B. Graph Representations (Adjacency Matrix, Incidence Matrix, etc.)
C. Graph Traversal Algorithms (DFS, BFS)
D. Graph Properties and Theorems (Euler, Hamiltonian, etc.)
E. Trees and Spanning Trees

V. Discrete Probability
A. Basic Concepts of Probability
B. Conditional Probability and Bayes’ Theorem
C. Random Variables and Expectation
D. Variance and Standard Deviation

VI. Formal Languages, Automata and Complexity
A. Introduction to Formal Languages
    1. Definitions and Examples
    2. Regular Languages
    3. Context-Free Languages
B. Automata Theory
    1. Finite Automata
    2. Pushdown Automata
    3. Turing Machines
C. Complexity Theory
    1. Time and Space Complexity
    2. P, NP, and NP-Completeness

VII. Boolean Algebra and Logic Gates
A. Basics of Boolean Algebra
    1. Definitions and Properties
    2. Basic Operations
    3. Boolean Functions
B. Logic Gates and Circuits
    1. Basic Gates (AND, OR, NOT, XOR, etc.)
    2. Universal Gates (NAND, NOR)
    3. Designing and Simplifying Circuits

VIII. Mathematical Reasoning and Proof Techniques
A. Proof Techniques
    1. Direct Proofs
    2. Indirect Proofs (Contradiction, Contrapositive)
    3. Mathematical Induction (Weak and Strong)
B. Proof of Correctness for Algorithms
C. Diagonalization and Pigeonhole Principle

IX. Number Theory and Cryptography
A. Basics of Number Theory
    1. Divisibility, Primes, and Greatest Common Divisors
    2. Euclidean Algorithm
    3. Modular Arithmetic
B. Introduction to Cryptography
    1. Classical Cryptosystems
    2. Public-Key Cryptography
    3. RSA Algorithm

Textbook: "Discrete Mathematics and Its Applications" by Kenneth H. Rosen.

I. Introduction to Discrete Mathematics

The objective of this initial unit is to establish a solid foundation in understanding the language and basic concepts of Discrete Mathematics. The module focuses on logical reasoning, an integral part of mathematical thinking.

A. Definitions, Scope, and Importance of Discrete Mathematics

Definition of Discrete Mathematics: Exploring the concept of 'discreteness,' difference between continuous and discrete structures.

Fields where Discrete Mathematics is used: Computer Science, Data Science, Statistics, Graph Theory, etc.
Importance and Applications of Discrete Mathematics: Cryptography, Network Analysis, Decision theory, Game theory, and other real-life applications.

B. Introduction to Mathematical Logic

Definition and importance of Mathematical Logic: Its role in Mathematical proofs and Computer Science.
Components of Logic: Propositions, Logical connectives, Truth values.

C. Propositions and Logical Operations

Definition of Proposition: Understanding declarative sentences that can be assigned a truth value.
Types of Proposition: Simple and compound propositions.
Logical Operations (Connectives): AND, OR, NOT, IF-THEN (Implication), IF-AND-ONLY-IF (Biconditional).

D. Truth Tables

Constructing Truth Tables: Introduction to the tabular representation that describes the truth value of complex propositions based on the truth values of their simple constituents.
Analyzing and interpreting Truth Tables.

E. Logical Equivalences and Quantifiers

  • Logical Equivalences: Introduction to laws of logic (Identity, Negation, Domination, Idempotent, Double

  • Negation, Commutative, Associative, Distributive, De Morgan's, Absorption laws).

  • Understanding and proving logical equivalences.

  • Quantifiers: Understanding Universal and Existential quantifiers.

  • Translating common English phrases into logical expressions with quantifiers.

bottom of page