1 Boolean Logic

What is the difference between searching Google for the following:

“cat OR dog sign”
“cat AND dog sign”

Suppose I like mystery and comedy movies, but I don’t like Halloween. What do I search for?

Boolean logic involves the classification of items into sets using keywords like:

Boolean logic was developed by the 19th-century English mathematician George Boole.

Question: Suppose I want to learn about what George Boole himself wrote about logic. What do I search for?

“George Boole” OR logic
“George Boole” AND logic
“George Boole” NOT logic

Boolean logic most often involves classifying items in sets.

Question: Describe all numbers from 1 to 9 (including 1 and 10) that meet the condition:

even
divisible by 3
even OR divisible by 3.
even AND divisible by 3.

Boolean operators are directly related to the mathematical set operators:

Union = $\cup$
Intersection = $\cap$
Complement = $^c$

Express the statements (a)-(d) above using this set of operators.

Questions: Describe the numbers from 1 to 20 that meet the condition:

(even) $\cap$ (multiples of 5)

A = {2,4,5,6,8,10,12,14,15,16,18,20}
B = {2,4,6,8,12,14,16,18}
C = {5,10,15,20}
D = {10,20}
(even) $\cup$ (multiples of 5)

A = {2,4,5,6,8,10,12,14,15,16,18,20}
B = {2,4,6,8,12,14,16,18}
C = {5,10,15,20}
D = {10,20}
(even) $\cap$ (multiples of 5)$^c$

A = {2,4,5,6,8,10,12,14,15,16,18,20}
B = {2,4,6,8,12,14,16,18}
C = {5,10,15,20}
D = {10,20}

Clearing up ambiguity

The English phrase “Go to the store and buy me eggs and bagels or cereal” is ambiguous; this could mean either of the following.

A. Buy eggs and (bagels or cereal) - I want eggs, and I want either bagels or cereal.
B. Buy (eggs and bagels) or cereal - I want eggs and bagels, or I want cereal.

For this reason, using parentheses clarifies the intent. See examples below.

Written Homework:

Describe the numbers from 1 to 30 that meet the condition:

(Even) $\cap$ (multiple of 5 $\cup$ multiple of 7)

A = {10,14,20,28,30}
B = {10,14,20,21,28,30}
C = {7,10,14,20,21,28,30}
(Even $\cap$ multiple of 5) $\cup$ (multiple of 7)

A = {10,14,20,28,30}
B = {10,14,20,21,28,30}
C = {7,10,14,20,21,28,30}

$~$

2 Conditional Logic

A statement (or proposition) is a sentence that is either true or false.

Question: Which of the following are statements.

Water freezes at 0 degrees Celsius.
There are 26 hours in a day.
The Earth orbits the Mars.
How old are you?
Please close the door.
If only I could fly!

A conditional statement is a compound statement of the form:

“If p then q” or
“If p then q, else s”.

In common language, we use conditional logic in statements like:

If it is raining, we’ll go to a movie.

If it is not raining, we’ll go to the lake.

2.1 Ways Logic Can Appear in Common Language

The phrase “if P, then Q” is logically equivalent to the following statements:

Q if P.
Whenever P, then also Q.
Q whenever P.
All P are Q.
No P is not Q.
Q, provided that P.

Here are some more technical ways to express “if P, then Q.”

For P (to occur), it is necessary that Q (occurs).
Q is a necessary condition for P.
For Q (to occur), it is sufficient that P (has occurred).
P is a sufficient condition for Q.

Practice: Translate “If it is raining, then there are clouds in the sky” into the above forms.

2.2 Conditional Logic with Spreadsheets

Conditional logic is commonly used in spreadsheet applications like Excel or Google Sheets.

Consider the expression.

=IF( A1<2000, A1+1, A1*2 )

This takes the value in cell A1, and then:

If A1<2000 is true, this cell will output the value in A1 plus one.
If A1<2000 is false ($A1\geq2000$), this cell will output the value in A1 times 2.

Question:
What does this cell output if A1=1000?

Question:
Consider the expression:

=IF(A1>5, 2*A1,3*A1)

This looks at the value in cell A1:

If A1>5 is true, this cell will output the value in A1 times 2.
If A1>5 is false ($A1\leq 5$), this cell will output the value in A1 times 3.

What does this cell output if A1=8?

$~$

Extra Credit Homework:

An accountant needs to withhold 15% of income for taxes if the income is below $30,000, and 20% of income if the income is $30,000 or more. Write an expression that would calculate the amount to withhold.

A. =IF(A1>30000, 0.15*A1, 0.20*A1)
B. =IF(A1<30000, 0.15*A1, 0.20*A1)
C. =IF(A1<30000, 0.20*A1, 0.15*A1)

A certain tax credit applies if someone with no dependents earns less than $10,000, or if someone with dependents earns less than $20,000. If in a spreadsheet, cell A1 contains annual income, and A2 contains the number of dependents, write a rule that describes this.

Hint: There are two ways the tax credit is applied

income is less than 10,000 and dependents is 0, or
income is less than 20,000 and dependents are not 0.

Informally, we could write these as:

(A1 < 10000 and A2 = 0) or (A1 < 20000 and A2 > 0)

In Excel format, we’d write

=IF( OR(AND(A1<10000, A2=0),
        AND(A1<20000, A2>0)),
    “you qualify”,
    “you don’t qualify”)

Type this formula in cell A3.

What is the output to this cell if A1 = 15000, A2 = 0?
What is the output to this cell if A1 = 15000, A2 = 1?
What is the output to this cell if A1 = 25000, A2 = 1?

$~$

3 Quantified Statements

A quantified statement is a logical statement that includes a quantifier to indicate the scope of the statement over a set of elements. Examples of quantifiers are:

for all, for every
there exists, at least one, some
there does not exist / none

A universal quantifier states that an entire set of things share a characteristic. They are words that describe an entire set:

all
every
none
no one

An existential quantifier states that a set contains at least one element. They are words that describe an on or more elements in a set:

at least one
some
one
someone

Characterize each of the following as a universally quantified or an existentially quanitified statement:

Someone in this class is named Bob.
All people in this class are named Bob.
There is a person in this class who speaks more than five languages.
For every triangle, the sum of its interior angles is 180 degrees.
There exists an integer such that $n^2 = 25$.
For every real number $x$, $x^2 \geq 0$.

What happens when you negate a universal quantifier?

Example: Suppose your friend tells you, “Everybody cheats on their taxes!”

What is the minimum amount of evidence you would need to prove your friend wrong?

What happens when you negate an existential quantifier?

Example: 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?

Write the negation of these statements:

Everyone failed the quiz today.

Someone in the car needs to use the restroom.

$~$

Written Homework:

Write the negation of the following statements:

“Somebody brought a flashlight.”
“There are no prime numbers that are even.”
“All Icelandic children learn English in school.”

$~$

4 Truth Tables

Here are some more commonly used symbols for and, or, and not.

Translate each statement into symbolic notation. Let:
P = “I like Pepsi”, and
C = “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.

$~$

Written Homework:

Translate “We have carrots or we will not make soup” into symbols. Let:

C = “We have carrots.” and
S = “We will make soup”.

Translate “I do not like carrots and I do not like zucchini” into symbols. Let:

C = “I like carrots” and
Z = “I like zucchini”

$~$

Note that the meaning of the above statement is equivalent in English to say “I do not like carrots nor zucchini,” OR “I do not (like carrots or like zucchini).”

Because complex Boolean statements can get tricky to think about, truth tables are a useful tool for keep track of truth values that make the complex statement true and false.

4.1 Conjunction, Disjunction, and Negation

The truth tables for the basic and, or, and not statements are shown below.

Example:
Create a truth table for the statement for $A \vee \mathord\sim B$.
Use it to determine, when is $A \vee \mathord\sim B$ false?

A. If A and B are both true
B. If A=true and B=false
C. IF A=false and B=true
D. If A and B are both false

$~$

Written Homework:

Create a truth table for the statement: $A \wedge (B \vee C)$

$~$

If A=T, B=T, C=F, what is the outcome of $A \wedge (B \vee C)$ true?
A: True
B: False

If A=F, B=T, C=T, what is the outcome of $A \wedge (B \vee C)$ true?
A: True
B: False

4.2 Conditional Statements

A conditional is a logical compound statement in which a statement p, called the antecedent, implies a statement q, called the consequent.

A conditional is written as $p \to q$ and is translated as “if p, then q”.

Example: The English statement “If it is raining, then there are clouds in the sky” is a conditional statement. It makes sense because if the antecedent “it is raining” is true, then the consequent “there are clouds in the sky” must also be true.

Example: Construct a truth table for the statement:

\[ \mathord\sim p \to r\]

4.3 Converse, Inverse, and Contrapositive Statements

Consider again the conditional “If it is raining, then there are clouds in the sky.” It seems reasonable to assume that this is true.

The converse would be “If there are clouds in the sky, then it is raining.” This is not always true.

The inverse would be “If it is not raining, then there are not clouds in the sky.” Likewise, this is not always true.

The contrapositive would be “If there are no clouds in the sky, then it is not raining.” This statement is true and is equivalent to the original conditional.

Example:
Suppose this statement is true: “If I eat this giant cookie, then I will feel sick.” Which of the following statements must also be true?

If I feel sick, then I ate that giant cookie.
If I don’t eat this giant cookie, then I won’t feel sick.
If I don’t feel sick, then I didn’t eat that giant cookie.

Written Homework:

“If you microwave salmon in the staff kitchen, then I will be mad at you.” If this statement is true, which of the following statements must also be true?

If you don’t microwave salmon in the staff kitchen, then I won’t be mad at you.
If I am not mad at you, then you didn’t microwave salmon in the staff kitchen.
If I am mad at you, then you microwaved salmon in the staff kitchen.

4.4 Negating a conditional

Consider the statement “If you park here, then you will get a ticket.” What set of conditions would prove this statement false?

You don’t park here and you get a ticket.
You don’t park here and you don’t get a ticket.
You park here and you don’t get a ticket.

$~$

Task: Write the logic tables for the following and compare:

$p \wedge \mathord\sim q$

$~$

$\mathord\sim(p \to q)$

$~$

Example: Suppose you order a team jersey online on Tuesday and want to receive it by Friday so you can wear it to Saturday’s game.

The website says that if you pay for expedited shipping, you will receive the jersey by Friday.

In what situation is the website telling a lie?

You pay for expedited shipping and receive the jersey by Friday
You pay for expedited shipping and don’t receive the jersey by Friday
You don’t pay for expedited shipping and receive the jersey by Friday
You don’t pay for expedited shipping and don’t receive the jersey by Friday

Written Homework:

A friend tells you “If you upload that picture to Facebook, you’ll lose your job.”

Under what conditions can you say that your friend was wrong?

You upload the picture and lose your job
You upload the picture and don’t lose your job
You don’t upload the picture and lose your job
You don’t upload the picture and don’t lose your job

Which of the following statements is equivalent to the negation of “If you don’t grease the pan, then the food will stick to it”?

I didn’t grease the pan and the food didn’t stick to it.
I didn’t grease the pan and the food stuck to it.
I greased the pan and the food didn’t stick to it.

Which of the following statements is equivalent to the negation of this statement:
“If you go swimming less than an hour after eating lunch, then you will get cramps.”

I went swimming for more than an hour after eating lunch and I got cramps.
I went swimming less than an hour after eating lunch and I didn’t get cramps
I went swimming more than an hour after eating lunch and I didn’t get cramps.

4.5 Biconditional Statements

A biconditional is a logical conditional statement in which the antecedent and consequent are interchangeable.

The biconditional is written $p \leftrightarrow q$, read “p if and only if q.”

The biconditional is the same as $(p \to q)\wedge(q \to p)$.

Task: Find the truth table for the biconditional using this fact.

$~$

Written Homework:

Suppose this statement is true: “I wear my running shoes if and only if I am exercising.” Determine whether each of the following statements must be true or false.

I am exercising and I am not wearing my running shoes.

A = True
B = False

I am wearing my running shoes and I am not exercising.

A = True
B = False

I am not exercising and I am not wearing my running shoes.

A = True
B = False

5 De Morgan’s Laws

Example: To serve as the President of the US, a person must have been born in the US, must be at least 35 years old, and must have lived in the US for at least 14 years. What minimum set of conditions would disqualify someone from serving as President?

$~$

Written Homework:

For Valentine’s Day, you did not get your sweetie flowers or candy: Which of the following statements is logically equivalent?

You did not get them flowers or did not get them candy.
You did not get them flowers and did not get them candy.
You got them flowers or got them candy.

$~$

Consider the statement: “He does not (like carrots or zucchini).” Let C = “I like carrots” and Z = “I like zucchini.” Write this statement using symbolic logic. Then determine, which of the following is equivalent to the original statement?

~C $\wedge$ ~Z (He does not like carrots, and he does not like zucchini.)
~C $\vee$ ~Z (He does not like carrots, or he does not like zucchini.)

6 Deductive Arguments

Argument types:

An inductive argument uses a collection of specific examples as its premises and uses them to propose a general conclusion.
A deductive argument uses a collection of general statements as its premises and uses them to propose a specific situation as the conclusion.

6.1 Evaluating Deductive Arguments with Euler Diagrams

Arguments can be analyzed with an Euler diagram, also called a Venn diagram.

Use a Venn diagram, truth table, or common form of an argument to decide whether each argument is valid or invalid. Explain your reasoning.

All cats are mammals. A tiger is a cat. Therefore, a Tiger is a mammal.

No cows are purple. Fido is not a cow. Therefore, Fido is purple.

If a person is on this reality show, they must be self-absorbed. Laura is not self-absorbed. Therefore, Laura cannot be on this reality show.

If you are a triathlete, then you have outstanding endurance. LeBron James is not a triathlete. Therefore, LeBron does not have outstanding endurance.

Written Homework:

Some of these kids are rude. Jimmy is one of these kids. Therefore, Jimmy is rude!

If a creature is a chimpanzee, then it is a primate. If a creature is a primate, then it is a mammal. Bobo is a mammal. Therefore, Bobo is a chimpanzee.

6.2 Evaluating Deductive Arguments with Truth Tables

More complex arguments can also be analyzed with truth tables.

Is the following argument valid or invalid?

Premise: If you bought bread, then you went to the store.
Premise: You bought bread.
Conclusion: You went to the store.

A = Valid
B = Invalid

Premise: If I have a shovel, I can dig a hole.
Premise: I dug a hole.
Conclusion: Therefore, I had a shovel.

A = Valid
B = Invalid

Homework Questions:

Use truth tables (or other means) to evaluate whether the following is valid or invalid reasoning.

Premise: If I go to the mall, then I’ll buy new jeans.
Premise: If I buy new jeans, I’ll buy a shirt to go with it.
Conclusion: If I go to the mall, I’ll buy a shirt.
Premise: If I drop my phone into the swimming pool, my phone will be ruined.
Premise: My phone isn’t ruined.
Conclusion: I didn’t drop my phone in the swimming pool.
Premise: If you pull that fire alarm, you will get in big trouble.
Premise: You got in big trouble.
Conclusion: You must have pulled the fire alarm.
Premise: If I go to the party, I’ll be really tired tomorrow.
Premise: If I go to the party, I’ll get to see friends.
Conclusion: If I don’t see friends, I won’t be tired tomorrow.

7 Logical Fallacies

Ad hominem: This is Latin for “to the person” and denotes an argument attacking the person making the argument, ignoring the argument itself.

“Jane says that whales aren’t fish, but she’s only in the second grade, so she can’t be right.”

Appeal to ignorance: assuming something to be true because it hasn’t been proven false.

“Nobody has proven that photo isn’t of Bigfoot, so it must be Bigfoot.”

Appeal to authority: attempting to use the authority of a person to prove a claim. (While often authority can strengthen a case, it does not necessarily prove it.)

“A diet high in bacon can be healthy; Doctor Atkins said so.”

Appeal to consequence: concluding a premise is true or false based on whether the consequences are desirable or not.

“Humans will travel faster than light: faster-than-light travel would be beneficial for space travel.”

False dilemma: falsely framing an argument as an “either/or” choice without allowing for additional options.

“Either those lights in the sky were an airplane or aliens. There are no airplanes scheduled for tonight, so it must be aliens.”

Circular reasoning: relying on the conclusion being true for the premise to be true.

“I shouldn’t have gotten a C in that class; I’m an A student!”

Post Hoc: “post hoc ergo proper hoc” meaning “after this, therefore because of this.” Claiming that because two things happened in sequence implies the first must have caused the second.

“Today I wore a red shirt, and my football team won! I need to wear a red shirt every time they play to make sure they keep winning.”

Correlation implies causation: Closely related to post hoc. Finding a correlation between two things DOES NOT imply causation!

“Months with high ice cream sales also have a high rate of deaths by drowning. Therefore, ice cream must be causing people to drown.”

Straw man: misrepresenting the argument in a less favorable way to make it easier to attack.

“Senator Jones has proposed reducing military funding by 10%. Apparently, he wants to leave us defenseless against attacks by terrorists.”

Written Work:

Identify each logical fallacy.

“Since the 1950s, both the atmospheric carbon dioxide level and obesity levels have increased sharply. Hence, atmospheric carbon dioxide causes obesity.”