Boolean Algebra and Logic Simplification #
Boolean Algebra #
Boolean Algebra is the mathematics of digital systems. A single variable can only have a value of 1 or 0.
Lows of Boolean Algebra #
Commutative Lows: The commutative laws are applied to addition and multiplication. the commutative law states: In terms of the result, the order in which variables are ORed or ANDed makes no difference.
A + B = B + A
AB = BA
Associative Laws: The associative laws are also applied to addition and multiplication. For addition, the associative law states: When ORing or ANDing more than two variables, the result is the same regardless of the grouping of the variables.
A + (B +C) = (A + B) + C
A(BC) = (AB)C
Distributive Law: The distributive law is the factoring law. A common variable can be factored from an expression just as in ordinary algebra. That is:
AB + AC = A(B+ C)
Rules of Boolean Algebra #
Rule 1: A + 0 = A, a variable ORed with 0 is always equal to the variable.
Rule 2: A + 1 = 1, a variable ORed with 1 is always equal to 1.
Rule 3: A . 0 = 0, a variable ANDed with 0 is always equal to 0.
Rule 4: A . 1 = A, a variable ANDed with 1 is always equal to the variable.
Rule 5: A + A = A, a variable ORed with itself is always equal to the variable.
Rule 6: A + A’ = 1, a variable ORed with its complement is always equal to 1.
Rule 7: A . A = A, a variable ANDed with itself is always equal to the variable.
Rule 8: A . A’ = 0, a variable ANDed with its complement is always equal to 0.
Rule 9: A = A’’, the double complement of a variable is always equal to the variable.
Rule 10: A + AB = A, this rule can be proved as follows:
A+AB = A (1+B) Factoring (distributive low)
= A.1 Rule2: (1+B) = 1
= A Rule4: A. 1 = A
Rule 11: A + A’B = A + B, this rule can be proved as follows:
A + A’B = (A +AB) + A’B Rule10 (A=A+AB)
= (AA+AB) + A’B Rule7: A = AA
= AA + AB +AA’ +AB Rule8: adding AA’ = 0
= (A+A’) (A+B) Factoring
= 1. (A+B) Rule6: A+A’=1
= A+ B Rule4: 1. X = X
Rule 12: (A + B)(A + C) = A + BC, this rule can be proved as follows:
(A + B)(A + C) = AA + AC + AB + BC Distributive low
= A + AC + AB + BC Rule7: AA = A
= A (1+C) + AB + BC Factoring
= A.1 + AB + BC Rule2: 1+C = 1
= A (1 + B) + BC Factoring
= A.1 +BC Rule2: 1+B = 1
= A + BC Rule4: A.1 = A
DeMorgan’s Theorems #
- 1st Theorem: The complement of a product of variables is equal to the sum of the complemented variables. (XY)’ = X’ + Y’
- 2st Theorem: The complement of a sum of variables is equal to the product of the complemented variables. (X + Y)’ = X’. Y’
- Example: Apply DeMorgan’s theorem to remove the overbar covering both terms from the expression X = (C’ + D)’
- Solution: To apply DeMorgan’s theorem to the expression, you can break the overbar covering both terms and change the sign between the terms.
- This results in: X = C’’ . D’
- Deleting the double bar gives X = C . D’
Example: Apply Boolean algebra to simplify this expression:
AB + A (B+C) + B (B+C)
Solution:
1. Apply the distributive low to the 2nd and 3rd terms:
AB + AB + AC + BB + B
2. Apply rule 7 (BB=B) to the 4th term:
AB + AB + AC + B + BC
3. Apply rule 5 (AB+AB=AB) to the first two terms
AB + AC + B + BC
4. Apply rule 10 (B+BC=B) to the last two terms
AB + AC + B
5. Apply rule 10 (AB+B=B) to the 1st and 3rd terms
B + AC
Sum-of-Products and Product-of-Sums Forms #
- Boolean expressions can be written in the sum-of-products form (SOP) or in the product-of-
- sums form (POS). These forms can simplify the implementation of combinational logic, particularly with PLDs. In both forms, an overbar cannot extend over more than one variable.
- An expression is in SOP form when two or more product terms are summed as in the following examples: A’ B’ C’ + A B, A B C’ + C’ D’, C D + E’
- An expression is in POS form when two or more sum terms are multiplied as in the following examples: (A + B)(A’ + C) (A + B + C’)(B + D) (A’ + B)C
Example: Convert each of the following Boolean expressions to SOP form:
(a) AB + B(CD + EF) (b) (A + B)(B + C + D) (c) ((A + B)’ + C))’
Solution:
AB + B(CD + EF) = AB + BCD + BEF
(A + B)(B + C + D) = AB + AC + AD + BB + BC + BD
((A + B)’ + C))’ = (A + B)’’ C’ = (A + B) C’= AC’ + BC’
Boolean Algebra Standard Forms #
The Standard SOP Form #
- In SOP standard form, every variable in the domain must appear in each term. You can expand a nonstandard term to standard form by multiplying the term by a term consisting of the sum of the missing variable and its complement.
Example: Convert X = A’ B’ + A B C to standard form.
Solution: The first term does not include the variable C. Therefore, multiply it by the (C + C’), which = 1:
-
-
- X = A’ B’ (C + C’) + A B C = A’ B’ C + A’ B’ C’ + A B C
-
The Standard POS Form #
- In POS standard form, every variable in the domain must appear in each sum term of the expression. You can expand a nonstandard POS expression to standard form by adding the product of the missing variable and its complement and applying rule 12, which states that A + BC = (A + B)(A + C).
Example: Convert X = ( A’ + B’ )(A + B + C) to standard form.
Solution: The first sum term does not include the variable C. Therefore, add C C’, which= 0, and expand the result by rule 12.
X = (A’ + B’ + C C’) (A + B + C) = (A’ +B’ + C) (A’ + B’ + C’) (A + B + C)
Summary:
Lows of Boolean Algebra #
A + B = B + A
AB = BA
A + (B +C) = (A + B) + C
A(BC) = (AB)C
AB + AC = A(B+ C)
Rules of Boolean Algebra #
A + 0 = A
A + 1 = 1
A . 0 = 0
A . 1 = A
A + A = A
A + A’ = 1
A . A = A
A . A’ = 0
A = A’’
A + AB = A
A + A’B = A + B
(A + B) (A + C) = A + BC
DeMorgan’s Theorems #
(XY)’ = X’ + Y’
(X + Y)’ = X’ . Y’
