Discrete Mathematics Practice Questions

### 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.