Boolean Algebra | Analog and Digital Electronics - Electrical Engineering (EE) PDF Download

Boolean Algebra

 Digital Electronics Module 2.1 showed that the operation of a single gate could be described by using a Boolean expression. For example the operation of a single AND gate with inputs A and B and an output X can be expressed as:

                                                                    X = A•B

Note:

The symbol • represents a logical AND, but because the use of special symbols can be inconvenient in printed material, the AND symbol is often omitted, as in AB or separated by a full stop as in A.B as used to indicate multiplication in standard algebra. The multiplication symbols x and * can also be seen in some texts, because the logical AND is similar to binary multiplication, (but not the same when numbers having more than one-bit are used).Module 2.2 showed the relationship between a truth table that describes the operation of a circuit, and a Boolean equation that describes the logic of the circuit.

A combinational logic circuit such as that shown in Fig 2.3.1 (a repeat of Fig 2.2.2) is described by a Boolean equation as:

                                                     X = (A•B) + (A•C) + (A•B•C)

Boolean Algebra | Analog and Digital Electronics - Electrical Engineering (EE)

 

This could also be written (less clearly) as "The output X will be 1 when A and B or A and C or A and B and C are 1, otherwise X will be 0".

However Module 2.2 also showed that although a Boolean equation may give an accurate description of a logic process described by a truth table, it might require simplification before being interpreted as an actual circuit. The circuit shown in Fig 2.3.1 was simplified in Module 2.2 by closely examining a truth table to find redundant gates. However, with anything but the simplest circuits this can be tedious and it is easy to make mistakes.

This module therefore describes methods for simplifying Boolean equations directly, using Boolean algebra, rather than by the use of truth tables.

 

 

Circuit Simplification Using Boolean Algebra

The algebraic method used to simplify digital circuits applies a number of Boolean laws to successively simplify complex equations. Selected laws and rules are applied, step by step, to the original equation, so as to eventually arrive at a simplified version that can be implemented with a smaller number of gates and therefore lead to a simpler circuit.

Boolean Laws

The laws of Boolean algebra are similar in some ways to those of standard algebra, but in some cases Boolean laws are unique. This is because when logic is applied to digital circuits, any variable such as A can only have two values 1 or 0, whereas in standard algebra A can have many values.

Commutative Laws

In a group of variables connected by operators AND or OR, the order of the variables does not matter.

1a. Boolean addition (OR): A+B = B+A

1b. Boolean multiplication (AND): A•B = B•A
 

Associative Laws

The order of calculation can be changed without affecting the result (Change which terms are in brackets, or remove brackets). Note: This is only OK so long as all signs (+ or •) are the same.

2a. Boolean addition (OR): (A+B)+C = A+(B+C) = A+B+C

2b. Boolean Multiplication (AND): (A•B)•C = A•(B•C) = A•B•C = ABC
 

Distributive Laws

The same answer is arrived at when multiplying (ANDing) a variable by a group of bracketed variables added (ORed) together, as when each multiplication (AND) is performed separately.

Law 3a is similar to factoring in normal algebra, but law 3b is unique to Boolean algebra because unlike normal algebra, where A x A=A2, in Boolean algebra A•A = A

3a. A•(B+C) = A•B+A•C

3b. A+(B•C) = (A+B) • (A+C)
 

Identity Elements

In rule 4a, when the variable A is ANDed with logic 1 (called the Identity Element for the AND operator). The variable ANDed with 1 retains its identity.

Rule 4b, shows that the Identity Element for the OR operator is 0, and any variable (e.g. A) ORed with 0 it retains its identity.

4a. A•1 = A

4b. A+0 = A                                        

                                          Boolean Algebra | Analog and Digital Electronics - Electrical Engineering (EE)            

5a and 5b show how by ‘forcing the Identity Element’, (in B column of the truth tables) to the opposite states to those used in 4a and 4b, produces an output that is the same as the Identity Element.

5a. A•0 = 0

5b. A+1 = 1

                              Boolean Algebra | Analog and Digital Electronics - Electrical Engineering (EE)

6a and 6b show that ANDing or ORing two identical variables, produces an output equal to a single variable, showing that one of the variables is redundant, a useful rule when simplifying Boolean equations.

6a. A•A = A

6b. A+A = A

                                      Boolean Algebra | Analog and Digital Electronics - Electrical Engineering (EE)

Complement Law

7a. A + A = 1 Any variable ORed with its inverse is 1

7b. A • A = 0 Any variable ANDed with its inverse is 0

Boolean Algebra | Analog and Digital Electronics - Electrical Engineering (EE)

Reduction

8a. When a single variable (A) is ANDed with itself OR a second variable (A+B), the result is equal to the single variable.

8a A•(A+B) = A

                                            Boolean Algebra | Analog and Digital Electronics - Electrical Engineering (EE)

 

8b. When a single variable (A) is ORed with itself AND a second variable (A•B), the result is equal to the single variable.

8b A+(A•B) = A  

                                            Boolean Algebra | Analog and Digital Electronics - Electrical Engineering (EE)

8c. When a single variable (A) is ORed with itself OR a second variable (A+B), the single variable disappears.

8c A+(A+B) = (A+B)

                                          Boolean Algebra | Analog and Digital Electronics - Electrical Engineering (EE)

8d. When a single variable (A) is ANDed with itself AND a second variable (A•B), the single variable disappears.

8d A•(A•B) = (A•B)

                                       Boolean Algebra | Analog and Digital Electronics - Electrical Engineering (EE)

 

 

Duality Rules

Boolean Algebra | Analog and Digital Electronics - Electrical Engineering (EE)

It is possible to derive additional identities by obtaining the Dual of an identity. This involves changing the AND operators to OR and the OR operators to AND. Additionally any 0s are changed to 1s and 1s to 0s as shown in Table 2.3.2.

The duality rule can be used to change a logic expression containing both AND and OR elements to its equivalent dual expression.

Table 2.3.3 shows that A•(B+C) is the same as A+(B•C).

 

 

Boolean Algebra | Analog and Digital Electronics - Electrical Engineering (EE)

Simplifying Boolean Equations

Minimising complex Boolean expressions to their simplest form using Boolean laws and rules is a matter of choosing the most appropriate law or rule to reduce the expression step by step. If the resulting minimisation is correct, the minimised equation and the original equation should give identical output columns when truth tables for the original and minimised circuits are compared.

These Boolean algebraic methods would normally be used on logic circuits with just a few gates and only two or three inputs, as this method of simplification becomes more difficult and cumbersome to use when more gates or inputs are involved.

Which laws are applied to change an equation, and in what order is a matter of practice and intuition. This method involves looking at the original complex equation and selecting a law that will simplify a particular part, so obtaining a simpler equation, and then choosing another law that will simplify the equation further, and so on until the equation can no longer be made simpler.

There is no simple algorithm to specify the order of steps to be taken and several routes may be taken to reach the goal of a simplified and ideally minimised circuit.

Whether the result is also the minimum possible circuit can only be judged by looking for any possible further reduction using the Boolean laws.

In practice, small circuits with just two or three inputs can very often be simplified just by looking at the truth table and picking out any redundant logic combinations, as shown in Table 2.2.2 in Module 2.2 (Combinational Logic), but Boolean simplification is useful for more complex circuits.

 

Boolean Simplification Examples

Example 1

Suppose the cash room at a store has access restricted to certain employees, each of whom has a key, which produces a logic 1 at particular inputs to an unlocking circuit.

                                                                                               Boolean Algebra | Analog and Digital Electronics - Electrical Engineering (EE)

Only the store manager (M) can enter alone. The assistant manager (A) and the cashier (C) also have access, but only when accompanied by each other, or by the store manager. Design a combinational logic circuit that will allow access by producing a logic 1 when the above conditions are met.

Truth table

The conditions requiring a logic 1 output can be arranged as a truth table (Table 2.3.4) and Boolean expressions can be derived from the truth table for each input combination that produces a logic 1 output.

The five Boolean expressions can be separated by OR operators to form a complete Boolean equation.

                             X = M + M•C + A•C + A•M + A•C•M

 

 

This suggests a circuit like that shown in Fig. 2.3.2, which would require four I.Cs:

1x 74HCT08   2 input AND (containing 4 gates).

1x 74HCT10   3 input AND (containing 3 gates).

1x 74HCT32   2 input OR (containing 4 gates).

1x 74HCT4075   3 input OR (containing 3 gates).

However, by choosing appropriate laws and rules from those listed above, the circuit can be considerably simplified.

                      Boolean Algebra | Analog and Digital Electronics - Electrical Engineering (EE)

 

                    Starting with the equation derived from Table 2.3.4:

 

X = M + M•C + A•C + A•M + A•C•M

Since M + M•C = M (Reduction rule 8b)

X = M + A•C + A•M + A•C•M

And as M + A•C + A•M = M + A•M + A•C (Commutative Law 1a)

X = M + A•M + A•C + A•C•M

And as M + A•M = M (Reduction rule 8b)

X = M + A•C + A•C•M

And as M + A•C + A•C•M = M + A•C•M + A•C (Commutative Law 1a)

X = M + A•C•M + A•C

And as M + A•C•M = (Reduction rule 8b)

X = M + A•C

          Boolean Algebra | Analog and Digital Electronics - Electrical Engineering (EE)

                             Boolean Algebra | Analog and Digital Electronics - Electrical Engineering (EE)

No further reduction possible.

The simplified circuit is shown in Fig 2.3.3, which provides exactly the same function as Fig. 2.3.2. This can be confirmed by comparing the simplified equation X = M + A•C with the original column X in Table 2.3.5.

 

The simplified circuit in Fig 2.3.3 still requires two I.Cs, (AND and OR) and it now only uses one gate per chip. Unless the spare gates are to be used elsewhere in another part of the circuit, this is still wasteful.

 

Fig. 2.3.4 NAND only Cash Room Access Circuit

A better option could be to replace the AND and OR functions with universal gates such as NOR or NAND. A ‘NAND only’ version of the simplified circuit is shown in Fig. 2.3.4. This version uses three gates instead of two, but all the gates are the same and can be accommodated within a single 7400 IC. The original circuit has therefore now been reduced from four ICs to one.

 

              Boolean Algebra | Analog and Digital Electronics - Electrical Engineering (EE)

Boolean Algebra | Analog and Digital Electronics - Electrical Engineering (EE)

Operation

NAND 1 has both its inputs connected together, which converts it to an inverter or NOT gate and therefore produces Mat its output. NAND 2 works as an AND gate with its output inverted and so produces an output of A•C. The Boolean expression for the circuit using NAND gates now becomes:

X = M + A•C

This is because of the application of another very useful Boolean algebra law, De Morgan’s Theorem. Before looking at how the theorem works, note the difference in the use of the inversion bars in Boolean expressions. This is an important feature in the application of De Morgan’s Theorem:

A broken bar A•B indicates that the inputs (to an AND gate for example) are inverted, whilst an unbroken bar A•B indicates an inverted output.

De Morgan’s Theorem

Augustus De Morgan formulated an extension to George Boole’s Algebraic logic that has become very important in digital logic. Not only is it used in the simplification of Boolean expressions but can also be used to change the function of logic gates, so that NAND gates (or NOR gates) can carry out any of the other standard logic functions of gates. The theorem comprises two laws that describe how inverting the inputs to a gate, changes the gate’s function.

Law 1.

A + B = A • B Inverting the inputs to an OR gate changes its function to NAND.

Law 2.

A • B = A + B Inverting the inputs to an AND gate changes its function to NOR

Considering these two equalities the other way round, A + B = A • B De Morgan’s Theorem is often described as "Break the bar and change the sign." Meaning that by placing, or removing the bar above the AND or OR operator (• or +) the operator is inverted. Therefore the complement of the AND function is OR.

 

Boolean Algebra | Analog and Digital Electronics - Electrical Engineering (EE)

 

Boolean Algebra | Analog and Digital Electronics - Electrical Engineering (EE)

 

Applying De Morgan’s Theorem

These equalities, generally called De Morgan’s Laws 1 and 2 are illustrated in Fig. 2.3.5 and Fig. 2.3.6 as they apply to AND, NOR, NAND and OR gates. Note however, that when De Morgan’s theorem is applied to the XOR and XNOR gates there is no change in the gate’s function.

The usefulness of De Morgan’s theorem when applied to circuits can be seen by comparing Fig. 2.3.3 and Fig. 2.3.4 where it was instrumental in changing the functions of the AND and OR gates in Fig.2.3.3 to all NAND gates in Fig. 2.3.4, so the circuit can be made using one IC instead of two.

Inverting the Inputs

In Fig. 2.3.4 an additional gate NAND 1 appears in the circuit, and has its two inputs connected together to act as a NOT gate (check this by looking at the truth table for a NAND gate in Fig. 2.3.5), when both inputs are the same (row 1 and row 4) the output (X) is an inverted version of the inputs (A•B).

This additional gate in Fig. 2.3.4 provides M at the top input to NAND 3 instead of the M applied to the top input of the OR gate in Fig 2.3.3.

NAND 2 in Fig. 2.3.4 replaces the AND gate in Fig 2.3.3 so that the bottom input to NAND 3 is now A•C instead of A•C.

Therefore inputs to NAND 3 are now M and M•C. Therefore both inputs to NAND 3 have been inverted (without actually using any NOT gates) to make NAND 3 act, according to De Morgan’s theorem, as an OR function, so giving the correct output of X = M + A•C.

Summary

Boolean algebra gives a more compact way to describe a combinational logic circuit than truth tables alone. It can also be used for simplification of circuits, however this can also be cumbersome and error prone. When circuits with more than two or three inputs are involved a better method of circuit reduction that works well with circuits having up to four or six inputs is the Karnaugh Map

The document Boolean Algebra | Analog and Digital Electronics - Electrical Engineering (EE) is a part of the Electrical Engineering (EE) Course Analog and Digital Electronics.
All you need of Electrical Engineering (EE) at this link: Electrical Engineering (EE)
137 videos|143 docs|71 tests

Top Courses for Electrical Engineering (EE)

FAQs on Boolean Algebra - Analog and Digital Electronics - Electrical Engineering (EE)

1. What is Boolean algebra?
Ans. Boolean algebra is a mathematical structure that deals with binary variables and logical operations. It provides a systematic way to analyze and simplify logical expressions using only two values, true and false, represented by 1 and 0, respectively.
2. How is Boolean algebra used in digital electronics?
Ans. Boolean algebra plays a crucial role in digital electronics as it provides a foundation for designing and analyzing digital circuits. It helps in simplifying complex logic expressions and determining the behavior of logic gates and logic circuits.
3. What are the basic operations in Boolean algebra?
Ans. The basic operations in Boolean algebra are AND, OR, and NOT. The AND operation returns true if all the inputs are true, the OR operation returns true if at least one input is true, and the NOT operation negates the input, returning the opposite value.
4. Can Boolean algebra be applied to real-life situations?
Ans. Yes, Boolean algebra can be applied to real-life situations beyond digital electronics. It can be used in various fields like computer science, telecommunications, database systems, and even in everyday decision-making scenarios where logical conditions need to be evaluated.
5. How does Boolean algebra relate to propositional logic?
Ans. Boolean algebra is closely related to propositional logic, which deals with the study of logical propositions and their truth values. Boolean algebra provides a systematic way to manipulate and simplify propositional logic expressions, making it easier to analyze and reason about logical statements.
137 videos|143 docs|71 tests
Download as PDF
Explore Courses for Electrical Engineering (EE) exam

Top Courses for Electrical Engineering (EE)

Signup for Free!
Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
10M+ students study on EduRev
Related Searches

pdf

,

Semester Notes

,

shortcuts and tricks

,

Boolean Algebra | Analog and Digital Electronics - Electrical Engineering (EE)

,

past year papers

,

MCQs

,

Viva Questions

,

Important questions

,

mock tests for examination

,

Sample Paper

,

Boolean Algebra | Analog and Digital Electronics - Electrical Engineering (EE)

,

Extra Questions

,

practice quizzes

,

Boolean Algebra | Analog and Digital Electronics - Electrical Engineering (EE)

,

Previous Year Questions with Solutions

,

Exam

,

ppt

,

video lectures

,

Summary

,

Objective type Questions

,

Free

,

study material

;