BOOLEAN MANIPULATION
Boolean equations are invaluable when designing digital logic. To properly use and devise such equations, it is helpful to understand certain basic rules that enable simplification and re-expression of Boolean logic. Simplification is perhaps the most practical final result of Boolean manipulation, because it is easier and less expensive to build a circuit that does not contain unnecessary components. When a logical relationship is first set down on paper, it often is not in its most simplified form. Such a circuit will function but may be unnecessarily complex. Re-expression of a Boolean equation is a useful skill, because it can enable you to take better advantage of the logic resources at your disposal instead of always having to use new components each time the logic is expanded or otherwise modified to function in a different manner. As will soon be shown, an OR gate can be made to behave as an AND gate, and vice versa. Such knowledge can enable you to build a lesscomplex implementation of a Boolean equation.
First, it is useful to mention two basic identities:
A & A = 0 and A + A = 1
The first identity states that the product of any variable and its logical negation must always be false. It has already been shown that both operands of an AND function must be true for the result to be true. Therefore, the first identity holds true, because it is impossible for both operands to be true when one is the negation of the other. The second identity states that the sum of any variable and its logical negation must always be true. At least one operand of an OR function must be true for the result to be true. As with the first identity, it is guaranteed that one operand will be true, and the other will be false.
Boolean algebra also has commutative, associative, and distributive properties as listed below:
• Commutative: A & B = B & A and A + B = B + A
• Associative: (A & B) & C = A & (B & C) and (A + B) + C = A + (B + C)
• Distributive: A & (B + C) = A & B + A & C
The aforementioned identities, combined with these basic properties, can be used to simplify logic. For example,
A & B & C + A & B & C
can be re-expressed using the distributive property as
A & B & (C + C)
which we know by identity equals
A & B & (1) = A & B
Another useful identity, A + AB = A + B, can be illustrated using the truth table shown in
Augustus DeMorgan, another nineteenth century English mathematician, worked out a logical
transformation that is known as DeMorgan’s law, which has great utility in simplifying and re-expressing
Boolean equations. Simply put, DeMorgan’s law states
These transformations are very useful, because they show the direct equivalence of AND and OR
functions and how one can be readily converted to the other. XOR and XNOR functions can be represented by combining AND and OR gates. It can be observed from Table 1.3 that A(+)B = AB + AB and that A(+) ? = ?? + ? ?. Conversions between XOR/XNOR and AND/OR functions are helpful when manipulating and simplifying larger Boolean expressions, because simpler AND and OR functions are directly handled with DeMorgan’s law, whereas XOR/XNOR functions are not.
Keyword :
boolean functions ,boolean manipulation ,variables ,representation ,manipulation ,truth table ,terminal ,model checking ,minterms ,memory ,expression ,boolean function ,vertex ,values ,search ,metacart ,ieee transactions on computers ,equivalence ,decision tree ,circuits ,circuit ,bryant ,boolean query ,boolean logic ,boolean expression ,boolean algebra ,boolean ,binary decision diagrams ,bdd package ,algorithm.
