Boolean theorems and Boolean Algebra

BOOLEAN THEOREMS AND BOOLEAN ALGEBRA

Boolean Algebra is used to analyse and simplify digital circuits.

Three basic laws of Boolean algebra are similar to the laws used in ordinary algebra.

These laws are:

1. Commutative Law

2. Associative Law

3. Distributive Law

BASIC BOOLEAN LAWS

Logical operations can be expressed and minimized mathematically using the rules, laws and theorems of boolean algebra.

Boolean Addition:

Boolean addition involves variables having values of either a binary 1 or 0. The basic rule for addition are given below

0+0=0

0+1=1

1+0=1

1+1=1

Boolean addition is same as the logical OR operation Boolean multiplication. Boolean multiplication involves logical AND operation.

0.0 = 0

0.1 = 0

1.0 = 0

1.1 = 1

The most common postulates used to formulate various algebraic structures are

1. Closure:

A set S is closed with respect to a binary operates if, for every pair of elements of S, the binary operator specifies a rule for obtaining a unique element of S.

For example, the set of natural numbers N = {1, 2, 3, 4 ...} is closed with respect to the binary operator plus (+) by the rules of arithmetic addition, since for any a, b, EN we obtain a unique C ∈ N by the operation a + b = c.

2. Associative low:

The associative property for addition is given by

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

The OR operation of several variables results in the same, regardless of the grouping of the variables.

The associative law of multiplication is given by

A.(B.C) = (A.B).C

According to this law, it makes no difference in what order the variables are grouped during the AND operation of several variables.

Example:

Law I→ A+ (B+ C) = (A+B) + C

From the above example grouping of the variable regardless of the grouped output is same Left hand side A+ (B+ C) equal to Right hand side (A + B) + C.

Law II → A.(B-C) = (A.B).C

From the above example A (B.C) = (A.B). C are same

Commutative Law

According to this law, the Boolean addition is commutative is given by ComputerScience

A+ B = B+ A

The OR operation conducted on the variables makes no difference.

A.B = B.A

This means AND operation conducted on the variables makes no difference.

Distributive Law

The boolean addition is distributive over boolean multiplications, given by ComputerScience

A+ BC = (A + B) (A + C)

This law states that the AND operation of several variables and then the OR operation of the result with a single variable is equivalent to the OR operation of single variable with each of the several variables and then the AND operation of the sums.

Example

A(B + C) = AB+ AC

Theorem 2: A+1 = 1

Proof: A + 1= (A + 1) • 1

But in Boolean algebra, A+ 1 = 1, because adding 1 always gives 1.

Therefore, A+1=1

Theorem 3: A • 0 = 0

A multiplied by 0 always results in 0.

Therefore, A•0=0

Theorem 4: Absorption Laws

1. A+AB = A

2. A(A+B) = A

3. A( + B) = AB

4. (A+B)(A+ C) = A + BC

Proof 1: A+AB = A • 1 + AB

Step 1: A+AB=A•1 + AB = A • (1+B)

But (1+B) =1

Step 2: → A×1 = A Hence Proved

Proof 2: A(A+B) = A

Step 1: A(A+B) = A•A+AB=A + AB

But from theorem (1): A+AB=A

Therefore,

Step 2: A(A+B) = A

Hence Proved

Proof 3: A(A+B) = AB

Step 1: A(+B)

Step 2: = A•+ AB

But A⚫=0

So expression becomes:

Step 3: 0+ AB = AB

Hence Proved

Proof 4: (A+B)(A+ C) = A+ BC

LHS = (A+B)(A+C)

Step 1:

= A•A + A•C + B•A + B•C

= A + AC + AB + BC

A+AB+BC

[Since A+AC=A]

Now, the expresion

A+AB+BC becomes

A+BC [since A+AB=A]

Thus, (A+B) (A+AC) = A+BC

Hence, proved

Step 2: We know that

A+AC=A

So expression becomes:

A+AB+BC

∴ A+BC

Step 3:

A+AB = A

∴  Expression becomes

Thus, (A+B) (A+C) = A + BC

Hence Proved

Theorem 5: A + B = A + B

R.H.S.

 A+B = A=B•1

= A+B•[A+]

= A + BA+B

= A[1+B]+B

= A+B = LHS

Hence, proved