Boolean Algebra

Boolean Algebra is an algebra, which deals with binary numbers & binary variables. Hence, it is also called as Binary Algebra or logical Algebra. A mathematician, named George Boole had developed this algebra in 1854. The variables used in this algebra are also called as Boolean variables.
The range of voltages corresponding to Logic ‘High’ is represented with ‘1’ and the range of voltages corresponding to logic ‘Low’ is represented with ‘0’.

Postulates and Basic Laws of Boolean Algebra

In this section, let us discuss about the Boolean postulates and basic laws that are used in Boolean algebra. These are useful in minimizing Boolean functions.

Boolean Postulates

Consider the binary numbers 0 and 1, Boolean variable (x) and its complement (x’). Either the Boolean variable or complement of it is known as literal. The four possible logical OR operations among these literals and binary numbers are shown below.
x + 0 = x
x + 1 = 1
x + x = x
x + x’ = 1
Similarly, the four possible logical AND operations among those literals and binary numbers are shown below.
x.1 = x
x.0 = 0
x.x = x
x.x’ = 0
These are the simple Boolean postulates. We can verify these postulates easily, by substituting the Boolean variable with ‘0’ or ‘1’.
Note− The complement of complement of any Boolean variable is equal to the variable itself. i.e., (x’)’=x.

Basic Laws of Boolean Algebra

Following are the three basic laws of Boolean Algebra.
  • Commutative law
  • Associative law
  • Distributive law

Commutative Law

If any logical operation of two Boolean variables give the same result irrespective of the order of those two variables, then that logical operation is said to be Commutative. The logical OR & logical AND operations of two Boolean variables x & y are shown below
x + y = y + x
x.y = y.x
The symbol ‘+’ indicates logical OR operation. Similarly, the symbol ‘.’ indicates logical AND operation and it is optional to represent. Commutative law obeys for logical OR & logical AND operations.

Associative Law

If a logical operation of any two Boolean variables is performed first and then the same operation is performed with the remaining variable gives the same result, then that logical operation is said to be Associative. The logical OR & logical AND operations of three Boolean variables x, y & z are shown below.
x + (y + z) = (x + y) + z
x.(y.z) = (x.y).z
Associative law obeys for logical OR & logical AND operations.

Distributive Law

If any logical operation can be distributed to all the terms present in the Boolean function, then that logical operation is said to be Distributive. The distribution of logical OR & logical AND operations of three Boolean variables x, y & z are shown below.
x.(y + z) = x.y + x.z
x + (y.z) = (x + y).(x + z)
Distributive law obeys for logical OR and logical AND operations.
These are the Basic laws of Boolean algebra. We can verify these laws easily, by substituting the Boolean variables with ‘0’ or ‘1’.

Theorems of Boolean Algebra

The following two theorems are used in Boolean algebra.
  • Duality theorem
  • DeMorgan’s theorem

Duality Theorem

This theorem states that the dual of the Boolean function is obtained by interchanging the logical AND operator with logical OR operator and zeros with ones. For every Boolean function, there will be a corresponding Dual function.
Let us make the Boolean equations (relations) that we discussed in the section of Boolean postulates and basic laws into two groups. The following table shows these two groups.
Group1Group2
x + 0 = xx.1 = x
x + 1 = 1x.0 = 0
x + x = xx.x = x
x + x’ = 1x.x’ = 0
x + y = y + xx.y = y.x
x + (y + z) = (x + y) + zx.(y.z) = (x.y).z
x.(y + z) = x.y + x.zx + (y.z) = (x + y).(x + z)
In each row, there are two Boolean equations and they are dual to each other. We can verify all these Boolean equations of Group1 and Group2 by using duality theorem.

DeMorgan’s Theorem

This theorem is useful in finding the complement of Boolean function. It states that the complement of logical OR of at least two Boolean variables is equal to the logical AND of each complemented variable.
DeMorgan’s theorem with 2 Boolean variables x and y can be represented as
(x + y)’ = x’.y’
The dual of the above Boolean function is
(x.y)’ = x’ + y’
Therefore, the complement of logical AND of two Boolean variables is equal to the logical OR of each complemented variable. Similarly, we can apply DeMorgan’s theorem for more than 2 Boolean variables also.

The Idempotent Laws
AA = A
A+A = A
The Associative Laws
(AB)C = A(BC)
(A+B)+C = A+(B+C)
The Commutative Laws
AB = BA
A+B = B+A
The Distributive Laws
A(B+C) = AB+AC
A+BC = (A+B)(A+C)
The Identity Laws
AF = F
AT = A
A+F = A
A+T = T
The Complement Laws
AA = F
A+A = T
F = T
T = F
The Involution Law
A = A
DeMorgan's Law
AB = A+B
A+B = A B

Simplification of Boolean Functions

Till now, we discussed the postulates, basic laws and theorems of Boolean algebra. Now, let us simplify some Boolean functions.

Example 1

  • Simplify: C + BC:
    ExpressionRule(s) Used
    C + BCOriginal Expression
    C + (B + C)DeMorgan's Law.
    (C + C) + BCommutative, Associative Laws.
    T + BComplement Law.
    TIdentity Law.


Example 2
  • Simplify: AB(A + B)(B + B):
    ExpressionRule(s) Used
    AB(A + B)(B + B)Original Expression
    AB(A + B)Complement law, Identity law.
    (A + B)(A + B)DeMorgan's Law  (x.y)’ = x’ + y’
    A + BBDistributive law. This step uses the fact that or distributes over and. It can look a bit strange since addition does not distribute over multiplication.   x + (y.z) = (x + y).(x + z)
    AComplement, Identity


Example 3

Let us simplify the Boolean function, f = p’qr + pq’r + pqr’ + pqr

Given Boolean function, f = p’qr + pq’r + pqr’ + pqr.
Step 1 − Use the Boolean postulate, x + x = x. That means, the Logical OR operation with any Boolean variable ‘n’ times will be equal to the same variable. So, we can write the last term pqr two more times.
⇒ f = p’qr + pq’r + pqr’ + pqr + pqr + pqr
Step 2 − Use Distributive law for 1st and 4th terms, 2nd and 5th terms, 3rdand 6th terms.
⇒ f = qr(p’ + p) + pr(q’ + q) + pq(r’ + r)
Step 3 − Use Boolean postulate, x + x’ = 1 for simplifying the terms present in each parenthesis.
⇒ f = qr(1) + pr(1) + pq(1)
Step 4 − Use Boolean postulate, x.1 = x for simplifying the above three terms.
⇒ f = qr + pr + pq
⇒ f = pq + qr + pr
Therefore, the simplified Boolean function is f = pq + qr + pr.

Comments

Post a Comment

Popular posts from this blog

WHAT ETHICAL, SOCIAL, AND POLITICAL ISSUES ARE RAISED BY INFORMATION SYSTEMS?

Image
Information technology is introducing changes for which laws and rules of acceptable conduct have not yet been developed. Increasing computing power, storage, and networking capabilities--including the Internet--expand the reach individual and organizational actions and magnify their impacts. The ease and anonymity with which information is now communicated, copied, and manipulated in online environments pose new challenges to the protection of privacy and intellectual property. The main ethical, social, and political issue raised by information systems center around information rights and obligations, property rights and obligations, accountability and control, system quality, and quality of life. 1.Ethical issues:  Intellectual property rights, electronic monitoring of employees and data utilization; 2.Cultural issues:  Assimilation of emerging technologies, developing trust, power asymmetry, policy implementation, and social environments; 3.Human interaction i...
Read more

Porter’s Value Chain Analysis

Image
What is a Value Chain Analysis? The value chain also known as Porter’s Value Chain Analysis is a business management concept that was developed by  Michael Porter . In his book  Competitive Advantage  (1985),  Michael Porter  explains Value Chain Analysis; that a value chain is a collection of activities that are performed by a company to create value for its customers.   Value Creation  creates added value which leads to competitive advantage. Ultimately, added value also creates a higher profitability for an organization. Porter’s Value Chain Analysis The strength of the Porter’s Value Chain Analysis is its approach. The Porter’s Value Chain Analysis focuses on the systems and activities with customers as the central principle rather than on departments and accounting expense categories. This system links systems and activities to each other and demonstrates what effect this has on costs and profit. Consequently, it (Value Chain Analysis) ma...
Read more

General Register organization & Components of CPU and their functions:

Image
Components of CPU and their functions: CPU or  Central processing unit  is the brain of the computer system. Functions of CPU varies from data processing to controlling input-output devices. Each and every instruction no matter how complex or simple, it has to go through the CPU. In this article we will learn various components of CPU and their functions. So, let us say we press a key on the keyboard and it instantly appears on our computer monitor so the CPU of the computer is what makes this possible. The central processing unit is also responsible for storing data or information, intermediate results and instructions in the memory system. It also controls the operations of all other parts of the computer system. Functions of a CPU: CPU generally performs the arithmetical and logical operations, controlling of different input-output devices. These operations are performed based on some predefined algorithm...
Read more