PG: Language inconsistency! Edit to clean up typos. I /really/ like the ideas here but the feedback has not been good.
BH: But change the "at least four" problem to make it clear that you're only allowed to ask one question.
MF: I want review this page and cut down on the switching back and forth among colored boxes.
"Zoey and I are from the same family." is a poor choice for motivating proof by contradiction because it doesn't require it. --MF, 9/1/19
Also, this lab overdoes decidability and solvability which has been simplified in the standards now (and is fully covered in 5.1.6 Heuristic Solutions. When we revise, we should distill down to the core of what we want to teach. --MF, 9/1/19
In this lab, you will learn that some problems can't be solved at all.
On this page, you will solve logic puzzles by finding a contradiction, that is, by showing that one possibility has to be true because the other possibility doesn't make sense.
Betsy, Gamal, and Alphie are considering the problem above.
Betsy: I'm pretty sure Zoey is a Truth-teller, but I don't know how to prove it.
A proof by contradiction is a two-step proof that a statement is false, which is done by
- assuming the statement is true
- based on that assumption, proving something known to be false (that is, showing the assumption creates a contradiction)
Gamal: Sometimes it's easier to prove that something is false than to prove that something is true. So let's assume the opposite of what you want to prove, and see where that leads us. Let's assume that Zoey is a False-teller.
Betsy: Okay. So if Diego is a Truth-teller, then what he said is true, and they are from the same family, the Truth-tellers. But we assumed that Zoey is a False-teller, so they're actually from different families, and so Diego can't be a Truth-teller.
Alphie: So, Diego has to be a False-teller.
Gamal: But that won't work either! If Diego is a False-teller, then what he said is false, and they are from different families. But they are both False-tellers, so they're actually in the same family, and so Diego can't be a False-teller either.
Betsy: No matter what family Diego is from, our assumption that Zoey is a False-teller led us to a contradiction. Zoey can't be a False-teller, so has to be a Truth-teller. We proved it.
Betsy and Gamal are exploring logical statements of their own.
Betsy: The statement I'm making right now is false.
Gamal: (Thinks for a moment) Wait! What?!?
Gamal: That's very clever, Betsy. Your statement can't be true, and it can't be false. So neither a Truth-teller nor a False-teller could say that.
There are four kinds of true/false statements:
An undecidable statement might be true or might be false; we don't know which.
A self-contradictory statement can be neither true nor false.
- Provably True: For example in this problem, "Zoey is a Truth-teller."
- Provably False: For example, "Zoey is a False-teller."
- Undecidable: For example, "Diego is a Truth-teller."
- Self-Contradictory: Such as "This statement is false."