Logic Basics: Learn It 1

  • Combine sets using Boolean logic and proper notation
  • Create and interpret expressions using statements and conditionals
  • Construct and analyze truth tables for complex statements or conditionals
  • Determine the logical equivalence between two statements

Logic

Logic is a systematic way of thinking that allows us to deduce new information from old information and to parse the meanings of sentences. You use logic informally in everyday life and certainly also in doing mathematics. Logic is, basically, the study of valid reasoning.

For example, suppose you are working with a certain circle, call it “Circle [latex]X[/latex],” and you have available the following two pieces of information.

  1. Circle [latex]X[/latex] has radius equal to [latex]3[/latex].
  2. If any circle has radius [latex]r[/latex], then its area is [latex]\pi{r}^{2}[/latex] square units.

You have no trouble putting these two facts together to get:

  1. Circle [latex]X[/latex] has area [latex]9\pi[/latex] square units.

You are using logic to combine existing information to produce new information. Since a major objective in mathematics is to deduce new information, logic must play a fundamental role. This chapter is intended to give you a sufficient mastery of logic.

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 set operations with the same terminology.

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 boolean search is true if the element in question is part of the set being searched.

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.

Connection to set operations:

[latex]\begin{array}{r@{\hfill}l}
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{array}[/latex]
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.
Suppose we are searching a library database for Mexican universities. Express a reasonable search using Boolean logic.

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”

Which Comes First?

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.

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
Describe the numbers that meet the condition: odd number and less than [latex]20[/latex] and greater than [latex]0[/latex] and (multiple of [latex]3[/latex] or multiple of [latex]5[/latex]).

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.

quantifiers

  • An universal quantifier states that an entire set of things share a characteristic.
    • Notation: The universal quantifier is typically symbolized by [latex]\forall[/latex] (an inverted letter ‘A’), which stands for “for all” or “for every.”
  • An existential quantifier states that a set contains at least one element.
    • Notation: The existential quantifier is symbolized by [latex]\exists[/latex] (a backwards letter ‘E’), which stands for “there exists.”
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.

Something interesting happens when we negate – or state the opposite of – a quantified statement. When we negate a statement with a universal quantifier, we get a statement with an existential quantifier, and vice-versa.

negating a quantified statement

The negation of “all [latex]A[/latex] are [latex]B[/latex]” is “at least one [latex]A[/latex] is not [latex]B[/latex] .”

 

The negation of “no [latex]A[/latex] are [latex]B[/latex]” is “at least one [latex]A[/latex] is [latex]B[/latex] .”

 

The negation of “at least one [latex]A[/latex] is [latex]B[/latex]” is “no [latex]A[/latex] are [latex]B[/latex] .”

 

The negation of “at least one [latex]A[/latex] is not [latex]B[/latex]” is “all [latex]A[/latex] are [latex]B[/latex] .”

Write the negation of this statement: “Somebody brought a flashlight.”

definition