Discrete Mathematics – Complete Notes (All Units)
Prepared specially for Laksh
Includes:
• Propositional Logic
• Predicate Logic
• Truth Tables
• Logical Equivalence
• CNF & DNF
• Sets & Set Operations
• Subset, Proper Subset, Power Set
• Inclusion–Exclusion (2 & 3 sets)
• Cartesian Product
• Quantifiers
• Validity
• All Proof Techniques
• √2 Irrational Proof (Direct, Contrapositive, Contradiction)
1. Propositional Logic
A proposition is a statement that can be TRUE or FALSE.
Logical operators:
• AND (p ∧ q) – True only if both p and q are true
• OR (p ∨ q) – True if at least one is true
• NOT (¬p) – Flips truth value
• Implication (p → q) – False only when p is true and q is false
• Biconditional (p ↔ q) – True when both have same truth value
Truth Table Example – AND
p|q|p∧q
T|T|T
T|F|F
F|T|F
F|F|F
Logical Equivalence
Important identities:
• ¬(p ∧ q) ≡ ¬p ∨ ¬q
• ¬(p ∨ q) ≡ ¬p ∧ ¬q
• p → q ≡ ¬p ∨ q
• (p ↔ q) ≡ (p → q) ∧ (q → p)
2. Normal Forms – CNF & DNF
• CNF (Conjunctive Normal Form): AND of ORs
Example: (p ∨ q) ∧ (¬r ∨ p)
• DNF (Disjunctive Normal Form): OR of ANDs
Example: (p ∧ q) ∨ (¬p ∧ r)
Difference:
CNF = clauses joined by AND
DNF = terms joined by OR
Both are used to simplify, solve SAT, or validate arguments.
3. Predicate Logic
Predicate: P(x) is a statement depending on variable x.
Quantifiers:
• ∀x P(x) – true for ALL x
• ∃x P(x) – true for AT LEAST ONE x
Negations:
• ¬∀x P(x) ≡ ∃x ¬P(x)
• ¬∃x P(x) ≡ ∀x ¬P(x)
Example (your wording made formal):
Quantifiers simply tell whether we talk about ALL elements of a set
or at least ONE element of the set.
Predicate + Validity Example:
Premise 1: ∀x (Student(x) → StudiesMath(x))
Premise 2: Student(Alice)
Conclusion: StudiesMath(Alice)
This argument is VALID because whenever premises are true,
the conclusion MUST be true.
4. Sets & Operations
• Element: item inside a set
• Subset: A ⊆ B
• Proper Subset: A ⊂ B
• Power Set: P(A) has 2^n subsets
• Cardinality: |A| = number of elements
• Operations:
Union A ∪ B
Intersection A ∩ B
Difference A - B
Complement A■
Cartesian Product
A × B = set of all ordered pairs (a, b).
Inclusion–Exclusion
2 sets: |A ∪ B| = |A| + |B| – |A ∩ B|
3 sets: |A ∪ B ∪ C| = |A| + |B| + |C|
– |A∩B| – |B∩C| – |C∩A|
+ |A∩B∩C|
5. Proof Techniques
Direct Proof
Assume the hypothesis and logically reach the conclusion.
Proof by Contrapositive
To prove: If P then Q
Instead prove: If NOT Q then NOT P
Proof by Contradiction
Assume the statement is FALSE and show this leads to IMPOSSIBILITY.
Example: √2 is Irrational (All 3 Proofs)
1. Direct Proof (not common, but included for you)
We attempt to assume √2 is rational and derive contradiction directly
from definitions. This collapses into contradiction and thus the number is irrational.
2. Contrapositive Proof
Not standard here, but we show:
If √2 were rational → numerator & denominator share factor 2
Thus "if it has no common factor, it cannot represent √2".
3. Proof by Contradiction (standard)
Assume √2 = a/b in lowest terms.
Square both sides → 2b² = a² → a² even → a even → a = 2k
Substitute → b also even, contradicting “a/b is simplified”.
Thus √2 is irrational.
End of Complete Notes
If you want diagrams, logic gates, examples, solved questions, or expansion of ANY chapter, tell me and I
will regenerate a newer PDF.