Boolean Algebra Full With Solved Examples.

 

Boolean algebra is the category of algebra in which the variable’s values are the truth values, true and false, ordinarily denoted 1 and 0 respectively. 

It is used to analyze and simplify digital circuits or digital gates. 

It is also called Binary Algebra or logical Algebra. 

It has been fundamental in the development of digital electronics and is provided for in all modern programming languages. It is also used in set theory and statistics.

The important operations performed in Boolean algebra are – conjunction (∧), disjunction (∨) and negation (¬). 

Hence, this algebra is far way different from elementary algebra where the values of variables are numerical and arithmetic operations like addition, subtraction is been performed on them.

Table of contents:

• Operations
• Terminologies
• Truth Table
• Rules
• Laws
• Theorems
• Solved Examples

Boolean Algebra Operations

The basic operations of Boolean algebra are as follows:

• Conjunction or AND operation
• Disjunction or OR operation
• Negation or Not operation

 

Below is the table defining the symbols for all three basic operations.

Operator	Symbol	Precedence
NOT	‘ (or) ¬	Highest
AND	. (or) ∧	Middle
OR	+ (or) ∨	Lowest

Suppose A and B are two Boolean variables, then we can define the three operations as;

• A conjunction B or A AND B, satisfies A ∧ B = True, if A = B = True or else A ∧ B = False.
• A disjunction B or A OR B, satisfies A ∨ B = False, if A = B = False, else A ∨ B = True.
• Negation A or ¬A satisfies ¬A = False, if A = True and ¬A = True if A = False

Boolean Expression

A logical statement that results in a Boolean value, either be True or False, is a Boolean expression. Sometimes, synonyms are used to express the statement such as ‘Yes’ for ‘True’ and ‘No’ for ‘False’. Also, 1 and 0 are used for digital circuits for True and False, respectively.

Boolean expressions are the statements that use logical operators, i.e., AND, OR, XOR and NOT. Thus, if we write X AND Y = True, then it is a Boolean expression.

Boolean Algebra Terminologies

Now, let us discuss the important terminologies covered in Boolean algebra.

Boolean Algebra: Boolean algebra is the branch of algebra that deals with logical operations and binary variables.

Boolean Variables: A Boolean variable is defined as a variable or a symbol defined as a variable or a symbol, generally an alphabet that represents the logical quantities such as 0 or 1.

Boolean Function: A Boolean function consists of binary variables, logical operators, constants such as 0 and 1, equal to the operator, and the parenthesis symbols.

Literal: A literal may be a variable or a complement of a variable.

Complement: The complement is defined as the inverse of a variable, which is represented by a bar over the variable.

Truth Table: The truth table is a table that gives all the possible values of logical variables and the combination of the variables. It is possible to convert the Boolean equation into a truth table. The number of rows in the truth table should be equal to 2n, where “n” is the number of variables in the equation. For example, if a Boolean equation consists of 3 variables, then the number of rows in the truth table is 8. (i.e.,) 23 = 8.

Boolean Algebra Truth Table

Now, if we express the above operations in a truth table, we get;

A	B	A ∧ B	A ∨ B
True	True	True	True
True	False	False	True
False	True	False	True
False	False	False	False

A	¬A
True	False
False	True

Boolean Algebra Rules

Following are the important rules used in Boolean algebra.

• Variable used can have only two values. Binary 1 for HIGH and Binary 0 for LOW.
• The complement of a variable is represented by an overbar.
• OR-ing of the variables is represented by a plus (+) sign between them. For example, the OR-ing of A, B, and C is represented as A + B + C.
• Logical AND-ing of the two or more variables is represented by writing a dot between them, such as A.B.C. Sometimes, the dot may be omitted like ABC.

Laws of Boolean Algebra

There are six types of Boolean algebra laws. They are:

• Commutative law
• Associative law
• Distributive law
• AND law
• OR law
• Inversion law

Those six laws are explained in detail here.

Commutative Law

Any binary operation which satisfies the following expression is referred to as a commutative operation. Commutative law states that changing the sequence of the variables does not have any effect on the output of a logic circuit.

• A. B = B. A
• A + B = B + A

Associative Law

It states that the order in which the logic operations are performed is irrelevant as their effect is the same.

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

Distributive Law

Distributive law states the following conditions:

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

AND Law

These laws use the AND operation. Therefore they are called AND laws.

• A .0 = 0
• A . 1 = A
• A. A = A
• $\begin{array}{l}�.\overline{�}=0\end{array}$

OR Law

These laws use the OR operation. Therefore they are called OR laws.

• A  + 0 = A
• A + 1 = 1
• A + A = A

Inversion Law

In Boolean algebra, the inversion law states that double inversion of variable results in the original variable itself.

• 
  $\begin{array}{l}\overline{\overline{�}}=�\end{array}$

Boolean Algebra Theorems

The two important theorems which are extremely used in Boolean algebra are De Morgan’s First law and De Morgan’s second law. These two theorems are used to change the Boolean expression. This theorem basically helps to reduce the given Boolean expression in the simplified form. These two De Morgan’s laws are used to change the expression from one form to another form. Now, let us discuss these two theorems in detail.

De Morgan’s First Law:

De Morgan’s First Law states that  (A.B)’ = A’+B’.

The first law states that the complement of the product of the variables is equal to the sum of their individual complements of a variable.

The truth table that shows the verification of De Morgan’s First law is given as follows:

A	B	A’	B’	(A.B)’	A’+B’
0	0	1	1	1	1
0	1	1	0	1	1
1	0	0	1	1	1
1	1	0	0	0	0

The last two columns show that (A.B)’ = A’+B’.

Hence, De Morgan’s First Law is proved.

De Morgan’s Second Law:

De Morgan’s Second law states that (A+B)’ = A’. B’.

The second law states that the complement of the sum of variables is equal to the product of their individual complements of a variable.

The following truth table shows the proof for De Morgan’s second law.

A	B	A’	B’	(A+B)’	A’. B’
0	0	1	1	1	1
0	1	1	0	0	0
1	0	0	1	0	0
1	1	0	0	0	0

The last two columns show that (A+B)’ = A’. B’.

Hence, De Morgan’s second law is proved.

 The other theorems in Boolean algebra are complementary theorem, duality theorem, transposition theorem, redundancy theorem and so on. All these theorems are used to simplify the given Boolean expression. The reduced Boolean expression should be equivalent to the given Boolean expression.

Solved Examples

Question: Simplify the following expression: 

$\begin{array}{l}�+\overline{��}\end{array}$

Solution:

Given: 

$\begin{array}{l}�+\overline{��}\end{array}$

According to Demorgan’s law, we can write the above expressions as

$\begin{array}{l}�+(\overline{�}+\overline{�})\end{array}$

From Commutative law:

$\begin{array}{l}(�+\overline{�})+\overline{�}\end{array}$

From Complement law

$\begin{array}{l}1+\overline{�}=1\end{array}$

Therefore, 

$\begin{array}{l}�+\overline{��}=1\end{array}$

Question 2: Draw a truth table for A(B+D).

Solution: Given expression A(B+D).

A	B	D	B+D	A(B+D)
0	0	0	0	0
0	0	1	1	0
0	1	0	1	0
0	1	1	1	0
1	0	0	0	0
1	0	1	1	1
1	1	0	1	1
1	1	1	1	1

Boolean Algebra Questions with Solutions

1. Define Boolean expression.

Answer:

The result of a Boolean expression is always a Boolean value. A Boolean expression is made up of the Boolean constants, logical connectives and Boolean variables and logical connectives. A Boolean function is represented by each Boolean expression. The Boolean expression XY′Z is an example.

2. What is meant by isomorphic Boolean algebra?

Answer:

Isomorphic Boolean algebras B and B1 are those that have a one-to-one correspondence f: B ⟶B1 that retains the three operations +,*, and ‘ for all elements x, y in B,

• f (x+y)=f(x)+f(y)
• f (x*y)=f(x)*f(y) and
• f(x’)=f(x)’

3. Define Boolean function.

Answer:

A Boolean function is a type of mathematical function with the formula f:Xn→X of degree n, where ‘n’ is a non-negative integer, and X = {0,1} is a Boolean domain. It explains how Boolean input generates Boolean output.

Let F(X, Y)=X′Y′ as an example. This is a degree 2 function from the collection of ordered pairs (two numbers) of Boolean variables to set 0,1 with F(0, 1)=0, F(0,0) = 1, F(1,1)=0, and F(1,0) = 0.

Boolean Identities

Double Complement Law ∼(∼X) = X Complement Law X+∼X = 1 (OR Form) X.∼X = 0 (AND Form) Idempotent Law X+X = X (OR Form) X.X = X (AND Form) Identity Law X+0 = X (OR Form) X.1 = X (AND Form) Dominance Law X+1 = 1 (OR Form) X.0 = 0 (AND Form) Commutative Law X+Y = Y+X (OR Form) X.Y = Y.X (AND Form) Associative Law X+(Y+Z) = (X+Y)+Z (OR Form) X.(Y.Z) = (X.Y).Z (AND Form) Absorption Law X.(X+Y) = X X+(X.Y) = X Simplification Law X.(∼X+Y) = X.Y X+(∼X.Y) = X+Y Distributive Law X+(Y.Z) = (X+Y).(X+Z) X.(Y+Z) = (X.Y)+(X.Z) De-Morgan’s Law ∼(X.Y)=∼X+∼Y ∼(X+Y)=∼X.∼Y

4. Using Boolean identities, reduce the given Boolean expression:

F(X, Y, Z) = X′Y + YZ′ + YZ + XY′Z′

Solution:

Given,F(X, Y, Z) = X′Y + YZ′ + YZ + XY′Z′

Using the idempotent law, we can write YZ’ = YZ’ + YZ’

⇒ F(X, Y, Z) = X′Y+(YZ′+YZ′)+YZ + XY′Z′

Now, interchange the second and third term, we get

⇒ F(X, Y, Z) = X′Y+(YZ′+YZ)+(YZ′+XY′Z′)

By using distributive law,

⇒ F(X, Y, Z) = X′Y+Y(Z′+Z)+Z′(Y+XY′)

Using Z’ + Z = 1 and absorption law (Y + XY’)= (Y + X),

⇒ F(X, Y, Z) = X′Y+Y.1+Z′(Y+X)

⇒ F(X, Y, Z) = X′Y+Y+Z′(Y+X) [Since Y.1 = Y ]

⇒ F(X, Y, Z) = Y(X′+1)+Z′(Y+X)

⇒ F(X, Y, Z) = Y.1+Z′(Y+X) [ As (X’ + 1) = 1 ]

⇒ F(X, Y, Z) = Y +Z′(Y+X) [ As, Y.1 = Y ]

⇒ F(X, Y, Z) = Y+YZ’+XZ’

⇒ F(X, Y, Z) = Y(1+Z′)+XZ′

⇒ F(X, Y, Z) = Y.1+XZ′ [Since (1 + Z’) = 1]

⇒ F(X, Y, Z) = Y+XZ′ [Since Y.1 = Y]

Hence, the simplified form of the given Boolean expression is F(X, Y, Z) = Y+XZ′.

5. Reduce the following Boolean expression: F(P ,Q, R)=(P+Q)(P+R)

Solution:

Given, F(P ,Q, R)=(P+Q)(P+R)

Using distributive law,

⇒ F(P, Q, R) = P.P + P.R +Q.P + Q.R

Using Idempotent law,

⇒ F(P, Q, R) = P + P.R +Q.P + Q.R

Again using distributive law, we get

⇒ F(P, Q, R) = P(1+R) + Q.P + Q.R

Using dominance law, we can write

⇒ F(P, Q, R) = P + Q.P + Q.R

Again using distributive law, we get

⇒ F(P, Q, R) = (P+1).P+ Q.R

Therefore, using dominance law, we can get the reduced form as follows:

⇒ F(P, Q, R) = 1.P+Q.R

⇒ F(P, Q, R) = P+Q.R

Hence, the reduced form of F(P, Q, R) = (P+Q)(P+R) is F(P, Q, R) = P+Q.R.

 

6. What is the equivalent expression for the Boolean expression x’y’z +yz+ xz?

Solution:

Answer: z

Given Boolean expression: x’y’z +yz+ xz

x’y’z +yz+ xz = z(x’y’+y+x)

Now, apply distributive law for the first two terms inside the bracket.

x’y’z +yz+ xz = z[(x’+y) (y+y’)+ x]

x’y’z +yz+ xz = z [(x’ + y) . 1 + x] [Since A+A’ = 1]

x’y’z +yz+ xz = z [x’ + y + x]

Further x+x’ = 1

So, x’y’z +yz+ xz = z(1+y)

Now, using null law, 1+y = 1

x’y’z +yz+ xz = z.1

Now, using identity law, A.1 = A

Therefore, x’y’z +yz+ xz = z.

Hence, the Boolean expression equivalent to x’y’z +yz+ xz is z.

7. What is the simplified sum of product form for the Boolean expression:

(A + B’ + C’)(A + B’ + C)(A + B + C’)

Solution:

Given Boolean expression: (A + B’ + C’)(A + B’ + C)(A + B + C’)

Now, using the distributive law, we can write

(A + B’ + C’)(A + B’ + C)(A + B + C’) = [(A+B’) + C’C](A + B + C’)

Using AA’ = 0, it becomes

(A + B’ + C’)(A + B’ + C)(A + B + C’) = [(A+B’) + 0](A + B + C’)

Since A + 0 = A,

(A + B’ + C’)(A + B’ + C)(A + B + C’) = (A+B’)(A + B + C’)

(A + B’ + C’)(A + B’ + C)(A + B + C’) = A + B’.(B+C’)

Again, using distributive law

(A + B’ + C’)(A + B’ + C)(A + B + C’) = A + B’B +B’C’

(A + B’ + C’)(A + B’ + C)(A + B + C’) = A + 0 + B’C’

(A + B’ + C’)(A + B’ + C)(A + B + C’) = A + B’C’.

8. Write the reduced form for the Boolean expression (AB’(C+BD) + A’B’)C.

Solution:

Given expression: (AB’(C+BD) + A’B’)C

Using distributive law, we can write;

(AB’(C+BD) + A’B’)C = (AB’C + AB’BD +A’B’) C

Since, BB’ = 0

(AB’(C+BD) + A’B’)C = (AB’C + 0 + A’B’)C

(AB’(C+BD) + A’B’)C = (AB’C + A’B’)C

(AB’(C+BD) + A’B’)C = AB’C + A’B’C

Now, take B’C as common,

(AB’(C+BD) + A’B’)C = B’C (A + A’)

(AB’(C+BD) + A’B’)C = B’C (1)

(AB’(C+BD) + A’B’)C = B’C.

Hence, the reduced form of (AB’(C+BD) + A’B’)C is B’C.

9. Reduce the Boolean expression: A = XY + X(Y+Z) + Y(Y+Z)

Solution:

Given: A = XY + X(Y+Z) + Y(Y+Z)

The given Boolean expression can be written as follows:

A = XY + XY + XZ + YY + YZ

Using Idempotent law, Y.Y = Y

Thus, A = XY + XY + XZ + Y + YZ

Again, XY + XY = XY, we get

A = XY + XZ + Y + YZ

A = XY + XZ + Y(1+Z)

Using null law, (i.e., 1+A = 1), we can write

A = XY + XZ + Y.1

Using Identity law, 1.Y = Y.

So, A = XY + XZ + Y

Now, the above form can be written as:

A = Y(1+X) + XZ

A = Y.1 + XZ

A = Y + XZ

Hence, the reduced form of the Boolean expression A = XY + X(Y+Z) + Y(Y+Z) is A = Y+XZ.

10. Check whether AC + ABC = AC is true or false?

Solution:

Given Boolean expression: AC + ABC = AC

AC (1+B) = AC

Now, using the null law 1+B = 1, the above expression can be written as:

AC.1 = AC

Thus, using the identity law, 1.A = A, the above expression becomes:

AC = AC

Hence, AC + ABC = AC is true.

MaxMalick