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. InclusionExclusion 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. ContextFree 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 NPCompleteness
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. PublicKey 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 reallife 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, IFTHEN (Implication), IFANDONLYIF (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.
â€‹