Chapter 1
Subsections of Basics and Logic Puzzles
Basic Logical Reasoning
What is logical reasoning?
Logical reasoning is an analysis of an argument according to a set of rules. In this course, we will be learning several sets of rules for more formal analysis, but for now we will informally analyze English sentences and logic puzzles. This will help us practice the careful and rigorous thinking that we will need in formal proofs and in computer science in general.
Premises and conclusions
A premise is a piece of information that we are given in a logical argument. In our reasoning, we assume premises are true – even if they make no sense!
A conclusion in a logical argument is a statement whose validity we are checking. Sometimes we are given a conclusion, and we are trying to see whether that conclusion makes sense when we assume our premises are true. Other times, we are asked to come up with our own (valid) conclusion that we can deduce from our premises.
Example
Suppose we are given the following premises:
- Premise 1: If a person wears a red shirt, then they don’t like pizza.
- Premise 2: Fred is wearing a red shirt.
Given those pieces of information, can we conclude the following?
Fred doesn’t like pizza.
Yes! We take the premises at face value and assume them to be true (even though it is kind of ridiculous that shirt color has anything to do with a dislike of pizza). The first premise PROMISES that any time we have a person with a red shirt, then that person does not like pizza. Since Fred is such a person, we can conclude that Fred doesn’t like pizza.
Logical arguments with “OR”
Interpreting English sentences that use the word “or” can be tricky – the or can either be an inclusive or or an exclusive or. In programming, we are used to using an inclusive or – a statement like p || q is true as long as at least one of p or q is true, even if both are true. The only time a statement like p || q is false is if both p and q are false.
In English, however, the word “or” often implies an exclusive or. If a restaurant advertises that customers can choose “chips or fries” as the side for their meal, they are certainly not intending that a customer demand both sides.
However, since this course is focused on formal logic and analyzing computer programs and not so much on resolving language ambiguity, we will adopt the stance that the word “or” always means inclusive or unless otherwise specified.
Or example #1
With that in mind, suppose we have the following premises:
- I have a dog or I have a cat.
- I do not have a cat.
What can we conclude?
The only time an “or” statement true is when at least one of its parts is true. Since we already know that the right side of the or (“I have a cat”) is false, then we can conclude that the left side MUST be true. So we conclude:
I have a dog.
In general, if you have an or statement as a premise and you also know that one side of the or is NOT true, then you can always conclude that the other side of the or IS true.
Or example #2
Suppose we have the following premises:
- I have a bike or I have a car.
- I have a bike.
Can we conclude anything new?
First of all, I acknowledge that the most natural interpretation of the first premise is an exclusive or – that I have EITHER a bike OR a car, but not both. I think that is how most people would naturally interpret that sentence as well. However, in this course we will always consider “or” to be an inclusive or, unless we specifically use words like “but not both”.
With that in mind, the second premise is already sufficient to make the first premise true. Since I have a bike, the statement “I have a bike or I have a car” is already true, whether or not I have a car. Because of this, we can’t draw any further conclusions beyond our premises.
Or example 3
Suppose we have the following premises:
- I either have a bike or a car, but not both.
- I have a bike.
What can we conclude?
This is the sentence structure I will use if I mean an exclusive or – “either p or q but not both”.
In this setup, we CAN conclude that I do not have a car. This is because an exclusive or is FALSE when both sides are true, and I already know that one side is true (I have a bike). The only way for the first premise to be true is when I do not also have a car.
Logical arguments with if/then (aka implies, →)
Statements with of the form, if p, then q are making a promise – that if p is true, then they promise that q will also be true. We will later see this structure using the logical implies operator.
If/then example 1
Suppose we have the following premises:
- If it is raining, then I will get wet.
- It is raining.
What can I conclude?
The first premises PROMISES that if it is raining, then I will get wet. Since we assume this premise is true, then we must keep the promise. Since the second premise tells us that it IS raining, then we can conclude:
I will get wet.
If/then example 2
Suppose we have the following premises:
- If I don’t hear my alarm, then I will be late for class.
- I am late for class.
Can we conclude anything new?
The first premise promises that if I don’t hear my alarm, then I will be late for class. And if we knew that I didn’t hear my alarm, then we would be able to conclude that I will be late for class (in order to keep the promise).
However, we do NOT know that I don’t hear my alarm. All we are told is that I am late for class. I might be late for class for many reasons – maybe I got stuck in traffic, or my car broke down, or I got caught up playing a video game. We don’t have enough information to conclude WHY I’m late for class, and in fact we can’t conclude anything new at at all.
If/then example 3
Suppose we have the following premises:
- If I don’t hear my alarm, then I will be late for class.
- I’m not late for class.
What can we conclude?
This is a trickier example. We saw previously that the first premise promised that anytime I didn’t hear my alarm, then I would be late for class. But we can interpret this another way – since I’m NOT late for class, then I must have heard my alarm. After all, if I DIDN’T hear my alarm, then I would have been late. But I’m not late, so the opposite must be true. So we can conclude that:
I hear my alarm.
Reframing an if/then statement like that is called writing its contrapositive. Any time we have a statement of the form if p, then q then we can write the equivalent statement if not q, then not p.
Knights and Knaves
We will now move to solving several kinds of logic puzzles. While these puzzles aren’t strictly necessary to understand the remaining course content, they require the same rigorous analysis that we will use when doing more formal truth tables and proofs. Plus, they’re fun!
The puzzles in this section and the rest of this chapter are all either from or inspired by: What is the Name of This Book?, by Raymond Smullyan.
Island of Knights and Knaves
This section will involve knights and knaves puzzles, where we meet different inhabitants of the mythical island of Knights and Knaves. Each inhabitant of this island is either a knight or a knave.
Knights ALWAYS tell the truth, and knaves ALWAYS lie.
Example 1
Can any inhabitant of the island of Knights and Knaves say, “I’m a knave”?
-→ Click for solution
No! A knight couldn’t make that statement, as knights always tell the truth. And a knave couldn’t make that statement either, since it would be true – and knaves always lie.
Example 2
You see two inhabitants of the island of Knights and Knaves – Ava and Bob.
- Ava says that Bob is a knave.
- Bob says, “Neither Ava nor I are knaves.”
What types are Ava and Bob?
-→ Click for solution
Suppose Ava is a knight. Then her statement must be true, so Bob must be a knave. In this case, Bob’s statement would be a lie (since he is a knave), which is what we want.
Let’s make sure there aren’t any other answers that work.
Suppose instead that Ava is a knave. Then her statement must be a lie, so Bob must be a knight. This would mean that Bob’s statement should be true, but it’s not – Ava is a knave.
We can conclude that Ava is a knight and Bob is a knave.
Example 3
If you see an “or” statement in a knights and knaves puzzle, assume that it means an inclusive or. This will match the or logical operator in our later truth tables and proofs, and will also match the or operator in programmimg.
You see two different inhabitants – Eve and Fred.
- Eve says, “I am a knave or Fred is a knight.”
What types are Eve and Fred?
-→ Click for solution
Suppose first that Eve is a knight. Then her statement must be true. Since she isn’t a knave, the only way for her statement to be true is if Fred is a knight.
Let’s make sure there aren’t any other answers that work.
Suppose instead that Eve is a knave. Already we are in trouble – Eve’s statement is already true no matter what type Fred is. Since Eve would lie if she was a knave, we know she must not be knave.
We can conclude that Eve and Fred are both knights.
Example 4
You see three new inhabitants – Sarah, Bill, and Mae.
- Sarah tells you that only a knave would say that Bill is a knave.
- Bill claims that it’s false that Mae is a knave.
- Mae tells you, “Bill would tell you that I am a knave.”
What types are Sarah, Bill, and Mae?
-→ Click for solution
Before starting on this puzzle, it might help to rephrase Sarah’s and Bill’s statements. Sarah’s statement that only a knave would say that Bill is knave is really saying that it is FALSE that Bill is a knave (since knaves lie). Another way to say it’s false that Bill is a knave is to say that Bill is a knight. Similarly, we can rewrite Bill’s statemnet to say that Mae is a knight.
Now we have the following statements:
- Sarah tells you that Bill is a knight.
- Bill claims that Mae is a knight.
- Mae tells you, “Bill would tell you that I am a knave.”
Suppose Sarah is a knight. Then her statement is true, so Bill must also be a knight. This would mean Bill’s statement would also be true, so Mae is a knight as well. But Mae says that Bill would say she’s a knave, and that’s not true – Bill would truthfully say that Mae is a knight.
Suppose instead that Sarah is a knave. Then her statement is false, so Bill must be a knave. This would make Bill’s claim false as well, so Mae must be a knave. Mae knows that Bill would say she was a knight (since Bill is a knave, and would lie), and if Mae was a knave then she would indeed lie and say that Bill would say she was a knave.
We can conclude that all three are knaves.
Other Puzzles
We will look at a variety of other logic puzzles, each of which involve some statements being false and some statements being true.
Lion and Unicorn
The setup for a Lion and Unicorn puzzle can vary, but the idea is that both Lion and Unicorn have specific days that they tell only lies, and other specific days that they only tell the truth.
Here is one example:
Lion always lies on Mondays, Tuesdays, and Wednesdays.
Lion always tells the truth on other days.
Unicorn always lies on Thursdays, Fridays, and Saturdays, and always tells the truth on other days.
On Sunday, everyone tells the truth.
Lion says: “Yesterday was one of my lying days."
Unicorn says: “Yesterday was one of my lying days, too.”
What day is it?
-→ Click for solution
To solve this puzzle, we consider what Lion’s and Unicorn’s statements would mean on each different day of the week.
Suppose it is Sunday. Then Lion’s statement would be a lie (Lion does not lie on Saturday), and yet Lion is supposed to be telling the truth on Sunday.
Suppose it is Monday. Then both Lion’s and Unicorn’s statements would be lies, since they both told the truth yesterday (Sunday).
Suppose it is either Tuesday or Wednesday. Then Lion’s statement would be true – but Lion is supposed to lie on both Tuesday and Wednesday.
Suppose it is Thursday. Then Lion’s statement would be true (Wednesday was one of their lying days), which is good since Lion is supposed to be telling the truth on Thursdays. Similarly, Unicorn’s statement would be false (Unicorn does not lie on Thursdays), which works out since Unicorn DOES lie on Thursdays.
Suppose it is either Friday or Saturday. Then Lion’s statement would be a lie (Lion doesn’t lie on either Thursday or Friday), but Lion should be telling the truth on Friday and Saturday.
We can conclude that it must be Thursday.
Tweedledee and Tweedledum
The Tweedledee and Tweedledum puzzles originate from Through the Looking-glass and What Alice Found There, by Lewis Carroll. There are different versions of these puzzles as well, but all of them involve the identical twin creatures, Tweedledee and Tweedledum. Like with Lion and Unicorn, there are different days on which Tweedledee and Tweedledum either only lie or only tell the truth (and often one creature is lying while the other is telling the truth).
Example 1
Consider this puzzle:
Tweedledee and Tweedledum are identical. You know that one of them lies Mon/Tues/Wed,and that the other lies Thurs/Fri/Sat. (They tell the truth on non-lying days.)
You don’t know which is which.
You see both of them together.
The first one says: “I’m Tweedledum."
The second one says: “I’m Tweedledee.”
Which is which? What day is it?
-→ Click for solution
Answer: Since the two creatures gave different answers, we can conclude that they must both be lying or both telling the truth. (Otherwise, both creatures would give you the same name.) Sunday is the only such day.
Each is telling the truth, so the first twin is Tweedledum and the second is Tweedledee.
Example 2
Consider a second puzzle, with the same setup as to which days each twin lies and tells the truth.
You know that either Tweedledum or Tweedledee has lost a rattle. You find it, and want to return it to the correct one. You don’t know what day it is, but are sure that it isn’t Sunday (so one must be lying and one must be telling the truth).
The first one says: “Tweedledee owns the rattle.”
The second one says: “I’m Tweedledee ¬”
Who gets the rattle?
-→ Click for solution
To solve this puzzle, we can explore the possibilities for each twin lying or telling the truth.
Suppose the first twin is telling the truth. Since it isn’t Sunday, we know the second twin must be lying. If the second twin’s statement is a lie, then the second is Tweedledum. Since the first twin is telling the truth, then they are Tweedledee (and the owner of the rattle).
Suppose instead that the first twin is lying. Again, since it isn’t Sunday, we know the second twin must be telling the truth. This would make the second twin Tweedledee, and the first twin Tweedledum. It would also mean that TweedleDUM owns the rattle (since the first statement is a lie), which is the first twin.
We don’t have enough information to determine which twin is which, but it doesn’t matter – in both cases, the first twin is the owner of the rattle.
Portia’s Caskets
This type of puzzle originates from The Merchant of Venice, by William Shakespeare. In the play, Portia’s father devised riddles to test potential suitors for his daughter.
Here is one such puzzle:
There are three caskets – one gold, one silver, and one lead. One of the caskets contains a portrait (of Portia). Each casket has a message on it, and you know that at most one of the messages is true.
Gold casket message: “The portrait is in this casket.” Silver casket message: “The portrait is not in this casket.” Lead casket message: “The portrait is not in the gold casket.”
Where is the portrait?
-→ Click for solution
To solve this puzzle, we recognize that there are only three possibilities – the portrait must be in either the gold casket, the silver casket, or the lead casket. We consider the implications of each:
Suppose the portrait is in the gold casket. Then the messages on both the gold and silver caskets would be true. This isn’t possible, as we know that at most one of the messages is true.
Suppose instead that the portait is in the silver casket. Then the messages on the gold and silver caskets would be false, and the message on the lead casket would be true. Only one message is true, so this is a possibility.
Finally, suppose the portrait is in the lead casket. Then the messages on all three caskets would be true, so this isn’t possible.
We conclude that the portrait must be in the silver casket.