Postulates (continued)

– Inverse. For a set with an identity element with respect to a
binary operation, the set is said to have an inverse if for every
element of the set the following property holds:
» x * y = e
• The additive inverse of element a is –a and it defines
subtraction, since a + (–a) = 0. Multiplicative inverse of
a is 1/a and defines division, since a.1/a = 1
– Distributive Law. * is said to be distributive over . when
» x * ( y · z) = (x * y) · (x * z)
– Note: * + and . are binary operators. Binary operator + defines
addition and binary operator . defines multiplication
• Two-value Boolean algebra is defined by the:
– The set of two elements B={0, 1}
– The operators of AND (·) and OR (+)
– Huntington Postulates are satisfied
Huntington Postulates:

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:
1. Closure.
a) with respect to the binary operation OR (+); c=x+y
b)with respect to the binary operation AND (·); c=x.y
2. Identity.
a) with respect to OR (+) is 0:
􀂙x + 0 = 0 + x = x, for x = 1 or x = 0
b)with respect to AND (·) is 1:
􀂙x · 1 = 1 · x = x, for x = 1 or x =0
3. Commutative Law.
a) With respect to OR (+):
􀂙x + y = y + x
b)With respect to AND (·):
􀂙x · y = y · x

4C.Doistnribtuitinveu Leawd.…
a) with respect to the binary operation OR (+):
x + (y · z) = (x + y) · (x + z) + is distributive over .
b)with respect to the binary operation AND (·):
x · (y + z) = (x · y) + (x · z) . is distributive over +
5.Complement. For every element x, that belongs to B, there also
exists an element x’ (complement of x) such that:
a) x + x’ = 1, for x = 1 or x = 0
b)x · x’ = 0 , for x = 1 or x = 0
6. Membership.
There exists at least two elements, x and y, of the set such that
x ≠ y.
0 ≠ 1
Notes on Huntington Postulate 

Comparing Boolean algebra with arithmetic and ordinary
algebra, we note the following differences:
• The associative law is not listed but it can be derived from
the existing postulates for both + and . operations.
• The distributive law of + over . i.e.,
x+(y . z) = (x + y) . (x + z)
is valid for Boolean algebra but not for ordinary algebra.
• Boolean algebra doesn’t have inverses (additive or
multiplicative) therefore there are no operations related to
subtraction or division.
• Postulate 5 defines an operator called complement that is
not available in ordinary algebra.
• Boolean algebra deals with only two elements, 0 and 1

Boolean Algebra

Boolean Algebra:
• Boolean algebra is the basic mathematics needed
for the study of logic design of digital systems.
• In 1854, George Boole an English mathematician
gave the concept of “Logical algebra” known
today as Boolean algebra.
• Boolean algebra is a convenient and systematic
way of expressing and analyzing the operation of
logic circuits.
• Claude Shannon was the first to apply Boole’s
work to the analysis of relays and switching
circuits in 1938.was Other Logic Operations
• In 1904, Huntington gave a set of postulates that
form the basis of formal definition of Boolean
algebra.
Set Notations:

Mathematical systems can be defined with:
– A set of elements; A set of elements is any collection of
objects having a common property.
– A set of operators; 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.
– A number of unproved axioms or postulates that form the
basic assumptions from which it is possible to deduce the
rules, theorems and properties of the system.
• The following notations are being used in this class:
–      x∈S indicates that x is an element of the set S.
–      y ∉ S indicates that y is not an element of the set S.


–    A = {1, 2, 3, 4} indicates that set A exists with a finite number
of elements (1, 2, 3, 4).
Basic Postulates:

The basic postulates of a mathematical system are:
– Closure. A set S is closed w.r.t a binary operator if this operation
only produces results that are within the set of elements defined by
the system.
– Associative Law. A binary operator is said to be associative when:
» (x * y) * z = x * (y * z)
– Commutative Law. A binary operator is said to be commutative
when:
» x * y = y * x
– Identity Element. A set is said to have an identity element with
respect to a binary operation if there exists an element, e, that is a
member of the set with the property:
» e * x = x * e = x for every element of the set
• Additive identity is 0 and multiplicative identity is 1
– Note: * + and . are binary operators

Complements

Complements are used to simplify subtraction
operations. We do subtraction by adding.
A – B = A+ (-B)
• There are two types:
– The radix complement, called the r’s complement.
– The diminished radix complement, called the (r-1)’s complement.
Diminished Radix Complement:

Given a number N in base r having n digits, the (r-1)’s
complement of N is defined as:
(rn – 1) – N
• Decimal numbers are in base-10.
(r-1) = (10-1) = 9.
• The 9’s complement would be defined as:
(10n – 1) – N
• So, to determine the 9’s complement of 52:
(102 – 1) – 52 = 47
• Another example is to determine the 9’s complement
of 3124:
(104 – 1) – 3124 = 6875
Finding Diminished Radix complement:

The DRC or (r-1)’s complement of decimal number is
obtained by subtracting each digit from 9
• The (r-1)’s complement of octal or hexadecimal
number is obtained by subtracting each digit from 7 or
F, respectively
• The DRC (1’s complement) of a binary number is
obtained by subtracting each digit from 1. It can also
be formed by changing 1’s to 0’s and 0’s to 1’s
DRC for Binary Numbers:

For binary numbers r = 2 and (r-1) = 1. So, the 1’s
complement would be defined as:
(2n – 1) – N
• To determine the 1’s complement of 1000101:
(27 – 1) – 1000101 = 0111010
• To determine the 1’s complement of 11110111101:
(211 – 1) - 11110111101 = 00001000010
• Note that 1’s complement can be done by switching
all 0’s to 1’s and 1’s to 0’s.
r's Complement

• The r’s complement of an n-digit number N in base-r is
defined as:
rn – N - for N ≠ 0
0 -for N = 0
• We may obtain r’s complement by adding 1 to (r-1)’s
complement. Since rn – N = [(rn – 1) – N]+1
• 10’s complement of 3229 is:
104 – 3229 = 6771
• 2’s complement of 101101 is:
26 – 101101 = 010011
• Note that to determine 2’s complement, leave the least
significant 0’s and the first 1 unchanged and then
switch the remaining 1’s to 0’ and 0’s to 1’s.

Different Base systems

Binary Numbers:
The binary system contains only two values in the
allowed coefficients (0 and 1).
• The binary system uses powers of 2 as the
multipliers for the coefficients.
• For example, we can represent the binary number
10111.01 as:
– 1 X 24 + 0 X 23 + 1 X 22 + 1 X 21 + 1 X 20 + 0 X 2-1 + 1 X 2-2 = 23.25
Octal Numbers:

The octal number system is a base-8 system that
contains the coefficient values of 0 to 7.
• The octal system uses powers of 8 as the multipliers
for the coefficients.
• For example, we can represent the octal number
72032 as:
7 X 84 + 2 X 83 + 0 X 82 + 3 X 81 + 2 X 80 = (29722)10
Hexadecimal Numbers:

The hexadecimal number system is a base-16 system
that contains the coefficient values of 0 to 9 and A to
F. The letters A through F represent the coefficient
values of 10, 11, 12, 13, 14, and 15, respectively.
• The hexadecimal system uses powers of 16 as the
multipliers for the coefficients.
• For example, we can represent the hexadecimal
number C34D as:
– 12 X 163 + 3 X 162 + 4 X 161 + 13 X 160 = (49997)10
Conversion From any base to Decimal:

Conversion of a number in base r to decimal is done
by expanding the number in a power series and
adding all the terms.
• For example, (C34D)16 is converted to decimal:
12 X 163 + 3 X 162 + 4 X 161 + 13 X 160 = (49997)10
• (11010.11)2 is converted to decimal:
1 X 24 + 1 X 23 + 0 X 22 + 1 X 21 + 0 X 20 + 1 X 2-1 + 1 X 2-2 = 26.75