1. Introduction to Boolean Algebra
- Boolean algebra is an algebraic structure defined on a set of elements together with two binary operators (+) and (.)
- A variable is a symbol, for example, 'Α' used to represent a logical quantity, whose value can be 0 or 1.
- The complement of a variable is the inverse of a variable and is represented by the variable over bar.
- A literal is a variable or the complement of a variable.
- Boolean Value
- The value of Boolean variable can be either 1 or 0.
- Boolean Operators: There are three basic Boolean operators
- AND (∙) operator
- OR (+) operator
- NOT operator
- If an expression contains only the operations AND, OR and NOT. Then, the dual of that expression is obtained by replacing
each AND by OR,
each OR by AND,
all occurrences of 1 by 0,
all occurrences of 0 by 1.
The principle of duality is useful in determining the complement of a function.
- Logic expression: (x •y' •z) + (x •y •z' ) + (y •z) + 0 ,
- Duality of above logic expression is: (x + y' + z) • (x + y + z' ) • (y + z) • 1
- Any Boolean functions can be formed from binary variables and the Boolean operators.
- For a given value of the variable, the function can take only one value either 0 or 1.
- A Boolean function can be shown by a truth table. To show a function in a truth table we need a list of the 2n combinations of 1's and 0's of the 'n' binary variables and a column showing the combinations for which the function is equal to 1 or 0. So, the table will have 2n rows and columns for each input variable and tile final output.
- A function can be specified or represented in any of the following ways:
- A truth table
- A circuit
- A Boolean expression
- SOP (Sum Of Products)
- POS (Product of Sums)
- Canonical SOP
- Canonical POS
- Important Boolean operations over Boolean values:
3. Basic Theorems
- Important Theorems used in Simplification
- A + BC = (A + B)(A + C)
- Consensus Theorem: This theorem is used to eliminate redundant term. It is applicable only when a boolean function contains three variables. Each variable used two times. Only one variable is complemented or uncomplemented. Then the related terms so that complemented or uncomplemented variable is the answer.
4. MinTerm & MaxTerm
- Each product term is known as a minimum term that contains all the variables used in a function.
- A minterm is also called a canonical product term.
- A minterm is a product term, but a product term may or may not be a minterm.
- Each sum term is known as a maximum term that contains all of the variables used in the function.
- A maxterm is a sum term of all variables in which each variable is either in complemented form or in uncomplemented form.
- A maxterm is also called a canonical sum term.
- A maxterm is a sum term, but a sum term may or may not be a maxterm.
- The following are examples of product term, minterm, sum term, and maxterm for a function of three variables a, b, and c:
- product terms: a, ac, b’c, abc, a’bc, a’b’c’, …
- minterms: ab’c, abc, a’b’c, a’b’c’, …
- sum terms: a, (a+b), (b+c), (a’+b), (a’+b’), …
- maxterms: (a+b+c), (a+b’+c), (a’+b’+c’), …
- Representations of Minterm and Maxterm:
Note: With' n' variables maximum possible minimum and maximum terms = 2n
- With' n' variables maximum possible logic expression =
5. SOP & POS
- SOP (Sum of Product): A sum of product expression is two or more OR functions of AND functions.
- SOP expression is used when output becomes logic 1.
- POS (Product of Sum): It is the AND function of two or more OR function.
- POS expression is used when output is logic '0'.
- Example: SOP and POS Equivalences for function F and Its Inverse F’.
6. Duality Theorem
- To convert positive logic into negative logic and vice-versa, a dual function is used.
- Change each AND sign by OR sign and vice versa (↔ +)
- Complement any 0 or l appearing in expression.
- Keep variable as it is.
7. Minimization of Boolean Expressions
The following two approaches can be used for simplification of a Boolean expression:
- Algebraic method (using Boolean algebra rules)
- Karnaugh map method
Representation of K-map: With n-variable Karnaugh-map, there are 2n cells
- 2 –variable K Map:
- 3 –variable K Map:
- 4 –variable K Map:
- NOTE: Once the Karnaugh map has been populated with 1s, 0s and Xs as specified the only task that remains is to group adjacent terms of the same state (usually 1) in groups of 2 raised to any rational power, i.e. 1, 2, 4, 8, 16, 32, 64 and so on. The larger the group the simpler the final expression. It is also possible for groups to overlap. This is often done to achieve a larger group size, hence simplifying the final expression.
Minimization Procedure of Boolean Expression using K-map
- Construct a K-map.
- Find all groups of horizontal or vertically adjacent cells that contain 1.
- Each group must be either rectangular or square with 1, 2, 4, 8, or 16 cells.
- Each group should be as large as possible.
- Each cell with 1 on the K-map must be covered at least once. The same
- the cell can be included in several groups if necessary.
- Select the least number of groups so as to cover all the 1’s.
- Adjacency applies to both vertical and horizontal borders.
- Translate each group into a product term. (Any variable whose value changes from cell to cell drops out from the term)
- Sum all the product terms.
- Note: Don't care conditions can be used to provide further simplification of a Boolean Expression.
- EXAMPLE: Simplify the following equation using a K-map (Karnaugh-map):
- SOLUTION: Draw the K-map and minimize.
If you are preparing for GATE and ESE, avail Online Classroom Program to get unlimited access to all the live structured courses and mock tests from the following link :