1.Simplification Methods for Logical Functions
The simpler the logical function is, the simpler the logical circuit used to implement it will be, and the fewer components will be used, resulting in lower cost and more reliable operation.
As mentioned above, the commonly used formulas can be expressed as circuits, as shown in the following figure：
2. The Simplest Form of a Boolean Function Expression
There are many different ways to express the simplest form of a logical function, but in digital circuits, we generally prefer to use the minimal sum-of-products (SOP) expression.
Minimal SOP expression refers to a logical function with the fewest possible product terms, with each product term containing the minimum number of variables.
The “Sum of Products” (SOP) is a simplest form of a Boolean function expression that is represented as the sum of several product terms. Each product term consists of all the input variables or their complements, and there are no further simplifications that can be made in this expression.
SOP expressions are also known as “AND expressions” because all variables in each product term must be true for the expression to be true. Therefore, SOP expressions are often used in switch control and memory addressing in logic circuits.
For example, here is a minimal SOP expression for a Boolean function with four input variables A, B, C, and D:
F = A’B’C’D + A’BC’D’ + AB’C’D’ + ABCD
Here,
- “+” represents logical OR,
- “.” represents logical AND,
- and “‘” represents logical NOT.
This expression can be derived and simplified using methods such as Karnaugh maps or Boolean algebra.
(Not Finished YET)
2.1) Any logical function can be transformed into a sum-of-products (SOP) expression, as shown below.
2.2) Converting a logical function expression into its simplest form is called function simplification. The simplification of a logical function means transforming it into a simpler and easier-to-implement form while maintaining the equivalence of the logical function. By simplifying a logical function, the circuit can be simplified, the use of components reduced, and the cost and the complexity lowered, thus improving the reliability of the circuit.
2.3) The two methods for simplifying logical expressions are formula simplification and Karnaugh map simplification.
- Formula simplification involves applying algebraic rules and logical identities to the expression to obtain a simplified form. This method is often used for small to medium-sized expressions.
- Karnaugh map simplification involves graphically representing the logical function using a two-dimensional table and grouping the cells containing 1’s together in a way that maximizes the number of adjacent cells. This method is often used for larger expressions.
Both methods can be used to obtain the same simplified form of a logical expression.
3.Formula Simplification
3.1) sum-of-products (SOP) form and product-of-sums (POS)
Sum-of-Products and Product-of-Sums are two commonly used methods in logical function simplification.
Sum-of-Products (SOP): refers to combining parts of two or more product terms that have only some variables in common. For example, by combining the first and second product terms of A’B’C + A’BC + AB’C + ABC, we get A’C(B+1) + AB’C + ABC, which reduces one product term.
Product-of-Sums (POS): refers to combining two or more terms that have the same variables. For example, by pairing the B variable in the first term of A’B + AB with the B variable in the second term of AB, we get AB + A’B, which reduces one variable.
These two methods can be used together and the appropriate method can be chosen based on the specific situation to obtain the simplest logical expression.
3.2) Idempotent Law
In Boolean algebra, a sum term is a term that represents the OR of two or more variables or literals. A sum term is also known as a minterm or a canonical sum term. It is called a minterm because it is the term that results in a value of 1 for a specific combination of inputs. For example, the sum term A’B’C represents the OR of three variables A, B, and C with their complements, and evaluates to 1 when A=0, B=1, and C=0.
3.3) Absorption Law
3.4) Boolean Algebra Simplification Summary
We have seen here in this Boolean Algebra simplification tutorial that the object of simplifying Boolean algebra expressions is to obtain a final logical expression that has the minimum number of terms. A Boolean function is an algebraic expression formed using the AND, OR, and NOT operators.
There are several Boolean Algebra laws, rules and theorems available which provides us with a means of reducing any long or complex expression or combinational logic circuit into a much smaller one with the most common laws presented in the following Boolean algebra simplification table.
Boolean Algebra Simplification TableExample 3.4.1 )
Boolean Algebra simplification is a method used to simplify logic expressions, which can make circuit design more efficient and reliable. The basic idea of simplifying logic expressions is to use the theorems of logic algebra to simplify complex logic expressions into simpler forms, which facilitates the design and implementation of circuits. Among them, Karnaugh mapping is a commonly used method for simplifying logic algebra, which can transform Boolean expressions in the truth table into a logic circuit that is easy to understand and design.
The basic principle of Karnaugh mapping is to map each term in the truth table (a term is an expression composed of the product of several variables) into a two-dimensional table composed of squares, and then combine the terms with the same variables in the table to find the same terms for merging. In this process, certain rules and constraints must be followed, such as only being able to combine terms containing the same number of variables, and only being able to combine adjacent terms.
By using the Karnaugh mapping method, logic expressions can be simplified into the form of minimum terms or the sum of minimum terms. This way, the simplest form of the circuit can be obtained, reducing the cost and difficulty of circuit design. In addition, Karnaugh mapping can also be used for the design and optimization of logic circuits. By merging terms with the same variables, the size of the logic circuit can be reduced, improving the speed and stability of the circuit.
1. What is Karnaugh Maps ?
Karnaugh maps, also known as K-maps, are a graphical method used to simplify Boolean algebra expressions. They provide a systematic and visual way to find the simplest form of a Boolean expression, which can then be used to design or optimize digital circuits. K-maps are particularly useful for minimizing Boolean expressions that have several variables, and they can be used to minimize both sum-of-products and product-of-sums expressions. The method was developed by Maurice Karnaugh in the 1950s, and it remains a fundamental technique in digital logic design.
1.1) The Steps to use Karnaugh Maps
Karnaugh maps are used to simplify Boolean algebra expressions. Here are the steps to use Karnaugh maps:
- Identify the Boolean expression that needs to be simplified.
- Write the Boolean expression in canonical form, which is a sum-of-products (SOP) or a product-of-sums (POS) expression.
- Create a Karnaugh map with the same number of rows and columns as there are variables in the Boolean expression.
- Fill in the Karnaugh map with the Boolean values for each combination of input variables.
- Group adjacent cells in the Karnaugh map that have a value of 1.
- Write the simplified Boolean expression by combining the grouped cells in the Karnaugh map.
Here is an example:
Simplify the Boolean expression F = A’B’ + A’BC + AB’C’ + ABC’
- Write the expression in canonical form: F = Σm(0,2,5,7)
- Create a Karnaugh map with 2 rows and 4 columns since there are 2 variables: A and B.
- Fill in the Karnaugh map with the Boolean values for each combination of input variables:
B' B
A' 1 0
A 1 1
4. Group adjacent cells that have a value of 1:
B' B
A' 1 0
A 1 1
- Group 1: A’B’
- Group 2: A’BC + ABC’
- Group 3: AB’C’
- Write the simplified Boolean expression by combining the grouped cells in the Karnaugh map:
F = A’B’ + A’BC + ABC’ + AB’C’
This simplification has four terms. The original expression had four terms as well. However, the Karnaugh map simplification removed one redundant term. The reduced expression is easier to read, and it has fewer terms, which makes it more efficient to implement in digital circuits.
Distributive Law
The distributive law is one of the fundamental laws in Boolean algebra, which states that for any Boolean expressions X, Y, and Z:
- X · (Y + Z) = X · Y + X · Z (Distributivity of AND over OR)
- X + Y · Z = (X + Y) · (X + Z) (Distributivity of OR over AND)
These laws are extremely useful for simplifying Boolean expressions, as they allow us to break up complex expressions into simpler ones by distributing terms.where · represents the AND operation and + represents the OR operation. These laws allow us to simplify complex logical expressions by breaking them down into smaller expressions that are easier to manipulate.
Absorption Law
In Boolean algebra, the absorption law is a pair of identities that describe the relationship between logical conjunction (AND) and logical disjunction (OR) of propositions.
The first absorption law states that for any propositions P and Q, P OR (P AND Q) is logically equivalent to P. In other words, if one of the propositions is true, then the entire expression is true.
The second absorption law states that for any propositions P and Q, P AND (P OR Q) is logically equivalent to P. In other words, if one of the propositions is false, then the entire expression is false.
These laws can be used in simplifying logical expressions by eliminating redundant terms.