UNIT 3: Boolean Algebra of Switching Circuits: - Introduction - Elements of Boolean Algebra - Basic

Postulates of Boolean Algebra - Boolean Operations - Principle of Duality - Basic Laws of Boolean Algebra -
De Morgan’s Theorem – Boolean Expressions. Logic Gates and Digital Circuits: - Introduction - Basic Logic
Gates - Derived Logic Gates - Conversion of Boolean Functions - Adder Circuits – Flipflop Circuits - Application
of Flip-flops. Computer Software: - Introduction - Types of Computer Software - System Management
Programs – System Development Programs - Standard Application Programs - Unique Application Programs -
Problem-Solving - Structuring the Logic - Using the Computer.

Introduction:

• An algebra that deals with binary number system is called “Boolean Algebra”.
• It is very power in designing logic circuits used by the processor of computer system.
• The logic gates are the building blocks of all the circuit in a computer.
• Boolean algebra derives its name from the mathematician George Boole (1815-1864) who isconsidered
the “Father of symbolic logic”.
• Boolean algebra deals with truth table TRUE and FALSE.
• It is also called as “Switching Algebra”.

Binary Valued Quantities – Variable and Constants:

• A variable used in Boolean algebra or Boolean equation can have only one of two variables.The two
values are FALSE (0) and TRUE (1)
• A Sentence which can be determined to be TRUE or FALSE are called logical statements or
truth functions and the results TRUE or FALSE is called Truth values.
• The variables which can store the truth values are called logical variables or binary valuedvariables.
These can store one of the two values 1 or 0.
• The decision which results into either YES (TRUE or 1) or NO (FALSE or 0) is called Binarydecision.

Truth Table:

• A truth table is a mathematical table used in logic to computer functional values of logical
expressions.
• A truth table is a table whose columns are statements and whose rows are possible scenarios.
• Example: Consider the logical expression
Logical Statement: Meals = “Ram prefer rice and roti for the meal”
Y = A AND B (Logical Variables: Y, A, B, Logical Operator AND)

Ram Prefer Rice Ram Prefer Roti Meals

FALSE FALSE FALSE
FALSE TRUE FALSE
TRUE FALSE FALSE
TRUE TRUE TRUE
• If result of any logical statement or expression is always TRUE or 1, it is called Tautology andif the
result is always FALSE or 0, it is called Fallacy.

Logical Operators:

• There are three logical operator, NOT, OR and AND.

• These operators are now used in computer construction known as switching circuits.

NOT Operator:
• The Not operator is a unary operator. This operator operates on single variable.
• The operation performed by Not operator is called complementation.
• The symbol we use for it is bar.
• ̅𝐗 means complementation of X

• If X=1, ̅X=0 If X=0, ̅X=1

• The Truth table and the Venn diagram for the NOT operator is:
X ̅X
1 0
0 1

OR Operator:
• The OR operator is a binary operator. This operator operates on two variables.
• The operation performed by OR operator is called logical addition.
• The symbol we use for it is ‘+’.
• Example: X + Y can be read as X OR Y
• The Truth table and the Venn diagram for the NOT operator is:
X Y X+Y
0 0 0
0 1 1
1 0 1
1 1 1

AND Operator:
• The AND operator is a binary operator. This operator operates on two variables.
• The operation performed by AND operator is called logical multiplication.
• The symbol we use for it is ‘.’.

• Example: X . Y can be read as X AND Y

• The Truth table and the Venn diagram for the NOT operator is:
X Y X.Y
0 0 0
0 1 0
1 0 0
1 1 1

Evaluation of Boolean Expression using Truth Table:

• To create a truth table, follow the steps given below.

• Step 1: Determine the number of variables, for n variables create a table with 2n rows.
o For two variables i.e. X, Y then truth table will need 22 or 4 rows.
o For three variables i.e. X, Y, Z, then truth table will need 23 or 8 rows.
• Step 2: List the variables and every combination of 1 (TRUE) and 0 (FALSE) for the givenvariables
• Step 3: Create a new column for each term of the statement or argument.
• Step 4: If two statements have the same truth values, then they are equivalent.

Example: Consider the following Boolean Expression F=X+ ̅𝐘

• Step 1: This expression as two variables X and Y, then 22 or 4 rows.
• Step 2: List the variables and every combination of X and Y.
• Step 3: Create a new column ̅𝐘of the statement, and then fill the truth values of Y in that column.
• Step 4: The final column contain the values of X+ .̅𝐘

X Y ̅Y X+ ̅𝐘
0 0 1 1
0 1 0 0
1 0 1 1
1 1 0 1

Exercise Problems:
1. Prepare a table of combination for the following Boolean algebra expressions.
a) X
̅ Y +̅ X
Y b) XY Z̅ + ̅X ̅Y Z
2. Verify using truth table for the following Boolean algebra.
a) X + XY = X b) ̅̅ X
̅ = ̅X . ̅Y
Y
+
Boolean Postulates:

• The fundamental laws of Boolean algebra are called as the postulates of Boolean algebra.
• These postulates for Boolean algebra originate from the three basic logic functions AND, ORand NOT.
• Properties of 0 and 1:
I. If X ≠ 0 then X = 1, and If X ≠1 then X = 0
II. OR relation ( Logical Addition)
a. 0 + 0 = 0 c. 1 + 0 = 1
b. 0 + 1 = 1 d. 1 + 1 = 1
III. AND relation ( Logical Multiplication)a. 0
.0=0 c. 1 . 0 = 0
b. 0 . 1 = 0 d. 1 . 1 = 1

IV. Complement Rules

a. ̅0= 1 b. ̅1= 0
Principle of Duality Theorem:

• This is very important principle used in Boolean algebra.

• Principle of Duality states that;
o Changing each OR sign (+) to an AND sign (.)
o Changing each AND sign (.) to an OR sign (+)
o Replacing each 0 by 1 and each 1 by 0.
• The derived relation using duality principle is called dual of original expression.
• Example: Take postulate II, related to logical addition:
1) 0 + 0 = 0 2) 0 + 1 = 1 3) 1 + 0 = 1 4) 1 + 1 = 1
2. Now working according to above relations, + is changed to . and 0’s replaced by 1’sa) 1 . 1 =
1 b) 1 . 0 = 0 c) 0 . 1 = 0 d) 0 . 0 = 0
• which are nothing but same as that of postulate III related to logical multiplication.
• So 1, 2, 3, 4, are the duals of a, b, c, d.
• Example: Find the duals for the following Boolean Expression

Sl No Boolean Expression Duals

1 X+0=X X.1=X
2 X+1=1 X.0=0
3 X . ̅X = 0 X + ̅X = 1
4 X . ( Y + Z) X + ( Y . Z)
5 X + X.Y = X + Y X.(X + Y) = X.Y
 Boolean Theorems:

• Boolean Theorem can be proved by substituting all possible values of the variable that are 0and 1.
• This technique of proving theorem is called Proof by perfect induction.

Sl No Theorem Sl No Theorem
Properties of 0 and 1 Associative Law
1 0+X=X 12 X .(Y.Z) = (X.Y).Z
2 1+X=1 13 (X+Y).Z = X+(Y.Z)
3 0.X=0 Distributive Law
4 1.X=X 14 X.(Y+Z) = X.Y + X.Z
Indempotence Law 15 X+Y.Z = (X+Y).(X+Z)
5 X+X=X Absorption Law
6 X.X=X 16 X + XY = X
Complementary Law 17 X(X+Y) = X
7 X + ̅X = 1 18 XY + X̅Y = X
8 X . ̅X = 0 19 (X+Y)(X+̅Y)= X
Involution Law 20 X+̅XY = X+Y
9 "
X=X 21 X(̅X+Y) = XY

Commutative Law
10 X+Y=Y+X
11 X.Y=Y.X
Theorem 1: 0+X=X

Proof: If X = 0 Proof: If X = 1 Using Truth Table

then LHS =0+X then LHS =0+X 0+X
0 X
=0+0 =0+1 0 0 0
=0 =1 0 1 1
= RHS = RHS

Theorem 2: 1+X=1

Proof: If X = 0 Proof: If X = 1 Using Truth Table

then LHS =1+X then LHS =1+X 1+X
1 X
=1+0 =1+1 1 0 1
=1 =1 1 1 1
= RHS = RHS

5|Page Keerthi Kumar H.M

Theorem 3: 0.X=0

Proof: If X = 0 Proof: If X = 1 Using Truth Table

then LHS =0.X then LHS =0.X 0.X
0 X
=0.0 =0.1 0 0 0
=0 =0 0 1 0
= RHS = RHS

Theorem 4: 1.X=X

Proof: If X = 0 Proof: If X = 1 Using Truth Table

then LHS =1.X then LHS =1.X 0.X
1 X
=1.0 =1.1 1 0 0
=0 =1 1 1 1
= RHS = RHS

Indempotence Law: “This law states that when a variable is combines with itselfusing OR or AND
operator, the output is the same variable”.

Theorem 5: X+X=X

Proof: If X = 0 Proof: If X = 1 Using Truth Table

then LHS =X+X then LHS =X+X X+X
X X
=0+0 =1+1 0 0 0
=0 =1 1 1 1
= RHS = RHS

Theorem 6: X.X=X

Proof: If X = 1 Using Truth Table

Proof: If X = 0 =X.X
then LHS
X X X.X
then LHS =X.X =1.1
0 0 0
=0+0 =1
1 1 1
=0 = RHS

= RHS

Complementary Law: “This law states that when a variable is And ed with itscomplement is equal
to 0 and a variable is OR ed with its complement is equal to 1”.
Theorem 7: X + ̅𝐗= 1

Proof: If X = 0 Proof: If X = 1 Using Truth Table

then LHS = X + ̅X then LHS = X + ̅X X + ̅𝐗
X ̅𝐗
=0+1 =1+0 1
0 1
=1 =1 1
1 0
= RHS = RHS

Theorem 8: X . ̅𝐗= 0

Proof: If X = 0 Proof: If X = 1 Using Truth Table

then LHS = X . ̅X then LHS = X . ̅X ̅𝐗 X . ̅𝐗
X
=0.1 =1.0 0
0 1
=0 =0 1 0 0
= RHS = RHS

Involution Law: “This law states that when a variable is inverted twice is equal tothe original variable”.
Theorem 9: "
𝐗=X

Proof: If X = 0, then ̅X = 1 Using Truth Table

Take complement again, then "X = 0 i.e. X If
X ̅𝐗 "
𝐗
X = 1, then ̅X = 0
0 1 0
Take complement again, then "X = 1 i.e. X
1 0 1

Commutative Law: “This law states that the order in which two variable are Or edor AND ed make no
difference”.

Theorem 10: X+Y=Y+X

Proof: If Y = 0 Proof: If Y = 1 Using Truth Table

then LHS =X+Y then LHS =X+Y
X Y X+Y Y+X
=X+0 =X+1
0 0 0 0
=X =1
0 1 1 1
RHS =Y+X RHS =Y+X
1 0 1 1
=0+X =1+X
1 1 1 1
=X =1
Therefore LHS = RHS Therefore LHS = RHS
Theorem 11: X.Y=Y.X

Proof: If Y = 0 Proof: If Y = 1 Using Truth Table

then LHS =X.Y then LHS =X.Y
X Y X.Y Y.X
=X.0 =X.1
0 0 0 0
=0 =X
0 1 0 0
RHS =Y.X RHS =Y.X
1 0 0 0
=0.X =1.X
1 1 1 1
=0 =X
Therefore LHS = RHS Therefore LHS = RHS

Associative Law: “This law allows the removal of brackets from an expression andregrouping of the
variables”.

Theorem 12: X.(Y.Z) = (X.Y).Z

Proof: If Y = 0 Proof: If Y = 1 Using Truth Table

LHS = X.(Y.Z) LHS = X.(Y.Z)
X Y Z XY YZ X.(Y.Z) (X.Y).Z
= X.(0.Z) = X.(1.Z)
0 0 0 0 0 0 0
= X.0 = X.Z
0 0 1 0 0 0 0
=0 = XZ RHS
RHS = (X.Y).Z = (X.Y).Z 0 1 0 0 0 0 0

= (X.0).Z = (X.1).Z 0 1 1 0 1 0 0

= 0.Z = X.Z 1 0 0 0 0 0 0
=0 = XZ 1 0 1 0 0 0 0
Therefore LHS = RHS Therefore LHS = RHS 1 1 0 1 0 0 0
1 1 1 1 1 1 1
Theorem 13: X+(Y+Z) = (X+Y)+Z
Proof: If Y = 0 Proof: If Y = 1 Using Truth Table
LHS = X+(Y+Z) LHS = X+(Y+Z)
= X+(0+Z) = X+(1+Z) X Y Z X+Y Y+Z X+(Y+Z) (X+Y)+
0 0 0 0 0 0 Z
= X+Z = X+1 0
0 0 1 0 1 1
=1 1
0 1 0 1 1 1
RHS = (X+Y)+Z RHS = (X+Y)+Z 1
0 1 1 1 1 1
= (X+0)+Z = (X+1).Z 1 0 0 1 0 1 1
= X+Z = 1+Z 1 0 1 1 1 1 1
Therefore LHS = RHS =1 1 1 0 1 1 1 1
Therefore LHS = RHS 1 1 1 1 1 1 1
1
Distributive Law: “This law allows the multiplying or factoring out an expression”.
Theorem 14: X.(Y+Z) = XY + XZ

Proof: If X = 0 LHS Proof: If X = 1

= X.(Y+Z) LHS = X.(Y+Z)
= 0.(Y+Z) = 1.(Y+Z)
=0 = Y+Z RHS
RHS = XY + XZ = XY + XZ
= 0.Y+0.Z = 1.Y+1.Z
=0 = Y+Z
Therefore LHS = RHS Therefore LHS = RHS

Theorem 15: (𝑋 + 𝑌) (𝑋 + 𝑍) = 𝑋 + 𝑌𝑍
LHS: (𝑋 + 𝑌) (𝑋 + 𝑍) = 𝑋𝑋 + 𝑋𝑍 + 𝑋𝑌 +𝑌𝑍
= 𝑋 + 𝑋𝑍 + 𝑋𝑌 + 𝑌𝑍
= 𝑋(1 + 𝑍) + 𝑋𝑌 + 𝑌𝑍
= 𝑋 + 𝑋𝑌 + 𝑌𝑍 Important
= 𝑋(1 + 𝑌) + 𝑌𝑍 2 Marks
= 𝑋 + 𝑌𝑍
= RHS

Absorption Law: “This law enables a reduction of complicated expression to asimpler one by absorbing
common terms”.
17) X (X+Y) = X 18) XY + X̅𝐘= X
16) X+XY = X
LHS = X (X+Y) LHS = XY + X̅Y
LHS = X + XY
= XX + XY = X(Y+̅Y)
= X (1 + Y)
= X + XY = X.1
=X
= X (1+Y) =X
= RHS
=X = RHS

19) (X+Y) (X+̅)𝐘= X

20) X + ̅ 𝐗Y = X+Y 21) X ( ̅ 𝐗
+ Y) = XY
LHS = (X+Y) (X+̅Y)
LHS = X + ̅XY LHS = X (̅X+Y)
= XX + X̅Y + XY +Y̅Y
= (X + ̅X ) (X+Y) = X. ̅X + X.Y
= X + X̅Y + XY + 0
= 1. (X+Y) = 0 + XY
= X (1 + ̅Y + Y)
= X+Y = XY
= X. 1
= RHS = RHS
=X
De Morgan’s First Law:

De Morgan’s First Law states that (A.B)’ = A’+B’.

The first law states that the complement of the product of the variables is equal to the sum of their individual
complements of a variable.

The truth table that shows the verification of De Morgan’s First law is given as follows:

A B A’ B’ (A.B)’ A’+B’
0 0 1 1 1 1
0 1 1 0 1 1
1 0 0 1 1 1
1 1 0 0 0 0
The last two columns show that (A.B)’ = A’+B’.

Hence, De Morgan’s First Law is proved.

De Morgan’s Second Law:

De Morgan’s Second law states that (A+B)’ = A’. B’.

The second law states that the complement of the sum of variables is equal to the product of their individual
complements of a variable.

The following truth table shows the proof for De Morgan’s second law.

A B A’ B’ (A+B)’ A’. B’

0 0 1 1 1 1

0 1 1 0 0 0

1 0 0 1 0 0

1 1 0 0 0 0

The last two columns show that (A+B)’ = A’. B’.

Hence, De Morgan’s Second Law is proved.

 Boolean Expression:
Boolean expressions are made up of Boolean variables and Boolean operators. A Boolean
expression determines the number of the logic gates required to create an electrical, a digital or
a logical circuit. The more the complexity of the Boolean expression, the more is the complexity
of the electrical, the digital or the logical circuit. So, in order to create simpler circuits, the
Boolean expressions should be simplified. There are two standards for representing the Boolean
expressions in the simplified form. These standard forms are as follows:
• Sum-of-Products (SOP)
• Product-of- Sum(POS)

Product Term. In Boolean algebra, the logical product of several variables on which a function
depends is considered to be a product term. In other words, the AND function is referred to as a
product term or standard product. The variables in a product term can be either in true form or
in complemented form.

For example, ABC′ is a product term.

Sum Term. An OR function is referred to as a sum term. The logical sum of several variables
on which a function depends is considered to be a sum term. Variables in a sum term can also
be either in true form or in complemented form.
For example, A + B + C′ is a sum term.

Sum of Products (SOP). The logical sum of two or more logical product terms is referred to as
a sum of products expression. It is basically an OR operation on AND operated variables.

For example, Y = AB + BC + AC or Y = A′B + BC + AC′ are sum of

products expressions.

Product of Sums (POS). Similarly, the logical product of two or more logical sum terms is
called a product of sums expression. It is an AND operation on OR operated variables.

For example, Y = (A + B + C)(A + B′ + C)(A + B + C′) or Y = (A + B +

C)(A′ + B′ + C′) are product of sums expressions.

Standard form. The standard form of the Boolean function is when it is expressed in sum of
the products or product of the sums fashion.

The examples stated above, like Y =AB + BC + AC or Y = (A + B + C)(A

+ B′ + C)(A + B + C′) are the standard forms.

Minterm:

A product term containing all n variables of the function in either true or

complemented form is called the minterm. Each minterm is obtained by an AND operation of
the variables in their true form or complemented form. For a two-variable function, four different
combinations are possible, such as, A′B′, A′B, AB′, and AB. These product terms are called the
fundamental products or standard products or minterms. In the minterm, a variable will possess
the value 1 if it is in true or uncomplemented form, whereas, it contains the value 0 if it is in
complemented form.
 The main property of a minterm is that it possesses the value of 1 for only one combination of
n input variables and the rest of the 2n – 1 combinations have the logic value of 0. This means,
for the above three variables example, if A = 0, B = 1, C = 1 i.e., for input combination of 011,
there is only one combination A′BC that has the value 1, the rest of the seven combinations have
the value 0.

Canonical Sum of Product Expression.

A Boolean function is expressed as the logical sum of all the minterms from the rows of a truth table,
for which the value of the function is 1, it is referred to as the canonical sum of product expression.
The same can be expressed in a compact form by listing the corresponding decimal-equivalent codes
of the minterms containing a function value of 1.

For example, if the canonical sum of product form of a three-variable logic function F has the
minterms A′BC, AB′C, and ABC′, this can be expressed as the sum of the decimal codes corresponding
to these minterms as below.

F (A,B,C) = (3,5,6)
= m3 + m5 + m6
= A′BC + AB′C + ABC′
The canonical sum of products form of a logic function can be obtained by using the following
procedure:
1. Check each term in the given logic function. Retain if it is a minterm, continue to
examine the next term in the same manner.
2. Examine for the variables that are missing in each product which is not a minterm.
If the missing variable in the minterm is X, multiply that minterm with (X+X′).
3. Multiply all the products and discard the redundant terms.
Example Obtain the canonical sum of product form of the following function:
F (A, B) = A + B
Solution. The given function contains two variables A and B. The variable B is missing from
the first term of the expression and the variable A is missing from the second term of the
expression. Therefore, the first term is to be multiplied by (B + B′) and the second term is to
be multiplied by (A + A′) as demonstrated below.

F (A, B) = A + B
= A.1 + B.1
 = A (B + B′) + B (A + A′)
= AB + AB′ + AB + A′B
= AB + AB′ + A′B (as AB + AB = AB)
Hence the canonical sum of the product expression of the given function is
F (A, B) = AB + AB′ + A′B.
Maxterm
A sum term containing all n variables of the function in either true or complemented
form is called the max term. Each maxterm is obtained by an OR operation of the variables in
their true form or complemented form. Four different combinations are possible for a two-
variable function, such as, A′ + B′, A′ + B, A + B′, and A + B. These sum terms are called the
standard sums or maxterms. Note that, in the maxterm, a variable will possess the value 0, if
it is in true or uncomplemented form, whereas, it contains the value 1, if it is in complemented
form.

The main property of a maxterm is that it possesses the value of 0 for only one combination
of n input variables and the rest of the 2n –1 combinations have the logic value of 1. This
means, for the above three variables example, if A = 1, B = 1, C = 0 i.e., for input combination
of 110, there is only one combination A′ + B′ + C that has the value 0, the rest of the seven
combinations have the value 1.

Canonical Product of Sum Expression.

A Boolean function is expressed as the logical product of all the maxterms from the
rows of a truth table, for which the value of the function is 0, it is referred to as the canonical
product of sum expression. The same can be expressed in a compact form by listing the
corresponding decimal equivalent codes of the maxterms containing a function value of 0.

For example, if the canonical product of sums form of a three-variable logic function F has the
maxterms A + B + C, A + B′ + C, and A′ + B + C′
F (A,B,C) = Π (0,2,5)
= M0 M2 M5
= (A + B + C) (A + B′ + C) (A′ + B + C′)

The canonical product of sums form of a logic function can be obtained by using the following
procedure.

1. Check each term in the given logic function. Retain it if it is a maxterm, continue to
examine the next term in the same manner.
2. Examine for the variables that are missing in each sum term that is not a maxterm. If
 the missing variable in the maxterm is X, add that maxterm with (X.X′).
3. Expand the expression using the properties and postulates as described earlier and
discard the redundant terms.

Example Obtain the canonical product of the sum form of the following function.
F (A, B, C) = (A + B′) (B + C) (A + C′)

Solution. In the above three-variable expression, C is missing from the first term, A is missing
from the second term, and B is missing from the third term. Therefore, CC′ is to be added with
first term, AA′ is to be added with the second, and BB′ is to be added with the third term. This
is shown below.

F (A, B, C) = (A + B′) (B + C) (A + C′)

= (A + B′ + 0) (B + C + 0) (A + C′ + 0)
= (A + B′ + CC′) (B + C + AA′) (A + C′ + BB′)
= (A + B′ + C) (A + B′ + C′) (A + B + C) (A′ + B + C) (A + B + C′) (A + B′ + C′) [using
the distributive property, as X + YZ = (X + Y)(X + Z)]
= (A + B′ + C) (A + B′ + C′) (A + B + C) (A′ + B + C) (A + B + C′) [as (A + B′ + C′)
(A + B′ + C′)
= A + B′ + C′]

Hence the canonical product of the sum expression for the given function is

F (A, B, C) = (A + B′ + C) (A + B′ + C′) (A + B + C) (A′ + B + C) (A + B + C′)

Logic Gates
A logic gate is a simple switching circuit that determines whether an input pulse can pass
through to the output in digital circuits.
The building blocks of a digital circuit are logic gates, which execute numerous logical
operations that are required by any digital circuit. These can take two or more inputs but
only produce one output.
Types of Logic Gates
A logic gate is a digital gate that allows data to be transferred. Logic gates, use logic to
determine whether or not to pass a signal. Logic gates, on the other hand, govern the flow of
information based on a set of rules. The following types of logic gates are commonly used:
1. AND
2. OR
3. NOT
4. NOR
5. NAND
6. XOR
7. XNOR
Basic Logic Gates
AND Gate
An AND gate has a single output and two or more inputs.
1. When all of the inputs are 1, the output of this gate is 1.
2. The AND gate’s Boolean logic is Y=A.B if there are two inputs A and B.
An AND gate’s symbol and truth table are as follows:
 Input Output
A B A AND B
0 0 0
0 1 0
1 0 0
1 1 1

Symbol of AND gate

Therefore, in And gate, the output is high when all the inputs are high.
OR Gate
Two or more inputs and one output can be used in an OR gate.
1. The logic of this gate is that if at least one of the inputs is 1, the output will be 1.
2. The OR gate’s output will be given by the following mathematical procedure if there are two
inputs A and B: Y=A+B
Input Output
A B A OR B
0 0 0
0 1 1
1 0 1
1 1 1

Symbol of OR gate

Therefore, in the OR gate, the output is high when any of the inputs is high.
NOT Gate
The NOT gate is a basic one-input, one-output gate.
1. When the input is 1, the output is 0, and vice versa. A NOT gate is sometimes called an
inverter because of its feature.
2. If there is only one input A, the output may be calculated using the Boolean equation Y=A’.
Input Output
A Not A
0 1
1 0
Symbol of NOT gate
 A NOT gate, as its truth table shows, reverses the input signal.
Universal Logic Gates
NOR Gate
A NOR gate, sometimes known as a “NOT-OR” gate, consists of an OR gate followed by a
NOT gate.
1. This gate’s output is 1 only when all of its inputs are 0. Alternatively, when all of the inputs
are low, the output is high.
2. The Boolean statement for the NOR gate is Y=(A+B)’ if there are two inputs A and B.
Input Output
A B A NOR B
0 0 1
0 1 0
1 0 0
1 1 0

Symbol of NOR gate

By comparing the truth tables, we can observe that the outputs of the NOR gate are the polar
opposite of those of an OR gate. The NOR gate is sometimes known as a universal gate since
it may be used to implement the OR, AND, and NOT gates.
NAND Gate
A NAND gate, sometimes known as a ‘NOT-AND’ gate, is essentially a Not gate followed
by an AND gate.
1. This gate’s output is 0 only if none of the inputs is 0. Alternatively, when all of the inputs
are not high and at least one is low, the output is high.
2. If there are two inputs A and B, the Boolean expression for the NAND gate is Y=(A.B)’
Input Output
A B A NAND B
0 0 1
0 1 1
1 0 1
1 1 0

Symbol of NAND gate

By comparing their truth tables, we can observe that their outputs are the polar opposite of
an AND gate. The NAND gate is known as a universal gate because it may be used to
implement the AND, OR, and NOT gates.
Other Logic Gates
XOR Gate
The Exclusive-OR or ‘Ex-OR’ gate is a digital logic gate that accepts more than two inputs
but only outputs one value.
1. If any of the inputs is ‘High,’ the output of the XOR Gate is ‘High.’ If both inputs are ‘High,’
the output is ‘Low.’ If both inputs are ‘Low,’ the output is ‘Low.’
2. The Boolean equation for the XOR gate is Y=A’.B+A.B’ if there are two inputs A and B.
Input Output
A B A XOR B
0 0 0
0 1 1
1 0 1
1 1 0

Symbol of XOR gate

Its outputs are based on OR gate logic, as we can see from the truth table.
XNOR Gate
The Exclusive-NOR or ‘EX-NOR’ gate is a digital logic gate that accepts more than two
inputs but only outputs one.
1. If both inputs are ‘High,’ the output of the XNOR Gate is ‘High.’ If both inputs are ‘Low,’
the output is ‘High.’ If one of the inputs is ‘Low,’ the output is ‘Low.’
2. If there are two inputs A and B, then the XNOR gate’s Boolean equation is: Y=A.B+A’B’.
Input Output
A B A XNOR B
0 0 1
0 1 0
1 0 0
1 1 1

Symbol of XNOR gate

The truth table shows that its outputs are based on NOR gate logic.
Uses of Logic Gates
1. Logic gates are utilized in a variety of technologies. These are components of chips (ICs),
which are components of computers, phones, laptops, and other electronic devices.
2. Logic gates may be combined in a variety of ways, and a million of these combinations are
necessary to make the newest gadgets, satellites, and even robots.
3. Simple logic gate combinations can also be found in burglar alarms, buzzers, switches, and
street lights. Because these gates can make a choice to start or stop based on logic, they are
often used in a variety of sectors.
4. Logic gates are also important in data transport, calculation, and data processing. Even
transistor-transistor logic and CMOS circuitry make extensive use of logic gates.

CONVERSION OF BOOLEAN FUNCTIONS

 All logical operations—such as AND and OR—can be expressed in the form of
Boolean expressions. Boolean expressions enable a designer to express the complete logic
of a digital circuit. Boolean expressions can be simplified or reduced in order to reduce the
size and complexity of a digital circuit. Boolean expressions can be converted into an
equivalent logic diagram and vice versa.
Boolean Expression to Logic Diagram
A Boolean expression can be of two types, Sum Of Product (SOP) and Product Of Sum
(POS). In the SOP Boolean expression, different product terms are combined with the
addition operators, while in the POS Boolean expression, different sum terms are combined
with the product operator. The product terms in SOP Boolean expression are called
minterms, while the sum terms in POS Boolean expression are called maxterms.
To draw a logic circuit diagram from a Boolean expression, we need to perform the following
steps:
1. Simplify the given Boolean expression using Karnaugh map (k-map).
2. Identify the variables present in the simplified Boolean expression.
3. Draw an input line corresponding to each of the input variables.
4. Draw the corresponding logic gates for the terms contained in the Boolean expression.Table
9.8 lists the terms and symbols related to the logic gates.
The terms and symbols related to logic gates

Terms Logic Symb

gate ol

Product term AND

gate

Sum term OR gate

Inversion NOT

Simplification of Boolean Expression using the k-map K-map is a technique of simplifying the
Boolean expressions using graphical representation method. It simplifies the expressions by
combining the similar expressions and deleting the repeated variables. K-map expresses all the
input and the output valuesgiven in the truth table in the form of a graphical representation. shows
a truth table and its corresponding k-map.

The truth table and its k-map

The 0’s and 1’s written at the top of the k-map represent the values of the input variables,A
and B. The values written inside the boxes of the k-map represent the values of the output Y. For
example, the lower left corner contains the output corresponding to the inputs A = 1, B = 0.
Moreover, the decimal value corresponding to each block is also written inside the block.
The k-map shown in Fig. 9.9 can also be termed as a two-variable k-map. Depending on the
 number of variables used in a Boolean expression, a k-map can have three or four variables, as
shown in Fig. 9.10.

Three and four variable k-maps

The plotting of a Boolean expression on the k-map is the first step in simplifying the expression.
To plot a Boolean expression on a k-map, we first need to draw the k-map depending upon the
number of input variables present in the expression. Then, we need to fill the k-map with 1’s at all
those places for which a product or sum term is present in the expression.
 The next step in simplifying the Boolean expression is to group the 0’s and 1’s present in the k-
map. When adjacent 1’s are grouped, SOP form of Boolean expression is obtained and when
adjacent 0’s are grouped, POS form of Boolean expression is obtained. Don’t care conditions
can also be grouped with1’s or 0’s. Don’t care conditions refer to those outputs, whose values
cannot be determined from the given inputs. The simplification of Boolean expression involves
grouping of two, four and eight adjacent 1’s and 0’s.
After the groups of 1’s and 0’s are marked in a k-map, the groups are analysed for change of
state of input variables. If a variable changes its state from 1 to 0 or vice versa then this variable is
eliminated from the term of the simplified Boolean expression.
Group of two adjacent 1’s In a k-map, two adjacent 1’s can be grouped in different ways.
(a), (b), (c) and (d) represent the various ways of grouping two adjacent 1’s.

The grouping of two horizontal 1’s The grouping of two vertical 1’s

The Grouping of 1’s at Corner The Grouping of two Overlapped

1’s
Problem-01:
 Minimize the following boolean function-
F(A, B, C, D) = Σm(0, 1, 2, 5, 7, 8, 9, 10, 13, 15)

Solution-

• Since the given boolean expression has 4 variables, so we draw a 4 x 4 K Map.

• We fill the cells of K Map in accordance with the given boolean function.
• Then, we form the groups in accordance with the above rules.

Then, we have-

Now,
F(A, B, C, D)
= (A’B + AB)(C’D + CD) + (A’B’ + A’B + AB + AB’)C’D + (A’B’ + AB’)(C’D’ + CD’)
= BD + C’D + B’D’

Thus, minimized boolean expression is-

F(A, B, C, D) = BD + C’D + B’D’
ADDER CIRCUITS
A computer performs various arithmetic and logical operations, such as addition and comparison
with the help of special-purpose digital circuits. Adder is one of these digital circuits that can be
used to add two or more numbers. On the basis of the number of inputs provided to a digital circuit,
the adder is categorised into three types:
• Half adder
• Full adder
• 4-bit adder
Half Adder
A half adder adds two binary numbers to produce the sum and carry. The half adder circuit uses the
XOR gate to produce the sum and AND gate to generate the carry. Figure 9.22 shows the circuit
diagram of ahalf adder.
Input 1 and Input 2 are the two inputs that are provided to both the logic gates, XOR and AND.
The XOR gate produces the sum of the two numbers and the AND gate generates the carry for the
addition operation. Table shows the truth table of a half adder circuit.
 The truth table of a half adder circuit

Inpu Output
t
A B Su Carry
m
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1

Full Adder:

A full adder is a digital circuit that adds three binary numbers and produces the sum and carry.
The circuitryof full adder comprises of two XOR gates to produce the sum of the input values and
an AND gate to produce the carry.
• In other words, in a full adder circuit, two half adder circuits are combined to generate the
result of addition of three binary numbers. Figure 9.23 shows the circuit diagram of a full
adder.
The circuit diagram of a full adder

• Input 1, Input 2 and Input 3 are the three inputs of the full adder.
• Input 1 and Input 2 are provided to the first XOR gate, XOR1, which produces the sum
of the first two numbers. The output of the XOR1 gate is applied to another XOR gate,
XOR2 along with the third input, Input 3. The XOR2 gate produces the final sum of
three inputs.
• Similarly, Input 1 and Input 2 are provided to the first AND gate, AND1, which produces
the carry for the addition of the first two numbers. The output of the AND1 gate is
applied to another AND gate, AND2 along with the third input, Input 3. The AND2 gate
produces the final carry for the addition of three inputs. Table 9.10 shows the truth table
of a full adder circuit.

4-bit Adder
• A 4-bit adder is a digital circuit that helps the CPU in performing addition of two 4 bit
binary numbers.
• The 4-bit binary adder is implemented by using four full adder circuits, each corresponding
to one of the four bits of theoperands.
 • Each full adder adds two input bits along with the previous carry and generates the sum and
the carry bits.
• The output of each of thefull adder comprises the 4-bit addition result andthe carry generated
by the 4th adder comprises the final carry of the addition operation. Figure shows the logic
circuit of the 4-bit binary adder.

The truth table of full adder

Input Output
A B C Sum Carry
0 0 0 0 0
0 0 1 1 0
0 1 0 1 0
0 1 1 0 1
1 0 0 1 0
•
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1

The logic circuit of 4-bit binary adder

FLIP-FLOP CIRCUITS
• The flip-flop is a sequential electronic circuit that is used to store 1-bit information, i.e.,
either 0 or 1.
• A sequential electronic circuit produces the output on the basis of the present input as well
as the previous output of the circuit.
• To store information in a flip-flop, two stable states, set or reset are used along with a clock
signal. The set state represents the value 1 and the reset state represents the value 0.
 • All flip-flops generate two outputs, one is the present output of the circuit and the other is
the complemented value of the present output.
The various types of flip-flops are:
• SR
• JK
• D type
• T type

SR Flip Flop

The S-R flip flop is the most common flip flop used in the digital system. In SR flip flop, when
the set input "S" is true, the output Y will be high, and Y' will be low. It is required that the wiring of
the circuit is maintained when the outputs are established. We maintain the wiring until set or reset
input goes high, or power is shutdown.

The S-R flip flop is the simplest and easiest circuit to understand.

Truth Table:

J-K Flip-flop

The JK flip flop is used to remove the drawback of the S-R flip flop, i.e., undefined states. The
JK flip flop is formed by doing modification in the SR flip flop. The S-R flip flop is improved in order
to construct the J-K flip flop. When S and R input is set to true, the SR flip flop gives an inaccurate
result. But in the case of JK flip flop, it gives the correct output.
 In J-K flip flop, if both of its inputs are different, the value of J at the next clock edge is taken by
the output Y. If both of its input is low, then no change occurs, and if high at the clock edge, then from
one state to the other, the output will be toggled. The JK Flip Flop is a Set or Reset Flip flop in the
digital system.

Truth Table:

D Flip Flop

D flip flop is a widely used flip flop in digital systems. The D flip flop is mostly used in shift-
registers, counters, and input synchronization.

Truth Table:

T Flip Flop
 Just like JK flip-flop, T flip flop is used. Unlike JK flip flop, in T flip flop, there is only single
input with the clock input. The T flip flop is constructed by connecting both of the inputs of JK flip
flop together as a single input.

The T flip flop is also known as Toggle flip-flop. These T flip-flops are able to find the complement
of its state.

Truth Table:

Applications of Flip Flops:

Data Storage

• A flip flop store one bit at a time in digital circuit. In order to store more than one bit flip flop
can be connected in series and parallel called registers.
• A register is simply a data storage device for a number of bits in which each flip flop store one
bit of information (0 or 1). Thus a 4 bit register consists of 4 individual flip flops, each able to
store one bit of information at a time.

Bit Binary Register

Figure: shows a 4 bit register. Any number from (0000)2 to (1111)2 may be stored in it simply by
setting or resetting the appropriate flip flops. Let us suppose that flip flop one is SET(1) , Flip flop 2
is RESET(0), flip flop 3 is RESET(0) and flip flop 4 is SET(1), the binary number stored in this register
is (1001)2.

Data Transfer

• Flip flops can also be used extensively to transfer the data. For this purpose shift register is
used.
 • A shift register is a register which is able to shift or transfer it content within itself without
changing the order of the bits.
• It may be designed to shift or transfer data either left or right. The data is shifted or transferred
one bit at a time, when a clock pulse is applied.
• The shift register can be used for temporary storage of data. The shift register is used for
multiplication and division where bit shifting is required. The shift register can be built using
RS, JK or D flip flops.
A four stage shift right register is shown in Figure 2. Input data is applied to store D and shifted right.

Shift Right Register

Each flip flop is controlled by the output Figure 2: Shift Right Registerof the proceeding flip flop.
Clock signal is applied simultaneously to all flip flops. With each clock pulse information is transferred
to next flip flop as shown below.
DC BA
0000
1011 After 1st Clock
1000
1100
0110
1011

Counter

• Another major application of flip flops is a digital counter. It is used to count pulses or events
and it can be made by connecting a series of flip flops. Counter can count up to 2n. Where n is
the number of flip flops. Figure shows a simplest binary ripple counter made by flip flops.
• It consists of connections of flip flop without any logic gate. Each flip flop is triggered by the
output of its proceeding flip flop.

Figure: Four Stage Binary Counter

They are used in digital equipments, clocks, frequency counters and computers etc.

Frequency Division:

Flip flops can divide the frequency of periodic waveform. When a pulse wave is used to toggle an flip
flop, the output frequency becomes one half the input frequency, as shown in Figure 4
Figure: JK Flip Flop Used as A Frequency Division
The output of each flip flop is half the frequency of an input. If the input frequency is 160 KHz then
output of each flip flop would be so after first flip flop, 40 after second flip flop and 20 after third flip
flop.
Input frequency 160 KHz
Frequency of first flip flop 80 KHz
Frequency of 2nd flips flop 40 KHz
Frequency of 3rd flips flop 20 KHz
Computer Software: -
Introduction:
All computer systems consist of two major components, namely, hardware and software. The hardware
refers to the physical equipment that is necessary for performing various operations, such as reading
and processing data, storing results, and providing output to the users in a desired form. The software
refers to a set of computer programs that are required to enable the hardware to work and perform these
operations effectively. A computer program is basically a set of logical instructions, written in a
computer programming
language that tells the computer how to accomplish a task. The software is therefore an essential
interface between the hardware and the user.

Types of computer software:

A computer software performs two distinctive tasks. The first task is to control and coordinate the
hardware components and manage their performances and the second one is to enable the users to
accomplish their required tasks. The software that is used to achieve the first task is known as the
system software and the software that is used to achieve the second task is known as the application
software.

System Software
System software consists of many different programs that manage and support different tasks.
Depending
upon the task performed, the system software can be classified into two major groups:
• System management programs used for managing both the hardware and software systems.
• System development programs used for developing and executing application software.

Application Software
Application software includes a variety of programs that are designed to meet the information
processing
needs of end users. They can be broadly classified into two groups:
• Standard application programs that are designed for performing common application jobs.
 • Unique application programs that are developed by the users themselves to support their
specific
needs.

System Management Programs:

• System management programs are those programs that are meant for operating the
hardware system and managing their resources effectively.
• They also enable the users to perform certain utility functions, such as creating backup files,
recovering damaged files and merging fi les.
• They minimize the human intervention during processing and aid in maximising the
productivity of a computer system. System management programs include:
• Operating system
• Utility programs
• Device drivers

System Management Programs

Operating System
Operating System (OS) is the principal component of systemsoftware and is responsible for
overall management of computer resources. It also provides an interface between the
computer and the user and helps in implementing the application programs as illustrated in
Fig. 10.5.
Major functions of an operating system are:
• Scheduling and execution of all processes.
 • Allocation and management of main memory and otherstorage areas to the programs.
• Coordination and assignment of different hardware devicesto the programs.
• Creation, storage and manipulation of files required by thevarious processes.
• Determining and maintaining the order of execution of programs.
• Interpretation of commands and instructions.
• Coordination and assignment of other development and utility programs.
• Providing a friendly interface between the computer and the user.
• Ensuring security of access to computer resources.
Operating systems are usually supplied by the hardware manufacturers and are rarely developed

Hardware-OS-User Interface

Utility Programs:

Utility software is developed to provide support in analyzing, optimizing, along

configuring and maintaining a computer. The job of the utility program is to offer support
to the system infrastructure. Though the system will work even if it doesn't have any utility
software, the right kind of utility software enhances its performance and makes it more
reliable.

Some of the common examples of utility software are as follows:

o Norton and McAfee Antivirus

o WinRAR
o Directory Opus
o Disk defragmenter
o WinZip
o Windows File Explorer
o Razer Cortex
Device Drivers

In computing, the device driver is a type of software that operates or controls some specific
hardware devices linked to your system. They provide a software interface to hardware devices
allowing computer operating systems and other applications to fetch hardware functions without
knowing the exact specifications of the hardware. Some common examples of such device drivers that
connect hardware devices (printers, sound cards, network cards, hard disks, floppy disk, keyboard,
mouse, etc.) to a system easily are as follows:

o BIOS (Basic Input/Output System) Device Driver

o USB (Universal Serial Bus) Drivers
o Motherboard Drivers
o Display Drivers
o Printer Drivers
o Sound Card Driver
o ROM (Read-only memory) Drivers
o VGA (Video Graphic Array) Drivers

Working Device Driver

System development programs
System development programs known as programming software allow the users to develop programs
in different programming languages. The process of developing and executing a program involves the
following tasks:
• Debugging the program
• Linking the various variables and objects with the libraries files
• Translating the code from one language to another
• Running the machine code to perform the desired task
In order to carry out these tasks, we need the following system development tools:
• Language translators
• Linkers
• Debuggers
• Editors

Language Translators
A language translator is used to convert
the program code written in one
language to another language. The
program code provided as input tothe
language translator is known as source
code. The source code is a high-level or
an assembly language program. The
language translator converts the high-
level language program into the low-
level language program called object
code. Compiler, interpreter, and
assembler are the most common
examples of language translators. A
compiler translates a high-level program Language translators
into a low-level program and an
assembler translates an assembly

language program into a low-level program. An interpreter also produces a low-level program from a high-
level program, but the working of the interpreter is not similar to that of the compiler. An interpreter processes
the high-level program line-by-line and simultaneously, produces the low-level program. On the other hand,
a compiler compiles the high-level program in one go. The figure shows the input and the output of the
various language translators.

Linkers
Most of the high-level languages allow the developer to develop a large program containing multiple
modules. Linker arranges the object code of all the modules that have been generated by the language
translator into a single program. The execution unit of the computer system is incapable of linking all the
modules at the execution time and therefore, linker is regarded as one of the important software because of
its ability to combine all the modules into a single program. Linker assembles the various objects generated
by the compiler in such a manner that all the objects are accepted as a single program during execution.
Linker also includes the links of various objects, which are defined in the runtime libraries. In many cases,
linker inserts the symbolic address of the objects in place of their real address. Below Figure illustrates the
working of a linker.

Debuggers
Debugger is the software that is used to detect the errors and bugs present in the programs. The debugger
locates the position of the errors in the program code with the help of what is known as the Instruction Set
Simulator (ISS) technique. ISS is capable of stopping the execution of a program at the point where an
erroneous statement is encountered.
Debugger is divided into two types, namely, machine-level debugger and symbolic debugger. The
machine-level debugger debugs the object code of the program and shows all the lines where bugsare
detected. On the other hand, the symbolic debugger debugs the original code, i.e., the high-level language
code of the program. It shows the position of the bug in the original code of the program developed by the
programmer.
 Working of linker

The debugger performs a number of functions other than debugging, such asinserting breakpoints in the
original code, tracking the value of specific variables, etc. In order to debug the program, a debugger helps
us to perform the following tasks:
• Step-by-step execution of a program
• Back tracking for checking the previous steps
• Stopping the execution of the program until the errors are corrected

Editors
Editor is a special program that allows the user to work with text in the computer system. It is used for the
documentation purposes and enables us to edit the information present in an existing document or a file.
The editor enables us to perform the various editing operations such as copy, cut and paste while editing the
text. On the basis of the content edited by the editors, they are divided into the following categories:
• Text editor It is used to edit plain text. An operating system always includes a text editor for updating
the configuration files.
• Digital audio editor It is used to edit the information related to the audio components of a multimedia
application. These editors are used in audio applications where editing the music and the sound signals
is necessary.
• Graphics editor It is used to edit the information related to the graphical object. These editorsare
generally used in the multimedia applications where the user is working with multiple animation
objects.
• Binary file editor It is used to edit the digital data or the binary data, i.e., data having strings of0s
and 1s.
• HTML editor It is used to edit the information included in the web pages.

• Source code editor It is used to edit the source code of a program written in a programming
language such as C, C++ and Java.

Standard application programs

Standard application programs, also known as general-purpose application programs, are
programs that perform certain common information processing tasks for the users. For example,
preparing documents suchas letters and notes are common among almost all organizations as well
as individuals. Similarly, creating and managing databases of products and employees are very
common activities in large organizations. Ready-to-use programs for such applications are
available from hardware or software vendors. These programs would not only significantly increase
the productivity of users but also decrease the investment interms of time and cost. Examples of
standard application programs include:
• Word processor
• Spreadsheet
• Database Manager
• Desktop Publisher
• Web Browser
Word Processor
Word processor is an application software that is generally used to create documents such as
letters, reports,etc. It is one of the most commonly used computer applications. Word processor
enables us to enter textin a document in a particular format. It also allows us to modify the existing
text and apply the formatting features, such as boldface and italic, change the colour of the text,
change the writing style of the text,etc. The word processor application software also allows us
to perform different operations, such ascut-paste for moving the text within the document, copy-
paste for copying the text within a document or from one document to another document, etc. MS
Word is the most common example of a word processor. Below Figure shows the default window
of MS Word.

FigThe default window of MS Word

Spreadsheet
A spreadsheet is an application software that enables the user to maintain a worksheet in which
informationis stored in different cells. Each cell in the spreadsheet can contain numeric and
alphanumeric data. The spreadsheet is also used as a computational tool by applying formulas to
the values of cells. If we change the value of a cell in a spreadsheet, then all the values, that are
dependent on that value, get automaticallyupdated according to the new value. As a result, the
users, who need to store and maintain financial information, always prefer a spreadsheet for storing
the information.
MS Excel is the most common example of the spreadsheet software. Figure shows the default
window of MS Excel.
Fig The default window of MS E
Database Management System
Database Management System (DBMS) is a computer software that helps us to store and maintain
records in a database. Database refers to a set of records, which are stored in a structured manner
in the computer system. Record refers to a set of similar or dissimilar values related to an entity
such as student and employee. DBMS allows a user to perform various operations such as search,
update and delete on the data stored in the database. With the help of DBMS an end user can store,
retrieve, and modify the data in an easy manner. The advantages of DBMS are as follows:
• It enables the user to organise all the information in a strategic manner.
• It helps the users in maintaining consistency in the information stored in the database.
• It helps the user in maintaining data integrity while performing the various operations on the
databasevalues.
• It allows the user to maintain the security of the confidential information by password-
protecting thedatabase.
• It helps in accessing information from any system connected in a networked system
environment.
The DBMS used for maintaining a database always uses specific data model such as
relational,
hierarchical and network that describes the physical and the logical arrangement of data in the
database.In the relational data model, different records are arranged in the form of tables
containing rows and
columns. In the hierarchical model, records are arranged in the form of a tree where each record is
attached with one parent node and one or more child nodes. In the network model, data is arranged
in the form of a network where each node is connected with one or more parent nodes as well as
child nodes. shows the arrangement of records in different data models of the DBMS.
 Fig. Different data models used to design DBMS
DBMS comprises of different components, which are responsible for performing a specific task
in the database system. Some of the components of DBMS are as follows:
• Data structure Data structure refers to a storage mechanism that is used to store multiple
valuesas a single entity. In DBMS, different types of data structures are used to store the
information relatedto an entity. These data structures include:
❑ File It refers to a collection of multiple records.
❑ Record It refers to a collection of multiple values of different data types related to one
entity.
❑ Field It refers to a set of different values having similar data type.
• Transaction mechanism DBMS always includes a transaction mechanism, which ensures
thatthe basic properties of the database system are not affected by the processing of the
transactions.A transaction mechanism included in a database system consists of the following
properties:
❑ Atomicity The transaction mechanism should complete either all tasks included in a
transactionprocessing or none of them.
❑ Consistency The transaction mechanism should be capable of maintaining
consistency in theinformation stored in the multiple files of DBMS after the processing of a
transaction.
 ❑ Isolation The transaction mechanism should not allow any sub process of the
transaction to usethe intermediate data of another transaction.
❑ Durability The transaction mechanism should be capable of providing information
related tothe transactions, which have been processed to change the information stored in
the database.
• Database query language DBMS includes a query language system, which enables a user
to perform various operations such as searching and updating the information stored in the
database.
Desktop Publishing System
Desktop publishing system enables the user to perform various activities required for publishing of
a page or set of pages. These activities include organising the content layout by setting margins and
justification properties of the page. In the desktop publishing system, a page layout software is
installed on a computer system that enables the end users to view the changes done at the time
of designing the document. Thepage layout software uses the ‘What You See Is What You Get
(WYSIWYG)’ technique for displaying the preview of the page being designed. Desktop
publishing system is also referred as DTP.
Desktop publishing system is generally used in the publishing industry, where there is a need to
publish information either through print media or display media. It helps the users to design the
desired page layout containing different components such as text, graphics and images. Some of
the commonly used DTP application software include: Quark XPress, InDesign, Microsoft
Publisher, Apple Pages.

Unique application programs

There are situations where organisations need to develop their own programs to accomplish certain
tasks that are unique to their areas of operations. Similarly, individuals like scientists, engineers,
accountants, teachers and other professionals write their own programs to solve their problems.
Such programs are known as unique application programs or application-specific programs. These
programs are also referred to as end-user application programs. Examples of unique applications
include:
• Managing the inventory of a store
• Preparing pay-bills of employees in an organisation
• Processing examination results of students
• Reserving seats in trains or airlines
• Analysing mathematical models
• Computing personal income tax
• And many more

Inventory Management System

Inventory management system helps in keeping a record of the huge amount of items stored in
warehouse and storerooms. In order to keep a record of inventory or items, application software
called inventory management system, which makes use of DBMS, is used. DBMS is responsible
for storing the information related to the items in the form of various files and tables. It also helps
in storing the information relatedto the location, where a particular item is placed. Inventory
management system enables a user to get a report on the items stored in the warehouse or storeroom
on the basis of the different conditions, such as availability of items, shipping date of item, etc.
Pay-roll System
Pay-roll system is the application software that enables us to perform the various activities related
to pay- roll accounting and pay-roll administration process. It is used by the HR department of
an organisationfor the purpose of computation of salary of employees. A typical pay-roll
 processing system providesan interface to the user through which the user can enter salary
related details, such as attendance, tax, deduction etc.

Problem solving
Problems that can be solved through a computer may range in size and complexity. Since
computers do not possess any common sense and cannot make any unplanned decisions, the
problem, whether it is simple or complex, has to be broken into a well-defined set of solution steps
for the computer to implement.
Problem solving is the process of solving a problem in a computer system by following a
sequence of steps. The major steps that we need to follow for solving a problem are:
1. Preparing hierarchy chart A hierarchy chart shows the top-down solution of a problem. In
caseof large problems, we can break them into parts representing small tasks, prepare several
algorithms and later combine them into one large algorithm.
2. Developing algorithm An algorithm is a sequence of steps written in the form of English
phrases that specify the tasks that are performed while solving a problem. It involves
identifying the variable names and types that would be used for solving the problem.
3. Drawing flowchart A flowchart is the graphical representation of the flow of control and
logic in the solution of a problem. The flowchart is a pictorial representation of an algorithm.
4. Writing Pseudocode Pseudocode is pretty much similar to algorithms. It uses generic syntax
for describing the steps that are to be performed for solving a problem. Along with the
statements written using generic syntax, pseudocode can also use English phrases for
describing an action.
Hierarchy Chart
Hierarchy chart is a solution approach that
suggests a top-down solution of a problem.
We very often come across large problems
to be solved using computers. It may be
very difficult to comprehend the solution
steps of such large problemsat one go. In
such situations, we can decompose the
problem into several parts, each representing
a small task which is easily comprehensible
and solvable. We canthen prepare solution
steps for each taskindependently and later
combine them into
one large solution algorithm. Figure 10.13
Fig. 10.13 Hierarchy chart for pay-roll problem
illustrates a hierarchy chart for computin
 pay of an employee in an organisation. Since the chart graphically illustrates the structure of a program, it is
also known as a structure chart.
While developing a computer program, we may treat each subtask as a module and prepare computer code
for testing independently. This approach is popularly known as modular programming. Note that the
hierarchy chart does not provide any detail about program logic. We have to use the tools discussed below to
prepare logic for each task.

Algorithms
Algorithms help a programmer in breaking down the solution of a problem into a number of sequential steps.
Corresponding to each step a statement is written in a programming language; all these statementsare
collectively termed as a program. The following is an example of an algorithm to add two integers and display
the result:

Algorithm to add two integers and display the result

Step 1 – Accept the first integer as input from the user.
(integer1)
Step 2 – Accept the second integer as input from the user.
(integer2)
Step 3 – Calculate the sum of the two integers.
(integer3 = integer1 + integer2)
Step 4 – Display integer3 as the result.

There is a time and space complexity associated with each algorithm. Time complexity specifies the
amount of time required by an algorithm for performing the desired task. Space complexity specifies the
amount of memory space required by an algorithm for performing the desired task. When solving a complex
problem, it is possible to have more than one algorithm to provide the required solution. The algorithm that
takes less time and requires less memory space is the best one.

Flowcharts
A flowchart can be defined as the pictorial representation of a process, which describes the sequence and flow
of the control and information in a process. The flow of information is represented in a flowchart in a step-
by-step form. This technique is mainly used for developing business workflows and solving problems using
computers.
Flowchart uses different symbols for depicting different activities, which are performed at different stages
of a process. The various symbols used in a flowchart are as follows:
• Start and end It is represented by an oval
or a rounded rectangle in a flowchart. It is used to
represent the starting and the ending of a process.
Every process starts and ends at some point so a
flowchart always contains one start as well as one Fig. 10.14 Start and end symbol

end point. Figure 10.14 shows the start and the end
symbols used in a flowchart.
• Input or output It is represented by a parallelogram in a
flowchart. It is used to represent the inputs given by the user
Fig. 10.15 Input or output symbol
to the process and the outputs given by the process to the user.
Figure 10.15 shows the input or output symbol.
 • Action or process It is represented by a rectangle. It
represents the actions, logics and calculations taking place in
a process. Figure 10.16 shows the action or process symbol.
• Decision or condition It is represented by a rhombus or
a diamond shape in a flowchart. It represents the condition
or the decision-making step in the flowchart. The result of
the decision is a Boolean value, which is either true or false. Fig. 10.16 Action or process symbol
Each of these values takes the flow of the program to a certain
point, which is shown with the help of arrows. Figure 10.17
shows the decision or condition symbol.
• Arrow It is represented by a directed line in a flowchart.
It represents the flow of process and the sequence of steps in
the flowchart. It guides the process about the direction and
the sequence, which is to be followed while performing the Fig. 10.17 Decision or condition symbol
various steps in the process. Figure 10.18 shows the arrow
symbol.

• Connector It is represented by a circle in a flowchart. It represents the continuation of the flowof

steps when a flowchart continues to the next page. A character, such as an alphabet (a to z) ora
symbol (a, b or c), etc. can be placed in the circle at the position where the flow is broken andthe
same character is also placed in the circle at the position from where the flowchart continues. Figure
10.19 shows the connector symbol.

Fig. 10.18 Arrow symbol Fig. 10.19 Connector symbol

In order to understand how a flowchart represents flow

of information, consider an example of flowchart in which
addition of two numbers is represented. Figure 10.20 shows
the flowchart for addition of two numbers.

Pseudocodes
Analysing a detailed algorithm before developing a program
is very time consuming. Hence, there arises a need of a
specification that only focuses on the logic of the program.
Pseudocodes serve this purpose by specifying only the logic,
which is used by the programmer for developing a computer
program.
Pseudocode is not written using specific syntax of
a programming language rather it is written with a
combination of generic syntax and normal English language. Fig. 10.20 Flowchart of addition of two numbers
 It helps the programmer understand the basic logic of the program after which it is the programmer’s choice
to write the final code in any programming language.
The example of a pseudocode to add two numbers and display the result is shown below:

A pseudocode to add two numbers and display the result

Define: Integer num1, num2, result.
Input: Integer num1.
Input: Integer num2.
Sum: result = num1 + num2
Output: Display(result).

After the pseudocode for a computer program has been written, it is used to develop the source code
for the computer program. The source code is developed using a programming language, which can be
an assembly language or a high level programming language. After the source code has been written, the
programmer detects and eliminates any errors in the program so that the program generates the desired output
after its execution.

STRUCTURING THE LOGIC

While writing the pseudocode for a problem, it is necessary to define all the logics used in the pseudocode
for developing the program. Pseudocode of a problem should be able to describe the sequence of execution
of statements and procedures specified in the program. The sequence of the execution of instructions
determines the basic structure of a program or the logic used to solve a problem.
The basic structure of a program comprises of different sets of the statements, whose execution is
dependent on some conditions and decisions. These conditions and decision-making statements are specified
in a control structure. Depending upon the sequence of the execution of the statements, the controlstructures
are categorised into the following types:
• Sequence structure The execution of the statements in a sequence structure is done sequentially, i.e.,
all the statements are executed in the same order as they are written in the program.
• Selection structure In the selection structure, two sets of statement blocks are written in a program
along with one or more conditions. The execution of a particular block’s statements occurs only if the
conditional statement specified at the beginning of the block is true. A selection structure is
also known as branching structure.
• Repetition structure In the repetition structure, a block of two or more instructions is specified along
with a conditional statement. The execution of these instructions is repeated many times if the
conditional statement is true. This structure is also known as looping structure.
We must incorporate these program constructs into the program design, whether as a flowchart or as a
pseudocode. We can also combine the constructs, if necessary. For example, a selection structure can be a
part of a looping structure.

Sequence Structure
In a sequence structure, multiple statements are written in a simple sequence in the program. The execution
of these statements is not affected by any condition. Generally, sequence structure is used for performing
 simple computations, which do not require any decision-making. Figure 10.21 shows the representation of
statements in the sequence structure.

Representation of statements in the sequential structure

Selection Structure
In the selection structure, the execution of a set of statements is done according to a pre-specified condition.
The selection structure is also known as decision-making structure because the decision to execute a
particular set of statements is made on the basis of the conditional statement. The selection structure is
categorised into the following types:
• If-Then In this selection structure, If and Then clauses are used to represent a condition as well as set
of statements. In the If clause, the conditional statement is written, while in the Then clause the
set of statements to be executed are specified. The execution of the statements specified in the Then
clause occurs only if the condition is true.
• If-Then-Else This selection structure is very much similar to the If-Then selection structure. The only
difference between the two is that in If-Then-Else selection structure two sets of statements are
specified. One set of statements is represented in the Then clause and another is represented in the
Else clause. If the condition given in the If clause is true, then all the statements specified in the Then
clause are executed; otherwise statements given in the Else clause are executed.
• Case Type In this selection structure, multiple sets of statements are specified. Each block of
statements is associated with a value. The selection of a particular set of statements is made on the basis
of the value of the variable given at the beginning of the selection structure.
 Figushows the representation of statements in the If-Then-Else selection structure.

Fig. 10.22 Representation of statements in the If-Then-Else selection structure

Repetition Structure
In the repetition structure, only one set of multiple statements is specified. The same set of statements is
executed several times on the basis of the condition specified along with the structure. The various types of
repetition structure are as follows:
• Do-while In the Do-while structure, a set of statements is given in the Do block and a condition is
given in the While block. The statements given in the Do block are executed till the given condition
is true. At each instance of execution of block statements, the condition is checked. If the condition is
true, then only the block statements are executed; otherwise the repetition structure is terminated.
• Repeat-until The Repeat-until structure is opposite to the Do-while repetition structure. In this
structure, the repetitive execution of statements given in the Repeat clause occurs only when the
condition given in the Until clause is false.
 Figure shows the representation of statements in the Do-while repetition structure.

Fig. 10.23 Representation of the statements in the Do-while repetition structure

USING THE COMPUTER

Whenever a user wants to use a computer for solving a problem, he/she has to perform various interrelated
tasks in a systematic manner. A user can not get the solution of a problem by simply providing input to the
computer without preparing the base for solving the problem. The working process of a computer is similar
to the human mind, which first analyses the complete situation of a problem, its causes and its parameters,
and then decides the way to solve the problem on the basis of available parameters. All the activities, which
have to be performed by a user in order to solve a problem using computer, are grouped into three phases:
• Understanding the problem
• Developing a program
• Executing the program

1. Understanding the problem It is the first stage of problem solving using a computer. In this
stage, two basic activities are performed by the user. These activities are as follows:
❑ Identifying parameters and constraints A user has to identify the role of different parameters
in solving the problem, i.e., the user must have the knowledge about the relation between the
various parameters and the problem itself. After identifying the problem and its parameters, the
user has to identify the associated constraints that need to be considered in order to generate an
accurate solution of the problem. The identification of parameters and constraints help in choosing
the most appropriate method to solve the problem.
 ❑ Collecting information After analysing the problem and choosing the solution method, a
user has to collect the information related to the identified parameters of the problem. In order
to collect the information, a user can use the documents and reports pertaining to the previous
versions of the problem. The collected information helps in designing the layout of the output or
solution of the problem.
2. Developing a program After analysing the problem, a user has to plan for developing the program,
which will provide the solution of the program after execution. A program includes multipleinstructions
having a specific syntax. For developing a program, a user has to perform the following activities:
❑ Identifying the logical structure It is the most important activity in which a user preparesthe
logical structure of the program by analysing the various tasks that need to be performed for
solving the problem. In order to prepare the logical structure of a program, a user performs the
following task:
(i) Writing algorithm to list the various steps.
(ii) Drawing flowchart to represent the flow of information.
(iii) Writing pseudocode to specify the programming specifications.
❑ Writing the computer program After preparing the logic, a user has to write the program code
in a particular programming language. The program code should be syntactically and semantically
correct in order to generate the desired result.
❑ Debugging the program After writing the complete program, a user has to apply the debugging
techniques for removing any possible errors in the program. Several programming environments
provide debugging tools that aid the users in effectively and efficiently remove the errors in a
program.
3. Executing the program After developing an error free program, it needs to be executed in orderto
view the solution of the original problem.