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.
