Lesson 5-1: Sets & Logic

Master set operations, logical connectives, truth tables, predicates, quantifiers, and logical reasoning with practical applications in discrete mathematics.

Learning Objectives

Perform set algebra and prove identities using laws.
Build and analyze truth tables for complex propositions.
Translate between natural language and quantifiers/predicates.
Spot common fallacies and correctly negate quantified statements.

Core Set Operations

Basic Operations

A \cup B \text{ (Union): elements in A or B}

A \cap B \text{ (Intersection): elements in both A and B}

A - B \text{ (Difference): elements in A not in B}

Complement & Laws

\overline{A} \text{ (Complement): elements not in A}

\overline{A \cup B} = \overline{A} \cap \overline{B}

\overline{A \cap B} = \overline{A} \cup \overline{B}

Set Laws (De Morgan's Laws)

De Morgan's Laws

\overline{A \cup B} = \overline{A} \cap \overline{B}

\overline{A \cap B} = \overline{A} \cup \overline{B}

The complement of a union is the intersection of complements, and vice versa.

Other Important Laws

A \cup (B \cap C) = (A \cup B) \cap (A \cup C)

A \cap (B \cup C) = (A \cap B) \cup (A \cap C)

Propositional Logic

Logical Connectives

\neg p \text{ (NOT): negation}

p \land q \text{ (AND): conjunction}

p \lor q \text{ (OR): disjunction}

p \to q \text{ (IF-THEN): implication}

Truth Table Example

p	q	p ∧ q	p ∨ q	p → q
T	T	T	T	T
T	F	F	T	F
F	T	F	T	T
F	F	F	F	T

Predicates and Quantifiers

Universal Quantifier

\forall x \in S, P(x) \text{ (For all x in S, P(x) is true)}

Example: "All students are hardworking" becomes $\forall x \in \text{Students}, \text{Hardworking}(x)$

Existential Quantifier

\exists x \in S, P(x) \text{ (There exists x in S such that P(x) is true)}

Example: "Some students are brilliant" becomes $\exists x \in \text{Students}, \text{Brilliant}(x)$

Worked Examples

Example 1: Set Operations

Given $A = \{1, 2, 3\}$ and $B = \{2, 3, 4\}$ , find $A \cup B$ and $A \cap B$ .

Solution:

A \cup B = \{1, 2, 3, 4\}

A \cap B = \{2, 3\}

Example 2: Logical Negation

Negate the statement: "All birds can fly"

Solution:

\neg(\forall x \in \text{Birds}, \text{CanFly}(x))

\exists x \in \text{Birds}, \neg\text{CanFly}(x)

"There exists a bird that cannot fly"

Practice Problems

Problem 1

Prove that $\overline{A \cup B} = \overline{A} \cap \overline{B}$ using De Morgan's law.

x \in \overline{A \cup B} \Leftrightarrow x \notin A \cup B \Leftrightarrow x \notin A \text{ and } x \notin B \Leftrightarrow x \in \overline{A} \cap \overline{B}

Problem 2

Create a truth table for $(p \to q) \land (q \to r)$ .

\text{This is a chain of implications: } p \to q \to r

Key Takeaways

Set operations follow specific algebraic laws similar to arithmetic.
De Morgan's laws are fundamental for working with complements.
Truth tables provide a systematic way to analyze logical statements.
Quantifiers allow us to express statements about all or some elements.
Proper negation of quantified statements requires careful attention to quantifier changes.

Continue to Lesson 5-2 for graph theory basics.

← Back to 12th Grade Math ← Back to Unit 5 Next: Lesson 5-2 →

← Back to Unit 5 Next: Lesson 5-2 →