Skip to main content

Section 17.1 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 19th-century English mathematician George Boole.)

Definition 17.1.1. Boolean Logic.

Boolean logic combines multiple statements that are either true or false into an expression that is either true or false.

In connection to sets, a search is true if the element is part of the set.

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.

Definition 17.1.2. Connection to Set Operations.
\begin{align*} A\text{ and }B && \text{elements in the intersection } A\cap B\\ A\text{ or }B && \text{elements in the union } A\cup B\\ \text{not }A && \text{elements in the complement } A^c \end{align*}

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.

Example 17.1.3.

Suppose we are searching a library database for Mexican universities. Express a reasonable search using Boolean logic.

We could start with the search “Mexico and university”, but would be likely to find results for the U.S. state New Mexico. To account for this, we could revise our search to read:

Mexico and university not “New Mexico”

Example 17.1.4.

Describe the numbers that meet the condition:

even and less than 10 and greater than 0.

The numbers that satisfy all three requirements are \(\{2, 4, 6, 8\}\text{.}\)

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

Example 17.1.5.

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).

The first three conditions limit us to the set \(\{1, 3, 5, 7, 9, 11, 13, 15, 17, 19\}\text{.}\)

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 \(\{3, 5, 9, 15\}\text{.}\)

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\}\text{.}\) When combined with the last condition, though, this set expands without limits:

\begin{equation*} \{3, 5, 9, 15, 20, 25, 30, 35, 40, 45, \ldots\}. \end{equation*}
Example 17.1.6.

The English phrase “Go to the store and buy me eggs and bagels or cereal” is ambiguous; it is not clear whether the requestors is asking for eggs always along with either bagels or cereal, or whether they’re asking for either the combination of eggs and bagels, or just cereal.

For this reason, using parentheses clarifies the intent:

\begin{align*} \text{Eggs and (bagels or cereal) } &\text{means}& \text{Option 1: Eggs and bagels, Option 2: Eggs and cereal}\\ \text{(Eggs and bagels) or cereal } &\text{means}& \text{Option 1: Eggs and bagels, Option 2: Cereal} \end{align*}

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.

Exercises 17.1.1 Exercises

For questions 1-2, list the set of integers that satisfy the given conditions.

1.

A positive multiple of 5 and not a multiple of 2.

Answer

\(\{5, 15, 25, \ldots \}\text{.}\)

2.

Greater than 12 and less than or equal to 18.