BOOLEAN ALGEBRA --------------- George Boole: English mathematician published in Laws OF Thought (1854) DeMorgan: DeMorgan's Laws Charles Babbage: Builder of First Mechanical Computer Augusta Ada: First Programmer VARIABLES: BINARY (LOGICAL) 1,0 (True,False) Usually denoted by single letters. OPERATIONS: AND (*) OR (+) NOT (') Laws and theorems are valid IF all expressions are represented only in terms of these operators. NOTE: We also use gate diagrams for NAND, NOR, XOR, but the Laws of Boolean algebra DO NOT APPLY TO THEM DIRECTLY. Expressions using those operators must be re-represented with AND, OR, NOT before performing any algebraic tansformations. TRUTH TABLE One representation of a Boolean relation is to enumerate all possible input states and the result of the function for each such state. This is tabulated as a table with the input variables and the value of the input states on the left and the output on the right. For each state variable or Boolean result we use 0 or 1 to represent the possible values FALSE and TRUE, respectively. Where we wish to represent multiple functions on the same input variables we use additional labeled output columns. In order to interpret a truth table we always list the combinations of input variables in the columns at the left in a systematic ordered sequence. This is to assure that all combinations are enumerated without duplication or omissions. Also can facilitate recognizing patterns when we are looking for algebraic simplifications. A truth table can be constructed by directly evaluating the expression for each set of input states and writing down the truth value outputs. By definition, if alternative Boolean representations result in an identical truth table, then the functions are identical. A typical problem in Boolean algebra is proving or disproving the identity of two algebraic expressions. Truth Tables of some Alternative Boolean Expressions ---------------------------------------------------- A B AB A + B (AB)' (A + B)' ----------------------------------------------- 0 0 0 0 1 1 0 1 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 0 ---------------------------------------------------- A B A XOR B A NAND B A NOR B ----------------------------------------- 0 0 0 1 1 0 1 1 1 0 1 0 1 1 0 1 1 0 0 0 ---------------------------------------------------- BASIC POSTULATES (These are fundamental assumptions) ------------------------------------------------------------------- Identity A+0 = A A*1 = A Inverse A'+ A = 0 A' * A = 1 Nullity A+1 = 1 A*0 = 0 Commutative Laws A+B = B+A A*B = B*A Associateve Laws (A+B)+C = A+(B+C) (A*B)*C = A*(B*C) Distributive Laws A+(B*C) = (A+B)*(A+C) A*(B+C) = (A*B)+(A*C) Idempotent A+A = A A*A = A Absorption A+A*B = A A*(A+B) = A ------------------------------------------------------------------- AND (*) is usually used as an Implicit Operator just as in Real Numbers NEGATION ('), read as 'NOT', is the operation of taking the Complement, or inverting the value of a logic state. De Morgan's Laws ---------------- A NAND B = A' OR B' (A * B)' = A' + B' A NOR B = A' AND B' (A + B)' = A' * B' These examples are special cases of DeMorgan's theorem. The most general case may be stated as: To form the complement of two (or more) variables which are all ANDed (or ORed) together; there is an equivalent expression formed by complementing each variable and conjoining them with the dual of the first operator. Examples: ( A B' C )' = A' + B + C' ( B' + C )' = B C' Go back to our truth table examples and find examples of DeMorgan's law. DUALITY - BOOLEAN ALGEBRA THEOREM ANY VALID EQUALITY BETWEEN TWO EXPRESSIONS formed of operators AND, OR, NOT) RESULTS IN ANOTHER VALID EQUALITY IF THE OPERATORS (*, +) AND IDENTITY ELEMENTS (0,1) ARE INTERCHANGED. Such an alternate relation are equally true, but not equivalent. Note that in each of the laws and theorems above that there is an alternate form which can be constructed by applying the DUALITY PRINCIPLE. ABSORPTION THEOREM X + XY = X A variable ORed with a subset of itself can be represented by the variable alone. This is easily visualized in a graphical representation. (see Venn diagrams) The dual of that relation is X * (X+Y) = X GATES - SYMBOLS USED TO REPRESENT PHYSICAL LOGIC DEVICES Logic operations can be physically implemented as electronic circuit elements, typically now in integrated circuits (IC's). Gate symbols are graphic representations of logic operators as physical devices which are used in 'circuit diagrams'. Such diagrams are used by engineers and technicians to design and fabricate physical interconnections of devices. Such circuit diagrams are used to analyze and maintain physical electronic devices. These circuits, of course, may be parts of a computing system. Early computers were in fact constructed directly from individual gates as logic elements. ALGEBRAIC GATE Our apologies, but NIU REPRESENTATION NAME does not provide the software and printing F = AB AND support to display bit mapped graphics on your F = A + B OR terminal screen or let you print them. F = A' NOT See Barron & Higbie, or INVERTER Appendix B, Fig. B-4, p.416 F = (AB)' NAND F = (A + B)' NOR F = (AB' + A'B) XOR Circuits are often built using NAND, NOR, and XOR elements for good technical reasons. In some solid state technologies these elements switch faster. Switching delay is the time interval between when inputs change and when the valid logical output becomes true. These same elements are also cheaper (fewer lower level elements, transistors, results is less area of silicon required; resulting in less cost). SIMPLIFICATION OF EXPRESSIONS - EXAMPLE F = A + B + BC F = A + (B*1) + (B*C) : SUBSTITUTE B = B*1 F = A + B * (1 + C) : FACTOR, DISTRIBUTIVE LAW F = A + B * 1 : 1+C = 1 F = A + B ; B * 1 = B Note that we just did an algebraic proof of the Absorption Theorem. BY DUALITY, then, another function G: G = A * B * BC CAN BE SIMPLIFIED TO G = A * B Algebraic simplification is an art involving multiple substitutions of valid transformations so that the form of representation can be altered. The goal is to minimize the number of operators and the number of occurrences of variables. To be good at it requires: 1. memorizing all the laws of Boolean algebra and a number of theorems such as DeMorgan's' law and Absorption Theorem. 2. Practice COMPLEMENT OF A FUNCTION - generalization of DeMorgan Law The complement of a function F, denoted F', may be constructed from F by negating each operand (including any Boolean constants (0 or 1)) and interchanging the operators AND, OR. Example: find the complement of F = A(B' + C) F' = A' + BC' FROM TRUTH TABLE TO ALGEBRAIC REPRESENTATION: SUM OF PRODUCTS representation of a function F We are given a truth table which defines F as a function of the Boolean variables A, B, C. By definition, if a set of values for A,B,C gives an output of 1 for F then a term with he three variables ANDed together with the variable for each input 1 and the complement of each variable for each 0 in the input state. The entire function is then represented by ORing all the terms for which there is a 1 in the output column. Thus we can write down a representation of the function by inspection from the truth table. A B C F F' --------- ----- ----- 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 1 1 0 1 1 0 0 1 A B' C 0 1 0 1 1 A B' C 0 1 1 0 0 1 1 1 1 1 A B C 0 What is the above function, F, as a Boolean algebraic expression? F = 1 WHEN A = 1, B = 0, C = 0 --> A B'C' A = 1, B = 0, C = 1 --> A B'C A = 1, B = 1, C = 1 --> ABC So F = A B'C'+ AB'C + ABC SUM OF PRODUCTS FORM Note that this can be written by inspection from the truth tale. We get one term for each 1 in the output column. The term is formed by ANDing each variable which has a 1 in the input state, and ANDing the complement of each variable which has a 0 as its input state. All the terms from the output 1's are then ORed together. PRODUCT OF SUMS representation Alternatively, using the same function above, F is TRUE when the terms that produce a 0 output are ALL NOT TRUE. Consider F = (F')' and note that a 1 of F' is a 0 of F. A B C F F' --------- - - 0 0 0 0 1 A'B'C' 0 1 0 0 1 A'BC' 0 1 1 0 1 A'BC 1 0 0 0 1 AB'C' 1 1 0 0 1 ABC' Thus F' = A'B'C' + A'BC' + A'BC + AB'C' + ABC' and F = ( F' )' and by applying DeMorgan's law we get: F = (A+ B+ C)(A+ B'+ C)(A + B'+ C')(A'+ B + C )(A'+B'+C) This is the 'Product of Sums' representation - the general form is a set of terms all ANDed together, a 'Product'. Each term contains all the variables (or its complement), ORed together, as a 'Sum'. This form also can be written by inspection from the truth table. In this case we look at all the ZEROs of F, and write a term for each ZERO. The variables in the 'Sum' term are entered as the COMPLEMENT of the input state variables. to form the term. The terms are then all ANDed together. We do not need to formally write out F' and apply DeMorgan's law explicitly. While the 'Sum of Products' or 'Product of Sums' representation written from the truth table gets us an algebraic representation it does not necessarily get us a simplified representation. Note however that either form has a number of terms depending on the number of 1's or 0's. Hence if the number of 1's is smaller than the number of zeros. the 'Sum of Products' will be simpler. On the other hand if there are only a few zeros, the 'Product of Sums' form will be simpler. EXPANSION THEOREM Any simplified term or expression can be expanded to a form where it is composed only of terms where each contains all of the variables. That is to say we can use an algebraic transformation to get to the form we could write by inspection from the truth table. [That means if we have an algebraic representation of a function we can rewrite to a form where each term maps to a single 1 or 0 of the truth table.] If we expand to a 'Sum of Products' form, we can write all the 1's into the truth table. All the rest of the table entries then must be 0's. Given a function P( A,B,C), P = AB + BC' The first term does not contain variable C. But AB * 1 = AB and C + C' = 1, so AB = AB * ( C + C') = ABC + ABC' The second term can be similarly transformed by: BC' = BC"* ( A + A') = ABC' + A'BC' So we can rewrite P = ABC + ABC' + ABC' + A'BC and since ABC' + ABC' = ABC' ; the expanded Sum of Products form is: P = ABC + ABC' + A'BC A B C P --------- from this we can write the 0 0 0 3 0 truth table at the right 0 0 1 3 0 by inspection: 0 1 0 3 0 0 1 1 3 1 A'BC We write in the one's for 1 0 0 3 0 each of the given 3 terms 1 0 1 3 0 of P, and write in 0's for 1 1 0 3 1 ABC' the rest. 1 1 1 3 1 ABC PROVING THEOREMS (1). F1 = F2 IF YOU CAN TRANSFORM ---------------- BOTH SIDES TO IDENTICAL FORM BY A SEQUENCE OF LEGAL ALGEBRAIC STEPS (2). F1 = F2 IF BOTH HAVE SAME TRUTH TABLE. (3). F1 = F2 IF BOTH FUNCTIONS RESULT IN AN EQUIVALENT VENN DIAGRAM. (USEFUL ONLY FOR 2 OR 3 VARIABLES) A highly relevant problem in software maintenance is proving that two Boolean expressions are equivalent. For example you read the specifications for a program, on which you need to do maintenance. You decide that the termination condition for a loop is: B OR (NOT A AND B) OR ( NOT A AND NOT B AND NOT C) the current copy of the source code has the condition as: (NOT A) OR B is the code correct? (Good programming practice, however, is to NOT do a simplification of conditional expressions unless : 1. the simplified form also makes sense from the stated specifications. OR 2. there is a need to optimize the code AND the simplified expression would speed up the computation. In which case the fact that the Boolean algebra equivalence to the previous version should be noted in the source code commentary. The best form for representing a conditional expression in a program, is to use a form which can be most easily understood from the program specification. If efficiency is a relevant factor then a condition which is evaluated every time a loop is executed will be speeded up by expressing the condition in the simplest algebraic form. In many cases the evaluation stops as soon as a true condition is reached. Example: (expr1 OR expr2 OR expr3) is true as soon as the evaluation of one expression becomes TRUE, and no further expression evaluation is needed. Therefore in such cases it may be important be able to order the expressions in the order of their probability of occurrence in the application.