Discrete Mathematics – Detailed Notes
1. Introduction
Discrete Mathematics studies mathematical structures that are fundamentally discrete, not
continuous. Unlike calculus, which deals with continuous functions, discrete mathematics
focuses on objects that can be counted. It is essential in computer science, as it provides the
theoretical foundation for algorithms, programming languages, cryptography, and more.
Importance in Computer Science:
• Designing algorithms and analyzing complexity.
• Data structures like graphs, trees, and sets.
• Logical reasoning in programming and debugging.
• Cryptography and security protocols.
• Database theory and network design.
2. Propositional Logic
Definition:
A propositional statement is a sentence that is either true (T) or false (F), but not both.
Logical Connectives:
• AND ( ∧ ) – True if both statements are true.
• OR ( ∨ ) – True if at least one statement is true.
• NOT ( ¬ ) – Negates the truth value.
• IMPLICATION ( → ) – "If P then Q". False only if P is true and Q is false.
• BICONDITIONAL ( ↔ ) – True if both statements have the same truth value.
Example:
Let P: “It is raining.”
Let Q: “I will take an umbrella.”
• P ∧ Q: “It is raining AND I will take an umbrella.”
• P → Q: “If it is raining, then I will take an umbrella.”
Truth Tables:
A truth table lists all possible truth values for propositions.
P Q P ∧ Q P ∨ Q P → Q ¬P
TT T T T F
TF F T F F
FT F T T T
FF F F T T
Applications: Logical circuits, conditional programming statements, AI reasoning.
3. Predicate Logic
Definition:
Predicate logic extends propositional logic by including quantifiers and variables. It can
express statements like “All students are enrolled in a course.”
Quantifiers:
• Universal Quantifier ( ∀ ): “For all x, P(x)”
• Existential Quantifier ( ∃ ): “There exists x such that P(x)”
Example:
• ∀x ∈ Students, Enrolled(x) → True (All students are enrolled)
• ∃x ∈ Students, Enrolled(x) → True if at least one student is enrolled.
Applications: Database queries, formal verification of software.
4. Set Theory
Definition:
A set is a collection of distinct objects, called elements.
Operations:
• Union ( ∪ ): Elements in A or B
• Intersection ( ∩ ): Elements in both A and B
• Difference ( - ): Elements in A but not in B
• Complement ( A' ): All elements not in A
Example:
A = {1,2,3}, B = {2,3,4}
• A ∪ B = {1,2,3,4}
• A ∩ B = {2,3}
• A - B = {1}
Applications: Data organization, database relations, probability theory.
5. Functions and Relations
Functions:
A function f: A → B assigns each element in A exactly one element in B.
Types of Functions:
• One-to-One (Injective): No two elements of A map to the same element in B.
• Onto (Surjective): Every element in B has a pre-image in A.
• Bijective: Both one-to-one and onto.
Relations:
A relation R from set A to set B is a subset of A × B.
• Reflexive: Every element is related to itself.
• Symmetric: If aRb then bRa.
• Transitive: If aRb and bRc then aRc.
Applications: Hashing, relational databases, graph theory.
6. Proof Techniques
1. Direct Proof: Prove “If P then Q” by straightforward reasoning.
2. Proof by Contradiction: Assume the opposite of what you want to prove, then show
it leads to a contradiction.
3. Mathematical Induction:
o Base Case: Prove the statement for n = 1.
o Inductive Step: Assume true for n = k, prove for n = k+1.
Example:
Prove sum of first n natural numbers = n(n+1)/2 using induction.
• Base case: n=1 → 1 = 1(1+1)/2
• Inductive step: Assume true for n=k, sum = k(k+1)/2. For n=k+1: sum = k(k+1)/2 +
(k+1) = (k+1)(k+2)/2
7. Graph Theory
Definition: A graph G = (V, E) where V is a set of vertices and E is a set of edges.
Types of Graphs:
• Undirected vs Directed
• Weighted vs Unweighted
• Trees: A connected acyclic graph
Applications: Networks, social media connections, shortest path algorithms.
8. Combinatorics
Permutations: Arrangements of n objects.
• Example: 3 objects A, B, C → ABC, ACB, BAC…
Combinations: Selection of objects where order doesn’t matter.
• Example: Choosing 2 fruits from {apple, banana, orange} → {apple, banana}, {apple,
orange}, {banana, orange}
Applications: Probability, algorithm complexity, cryptography.
9. Exercises
1. Construct truth tables for: (P ∨ Q) ∧ ¬R
2. Define a function f: Z → Z where f(x) = 2x. Show it is one-to-one.
3. Draw an ER diagram for a library system.
4. Solve: Sum of first 20 natural numbers using induction.
5. Given a graph with 5 vertices and edges { (1,2),(1,3),(2,4),(3,5) }, draw it.
