Boolean Algebra and Logic Gates for enginnering.pdf

Set Theory and Boolean Algebra
Boolean Algebra, Boolean Functions and Logic Gates
Juhi Kesarwani Ashish Kumar Kesarwany
Mathematics Division, School of Advanced Sciences and Languages
VIT Bhopal University, Bhopal-Indore Highway, Kothrikalan, Sehore, Madhya Pradesh, 466114, India
May 11, 2024
Juhi Kesarwani & Ashish Kumar Kesarwany (VITB) Set Theory and Boolean Algebra May 11, 2024

Table of Contents
1
Boolean Algebra
2
Boolean Expressions and Boolean Functions
3
Logic Gates
4
Exercise
Juhi Kesarwani & Ashish Kumar Kesarwany (VITB) Set Theory and Boolean Algebra May 11, 2024

Boolean Algebra
A Swith two distinct elements 0 and 1 which is
closed under the binary operations∨(called), ∧(called), and the unary
operation¬(called) satisfying the following properties (called
the) for all x,y,z∈S:
1.[Commutative laws]:
(a)x∨y=y∨x (b)x∧y=y∧x
2.[Distributive laws]:
(a)x∨(y∧z) = (x∨y)∧(x∨z) x∧(y∨z) = (x∧y)∨(x∧z)
3.[Identity laws]:
(a)x∨0 =x (b)x∧1 =x
4.[Complement or inverse laws]:
(a)x∨ ¬x= 1 x∧ ¬x= 0
Juhi Kesarwani & Ashish Kumar Kesarwany (VITB) Set Theory and Boolean Algebra May 11, 2024

Note
When required, we write the Boolean algebraSas (S,∨,∧,¬,0,1) showing the
operations explicitly.
Juhi Kesarwani & Ashish Kumar Kesarwany (VITB) Set Theory and Boolean Algebra May 11, 2024

Example
LetSbe a non-empty set. ThenP(S) is a Boolean algebra with∨=∪and
∧=∩,¬A=A
c
, 0 =ϕand 1 =S. This is called thepower set Boolean
algebra.
Example
TakeD30={n∈N:n|30}withx∨y= lcm(x,y),x∧y= gcd(x,y) and
¬x=
30
x
. It is a Boolean algebra with 0 = 1 and 1 = 30.
Juhi Kesarwani & Ashish Kumar Kesarwany (VITB) Set Theory and Boolean Algebra May 11, 2024

Example
TakeD8={1,2,4,8}withx∨y= lcm(x,y),x∧y= gcd(x,y) and¬x=
8
x
with
0 = 1 and 1 = 8. Show that (D8,∨,∧,¬,0,1) is not a Boolean algebra.
Solution
(1) Commutative Law:The following are the tables for∨,∧and¬:
∨1248
11248
22248
44448
88888
∧1248
11111
21222
41244
81244
¬1248
8421
From the tables it is clear that∀x,y∈D8,x∨y= lcm(x,y)∈D8andx∧y=
gcd(x,y)∈D8.∴∨and∧are binary operations.
The symmetry about the principal diagonal of first two tables indicates the com-
mutative laws hold.
Juhi Kesarwani & Ashish Kumar Kesarwany (VITB) Set Theory and Boolean Algebra May 11, 2024

Solution cont...
(2) Distributive laws:We verify distributive laws for 2, 4 and 8
2∨(4∧8) = 2∨4 = 4 and (2 ∨4)∧(2∨8) = 4∧8 = 4
Thus,
2∨(4∧8) = (2∨4)∧(2∨8)
and
2∧(4∨8) = 2∧8 = 2 and (2 ∧4)∨(2∧8) = 2∨2 = 2
Thus,
2∧(4∨8) = (2∧4)∨(2∧8)
Similarly, it may be verified for other cases.
Juhi Kesarwani & Ashish Kumar Kesarwany (VITB) Set Theory and Boolean Algebra May 11, 2024

Solution cont...
(3) Identity laws:
1∨1 = lcm(1,1) = 1,1∨2 = lcm(1,2) = 2,1∨4 = lcm(1,4) = 4,1∨8 = lcm(1,8) = 8
8∧1 = gcd(8,1) = 1,8∧2 = gcd(8,2) = 2,8∧4 = gcd(8,4) = 4,8∧8 = gcd(8,8) = 8
∴1 is the zero element and 8 is the unit element.
(4) Complement laws:
1∨ ¬1 = 1∨8 = lcm(1,8) = 8 and 1 ∧ ¬1 = 1∧8 = gcd(1,8) = 1
2∨ ¬2 = 2∨4 = lcm(2,4) = 4̸= 8 and 2 ∧ ¬2 = 2∧4 = gcd(2,4) = 2̸= 1
Thus, complement law is not true here. So, (D8,∨,∧,¬,0,1) is not a Boolean
algebra.
Juhi Kesarwani & Ashish Kumar Kesarwany (VITB) Set Theory and Boolean Algebra May 11, 2024

Result
LetDn={m∈N:m|n}withx∨y= lcm(x,y),x∧y= gcd(x,y) and¬x=
n
x
with 0 = 1 and 1 =n. Then (Dn,∨,∧,¬,0,1) is a Boolean algebra if number of
elements ofDnis of the form 2
t
, and none of the numbers are perfect squares.
Juhi Kesarwani & Ashish Kumar Kesarwany (VITB) Set Theory and Boolean Algebra May 11, 2024

Example
LetB={0,1}, where∨,∧and¬given in following tables, is a Boolean algebra,
calledtwo element Boolean algebra.
x¬x
10
01
Table 1:¬x
xyx∨y
111
101
011
000
Table 2:x∨y
xyx∧y
111
100
010
000
Table 3:x∧y
Juhi Kesarwani & Ashish Kumar Kesarwany (VITB) Set Theory and Boolean Algebra May 11, 2024

Laws of Boolean algebra
Letx,y,z∈S, then
1.[Idempotent laws]:
(a)x∨x=x (b)x∧x=x
2.[Boundedness or domination laws]:
(a)x∨1 = 1 x∧0 = 0
3.[Absorption laws]:
(a)x∨(x∧y) =x (b)x∧(x∨y) =x
4.[Associative laws]:
(a) x∨y)∨z=x∨(y∨z) x∧y)∧z=x∧(y∧z)
5[Involution law or law of double complement]:¬(¬x) =x.
6[De-Morgan’s laws]:
(a)¬(x∨y) = (¬x)∧(¬y) ¬(x∧y) = (¬x)∨(¬y)
Juhi Kesarwani & Ashish Kumar Kesarwany (VITB) Set Theory and Boolean Algebra May 11, 2024

Example
Prove idempotent laws, i.e., show thatx∨x=xandx∧x=x.
Solution
(a)
x=x∨0 Using Identity law
=x∨(x∧ ¬x) Using Complement law
= (x∨x)∧(x∨ ¬x) Using Distributive law
= (x∨x)∧1 Using Complement law
=x∨x Using Identity law
(b)
x=x∧1 Using Identity law
=x∧(x∨ ¬x) Using Complement law
= (x∧x)∨(x∧ ¬x) Using Distributive law
= (x∧x)∨0 Using Complement law
=x∧x Using Identity law
Juhi Kesarwani & Ashish Kumar Kesarwany (VITB) Set Theory and Boolean Algebra May 11, 2024

Example
Show thata∨1 = 1.
Solution
a∨1 =a∨(a∨ ¬a) Using Complement law
= (a∨a)∨ ¬a Using Associative law
=a∨ ¬a Using Idempotent law
= 1 Using Complement law
Juhi Kesarwani & Ashish Kumar Kesarwany (VITB) Set Theory and Boolean Algebra May 11, 2024

Example
Prove De-Morgan’s law, i.e., show that¬(x∨y) = (¬x)∧(¬y) and
¬(x∧y) = (¬x)∨(¬y).
Solution
(a)By complement law, it suffices to show that(x∨y)∨(¬x∧ ¬y) = 1.
(x∨y)∨(¬x∧ ¬y) = [(x∨y)∨ ¬x]∧[(x∨y)∨ ¬y]Distributive law
= [¬x∨(x∨y)]∧[x∨(y∨ ¬y)]Associative & Commutative
= [(¬x∨x)∨y)]∧[x∨1] Associative & complement
= [1∨y]∧1 Domination
= 1∧1 Domination
= 1 Identity
(b)Left for the reader to complete the proof.
Juhi Kesarwani & Ashish Kumar Kesarwany (VITB) Set Theory and Boolean Algebra May 11, 2024

Example
Find the value of (1∧0)∨ ¬(0∨1).
Solution
(1∧0)∨ ¬(0∨1) = 0∨ ¬1 Domination and identity
= 0∨0 Complement
= 0 Identity
Note
From now onwards we’ll denote
∨by+
∧by·
¬by¯
Juhi Kesarwani & Ashish Kumar Kesarwany (VITB) Set Theory and Boolean Algebra May 11, 2024

Boolean Expressions and Boolean Functions
Boolean Functions
LetB={0,1}. ThenB
n
={(x1,x2, . . . ,xn)|xi∈Bfor 1≤i≤n}is the set of
all possiblen-tuples of 0sand 1s. The variablexis called a
it assumes values only fromB, that is, if its only possible values are 0 and 1. A
function fromB
n
toBis called a n.
Boolean Expressions
Boolean functions can be represented using expressions made up from variables
and Boolean operations. The x1,x2, . . . ,xnare
defined recursively as
1.
2.x1,x2, . . . ,xnare Boolean expressions.
3. a1anda2are Boolean expressions, thena1,a1+a2anda1·a2are also
Boolean expressions.
4. x1,x2, . . . ,xnare those
that are determined by rules 1-3.
Juhi Kesarwani & Ashish Kumar Kesarwany (VITB) Set Theory and Boolean Algebra May 11, 2024

Example
The functionF:B
2
→Bdefined byF(x,y) =x·yis a Boolean function of
degree 2 withF(1,1) = 0,F(1,0) = 1,F(0,1) = 0, andF(0,0) = 0. The values
ofFare displayed in the table below.
xyF(x,y) =x·y
11 0
10 1
01 0
00 0
Table 4: F(x,y) =x·y
Juhi Kesarwani & Ashish Kumar Kesarwany (VITB) Set Theory and Boolean Algebra May 11, 2024

Example
Find the values of the Boolean function represented byF(x,y,z) =xy+z.
xyzx·yzF(x,y,z) =xy+z
11110 1
11011 1
01100 0
10100 0
10001 1
01001 1
00100 0
00001 1
Table 5: F(x,y) =xy+z
Juhi Kesarwani & Ashish Kumar Kesarwany (VITB) Set Theory and Boolean Algebra May 11, 2024

Duality
Duality
The
Boolean products and interchanging 0s and 1s, variables and complements are left
unchanged.
Example
Find the duals ofx(y+ 0) andx·1 + (y+z).
Solution
Interchanging·signs and + signs and interchanging 0s and 1s in these expressions
produces their duals. The duals arex+ (y·1) and (x+ 0)(yz), respectively.
Juhi Kesarwani & Ashish Kumar Kesarwany (VITB) Set Theory and Boolean Algebra May 11, 2024

Representing Boolean Functions
Sum of products form
A Boolean expressionEis said to be in a Eis a sum
of two or more product of variables (complemented or uncomplemented), none of
which is included in another.
Example
Some examples of this form are
1.xz+xyz+xyz
2.abc+ac+abc
3.xy+xyz+yz+w
Note
In a sum of product expression, one complementation sign can not cover more
than one variable in a term (e.g., we can not havexyzorabc).
Juhi Kesarwani & Ashish Kumar Kesarwany (VITB) Set Theory and Boolean Algebra May 11, 2024

Product of sums form
A Boolean expressionEis said to be in a product of sums form if it consists of
Boolean product of Boolean sums. The variables may or may not be complemented.
Example
Some examples of product of sums form are
1.x+y)(x+y)
2.x+y+z)(x+z)
3.a+b)(c+d)f
Juhi Kesarwani & Ashish Kumar Kesarwany (VITB) Set Theory and Boolean Algebra May 11, 2024

Definition(Literal)
A literal is a Boolean variable or its complement.
Definition(Minterm)
A minterm ofnvariables is a product ofnliterals in which each variable appears
exactly once in either true or complemented form, but not both ,i.e., A minterm of
the Boolean variablesx1,x2, . . . ,xnis a Boolean producty1y2· · ·yn, whereyi=xi
oryi=xi.
Example
1. xandyare
xy,xy,xy,¯x¯y
2 x,yandzare
xyz,xyz,xyz,xyz,x¯y¯z,¯x¯yz,xyz,¯x¯y¯z
3. nvariables can be combined to form 2
n
minterms.
Juhi Kesarwani & Ashish Kumar Kesarwany (VITB) Set Theory and Boolean Algebra May 11, 2024

Definition(Maxterm)
A maxterm ofnvariables is a sum ofnliterals in which each variable appears exactly
once in either true or complemented form, but not both ,i.e., A maxterm of the
Boolean variablesx1,x2, . . . ,xnis a Boolean sumy1+y2+· · ·+yn, whereyi=xi
oryi=xi.
Example
1. xandyare
x+y,x+y,x+y,x+y
2 x,yandzare
x+y+z,x+y+z,x+y+z,x+y+z,x+y+z,x+y+z,x+y+z,x+y+z
3. nvariables can be combined to form 2
n
maxterms.
Juhi Kesarwani & Ashish Kumar Kesarwany (VITB) Set Theory and Boolean Algebra May 11, 2024

Disjunctive normal form
Disjunctive normal form
If a Boolean functionfis written as a sum of minterms then it is called
normal form
ical sum of products.
Example
The following are disjunctive normal form of Boolean functions
1.f(x,y) =xy+xy
2.f(x,y,z) = ¯x¯yz+xyz+x¯y¯z+xyz
Juhi Kesarwani & Ashish Kumar Kesarwany (VITB) Set Theory and Boolean Algebra May 11, 2024

Conjuctive normal form
Conjuctive normal form
If a Boolean functionfis written as a product of maxterms then it is called
juctive normal form
canonical product of sums
Example
The following are conjuctive normal forms of the Boolean functions
1.f(x,y) = (x+y)(x+y)
2.f(x,y,z) = (x+y+z)(x+y+z)(x+y+z)(x+y+z)
Juhi Kesarwani & Ashish Kumar Kesarwany (VITB) Set Theory and Boolean Algebra May 11, 2024

Expression of a Boolean function as a normal form
A Boolean function can be expressed to DNF or CNF either using a truth table or
algebraically.
From a given truth table
When a Boolean function is given in form of a table then DNF can be obtained
from the truth table by the method described below:
(a)
and pick the row with 1 entry.
(b)
ANDing all the independent variables in the truth table.
(c)
is exhausted.
(d)
of dependent variables.
Juhi Kesarwani & Ashish Kumar Kesarwany (VITB) Set Theory and Boolean Algebra May 11, 2024

Remark
The method for finding CNF is similar, instead of picking the rows of 1 entry in the
dependent variable, the rows of 0 entry are to be picked up. The individual term is
formed by ORing of independent variables. The expression is obtained by ANDing
the individual terms.
Juhi Kesarwani & Ashish Kumar Kesarwany (VITB) Set Theory and Boolean Algebra May 11, 2024

Example
Find Boolean expression in DNF and CNF that represent the functionF(x,y,z),
which given in the Table below.
x1x2x3f(x1,x2,x3)
111 1
110 0
101 1
011 0
100 0
010 1
001 0
000 0
Juhi Kesarwani & Ashish Kumar Kesarwany (VITB) Set Theory and Boolean Algebra May 11, 2024

Solution
From the table it is clear that, output is 1 for the rows 1, 3 and 6. Consider the
first row of the table and combination isx1x2x3asx1=x2=x3= 1. Similarly, for
the third row, we can construct the combinationx1x2x3asx1= 1,x2= 0,x3= 1.
Thus, for the sixth row the combination isx1x2x3.
Therefore, the DNF of the Boolean function is given as
f(x1,x2,x3) =x1x2x3+x1x2x3+x1x2x3
Corresponding to 0 entries of the output column in the second, fourth, fifth, seventh,
eighth row the corresponding maxterms arex1+x2+x3,x1+x2+x3,x1+x2+x3,
x1+x2+x3,x1+x2+x3. Hence CNF of the Boolean function is
f(x1,x2,x3) = (x1+x2+x3)(x1+x2+x3)(x1+x2+x3)(x1+x2+x3)(x1+x2+x3)
Juhi Kesarwani & Ashish Kumar Kesarwany (VITB) Set Theory and Boolean Algebra May 11, 2024

Algebraic Method
To obtain DNF by algebraic method, first write the expression as a sum of products
and then introduce the missing variable in each term by applying the complement
lawa+a= 1.
For finding CNF, factor the function to obtain a product of sums, introduce missing
variable in each sum term by using complement lawaa= 0
Juhi Kesarwani & Ashish Kumar Kesarwany (VITB) Set Theory and Boolean Algebra May 11, 2024

Example
Express the Boolean functionf(x,y,z) =x+yzin DNF.
Solution
The function has three variablesx,yandz. The first term is missing two variables
and the second term is missing one variable; therefore applying complement law
a+a= 1
f(x,y,z) =x+yz=x(y+y) + (x+x)yz
=xy+xy+xyz+ ¯x¯yz
=xy(z+z) +xy(z+z) +xyz+ ¯x¯yz
=xyz+xyz+xyz+x¯y¯z+xyz+ ¯x¯yz
=xyz+xyz+xyz+x¯y¯z+ ¯x¯yz
Using idempotent lawxyz+xyz=xyz
Juhi Kesarwani & Ashish Kumar Kesarwany (VITB) Set Theory and Boolean Algebra May 11, 2024

Example
Express the Boolean functionf(a,b,c) =ab+acin CNF.
Solution
First convert the function into factor to obtain the product of sums forms by using
distributive law
f(a,b,c) =ab+ac
= (ab+a)(ab+c)
= (a+a)(b+a)(a+c)(b+c) = (b+a)(a+c)(b+c)
Now, since each term is missing one variable, applying the complement ruleaa= 0,
we get
f(a,b,c) = (b+a)(a+c)(b+c)
= (cc+b+a)(a+c+bb)(aa+b+c)
= (a+b+c)(a+b+c)(a+b+c)(a+b+c)(a+b+c)(a+b+c)
= (a+b+c)(a+b+c)(a+b+c)(a+b+c)
Juhi Kesarwani & Ashish Kumar Kesarwany (VITB) Set Theory and Boolean Algebra May 11, 2024

Conversion of DNF to CNF and vice-versa
Conversion of DNF to CNF
The following steps can be followed to convert a Boolean function given in DNF to
CNF
1. f.
2. f, which is the sum of those terms of the complete DNF in the variables
off, that are not present in the given function.
3. foff.
4. fby De-Morgan’s laws. This will transform the R.H.S.
into its CNF.
5. f=f, the R.H.S. is the required CNF of the given function in DNF.
Juhi Kesarwani & Ashish Kumar Kesarwany (VITB) Set Theory and Boolean Algebra May 11, 2024

Conversion of CNF to DNF
The following steps can be followed to convert a Boolean function given in CNF to
DNF
1. f.
2. f, which is the product of those terms of the complete CNF in the
variables off, that are not present in the given function.
3. foff.
4. fby De-Morgan’s laws. This will transform the R.H.S.
into its DNF.
5. f=f, the R.H.S. is the required DNF of the given function in CNF.
Juhi Kesarwani & Ashish Kumar Kesarwany (VITB) Set Theory and Boolean Algebra May 11, 2024

Example
Convert the Boolean functionf(x,y) =xy+xy+ ¯x¯yto its CNF.
Solution
Heref(x,y) =xy+xy+ ¯x¯y. The complete DNF in two variablesxandyis
xy+xy+xy+ ¯x¯y
Hence
f(x,y) =xy
So,
f(x,y) =xy=x+y
=⇒f(x,y) =x+y
which is required CNF of given function.
Juhi Kesarwani & Ashish Kumar Kesarwany (VITB) Set Theory and Boolean Algebra May 11, 2024

Example
Convert the Boolean functionf(x,y,z) = (x+y+z)(x+y+z)(x+y+z) in
DNF.
Solution
Heref(x,y,z) = (x+y+z)(x+y+z)(x+y+z). The complete CNF in three
variablesx,y, andzis
(x+y+z)(x+y+z)(x+y+z)(x+y+z)(x+y+z)(x+y+z)(x+y+z)(x+y+z)
Hence
f(x,y,z) = (x+y+z)(x+y+z)(x+y+z)(x+y+z)(x+y+z)
So,
f(x,y,z) =(x+y+z)(x+y+z)(x+y+z)(x+y+z)(x+y+z)
f(x,y,z) =(x+y+z) +(x+y+z) +(x+y+z) +(x+y+z) +(x+y+z)
f(x,y,z) = ¯x¯y¯z+ ¯x¯yz+xyz+xyz+xyz
which is the required DNF of given function.
Juhi Kesarwani & Ashish Kumar Kesarwany (VITB) Set Theory and Boolean Algebra May 11, 2024

Logic Gates
Boolean algebra is used to model the circuitry of electronic devices. Each input and
each output of such a device can be thought of as a member of the set{0,1}. A
computer, or other electronic device, is made up of a number of circuits. Each circuit
can be designed using the rules of Boolean algebra that were studied in previous
sections. The basic elements of circuits are called. The block diagrams for
different gates are discussed below:
1.A NOT GATE
A x, wherexis a bit (binary digit) and produces
outputxwhere
x=
(
1 if x= 0
0 if x= 1
Figure 1:
The output state is always the opposite of the input state.
Juhi Kesarwani & Ashish Kumar Kesarwany (VITB) Set Theory and Boolean Algebra May 11, 2024

2.AN AND GATE
An xandy, wherexandyare bits and produces
outputx·y, where
x·y=
(
1 if x=y= 1
0 otherwise
Figure 2:Figure 3: ninputs
Juhi Kesarwani & Ashish Kumar Kesarwany (VITB) Set Theory and Boolean Algebra May 11, 2024

3.AN OR GATE
An xandy, wherexandyare bits and produces
outputx+y, where
x+y=
(
1 if x= 1,ory= 1
0 otherwise
Figure 4:Figure 5: ninputs
Juhi Kesarwani & Ashish Kumar Kesarwany (VITB) Set Theory and Boolean Algebra May 11, 2024

Two more gates
1.NOR GATE
A xand
y, wherexandyare bits and
produces outputx+y, where
x+y=
(
1 if x=y= 0
0 otherwise
Figure 6:
According to De-Morgan’s law
x+y=x·y
2.NAND GATE
A xand
y, wherexandyare bits and
produces outputx·y, where
x·y=
(
1 if x= 0 ory= 0
0 otherwise
Figure 7:
According to De-Morgan’s law
x·y=x+y
Juhi Kesarwani & Ashish Kumar Kesarwany (VITB) Set Theory and Boolean Algebra May 11, 2024

Combinations of Gates
Combinational circuits can be constructed using a combination of NOT gates, OR
gates, and AND gates. When combinations of circuits are formed, some gates
may share inputs. One method is to use branchings that indicate all the gates
that use a given input. The other method is to indicate this input separately for
each gate. The following figure illustrates the two ways of showing gates with the
same input values.
Figure 8:
Juhi Kesarwani & Ashish Kumar Kesarwany (VITB) Set Theory and Boolean Algebra May 11, 2024

Example
Construct circuits that produce the following outputs:
(a) x+y)x
(b)x(y+z)
(c) x+y+z)¯x¯y¯z
Solution
Circuits that produce these outputs are shown in the figure below.
(a)
Figure 9:Circuit representing(x+y)x
Juhi Kesarwani & Ashish Kumar Kesarwany (VITB) Set Theory and Boolean Algebra May 11, 2024

(b)
Figure 10: x(y+z)
(c)
Figure 11: x+y+z)¯x¯y¯z
Juhi Kesarwani & Ashish Kumar Kesarwany (VITB) Set Theory and Boolean Algebra May 11, 2024

Example
A committee of three individuals decides issues for an organization. Each individual
votes either yes or no for each proposal that arises. A proposal is passed if it receives
at least two yes votes. Design a circuit that determines whether a proposal passes.
Solution
Letx,y, andzbe three individuals. We denote a yes vote by 1 and a no vote by
0 and output 1 for the proposal of the bill. To accomplish this, we require a circuit
that satisfies the following truth table:
xyzpass
1111
1101
1011
0111
1000
0100
0010
0000
Table 6:
Juhi Kesarwani & Ashish Kumar Kesarwany (VITB) Set Theory and Boolean Algebra May 11, 2024

Solution cont...
The Boolean expression (DNF) corresponding to this truth table is
xyz+xyz+xyz+xyz. Now
f(x,y,z) =xyz+xyz+xyz+xyz
=xy(z+z) +xyz+xyz
=xy+xyz+xyz Complementation law:z+z= 1
=xy+xyz+xyz+xyzbecausexy+xyz=xy(1 +z) =xy.1 =xy
=xy+xz(y+y) +xyz
=xy+xz+xyz Complementation law:y+y= 1
=xy+xz+xyz+xyz becausexz+xyz=xz(1 +y) =xz.1 =xz
=xy+xz+yz(x+x)
=xy+yz+zx Complementation law:x+x= 1
The circuit that implements this function is shown in the figure below.
Juhi Kesarwani & Ashish Kumar Kesarwany (VITB) Set Theory and Boolean Algebra May 11, 2024

Solution cont...
Figure 12:
Juhi Kesarwani & Ashish Kumar Kesarwany (VITB) Set Theory and Boolean Algebra May 11, 2024

Example
Construct an AND gate using three NOR gates
Solution
Juhi Kesarwani & Ashish Kumar Kesarwany (VITB) Set Theory and Boolean Algebra May 11, 2024

Example
Construct an OR gate using three NAND gates
Solution
Juhi Kesarwani & Ashish Kumar Kesarwany (VITB) Set Theory and Boolean Algebra May 11, 2024

Exercise 1:
Find Boolean expressions that represent the functionsF(x,y,z) andG(x,y,z),
which are given in the Table below.
xyzF(x,y,z)G(x,y,z)
111 0 0
110 0 1
101 1 0
011 0 0
100 0 0
010 0 1
001 0 0
000 0 0
Exercise 2:
Show thatF(x,y,z) =xy+xz+yzhas the value 1 if and only if at least two of
the variablesx,y, andzhave the value 1.
Exercise 3:
Show thatxy+yz+xz=xy+yz+xz.
Juhi Kesarwani & Ashish Kumar Kesarwany (VITB) Set Theory and Boolean Algebra May 11, 2024

Exercise 4:
Show that the combinatorial circuits (a) and (b) are equivalent.
Juhi Kesarwani & Ashish Kumar Kesarwany (VITB) Set Theory and Boolean Algebra May 11, 2024

Exercise 5:
Given the Boolean functionf, writefin its CNF.
xyzf(x,y,z)
111 1
110 1
101 0
011 0
100 0
010 1
001 0
000 1
Ans:CNF : (x+y+z)(x+y+z)(x+y+z)(x+y+z)(x+y+z)
Juhi Kesarwani & Ashish Kumar Kesarwany (VITB) Set Theory and Boolean Algebra May 11, 2024

Exercise 6:
Find the DNF and CNF of the given function and find the combinatorial circuit
corresponding to DNF.
xyzf(x,y,z)
111 0
110 0
101 0
011 1
100 1
010 1
001 1
000 0
Ans:DNF :f(x,y,z) =xyz+x¯y¯z+xyz+ ¯x¯yz,
CNF :f(x,y,z) = (x+y+z)(x+y+z)(x+y+z)(x+y+z)
Juhi Kesarwani & Ashish Kumar Kesarwany (VITB) Set Theory and Boolean Algebra May 11, 2024

Exercise 7:
Find the DNF of the function using algebraic techniquef(x,y) = (x+y)(x+y)
Ans:DNF :f(x,y) =xy+xy
Exercise 8:
Find the DNF for the following combinatorial circuit
Ans:DNF :f(x,y,z) =xyz+xyz
Juhi Kesarwani & Ashish Kumar Kesarwany (VITB) Set Theory and Boolean Algebra May 11, 2024

Exercise 9:
Find DNF and CNF of each of the following Boolean functions using algebraic
technique
(a)f(x,y) =x+xy
(b)f(x,y,z) =x+y(x+z)
(c)f(x,y,z) =x+ (y+ (xy+xz))
Exercise 10:
Draw the logic circuit with inputsx,y,zand outputYwhich corresponds to
each Boolean expression
(a)Y=xyz+xyz+xyz
(b)Y=xyz+xz+yz
Juhi Kesarwani & Ashish Kumar Kesarwany (VITB) Set Theory and Boolean Algebra May 11, 2024

Exercise 11:
find the output of the given circuit.
Juhi Kesarwani & Ashish Kumar Kesarwany (VITB) Set Theory and Boolean Algebra May 11, 2024

Exercise 12:
Construct circuits from NOT gates, AND gates, and OR gates to produce these
outputs.
(a)x+y
(b)(x+y)x
(c)xyz+ ¯x¯y¯z
(d)(x+z)(y+z)
Exercise 13:
Find the DNF of these Boolean functions
(a)F(x,y,z) =x+y+z
(b)F(x,y,z) = (x+z)y
(c)F(x,y,z) =x
(d)F(x,y,z) =xy
Juhi Kesarwani & Ashish Kumar Kesarwany (VITB) Set Theory and Boolean Algebra May 11, 2024

Exercise 14:
Find the DNF of the Boolean functionF(x,y,z) that equals 1 if and only if
(a)x= 0
(b)xy= 0
(c)x+y= 0
(d)xyz= 0
Exercise 15:
Use truth table to show that (A+B)(A+C) =A+BC
Exercise 16:
Simplify the following expression using Boolean algebra:
(a) A¯B¯C+ABC+ABC+ABC)(A+B)
(b)P+PQR+(Q+R)
Exercise 17:
Express the functionsf(x,y,z) =x(yz) andg(x,y,z) = (x+y)(x+z) +y+z
in DNF.
Juhi Kesarwani & Ashish Kumar Kesarwany (VITB) Set Theory and Boolean Algebra May 11, 2024

Exercise 18:
Show that the complete DNF and complete CNF in three variables in a Boolean
algebra is equal to 1 and 0 respectively.
Exercise 19:
Use NAND gates to construct circuits with these outputs.
a)x b)x+y c)xy
Exercise 20:
Use NOR gates to construct circuits with these outputs.
a)x b)x+y c)xy
Exercise 21:
LetA,B,Crepresent three switches in “ON” position andA,B,Crepresent the
same three switches in “OFF” position. Construct a switching circuit representing
the Boolean expression (A+B)·(A+C) +B·(B+C). Using the laws of
Boolean algebra, show that above expression is equivalent toAC+B& construct
a switching circuit.
Juhi Kesarwani & Ashish Kumar Kesarwany (VITB) Set Theory and Boolean Algebra May 11, 2024

Exercise 22:
Find the CNF and DNF forf(x,y,z) = (x+y)zand draw its logical circuit too.
Juhi Kesarwani & Ashish Kumar Kesarwany (VITB) Set Theory and Boolean Algebra May 11, 2024

Boolean Algebra and Logic Gates for enginnering.pdf

About This Presentation

Slide Content

Tags

Categories

Download

Quick Actions

Statistics

Related Slideshows

Boolean Algebra and Logic Gates for enginnering.pdf

About This Presentation

Slide Content

Slide 1

Slide 2

Slide 3

Slide 4

Slide 5

Slide 6

Slide 7

Slide 8

Slide 9

Slide 10

Slide 11

Slide 12

Slide 13

Slide 14

Slide 15

Slide 16

Slide 17

Slide 18

Slide 19

Slide 20

Slide 21

Slide 22

Slide 23

Slide 24

Slide 25

Slide 26

Slide 27

Slide 28

Slide 29

Slide 30

Slide 31

Slide 32

Slide 33

Slide 34

Slide 35

Slide 36

Slide 37

Slide 38

Slide 39

Slide 40

Slide 41

Slide 42

Slide 43

Slide 44

Slide 45

Slide 46

Slide 47

Slide 48

Slide 49

Slide 50

Slide 51

Slide 52

Slide 53

Slide 54

Slide 55

Slide 56

Slide 57

Slide 58

Slide 59

Slide 60

Slide 61

Slide 62

Slide 63

Slide 64

Slide 65

Slide 66

Slide 67

Slide 68

Slide 69

Slide 70

Slide 71

Slide 72

Slide 73

Slide 74

Slide 75

Slide 76

Slide 77