The Relationship Between Sets and Logic

Logic and set theory are closely intertwined. The truth value of a statement (true/false) corresponds to whether an element is in a set or not. Therefore, logical operations work very similarly to set operations.

Correspondence Between Logic and Sets

• Logical AND (p ∧ q) ↔ Set intersection (A ∩ B) → an element is in the intersection if it is in both sets.
• Logical OR (p ∨ q) ↔ Set union (A ∪ B) → an element is in the union if it is in at least one set.
• Logical NOT (¬p) ↔ Set complement (Aᶜ) → all elements not in the set.
• Implication (p → q) ↔ Subset (A ⊆ B) → if every element of A is in B, then p → q is always true.
• Equivalence (p ↔ q) ↔ Set equality (A = B) → true if they contain exactly the same elements.

Concrete Examples

Let A = {1,2,3}, B = {2,3,4}. Let's see how the operations correspond:

• A ∩ B = {2,3} ↔ p ∧ q → only those elements that are in both sets.
• A ∪ B = {1,2,3,4} ↔ p ∨ q → every element that is in at least one.
• Aᶜ (interpreted over integers) = {..., -1,0,4,5,...} ↔ ¬p → everything not in A.
• A ⊆ B? → no, because e.g. 1 ∈ A but 1 ∉ B → this corresponds to when an implication can be false.
• If A = {2,3}, B = {2,3} → A = B ↔ p ↔ q → complete identity, like equivalence.

Why is this relationship useful?

The correspondence between logic and set theory is important because it connects two ways of thinking: the truth values of statements and the membership of elements in sets. This allows us to:

• Illustrate logical laws with set operations.
• Represent truth tables with set diagrams (Venn diagrams).
• Better understand subsets, unions, and intersections through logical examples.
• In computer science, apply set and logical operations uniformly in databases, programming, and search algorithms.

Venn Diagram Illustration

Logical operations are often illustrated with Venn diagrams. In these, sets are represented by circles, and intersection, union, complement are clearly visible as regions.

Venn diagram of two sets: the overlapping part is the intersection (A ∩ B).

Summary

Aligning logical operations with set operations helps us understand both areas at once. Logic → truth values, set theory → element membership. But the underlying rules are the same.

Practice Exercise