Discrete MathDiscrete MathematicsCollege

Logic and Sets

Truth tables, quantifiers, set operations and De Morgan's laws.

Logic studies statements that are either true or false and how connectives combine them: and ( $\land$ ), or ( $\lor$ ), not ( $\neg$ ) and if-then ( $\to$ ). Truth tables list every case. An implication $p \to q$ is false only when $p$ is true and $q$ is false, and it is logically equivalent to its contrapositive $\neg q \to \neg p$ , but not to its converse $q \to p$ .

Set theory is the parallel language for collections. Union, intersection and complement correspond to or, and and not, and De Morgan's laws hold in both worlds: $\neg(p \land q) \equiv \neg p \lor \neg q$ and $(A \cap B)^c = A^c \cup B^c$ .

Key terms

De Morgan's law: The negation of a conjunction is the disjunction of the negations.
$\neg(p \land q) \equiv \neg p \lor \neg q$

Key ideas

Contrapositive is equivalent; converse and inverse are not.
De Morgan: negating flips and/or (or $\cap$ / $\cup$ ) and negates each part.
Inclusion-exclusion: $|A \cup B| = |A| + |B| - |A \cap B|$ .
A set with $n$ elements has $2^n$ subsets.

Worked example

In a class of 30, 18 take French, 12 take Spanish and 5 take both. How many take neither?

$|F \cup S| = 18 + 12 - 5 = 25$ .
Neither: $30 - 25 = 5$ .
A Venn diagram shows 13 French only, 7 Spanish only, 5 both, 5 neither.

Answer: $5$

Common mistakes

Treating the converse as equivalent to the original statement.
Negating 'and' as 'and'.
Adding set sizes without subtracting the overlap.

Practice questions

Try each one, then open the answer. Numerical answers on this page are verified by an automated calculation check.

1.How many subsets does a 5-element set have?
Show answer
$32$
2. $|A| = 10$ , $|B| = 7$ , $|A \cap B| = 3$ . Find $|A \cup B|$ .
Show answer
$14$
3.How many rows does a truth table for 3 variables have?
Show answer
$8$

Key terms

Key ideas

Worked example

Common mistakes

Practice questions

More in Discrete Mathematics