Boolean Algebra
❖ Boolean algebra, like any other deductive mathematical system, may be defined with a
set of elements, a set of operators, and a number of unproved axioms or postulates.
❖ A set of elements is any collection of objects, usually having a common property.
❖ A binary operator defined on a set S of elements is a rule that assigns, to each pair of
elements from S, a unique element from S.
As an example, consider the relation a*b = c. We say that * is a binary operator if it
specifies a rule for finding c from the pair (a, b) and also if a, b, c are the member of S.
However, * is not a binary operator if a, b are member of S, and if c is not a member of S.
The postulates of a mathematical system form the basic assumptions from which it is
possible to deduce the rules, theorems, and properties of the system. The most common
postulates used to formulate various algebraic structures are as follows:
AXIOMATIC DEFINITION OF BOOLEAN ALGEBRA
In 1854, George Boole developed an algebraic system now called Boolean algebra. For the
formal definition of Boolean algebra, we shall employ the postulates formulated by E. V.
Huntington in 1904.
Boolean algebra is an algebraic structure defined by a set of elements, B, together with two binary
operators, ‘+’ and ‘.’ , provided that the following (Huntington) postulates are satisfied:
Comparing Boolean algebra with arithmetic and ordinary algebra (the field of real numbers), we
note the following differences:
1. Huntington postulates do not include the associative law. However, this law holds for
Boolean algebra and can be derived (for both operators) from the other postulates.
2. The distributive law of + over • (i.e., x + (y • z) = (x + y) • (x + z) ) is valid for Boolean
algebra, but not for ordinary algebra.
3. Boolean algebra does not have additive or multiplicative inverses; therefore, there are no
subtraction or division operations.
4. Postulate 5 defines an operator called the complement that is not available in ordinary
algebra.
5. Ordinary algebra deals with the real numbers, which constitute an infinite set of elements.
Boolean algebra deals with the as yet undefined set of elements, B, but in the two‐valued
Boolean algebra defined next (and of interest in our subsequent use of that algebra), B is
defined as a set with only two elements, 0 and 1.
Two‐Valued Boolean Algebra
A two‐valued Boolean algebra is defined on a set of two elements, B = {0, 1}, with rules for the
two binary operators + and • as shown in the following operator tables
Duality principle states that every algebraic expression deducible from the postulates of
Boolean algebra remains valid if the operators and identity elements are interchanged.
BOOLEAN FUNCTIONS
A Boolean function described by an algebraic expression consists of binary variables, the
constants 0 and 1, and the logic operation symbols. For a given value of the binary variables,
the function can be equal to either 1 or 0.
A Boolean function can be represented in a truth table.
Simplify the following Boolean functions to a minimum number of literals.
Problem: In a room there are three electrical equipment viz. tube light, TV and fan. Design an
alarm system to make sound using NAND gates only, if there are two or more than two
applications running simultaneously. The ON condition of the application is denoted by
logic‘1’, and the OFF condition of the application is denoted by logic ‘0’.
Problem: A coin is tossed three times. A win is said to occur if the result obtained is Heads for
at least 2 tosses. The variables A, B, and C are considered as outcome of the toss. It is given
that A, B, and C are 1 if the outcome of the toss is Head otherwise, they are taken as 0.
Similarly, W is 1 if a win occurs otherwise, it is zero 0. Obtain a truth table, Minimized
Boolean equation for the output and design the logic circuit using NOR gates only.
Minterms and Maxterms
A binary variable may appear either in its normal form (x) or in its complement form (x′) Now
consider two binary variables x and y combined with an AND operation. Since each variable
may appear in either form, there are four possible combinations: x′y′, x′y, xy′, and xy. Each of
these four AND terms is called a minterm.
A Boolean function can be expressed algebraically from a given truth table by forming a
minterm for each combination of the variables that produces a 1 in the function and then
taking the OR of all those terms.
f1 = x′y′z + xy′z ′ + xyz = m1 + m4 + m7
f1 = ∑(m1, m4, m7) = ∑(1, 4, 7)
f1′ = x′y′z′ + x′yz′ + x′yz + xy′z + xyz′
(f1′)′ = (x′y′z′ + x′yz′ + x′yz + xy′z + xyz′)′
f1= (x + y + z)(x + y′ + z)(x + y′ + z′)(x′+ y +
z′)(x′ + y′ + z)
f1 = M0M2M3M5M6 = ∏(M0, M2, M3, M5, M6)
f1 = ∏(0, 2, 3, 5, 6)
Boolean functions expressed as a sum of minterms or product of maxterms are said to be in
canonical form .
K-Map Method
This method may be regarded as a pictorial form of a truth table.
Two Variable Three Variable
x y x y z
0 0 0 0 0
0 1 0 0 1
1 0 0 1 0
1 1 0 1 1
1 0 0
1 0 1
1 1 0
1 1 1 K-Map for three variable
K-Map for two variable
K-Map for four variable
Prime Implicants: A prime implicant is a product term obtained by combining the maximum
possible number of adjacent squares in the map. In other words, it is the largest possible group of
minterm ‘1’.
Essential Prime Implicants: If a minterm in a square is covered by only one prime implicant,
that prime implicant is said to be essential..
