Statements, Logic, and Sets

How to use this guide

Read one section, hide the page, then reconstruct the rules and examples from memory. Use the answers only after you have committed to a response.

1. Day 0: Do the cold start, read §§1.1–1.2, and try the worked examples with the answers covered.
2. Day 1: Rebuild the truth table and the set operations from memory; solve practice 1–8.
3. Day 3: Solve practice 9–16 without notes, then check each answer and revisit its section reference.
4. About day 7: Solve practice 17–24 in mixed order and explain the De Morgan rules aloud.
5. About day 14: Solve practice 25–33, reconstruct the derivations, then take one exam problem under time limits.
6. Before the exam: Complete the self-check and both exam problems. Return to any skill you cannot demonstrate unaided.

When stuck: identify the definitions involved, test a small example, and write each membership or truth condition explicitly before simplifying.

How the chapter fits together

The chapter moves from evaluating statements to describing collections and proving relationships between them.

1.1 Propositional Logic

Logic gives precise rules for combining claims. It lets you test arguments, simplify conditions, and express properties that will reappear throughout mathematics.

In plain words: logic is a set of rules for combining claims that are either true or false. ¬ flips a claim, ∧ (and) needs both parts true, ∨ (or) needs at least one, and ⇒ (if … then) fails only when the first part is true and the second false. A quantifier says how many things a claim is about: ∀ means every one, ∃ means at least one.

A statement has a truth value

A statement is a sentence that is either true or false; its truth value is 1 or 0, respectively. “9 > 8” is a statement. “Friday the 13th is unlucky” is not a statement here because it does not have a definite mathematical truth value. A claim may still be a statement even if its truth is not currently known.

The implication A ⇒ B is false in exactly one case: A is true and B is false. This is why a false premise makes the implication true under the truth-table definition; it does not claim that the conclusion follows from a false premise in ordinary causal language. The notes’ reason: nothing false can be deduced from something true, but anything can come from something false. From the false statement 2=1, multiplying both sides by 0 gives the true statement 0=0.

Take “if it is raining, the street is wet”, with A = “it is raining” and B = “the street is wet”. It is true when rain wets the street, when it is dry and the street is dry, and when it is dry and the street is wet from a hose. It is false only when it rains and the uncovered street stays dry.

Tautologies and logical rules

A tautology is true for every assignment of truth values. Two forms are logically equivalent when their truth values agree in every row. A truth table is a direct proof for expressions with a small number of variables: four rows for two variables, eight for three.

Trap: the converse B ⇒ A is not generally equivalent to A ⇒ B. “If it rains, the street is wet” does not imply “if the street is wet, it rained.” (The contrapositive ¬B ⇒ ¬A has the same truth table as A ⇒ B. This follows directly from the notes’ truth table; the notes do not name it.)

Predicates and quantifiers

A propositional form A(x₁,…,x_n) depends on variables; assigning values turns it into a statement. For A(x,y): 5+x=10y, A(5,1) is true and A(6,1) is false. Below, P(x) is a form in one variable. A quantifier specifies how many values in a domain must satisfy it.

Let D be a dog and P a person. ∃D ∀P: D bites P says one dog bites everyone. ∀P ∃D: D bites P says each person is bitten by some dog, possibly different dogs.

Negation changes “every” to “there exists at least one counterexample”, and changes “there exists” to “none exist”.

Memory hook: to disprove a universal claim, give one counterexample. To prove an existential claim, give one witness.

Applications: voting, circuits and SAT

These apply the truth rules; they add no new operators.

• Safety voting. Aircraft and spacecraft use three independent sensors for one quantity. V is 1 when at least two report 1, so one faulty sensor cannot change V when the other two agree.
• Circuits. Logic gates realise ¬, ∧ and ∨. In hardware design the truth table is fixed in advance, and the task is the smallest circuit that achieves it. The simplification above replaces four gates by one wire.
• SAT. Satisfiability asks: given a formula F(A₁,…,A_n), is there an assignment of truth values that makes F true? A∧¬B is satisfiable, with A=1, B=0. A∧¬A is not, since no assignment makes it true. SAT solvers test and verify hardware and model constraints in scheduling and planning.

Near miss: “if n is divisible by 4, then n is even” is true, and its converse “if n is even, then n is divisible by 4” sounds just as reasonable, but it fails at n = 2. One counterexample is enough to sink a universal claim.

Try it: truth-table experiments and quantifier experiments; sensor-vote and circuit experiments.

1.2 Set Theory

Sets let us collect objects by a precise membership rule. Logical connectives reappear here as operations on membership conditions.

In plain words: a set is a collection with a clear membership test: for any object you can say whether it is in or out. The union A ∪ B collects everything in either set, the intersection A ∩ B keeps what is in both, and the difference A \ B keeps what is in A but not in B. Each operation is a logic connective applied to the membership test.

Membership, descriptions, and inclusion

A set is a well-defined collection of distinct objects. Write x ∈ A when x is a member and x ∉ A otherwise. A set may be given by listing its elements, such as {1,2,3}, or by a property, such as {x ∈ ℝ : x > 0}. The notes also write {x | A(x)} for {x : A(x)}. The solutions of x³−2x=0 form {x : x³=2x}={0,√2,−√2}. Order and repetition do not change a set.

The empty set ∅={x : x≠x} has no elements and is a subset of every set. Every set is also a subset of itself: X⊂X. Standard number sets are ℕ (positive natural numbers in these notes), ℤ (integers), ℚ (rationals), ℝ (reals), and ℂ (complex numbers).

Intervals, power sets, and size

Intervals describe parts of the real line. Round endpoints are excluded and square endpoints included: (a,b), [a,b), (a,b], [a,b]. Unbounded intervals include (a,∞) and (−∞,b]; the notes also use ℝ=(−∞,∞), ℝ⁺=(0,∞), and ℝ_≥0=[0,∞). The power set 𝒫(X) contains every subset of X. For finite X, cardinality |X|, also written #X, counts its elements, and |𝒫(X)| = 2^|X|.

Set operations

Each operation is easiest to understand by asking when an arbitrary element x belongs to the result. Sets with empty intersection are called disjoint.

Union collects elements in either set; intersection keeps elements in both; difference keeps elements in A but removes those in B. The Cartesian product contains ordered pairs, not sets of the factors.

Set algebra and De Morgan’s laws

Set identities can be proved by translating both sides into membership conditions. For example, x ∈ (A∩B)ᶜ exactly when x∉A∩B; this means it is not true that x is in both sets, or equivalently x∉A or x∉B. Thus x∈Aᶜ∪Bᶜ, proving (A∩B)ᶜ=Aᶜ∪Bᶜ.

Trap: A\B is not generally B\A. Check the direction by testing membership: the first set supplies candidates; the second removes them.

Near miss: {1, 2} ⊂ {1, 2, 3} is true, but {1, 4} ⊂ {1, 2, 3} fails: the single element 4 lies outside, and one element outside is enough.

Try it: set-operation experiments and finite-set experiments; interval experiments.

Formula map and notation

Check every answer: for logic, test all truth assignments; for sets, test membership element by element and state the universal set when using complements.

Derive it cold

Rebuild these on blank paper before opening the answers in the relevant sections.

1. Use the truth table to derive A⇒B ⇔ ¬A∨B. §1.1
2. Use the truth table to derive both logical De Morgan laws. §1.1
3. Negate a universal and an existential statement by swapping quantifiers and negating the predicate. §1.1
4. Prove one set identity by writing an arbitrary x-membership condition for each side. §1.2
5. Derive the set De Morgan laws from the logical De Morgan laws and membership tests. §1.2

Explain it

Answer each “why” in your own words before checking the model response.

1. Why is A⇒B true when A is false under the truth-table definition?
2. Why does matching truth-table columns prove equivalence?
3. Why can one counterexample disprove a universal statement?
4. Why does quantifier order change the meaning of a claim about dogs and people?
5. Why must the universal set be fixed to define a complement?
6. Why is A\B different from B\A?
7. Why are ordered pairs in A×B generally not the same as those in B×A?
8. Why can a set identity be proved by comparing membership conditions?

Mixed practice

Try all 33 problems before opening the answer key. The sections alternate so you must identify the right tool.

1. For A=1 and B=0, evaluate ¬A, A∧B, A∨B, A⇒B, and A⇔B.
2. Let A={1,2,3}, B={3,4}. Find A∪B, A∩B, A\B, and B\A.
3. Is “There are infinitely many twin primes” a statement even if its truth is unproven? Explain briefly.
4. Let X={p,q,r}. List 𝒫(X) and state its cardinality.
5. Use a truth table to verify ¬(A⇒B) ⇔ A∧¬B. Which input row makes both sides true?
6. Let A=[0,2] and B=(1,3). Find A∩B and A∪B.
7. Negate: “For every integer n, n²≥0.”
8. Let X={1,2,3,4} and A={1,4}. Find Aᶜ relative to X.
9. Build a truth table for ¬(A∨B). In which row is it true?
10. If |X|=3, how many elements does 𝒫(X) have?
11. Translate “There is exactly one real x such that x²=4” using quantifier notation.
12. Let A={1,2}, B={x,y,z}. List A×B.
13. Are A⇒B and B⇒A equivalent for all A,B? Give one truth assignment that disproves equivalence.
14. Let X=ℝ and A=(−1,3]. Describe Aᶜ as intervals.
15. Let P(x) mean “x is even”, with domain ℤ. Write “some integer is not even” symbolically.
16. Let A={1,2,3}, B={2,3,4}, C={3,4,5}. Find A∩(B∪C).
17. Classify each as a statement or not: (i) 4 is prime; (ii) x+1=2; (iii) 4 is lucky.
18. Use De Morgan’s law to simplify (A∩B)ᶜ.
19. For A=0 and B=0, compare A⇒B with ¬A∨B. Then use a truth table to verify ¬(A∧B) ⇔ ¬A∨¬B.
20. Let A={1,2,3,4} and B={2,4}. Is B⊂A? Is B⊊A?
21. Negate: “There exists a real x such that x²<0.”
22. Let X={1,2,3,4,5}, A={1,2,3}, B={3,4}. Find (A∪B)ᶜ relative to X.
23. Let S be a student and T a tutor. Compare ∃T ∀S: T helps S with ∀S ∃T: T helps S in plain language.
24. For A={1,2} and B={2,3}, find A×B and B×A. State one ordered pair in only one of them.
25. Simplify (A∨B)∧(A∨¬B) with the logical rules, naming each rule. How many gates does this remove?
26. Let A={1,3}, B={2,4}, C={3,4}. Which pairs of these sets are disjoint?
27. For the sensor vote V, find V for A=B=1 with C=0 and with C=1. Then repeat for A=1, B=0. What do the results show about a faulty third sensor?
28. Let A₁={1,2}, A₂={2,3}, A₃={2,4}. Find ⋃_k=1³A_k and ⋂_k=1³A_k. How many elements has ∏_k=1³A_k? Give one.
29. Negate ∀S ∃T: T helps S, and say it in words.
30. Describe [0,2]×[1,3] as a set in ℝ² and name its shape. Is (2,3) in it? Is (3,2)?
31. Use an 8-row truth table to prove A∧(B∨C) ⇔ (A∧B)∨(A∧C).
32. List every element of {0,1}³. What do they represent geometrically?
33. Is (A∨B)∧¬A satisfiable? Is (A∨B)∧¬A∧¬B? Give an assignment or a reason.

Exam-style problems

Set a timer for about 20 minutes per problem. Write the reasoning, not just the final values.

1 · Logic for a sensor check

Three sensors report truth values A, B, and C. A majority vote is represented by V=(A∧B)∨(A∧C)∨(B∧C).

1. Make a truth table for V and identify the rows where V=1.
2. Show that swapping any two sensor labels leaves V unchanged, using commutativity of ∧ and ∨.
3. Negate the claim “For every sensor configuration with at most one report equal to 1, the majority output is 0.” State the form of a counterexample.
4. Let S be the set of configurations (A,B,C) in X={0,1}³ with V=1. List S, then find |S| and |Sᶜ| relative to X.

2 · Sets of admissible inputs

Let the universal set be X={1,2,3,4,5,6,7,8}. Let A be the even elements of X, B={1,2,3,4}, and C={3,4,5,6}.

1. List A, A∩B, and A∪B.
2. Find (B∪C)ᶜ and Bᶜ∩Cᶜ relative to X, and use the results to check a De Morgan identity.
3. Let D={red, blue}. List A×D and give its cardinality.
4. Write “every element of A∩B is even” with a quantifier, negate it, and say which of the two is true.

Slips in the notes

These are the places where the notes are wrong, loose or need a qualification, and where this guide differs from them. Printed page numbers refer to the notes.

1. Printed page 3, error: the example gives ¬(9 ≥ 8) as “9 ≤ 8”. The negation of ≥ is <, so it should be 9 < 8. The printed form happens to be false too, but it is not the negation: 8 ≤ 8 and 8 ≥ 8 both hold.
2. Printed page 4, error: the two coffee sentences are not equivalent. “Milk or sugar, then I do not drink” is (M∨S)⇒¬D, which is equivalent to its contrapositive D⇒(¬M∧¬S). The printed second sentence, (¬M∧¬S)⇒D, is the converse of that. They differ for M=S=D=0, where the first is true and the second false. R9 alone only rewrites the premise. This guide leaves the example out.
3. Printed page 9, edge case: the notes say that A×B is neither contained in A nor in B. If either factor is empty, then A×B=∅, and ∅ is a subset of both factors. The definition of the Cartesian product remains correct; the remark about containment is too broad for empty factors.
4. Printed page 5, minor: “x is divisible only by 1 and itself” is glossed as “x is prime”, but x=1 satisfies the formula and is not prime. The quantified statement stays true.
5. Printed page 6, loose wording: “a single faulty sensor cannot change the truth value” holds only when the other two sensors agree, which is how the page ends (“two sensors must agree”) and how §1.1 here states it. If they disagree, the third decides V.
6. Printed page 6, notation: the remark on the crossed-out ∃ joins statements with “=”. This guide writes ⇔ between statements.
7. Printed page 7, minor: Definition 1.8(iii) writes A = B :⇔ (x∈A ⇔ x∈B) without the ∀x that part (i) has. This guide uses the wording of that definition, A⊂B and B⊂A, which carries the quantifier.
8. Printed page 3, typographic: leftover German (“Dann gilt für die neuen Aussagen”) stands before the English sentence. It has no effect on the content.

Self-check

Use day 0 to learn and practise. Tick a skill only in a later session, at least one day afterward, when you can show it without notes. Use the listed problem numbers as evidence.

• Evaluate all five logical connectives from input truth values. (1, 5, 9, 13, 19, 27)
• Distinguish a statement from an open or undefined sentence. (3, 17)
• Prove equivalence with complete truth tables, simplify, and test satisfiability. (5, 19, 25, 31, 33)
• Translate and negate quantified claims. (7, 11, 15, 21, 23, 29)
• Compute unions, intersections, and differences from membership, for two or n sets. (2, 6, 16, 26, 28)
• Use subset, proper subset, and equality definitions. (20)
• Find complements relative to an explicit universe. (8, 14, 22)
• Enumerate small power sets and count subsets. (4, 10)
• List Cartesian products and track coordinate order. (12, 24, 30, 32)
• Apply De Morgan’s laws to statements and sets. (18, 19)
• Rebuild the listed derivations from definitions.
• Solve both multi-part problems and justify each step.