Basic logical operators: conjunction, disjunction and negation
The photo above shows something incredible: a ship that appears to be floating in the sky. There is no deception: no photographic tricks were used, it is not generated by artificial intelligence or retouched, and it is not even an experimental aircraft… it is a very normal ship, and the photo actually shows what the observer was seeing in that moment.
How is it possible? We see a ship that flies, but we know that there are no ships that can fly. We are therefore seeing something that makes no sense, yet it is in front of us: something that contradicts the reality of the facts.
Can contradictions be a mathematical concept? We’ll see it at the end of the article.
Formalizing mathematical statements
The mathematical language is capable of expressing complex concepts with few symbols. Take for example this statement, which says that 7 is between 3, excluding, and 10, inclusive:
3 \lt 7 \le 10We could also express the statement in different terms: 7 is greater than 3 and is less than or equal to 10. Seen this way, we can see it as the combination of three statements: 7 \gt 3, 7 \lt 10, 7 = 10, joined by what in grammar are called conjunctions.
In logic, the equivalent of conjunctions are the logical operators, expressed by special symbols, which allow us to combine simple, or atomic, statements to compose more complex ones. Using logical operators it is possible to go beyond the possibilities offered by mathematical symbols alone: for example, without using logical operators, it would be impossible to translate into symbols the statement 31 is different from 3 and is greater than 20.
Conjunction
The conjunction operator, indicated by the symbol \land, is used to construct, starting from two sentences, a new sentence which is true when both are true, and false otherwise. For example, the previous statement can be expressed as the conjunction of the statements 31 \neq 3 and 31 \gt 20 like this:
(31 \neq 3) \land (31 \gt 20)31 \neq 3 \land 31 \gt 20
In this case the meaning of the statement is always the same: in practice, when parentheses are missing, we must remember that logical operators join mathematical statements, so the non-logical symbols must be read before the logical ones. For example, if in the previous statement we read the symbol \land first, we would obtain:
31 \neq (3 \land 31) \gt 20
which however is not a valid mathematical statement. Therefore the non-logical operators \neq and \gt must be read before the logical operator \land, as in the version with brackets.
Other times, however, the logical conjunction is represented by words other than “and”; for example the sentence my friends are few but good from a logical point of view means that my friends are few and good. In short, in logic, we do not pay attention to the nuances of meaning: there is only one way of affirming that two sentences are both true (i.e. by joining them with the symbol \land), even if in words it can be said in many different ways.
Disjunction
The disjunction operator is quite particular, because there are two types of it. Suppose we have this non-mathematical statement:
I will go on holiday to the seaside or to the mountains
It presents an ambiguity: is it accepted that I can do both? The question is more serious than it seems, because logic, which works like a calculation, does not allow ambiguities like this. For this reason, in logic there are two different symbols to indicate how we are interpreting the “or”:
- The inclusive disjunction, indicated with the symbol \lor, which is true when at least one of the starting sentences is true, and which therefore allows them to be both true;
- The exclusive disjunction, indicated with multiple symbols, some of which are \oplus, \not\equiv, \veebar, \mathbin{\dot{\lor}} (here and in the following we’ll use the latter); it is true when only one of the two starting sentences is true, and false otherwise, therefore it does not allow them to be both true.
Once, having clarified the context of the statement, we have established what we mean by that “or”, using logical symbolism we could rewrite it as:
- I will go on holiday to the seaside \lor I will go on holiday to the mountains, to indicate that I could do one of two things or even both;
- I will go on holiday to the seaside \mathbin{\dot{\lor}} I will go on holiday to the mountains, to indicate that I will choose only one destination.
Negation
The negation operator, which is indicated with the symbol \lnot, transforms a statement into its opposite, which is false if the starting statement is true, and viceversa. Starting for example from this statement, which is true:
(2 + 2 = 4) \land (4 \lt 10)its opposite, which is false, is:
\lnot ((2 + 2 = 4) \land (4 \lt 10))- \lnot (10 = 3) can be written as 10 \neq 3;
- 10 \gt 5 \land ((10 \lt 30) \lor (10 = 30)) can be written as 5 \lt 10 \leq 30;
- \lnot (20 \lt 6) can be written as 20 \ge 6.
and so on. For this reason, logical operators are rarely found in mathematics books, but it is good to remember that, behind the scenes, they are present.
The negation of 3 \lt 4 is:
3 \gt 4
3 \ge 4
3 = 4
How should this sentence be expressed in logical formalism: “25 can be written as 5 \cdot 5, alternatively as 5 ^ 2, and in this way it’s expressed as a power”?
(25 can be written as 5 \cdot 5, alternatively as 5 ^ 2) \land (in this way it’s expressed as a power)
(25 can be written as 5 \cdot 5) \lor (25 can be written as 5 ^ 2) \land (in this way 25 is expressed as a power)
(25 can be written as 5 \cdot 5) \lor ((25 can be written as 5 ^ 2) \land (in this way 25 is expressed as a power))
Some important properties
Double negation
As it happens in grammar, where the sentence you can’t fail to do it is the same as you can do it, logical operators follow the rule according to which two negations affirm. That is, given a generic statement P, we have:
\lnot (\lnot P) = PFor example:
\begin{aligned}\lnot (\lnot 10 \gt 20) &= \\ 10 \gt 20 \end{aligned}De Morgan’s laws
The British mathematician and logician Augustus De Morgan, based on a series of observations by previous scholars including the Greek Aristotle, formulated two important rules, known as De Morgan’s laws, which allow us to move from conjunctions to disjunctions and vice versa. Given two generic statements P and Q, we have:
\lnot (P \lor Q) = \lnot P \land \lnot Q \lnot (P \land Q) = \lnot P \lor \lnot QFor example:
- saying that The winner of the race is not one of the first two winners of last year is the same thing as saying The winner of the race is neither the first winner of last year, nor the second.
- saying that Carlo is not an engineer from Milan is the same thing as saying Carlo is not an engineer or is not from Milan.
Distributive property of conjunction and disjunction
We know that, in mathematics, the distributive property of multiplication with respect to addition holds, i.e. a \cdot (b + c) = a \cdot b + a \cdot c. In logic, inclusive conjunction and disjunction behave the same way. In fact, given three statements P, Q and R, we have:
P \land (Q \lor R) = (P \land Q) \lor (P \land R)which is precisely called the distributive property of conjunction with respect to inclusive disjunction.
For example, the sentence tomorrow I will put on a new dress and go to the cinema or to the theater is equivalent to tomorrow I will put on a new dress and go to the cinema, or I will put on a new dress and go to theatre.
The similarity with arithmetic expressions, however, stops here, because we know that in mathematics the distributive property of addition does not hold with respect to multiplication – for example 2 + (3 \cdot 4) \neq (2 + 3) \cdot (2 + 4) – while in logic the distributive property of the inclusive disjunction with respect to the conjunction holds, which is the same as before but with the logical symbols reversed:
P \lor (Q \land R) = (P \lor Q) \land (P \lor R)For example, the two following sentences are equivalent:
- The clues found by investigators as a whole suggest that the culprit could be the butler, or a tall woman.
- Some clues found by investigators suggest that the culprit could be either the butler or a woman; the other clues suggest that the culprit could be either the butler or a tall person.
In order to transform the statement:
\lnot(3 \lt 4 \lt 5)into the statement:
(3 \ge 4) \lor (4 \ge 5)what property has to be applied?
The distributive property
The negation
De Morgan’s laws
Tautologies and contradictions
Suppose we have any P statement. Starting from it, we can construct the following statement:
P \lor \lnot PA statement of this type has a peculiarity: it is always true, whatever the statement P is! Here are some examples:
- (10 = 3) \lor (10 \neq 3)
- (20 \gt 10) \lor (20 \leq 10)
- Tomorrow I will go to school or I won’t go
Statements with this characteristic are called tautologies, and, as you can imagine, they add nothing to the reasoning of which they are part.
The opposite case is given by contradictions, that are statements which are always false. Most often they are of the following type:
P \land \lnot PFor example:
- (10 = 3) \land (10 \neq 3)
- (20 \gt 10) \land (20 \leq 10)
- Tomorrow I will go to school and I won’t go
As the word itself says, a contradiction is composed of statements that contradict each other, that is, that are the opposite of each other. If in a logical reasoning we obtain a contradiction, it is an alarm bell, because it means that something is wrong in the statements we are manipulating, or in the premises which we started from, or in the intermediate steps; we will delve deeper into this aspect later.
The statement “To be or not to be” is:
A conjunction
A disjunction
A tautology
A contradiction
Other exercises
The ship that floats: what’s behind it?
The effect behind the photo is known as Fata Morgana , and it is due to the fact that the light, when it passes through layers of air at very different temperatures, is deflected: in the case of the photo, the ship is actually below the horizon, and therefore should not even be visible, while this phenomenon causes its image to appear raised, therefore the ship appears to float above the horizon. A contradictory situation like this originates from the difference between common knowledge, based on common sense, and what you see, which in this case is due to physics.
Logical contradictions are the mathematical equivalent of optical illusions like the one in the photo: when one is found, as we have seen, it is necessary to investigate what caused them. As we’ll see later, in some cases contradictions can even be used to our advantage…
Statement
A statement is a sentence with complete meaning, with objective content, of which it makes sense to ask whether it is true or false.For example: 2 is an even number is a statement, Maybe it will rain today is not.
Contradiction
A contradiction is a sentence in which we state something and its opposite at the same time.For example: Even numbers are odd.
