The name “boolean” comes from Geroge Boole, an English mathematician, philosopher and logician, who was the first to introduce the algebraic logical system in the 19th century.
To start with, let’s introduce the so called “truth tables” and with the variables “True” or “False”, often used in mathematics, in equations and inequalities, and for valid expression ranges. We are not going to go deeper into this issues we study on mathmatics and let’s go directly to their applicability in computer science. However, let’s just take a look in the most common operations – “AND”, “OR”, “eXclusive-OR” and “NOT” – using the letters T and F to represent True and False, respectively.
This means we can express these tables as:
- True AND True = True
- True AND False = False
- False AND True = False
- False AND False = False
- True OR True = True
- True OR False = True
- False OR True = True
- False OR False = False
- True “eXclusive OR” (XOR) True = False
- True XOR False = True
- False XOR True = True
- False XOR False = False
- NOT True = False
- NOT False = True
Let’s now take a computer science approach and represent False as 0 and True as 1. The truth tables will look like as follows:
On Maths, we can also use some of these operations on the set theory:
- AND – Intersection ( symbol ˄ )
- OR – Union ( symbol ˅ )
- NOT – Negation ( symbol ¬ )
We can also find an interesting equivalence in binary for the AND and XOR operations and the arithmetic operations of Multiplication and Addition:
AND and Multiplication:
We can state that, using one bit, the multiplication is equivalent to the logical operation AND.
XOR and Addition:
Remember that 1 + 1 is 0 and “carry 1”! Thus, we can also say that, using one bit, the addition is equivalent to the logical operation XOR.
Operations with more than one bit
These logical operations can also be performed with a greater number of bits. In this case, the operation is done bit by bit. In the examples below, column by column:
1101 AND 0111 = ?
1101 AND 0111 = 0101
1110 OR 0110 = ?
1110 OR 0110 = 1110
1011 XOR 0011 = ?
1011 XOR 0011 = 1000
To end with, let’s see some practical examples with these operators.
Let’s imagine we have a controller register of 8 bits which controls the “switch on” or “switch off” of some devices. Let’s also assume that the 3rd bit (remember that we can number the bits from right to left from 0 to 7) controls the PC speaker and the 2nd bit controls a second screen.
And let’s also assume we have this register with the following binary values:
We have the 3rd bit (speaker – in green) set to 0, which means that the speaker is switched off, and the 2nd bit (2nd screen – in yellow) set to 1, which means that the second screen is switched on.
We want to perform an operation to switch on both devices, independently if they are already switched on or not. To do so, we use the OR operator where 0 is the identity element and 1 is the absorbing element:
Notice that in the first row we have the register bits and in the second row the bits used to perform the operation. Also notice that all the bits on this second row are set to 0 with the exception of the 2nd and 3rd bits which are set to 1. By doing so, we assure that with the remaining bits set to 0 we won’t change the state of the other bits in the register! We only want to activate the 2nd and 3rd bits and that’s the reason why the same bits on the second row are set to 1. In fact, by observing the third row, which represents the new state of the register, only the 2nd and 3rd bits were forced to be set to 1 and there are no changes on the remaining bits.
Let’s go back to the initial state of the register. Now, we want to switch off those devices, independently if they are already switched off or not. In this case we will use the AND operator where 1 is the identity element and 0 is the absorbing element:
Now, notice that in the second row, all the bits used for the operation are set to 1 with the exception of the 2nd and 3rd bits, that we want to switch off, which are set to 0. In this case, we assure that we are only changing the 2nd and 3rd bits to 0! The remaining bits won’t be changed!
Let’s finish with a last example and let’s consider again the initial values of the register. Now we want to “invert” the state of the devices from switched on to switched off and vice-versa! To do so, we will use the XOR operator where we can say that the 0 is the identity element and 1 is the “inverter” element:
Notice that we have some similarities to the OR operator where the bits used in the operation that are set to 0 won’t change the result of the same bits in the register. However, having the 2nd and 3rd bits set to 1 we are “inverting” the corresponding bits in the register. So, we had the speaker switched off and now it is switched on and the second screen, which was switched on, is now switched off.
The case of the second screen is something more specific on display adapters and it was just used here as a mere example. However, there is a controller on the main board that use one of its bits to switch on or off the PC speaker (PIT – Programmable Interval Timer). In the past, where sound cards were just a mirage, some “melodies” were reproduced by using another register to set the sound frequency and the bit 1 of the PIT was used to switch on or off the PC speaker. (In fact, it was an input/output port of that controller, but we will speak about this later).
In all these examples, the binary number used in the operations is commonly called a bit mask. We will talk about this with more details in a future article about logical circuits…