Basic Theorems & Properties of Boolean Algebra || Boolean Algebra and Logic Gates || Bcis Notes

Basic theorems & Properties of Boolean algebra:

Duality 

The Huntington postulates have been listed in pairs and designated by parts (a) and part (b). One part may be obtained from the other if the binary operators and those identity elements are interchanged. the important property of Boolean algebra is called the duality principle. It states that every algebraic expression deducible from the postulates of Boolean algebra remains valid if the operators and identity elements are interchanged. In a two-valued Boolean algebra, the identity elements and the elements of the set B are the same: 1 and 0. If the dual of an algebraic expression is desired, we simply interchange OR and AND operators and replace
1’s by 0’s and 0’s by 1’s.

Basic theorems

The theorems, like the postulates, are listed in pairs; each relation is the dual of the one paired with it. 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: Demorgan (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)
Hey! Each step in theorem 1(b) and 1(a) are dual of each other.

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 by duality.

THEOREM 3: (x ‘)’ = x. From P5, we have x + x’ = 1 and x.x’ = 0, which defines the complement of x. The complement of x’ is x and is also (x’)’. Therefore, since the complement is unique, we have that (x’)’ = x.

(b) The theorems involving two or three variables may be proven algebraically from the postulates and
the theorems that have already been proven. For example, let’s prove Demorgan’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). Each step in the proof of 5(b) is the dual of its 5(a) counterparts.
Hey! Theorems above can also be proved using truth tables (alternative to algebraic simplification). Viz.

Operator Precedence 

The operator precedence for evaluating Boolean expressions is
1. Parentheses
2. NOT
3. AND
4. OR
In other words, the expression inside the parentheses must be evaluated before all other operations. The next operation that holds precedence is the complement, then follows the AND, and finally the OR. Example: (a+b.c).d’  here we first evaluate ‘b.c’ and OR it with ‘a’ followed by ANDing with a complement of ‘d’.

You may like an introduction to Boolean Algebra