Back to Course
Sets and Logic
Set Fundamentals and Notation
A set is a well-defined collection of distinct objects, called Elements, typically denoted by capital letters like $A$ or $B$.
$$x \in A, \quad x \notin A$$
Notation describing the membership status of an object relative to a set.
$\in$=Element of / Belongs to(none)
$\notin$=Not an element of(none)
$A$=Target set(none)
Distinctness: Elements within a set must be unique; repetitions do not change the set.
Well-Defined: There must be a clear criterion to determine if any object belongs to the set.
Cardinality: Represented as $|A|$, it denotes the number of unique elements in set $A$.
Set Operations and Venn Diagrams
Sets can be manipulated through Union, Intersection, and Relative Complement to form new collections. A Venn Diagram uses overlapping circles inside a rectangle to visualise these operations.
$$|A \cup B| = |A| + |B| - |A \cap B|$$
The Inclusion-Exclusion Principle calculates the size of the union by subtracting the double-counted intersection.
$|A \cup B|$=Cardinality of the union(count)
$|A \cap B|$=Cardinality of the intersection(count)
$|A|$=Size of set A(count)
Union (∪): Contains all elements present in either set A, set B, or both. Symbolically: $A \cup B = \{x \mid x \in A \lor x \in B\}$.
Intersection (∩): Contains only elements present in both set A and set B simultaneously. Symbolically: $A \cap B = \{x \mid x \in A \land x \in B\}$.
Disjoint Sets: Sets with an empty intersection ($A \cap B = \emptyset$). For disjoint sets, $|A \cup B| = |A| + |B|$ since there is no overlap to subtract.
Overlapping Sets: Sets whose intersection is non-empty but neither is a subset of the other.
The Complement of set $A$ (written $A'$ or $A^c$) is everything in the Universal Set $U$ that is not in $A$. The set difference $A - B$ removes elements of $B$ from $A$.
$$A' = U - A = \{x \mid x \in U \land x \notin A\}$$
The complement contains every element of the universal set that does not belong to A.
$A'$=Complement of A(none)
$U$=Universal set(none)
$A - B$=Elements in A but not in B (set difference)(none)
Complement Notation: $A'$, $A^c$, and $U - A$ all mean the same thing.
Set Difference: $A - B = \{x \mid x \in A \land x \notin B\}$. Note: $A - B \neq B - A$ in general.
Difference via Intersection: $A - B = A \cap B'$, which is equivalent by definition.
Properties of Union and Intersection
Set operations obey algebraic properties analogous to arithmetic, including commutative, associative, and distributive laws.
$$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$$
Union distributes over intersection, just as multiplication distributes over addition in algebra.
$\cup$=Union (analogous to addition)(none)
$\cap$=Intersection (analogous to multiplication)(none)
$B = \emptyset$
→Both sides reduce to $A$, since $A \cup \emptyset = A$ and $A \cap A = A$.
$A \subseteq B \subseteq C$
→LHS = $A \cup B = B$. RHS = $B \cap C = B$. Both give $B$.
Commutative: $A \cup B = B \cup A$ and $A \cap B = B \cap A$.
Associative: $A \cup (B \cup C) = (A \cup B) \cup C$ and $A \cap (B \cap C) = (A \cap B) \cap C$.
Distributive: Union distributes over intersection AND intersection distributes over union — both directions work for sets (unlike numbers where only × distributes over +).
Identity Elements: $A \cup \emptyset = A$ (empty set is identity for ∪) and $A \cap U = A$ (universal set is identity for ∩).
Idempotent Laws: $A \cup A = A$ and $A \cap A = A$.
Complement Laws: $A \cup A' = U$ and $A \cap A' = \emptyset$.
Absorption Laws: $A \cap (A \cup B) = A$ and $A \cup (A \cap B) = A$.
De Morgan's Laws connect complement with union and intersection, allowing you to 'break apart' complements of compound sets.
$$(A \cup B)' = A' \cap B', \quad (A \cap B)' = A' \cup B'$$
Complementing a union turns it into an intersection of complements, and vice versa. The complement 'flips' the operation.
$(A \cup B)'$=Everything NOT in A or B(none)
$A' \cap B'$=Elements outside A AND outside B(none)
Proof Strategy: Show each side is a subset of the other. If $x \in (A \cup B)'$, then $x \notin A \cup B$, so $x \notin A$ AND $x \notin B$, meaning $x \in A' \cap B'$.
Verification Shortcut: Pick concrete sets and compute both sides. If $U = \{1,...,10\}$, $A = \{1,2,3\}$, $B = \{2,3,4,5\}$: LHS $(A \cup B)' = \{6,7,8,9,10\}$, RHS $A' \cap B' = \{4,5,...,10\} \cap \{1,6,...,10\} = \{6,7,8,9,10\}$.
Mnemonic: 'Break the bar, change the sign' — the complement bar distributes but the operation flips.
Propositions and Logical Operators
Logic uses Conjunction (AND), Disjunction (OR), and Negation (NOT) to evaluate the truth of complex statements.
$$p \lor q, \quad p \land q, \quad \neg p$$
Standard symbolic representations for logical disjunction, conjunction, and negation.
$\land$=Conjunction (AND)(logic)
$\lor$=Disjunction (OR)(logic)
$\neg$=Negation (NOT)(logic)
Conjunction (∧): True ONLY when both components are True. With $n$ propositions, the conjunction has $2^n$ rows in its truth table.
Disjunction (∨): False ONLY when both components are False. This is inclusive OR (both true is still true).
Negation (¬): Flips the truth value. Double negation cancels: $\neg(\neg p) \equiv p$.
Truth Table: A systematic table listing all $2^n$ combinations of truth values for $n$ variables, used to evaluate compound propositions.
Tautology vs Contradiction: A tautology is always True (e.g., $p \lor \neg p$). A contradiction is always False (e.g., $p \land \neg p$). Every other formula is a contingency.
Conditional Logic and Quantifiers
A Conditional statement $p \to q$ asserts that if $p$ is true, then $q$ must also be true.
$$p \to q \equiv \neg q \to \neg p$$
The contrapositive of a conditional statement is logically equivalent to the original statement.
$\to$=Implication (If...then)(logic)
$\equiv$=Logical Equivalence(logic)
$\neg$=Negation(logic)
Only False Case: $p \to q$ is False ONLY when $p$ is True and $q$ is False. A false hypothesis makes the conditional automatically True (vacuous truth).
Contrapositive: $\neg q \to \neg p$ — logically equivalent to $p \to q$. Always valid for proofs.
Converse: $q \to p$ — NOT equivalent to $p \to q$.
Inverse: $\neg p \to \neg q$ — NOT equivalent to $p \to q$. The inverse is the contrapositive of the converse.
Material Equivalence: $p \to q \equiv \neg p \lor q$. This lets you convert any conditional into a disjunction.
A Biconditional $p \leftrightarrow q$ asserts that $p$ and $q$ have the same truth value — both true or both false.
$$p \leftrightarrow q \equiv (p \to q) \land (q \to p)$$
The biconditional is true exactly when both the conditional and its converse hold simultaneously.
$\leftrightarrow$=If and only if (iff)(logic)
$p \to q$=Forward direction(logic)
$q \to p$=Backward direction (converse)(logic)
Truth Values: True when both are T or both are F. False when they differ — exactly 2 True rows out of 4.
Read As: 'p if and only if q', abbreviated 'p iff q'.
Inductive and Deductive Reasoning
Mathematical reasoning falls into two categories: induction (specific → general) and deduction (general → specific).
Inductive Reasoning: Drawing general conclusions from specific observations or patterns. Example: observing 2, 4, 6, 8, ... and concluding the pattern is $2n$.
Deductive Reasoning: Drawing specific conclusions from accepted general premises. Example: 'All men are mortal; Socrates is a man; therefore Socrates is mortal.'
Key Difference: Inductive conclusions are probable but not certain; deductive conclusions are guaranteed if the premises are true.
Aristotelian Logic: Every Proposition is either True or False with no third option — the foundation of all deductive reasoning in mathematics.
Truth Sets: Linking Sets and Logic
Every logical proposition $p(x)$ has a truth set — the set of all values making $p$ true — creating a direct bridge between set theory and logic.
Truth Set of $\neg p$: The complement $P'$, since $\neg p$ is true exactly where $p$ is false.
Truth Set of $p \lor q$: The union $P \cup Q$, since the disjunction is true when either is true.
Truth Set of $p \land q$: The intersection $P \cap Q$, since both must be true simultaneously.
Truth Set of $p \to q$: The set $P' \cup Q$, using the equivalence $p \to q \equiv \neg p \lor q$.
Power of the Link: Any set identity (like De Morgan's Law) can be proved via truth tables, and any logical equivalence can be expressed in set notation.
Application Strategy
Worked Examples
Problem Statement
Let $U = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$ be the universal set. If $A = \{1, 3, 5, 7, 9\}$ and $B = \{2, 3, 5, 7\}$, find $(A \cup B)'$.
Union of setsSet Complement
Strategic Toolkit
$A' = U \setminus A$
Step 1
Identify Elements
List the elements of set A and set B.
$A = \{1, 3, 5, 7, 9\}, \quad B = \{2, 3, 5, 7\}$
Step 2
Calculate Union
Combine elements from both sets, removing duplicates.
$A \cup B = \{1, 2, 3, 5, 7, 9\}$
Step 3
Determine Complement
Find elements in $U$ that are not in the union.
$(A \cup B)' = U \setminus \{1, 2, 3, 5, 7, 9\} = \{4, 6, 8, 10\}$
Problem Statement
Let $U = \{1,...,10\}$, $A = \{2,4,6,8,10\}$, $B = \{1,2,3,4,5\}$. Verify that $(A \cap B)' = A' \cup B'$.
De Morgan's LawsSet ComplementIntersection
Strategic Toolkit
$(A \cap B)' = A' \cup B'$
Step 1
Compute Intersection
Find elements common to both A and B.
$A \cap B = \{2, 4\}$
Step 2
Complement the Intersection (LHS)
Remove $A \cap B$ from U.
$(A \cap B)' = U - \{2,4\} = \{1,3,5,6,7,8,9,10\}$
Step 3
Compute Individual Complements
Find $A'$ and $B'$ separately.
$A' = \{1,3,5,7,9\}, \quad B' = \{6,7,8,9,10\}$
Step 4
Union of Complements (RHS)
Combine $A'$ and $B'$.
$A' \cup B' = \{1,3,5,6,7,8,9,10\}$
Step 5
Compare
LHS = RHS, confirming the law.
$\{1,3,5,6,7,8,9,10\} = \{1,3,5,6,7,8,9,10\} \checkmark$
Problem Statement
Prove that $\neg(p \lor q)$ is logically equivalent to $\neg p \land \neg q$ using a truth table.
De Morgan's LawsTruth Table construction
Strategic Toolkit
$\neg(p \lor q) \equiv \neg p \land \neg q$
Step 1
Setup Base Columns
Create all 4 combinations for p and q.
$p, q \in \{T, F\}$ combinations: (T,T), (T,F), (F,T), (F,F)
Step 2
Evaluate Left Side
Calculate $p \lor q$ then negate it.
$\neg(p \lor q) \text{ values: } [F, F, F, T]$
Step 3
Evaluate Right Side
Calculate $\neg p$ and $\neg q$, then find their conjunction.
$\neg p \land \neg q \text{ values: } [F, F, F, T]$
Step 4
Conclusion
Verify identical truth values.
$\text{Both columns are identical} \Rightarrow \text{Equivalent}$
Problem Statement
Construct the truth table for $p \to q$ and identify when it is false.
Conditional logicTruth Table
Strategic Toolkit
$p \to q \equiv \neg p \lor q$
Step 1
List All Cases
Write all four combinations of truth values for p and q.
$(T,T), (T,F), (F,T), (F,F)$
Step 2
Apply the Rule
The conditional $p \to q$ is false ONLY when p is True and q is False.
$p \to q \text{ values: } [T, F, T, T]$
Step 3
Verify via Equivalence
Check using $\neg p \lor q$: negate p, then OR with q.
$\neg p \lor q \text{ values: } [F \lor T, F \lor F, T \lor T, T \lor F] = [T, F, T, T] \checkmark$
Problem Statement
Let $A = \{1,2,3\}$, $B = \{2,3,4,5\}$, $C = \{3,4,5,6,7,8\}$. Verify $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$.
Distributive propertyUnionIntersection
Strategic Toolkit
$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$
Step 1
Compute Inner Operation (LHS)
Find $B \cap C$ first.
$B \cap C = \{3,4,5\}$
Step 2
Complete LHS
Take the union with A.
$A \cup \{3,4,5\} = \{1,2,3,4,5\}$
Step 3
Compute RHS Components
Find $A \cup B$ and $A \cup C$ separately.
$A \cup B = \{1,2,3,4,5\}, \quad A \cup C = \{1,2,3,4,5,6,7,8\}$
Step 4
Complete RHS and Compare
Intersect the two unions.
$(A \cup B) \cap (A \cup C) = \{1,2,3,4,5\}$ = LHS $\checkmark$
Memorize formulas
Inclusion-Exclusion Principle
Add individual sets, subtract the intersection to correct for overlap.
Formula
$|A \cup B| = |A| + |B| - |A \cap B|$
De Morgan's Law (Union)
Complement of union = intersection of complements. The bar 'breaks' and ∪ flips to ∩.
Formula
$(A \cup B)' = A' \cap B'$
De Morgan's Law (Intersection)
Complement of intersection = union of complements.
Formula
$(A \cap B)' = A' \cup B'$
Distributive Law (Sets)
Union distributes over intersection (and vice versa).
Formula
$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$
Conditional Equivalence
An 'if-then' can be rewritten as a disjunction.
Formula
$p \to q \equiv \neg p \lor q$
Cardinality of Power Set
Each element has 2 choices: 'in' or 'out' of the subset.
Formula
$|P(S)| = 2^n$
Review
1
In a group of 80 students, 50 play basketball and 35 play volleyball. If 10 students play neither sport, how many play both?
Ans
15
Review
Tap to reveal
Find the number who play at least one sport
Subtract the students who play neither sport from the total to get the size of the union.
$$|B \cup V| = 80 - 10 = 70$$
Apply inclusion-exclusion
Use $|B \cup V| = |B| + |V| - |B \cap V|$ and solve for the overlap.
$$70 = 50 + 35 - |B \cap V| \Rightarrow |B \cap V| = 15$$
2
Given the conditional 'If a number is divisible by 6, then it is divisible by 3', which statement is the inverse?
Ans
If a number is not divisible by 6, then it is not divisible by 3.
Review
Tap to reveal
Negate both parts of the statement
The inverse of a conditional keeps the order but negates both the hypothesis and the conclusion.
$$p \to q \Rightarrow \neg p \to \neg q$$
Match the given wording
Here the hypothesis is 'divisible by 6' and the conclusion is 'divisible by 3', so both are negated.
If a number is not divisible by 6, then it is not divisible by 3.
3
Let $U = \{1,...,10\}$, $A = \{2,4,6,8,10\}$, $B = \{1,2,3,4,5\}$. What is $(A \cap B)' \cap A$?
Ans
$\{6, 8, 10\}$
Review
Tap to reveal
Find the overlap of A and B
First identify which elements are present in both sets.
$$A \cap B = \{2,4\}$$
Remove that overlap from the universe and intersect with A
Take the complement of the overlap in U, then keep only the elements that remain in A.
$$ (A \cap B)' \cap A = \{1,3,5,6,7,8,9,10\} \cap \{2,4,6,8,10\} = \{6,8,10\} $$
4
Identify the truth value of $(P \land Q) \to P$ for all possible truth values of $P$ and $Q$.
Ans
It is a tautology
Review
Tap to reveal
Check the only way an implication can fail
A conditional is false only when the antecedent is true and the consequent is false. If $P \land Q$ is true, then $P$ is already true, so that failure case cannot occur.
$$T \to T = T$$
Use the false-antecedent rule
When $P \land Q$ is false, the implication is automatically true. So every truth-table row evaluates to true.
The proposition is a tautology.
5
For sets A, B, C, which expression equals $A \cap (B \cup C)$ by the distributive law?
Ans
$(A \cap B) \cup (A \cap C)$
Review
Tap to reveal
Distribute the intersection
Apply the standard distributive law for sets, where intersection distributes over union.
$$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$$
6
If $|A| = 12$, $|B| = 8$, and $|A \cup B| = 16$, what is $|A \cap B|$?
Ans
4
Review
Tap to reveal
Use the two-set counting formula
The overlap is found by adding the set sizes and subtracting the union.
$$|A \cap B| = |A| + |B| - |A \cup B|$$
Substitute the given values
Now evaluate the expression directly.
$$|A \cap B| = 12 + 8 - 16 = 4$$
7
Which of the following compound propositions is a contradiction?
Ans
$p \land \neg p$
Review
Tap to reveal
Identify the impossible statement
A contradiction must be false in every row. The conjunction $p \land \neg p$ cannot ever be true because it demands opposite truth values at the same time.
$$p \land \neg p$$
Rule out the remaining options
The other choices are standard tautologies, so the only contradiction is the self-negating conjunction.
Option A is the contradiction.
8
Let $U = \{1,...,20\}$, $A = \{2,4,...,20\}$ (even numbers), $B = \{1,3,...,19\}$ (odd numbers). What is $A' \cup B'$?
Ans
$U$
Review
Tap to reveal
Identify each complement
Inside the universal set, the complement of the evens is the odds, and the complement of the odds is the evens.
$$A' = B \quad \text{and} \quad B' = A$$
Take the union
The evens and odds together cover the whole universe.
$$A' \cup B' = B \cup A = U$$
9
The biconditional $p \leftrightarrow q$ is true in exactly how many rows of its truth table?
Ans
2
Review
Tap to reveal
Use the biconditional rule
A biconditional is true exactly when both propositions have the same truth value.
$$p \leftrightarrow q \text{ is true when } p,q \text{ are both T or both F}$$
Count the matching rows
Among the four possible assignments, only the matching pairs satisfy the condition.
$$(T,T) \text{ and } (F,F) \Rightarrow 2 \text{ true rows}$$
10
In a school of 60 students, 30 are in the Art club, 24 in Drama, and 18 in Music. 10 are in both Art and Drama, 7 in both Drama and Music, and 5 in both Art and Music. If 7 students are in none of the three clubs, how many are in all three?
Ans
3
Review
Tap to reveal
Find the number in at least one club
Subtract those in none from the total to get the union size.
$$|A \cup D \cup M| = 60 - 7 = 53$$
Apply inclusion-exclusion for three sets
Substitute the given counts and solve for the triple overlap.
$$53 = 30 + 24 + 18 - 10 - 7 - 5 + |A \cap D \cap M| \Rightarrow |A \cap D \cap M| = 3$$
11
If $A \cap B = A$, which relationship between A and B must hold?
Ans
$A \subseteq B$
Review
Tap to reveal
Read the intersection condition
If the overlap equals A itself, then every element of A must also belong to B.
$$A \cap B = A \Rightarrow A \subseteq B$$
Keep the conclusion as a subset relation
Equality is not required; A can be a proper subset of B and still satisfy the statement.
The necessary relationship is $A \subseteq B$.
12
Which logical expression is equivalent to $\neg(p \to q)$?
Ans
$p \land \neg q$
Review
Tap to reveal
Rewrite the implication
Convert the conditional into an equivalent disjunction before negating it.
$$\neg(p \to q) = \neg(\neg p \lor q)$$
Apply De Morgan's law
Negating a disjunction gives a conjunction of negations, which simplifies the expression.
$$\neg(\neg p \lor q) \equiv p \land \neg q$$
Question 1 of 12
0:00
1
In a group of 80 students, 50 play basketball and 35 play volleyball. If 10 students play neither sport, how many play both?