Актуализиране на кошницата
Вашата кошница е празна
Logic problems and statements
Necessary, sufficient, necessary and sufficient conditions
Generally, those problems or puzzles are called logic problems which include true or false statements, or where consequences have to be drawn from specific statements or facts. Here we present some typical examples of this type of problems, with methods for solving them.
The following couple of stories take place on Luth Island, where all inhabitants are either knights, who always tell the truth, or knaves, who always lie. Furthermore they pretty much reply sparingly, and for a stranger, they usually respond with either yes or no. They seldom answer to more than one question.
Example 1
On the first day, the traveller meets a man on Luth Island, who tells the following: “I am a knave”. What do we know about him?
Solution
If the individual were a knight, he would have to tell the truth; however, the statement “I am a knave” would be false for him, therefore he cannot be a knight.
If he were a knave, he would have to lie, however the statement “I am a knave” would be true for him, therefore he cannot be a knave either.
Consequently, our first acquaintance cannot be an inhabitant of Luth Island.
If he were a knave, he would have to lie, however the statement “I am a knave” would be true for him, therefore he cannot be a knave either.
Consequently, our first acquaintance cannot be an inhabitant of Luth Island.
Example 2
Next day the traveller happens to meet two inhabitants: a tall and a short one. In English, he asks the taller one: “Are you a knight?”, but the tall inhabitant merely mutters something that the traveller cannot understand. At this moment, the short man says: “He says that he is a knight. But he keeps on lying all the time.” Who is a knight and who is a knave?
Solution
All inhabitants claim that he is a knight, therefore we can take for sure that the short man's statement is true. In conclusion, he is a knight, and he says that the tall man is a knave.
Note: After listening to the traveller's explanation, his companion says: “The situation is different if the tall man did not respond to the question, or if he did not understand this because he does not speak English. In this case, the short man is the knave and since he lies when he tells that the tall man is a knave, then the tall man is a knight.” For this reason, we assume in all subsequent problems that the responder understands the question and it is the question that they respond to.
Example 3
In a village of Luth Island, inhabitants use the words plink and plank, instead of yes or no, but we do not know which means what. The traveller can ask one question from a villager, who will respond to it with either plink or plank. What should the traveller ask to find out which word means yes?
Solution
For the question “Are you a knight?” everyone will respond with yes, so whichever word the villager says in response, it means yes.
Example 4
The traveller comes across two inhabitants in Luth Island. The taller of them tells the traveller: “At least one of us is a knave.” Does the traveller know now what they are?
Solution
If the taller inhabitant is a knight, his statement “at least one of us is a knave” is true, and the knave must be the shorter man.
If the taller one is a knave, then one of them is a knave, thereby his statement would be true. Therefore he cannot be a knave. So the taller inhabitant is a knight, the shorter one is a knave.
If the taller one is a knave, then one of them is a knave, thereby his statement would be true. Therefore he cannot be a knave. So the taller inhabitant is a knight, the shorter one is a knave.
Example 5
On Luth Island, the traveller meets a pair of twins. The traveller knows that one of the twins is called John and the other one has a different name, and one of them is knight and the other is a knave, but does not know who is which. What should the traveller ask, if
- he can ask one of them one question consisting of up to five words, in order to find out who is John;
- he can ask one of them one question consisting of up to five words, in order to find out whether John is a knight or not?
Solution
It is rather obvious to ask one of them the question: “Are you John?” Take a look at the possible answers depending on whether John is a knight or a knave, and if he is the one questioned or his sibling. The results can be tabulated as follows:
John is askedHis sibling is askedJohn is a knightyesyesJohn is a knavenonoFor the question “Are you John?” John responds with yes if he is a knight, and with no if he is a knave. If his sibling is questioned, and John is a knight, then his sibling must be a knave, and since he lies, he will respond with yes. If John is a knave, then his sibling is a knight, who will respond with no to the question, for this being the truth.
You can see from the table that if the answer to the question “Are you John?” is yes, then John is a knight, and if the answer is no, then John is a knave, no matter who was given the question.
You can see from the table that if the answer to the question “Are you John?” is yes, then John is a knight, and if the answer is no, then John is a knave, no matter who was given the question.
As we know that John is either a knight or a knave, in order to find out which of them is John, we have to take one question which leads us to find out if our talking partner is a knight or a knave. This can be done by asking something which can be decided obviously, like: “Do you wear glasses?” If the response is yes, we talk with a knight, if the response is no, then our partner is a knave.
Interestingly, if we do not know which of them is the knight, we can find out John's identity with only one question. Give a try to the question “Does John tell the truth?”. Let us prepare another table with the possible answers:
Interestingly, if we do not know which of them is the knight, we can find out John's identity with only one question. Give a try to the question “Does John tell the truth?”. Let us prepare another table with the possible answers:
John is askedHis sibling is askedJohn is a knightJohn is a knaveyesnoyesnoIf we ask John and he is the knight, the response will be yes, and if he is the knave, then he will lie that “Yes, he tells the truth”. If his brother is questioned and John is the knight, then his brother is the knave, who will deny that John tells the truth, so the response will be no. If John is the knave, then his brother is the knight, who tells the truth when he claims that John is a liar, and as such, he will respond with no.
You can see from the table that if the answer to the question “Does John tell the truth?” is yes, then we asked John, and if the answer is no, then it was his brother, so now we know who is John.
You can see from the table that if the answer to the question “Does John tell the truth?” is yes, then we asked John, and if the answer is no, then it was his brother, so now we know who is John.
⯁ ⯁ ⯁
Arranging possibilities into tables is a useful method for other problems as well:
Example 6
Three friends meet at the café: Mr White is a sculptor, Mr Black is a musician and Mr Brown is an actor. “How interesting! The colours of our hair are white, black or brown, but no one has the same colour hair as his name is”, tells the man with black hair. “You are right” tells the sculptor. What colour is the actor’s hair?
Solution
First of all, put “\latex{ – }” marks to the table, indicating that no one has the same name than his hair colour.
hair\namewhiteblackbrownMr White, sculptor\latex{ - }Mr Black, musician\latex{ - }Mr Brown, actor\latex{ - }Since the sculptor responded to the man with black hair, the sculptor cannot have black hair, and his name being Mr White, his hair colour cannot be white either, consequently, he can only have brown hair.
hair\namewhiteblackbrownMr White, sculptor\latex{ - }\latex{ - }\latex{ + }Mr Black, musician\latex{ - }Mr Brown, actor\latex{ - }
Considering the above, Mr Black cannot have brown hair, neither can he have black hair, so his hair must be white.
hair\namewhiteblackbrownMr White, sculptor\latex{ - }\latex{ - }\latex{ + }Mr Black, musician\latex{ + }\latex{ - }\latex{ - }\latex{ - }Mr Brown, actorThis leaves Mr Brown, the actor to be the one with black hair.
hair\namewhiteblackbrownMr White, sculptorMr Black,musicianMr Brown, actor\latex{ - }\latex{ - }\latex{ - }\latex{ - }\latex{ - }\latex{ - }\latex{ + }\latex{ + }\latex{ + }To sum up, Mr White has brown hair, Mr Black has white hair and Mr Brown has black hair.
⯁ ⯁ ⯁
In the above problems, it was essential to decide whether certain statements are true or false.
DEFINITION: In a logical sense, statement is understood as a declarative sentence which can be unequivocally decided to be true or false.
Therefore a statement can only be of two types: either true or false, and it cannot be both at the same time.
For example, the sentence “when they asked about my favourite school subject, I said it was maths” is a statement, however the claim “mathematics is the most delicate science” is not a statement, since the meaning of “the most delicate” is very vague.
Generally, statements are symbolised with letters, like \latex{ A }, \latex{ B }, \latex{ C }, … or \latex{ p }, \latex{ q }, \latex{ r }, …
For example, the sentence “when they asked about my favourite school subject, I said it was maths” is a statement, however the claim “mathematics is the most delicate science” is not a statement, since the meaning of “the most delicate” is very vague.
Generally, statements are symbolised with letters, like \latex{ A }, \latex{ B }, \latex{ C }, … or \latex{ p }, \latex{ q }, \latex{ r }, …
statementtruefalse
True and false are the logical values of a statement.
If the statement \latex{ A } is true and \latex{ B } is false, we can also say that the logical value of \latex{ A } is true, and the logical value of \latex{ B } is false.
The same with symbols: \latex{|A|=t} and \latex{|B|=f.}
Unless it leads to a misunderstanding, this can be written without the vertical lines, like: \latex{A=t, B=f.}
If the statement \latex{ A } is true and \latex{ B } is false, we can also say that the logical value of \latex{ A } is true, and the logical value of \latex{ B } is false.
The same with symbols: \latex{|A|=t} and \latex{|B|=f.}
Unless it leads to a misunderstanding, this can be written without the vertical lines, like: \latex{A=t, B=f.}
Examine this sentence: “This sentence is false.” If this statement was true, it would mean that the statement is false. In the other hand, if the statement was false, it would mean exactly that the negation of the sentence is true, so the statement is true. Either way, we end up in a contradiction, which we call a paradox. These sentences cannot be considered as statements either, they do not carry any information, they are not “established”.
Exercises
{{exercise_number}}. The traveller visiting Luth Island comes across three inhabitants, and asks them: “How many of you are knights?” The tallest one mutters something which cannot be understood. The traveller asks the second one: “What did your buddy say?” “He said that there is one knight among us”, the second inhabitant replies. “Do not believe him! He’s lying”, intervenes the third inhabitant. Based on these information, which inhabitant can be identified as either a knight or a knave?
{{exercise_number}}. Omar, an inhabitant of Luth Island had been accused with stealing an elephant. When facing the court, Omar said only one sentence which proved that he was not guilty. What could he have said?
{{exercise_number}}. In a village of Luth Island, where knights and knaves reside, inhabitants use the words plink and plank, instead of yes or no, but we do not know which means what. What can we find out from the answer given to this question: “If you are asked ‘Are you a knight?’do you answer plink?”
{{exercise_number}}. Four girls visit their friend on her birthday. Their family names are: Smith, Taylor, Jones and Williams. Their given names are, not necessarily in this order, Mary, Sarah, Kathy and Esther. Miss Williams was the first to arrive, and Sarah followed her. Then came Miss Smith and the last one was Mary. All of them brought a gift: a pen from Miss Williams, chocolate from Kathy, a photo album from Mary and a book from Miss Jones. What are the complete names of the girls?
{{exercise_number}}. Brian, Stevie and Valentine are classmates. One of them goes to school by bike, the other one by bus and the third one by tram. One of them plays basketball, the other plays handball and the third one is a swimmer. Stevie and Valentine do not play basketball, Stevie does not go to school by bike, the swimmer does not go to school by tram and the one who rides the bike on the way to school plays handball. Who uses which meens of transport to get to the school, and who does which sport?
Puzzle
The following puzzle had been proposed by Albert Einstein. According to him, \latex{ 98 }% of the people cannot solve it. Do you belong to the \latex{ 2 }%?
Facts:
Facts:
- There are \latex{ 5 } houses next to each other, all of a different colour.
- One person lives in each house, and they all have different nationalities.
- Each person has a favourite drink and tobacco, and has a pet animal.
- Each of them drinks a different kind of beverage, smokes a different kind of tobacco and keeps a different pet.
Further information:
- The man from Britain lives in a red house.
- The Swede keeps dogs as pets.
- The man who keeps horses lives next to the man who smokes Dunhill.
- The green house is on the left of the while, next to it.
- The Dane drinks tea.
- The person who smokes Pall Mall rears birds.
- The man who smokes Blend lives next to the one who keeps cats.
- The man living in the house in the middle drinks milk.
- The green house’s owner drinks coffee.
- The Norwegian lives next to the blue house.
- The owner of the yellow house smokes Dunhill.
- The owner who smokes Blue Master drinks beer.
- The Norwegian lives in the first house.
- The German smokes Prince.
- The man who smokes Blend has a neighbour who drinks water.
The question is: Who keeps fish?