It is a well developed e-book for the students to study at the last minute of examination
It is helpfull to your examination and you will got a high mark
You will score 100 out of 100
EnggTree.com
EC3352 DSD IIYR/III SEM R2021 MSAJCE/ECE
EC3352-DIGITAL SYSTEM DESIGN
II YEAR – III SEMESTER – R2021
UNIT- I BASIC CONCEPTS
INTRODUCTION:
In 1854, George Boole, an English mathematician, proposed algebra for
symbolically representing problems in logic so that they may be analyzed
mathematically. The mathematical systems founded upon the work of Boole are called
Boolean algebra in his honor.
The application of a Boolean algebra to certain engineering problems was
introduced in 1938 by C.E. Shannon.
For the formal definition of Boolean algebra, we shall employ the
postulates formulated by E.V. Huntington in 1904.
Fundamental postulates of Boolean algebra:
The postulates of a mathematical system forms the basic assumption from
which it is possible to deduce the theorems, laws and properties of the system.
The most common postulates used to formulate various structures are—
i) Closure:
A set S is closed w.r.t. a binary operator, if for every pair of elements of S, the
binary operator specifies a rule for obtaining a unique element of S.
The result of each operation with operator (+) or (.) is either 1 or 0 and 1, 0 ЄB.
ii) Identity element:
A set S is said to have an identity element w.r.t a binary operation * on S, if
there exists an element e Є S with the property,
e* x = x * e = x
Eg: 0+ 0 = 0 0+1=1+0=1 a) x+ 0= x
1.1=1 1.0=0.1=1 b) x. 1 = x
iii) Commutative law:
A binary operator * on a set S is said to be commutative if,
x*y=y*x for all x, y Є S
1
Downloaded from EnggTree.com
, EnggTree.com
EC3352 DSD IIYR/III SEM R2021 MSAJCE/ECE
Eg: 0+ 1 = 1+ 0 = 1 a) x+ y= y+ x
0.1=1.0=0 b) x. y= y. x
iv) Distributive law:
If * and • are two binary operation on a set S, • is said to be distributive over +
whenever,
x . (y+ z) = (x. y) + (x. z)
Similarly, + is said to be distributive over • whenever,
x + (y. z) = (x+ y). (x+ z)
v) Inverse:
A set S having the identity element e, w.r.t. binary operator * is said to have an
inverse, whenever for every x Є S, there exists an element x’ Є S such that,
x. x’ Є e
a) x+ x’ = 1, since 0 + 0’ = 0+ 1 and 1+ 1’ = 1+ 0 = 1
b) x. x’ = 1, since 0 . 0’ = 0. 1 and 1. 1’ = 1. 0 = 0
Summary:
Postulates of Boolean algebra:
POSTULATES (a) (b)
Postulate 2 (Identity) x+0=x x.1=x
Postulate 3 (Commutative) x+ y = y+ x x . y = y. x
Postulate 4 (Distributive) x (y+ z) = xy+ xz x+ yz = (x+ y). (x+ z)
Postulate 5 (Inverse) x+x’ = 1 x. x’ = 0
Basic theorem and properties of Boolean algebra:
Basic Theorems:
2
Downloaded from EnggTree.com
, EnggTree.com
EC3352 DSD IIYR/III SEM R2021 MSAJCE/ECE
The theorems, like the postulates are listed in pairs; each relation is the dual of
the one paired with it. The postulates are basic axioms of the algebraic structure and
need no proof. The theorems must be proven from the postulates. The proofs of the
theorems with one variable are presented below. At the right is listed the number of the
postulate that justifies each step of the proof.
1) a) x+ x = x
x+ x = (x+ x) . 1------------------- by postulate 2(b) [ x. 1 = x ]
= (x+ x). (x+ x’)------------------- 5(a) [ x+ x’ = 1]
= x+ xx’------------------- 4(b) [ x+yz = (x+y)(x+z)]
= x+ 0------------------- 5(b) [ x. x’ = 0 ]
= x------------------- 2(a) [ x+0 = x ]
b) x. x = x
x. x = (x. x) + 0------------------- by postulate 2(a) [ x+ 0 = x ]
= (x. x) + (x. x’)------------------- 5(b) [ x. x’ = 0]
= x ( x+ x’)------------------- 4(a) [ x (y+z) = (xy)+ (xz)]
= x (1)------------------- 5(a) [ x+ x’ = 1 ]
= x------------------- 2(b) [ x.1 = x ]
2) a) x+ 1 = 1
x+ 1 = 1 . (x+ 1)------------------- by postulate 2(b) [ x. 1 = x ]
= (x+ x’). (x+ 1)------------------- 5(a) [ x+ x’ = 1]
= x+ x’.1------------------- 4(b) [ x+yz = (x+y)(x+z)]
= x+ x’------------------- 2(b) [ x. 1 = x ]
= 1------------------- 5(a) [ x+ x’= 1]
b) x .0 = 0
3) (x’)’ = x
From postulate 5, we have x+ x’ = 1 and x. x’ = 0, which defines the
complement of x. The complement of x’ is x and is also (x’)’.
Therefore, since the complement is unique,
(x’)’ = x.
4) Absorption Theorem:
a) x+ xy = x
3
Downloaded from EnggTree.com
, EnggTree.com
EC3352 DSD IIYR/III SEM R2021 MSAJCE/ECE
x+ xy = x. 1 + xy------------------- by postulate 2(b) [ x. 1 = x ]
= x (1+ y)------------------- 4(a) [ x (y+z) = (xy)+ (xz)]
= x (1)------------------- by theorem 2(a) [x+ 1 = x]
= x.------------------- by postulate 2(a) [x. 1 = x]
b) x. (x+ y) = x
x. (x+ y) = x. x+ x. y------------------- 4(a) [ x (y+z) = (xy)+ (xz)]
= x + x.y------------------- by theorem 1(b) [x. x = x]
= x.------------------- by theorem 4(a) [x+ xy = x]
c) x+ x’y = x+ y
x+ x’y = x+ xy+ x’y------------------- by theorem 4(a) [x+ xy = x]
= x+ y (x+ x’)------------------- by postulate 4(a) [ x (y+z) = (xy)+ (xz)]
= x+ y (1)------------------- 5(a) [x+ x’ = 1]
= x+ y------------------- 2(b) [x. 1= x]
Properties of Boolean algebra:
1. Commutative property:
Boolean addition is commutative, given by
x+ y = y+ x
According to this property, the order of the OR operation conducted on the
variables makes no difference.
Boolean algebra is also commutative over multiplication given by,
x. y = y. x
This means that the order of the AND operation conducted on the variables makes
no difference.
2. Associative property:
4
Downloaded from EnggTree.com
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller dhanushkumarjayaraman6. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $7.99. You're not tied to anything after your purchase.
