Boolean Algebra in Computer Science

Boolean Algebra

Boolean theorems are used to simplify Boolean functions in order to use fewer gates. Any variable such as X in binary can have a value of one or zero.

Theorem-1:

[no-highlight]X + X = X
[/no-highlight]

Proof: Select X as 0 then 0+0 = 0, select X = 1 then 1 + 1 = 1 results: X+ X = X

Theorem-2:

[no-highlight]X + 1 = 1
[/no-highlight]

Proof: Select X = 0 then 0+1 = 1, select X = 1 then 1 + 1 = 1, both cases result in 1 then X + 1 = 1

Theorem-3:

[no-highlight]X + 0 = x
[/no-highlight]

Proof: Select X = 0 then 0+0 = 0, select X = 1 then 1 + 0 = 1, result is whatever value X is.

Theorem-4:

[no-highlight]X + X’ = 1
[/no-highlight]

Proof: Select X = 0 then 0+1 = 1, select X = 1 then 1 + 0 = 1, both cases result is 1

Theorem-5:

[no-highlight]X.X = X
[/no-highlight]
Proof: Select X = 1 then 1.1 = 1, select X = 0 then 0.0 = 0, therefore XX=X.

Theorem-6:

[no-highlight]X.1 = X
[/no-highlight]

Proof: Select X = 0 then 1.1 = 1, select X = 0 then 0.1 =0, therefore, X.1 = X.

Theorem-7:

[no-highlight]X.X’ = 0
[/no-highlight]

Proof: Select X = 0 then 0.1 = 1, select X = 1 then 1.0 =0, both values of X result is 0.

Theorem-8:

[no-highlight](X’)’ = X
[/no-highlight]

(0′)’ = (1)’ = 0, (1′)’ = (0)’ = 1 Whatever the value X has.

Distributive Theorem:

[no-highlight]X(Y + Z) = XY + XZ
[/no-highlight]

To prove the above theorem, the truth table of both sides of the theorem is generated as shown above table and it shows that both sides generate the same truth table.

De Morgan’s Theorem-I:

[no-highlight](X + Y)’ = X’Y’
[/no-highlight]
In this theorem, the OR between X and Y is negated and changes the OR operation to the AND operation.

Proof: By making a truth table for both sides of the theorem, it shows that both sides of the theorem generate the same truth table

De Morgan’s Theorem-II:

[no-highlight](XY)’ = X’ + Y’
[/no-highlight]
In this theorem, the XY is complemented and changes from an AND operation to an OR operation with each component complimented.

If the truth table of both sides were generated, then it would show that both sides have the same truth table result.

Commutative Law:

[no-highlight]X + Y = Y + X
XY = YX
[/no-highlight]

Associative Law:

[no-highlight]X(YZ) = (XY)Z
X + (Y + Z) = (X + Y) + Z
[/no-highlight]