Scribd
Upload
51 views6 pages

Unit 3 Boolean Algebra and Switching Circuits

boolean-algebra-and-switching-circuits

Uploaded by

shraddha_mundadada
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
51 views6 pages

Unit 3 Boolean Algebra and Switching Circuits

boolean-algebra-and-switching-circuits

Uploaded by

shraddha_mundadada
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 6

lOMoARcPSD|23064267

Unit 3 Boolean Algebra and Switching Circuits

Data Structures (Delhi Technological University)

Scan to open on Studocu

Studocu is not sponsored or endorsed by any college or university


Downloaded by shraddha mundada (shraddha.mundada12@gmail.com)
lOMoARcPSD|23064267

Unit 3: Boolean Algebra and Switching Circuits


3.1 Introduction
Both sets and propositions have been found to have similar properties and satisfy the
same theorems and laws. Specifically, any propositions P, Q and R can be substituted
by the sets A, B and C while the symbols ú, ù can respectively be substituted by the
set operations ø, ÷. In this Unit we state the laws that define a mathematical structure
called a Boolean Algebra. We then prove basic theorems based on these laws. We
complete the discussion by considering switching circuit designs.
Objectives
By the end of the Unit you should be able to
(a) Define a Boolean Algebra
(b) Prove basic Boolean Algebra theorems
(c) Apply Boolean Algebra in switching circuit designs

3.2 Boolean Algebra


3.2.1 Definition: A Boolean algebra is a set B of elements a, b, c, … and two binary
operations called sum and product, denoted respectively by + and ú respectively,
such that
B0 Closure law: For any a, b þ B , a û b þ B & a ú b þ B ; a û b , a ú b are unique
elements of B.
B1 Commutative law: (1a) a û b ý b û a (1b) a ú b ý b ú a
B2 Associative law: (2a) ( a û b) û c ý a û (b û c) (2b) ( a ú b) ú c ý a ú (b ú c)
B3 Distributive law:
(3a) a û (b ú c) ý (a û b) ú ( a û c) (3b) a ú (b û c) ý (a ú b) û (a ú c)
B4 Identity law: There exist an additive identity 0 and a multiplicative identity 1 in B
such that for any a þ B , (4a) a û 0 ý a (4b) a ú 1 ý a
B5 Complement law: For any a þ B , there exist an element a'þ B called the
complement of a such that (5a) a û a' ý 1 (5b) a ú a' ý 0
Remark: Note that, by definition, a binary operation satisfies the closure law; hence
axiom B0 need not have been explicitly stated.
3.2.2 Example
Let A be a family of sets which is closed under the operations of union, intersection
and complement. Then (A ,ø,÷) is a Boolean algebra. Note that the universal set is
the unit element and the null set is the zero element.
3.2.3 Example
Let B be the set of propositions generated by the variables p, q, … . Then (B ,ú ,ù ) is
a Boolean algebra.
Remark: Since sets and propositions are classical examples of Boolean algebras,
many authors denote the operations of a Boolean algebra by ú and ù or by ø and ÷.
3.2.4 Definition
The dual of any statement in a Boolean algebra ( B,û,ú) is the statement that is
derived by interchanging + and ú and their identity elements 1 and 0 in the original
statement.

17

Downloaded by shraddha mundada (shraddha.mundada12@gmail.com)


lOMoARcPSD|23064267

As an example, the dual of De Morgan9s law: ( a û b)' ý a 'ú b' is ( a ú b)' ý a'ûb'
Note: The dual of each axiom of a Boolean algebra is also an axiom, and this leads us
to the following theorem.
3.2.5 Theorem
The dual of any theorem in a Boolean algebra is also a theorem.
In other words, if any statement is a result of the axioms of a Boolean algebra, then
the dual is also a result of these axioms since the dual statement can be proved using
the dual of each step of the proof of the original statement.
3.2.5 Basic theorems
The five axioms in 3.2.1 do not include all the properties of sets and propositions
discussed in earlier units. However, the other properties are a direct result of the
axioms and these are listed as theorems as follows.
1 (Idempotent law) (i ) a û a ý a (ii) a ú a ý a
2 (i ) a û 1 ý 1 (ii) a ú 0 ý 0
3 (Involution law) ( a' )' ý a
4 (i) 1' ý 0 (ii) 0' ý 1
5 ( DeMorgan’s Law) (i) ( a û b)' ý a 'ú b' and (ii) ( a ú b)' ý a 'û b'

Proofs:
1(i) a ý a û 0 Identity law
ý a û (a ú a ' ) Complement law
ý (a û a) ú (a û a' ) Distributive law
ý (a û a) ú 1 Complement law
=aûa Identity law

(ii) a ý a ú1 Identity law


ý a ú (a û a' ) Complement law
ý (a ú a) û (a ú a' ) Distributive law
ý (a ú a) û 0 Complement law
=aúa Identity law
Notice that we could have used the principle of duality to derive the proof of 1(ii)
from the proof of 1(i).
2(i) a û 1 ý a û (a û a ' )
ý (a û a) û a'
ý a û a'
=1

3.3 Switching Networks


In this section, we shall discuss an important practical application of symbolic logic in
electrical engineering. The algebra of logic plays a significant role in the design of
switching networks which are concerned with the flow of current through various
switches and wires.
A switching network is an arrangement of wires and switches connecting two
terminals, as shown below. A switch that permits the flow of current is said to be
closed, or on as shown in figure 3.1(b), otherwise it is open, or off as shown in figure
3.1(a). A switching network is closed if current can flow from one end of the network
to the other and open otherwise.

  
18

Downloaded by shraddha mundada (shraddha.mundada12@gmail.com)


lOMoARcPSD|23064267

   
Figure 3.1(a) Open switch Figure 3.1(b) Closed switch

Two switches A and B can be connected in series or in parallel as shown below.

A
 A B 
 
B

Figure 3.2(a) series connection Figure 3.2(b) parallel connection

Notice that the circuit in Figure 3.2(a) is closed if both switch A and B are closed, and
open if at least one of them is open. Notice the similarity between this and the logical
operation of conjunction of two statements: The conjunction p ù q of two statements
p and q is true if both p and q are true, and false if at least one of them is false.
Accordingly, the switching circuit in (a) is denoted by A ù B
It is clear from Figure 3.2(b) that the network will permit the flow of current if either
A or B is closed or if both are closed. Because of the analogy between this and the
logical operation of disjunction, the switching circuit in (b) above is denoted by
Aú B.
An electrical network may also have two switches A and A' with the property that if
A is closed then A' is open.
A Boolean switching circuit design, in general, consists of series and parallel
connections and can be described symbolically using the connectives ù ,ú , '
3.3.1 Example
Describe the circuits below symbolically.

B
(a)
 A 

A'

b) A B'

 
A'

19

Downloaded by shraddha mundada (shraddha.mundada12@gmail.com)


lOMoARcPSD|23064267

In circuit (a) switches B and A' are in parallel and so we can write B ú A' for the
small circuit they form. Now switch A is in series with B ú A' and so we can finally
describe circuit (a) by A ù ( B ú A' ) . Using the same argument circuit (b) can be
described by ( A ù B' ) ú [( A'úC ) ù B] .
Now let 1 and 0 denote, respectively, that a switch or circuit is on and that a switch or
circuit is off. The next two tables describe the behaviour of a series circuit A ù B and
parallel circuit A ú B .

A B AùB
1 1 1
1 0 0
0 1 0
0 0 0

A B AúB
1 1 1
1 0 1
0 1 1
0 0 0

The next table shows the relationship between a switch A and a switch A' .

A A'
1 0
0 1

Notice that the above three tables are identical with the tables for conjunction,
disjunction and negation for statements (and propositions). The only difference is that
1 and 0 are used here instead of T and F.
3.3.2 Theorem
The algebra of Boolean switching circuits is a Boolean algebra.
In order to find the behaviour of a Boolean switching circuit, a table is constructed
which is analogous to the truth tables for propositions
3.3.3 Example
Consider circuit (1) in Example 3.3.1. What is the behaviour of the circuit, that is,
when will the circuit be on (i.e. when will current flow) and when will the circuit be
off? A truth table is constructed for A ù ( B ú A' ) as follows:

A B A' B ú A' A ù ( B ú A' )


1 1 0 1 1
1 0 0 0 0
0 1 1 1 0
0 0 1 1 0

The current will flow only if both A and B are on.

20

Downloaded by shraddha mundada (shraddha.mundada12@gmail.com)


lOMoARcPSD|23064267

Exercises

Q1 Prove theorems 3.1.5 - 2(ii), 3, 4, 5


Q2 Construct a switching circuit for each of the symbolic representations
(a) ( A ú B ) ù A'
(b) A ú ( B ù C )
(c) ( A ú B ) ù ( A ú C )
(d) ( A ù B' ) ú ( A ú B)
(e) ( A ù B ' ) ú ( A' ù B )
(f) ( A ú B) ù [ A'ú (C ù B' )
(g) ( A ù B ' ) ú B ú ( A'ù B )

21

Downloaded by shraddha mundada (shraddha.mundada12@gmail.com)

You might also like