Boolean Algebra
Boolean algebra is a branch of algebra that deals with variables that can take on only two values: true (often represented as 1) and false (often represented as 0). Boolean algebra is a type of algebra that is created by operating the binary system. Boolean algebra is concerned with binary variables and logic operations. Boolean algebra is fundamental in the development of digital electronics systems as they all use the concept of Boolean algebra to execute commands. Apart from digital electronics this algebra also finds its application in Set Theory, Statistics, and other branches of mathematics.
Rules for Boolean Algebra
i) Variable used can have only two values
ii) The complement of a variable is represented by an over bar
iii) OR(adding) of the variables is represented by a plus (+) sign between them
iv) Logical AND(multiplying) of the two or more variables is represented by writing a dot between them
Boolean Laws
Boolean laws refer to a set of fundamental principles or rules that govern the behavior and manipulation of Boolean expressions, which consist of variables that can take on only two values: true (usually represented as 1) and false (usually represented as 0). These laws are essential in Boolean algebra for simplifying expressions, analyzing logical circuits, and solving logical problems.
Basic Boolean Laws:
1) Commutative Law: In Boolean algebra, the commutative law states that the order of operands does not affect the result of the operation. This means that for AND & OR operations, the order of the inputs does not matter. It`s like a magical rule that allows for flexibility and simplicity in Boolean algebra equations.
Example: Commutative law
OR operator → A + B = B + A
AND operator→ A.B = B . A
2) Associative Law: The associative law states that when OR’ing more than two variables, the result is the same regardless of the grouping of those variables. Similarly, the communicative law states that the order in which two variables are OR’ed makes no difference to the outcome.
Example: Associative Law
(a + b) + c = a + (b + c)
(a. b).c = a.(b .c)
3) Distributive Law: This law permits the multiplying or factoring out of an expression.
Example:
A(B + C) = A.B + A.C (OR Distributive Law)
A + (B.C) = (A + B).(A + C) (AND Distributive Law)
4) Inversion Law: The inversion law states that double inversion of variable results in the original variable itself. Example: A”=A, (A+B)” = (A+B), etc.
Boolean Expression Rules
Boolean expression rules define the principles and operations governing the construction and evaluation of logical expressions that yield (true/false) results.
Rule 1: A + 0 = A
Let’s suppose; we have an input variable A whose value is either 0 or 1. When we perform OR operation with 0, the result will be the same as the input variable. So, if the variable value is 1, then the result will be 1, and if the variable value is 0, then the result will be 0.
Diagrammatically, this rule can be defined as:
Rule 2: (A + 1) = 1
Let’s suppose; we have an input variable A whose value is either 0 or 1. When we perform OR operation with 1, the result will always be 1. So, if the variable value is either 1 or 0, then the result will always be 1.
Diagrammatically, this rule can be defined as:
Rule 3: (A.0) = 0
Let’s suppose; we have an input variable A whose value is either 0 or 1. When we perform the AND operation with 0, the result will always be 0. This rule states that an input variable AND’ed with 0 is equal to 0 always.
Diagrammatically, this rule can be defined as:
Rule 4: (A.1) = A
Let’s suppose; we have an input variable A whose value is either 0 or 1. When we perform the AND operation with 1, the result will always be equal to the input variable. This rule states that an input variable ANDed with 1 is equal to the input variable always.
Diagrammatically, this rule can be defined as:
Rule 5: (A + A) = A
Let’s suppose; we have an input variable A whose value is either 0 or 1. When we perform the OR operation with the same variable, the result will always be equal to the input variable. This rule states an input variable ORed with itself is equal to the input variable always.
Diagrammatically, this rule can be defined as:
Rule 6: (A + A’) = 1
Let’s suppose; we have an input variable A whose value is either 0 or 1. When we perform the OR operation with the complement of that variable, the result will always be equal to 1. This rule states that a variable ORed with its complement is equal to 1 always.
Diagrammatically, this rule can be defined as:
Rule 7: (A.A) = A
Let’s suppose; we have an input variable A whose value is either 0 or 1. When we perform the AND operation with the same variable, the result will always be equal to that variable only. This rule states that a variable ANDed with itself is equal to the input variable always.
Diagrammatically, this rule can be defined as:
Rule 8: (A.A’) = 0
Let’s suppose; we have an input variable A whose value is either 0 or 1. When we perform the AND operation with the complement of that variable, the result will always be equal to 0. This rule states that a variable ANDed with its complement is equal to 0 always.
Diagrammatically, this rule can be defined as:
Rule 9: A = (A’)’
This rule states that if we perform the double complement of the variable, the result will be the same as the original variable. So, when we perform the complement of variable A, then the result will be A’. Further if we again perform the complement of A’, we will get A, that is the original variable.
Rule 10: (A + AB) = A
Solution: here,
=A(1 + B)
= A.1
= A
Rule 11: A + AB = A + B
Solution: here,
= (A + AB)+ AB
= (AA + AB)+ AB
=AA +AB +AA +AB
= (A + A)(A + B)
= 1.(A + B)
=A + B
Rule 12: (A + B)(A + C) = A + BC
solution: here,
= AA + AC + AB + BC
= A + AC + AB + BC
= A( 1 + C)+ AB + BC
= A.1 + AB + BC
= A(1 + B)+ BC
= A.1 + BC
=A + BC
Boolean Functions
In Boolean algebra, we deal with various logic operations and binary variables. Here, we make use of an algebraic expression known as the Boolean Expression to describe the Boolean Function. The Boolean Expression contains the logic operation symbols, binary variables, and the constants 1 and 0.
i) Variables: These are the input values of a Boolean function. In Boolean algebra, variables typically represent binary values and are often denoted by letters such as 𝐴A, 𝐵B, 𝐶C, etc.
ii) Prime Implicant: A prime implicant is a product term that, when combined with others, covers a min-term in a truth table representing a Boolean function. It’s said to be prime if removing any variable from it would result in a term that does not cover any min-term.
iii) Essential Prime Implicant: A prime implicant that covers at least one min-term not covered by any other prime implicant is called an essential prime implicant. They are crucial for determining a minimal sum-of-products (SOP) or product-of-sums (POS) representation of a Boolean function.
iv) Literal: A literal is a variable or its complement (NOT) within a Boolean expression
v) Product Terms: These are terms in a Boolean expression that represent the ANDing of literals.
vi) Min-terms: In a truth table, each row where the output of a Boolean function is 1 is called a min-term. Min-terms are represented using the variables in their true or complemented form.
vii) Max-terms: Conversely, a max-term is a term that represents the logical OR of literals. In a truth table, each row where the output of a Boolean function is 0 is called a max-term. Max-terms are represented using the variables in their true or complemented form.
Canonical and Standard Form
Canonical Form: In Boolean algebra, the Boolean function can be expressed as Canonical Disjunctive Normal Form known as min-term and some are expressed as Canonical Conjunctive Normal Form known as max-term.
In Min-term, we look for the functions where the output results in “1” while in Max-term we look for functions where the output results in “0”.
We perform the Sum of min-term also known as the Sum of products (SOP).
We perform Product of Max-term also known as Product of sum (POS).
Boolean functions expressed as a sum of min-terms or product of max-terms are said to be in canonical form.
Standard Form: A Boolean variable can be expressed in either true or complementary forms. In standard form Boolean function will contain all the variables in either true form or complemented form while in canonical number of variables depends on the output of SOP (Sum of product) or POS(Product of Sum) .
Sum of Product (SOP) Form
The sum-of-products (SOP) form is a method (or form) of simplifying the Boolean expressions of logic gates. In this SOP form of Boolean function representation, the variables are operated by AND (product) to form a product term and all these product terms are ORed (summed or added) together to get the final function. A sum-of-products form can be formed by adding (or summing) two or more product terms using a Boolean addition operation. Here the product terms are defined by using the AND operation and the sum term is defined by using OR operation. The sum-of-products form is also called as Disjunctive Normal Form as the product terms are ORed together and Disjunction operation is logical OR. Sum-of-products form is also called as Standard SOP. SOP form representation is most suitable to use them in FPGA (Field Programmable Gate Arrays).
In SOP Form: A=1, A’=0. SOP form is denoted by Σ.
SOP form can be obtained by
i) Writing an AND term for each input combination, which produces HIGH output.
ii) Writing the input variables if the value is 1, and write the complement of the variable if its value is 0.
iii) OR the AND terms to obtain the output function.
Example: Boolean expression for majority function F = A’BC + AB’C + ABC’+ ABC
Product of Sums (POS) Form
The product of sums form is a method (or form) of simplifying the Boolean expressions of logic gates. In this POS form, all the variables are ORed, i.e. written as sums to form sum terms. All these sum terms are ANDed (multiplied) together to get the product-of-sum form. This form is exactly opposite to the SOP form. So this can also be said as “Dual of SOP form”. Here the sum terms are defined by using the OR operation and the product term is defined by using AND operation. When two or more sum terms are multiplied by a Boolean OR operation, the resultant output expression will be in the form of product-of-sums form or POS form. The product-of-sums form is also called as Conjunctive Normal Form as the sum terms are ANDed together and Conjunction operation is logical AND. Product-of-sums form is also called as Standard POS.
In POS form: A=0, A’=1. It is denoted by pie (π)
POS form can be obtained by
i) Writing an OR term for each input combination, which produces LOW output.
ii) Writing the input variables if the value is 0, and write the complement of the variable if its value is 1.
iii) AND the OR terms to obtain the output function.
Example: Boolean expression for majority function F = (A + B + C) (A + B + C ‘) (A + B’ + C) (A’ + B + C)
K-map(Karnaugh-Map)
The K-map is a systematic way of simplifying Boolean expressions. With the help of the K-map method, we can find the simplest POS and SOP expression, which is known as the minimum expression. The K-map provides a cookbook for simplification. Just like the truth table, a K-map contains all the possible values of input variables and their corresponding output values. However, in K-map, the values are stored in cells of the array. In each cell, a binary value of each input variable is stored. The K-map method is used for expressions containing 2, 3, 4, and 5 variables. The K-map takes the SOP and POS forms. The K-map grid is filled using 0’s and 1’s. The K-map is solved by making groups.
There are the following steps used to solve the expressions using K-map:
i) First, we find the K-map as per the number of variables.
ii) Find the max-term and min-term in the given expression.
iii) Fill cells of K-map for SOP with 1 respective to the min-terms.
iv) Fill cells of the block for POS with 0 respective to the max-term.
v) Next, we create rectangular groups that contain total terms in the power of two like 2, 4, 8, … and try to cover as
many elements as we can in one group.
vi) With the help of these groups, we find the product terms and sum them up for the SOP form.
K-map is a graphical representation of truth-table of given expression.
Types of K-map
i) 2 Variable K-map
There is a total of 4 variables in a 2-variable K-map. There are two variables in the 2-variable K-map. The following figure shows the structure of the 2-variable K-map:
- ii) 3 Variable K-map
3-variable K-map is represented as an array of eight cells. In this case, we used A, B, and C for the variable. We can use any letter for the names of the variables. The binary values of variables C and B are along the right side, and the value of ‘A’ is at the left side. The value of the given cell is the binary values of C and B at right side in the same row combined with the value of A at the left side in the same column. For example, the cell in the upper left corner has a binary value of 000, and the cell in the lower right corner has a binary value of 101.
iii) The 4-Variable K-Map
The 4-variable K-map is represented as an array of 16 cells. Binary values of A and B are along the left side, and the values of C and D are across the top. The value of the given cell is the binary values of A and B at left side in the same row combined with the binary values of C and D at the top in the same column. For example, the cell in the upper right corner has a binary value of 0010, and the cell in the lower right corner has a binary value of 1010.
Terms of K-map
Pair: If there are 2 ones in the k map then it is called as pair.
Example:
Quads: Quads are groups of four adjacent cells (2×2) in a K-map. These cells can be arranged horizontally or vertically, forming a square. Quads are useful for identifying adjacent terms that can be combined to simplify the Boolean expression.
Example:
Octets: Octets are groups of eight adjacent cells (4×2 or 2×4) in a K-map. These cells can be arranged horizontally, vertically, or in a rectangular shape. Octets are larger groups than quads and are used to identify larger patterns for simplification.
Example:
Plotting On K-map
i) In SOP Form
1) Place 1 In each cell corresponding to a term (min-term) in SOP expression
2) Remaining cells are filled with 0 or left empty
3) In SOP Form: A=1, A’=0
Example:
ii) In POS Form
1) Place 0 in each cell corresponding to a term (max-term) in POS expression
2) Remaining cells are filled with 1 or left empty
3) In POS Form: A=0, A’=1
Example: