DHARM
N-COM\APPENDIX.PM5BOOLEAN ALGEBRA 353and also operator ‘+’ is distributive over operator ‘. ’ whenever,
x + (y. z) = (x + y). (x + z)
One of the example of an algebraic system is a field. A field is defined by a set of ele-
ments, binary operations ‘. ’ and ‘+’, a set of postulates 1 to 5, and combination of both opera-
tions fulfilling postulates 6. A field of real numbers is a common example consists of set of real
numbers, with binary operations ‘. ’ and ‘+’ which is the basis for ordinary algebra.A.2 Definition of Boolean Algebra.........................................................................................
A Boolean algebra is an algebraic structure denoted as (X, +,. , ′, 0, 1) in which (X, +, .) is a
lattice, where X is a set of elements and binary operations + and. are called GLB and LUB
respectively. 0 and 1 are least and greatest element of the poset (X, ≤). Fig. A.1 shows the
postulates that are satisfied by Boolean algebra.
No. Name of the postulates Statement of the postulates
These pairs of laws are dual to each other
1 Closure Closure w.r.t. operator ‘+’ Closure w.r.t. operator ‘. ’
2 Existence of an Identity There exist elements 0, 1 ∈ X such that for all x ∈ X
Element x + 0 = 0 + x = xx. 1 = 1. x = x
3 Commutative Law x + y = y + xx. y = y. x
4 Distributive Law x. (y + z) = (x. y) + (x. z) x + (y. z) = (x + y). (x + z)
5 Complement ∀x ∈ X there exist an element x′ (known as complement of x)
such that
x + x′ = 1 x. x′ = 0
6 Uniqueness There exists at least two elements x, y ∈ X i.e., x ≠ y
(Postulates 1–6 are called Huntington postulates)
Fig. A.1
We can formulate many Boolean algebra, depending upon the choice of the set X and the
rules of operations. For example, a two-value Boolean algebra is defined on a set of two elements
X = {0, 1}. The operations (+,. , ′) are shown in Fig. A.2 (a), (b) and (c) respectively. The two-
value Boolean algebra is denoted by a Boolean structure ({0, 1}, +,. , ′ , 0, 1) and it satisfies all
the postulates 1-6. It is the only Boolean structure whose representation is a chain.
x y x + y x y x. yxx′
00 0 00 0 01
01 1 01 0 10
10 1 10 0
11 1 11 1
(a) operations same as OR (b) operations same as AND (c) operations same as NOT
Fig. A.2
We can also verify that Huntington postulates 1–6 are satisfied by a two-value Boolean
algebra ({0, 1}, +, ., ′, 0, 1), i.e.,
- Closure is obvious, because from the operations tables shown in Fig. A.2 we saw that
result of each operation is either 0 or 1 that is in set X.