Your cart is empty
Logical operators: negation,
conjunction, disjunction
conjunction, disjunction
There are different ways to connect statements with each other, thus creating composite statements. Generally, composite statements have a mutual structure which can be described by the logical operators referring to the statements.
Example 1
On Luth Island, the traveller met three inhabitants. The tallest inhabitant told him “All of us are knaves.” One of his companions replied, “Exactly one of us is a knight.” What are the inhabitants?
Solution
If the tallest inhabitant was a knight, he would have to tell the truth and this way he could not tell that all of them are knaves.
Consequently the tallest person is a knave and it is sure that he lies, therefore his statement “All of us are knaves” is false. This means that the statement “not all of us are knaves” is true. Therefore there cannot be \latex{ 3 } knaves; the number of knaves has to be either \latex{ 0 },\latex{ 1 } or \latex{ 2 }.
Consequently the tallest person is a knave and it is sure that he lies, therefore his statement “All of us are knaves” is false. This means that the statement “not all of us are knaves” is true. Therefore there cannot be \latex{ 3 } knaves; the number of knaves has to be either \latex{ 0 },\latex{ 1 } or \latex{ 2 }.
It cannot be 0 because we already know that the tallest inhabitant is a knave.
If the tallest inhabitant was the only knave, there would be two knights, and one of them would say “Exactly one of us is a knight”, which is impossible, since this statement would be false in such situation.
Therefore, there are \latex{ 2 } knaves and \latex{ 1 } knight. In this situation, the statement “Exactly one of us is a knight” is true, and it is told by the knight, and the other two people are knaves.
Therefore, there are \latex{ 2 } knaves and \latex{ 1 } knight. In this situation, the statement “Exactly one of us is a knight” is true, and it is told by the knight, and the other two people are knaves.
DEFINITION: Negation, or logical complement, of a statement \latex{ A } is the statement which is true if \latex{ A } is false, and is false if \latex{ A } is true.
The negation of \latex{ A } is written as \latex{\neg A}, pronounced as “not \latex{ A }”.
If \latex{ A } is true, then not \latex{ A } is false and if \latex{ A } is false, then not \latex{ A } is true.
The negation of \latex{ A } is written as \latex{\neg A}, pronounced as “not \latex{ A }”.
If \latex{ A } is true, then not \latex{ A } is false and if \latex{ A } is false, then not \latex{ A } is true.
E.g. the statement “\latex{ 3 } is a divisor of \latex{ 2004 }” is true, the statement “\latex{ 3 } is not a divisor of \latex{ 2004 }” is false. The statement “ \latex{\sqrt{2}} is a rational number” is false, the statement “ \latex{\sqrt{2}} is not a rational number” is true. The negation of the statement “All people are mathematicians” is “There exists a person who is not a mathematician”. The negation of the statement “There exists a dog which says meow” is: “It is true for all dogs that they do not say meow”, or “There is no dog which says meow”.
\latex{A}\latex{\neg A}\latex{ t }\latex{ t }\latex{ f }\latex{ f }Example 2
While wandering on Luth Island, the traveller arrived at a fork in the road near a village. One way leads to the desert, the other one leads to the next oasis. All villagers know where the roads lead, but they are willing only to respond for one question of the traveller, furthermore, they will only answer yes or no. What should the traveller ask in order to find the right way?
Solution
The traveller points at one road and asks an inhabitant: “What do you say when somebody asks whether this road leads to the oasis?”
If the questioned islander is a knight, than he would tell the truth. He also tells the truth now, so if the road leads to the oasis he answers yes, and if it leads to the desert, he answers no.
If the questioned islander is a knave, he would tell no for the road leading to the oasis, however he lies this time as well, so he will say yes. Also, if the road leads to the desert, he would answer yes, but as he lies this time as well, he will say no to the traveller’s question.
If the questioned islander is a knight, than he would tell the truth. He also tells the truth now, so if the road leads to the oasis he answers yes, and if it leads to the desert, he answers no.
If the questioned islander is a knave, he would tell no for the road leading to the oasis, however he lies this time as well, so he will say yes. Also, if the road leads to the desert, he would answer yes, but as he lies this time as well, he will say no to the traveller’s question.
Therefore no matter whom the traveller asks this question, the response will be true.
Similarly, we can easily see that this question is suitable: “If I asked you now if this road leads to the oasis, would you say yes?”
The solution lies in the fact that any villager will either tell the truth or deny his lie, or, in other words, denies the truth twice, which results in him telling exactly the same as a truthsayer. This is satisfied for any statement, as it is stated by the following theorem:
In a village, the barber is a man from the village
who shaves all men in town who do not shave themselves. Who shaves the barber of the village?
who shaves all men in town who do not shave themselves. Who shaves the barber of the village?
THEOREM: Negation of the negation of a statement is the original statement (double negative elimination rule):
\latex{\neg (\neg A)\equiv A.}
Example 3
An inhabitant of Luth Island tells the following: “I am a knave but my brother is not.” What are they?
Solution
In other words, the inhabitant could have told his statement like “I am a knave and my brother is a knight.”
If the speaker is a knight, the statement is true, which means that it is true that he is a knave and his brother is a knight. However if the speaker is a knight, it cannot be true that he is a knave, so the speaker cannot be a knight.
If the speaker is a knave, his statement is false.
This can happen in three ways:
If the speaker is a knight, the statement is true, which means that it is true that he is a knave and his brother is a knight. However if the speaker is a knight, it cannot be true that he is a knave, so the speaker cannot be a knight.
If the speaker is a knave, his statement is false.
This can happen in three ways:
- it is true that he is a knave but it is false that his brother is a knight;
- it is false that he is a knave but it is true that his brother is a knight;
- it is false that he is a knave but it is false that his brother is a knight.
Since the speaker is a knave, only the first option can be real which means that both the speaker and his brother is a knave.
DEFINITION: The conjunction of two statements is true precisely when both statements are true, otherwise it is false. The conjunction of \latex{ A } and \latex{ B } is written as \latex{A\wedge B} , pronounced as “\latex{ A } and \latex{ B }”.
For example the statement “it is raining and the sun is shining” is true only if it is raining and at the same time the sun is shining. However it is false if it is raining but the sun does not shine; or if there is no rain and the sun is shining; or when there is neither rain nor sunshine.
In the solution of Problem \latex{ 3 }, we can observe how the following was used: the speaker cannot be a knight and a knave at the same time, thus a statement cannot be both true and false. This is established for any statement in the following theorem:
In the solution of Problem \latex{ 3 }, we can observe how the following was used: the speaker cannot be a knight and a knave at the same time, thus a statement cannot be both true and false. This is established for any statement in the following theorem:
\latex{A}\latex{B}\latex{A\wedge B}\latex{ t }\latex{ t }\latex{ t }\latex{ t }\latex{ t }\latex{ f }\latex{ f }\latex{ f }\latex{ f }\latex{ f }\latex{ f }\latex{ f }THEOREM: A and \latex{\neg A} cannot be true at the same time (law of non-contradiction).
\latex{A\wedge \neg A=f.}
Properties of the conjunction operator for any \latex{ A }, \latex{ B }, \latex{ C } statements are:
- commutativity (order of the operands can be changed): \latex{A\wedge B=B\wedge A;}
- associativity (operands can be grouped): \latex{A\wedge (B\wedge C)\equiv (A\wedge B)\wedge C,} (in other words, \latex{A\wedge B\wedge C} is true if and only if all three statements are true);
- \latex{A\wedge A\equiv ;A\wedge t\equiv A;A\wedge f\equiv f.}
Example 4
An inhabitant of Luth Island tells: “I am a knave, or there is treasure hidden under this tree.” Is it worth starting seeking for the treasure under the tree?
Solution
If the speaker is a knight, his statement is true. This leaves us with three outcomes:
- the speaker is a knave and there is treasure under the tree;
- the speaker is a knave and there is no treasure under the tree;
- the speaker is not a knave, but there is treasure under the tree.
As we assumed that the speaker is a knight, and as such, cannot be a knave, only the third outcome can happen, which means that there is treasure under the tree.
If the speaker is a knave, then his statement must be false. This can only happen when he is not a knave and there is no treasure under the tree. This contradicts the fact that he is a knave.
Thus there is treasure under the tree, and the speaker can only be a knight.
DEFINITION: The disjunction of two statements is false precisely when both statements are false, otherwise it is true. The disjunction of \latex{ A } and \latex{ B } is written as \latex{A\vee B,} pronounced as “\latex{ A } or \latex{ B }”.
For example, the statement “I drink tea or eat pie” is true if I drink tea and eat pie, or if I only drink tea and do not eat pie, or even if I do not drink tea but instead I eat pie. However, it is false when neither I do drink tea nor eat pie.
In the solution of Problem \latex{ 4 }, we can observe that if an inhabitant is not a knight, then he must be a knave for sure; there is no third possibility. This is satisfied by any statement: a statement can be either true or false, there is no third outcome in the logic detailed herein. This fact is established in the following theorem:
In the solution of Problem \latex{ 4 }, we can observe that if an inhabitant is not a knight, then he must be a knave for sure; there is no third possibility. This is satisfied by any statement: a statement can be either true or false, there is no third outcome in the logic detailed herein. This fact is established in the following theorem:
\latex{A}\latex{B}\latex{ t }\latex{ t }\latex{ t }\latex{ t }\latex{ t }\latex{ t }\latex{ t }\latex{ f }\latex{ f }\latex{ f }\latex{ f }\latex{ f }\latex{A \wedge B}THEOREM: \latex{ A } and \latex{\neg A} cannot be false at the same time (law of the excluded middle).
\latex{A\vee \neg A\equiv t.}
Properties of the disjunction operator for any statements \latex{ A }, \latex{ B }, \latex{ C } are:
- commutativity (order of the operands can be changed): \latex{A\vee B=B\vee A;}
- associativity (operands can be grouped): \latex{A\vee (B\vee C)\equiv (A\vee B)\vee C,} (in other words \latex{A\vee B\vee C} is false if and only if all three statements are false);
- \latex{A\vee A\equiv A;A\vee t=t;A\vee f=A.}
Example 5
Using the above logical operators, describe the following statements if
S = this year’s football champions are Shortlegs FC,
T = this year’s football champions are Timbertoes FC:
S = this year’s football champions are Shortlegs FC,
T = this year’s football champions are Timbertoes FC:
- It is not true that Shortlegs FC or Timbertoes FC has won.
- Neither Shortlegs FC nor Timbertoes FC has won.
- The teams of Shortlegs FC and Timbertoes FC did not share the first place with each other.
- One team out of Shortlegs FC and Timbertoes FC did not win.
Solution (a)
It is not true that either Shortlegs FC or Timbertoes FC has won \latex{ = } not
true that (Shortlegs FC has won or Timbertoes FC has won) \latex{ = } \latex{\neg (T\vee S).}
true that (Shortlegs FC has won or Timbertoes FC has won) \latex{ = } \latex{\neg (T\vee S).}
Solution (b)
Neither Shortlegs FC nor Timbertoes FC has won \latex{ = } Shortlegs FC has not won and Timbertoes FC has not won either \latex{ = } \latex{\neg T\wedge \neg S.}
The statement “neither Shortlegs FC nor Timbertoes FC has won” tells the same as “it is not true that at least one of the teams has won” does, thus it is not true that the winner was Shortlegs FC or Timbertoes FC are champions. As such, the two statements in the first two points tell the same, thus \latex{\neg (T\vee S)=\neg T\wedge \neg S.}
The statement “neither Shortlegs FC nor Timbertoes FC has won” tells the same as “it is not true that at least one of the teams has won” does, thus it is not true that the winner was Shortlegs FC or Timbertoes FC are champions. As such, the two statements in the first two points tell the same, thus \latex{\neg (T\vee S)=\neg T\wedge \neg S.}
Solution (c)
The teams of Shortlegs FC and Timbertoes FC did not share the first place with each other \latex{ = } it is not true that Shortlegs FC has won and Timbertoes FC has also won \latex{ = } \latex{\neg (T\vee S).}
Solution (d)
One team out of Shortlegs FC and Timbertoes FC did not win \latex{ = } Shortlegs FC has not won, or Timbertoes FC has not won = \latex{\neg T\vee \neg S.}
The statement “one out of Shortlegs FC and Timbertoes FC did not win” says that both teams could not have won at the same time, which means that Shortlegs FC and Timbertoes FC has not won the championship in a dead heat. As such, the two statements in the last two points say the same, thus \latex{\neg (T\wedge S)\equiv \neg T\vee \neg S.}
These equivalences are satisfied by any statements, regardless of the content of the statements. This fact is stated in the following theorem:
The statement “one out of Shortlegs FC and Timbertoes FC did not win” says that both teams could not have won at the same time, which means that Shortlegs FC and Timbertoes FC has not won the championship in a dead heat. As such, the two statements in the last two points say the same, thus \latex{\neg (T\wedge S)\equiv \neg T\vee \neg S.}
These equivalences are satisfied by any statements, regardless of the content of the statements. This fact is stated in the following theorem:
THEOREM: For any statements \latex{ A } and \latex{ B } logical value of “it is not true that \latex{ A } and \latex{ B }” equals that of “not \latex{ A } or not \latex{ B }”. Furthermore, logical value of the statement “it is not true that \latex{ A } or \latex{ B }” equals that of „not \latex{ A } and not \latex{ B }” (De Morgan’s laws).
\latex{\neg (A\wedge B)\equiv \neg A\vee \neg B,}
\latex{\neg (A\wedge B)\equiv \neg A\wedge \neg B.}
\latex{\neg (A\wedge B)\equiv \neg A\wedge \neg B.}
Example 6
Andy says “I go to the cinema, and swim or ride a bike.” While Billy says “I go to the cinema and swim, or ride a bike.” Do they say the same?
Solution
Andy tells the truth if and only if he goes to the cinema and besides this, he does at least one out of swimming and riding a bike. He could have said it otherwise, like “I go to the cinema and swim, or I go to the cinema and ride a bike.”
Billy’s statement can be true either if he goes to the cinema and swims, or just rides a bike, or he does all of them.
The statement made by Andy is not satisfied if he only goes cycling, therefore the statements made by the two boys are not the same.
Billy’s statement can be true either if he goes to the cinema and swims, or just rides a bike, or he does all of them.
The statement made by Andy is not satisfied if he only goes cycling, therefore the statements made by the two boys are not the same.
\latex{\blacklozenge} \latex{\blacklozenge} \latex{\blacklozenge}
We can have a more clear understanding on the precise meaning of complex statements if we express them using logical operators. Let us use letters for the statements: \latex{ C = I } go to cinema, \latex{ S = I } swim, \latex{ B = I } ride a bike. By using these, the statement of Andy is: \latex{C\wedge (S\vee B).} Billy’s statement is: \latex{(C\wedge S)\vee B.}
We can see that the difference between the two statements is in the brackets, which means that in case we modify the placement of brackets in such complex statements, it might result in a different meaning. In the text, we tried to use commas to indicate where the brackets are.
We can see that the difference between the two statements is in the brackets, which means that in case we modify the placement of brackets in such complex statements, it might result in a different meaning. In the text, we tried to use commas to indicate where the brackets are.
Andy’s statement in another way is: \latex{(C\wedge S)\vee (C\wedge B).} From this, we can conjecture that the following equivalence is true:
\latex{C\wedge (S\vee B)\equiv (C\wedge S)\vee (C\wedge B).}
In general:
THEOREM: Conjunction is distributive, over disjunction. In other words, for any statements \latex{ A }, \latex{ B }, and \latex{ C }:
\latex{A\wedge (B\vee C)\equiv (A\wedge B)\vee (A\wedge C).}
Disjunction is distributive over conjunction, that is,
for any statements \latex{ A }, \latex{ B }, and \latex{ C }:
\latex{A\vee (B\wedge C)\equiv (A\vee B)\vee (A\vee C).}
We made use of the fact that the result of logical operators depends only on the logical value of the operands.
No matter what statements are in the place of \latex{ A } and \latex{ B }, \latex{\neg (A\wedge B)\equiv \neg A\vee \neg B} will be satisfied regardless of the content of the statements \latex{ A } and \latex{ B. }
The equality \latex{\neg (A\wedge B)\equiv \neg A\vee \neg B} stands true for all possible logical values of \latex{ A } and \latex{ B } therefore it is an equivalence.
The equality \latex{\neg (A\wedge B)\equiv \neg A\vee \neg B} stands true for all possible logical values of \latex{ A } and \latex{ B } therefore it is an equivalence.
Exercises
{{exercise_number}}. There are \latex{ 2 } white, \latex{ 2 } red, \latex{ 2 } blue, \latex{ 2 } green and \latex{ 2 } yellow balls distributed between a white, a red, a blue, a green and a yellow bin in such a way that there are two balls in each bin. Using the following statements, find out where is each ball.
- None of the balls are in the same coloured bin.
- There is a green and a blue ball in the yellow bin.
- There is a yellow ball in the blue bin.
- There is no blue ball in the red bin.
- A red and a green ball are together in either the white or the yellow bin.
- There is only one bin in which there are one white and one yellow ball together.
{{exercise_number}}. Formulate the negation of the following statements.
- Every angle of the square is right angle.
- Every triangle is right angled.
- None of the angles of the regular pentagon are right angles.
- There exists a deltoid which is a rhombus.
- There exists a trapezoid which is not a parallelogram.
- There exists an obtuse triangle.
- Every triangle has a circumscribed circle.
- \latex{ 3 } is smaller than \latex{\Pi}
- \latex{ 4 } is greater than or equal to \latex{ 5 }.
- The largest number possibly rolled by a regular die is \latex{ 6 }.
- \latex{ 9 } has at least \latex{ 3 } divisors.
- There exists a quadratic equation which has at least \latex{ 3 } solutions.
{{exercise_number}}. Formulate the statements whose negation is the following:
- There exists a village without a post office.
- Everyone is blue-eyed.
- Every spider has at most \latex{ 8 } eyes.
- There exists a year when February has \latex{ 30 } days.
- There is a telephone in every hotel’s every room.
- There exists a workplace where there is a person who works.
{{exercise_number}}. In one village of Luth Island the residents use the words plink and plank instead of yes and no, but we don’t know which word means what. Ask a question to a villager for which the response will be plink.
{{exercise_number}}. Nicky is either a truthsayer or a liar, and similarly Picky and Ticky are also either a truthsayer or a liar. A truthsayer always tells the truth while a liar always lies. Who is a truthsayer if they say the following?
- Nicky: “Picky is a liar.”
Picky: “Ticky is a liar.”
Ticky: “Nicky and Picky are liars.”
- Nicky: “We are all liars.”
Picky: “There is exactly one liar among us.”
{{exercise_number}}. If \latex{ M = } ‘today is Monday’ and \latex{ T = } ‘I am tired’, then construct the following statements using logical operators and construct their negation as well:
- Today is not Monday.
- Today is Monday and I am tired.
- Today is Monday but I am not tired.
- Today is not Monday yet I am tired.
- Today is not Monday and I am not tired.
{{exercise_number}}. If \latex{ T = } ‘today is Monday’ and \latex{ Y = } ‘yesterday was Sunday’, then construct the following statements using logical operators and construct their negation as well:
- Today is Monday or yesterday was Sunday.
- Today is not Monday or yesterday was not Sunday.
- Yesterday was not Sunday or today is Monday.
- Today is not Monday or yesterday was not Sunday.
On which days are the above statements true?
{{exercise_number}}. Form a sentence from the statements below using \latex{ P = } ‘I am going’, \latex{ Q = } ‘you are going’ and \latex{ R = } ‘Otto is going’.
- \latex{P\wedge (Q\vee R)}
- \latex{(Q\wedge P)\vee (R\wedge P)}
- \latex{\neg (P\wedge Q)}
- \latex{\neg Q\vee \neg P}
{{exercise_number}}. Let \latex{ A = } ‘Kathy is sad’, \latex{ B = } ‘Kathy is angry’, \latex{ C = } ‘Kathy is happy’. Construct the following statements using logical operators:
- Kathy is both sad and angry and definitely not happy.
- Kathy is either sad or angry, but not happy.
- Kathy is neither sad nor angry, but she is not happy yet.
- Kathy is either sad and angry, or happy.
{{exercise_number}}. There are five suspects of the murder of Cock Robin. During interrogation the following statements are being told:
- ‘\latex{ C } and \latex{ D } lie’
- ‘\latex{ A } and \latex{ E } lie’
- ‘\latex{ B } and \latex{ D } lie’
- ‘\latex{ C } and \latex{ E } lie’
- ‘\latex{ A } and \latex{ B } lie’
Who’s lying?
{{exercise_number}}. The length of the sides \latex{ AB }, \latex{ BC }, \latex{ CD } and \latex{ DA } of quadrilateral \latex{ ABCD } are \latex{ 1;\, 9;\, 8;\, 6; } respectively. Let
- Quadrilateral \latex{ ABCD } has a circumscribed circle.
- Quadrilateral \latex{ ABCD } does not have a circumscribed circle.
- Diagonals \latex{ AC } and \latex{ BD } are not perpendicular.
- The angle \latex{ ADC } is at least \latex{ 90° .}
- Triangle \latex{ BCD } is isosceles.
Form a sentence from the statements below and pick those which are true.
- \latex{p\wedge \neg q\wedge r}
- \latex{p\wedge \neg s\wedge t}
- \latex{r\wedge \neg s\wedge t}
- \latex{\neg q\wedge \neg r\wedge s}
Puzzle
An evil wizard captures \latex{ 100 } gnomes and then he makes them the following offer: They can form a single line such that every one of them can see everyone standing in the line before themselves but none of them can see anyone standing behind themselves. He then places either a black or white hat on each gnome and, starting from the end of the row, each gnome has to bet on the colour of their hat. Those who answer correctly will be freed, the rest will die. The gnomes can hear every answer, they are clever and they have some time to discuss a strategy. Suggest a way to free as many gnomes as possible.
