Skip to main content
Engineering LibreTexts

4.2 The Boolean Algebra of Sets

  • Page ID
    9680
  • It is clear that set theory is closely related to logic. The intersection and union of sets can be defined in terms of the logical ‘and’ and logical ‘or’ operators. The notation {P(x)} makes it possible to use predicates to specify sets. And if is any set, then the formula x ∈ defines a one place predicate that is true for an entity if and only if is a member of A. So it should not be a surprise that many of the rules of logic have analogues in set theory.

    For example, we have already noted that ∪ and ∩ are commutative operations. This fact can be verified using the rules of logic. Let and be sets. According to the definition of equality of sets, we can show that ABby showing that ∀x((∪ B) ↔ (∈ ∪ A)). But for any x,

    ∈ ∪ ↔ ∈ ∨ ∈ B        (definition of ∪)

    ↔ ∈ ∨ ∈ A        (commutativity of ∨)

    ↔ ∈ ∪ A        (definition of ∪)

    The commutativity of ∩ follows in the same way from the definition of ∩ in terms of ∧and the commutativity of ∧, and a similar argument shows that union and intersection are associative operations.

    The distributive laws for propositional logic give rise to two similar rules in set theory. Let AB, and be any sets. Then

    A∪(BC) = (AB)∩(AC)

    and

    A∩(BC) = (AB)∪(AC)
    These rules are called the distributive laws for set theory. To verify the first of these laws, we just have to note that for any x,

    ∈ A∪(BC)        

    ↔ (∈ A) ∨ ((∈ B) ∧ (∈ C))        (definition of ∪, ∩)

    ↔ ((∈ A) ∨ (∈ B)) ∧ ((∈ A) ∨ (∈ C))        (distributivity of ∨)

    ↔ (∈ ∪ B) ∧ (∈ ∪ C)        (definition of ∪)

    ↔ ∈ ((∪ B) ∩ (∪ C))        (definition of ∩)

    The second distributive law for sets follows in exactly the same way.