Boolean Algebra
1
By: TUSAR PADHAN
INSTITUTE OF MATHEMATICS
AND APPLICATIONS
Boolean Algebra
Boolean algebra provides the operations and the rules for working with the set {0, 1}.
These are the rules that underlie electronic circuits, and the methods we will discuss are fundamental to VLSI design.
We are going to focus on three operations:
2
Boolean Operations
The complement is denoted by a bar (on the slides, we will use a minus sign). It is defined by
-0 = 1 and -1 = 0.
The Boolean sum, denoted by + or by OR, has the following values:
1 + 1 = 1, 1 + 0 = 1, 0 + 1 = 1, 0 + 0 = 0
The Boolean product, denoted by ⋅ or by AND, has the following values:
1 ⋅ 1 = 1, 1 ⋅ 0 = 0, 0 ⋅ 1 = 0, 0 ⋅ 0 = 0
3
Boolean Functions and Expressions
Definition: Let B = {0, 1}. The variable x is called a Boolean variable if it assumes values only from B.
A function from Bn, the set {(x1, x2, …, xn) |xi∈B, �1 ≤ i ≤ n}, to B is called a Boolean function of degree n.
Boolean functions can be represented using expressions made up from the variables and Boolean operations.
4
Boolean Functions and Expressions
The Boolean expressions in the variables x1, x2, …, xn are defined recursively as follows:
Each Boolean expression represents a Boolean function. The values of this function are obtained by substituting 0 and 1 for the variables in the expression.
5
Boolean Functions and Expressions
For example, we can create Boolean expression in the variables x, y, and z using the “building blocks”�0, 1, x, y, and z, and the construction rules:
Since x and y are Boolean expressions, so is xy.
Since z is a Boolean expression, so is (-z).
Since xy and (-z) are expressions, so is xy + (-z).
… and so on…
6
Boolean Functions and Expressions
Example: Give a Boolean expression for the Boolean function F(x, y) as defined by the following table:
7
x | y | F(x, y) |
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 0 |
1 | 1 | 0 |
Possible solution: F(x, y) = (-x)⋅y
Boolean Functions and Expressions
Another Example:
8
Possible solution I:
F(x, y, z) = -(xz + y)
0
0
1
1
F(x, y, z)
1
0
1
0
z
0
0
1
0
1
0
0
0
y
x
0
0
0
1
1
0
1
0
1
1
1
1
0
1
0
1
Possible solution II:
F(x, y, z) = (-(xz))(-y)
Boolean Functions and Expressions
There is a simple method for deriving a Boolean expression for a function that is defined by a table. This method is based on minterms.
Definition: A literal is a Boolean variable or its complement. A minterm of the Boolean variables x1, x2, …, xn is a Boolean product y1y2…yn, where yi = xi or yi = -xi.
Hence, a minterm is a product of n literals, with one literal for each variable.
9
Boolean Functions and Expressions
Consider F(x,y,z) again:
10
F(x, y, z) = 1 if and only if:
x = y = z = 0 or
x = y = 0, z = 1 or
x = 1, y = z = 0
Therefore,
F(x, y, z) =�(-x)(-y)(-z) +�(-x)(-y)z +�x(-y)(-z)
0
0
1
1
F(x, y, z)
1
0
1
0
z
0
0
1
0
1
0
0
0
y
x
0
0
0
1
1
0
1
0
1
1
1
1
0
1
0
1
Boolean Functions and Expressions
Definition: The Boolean functions F and G of n variables are equal if and only if F(b1, b2, …, bn) = G(b1, b2, …, bn) whenever b1, b2, …, bn belong to B.
Two different Boolean expressions that represent the same function are called equivalent.
For example, the Boolean expressions xy, xy + 0, and xy⋅1 are equivalent.
11
Boolean Functions and Expressions
The complement of the Boolean function F is the function –F, where –F(b1, b2, …, bn) = �-(F(b1, b2, …, bn)).
Let F and G be Boolean functions of degree n. The Boolean sum F+G and Boolean product FG are then defined by
(F + G)(b1, b2, …, bn) = F(b1, b2, …, bn) + G(b1, b2, …, bn)
(FG)(b1, b2, …, bn) = F(b1, b2, …, bn) G(b1, b2, …, bn)
12
THANK YOU
13