Theorems of Boolean Algebra

Theorems of Boolean Algebra are as follows;

1. Duality Theorem

It states that“Every algebraic expression deducible from the postulates of Boolean algebra remains valid if the operators and identity elements are interchanged”.
Starting from a boolean relation, we can derive another boolean relation by:
1. Changing each OR(+) sign to AND(•) sign or Vice-versa
2. Complementing any 0 or 1 appearing in the expression.
Eg:
a) x + 0 = x --> x • 1 = x
b) x(y+z) = xy+xz --> x+yz = (x+y)(x+z)

Here: Dual of x(y+z) = x+yz and Dual of xy+xz = (x+y)(x+z)

c) AB + A'C + BC = AB + A'C --> (A+B)(A'+C)(B+C) = (A+B)(A'+C)

Here: Dual of AB + A'C + BC = (A+B)(A'+C)(B+C) and

Dual of AB + A'C = (A+B)(A'+C)

Basic Theorems of Boolean Algebra

Basic theorems of Boolean Algebra are Idempotence, existence, involution, associative, de morgan's, and absorption.

The postulates are basic axioms of the algebraic structure and need no proof. The theorems must be proven from the postulates. Six
theorems of Boolean algebra are given below:

Theorem1: Idempotence    (a) x + x = x (b) x.x = x
Theorem2: Existence: 0 & 1(a) x + 1 = 1 (b) x.0 = 0
Theorem3: Involution              (x')' = x
Theorem4: Associative        (a) x+(y+z) = (x+y)+z (b) x(yz) = (xy)z
Theorem5: De-morgan       (a) (x + y)' = x'y' (b) (xy)' = x' + y'
Theorem6: Absorption        (a) x + xy = x (b) x(x + y) = x

Proofs:

(a) The proofs of the theorems with one variable are presented below:
THEOREM 1(a): x + x = x

=x + x = (x + x) . 1 (P4: Identity element)
= (x + x)(x + x') (P5: Existence of inverse)
= x + xx' (P3: Distribution)
=x + 0 (P5: Existence of inverse)
=x (P4: Identity element)

THEOREM 1(b): x·x = x

=x.x = xx + 0 (P4: Identity element)
=xx + xx' (P5: Existence of inverse)
=x(x + x') (P3: Distribution)
= x.1 (P5: Existence of inverse)
=x (P4: Identity element)

THEOREM 2(a): x + 1 = 1

= x + 1 = 1· (x + 1) (P4: Identity element)
= (x + x')(x + 1) (P5: Existence of inverse)
= x + x'·1 (P3: Distribution)
= x + x' (P4: Identity element)
= 1 (P5: Existence of inverse)

THEOREM 2(b): x.0 = 0

 

Prove De-Morgan's Theorem:

THEOREM 5 (a): (x + y)' = x'y'
From postulate P5 (Existence of inverse), for every x in a Boolean algebra there is a unique x' such that x + x' = 1 and x • x' = 0. So, it is sufficient to show that x'y' is the complement of x + y. We'll do
this by showing that (x + y) + (x'y') = 1 and (x + y) • (x'y') = 0.

=(x + y) + (x'y')
= [(x + y) + x'] [(x + y) + y'] [OR distributes over AND (P3)]
= [(y + x) + x'] [(x + y) + y'] [OR is commutative (P2)]
= [y + (x + x')] [x + (y + y')] [OR is associative (Theorem 3(a)),

used twice]

= (y + 1)(x + 1) [Complement, x + x' = 1 (P5), twice]
= 1 • 1 [x + 1 = 1, (Theorem 2), twice]
= 1 [Idempotent, x • x = x (Theorem 1)]

 

Also,
=(x + y)(x'y')
= (x'y') (x + y) [AND is commutative (P2)]
= [(x'y') x] + [(x'y') y] [AND distributes over OR (P3)]
= [(y'x')x] + [(x'y')y] [AND is commutative (P2)]
= [y'(x'x)] + [x'(y'y)] [AND is associative (Theorem 3(b)), twice]
= [y'(xx')] + [x'(yy')] [AND is commutative, twice]
= [y' • 0] + [x' • 0] [Complement, x • x' = 0, twice]
= 0 + 0 [x • 0 = 0, twice]
= 0 [Idempotent, x + x = x]

THEOREM 5(b): (xy)' = x' + y' can be proved similarly as in Theorem 5(a).