Further Boolean logic

In this topic, we will cover more advanced concepts in Boolean logic – implication, proof by contradiction, equivalence, and operator XOR. These tools and concepts are used to express logical thoughts and dependencies using Boolean algebra and provide us with a way to correctly formulate and prove them. Knowledge of these concepts is essential for understanding and writing statements in Boolean logic.

Implication

Also known as a logical consequence, the implication is a logical operator. Like other Boolean operators, it forms a compound statement from two simpler statements. Here is how it works: for statements $A$ and $B$ it is denoted as $A \implies B$ and is read: "Statement $A$implies statement $B$" or simply: "From $A$ follows $B$". But what does "implication" actually mean? If statement $A$ is true, then statement $B$ must be true as well. Bear in mind that statement $B$ might be true, without $A$ being true. Take a look at the following example, which helps to understand and memorize how implication works.

Imagine that the statement $A$ says "It is raining at the moment", and the statement $B$ says "The road is wet". Now, let's elaborate: if it doesn't rain, the road is not wet, we can easily imagine such a situation. Therefore both statements $A$ and $B$ are false, but the implication as a whole makes sense, so the expression $A \implies B$ output is true. Now, could it be possible that it doesn't rain, but the road is wet nonetheless? Sure! let's say that someone spilled a bucket of water, so the road is wet, but it doesn't rain. Again, $A \implies B$ gives us 1. But how could it be possible that the rain pours outside, but the road stays perfectly dry? This is impossible, so for $A = 1$ and $B = 0$, the $A \implies B$ is equal to 0.

In short: if $A$ is true, then $B$ must be true as well, and if $A$ is false, $B$ can be anything. Hence the truth table of the implication operator:

Equivalence

The equivalence operator is formed by the conjunction of two implications: $(A \implies B) \land (B \implies A)$. You may directly read it as: "the expression $A$ implies $B$, and $B$ implies $A$", and it is denoted by an appropriate two-sided implication arrow: $A \iff B$. It may be understood as " one of the statements is true only if the other statement is true as well", and it has the following truth table:

More interestingly, if a statement $A$ is equivalent to a statement $B$, they share the same truth table. For example, the implication $A \implies B$ is actually equivalent to $\neg A \lor B$. Here you may compare their truth tables:

To sum it up, equivalence operator shows a mutual implication of the two statements. Saying "it is day now" is equivalent to saying "at the moment, it is not night", or "an integer x is even" is equivalent to "integer x is divisible by two".

Proof by contraposition

This proof is also called "indirect proof", is one of the main ways of proving a logical statement and is based upon the properties of implication and equivalence. First of all, we must note that the implication $A \implies B$ is actually equivalent to the implication $\neg B \implies \neg A$, you may check it for yourself using their respective truth tables.

But what do we need it for? Well, it so happens that sometimes instead of proving the direct implication it is much easier to do it by contraposition. You start by assuming that $B$ is false and try to prove that in this case, $A$ is false as well. Here is an example: for statement $A$: "$4^n-1$ is a prime number (i. e. it is only divisible by 1 and by itself), for some $n>0$" and $B$: "$n$ is an odd number", we must prove that $A \implies B$. We want to prove this statement via indirect proof, by showing that $\neg B \implies \neg A$. First, we assume that $n$ is not odd(i. e. is even), so it may be written as $n = 2k$. We incorporate our assumption into the negation of the statement $A$: "$4^{2k} -1$ is not a prime number". We rewrite it using the rule of difference of two squares: $4^{2k} -1 = (4^k-1) \cdot (4^k +1)$ which proves that if $n$ is even, then $4^n-1$ may be represented as a product of two numbers, so it cannot be prime.

Indirect proof is a crucial tool, used for proving logical statements. If a direct approach seems too hard or doesn't work, try proving it using contraposition.

Exclusive–OR operator (XOR)

Last, but not least, we will learn about the exclusive–or operator, more commonly known as just XOR. It fully lives up to its name and behaves exactly like a regular OR operator, except produces 0 if both inputs are positive. As reflected in the name of the operator, one input excludes the other. For inputs $A$ and $B$ it is denoted as: $A \bigoplus B$, and has the following truth table:

The use of XOR operator is usually pretty intuitive – you must choose one of two options, but not both. Here is an example: a statement $A$ states: "I will have a pizza for lunch", and a statement $B$: "I will have spaghetti for lunch". Even though the dishes are delicious, eating both would be too much for you. This condition forms a new logical statement: "I will have a pizza or spaghetti for lunch, but not both". We can easily rewrite this statement in Boolean algebra using the XOR operator: $A \bigoplus B$.

One last thing. The most perceptive of you may have noticed that the XOR operator produces true when the equivalence operator would produce false and the other way around. Their truth tables are reversed, and we can rewrite XOR as: $A \bigoplus B \iff \neg (A \iff B)$. You may play around and try to further rewrite XOR as a conjunction of implications or even logical OR operators.

Conclusion

In this topic, you have learned about more advanced operators and notions of Boolean logic, moreover, we introduced a new type of proof. Now let's highlight the most interesting parts of this topic:

• The implication is a logical operator which says "from $A$ follows $B$." It is depicted by an arrow as follows: $A\implies B$
• Equivalence is another operator which is "double implication", and so it can be represented as following: $(A \implies B) \land (B \implies A)$
• Proof by contraposition is tightly connected with implication and lets us instead of proving that $A\implies B$, prove that $\neg B\implies\neg A$
• The Exclusive-OR operator is almost the same as the regular OR, but one difference is that the former only allows one statement to be true and excludes the other one, hence the name