Boolean algebra is a mathematical structure that is mainly used in the analysis and simplification of digital or logic circuits (Kudryavtseva and Lawson, 2015). Boolean algebra was introduced in 1854 by a mathematician known as George Boole (Leech and Spinks, 2008). It only uses two binary numbers 0 and 1. Boolean algebra had a similar mathematical structure as that of Boolean ring, but defined in a way such that it meets and joins operators instead of multiplication and addition operators that are usually used in most mathematical structures. In a nutshell, a Boolean algebra is defined to be the partial order on subsets of a set say X defined by inclusion (Khuzam and Yaqub, 2013; Avilés, 2004). The origin of Boolean algebra was based on the fact that the structure of logical thoughts can be represented by mathematical symbols. The expressions in a Boolean algebra can always be converted into logic diagrams with the use of different gates of logic. Some laws or rules govern Boolean algebra, and they are known as the laws of Boolean algebra. Logical operations are always carried out using these laws. The laws that govern Boolean algebra include the commutative law, the distributive law, “and” law, the associative law, “or” law, the inversion law, involution law, absorption law and many others. This paper aims at proving some of the laws of Boolean algebra.
If a binary operation satisfies the operations below then it is called a commutative operation (Whitesitt, 1995).
B.A=A.B and A+B=B+A
In a nutshell, the commutative law states there is no effect on the output of an operation in Boolean algebra when the sequence of the variables is changed.
If A+B=B+A it implies that id A=1 AND B=1 then the left hand side of the equation will be 1+1=2=B+A which is the right hand side.
If B=0 and A=0 then for the left hand side 0+0=B+A which is equal to the right hand side.
If A=0 AND B=1 the for the left hand side 0+1=1=1+0=B+A which is the right hand side.
The proof is satisfied.
The proof for the commutative law for AND is as follows.
If we let A=1 and B=1 then for the left hand side we will have 1.1=1=B.A which is equal to the right hand side.
If we now let B=0 and A=0 then for the left hand side we have 0.0=0=B.A which is equal to the right hand side.
Hence the proof is satisfied.
The associative law states that the order in which operations in Boolean algebra are performed are irrelevant as their effect is just the same (Whitesitt, 1995).
To proof the associative law, we need to show that the left hand side is equal to the right hand side
Let A=X+(Y+Z) and B=(X+Y)+Z
XA=X[X+(Y+Z)] Substitution of A
X(X+Y)=X Through the absorption law.
XB=X[(X+Y)+Z] By substitution of B
=X(X+Y)+XZ Since the operation AND distributes over the operation OR
=X+XZ By the absorption law
=X also by the absorption law
Therefore XA=XB=X hence the proof is satisfied
The distributive law for Boolean algebra comprises of two operators namely AND and OR operator where AND implies multiplication and OR implies addition.
- (B+C) =A.B+A.C
The proof for the distributive law can be obtained from the definition of a Boolean algebra. Thus a Boolean algebra is clearly distributive from its definition.
The following laws use the AND operation and they are called the AND laws. The AND operation is basically the multiplication operation in real numbers.
The proof for and law follows from the proof for OR laws
The following operations use the OR operation and are called the OR laws. The OR operation is basically the addition operation in real numbers.
- The zero element is the identity element in OR law and the addition of the identity element to an element is clearly the same element. That is an element remains unchanged when an identity element is added to it. Hence the proof.
- The second law is also called the law for an idempotent element.
A=A+1. This is true due to the identity law
A=A+ . This is true due to the unit property
A=A+A+0. This is true due to the zero property
Hence the proof
The law can also be roved as shown below;
A+A=(A+A).1 since 1 is the identity for AND
A+A=(A+A).(A+A’) this is due to the complement A+A’=1
A+A=A+(A.A’) this is because OR distributes over AND
A+A=A+0 this is because of complement A.A’=0
A+A=A since 0 is the identity for OR
- A+1=1 This is the identity law
A+1=1.(A+1) 1 is the identity for AND
A+1=(A+A’).(A+1) the complement A+A’=1
A+1=A+(A’.1) Clearly OR distributes over AND
A+1=A+A’ the identity for AND is 1
A+1=1 Complement A+A’=1
- When a number is added to its complement, the number remains unchanged.
For every element a in a universal set A, (a’)’=a. That is, the complement of a complement of an element is equal to the same element (Whitesitt, 1995).
Let a be one complement of a’
Thus the complement of the element a’ is unique
For this reason a =(a’)’
Let a and b be some elements in a universal set B, then
a.(a+b)=a and a+a.b=a
a(a+b)= (a+0)(a+b) since 0 is the identity element for a
=a. Hence the proof
DE Morgan’s laws
The first DE Morgan’s law states that the complement of a sum of two elements is equal to the product of the complements of the same elements. That is,
The second DE Morgan’s law states that the complement of a product of two elements is equal to the sum of the complements of the elements. That is,
To proof the first law we let A=0 and B=0
For the left hand side (A+B)’=(0+0)’=0’=1
For the right hand side A’.B’=0’.0’=1.1=1
The right hand side is equal to the left hand side which proofs the first law.
To proof the second law, we let A=0 and B=0
For the left hand side A’.B’=0’.0’=1.1=1
For the right hand side A’+B’=0’+0’=1’+1’=1
The left hand side is equal to the right hand side which proves the second law.
The laws that have been proved in this paper are vital for any operations in Boolean algebra. Boolean algebra is applied in various fields including the design of logic circuits. The statements that are always expressed in the everyday language such as “I will be home today” can be converted into mathematical operations using the laws of Boolean algebra. Most theorems in Boolean algebra are also proved using the laws that have been discussed in this paper.
Avilés, A. (2004). Boolean Metric Spaces and Boolean Algebraic Varieties. Communications in Algebra, 32(5), pp.1805-1822.
Khuzam, H. and Yaqub, A. (2013). Generalized Boolean and Boolean-like rings. International Journal of Algebra, 7, pp.429-438.
Kudryavtseva, G. and Lawson, M. (2015). Boolean sets, skew Boolean algebras and a non-commutative Stone duality. Algebra universalis, 75(1), pp.1-19.
Leech, J. and Spinks, M. (2008). Skew Boolean algebras derived from generalized Boolean algebras. Algebra universalis, 58(3), pp.287-302.