Boolean Algebra and Logic Gates

Boolean Algebra:

Boolean Algebra is defined for a set A in terms of two binary operations . and +. The symbols . and + are called the AND and inclusive OR, respectively. The operations in Boolean Algebra are based on the following axioms or postulates:

1. If x, y ε A, then x + y ε A; x . y ε A
This is known as the closure property.

2. If x, y ε A, then x + y = y + x; x . y = y . x
That is + and . operations are commutative.

3. If x, y, z ε A, then

x + (y.z) = (x + y) . (x + z)
x.(y + z) = (x.y) + (x.z)

That is + and . operations are distributive.

4. Identity elements denoted as 0 and 1 must exist such that x + 0 = x and x . 1 = x for all elements of A.
x + 0 = x and x.1 = x for all elements of A.

5. For every element x in A there exists an element x’ called the complement of x such that
x + x’ = 1
x . x’ = 0

Note: The basic postulates are grouped in pairs. One postulate can be obtained from the other by simply interchanging all OR and AND operations, and the identity elements 0 and 1. This property is known as duality.

There are mainly 8 theorems that can be used for manipulating Boolean functions.

Theorem-1: The identity elements 0 and 1 are unique.

Theorem-2: The idempotent laws

i. x + x = x

ii. x.x = x

Theorem-3: i. x + 1 = 1
ii. x.0 = 0

Theorem-4: The absorption laws

i. x + xy = x

ii. x.(x + y) = x

Theorem-5: Every element in A has a unique complement

Theorem-6: Involution law
(x’)’ = x

Theorem-7: i. x + x’y = x + y
ii. x(x’ + y) = xy

Theorem-8: i. (x + y)’ = x’.y’
ii. (xy)’ = x’ + y’

Logic Gates:

A small set of circuit elements known as logic gates can be used to implement Boolean functions. This set is called basis. The most common basis contains the following three gates:

1. AND Gate: The AND gate produces a 1-output if and only if all input variables are 1s. The following figure shows a two-input AND gate with four possible input combinations.

2. OR Gate: The OR gate produces a 0 output only if all the inputs are 0. The following figure shows a two-input OR gate.

3. NOT Gate: The NOT gate produces an output of 1 when the input is 0, and an output of 0 when the input is 1. The following figure shows the symbol for the NOT gate. It is sometimes referred to as an inverting buffer or simply an inverter.