Laws & Rules of Boolean algebra
|
|
The manipulation of algebraic expressions is based on fundamental laws. Some of these laws extend to the manipulation of Boolean expressions. For example, the commutative law of algebra which states th at the result of an operation is the same regardless of the order of operands holds true for Boolean algebra too. This is shown for the OR function applied to two variables in the truth tables given below |
|
|
|
Not only does image above show how the commutative law applies to the OR function, it also shows how truth tables can be used in Boolean algebra to prove laws and rules. If a rule states that two Boolean expressions are equal, then by developing the truth table for each expression and showing that the output is equal for all combinations of ones and zeros at the input, then the rule is proven true. |
|
Below, the three fundamental laws of Boolean algebra are given along with examples. |
|
Commutative Law: |
|
The results of the Boolean operations AND and OR are the same regardless of the order of their operands. |
|
|
|
Associative Law: |
|
The results of the Boolean operations AND and OR with three or more operands are the same regardless of which pair of elements are operated on first. |
|
|
|
Distributive Law: |
|
The AND’ing of an operand with an OR expression is equivalent to OR’ing the results of an ANDbetween the first operand and each operand within the OR expression. |
|
|
|
Rules of Boolean algebra |
|
NOT Rules |
|
In algebra, the negative of a negative is a positive and taking the inverse of an inverse returns the original value. Although the NOT gate does not have an equivalent in mathematical algebra, it operates in a similar manner. If the Boolean inverse of a Boolean inverse is taken, the original value results. |
|
|
|
This is proven with a truth table. |
|
|
|
Since the first column and the third column have the same pattern of ones and zeros, they must be equivalent. Image below shows this rule in schematic form. |
|
|
|
OR Rules |
|
If an input to a logic gate is a constant 0 or 1 or if the same signal is connected to more than one input of a gate, a simplification of the expression is almost always possible. This is true for the OR gate as is shown with the following four rules for simplifying the OR function. First, what happens when one of the inputs to an OR gate is a constant logic 0? It turns out that the logic 0 input drops out leaving the remaining inputs to stand on their own. Notice that the two columns in the truth table below are equivalent thus proving this rule. |
|
|
|
What about inputting a logic 1 to an OR gate? In this case, a logic 1 forces the other operands into the OR gate to drop out. Notice that the output column (A + 1) is always equal to 1 regardless of what A equals. Therefore, the output of this gate will always be 1. |
|
|
|
Another case of simplification occurs when an operand is connected to one input of a two-input ORgate and its inverse is connected to the other. In this case, either the operand is equal to a one or its inverse is. There is no other possibility. Therefore, at least one logic 1 is connected to the inputs of the OR gate. This gives us an output of logic 1 regardless of the inputs. |
|
|
|
AND Rules |
|
Just as with the OR gate, if either of the inputs to an AND gate is a constant (logic 0 or logic 1) or if the two inputs are the same or inversesof each other, a simplification can be performed. Let’s begin with the case where one of the inputs to the AND gate is a logic 0. Remember that an AND gate must have all ones at its inputs to output a one. In this case, one of the inputs will always be zero forcing this ANDto always output zero. The truth table below shows this. |
|
|
|
If one input of a two-input AND gate is connected to a logic 1, then it only takes the other input going to a one to get all ones on the inputs. If the other input goes to zero, the output becomes zero. This means that the output follows the input that is not connected to the logic 1. |
|
|
|
If the same operand is connected to all of the inputs of an AND gate, we get a simplification similar to that of the OR gate. Notice that the two columns in the truth table below are equivalent proving this rule. |
|
|
|
Last of all, when an operand is connected to one input of a two-input AND gate and its inverse is connected to the other, either the operand is equal to a zero or its inverse is equal to zero. There is no other possibility. Therefore, at least one logic 0 is connected to the inputs of the AND gate giving us an output of logic 0 regardless of the inputs. |
|
|
|
XOR Rules |
|
Now let’s see what happens when we apply these same input conditions to a two-input XOR gate. Remember that a two-input XOR gate outputs a 1 if its inputs are different and a zero if its inputs are the same. If one of the inputs to a two-input XOR gate is connected to a logic 0, then the gate’s output follows the value at the second input. |
|
In other words, if the second input is a zero, the inputs are the same forcing the output to be zero and if the second input is a one, the inputs are different and the output equals one. |
|
|
|
If one input of a two-input XOR gate is connected to a logic 1, then the XOR gate acts as an inverter as shown in the table below. |
|
|
|
If the same operand is connected to both inputs of a two-input XOR gate, then the inputs are always the same and the gate outputs a 0. |
|
|
|
Lastly, if the inputs of a two-input XOR gate are inverses of each other, then the inputs are always different and the output is 1. |
|
|