Boolean functions
Dr. S. RAMESH
Department of Mathematics
Institute of Science
GITAM(Deemed to be University)
Boolean functions [Link], Dept. of Mathematics,GIS
Boolean expression
A Boolean expression, form, or formula in n-variables x1 , x2 , x3 , · · · xn is any finite
string of symbols formed in the following manner:
1. a and 1 are Boolean expressions
2. x1 , x2 , x3 , · · · xn are Boolean expressions
3. If α1 and α2 are Boolean expressions, then (α1 ∗ α2 ) and (α1 ⊕ α2 ) are also
Boolean expressions.
4. If α is a Boolean expression, then α0 is also a Boolean expression.
5. No string of symbols except those formed in accordance with rules 1 to 4 are
Boolean expressions.
Notation
Boolean expressions are denoted by α, β, γ or more precisely as α(x1 , x2 , x3 , · · · xn ).
Examples
x1 , (x10 ⊕ x2 ), (x20 ⊕ x1 )0 ∗ (x3 ⊕ x1 ), (x10 ⊕ x1 ) ∗ x2 ∗ x30 .
Boolean functions [Link], Dept. of Mathematics,GIS
Equivalent Boolean forms
Tow Boolean forms α(x1 , x2 , x3 , · · · xn ) and β(x1 , x2 , x3 , · · · xn ) are called equivalent (or
equal) if one can be obtained from the other by a finite number of applications of the
identities of a Boolean algebra.
Boolean functions [Link], Dept. of Mathematics,GIS
Problems
Write the following Boolean expressions in an equivalent sum-of-products canonical
forms.
1. x1 ∗ x2 (Assuming the problem is in the three variables x1 , x2 and x3 )
2. x1 ⊕ x2 (Assuming the problem is in the three variables x1 , x2 and x3 )
3. (x1 ⊕ x2 )0 ∗ x3
4. x1 ⊕ (x2 ∗ x30 )
5. (x1 ⊕ x2 )0 ⊕ (x10 ∗ x3 )
6. (x ∗ z) ⊕ (x 0 ∗ y ) ⊕ (y ∗ z)
7. (x ⊕ y ) ∗ (x 0 ⊕ z) ∗ (y ⊕ z)
8. (x ⊕ y ) ∗ (x 0 ⊕ z)
9. (x ∗ z) ⊕ (x 0 ∗ y )
10. (x1 ∗ x20 ) ⊕ x4 (Assuming the problem is in the four variables x1 , x2 , x3 and x4 )
Boolean functions [Link], Dept. of Mathematics,GIS
Problems continued
Write the following Boolean expressions in an equivalent product-of-sums canonical
forms.
1. (x1 ∗ x20 ) ⊕ x3
2. [(x1 ⊕ x2 ) ∗ (x3 ∗ x4 )0 ]0
3. (x20 ⊕ [x30 ⊕ x1 ⊕ (x2 ∗ x3 )0 ]) ∗ [x3 ⊕ (x10 ∗ x2 )]
Boolean functions [Link], Dept. of Mathematics,GIS
Boolean function
Let (B, ∗, ⊕,0 , 0, 1) be a Boolean algebra. A function f : B n → B which is associated
with a Boolean expression in n variables is called a Boolean function.
Example
1. A mapping f : B 2 → B defined by f (a, b) = (a ∗ b), for all a, b ∈ B is a Boolean
function.
2. A mapping f : B 2 → B defined by f (a, b) = (a ⊕ b), for all a, b ∈ B is a Boolean
function.
Boolean functions [Link], Dept. of Mathematics,GIS
The value of a Boolean function
If f (a, b) = (a ∗ b) is a Boolean function, then f (0, 1) = 0 ∗ 1 = 0 is called the value
of f (a, b), when a = 0 and b = 1.
Boolean functions [Link], Dept. of Mathematics,GIS
Problems on Karnaugh map
Using Karnaugh mapping, find a minimal sum of products (or product of sums) of the
following
P
1. f (a, b, c) = (0, 1, 4, 6)
P
2. f (a, b, c) = (0, 2, 3, 7)
P
3. f (a, b, c, d) = (0, 5, 7, 8, 12, 14)
P
4. f (a, b, c, d) = (0, 1, 2, 313, 15)
P
5. f (a, b, c, d) = (5, 7, 10, 13, 15)
P
6. f (a, b, c, d) = (0, 2, 6, 7, 8, 9, 13, 15)
Boolean functions [Link], Dept. of Mathematics,GIS
