Logic and Sets: An Intro to Discrete Math
Logic is the math of true and false. Sets are the math of groups of things. Together they power computer code, database searches, legal contracts and every “if this, then that” you've ever written. Build truth tables, shade Venn diagrams, and see how the two ideas are really one.
Statements and AND, OR, NOT
In logic, a statement (or proposition) is a sentence that is either true or false, never both. “It is raining” is a statement. “Close the door” and “Is it raining?” are not. We use letters like P and Q to stand for statements.
| Word | Symbol | True when... | Example |
|---|---|---|---|
| NOT | ¬P | P is false | “It is not raining” |
| AND | P ∧ Q | both are true | “It's raining and it's cold” |
| OR | P ∨ Q | at least one is true | “It's raining or it's cold” |
OR in math is inclusive. “P or Q” is true if P is true, Q is true, or both. In everyday speech, “soup or salad” usually means just one. That's called exclusive or (XOR), and logicians write it separately.
- ¬Q: “7 is not greater than 10” → true
- P ∧ Q: both must be true, Q is false → false
- P ∨ Q: at least one is true → true
If-then statements
“If P, then Q” is written P → Q. P is the hypothesis and Q is the conclusion. It's a promise: whenever P happens, Q happens too. The only way to break the promise is P true and Q false.
| P | Q | P → Q | Think of it as... |
|---|---|---|---|
| T | T | T | Promise kept |
| T | F | F | Promise broken |
| F | T | T | Promise not tested |
| F | F | T | Promise not tested |
If you don't finish your homework, the promise says nothing about what happens. Playing outside or not, nobody lied. That's why the last two rows are true. Logicians call this vacuously true.
Converse, inverse and contrapositive
Start with “If it's a dog, then it's a mammal” (true).
| Name | Form | Example | Same meaning? |
|---|---|---|---|
| Original | P → Q | If dog, then mammal | ✓ true |
| Converse | Q → P | If mammal, then dog | ✗ (cats!) |
| Inverse | ¬P → ¬Q | If not a dog, then not a mammal | ✗ |
| Contrapositive | ¬Q → ¬P | If not a mammal, then not a dog | ✓ always equivalent |
A classic mistake: assuming the converse. “All dogs are mammals” doesn't mean “all mammals are dogs.” This trips up arguments everywhere, from ads to court cases.
“If and only if” (P ↔ Q) means both directions hold: P → Q and Q → P. It's true when P and Q have the same truth value. “A triangle is equilateral if and only if all its sides are equal.”
Build truth tables
A truth table lists every possible combination of true and false for the letters, and works out the result for each. With n letters there are 2ⁿ rows: 2 letters → 4 rows, 3 letters → 8 rows, 4 letters → 16 rows.
- List the letters as columns. Fill the first column half T, half F. Halve again for each next column.
- Add a column for each smaller piece, working from the inside out (NOT first, then AND, then OR, then →).
- The last column is the answer.
- A tautology is always true (every row T), like P ∨ ¬P.
- A contradiction is always false, like P ∧ ¬P.
- Two expressions are equivalent if their final columns match in every row. Test it with ↔: if the result is a tautology, they're equivalent.
Type an expression using single letters (P, Q, R, S) and the buttons, or words: and, or, not, ->, <->.
Sets
A set is a collection of distinct things, called elements. Order doesn't matter, and repeats don't count. We name sets with capital letters and list elements in curly braces.
| Notation | Means | Example |
|---|---|---|
| { } | a set (roster form) | A = {1, 2, 3, 4} |
| ∈ | is an element of | 3 ∈ A |
| ∉ | is not an element of | 7 ∉ A |
| ⊆ | is a subset of (every element is also in) | {1, 2} ⊆ A |
| ∅ | the empty set, no elements | { } |
| U | the universal set: everything we're talking about | U = {1, 2, ..., 10} |
| |A| | cardinality: how many elements | |A| = 4 |
Set-builder notation describes a rule instead of a list: {x | x is an even number} reads “the set of all x such that x is an even number.” Useful when the set is huge or infinite.
{1, 2, 2, 3} is the same set as {3, 1, 2}. Duplicates and order don't matter. Its cardinality is 3.
Union, intersection and Venn diagrams
Let U = {1, 2, ..., 8}, A = {1, 2, 3, 4} and B = {3, 4, 5, 6}.
| Operation | Symbol | Means | Result | Logic twin |
|---|---|---|---|---|
| Union | A ∪ B | in A or B (or both) | {1, 2, 3, 4, 5, 6} | OR ∨ |
| Intersection | A ∩ B | in both A and B | {3, 4} | AND ∧ |
| Complement | A′ | in U but not in A | {5, 6, 7, 8} | NOT ¬ |
| Difference | A − B | in A but not in B | {1, 2} | A ∧ ¬B |
See the pattern? Union is OR, intersection is AND, complement is NOT. Even De Morgan's laws carry over: (A ∪ B)′ = A′ ∩ B′.
Counting with two sets
- 18 students play a sport, 12 play an instrument, 5 do both.
- Students who do at least one: 18 + 12 − 5 = 25
- With 30 in the class, 30 − 25 = 5 do neither.
Click a region in the diagram, or use these buttons:
FAQCommon questions
What is discrete math?
Math about separate, countable things (whole numbers, true/false, sets, graphs) rather than smooth, continuous quantities. It's the foundation of computer science.
Why is “if false, then anything” true?
Because the if-then statement only promises something when the “if” part happens. When it doesn't, the promise can't be broken, so we count it as true. Every other choice causes problems elsewhere in logic.
Where do programmers use this?
Everywhere: if (age >= 18 && hasID) is an AND, search filters are unions and intersections, and database queries use exactly these set operations.
Is a set the same as a list?
No. A list has an order and can repeat items. A set has no order and no duplicates.
Is the empty set a subset of every set?
Yes. “Every element of ∅ is in A” is vacuously true, since ∅ has no elements to break the rule.