Section 3.1 Introduction to Logic
Objectives
Introduce Boolean logic.
Define conditional statements.
Discuss quantified statements and how to negate them.
Write statements in symbolic form.
Subsection 3.1.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 3.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.
Note 3.1.2.
Connection to Set Operations
A and B: elements in the intersection \(A \cap B\)
A or B: elements in the union \(A \cup B\)
not A: elements in the complement \(A^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.
Example 3.1.3.
Suppose we are searching a library database for Mexican universities. Express a reasonable search using Boolean logic.
Solution.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”.
Example 3.1.4.
Describe the numbers that meet the condition:
even and less than 10 and greater than 0
Solution.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.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)
Solution.The first three conditions limit us to the set {1, 3, 5, 7, 9, 11, 13, 15, 17, 19}
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}
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:
{3, 5, 9, 15, 20, 25, 30, 35, 40, 45, …}
Example 3.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:
Eggs and (bagels or cereal) means Option 1: Eggs and bagels, Option 2: Eggs and cereal
(Eggs and bagels) or cereal means Option 1: Eggs and bagels, Option 2: Cereal
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.
Subsection 3.1.2 Conditional Statements
Beyond searching, Boolean logic is commonly used in spreadsheet applications like Excel to do conditional calculations. A statement is something that is either true or false. A statement like \(3 \le 5\) is true; a statement like “a rat is a fish” is false. A statement like \(x \le 5\)” is true for some values of x and false for others. When an action is taken or not depending on the value of a statement, it forms a conditional.
Definition 3.1.7. Statements and Conditionals.
A statement is either true or false.
A conditional is a compound statement of the form “if p then q” or “if p then q, else s”.
Example 3.1.8.
In common language, an example of a conditional statement would be “If it is raining, then we’ll go to the mall. Otherwise we’ll go for a hike.”
The statement “If it is raining” is the condition - this may be true or false for any given day. If the condition is true, then we will follow the first course of action, and go to the mall. If the condition is false, then we will use the alternative, and go for a hike.
Example 3.1.9.
A parent might say to their child “if you clean your room and take out the garbage, then you can have ice cream.”
Here, there are two simpler conditions:
The child cleaning her room.
The child taking out the garbage
Since these conditions were joined with and, the combined conditional will be true only if both simpler conditions are true; if either chore is not completed, then the parent’s condition is not met.
Notice that if the parent had said “if you clean your room or take out the garbage, then you can have ice cream”, then the child would need to complete only one chore to meet the condition.
Subsection 3.1.3 Quantified Statements
Words that describe an entire set, such as “all”, “every”, or “none”, are called universal quantifiers because that set could be considered a universal set. In contrast, words or phrases such as “some”, “one”, or “at least one” are called existential quantifiers because they describe the existence of at least one element in a set.
Definition 3.1.10. Quantifiers.
A universal quantifier states that an entire set of things share a characteristic.
An existential quantifier states that a set contains at least one element.
Something interesting happens when we negate - or state the opposite of - a quantified statement.
Example 3.1.11.
Suppose your friend says “Everybody cheats on their taxes.” What is the minimum amount of evidence you would need to prove your friend wrong?
To show that it is not true that everybody cheats on their taxes, all you need is one person who does not cheat on their taxes. It would be perfectly fine to produce more people who do not cheat, but one counterexample is all you need.
It is important to note that you do not need to show that absolutely nobody cheats on their taxes.
Example 3.1.12.
Suppose your friend says “One of these six cartons of milk is leaking.” What is the minimum amount of evidence you would need to prove your friend wrong?
Solution.When we negate a statement with a universal quantifier, we get a statement with an existential quantifier, and vice-versa.
Note 3.1.13. Negating a quantified statement.
The negation of “all A are B” is “at least one A is not B”.
The negation of “no A are B” is “at least one A is B”.
The negation of “at least one A is B” is “no A are B”.
The negation of “at least one A is not B” is “all A are B”
Example 3.1.14.
“Somebody brought a flashlight.” Write the negation of this statement.
Solution.Example 3.1.15.
“There are no prime numbers that are even.” Write the negation of this statement.
Solution.Problem 3.1.16. Try It Now.
Write the negation of “All Icelandic children learn English in school.”
Answer.Subsection 3.1.4 Statements in Symbolic Form.
Before we focus on truth tables, we’re going to introduce some symbols that are commonly used for and, or, and not.
Note 3.1.17. Symbols.
Some of the symbols that are used for and, or, and not are:
The symbol \(\wedge\) is used for and: A and B is notated \(A \wedge B\)
The symbol \(\vee\) is used for or: A or B is notated \(A \vee B\)
The symbol \(\sim\) is used for not: not A is notated \(\sim A\)
You can remember the first two symbols by relating them to the shapes for the union and intersection. \(A \wedge B\) would be the elements that exist in both sets, in \(A \cap B\text{.}\) Likewise, \(A \vee B\) would be the elements that exist in either set, in \(A \cup B\text{.}\) When we are working with sets, we use the rounded version of the symbols; when we are working with statements, we use the pointy version.
Example 3.1.18.
Translate each statement into symbolic notation. Let P represent “I like Pepsi” and let C represent “I like Coke”.
I like Pepsi or I like Coke.
I like Pepsi and I like Coke.
I do not like Pepsi.
It is not the case that I like Pepsi or Coke.
I like Pepsi and I do not like Coke.
\(\displaystyle P \vee C\)
\(\displaystyle P \wedge C\)
\(\displaystyle \sim P\)
\(\displaystyle \sim \left( P \vee C \right)\)
\(\displaystyle P \wedge \sim C\)
As you can see, we can use parentheses to organize more complicated statements.
Problem 3.1.19. Try It Now.
Translate “We have carrots or we will not make soup” into symbols. Let C represent “we have carrots” and let S represent “we will make soup”.
Answer.