Boolean Algebra - Boolean logic, Boolean operations, operator precedence, laws of Boolean algebra, representation of Boolean functions, simplification methods
Boolean Logic
Boolean algebra is a branch of algebra in which the values of the variables are the truth values TRUE or FALSE, usually denoted by 1 and 0 respectively. It is fundamental to the design and operation of digital computers and electronic circuits. Unlike regular algebra, which deals with continuous values, Boolean algebra deals with discrete values and logical relationships.
The core concept is that every statement or variable can be in one of two states: true or false. This binary nature makes it perfectly suited for representing the states of electronic switches, logic gates, and data bits within a computer.
Boolean Operations
Boolean algebra uses three basic logical operations: AND, OR, and NOT. These operations are performed on Boolean variables (which can be 0 or 1).
1. AND Operation (Logical Product)
The AND operation is true (1) only if both operands are true (1). Otherwise, it is false (0). It is often represented by a dot (.), a multiplication sign (*), or simply by juxtaposition.
Truth Table for AND:
| A | B | A AND B (A.B) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
2. OR Operation (Logical Sum)
The OR operation is true (1) if at least one of the operands is true (1). It is false (0) only if both operands are false (0). It is often represented by a plus sign (+).
Truth Table for OR:
| A | B | A OR B (A + B) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
3. NOT Operation (Complement or Negation)
The NOT operation inverts the operand. If the operand is true (1), the result is false (0), and vice versa. It is often represented by a prime ('), a bar over the variable, or a preceding symbol like '~'.
Truth Table for NOT:
| A | NOT A (A') |
|---|---|
| 0 | 1 |
| 1 | 0 |
Operator Precedence
In Boolean algebra, the order in which operations are performed is important, similar to regular algebra. The standard order of precedence is:
- NOT (Complement)
- AND (Product)
- OR (Sum)
Parentheses are used to override this precedence, just as in regular algebra. For example, in the expression A + B.C, the AND operation (B.C) is performed first, and then the result is ORed with A. However, in the expression (A + B).C, the OR operation (A + B) is performed first.
Example: Evaluate A + B.C' when A=1, B=0, C=0. First, evaluate C': C' = 0' = 1. Next, evaluate B.C': B.C' = 0.1 = 0. Finally, evaluate A + (B.C'): A + 0 = 1 + 0 = 1.
Laws of Boolean Algebra
Boolean algebra has a set of laws that are similar to, but distinct from, the laws of ordinary algebra. These laws are essential for simplifying Boolean expressions and designing logic circuits.
1. Identity Laws
These laws state that ANDing a variable with 1 results in the variable itself, and ORing a variable with 0 results in the variable itself.
- A . 1 = A
- A + 0 = A
2. Null or Dominance Laws
These laws state that ANDing a variable with 0 results in 0, and ORing a variable with 1 results in 1.
- A . 0 = 0
- A + 1 = 1
3. Idempotent Laws
These laws state that ANDing a variable with itself results in the variable, and ORing a variable with itself results in the variable.
- A . A = A
- A + A = A
4. Complement Laws
These laws state that ANDing a variable with its complement results in 0, and ORing a variable with its complement results in 1.
- A . A' = 0
- A + A' = 1
5. Commutative Laws
These laws state that the order of operands does not affect the result for AND and OR operations.
- A . B = B . A
- A + B = B + A
6. Associative Laws
These laws state that the grouping of operands does not affect the result for multiple AND or OR operations.
- (A . B) . C = A . (B . C)
- (A + B) + C = A + (B + C)
7. Distributive Laws
These laws show how AND and OR operations distribute over each other.
- A . (B + C) = (A . B) + (A . C)
- A + (B . C) = (A + B) . (A + C)
The second distributive law, A + (B . C) = (A + B) . (A + C), is particularly important as it does not have a direct counterpart in ordinary algebra.
8. Absorption Laws
These laws help simplify expressions where a variable is ORed with the AND of itself and another variable, or vice versa.
- A + (A . B) = A
- A . (A + B) = A
9. De Morgan's Laws
These laws are crucial for negating complex expressions and are fundamental in circuit design. They state how to distribute a negation over an AND or OR operation.
- (A . B)' = A' + B'
- (A + B)' = A' . B'
In words: The complement of a product is the sum of the complements. The complement of a sum is the product of the complements.
10. Involution Law
This law states that the double complement of a variable is the variable itself.
- (A')' = A
Representation of Boolean Functions
A Boolean function is an expression that represents a logical relationship between input variables and an output. It can be represented in various forms, the most common being:
1. Algebraic Form
This is the standard mathematical notation using Boolean operators (AND, OR, NOT), variables, and parentheses. Example: F(A, B, C) = A.B' + C
2. Truth Table
A truth table lists all possible combinations of input variable values and the corresponding output value of the function for each combination. This is a complete and unambiguous representation. Example: Function F(A, B) = A + B
| A | B | F(A, B) = A + B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
3. Sum of Products (SoP) Form
In this form, the function is represented as an OR of AND terms. Each AND term (called a product term or minterm) corresponds to a row in the truth table where the output is 1. A product term is an AND operation of all input variables, where each variable appears either in its normal form or complemented form. Example: F(A, B, C) = A'BC + AB'C' + ABC
To derive SoP from a truth table: 1. Identify rows where the output is 1. 2. For each such row, create a product term by ANDing the input variables. If a variable is 0 in that row, use its complement; if it's 1, use its normal form. 3. OR all these product terms together.
4. Product of Sums (PoS) Form
In this form, the function is represented as an AND of OR terms. Each OR term (called a sum term or maxterm) corresponds to a row in the truth table where the output is 0. A sum term is an OR operation of all input variables, where each variable appears either in its normal form or complemented form. Example: F(A, B, C) = (A'+B+C) . (A+B'+C) . (A+B+C')
To derive PoS from a truth table: 1. Identify rows where the output is 0. 2. For each such row, create a sum term by ORing the input variables. If a variable is 1 in that row, use its complement; if it's 0, use its normal form. 3. AND all these sum terms together.
Simplification Methods
Boolean expressions can often be simplified to reduce the number of logic gates required to implement them, leading to more efficient and cost-effective digital circuits. Common simplification methods include:
1. Algebraic Simplification
This method uses the laws of Boolean algebra to manipulate and simplify expressions. It requires a good understanding of the laws and practice in applying them.
Example: Simplify F = A.B + A.B' + A'.C F = A.(B + B') + A'.C (Distributive Law) F = A.(1) + A'.C (Complement Law) F = A + A'.C (Identity Law) F = (A + A').(A + C) (Distributive Law) F = (1).(A + C) (Complement Law) F = A + C (Identity Law)
2. Karnaugh Maps (K-maps)
K-maps are a graphical method for simplifying Boolean expressions. They are particularly effective for functions with up to 4 or 5 variables. A K-map is a grid where each cell represents a minterm (for SoP simplification) or maxterm (for PoS simplification) of the function. Adjacent cells (horizontally or vertically, wrapping around edges) differ by only one variable.
Steps for SoP simplification using K-maps: 1. Create a K-map grid for the number of variables (e.g., 2, 3, or 4 variables). 2. Fill the map with 1s in the cells corresponding to the minterms where the function's output is 1, or based on the truth table. 3. Group adjacent 1s in powers of 2 (1, 2, 4, 8, ...). The groups should be as large as possible. Groups can wrap around edges and corners. 4. Each group corresponds to a product term. The term is formed by ANDing the variables that are constant within that group. If a variable is complemented in the group, use its complement; if it's uncomplemented, use its normal form. If a variable changes within the group, it is eliminated from the term. 5. The simplified function is the OR (sum) of all product terms derived from the groups.
Example: Simplify F(A, B, C) = Σm(1, 3, 6, 7) using a 3-variable K-map. The minterms are: 001, 011, 110, 111.
| A\BC | 00 (0) | 01 (1) | 11 (3) | 10 (2) | ||||
|---|---|---|---|---|---|---|---|---|
| 0 (00) | 0 | 1 | 1 | 0 | ||||
| 1 (10) | 0 | 0 | 1 | 1 | ||||
Groups: Group 1: A vertical pair of 1s in the BC=11 column (minterms 3 and 7). A is 0 in this column, so A' is constant. Thus, the term is A'C. Group 2: A horizontal pair of 1s in the A=1 row, columns BC=10 and BC=11 (minterms 6 and 7). A is 1 (so A is constant). BC changes from 10 to 11, so B is constant at 1, but C changes. Thus, the term is AB. Simplified F = A'C + AB.
3. Quine-McCluskey Method
This is a tabular method for simplifying Boolean functions, especially useful for functions with more than 4 variables where K-maps become cumbersome. It is an algorithmic approach that guarantees finding the minimal sum-of-products form.
The method involves two main steps: 1. Finding Prime Implicants: Systematically combine minterms that differ by only one variable to find all possible implicants, then identify the prime implicants (implicants that cannot be combined further). 2. Forming the Minimum Cover: Select a minimal set of prime implicants that cover all the minterms of the function. This selection process often involves a prime implicant chart.
While powerful, the Quine-McCluskey method is more complex to perform manually compared to K-maps but is well-suited for computer implementation.