A · Compressed recap
Sets: distinct elements, no order; ∪ (or), ∩ (and), − (in first, not second); |A ∪ B| = |A| + |B| − |A ∩ B|; power set has 2ⁿ subsets. Tuples keep order; the Cartesian product A × B has |A|·|B| pairs; a relation is a subset of D₁ × … × Dₙ, so it has no duplicate tuples and no row order, and there are 2^N possible relations on N possible tuples.
Logic: p → q ≡ ¬p ∨ q, false only for T → F; De Morgan; ¬∀ = ∃¬ and ¬∃ = ∀¬; "for all" = "no counter-example"; ∀ pairs with →, ∃ with ∧; over an empty domain ∀ is true and ∃ false. Counting: n!, C(n, k), interleavings C(m + n, m), inclusion–exclusion, groups containing X: 2ⁿ⁻|X|.
B · Merged rule card
0.2.1 Sets: membership, subset, union, intersection, difference, cardinality, power set
- Set = distinct elements, no order; x ∈ A; ∅ has no elements.
- A ⊆ B: every element of A is in B. ∅ ⊆ A; A ⊆ A.
- ∪ or, ∩ and, − in first but not second; A − B ≠ B − A.
- |A ∪ B| = |A| + |B| − |A ∩ B|.
- |P(A)| = 2ⁿ for |A| = n; subsets containing k fixed elements: 2ⁿ⁻ᵏ.
0.2.2 Ordered tuples, Cartesian product and its size; a relation as a set of tuples
- Ordered pair: (a,b) = (c,d) iff a = c and b = d. n-tuple = n ordered components.
- A × B = {(a,b) | a ∈ A, b ∈ B}; |A × B| = |A|·|B|; A × ∅ = ∅.
- A relation on D₁..Dₙ = a subset of D₁ × … × Dₙ: a set of tuples (no duplicates, no row order).
- Number of possible relations = 2^(|D₁|·…·|Dₙ|).
0.2.3 Logic: propositions, AND/OR/NOT, implication, truth tables, quantifiers and their negation
- ∧ both; ∨ at least one; p → q false only for T → F; p → q ≡ ¬p ∨ q.
- De Morgan: ¬(p ∧ q) ≡ ¬p ∨ ¬q; ¬(p ∨ q) ≡ ¬p ∧ ¬q; ¬(p → q) ≡ p ∧ ¬q.
- ¬∀x P ≡ ∃x ¬P; ¬∃x P ≡ ∀x ¬P; ∀x P ≡ ¬∃x ¬P.
- ∀ pairs with →; ∃ pairs with ∧.
- Empty domain: ∀ true, ∃ false.
0.2.4 Counting toolkit: combinations, inclusion–exclusion
- Product rule: m × n. n! arrangements; 0! = 1.
- C(n, k) = n!/(k!(n − k)!); C(n, k) = C(n, n − k); Σₖ C(n, k) = 2ⁿ.
- Interleavings of m and n ordered steps: C(m + n, m).
- |A ∪ B| = |A| + |B| − |A ∩ B|; three sets: add singles, subtract pairs, add the triple.
- Groups of n attributes containing a fixed group X: 2ⁿ⁻|X|.
C · Interleaved GATE-style questions
Q1 · NAT · 1 mark(s) — Sets
| A | = 30, | B | = 20, | A ∩ B | = 5. What is | A ∪ B | ? |
|---|
Numerical answer: ________
Q2 · MCQ · 1 mark(s) — Tuples
Which pair of objects are equal?
- (A) {a} and a
- (B) (a, b) and (b, a)
- (C) (a, a) and (a)
- (D) {a, b} and {b, a, a}
Q3 · NAT · 2 mark(s) — Counting relations
How many relations are possible on two attributes whose domains have 3 and 1 values?
Numerical answer: ________
Q4 · MCQ · 2 mark(s) — Quantifiers
"Not every student has taken a course" is equivalent to:
- (A) Some student has taken a course
- (B) Some student has not taken any course
- (C) No student has taken a course
- (D) Every student has not taken a course
Q5 · MCQ · 1 mark(s) — Implication
If p is false, p → q is:
- (A) always true
- (B) always false
- (C) equal to ¬q
- (D) equal to q
Q6 · NAT · 1 mark(s) — Combinations
What is C(8, 2)?
Numerical answer: ________
Q7 · NAT · 2 mark(s) — Inclusion–exclusion
R(A, B, C, D, E, F). How many attribute groups contain A or BC?
Numerical answer: ________
Q8 · MSQ · 2 mark(s) — Power set
For A = {x, y, z}, which are elements of P(A)?
- (A) ∅
- (B) {x, z}
- (C) x
- (D) {x, y, z}
Q9 · NAT · 2 mark(s) — Interleavings
T1 has 3 operations and T2 has 3 operations. How many interleavings keep each transaction's own order?
Numerical answer: ________
D · Answer Vault
Reveal answers when you’re ready
Q1 Answer: 45 · 1 mark(s)
30 + 20 − 5 = 45.
Re-read: Lesson 0.2.1 — Sets: membership, subset, union, intersection, difference, cardinality, power set
Q2 Answer: (D) · 1 mark(s)
Sets ignore order and repeats.
- (A) is wrong: A set is not its element.
- (B) is wrong: Tuples keep order.
- (C) is wrong: Different lengths.
Re-read: Lesson 0.2.2 — Ordered tuples, Cartesian product and its size; a relation as a set of tuples
Q3 Answer: 8 · 2 mark(s)
3 × 1 = 3 possible tuples; 2³ = 8.
Re-read: Lesson 0.2.2 — Ordered tuples, Cartesian product and its size; a relation as a set of tuples
Q4 Answer: (B) · 2 mark(s)
¬∀x P(x) ≡ ∃x ¬P(x).
- (A) is wrong: Not implied.
- (C) is wrong: Too strong.
- (D) is wrong: Too strong.
Re-read: Lesson 0.2.3 — Logic: propositions, AND/OR/NOT, implication, truth tables, quantifiers and their negation
Q5 Answer: (A) · 1 mark(s)
False premise makes the implication true.
- (B) is wrong: Opposite.
- (C) is wrong: No.
- (D) is wrong: Only when p is true.
Re-read: Lesson 0.2.3 — Logic: propositions, AND/OR/NOT, implication, truth tables, quantifiers and their negation
Q6 Answer: 28 · 1 mark(s)
8·7/2 = 28.
Re-read: Lesson 0.2.4 — Counting toolkit: combinations, inclusion–exclusion
Q7 Answer: 40 · 2 mark(s)
Contain A: 2⁵ = 32. Contain BC: 2⁴ = 16. Contain ABC: 2³ = 8. 32 + 16 − 8 = 40.
Re-read: Lesson 0.2.4 — Counting toolkit: combinations, inclusion–exclusion
Q8 Answer: (A) (B) (D) · 2 mark(s)
P(A) contains subsets; x is an element of A, not a subset.
- (C) is wrong: Write {x}.
Re-read: Lesson 0.2.1 — Sets: membership, subset, union, intersection, difference, cardinality, power set
Q9 Answer: 20 · 2 mark(s)
C(6, 3) = 20.
Re-read: Lesson 0.2.4 — Counting toolkit: combinations, inclusion–exclusion