Time to start, bold truth-seekers! Today we are going to solve some logical problems. For example, have a look at this classic riddle:
Three kids are accused of breaking a window. Their statements are either true or false. Only one is telling a lie.
- 🐶 said, ”😼 is telling a lie.”
- 😼 said, ”🐰 broke the window.”
- 🐰 yelled, “I didn’t!”
Who’s going to tell me, which one is telling a lie? (click each sentence to see the contradictions if it is a lie.)
I might have seen this puzzle before. Let’s assume if 🐰 is telling a lie, and what 🐶 said shows that 😼 is telling a lie. A contradiction!
Well, let’s move on: if 🐶 is telling a lie, then 😼 claims 🐰 broke the window while 🐰 denies, another contradiction! …
make a table or something
Hey, move aside! I have found a secret. The statements of 🐶 and 😼 always contradict with each other, so at most one of them is true!
The same is for 😼 and 🐰. As a result, there is a lier between 🐶 and 😼, as well as between 😼 and 🐰. As we know there is at most 1 lier among the three, 😼 is the lier!
… If 😼 is telling a lie, then 🐶 is right, and 🐰 didn’t broke the window.
I have just finish my enumeration, and I agree that’s correct.
| 🐶 | 😼 | 🐰 | result |
|---|---|---|---|
| ❌ | ✅ | ✅ | 🐰 contradicts 😼 |
| ✅ | ❌ | ✅ | ✅ |
| ✅ | ✅ | ❌ | 🐶 contradicts 😼 |
Of course, I’ve also noticed that not all possibilities are listed here! The words “only 1️⃣ is telling a lie” explicitly excluded some possibilities.
| 🐶 | 😼 | 🐰 | result |
|---|---|---|---|
| ❌ | ✅ | ✅ | 🐰 contradicts 😼 |
| ✅ | ❌ | ✅ | ✅ |
| ✅ | ✅ | ❌ | 🐶 contradicts 😼 |
| ❌ | ❌ | ✅ | contradicts 1️⃣, and (🐶 lies) contradicts (😼 lies) |
| ✅ | ❌ | ❌ | contradicts 1️⃣, and (🐰 lies) contradicts (😼 lies) |
| ❌ | ✅ | ❌ | contradicts 1️⃣ |
| ❌ | ❌ | ❌ | contradicts 1️⃣🐰 contradicts 😼 |
| ✅ | ✅ | ✅ | contradicts 1️⃣, 🐰 and 🐶 contradict 😼 |
\ \ Whoa, I found a empty note? I can even write something here! %^(^^^(&$@#!))
Good, you have found two different ways to solve the problem. They are so similar that we can abstract them with a general process [code]. Such solutions can also be applied to Einstein’s puzzle, and a lot of scheduling problems if somewhat extended.
make a better run button, add grammar highlighting
Here we are tackling the puzzle with a programming language, Prolog, which abstracts some interesting logical operations.
If you’re familiar with programming, feel free to skip the paragraphs to direct play with the code.
Prolog uses First_letter_capitalized_word as something unknown, and
first_letter_lowercase_word as an entity. For example, we tell it that
person(alice).
person(bob).
person(cesi)., or that alice, bob and cesi are persons; and ask it that
person(X)., or that if X is a person, what does X represent.
The predicates make anything inside have a property. In Prolog,
we have seen that person(alice) makes alice have a property person.
Predicates can establish a property, or relation, between more than one item, but
we are not going to use such a feature.
We are also going to express causal relation with :- (if) and
yes-or-no information with \+ (not). For example, we tell Prolog that
truth_teller(X) :- person(X), \+ lie(X).
liar(X) :- person(X), lie(X)., the definition of “truth” and “lie”, and
break_window(cesi) :- \+ lie(bob).
lie(bob) :- \+ lie(alice).
lie(cesi) :- break_window(cesi)., what the three kids said. Note that I make some interpretations here.
(TODO: the program seems not very accurate. When I plug in more conditions, it still gives an answer, which does not make things satisfy.)
Solve via Prolog!
However, we still need to look at them from a more formal perspective.
As you have discovered, we are now dealing with the statements, or sentences / propositions / formulas, which are interchangeably used here.
A statement can be defined as a declarative sentence, or part of a sentence, that is capable of having a truth-value, such as being true or false. (Quote from online resource)
For you who easily spot the contradiction, and derive everything from the prerequisites, we call this process (formal) reasoning.
highlight with color, emoji and even styles
The reasoning process is like inspecting a crime case, which involves classical steps. We have premises, some statements given as a starting point; we have syntax rules, with which a new statement is acquired from existing ones; and we have a target, or conclusion, the fact we desire.
In this syntax, we say something is derivable, or provable, given a set of conditions, that is, by reasoning, we can reach the conclusion, just like math proof questions in your middle school tests.
The related theory is proof theory.
This is where syntax comes in? So syntax is a way to rule out things by only focusing on the valid statements.
Exactly, and we usually call a statement consistent, if no contradiction can be reasoned from it. This is a way to rule out incorrect guesses. Contradiction in propositional logic is simply claiming some statement is both true and false.
However, just like a detective solving a case, there are occasions when reasoning fails. When faced with similar puzzles, we humans usually identify the reasoning rules, and try to deduce with them. If no more information can be deduced, we turn to the other method, enumerating possible solutions and seek truths.
For you who check all possible solutions, and filter out the unqualified, the work is tedious, yet effective. When we talk about enumerate, possibility, combination, we are using this method.
We consider this a semantic process, and the truths are said to be satisfying, or simply true, in our daily sense. Note the key difference between a true sentence and a provable sentence, although they usually comes together.
The related theory is model theory. So the thing is a bit tricker when involving a model of the world. For some logic, the thing that is directly linked to a logical object is not unique, and may involve multiple interpretations.
So a semantic concept is always linked to the world or the basic facts.
The puzzle has three statements, each of which is either true or false. Everything is a yes-or-no question, that is exactly how propositional logic views the world.
We’ll talk more about propositional logic later. In fact, our discussion is all about propositions if not otherwise mentioned.
Before we move on, let’s grab some syntactic and semantic concepts. We have see the syntactic concept derivability before. Now, who can give me a semantic version of derivability?
Easy. By enumerating every truth value combination like every line in the table I drew, a conclusion statement is always true if the known conditions are all true!
Wait, does that mean, I can say “2 + 2 = 5” is derivable and “semantically derivable”, given the condition “1 + 1 = 3”? Nothing makes the condition true, and they don’t need to make the conclusion true then.
Yep, despite that your sentence is an arithmetic statement and beyond our propositional logic. We’d better only consider the formulas whose truth value can be enumerated!
Your idea is mostly interesting in the syntactic situation, where it is sometimes stated as anything can be derived from a contradiction.
By the way, semantical derivability is referred to as validity here.
I get it. After that, here comes the semantical consistency!
As stated before, the semantical consistency, a.k.a satisfiability, of a group of statements are actually about finding a set of values in the world to make every statement satisfy.
explain more about what SAT means and its outset
Yes. The semantical consistency, actually satisfiability, usually comes in the form of whether a statement is satisfiable. In propositional logic, it is called Boolean Satisfiability Problem, or SAT for short. When we decided which one was lying in the puzzle, we solved a SAT problem!
A good solution to SAT, as well as its extended versions like SMT and MaxSAT, will enhance greatly the industry of hardware manufacturing and software package dependency solving. However, that is out of the scope of our class.
And finally, syntactic consistency! Like what satisfiability is to derivability, it’s also about finding a way to reason from some statement to some others!
Wait, that doesn’t make sense. Anything can be derived from a contradiction, and I remember that consistency means no contradiction can be deduced.
Can I make sure every statement derived is not a contradiction? That should suffice.
Sorry, there are usually infinite derivations from a propositional logic thing. That is, a set of statements are inconsistent if contradiction can be deduced. However, nothing tells you if they are consistent!
It’s indeed a weird thing. You can easily tell something is inconsistent, but can never make sure it is consistent.
But try to recall the last time when you factorize a large number!
We easily see that 1561596 has a factor 2, but it may cost a lot to see if
1594897 is itself a prime number.
That asymmetry is partly studied in a field called theory of computation, and I believe we are still very superficial in that aspect.
give more exercises
Exercise:
- tell me if pythagoras theorem is derivable or valid, in the case when someone deduces it from some geometrical magic.
- tell your friends about the difference between something true and
something provable, as concise as possible.
(Bonus: it is a key difference between our minds and a stricter system to think they are equal or not, see Löb’s Theorem, where by not admitting they are equal, the system find a way to turn down Curry’s paradox)
Summary of part 1
what you need to know after reading ...
- We talked about semantic (satisfiability, derivability) and syntactic (consistency, validity) concepts.
- The propositional logic only cares about some statements’ truth value.
there is better a link to the place where it first appears