(Last Mod: 27 November 2010 21:38:40 )
In the context of this discussion, words like "logic" and "logical" refer to a means of analyzing information based on the premise that each piece of information can only take on one of two values - True and False. Boolean Logic - also referred to as Boolean Arithmetic - is just a means of combining expressions involving variables that are restricted to these values.
The field of Boolean Arithmetic goes far beyond what will be covered here - this is merely a brief introduction to the basics.
We use Boolean Logic in everyday life all the time. For instance, we might have a personal policy about when to fill the gas tank in our car that says that we will fill it whenever we are below one-quarter of a tank but that we will also fill it if the price of gas is not higher than a certain amount provided we are also below three-quarters of a tank. If we were to express this more formally we would need three bits of information to make our decision plus an additional bit to represent the result of that decision. For instance, we might name our bits as follows:
Our logical expression is then:
(FillUp) = (LessThan1/4) OR ( (LessThan3/4) AND (NOT(HigherThanPrice)) )
The above expression uses what are considered the three primitive operators of Boolean Logic - NOT, AND, and OR. Each of these operators takes on the properties that we normally expect it to based on everyday usage. To formalize these, we explicitly state all of the possible combinations of input values and what the resulting output value would be for each combination. This is referred to as a "Truth Table"
This operator has a single input, A. Its output, Y, has the opposite state as the input.
| IN | NOT |
| A | Y |
| F | T |
| T | F |
This operator has two inputs, A and B. Its output, Y, is TRUE only if both of its inputs are TRUE. It can be generalized to any number of inputs by following the rule that the output is TRUE only if ALL of the inputs are TRUE.
| IN | AND | |
| A | B | Y |
| F | F | F |
| F | T | F |
| T | F | F |
| T | T | T |
This operator has two inputs, A and B. Its output, Y, is TRUE if either of its inputs are TRUE. It can be generalized to any number of inputs by following the rule that the output is TRUE if ANY of the inputs are TRUE.
| IN | OR | |
| A | B | Y |
| F | F | F |
| F | T | T |
| T | F | T |
| T | T | T |
It turns out that, in everyday usage, we actually use two meanings for the word "or" and usually rely on context to determine which is meant. For instance, a parent might tell a child that they will get grounded if they don't do their homework or if they stay out too late. In this case, it is understood that they will get grounded if they don't do their homework and they stay out too late. In other words, the will get grounded if one or the other or both of the inputs are true. This is called an "inclusive-OR" because it includes as true the condition where both inputs are true. But that same child might get told at dinner that they can ice cream or chocolate cake for dessert. In this case, we do not mean that they can have ice cream and chocolate cake. In other words, than can have one or the other but not both. This is called an "exclusive-OR" because it excludes from being true the condition where both inputs are true.
In formal logic, we can't allow the context of usage to determine which form is meant - we must be explicit. The two operators are called IOR and XOR for Inclusive-OR and Exclusive-OR respectively. In practice the term IOR is seldom used and it is assumed that OR is to be interpreted as IOR and that we will explicitly indicate when we mean XOR.
Although not as apparent as the AND and IOR operators, the XOR can also be generalized to any number of inputs by following the rule that the output is TRUE only if an odd number of inputs is TRUE.
| IN | XOR | |
| A | B | Y |
| F | F | F |
| F | T | T |
| T | F | T |
| T | T | F |
The basic operators have some useful properties that can be exploited when developing logical systems - whether hardware or software based. Perhaps the three most fundamental of these properties is the ability to set, clear, and toggle a logical value using a "mask".
It is commonly the case that we have many bits that we can store logical values in but, because of the way our system is constructed, we can't read and write those bits individually. Instead, we have to read and write to a larger collection of bits, such as a byte or an even larger multi-byte value, simultaneously and as a whole. If we are going to work with individual bits under these conditions, then we must exploit the properties of the logical operators in such a way as to allow us to determine and/or change the state of one bit within a larger collection of bits without being affected by the state of any of the other bits and, just as importantly, without affecting the state of those other bits in the process. This is called "bit banging" and the material here provides the necessary understanding of the properties that need to be exploited in order to carry out useful bitwise operations.
In all of the discussions that follow, we will assume that we have a data bit, A, that we want to work with and a control bit, MASK, available to us. Let's look at the practical meaning of the basic logic operations in this context.
A = (A) AND (NOT (MASK))
- If the MASK bit is FALSE, then the value written to A is the same as what was already there.
- If the MASK bit is TRUE, then the value of A is cleared (forced to be FALSE)
A = (A) OR (MASK)
- If the MASK bit is FALSE, then the value written to A is the same as what was already there.
- If the MASK bit is TRUE, then the value of A is set (forced to be TRUE)
A = (A) XOR (MASK)
- If the MASK bit is FALSE, then the value written to A is the same as what was already there.
- If the MASK bit is TRUE, then the value written to A is the opposite of what was already there.
The important properties in each case is that (a) when the control bit is FALSE, the value in the data bit is left effectively unaltered regardless of what was originally stored there, and (b), when the control bit is TRUE the value written to the data bit accomplished some specific desired result regardless of the value originally stored.