Discrete Mathematics Notes & Formulas

1. Definition

Mathematics of discrete (countable) structures - logic, sets, relations, functions, combinatorics, and proof techniques.

2. Propositional Logic (Very Important)

Connectives

• ¬p (NOT), p∧q (AND), p∨q (OR), p→q (implication), p↔q (biconditional)

Implication p→q: False ONLY when p=T and q=F
Equivalent forms: ¬p∨q = ¬q→¬p (contrapositive)

• Contrapositive (¬q→¬p): logically equivalent to p→q
• Converse (q→p): NOT equivalent
• Inverse (¬p→¬q): NOT equivalent

Tautology: Always true. Contradiction: Always false. Contingency: Sometimes true.

3. Predicate Logic

• ∀x P(x): For all x, P(x) holds
• ∃x P(x): There exists x such that P(x) holds
• ¬∀x P(x) ≡ ∃x ¬P(x)
• ¬∃x P(x) ≡ ∀x ¬P(x)

4. Set Theory

• |A∪B| = |A| + |B| − |A∩B| (Inclusion-Exclusion)
• |A∪B∪C| = |A|+|B|+|C| − |A∩B| − |B∩C| − |A∩C| + |A∩B∩C|
• Power set of A: P(A), |P(A)| = 2^|A|
• A×B: Cartesian product, |A×B| = |A|·|B|

5. Relations (Very Important)

Properties of relation R on set A:
| Property | Condition |
|---|---|
| Reflexive | (a,a) ∈ R for all a |
| Irreflexive | (a,a) ∉ R for all a |
| Symmetric | (a,b) ∈ R → (b,a) ∈ R |
| Antisymmetric | (a,b) ∈ R and (b,a) ∈ R → a=b |
| Transitive | (a,b) and (b,c) ∈ R → (a,c) ∈ R |

Equivalence relation: Reflexive + Symmetric + Transitive
Partial order (POSET): Reflexive + Antisymmetric + Transitive
Total order: POSET where every pair is comparable

6. Functions

• Injective (one-one): f(a)=f(b) → a=b. |domain| ≤ |codomain|
• Surjective (onto): Every element of codomain is mapped. |domain| ≥ |codomain|
• Bijective: Both injective and surjective → invertible
• Number of functions from A to B: |B|^|A|
• Number of injections: |B|P|A| (permutation)
• Number of bijections: |A|! (only when |A|=|B|)

7. Combinatorics (Very Important)

• Permutation: nPr = n!/(n−r)!
• Combination: nCr = n!/[r!(n−r)!]
• Pigeonhole Principle: n+1 objects in n boxes → at least one box has ≥ 2 objects
• Generalized: ⌈n/k⌉ objects guaranteed in one box when n objects in k boxes
• Derangement (no fixed point): D(n) = n! Σ(−1)^k/k! for k=0 to n

8. Proof Techniques

• Direct proof, Proof by contradiction, Proof by contrapositive
• Mathematical induction: Base case + Inductive step (assume P(k), prove P(k+1))
• Strong induction: Assume all P(1),...,P(k), prove P(k+1)

9. GATE Trick

Contrapositive equivalence is heavily tested. Implication p→q is only false when p=T,q=F - memorize this. For counting problems, identify whether order matters (permutation) or not (combination) first. Equivalence classes partition the set - size of largest equivalence class is often asked.