# 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.