17.2 Boolean Logic

We can often classify items as belonging to sets. If you went the library to search for a book and they asked you to express your search using unions, intersections, and complements of sets, that would feel a little strange. Instead, we typically using words like “and”, “or”, and “not” to connect our keywords together to form a search. These words, which form the basis of Boolean logic, are directly related to our set operations. (Boolean logic was developed by the 19^th-century English mathematician George Boole.)

Suppose $M$ is the set of all mystery books, and $C$ is the set of all comedy books. If we search for “mystery”, we are looking for all the books that are an element of the set $M$ ; the search is true for books that are in the set.

When we search for “mystery and comedy”, we are looking for a book that is an element of both sets, in the intersection. If we were to search for “mystery or comedy”, we are looking for a book that is a mystery, a comedy, or both, which is the union of the sets. If we searched for “not comedy”, we are looking for any book in the library that is not a comedy, the complement of the set $C$ .

Notice here that or is not exclusive. This is a difference between the Boolean logic use of the word and common everyday use. When your significant other asks “do you want to go to the park or the movies?” they usually are proposing an exclusive choice – one option or the other, but not both. In Boolean logic, the or is not exclusive – more like being asked at a restaurant “would you like fries or a drink with that?” Answering “both, please” is an acceptable answer.

In most internet search engines, it is not necessary to include the word and; the search engine assumes that if you provide two keywords you are looking for both. In Google’s search, the keyword or has be capitalized as OR, and a negative sign in front of a word is used to indicate not. Quotes around a phrase indicate that the entire phrase should be looked for. The search from the previous example on Google could be written:

Mexico university -“New Mexico”

Sometimes statements made in English can be ambiguous. For this reason, Boolean logic uses parentheses to show precedent, just like in algebraic order of operations.

Example 3

Describe the numbers that meet the condition:

odd number and less than 20 and greater than 0 and (multiple of 3 or multiple of 5)

UNIVERSE = list(range(1, 51))       # EDIT: the numbers we are searching through

def search(name, condition):
    hits = [n for n in UNIVERSE if condition(n)]
    shown = hits if len(hits) <= 14 else hits[:14] + ["..."]
    print(f"{name}\n   -> {{{', '.join(str(h) for h in shown)}}}   ({len(hits)} found)")

search("even and less than 10 and greater than 0",
       lambda n: n % 2 == 0 and n < 10 and n > 0)

print()
search("odd and less than 20 and greater than 0 and (multiple of 3 OR multiple of 5)",
       lambda n: n % 2 == 1 and n < 20 and n > 0 and (n % 3 == 0 or n % 5 == 0))

print()
search("(odd and less than 20 and greater than 0 and multiple of 3) OR multiple of 5",
       lambda n: (n % 2 == 1 and n < 20 and n > 0 and n % 3 == 0) or n % 5 == 0)
print("   moving the parentheses let 'multiple of 5' escape every other condition,")
print("   so 20, 25, 30, ... come flooding in. Grouping is not decoration.\n")

# The same operators, done with sets - the book's point about and/or/not vs union/inter/comp
M = {"Poirot", "Gone Girl", "Clue", "The Thin Man"}          # mysteries
C = {"Clue", "Airplane", "The Thin Man", "Some Like It Hot"}  # comedies
LIBRARY = M | C
print(f"{'search':<28}{'set operation':<22}result")
print(f"{'mystery AND comedy':<28}{'M inter C':<22}{sorted(M & C)}")
print(f"{'mystery OR comedy':<28}{'M union C':<22}{sorted(M | C)}")
print(f"{'NOT comedy':<28}{'C complement':<22}{sorted(LIBRARY - C)}")
print(f"{'mystery AND NOT comedy':<28}{'M inter C complement':<22}{sorted(M - C)}")
print("\nnote 'or' in logic is never exclusive: a book that is both still shows up.")
# Try it: write your own condition, e.g. lambda n: n % 7 == 0 and not (n % 2 == 0)

Show solution

The first three conditions limit us to the set $open brace 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 close brace$

The last grouped conditions tell us to find elements of this set that are also either a multiple of 3 or a multiple of $5 .$ This leaves us with the set $open brace 3, 5, 9, 15 close brace$

Notice that we would have gotten a very different result if we had written

(odd number and less than 20 and greater than 0 and multiple of 3) or multiple of 5

The first grouped set of conditions would give {3, 9, 15}. When combined with the last condition, though, this set expands without limits:

$open brace 3, 5, 9, 15, 20, 25, 30, 35, 40, 45, and so on close brace$

Be aware that when a string of conditions is written without grouping symbols, it is often interpreted from the left to right, resulting in the latter interpretation.

Adapted from Math in Society by David Lippman, hosted on LibreTexts (math.libretexts.org) and licensed under CC BY-SA 3.0. Changes were made. License: CC-BY-SA-3.0.