DIGITAL ELECTRONICS

AND
COMPUTER ORGANIZATION

SYLLABUS
MODULE – I
Number systems & Conversions –Arithmetic of number systems –binary codes –BCD –The excess
–3code –Gray code –ASCII –EBCDIC - Introduction to Logic Circuits –logic functions & gates –
Inversion –truth tables –logic gates –truth table of basics gates –timing diagrams of NOT, AND & OR
gates –Boolean algebra –NAND& NOR logic gates - truth table of a logic circuit –de-morgan’s
theorem.
MODULE – II
Logic families –factors affecting performance of a logic family –register transistor logic –diode
transistor logic –DCTL –ECL –TTL logic family –Karnaugh maps –two, three & four-variables
K-map –loops in K-map –mapping of K-maps –don’t care condition
MODULE – III
Combinatorial logic circuits –designing procedure–code converters –multiplexers –multiplexer tree
–demultiplexers /decoders –half & full adder –half & full subtractor –encoders –BCD adder
MODULE – IV
Sequential logic circuits –sequential circuits –SR flip flop –D flip flop –JK flip flop –T flip flop –
flip flop triggering – Shift registers – Design of shift registers design of ripple counters with
examples Design of synchronous counter with examples timing sequences.
MODULE – V
Register transfer logic Inter register transfer Arithmetic, Logic and shift micro operations
Conditional control statements fixed point binary data overflow Arithmetic shifts Instruction codes
Design of simple computer.
Text Books:
1. Morris Mano M, “Digital Logic and Computer Design”, Pearson Education, 4th edition,
2014.
2. S.S. Bhatti & Ragul Malhotra, ”A Textbook of Digital Electronics”, I.K. International
publishing, New Delhi, 2013.
3. Carl Hamacher, Zvonko Vranesic, Safwat Zaky, “Computer Organization”, 5th edition,
McGraw Hill, 2002.
 UNIT – 1
NUMBER SYSTEM:

The number system is a way to represent or express numbers. You have heard of various types of
number systems such as the whole numbers and the real numbers. But in the context of
computers, we define other types of number systems. They are:

• The decimal number system

• The binary number system
• The octal number system and
• The hexadecimal number system

1. Decimal Number System:

• Decimal number system is a base 10 number system having 10 digits from 0 to 9.

• Decimal number system is also a positional value system. This means that the value of
digits will depend on its position.
• The weightage of each position can be represented as follows

Example :(123)10

123 = 1 X 102 + 2 X 101 + 3 x 100

= 1 x 100 + 2 X 10 + 3 X 1

2. Binary Number System:

• A computer can understand only the “on” and “off” state of a switch. These two states are
represented by 1 and 0.
• The combination of 1 and 0 form binary numbers. It is called a binary or base 2 number
system.
• Each binary digit is also called a bit.
• Binary number system is also positional value system, where each digit has a value
expressed in powers of 2
• The weightage of each position can be represented as follows

2-4
23 22 21 20 . 2-1 2-2 2-3
MSB LSB
 In any binary number, the rightmost digit is called least significant bit (LSB) and leftmost
digit is called most significant bit (MSB).

Example: (11010)2

Equivalent decimal number for 11010 binary number is

(11010)2 = 1×24 + 1×23 + 0×22 + 1×21 + 0×20

= 16 + 8 + 0 + 2 + 0

= (26)10

Computer memory is measured in terms of how many bits it can store. Here is a chart for memory
capacity conversion.

• 1 byte (B) = 8 bits

• 1 Kilobytes (KB) = 1024 bytes
• 1 Megabyte (MB) = 1024 KB
• 1 Gigabyte (GB) = 1024 MB
• 1 Terabyte (TB) = 1024 GB
• 1 Exabyte (EB) = 1024 PB
• 1 Zettabyte = 1024 EB
• 1 Yottabyte (YB) = 1024 ZB

3. Octal Number System:

• Octal number system has eight digits – 0, 1, 2, 3, 4, 5, 6 and 7.

• Octal number system is also a positional value system with where each digit has its value
expressed in powers of 8
• The weightage of each position can be represented as follows
Decimal equivalent of any octal number is sum of product of each digit with its positional value.

Ex: Converting (726)8 to decimal

(726)8 = 7×82 + 2×81 + 6×80

= 448 + 16 + 6

= (470)10

4. Hexadecimal numbers:

• Hexadecimal number system has 16 digits – 0, 1, 2, 3, 4, 5, 6 ,7,8,9,A,B,C,D,E,F.

• Hexadecimal numbering system uses the Base of 16
• It requires only 4 bits to represent value of any digit.
• Hexadecimal numbers are indicated by the addition of either an 0x prefix or an h suffix.
• Hexadecimal Number System is commonly used in Computer programming and
Microprocessors.
• It is also helpful to describe colors on web pages.

Ex: Converting (512)16 to decimal number

(512)16 = 5 x 162 + 1 x 161 + 2 x 160

= 5 x 256 + 1 x 16 + 2 x 1

= 1280 + 16 + 2

= (1298)10

Number system Convertions:

Converting decimal to binary:

➢ Repeatedly divide the decimal number by 2 and accumulate the remainders unil the
divided is less then 2.
Ex: Convert (17)10 to binary
Ex: Convert (21)10 to Binary

2 21

2 10 - 1

2 5 - 0 (21)10 = (10101)2

2 2 - 1

1 -0

Converting the decimal number 0.735 to binary

➢ Multiply the fractional part number continuously by 2 and take integer part only in
the reault until the desired accuracy is obtained.

0.735 x 2 = 1.47 -1
0.47 x 2 = 0.94 -0
0.94 x 2 = 1.88 -1
0.88 x 2 = 1.76 -1
0.76 x 2 = 1.52 -1
0.52 x 2 = 1.04 -1
0.04 x 2 = 0.08 -0

(0.735)10 = (1011110)2

Converting decimal number to Octal number system

➢ Repatedly divide the decimal number by 8 and accumulate the remainder until the
dividend is less the 8
 Ex : Convert (100)10 to Octal

8 100

8 12 -4

8 1 - 4 (100)10 = (144)8

Converting decimal number to Hexadecimal number system

➢ Repatedly divide the decimal number by 16 and accumulate the remainder until the
dividend is less the 16

Ex : Convert (437)10 to hexadecimal

16 437

16 27 -5

1 - 11(B) (437)10 = (1B5)16

Converting Binary number to Octal number system

➢ 23=8, each octal digit corresponds to thee binary digit

➢ When converting binary to Octal, arrange the binary numbers in groups of three from
right most binary digit and substitute the octal value.

Octal Binary
0 000
1 001
2 010
3 011
4 100
5 101
6 110
7 111
 Ex: Convert binary number (10011)2 to octal number

010 011

2 3

(10011)2 = (23)8

Convert binary number (10110001101011) to Octal number

010 110 001 101 011

2 6 1 5 3

(10110001101011)2 = (26153)8

Converting Binary number to Hexadecimal number system

➢ 24=16, each hexadecimal digit corresponds to four binary digit.

➢ When converting binary to Hexadecimal, arrange the binary numbers in groups of
four digits from right most binary digit and substitute the hexadecimal value.

Hexadecimal Binary
0 0000
1 0001
2 0010
3 0011
4 0100
5 0101
6 0110
7 0111
8 1000
9 1001
A 1010
B 1011
C 1100
D 1101
E 1110
F 1111
 Example: Convert the binary number (101100011011110011)2 to Hexadecimal number

0010 1100 0110 1111 0011

2 C 6 F 3

(101100011011110011)2 = (2C6F3)16

Converting other system to decimal number system

• Converting binary to decimal multiply each binary digit with 2p ( p is the positional
value) and sum all the products.
Ex: (101)2 = 1x22 + 0x21 + 1x20
= 4+0+1
= (5)10

• Converting Octal to decimal multiply each ocatl digit with 8p ( p is the positional value)
and sum all the products.
Ex: (726)8 = 7×82 + 2×81 + 6×80

= 448 + 16 + 6

= (470)10

• Converting hexadecimal to decimal multiply each hexadecimal digit with 16p ( p is the
positional value) and sum all the products.

Ex: (512)16 = 5 x 162 + 1 x 161 + 2 x 160

= 5 x 256 + 1 x 16 + 2 x 1

= 1280 + 16 + 2

= (1298)10

Converting Octal, Hexadecimal to Binary number system

• When converting an octal number to binary, substitute the binary value for each octal
digit(3 bits).
 Ex: Convert the octal number (735)8 into binary

7 3 5
111 011 101

(735)8 =(111011101)2

• When converting a hexadecimal number to binary, substitute the binary value for each
hexadecimal digit(4 bits)
Ex: Convert the hexadecimal number (5FA)16 into binary

5 F A
0101 1111 1010

(5FA)16 =(010111111010)2

Converting Octal to Hexadecimal and vice versa

• When converting an octal number to hexadecimal, first convert the octal to binary
equivalent and then arrange the binary numbers in group of three digits and substitute the
hexadicimal value.
Ex: Convert (245)8 to hexadecimal number
2 4 5
010 100 101

0000 1010 0101

0 A 5
(245)8 = (0A5)16

• When converting an hexadecimal number to octal, first convert the hexadecimal to binary
equivalent and then arrange the binary numbers in group of four digits and substitute the
hexadicimal value.

Ex: Convert (A13)16 to Octal number

A 1 3

1010 0001 0011

101 000 010 011

5 0 2 3 (A13)16 = (5023)8
 Binary Codes:

• Computers are designed to recognize and process only two values 0 and 1.
• Digital systems represent and manipulate not only binary number, but also many other
discrete elements of information.
• The Binary code can be classified into the following classes

7. Weighted Codes or BCD

8. Non-weighted code or Excess-3 Code
9. Self Complementing Codes
10. Gray Code or Reflected codes
11. Error Detection and Correction Codes
12. Alpha numeric codes

1. BCD or Weighted codes:

• Decimal value of a code is obtained by summing up the positional vaues,i.e., % w(i)b(i),

where w represents the weights (positional value) and b represents the binary value.
• There are billions of weighted codes, but the most popular one is 8421 code as it uses the
natural weights use in a binary representation.

23 22 21 20
8 4 2 1

• 8421 code is known as Binary Coded Decimal(BCD).

• Disadvantage of BCD is that it is very difficult to find the complement of the number
using this code.
• The following table show different weighted codes:

Decimal BCD 4221 2421

digit 8421
0 0000 0000 0000
1 0001 0001 0001
2 0010 0010 0010
3 0011 0011 0011
4 0100 1000 0100
5 0101 0111 1011
6 0110 1100 1100
7 0111 1101 1101
8 1000 1110 1110
9 1001 1111 1111
Example: Convert (345)10 into BCD quivalent.

3 4 5
0011 0100 0101

(345)10 = (001101000101)BCD

Example: Convert (100010010110)BCD into its decimal equivalent.

1000 1001 0110

8 9 6
(100010010110)BCD = (896)10

2. Excess-3 code (OR) Non-Weighted Codes :

Excess-3 code is a modify form of a BCD number. The excess-3 code can be derived from the
natural BCD by adding 3 to each coded number.

Decimal Excess-3
Digit Code
0 0011
1 0100
2 0101
3 0100
4 0111
5 1000
6 1001
7 1010
8 1011
9 1100

• Other non-weighted codes are ASCCI code, EBCDIC code. Gray code .

Example: Convert 654 into Excess-3 code.

Add 3 to each of the digits of 654

654
(+) 333

987
 Substitute the BCD code for each of the code

9 8 7
1001 1000 0111

Excess-3 value of (654)10 = (100110000111)

3. Self Complementing codes:

In a 4-bit code construction if we interchange 0’s and 1’s in a digit d we will obtain the value
equivalent to (9-D) and such a code is called self-complementing code. The 9’s complement of a
decimal can be obtained by interchanging 0’s and 1’s.

Decimal 8421 8421

digit (D) (9-D)
0 0000 1111
1 0001 1110
2 0010 1101
3 0011 1100
4 0100 1011
5 0101 1010
6 0110 1001
7 0111 1000
8 1000 0111
9 1001 0110

4. Gray Code or Reflected Code or Cyclic Code:

• The gray code is a minimum change code and to obtain the next code, it is required to
change only one bit from the previous code pattern and it is a non-weighted code.
• Gray code is used for reading positional information on mechanical devices.
• Check the gray code; if there is even number of 1’s change the Least Significant Bit and if
there is odd number of 1’s change the previous bit of the first occurrence of the 1 bit from
the LSB.

Decimal Gray Code

0 0000

1 0001

2 0011

3 0010
 4 0110

5 0111

6 0101

7 0100

8 1100

9 1101

10 1111

11 1110

12 1010

13 1011

14 1001

15 1000

Ex: Determine the subsequent gray code for 0110

Since there is even number of 1’ bit, change LSB.
Hence 0110 should be changed to 0111.

Converting Binary number to Gray Code:

To convert binary to Gray code use the following algorithm

Let B be the binary code and G be the gray code.

i) G1 = B1(Set the MSB of G to MSB of B)
ii) G2 = G1 + B2
iii) G3=G2 + B3
iv) G4= G3 + B4

Example: Covert the binary number 1101 to Gray code.

1 1 0 1
1 0 0

1 0 0 1
 Converting Gray Code to Binary:

To convert Gray code to Binary use the following algorithm

Let B be the binary code and G be the gray code.

i) B1 = G1(Set the MSB of G to MSB of B)
ii) B2 = B1 + G2
iii) B3=B2 + G3
iv) B4= B3 + G4

Example: Covert Gray code 1011 to binary.

1 0 1 1

1 0 1
1 1 10

5. Error Detection and Correction Codes:

In a digital communication channel transmitting binary series (0’s and 1’s) corresponding to
two different range of analog voltages. So, during transmission of binary data from one system
to the other, the noise may also be added. Due to this, there may be errors in the received data at
other system.
There are two tasks in the error control coding:
• Error dectection
• Error correction.

Error detection is the detection of errors caused by noise or other impairments during
transmission from the transmitter to the receiver.
Error correction is thedetection of errors and reconstruction of the original, error-free data.

Error detecting code:

Common type of error dectecting code is the parity check code.

Parity Checking:
• Parity bit means an additional bit added to the data at the transmitter before transmitting
the data.
• Before adding the parity bit, number of 1’s or zeros is calculated in the data. Based on
this calculation of data an extra bit is added to the actual information / data.
• The addition of parity bit to the data will result in the change of data string size.
• This means if we have an 8 bit data, then after adding a parity bit to the data binary string
it will become a 9 bit binary data string.
 There is two types of parity bits in error detection, they are
• Even parity
• Odd parity

Even Parity Code

The value of even parity bit should be zero, if even number of ones present in the binary code.
Otherwise, it should be one.
The following table shows the even parity codes corresponding to each 3-bit binary code.

Even parity
Binary Code Even Parity bit
code
000 0 0000
001 1 0011
010 1 0101
011 0 0110
100 1 1001
101 0 1010
110 0 1100
111 1 1111

Odd Parity Code

The value of odd parity bit should be zero, if odd number of ones present in the binary code.
Otherwise, it should be one.

The following table shows the odd parity codes corresponding to each 3-bit binary code.
Binary Code Odd Parity bit Odd parity code
000 1 0001
001 0 0010
010 0 0100
011 1 0111
100 0 1000
101 1 1011
110 1 1101
111 0 1110

Hamming Code:

Hamming code is useful for both detection and correction of error present in the received data.
This code uses multiple parity bits and we have to place these parity bits in the positions of
powers of 2.
6. Alphanumeric codes:

• All digital computers should possess the capability of manipulating alphabets and special
characters along with the digital data.
• A complete alphanumeric code would include the 26 lowercase characters, 26 uppercase
characters, 10 numeric digits, etc.
• There are many choices of codes sets to represent alphanumeric characters and several control characters.
Two well accepted code sets are used for information coding
• ASCII Code
• EBCDIC code.

ASCII code:
1. American Standard Code For Information Interchange.
2. It was invented over 50 years ago for displaying text on computer screen.
3. This was accomplished by assigning a number to each letter.
4. These coding schemes generally use 7 or 8 bits to code a character.
5. ASCIIcod was a very compact convention and was available on every computer platform.
6. The standard ASCII code defines 128 character codes (from 0 to 127).
7. The first 32 are control codes that means non printable- codes.
8. Other 96 are representable characters.
9. In addition to the 128 standard ASCII codes there are other 128 that are known as extended ASCII
codes.
10. Some of the ASCII codes are

Sl.No Character/Digit Decimal

equivalent
ASCII code
1 Digits 0-9 48-57
2 A–Z 65-90
3. a-z 97-122
4 Carriage 13
Return
5 Esc Key 27

6 Space bar 32

EBCDIC code
• Extended Binary Coded Decimal Interchange Code.
• It is a character encoding set developed by IBM.
• EBCDI uses the full 8 bits available to it.
• Parity checking cannot be used on 8-bits system
• It has a wider range of control characters than ASCII.
• The character encoding is based on BCD.
 Binary Arithmetic:
We can perform four types of operations in binary arithmetic.

1. Addition
2. Subtraction
3. Multiplication
4. Division

1.Binary Addition:

A binary addition operation requires two operands (Addend andAugend) and the binary
addition operator(+). The rules for binary addition are

A+B SUM CARRY

0+0 0 0
0+1 1 0
1+0 1 0
1+1 0 1

Ex: Add (110111)2 and (110011)2

Carry 11 111
Addend 1 10111
Augend 1 10011

Result 1101010

Ex:Add (1101.111)2 and (101.101)2

Carry 1 1111
Addend 1 1 0 1 .1 1 1
Augend 0 1 0 1 .1 0 1

Result 1 0 0 1 1 .1 0 0

2. Binary Subtraction :

A binary subtraction operation requires two operands (minuend and subtrahend) and the
binary subtraction operator (-). The rules for subtraction are

A+B Subtract Barrow

0-0 0 0
0-1 0 1
1-0 1 0
1-1 0 0
Ex:Subtract (111)2 from (1001)2

Barrow 1
10 10
Minuend 1 0 0 1
Subtrahend 0 1 1 1
Result 0 0 1 0

Ex2: Subtract (111.01)2from (1101.11)2

Barrow 10 10
Minuend 1 10 1 . 1 1
Subtrahend 0 1 1 1 . 0 1

Result 110.10

3. Multiplication :

A Binary multiplication operation requires a binary multiplication operator (*) and two
operands (multiplicand and multiplier). The rules for the binary multiplication are

AxB Multiplication
0x0 0
0x1 0
1x0 0
1x1 1

Ex: Multiply 1101 by 101

Multiplicand 1101
Multiplier 101
1101
0000
1101
1000001

4. Binary Division:

A binary division operation requires a binary dividion operator(/) and two operands
(dividend and divisor). The rules for the binary division are
 A/ B Result

1/1 1

0/1 0

Ex: Divide 11001 by 101

101

101 11001
101
101
101
0

Quotient = 101 and remainder = 0

Negative number:

One of the method to represent a negative number is signed-bit magnitude.

In this method the magnitude of the postive number is stored in a normal form, whareas the
magnitude of the negative number is stored by introducing a 1 in the MSB called signed bit
postion.

Ex: 10 and -10

10 = 00001010
-10 = 10001010

** Sign bit representation has a lot of disadvantages instead of we can use complements to
represent negative numbers

COMPLEMENT
S

o Compliments are used to simplifying the subtraction operation

o There are two types of compliments for each base-r system

1. r’s compliment

2. (r-1)’s compliment
 • r’s compliment support

1. 10’s compliment

2. 2’s compliment

• (r-1)’s compliments

1.9’s complement

2. 1’s complement

r’s complements

• The r’s complement of a positive value P in radix r is obtained by using the formula
rn – P, where n is the total number of digits in P.

Ex: Find the 10’s complemnt of (31593)10

n = 5 (no.of digits)

10’s complement of 31593 = 105 – 31593

= 100000 – 31593

= 68407

Ex: Find 10’s complement of 1.52

No.of digits in integer part is 1

10’s complement of 1.52 = 101 – 1.52

= 10 – 1.52

= 8.48

2’s
complements

Number of digit n=6

base r=2

2’s complement of 101100 =26 - 101100

=1000000-101100

= 01010
 II method:

• Retaining all the 0’s from the right hand side (LSB), till a 1 is encountered.
• Retain the first 1 too, and change all the 0’s to 1’s and 1’s to 0’s.

Ex: Find 2’s complement of 1100100 1100100

0011100

III method:

• Find 1’s Complement for the given number.

• Add 1 to the result

Ex: Find 2’s complement of 1100100

1’s Complement of 1100100 = 0011011

1
0011100

(r-1)’s Complement
• (r-1)’s complement can be represented by the formula (rn -1) – P, where n is the total number
of digits in positive value P.

9’s Complenet
Find the 9’s complement of (4752)10

9’s complemne tof (4752)10 = (104-1)-4752

= (10000-1)-4752
= 9999 – 4752
= 5247

1’s Complement

The (r-1) complement of binary number can be obtained by changing the 0’1 to 1’s and 1’s to 0’s.
Ex: Find the 1’s complent of 1100100
1’s complement of 1100100 = 0011011
Introduction to logic Circuits:

● Digital electronic circuits operate with voltages of two logic levels namely Logic Low
and Logic High.
● The value for Logic Low is represented with ‘0’ or ‘false’.
● The value for Logic High is represented with ‘1’ or ‘true’/
● A Digital Logic Gate is an electronic circuit which makes logical decisions based on the
combination of digital signals present on its inputs.
● Digital logic gates can have more than one input but generally only have
onedigital output.

Digital logic Gates:

● Digital Logic gates consists of binary variables and logical operations

● The variables are designed by alphabet such as A,B,C,x,y,z, etc.
● The logical operation support AND, OR, NOT and so on.

OR gate:
● OR gate performs Logical addition operation.
● This operation is represented by plus(+) operator
● The expression for OR operation is
Y=A+B
● OR operation produces result 1 when any one of the input is 1,otherwise it is 0.

Logic Circuit for OR gate:

Truth Table
Inputs Output

A B Y=A+B

0 0 0

0 1 1

1 0 1

1 1 1

AND gate:
● AND gate performs Logical Multiplication operation.
● This operation is represented by dot(.) operator
 ● The expression for OR operation is
Y=A.B
● AND operation produces result 1 when all the inputs are 1,otherwise it is 0.
Logic Circuit forAND gate:

Truth Table

Inputs Output
A B Y=A.B

0 0 0

0 1 0

1 0 0

1 1 1

NOT gate:
● NOT gate performs Logical Inverse or Complementation.
● This operation uses only one input.
● The expression for NOT operation is
●
Y = A’ or A
● NOT operation produces reverse value for the input.
● If input is 1, the result is complemented to 0 and if the input is 0, the result is
complemented to 1.
Logic Circuit forAND gate:

Truth Table

Input Output
A Y=A

0 1

1 0
Buffer:
● A buffer is a temporary storage area.
● The output of the buffer is the same as its input.
● The main operation is to store the data that is placed on it for a certain amount of time.
Logic Circuit forBuffer is:

A Y= A

Truth Table:

Input Output
A Y= A
0 0
1 1

Derived Gates: The gates which can be derived from the basic gates are called derived gates.
NOR,NAND,XOR,XNOR are the derived gates.

NOR gate:
● The NOR gate is the complement of the OR operation and it is also called Not-OR
● The expression for OR operation is
Y=A+B
● NOT operation if all inputs are 0 then the result is 1, otherwise it is 0.
● NOT operation produces result 0 when any of the input is 1.

Logic Circuit for NOR gate:

(OR)

Truth Table

Input Output
Y=A+
A B
B

0 0 1
0 1 0

1 0 0

1 1 0
NAND gate:
● The NAND gate is the complement of the AND operation and it is also called Not-AND
● The expression for NAND operation is
Y=A.B
● NAND operation if all the inputs are 1 then the result is 0,otherwise it is 1.

Logic Circuit forNAND gate:

(OR)

Truth Table

Input Output

A B Z=A.B

0 0 1

0 1 1

1 0 1

1 1 0

XOR or Ex-OR gate:

● This operation is called Exculsive-OR operation.

● An XOR gate has a same symbol similar to that of the OR gate with an additional curve
line on the input side.
● The operator used for XOR is ⊕ operator
● The expression for XOR is
Y = (A ⊕ B) = A.B + A.B
● If all the values are ‘0’ or ‘1’ then the result is 0, otherwise it is 1.

Logic Circuit for NAND gate:

Truth Table

Input Output

A B Y=A ⊕ B

0 0 0

0 1 1

1 0 1

1 1 0

XNOR or Ex-NOR gate:

● The XNOR is called Exculsive-NOR operation.

● This operation is the complement of the XOR operation.
● The operator used for XNOR is ⊙operator
● The expression for XNOR is
Y=A ⊙ B = AB+AB
● If all the values are ‘0’ or ‘1’ then the result is 1, otherwise it is 0.

Logic Circuit forXNOR gate:

Truth Table

Input Output
A B Y=A ⊙ B

0 0 1

0 1 0

1 0 0

1 1 1
Hierarchy of logic circuits:
1. Parantheses have the highest priority
2. Inversion have next highest priority
3. AND operation
4. OR operation
5. If an expression has a bar over it, the operation should be performed first and the result
should be inverted next.

Timing Diagram for AND gate:

Timing Diagram for OR gate:

Boolean Algebra:

● Boolean Algebra is a systematic treatment of logic developed by George Boole.

● Boolean Algebra uses a set of Laws and Rules to define the operation of a digital logic
circuit.
● Boolean Algebra is the mathematics we use to analyse digital gates and circuits.
 ● We can use these “Laws of Boolean” to both reduce and simplify a complex Boolean
expression in an attempt to reduce the number of logic gates required.
● The variables used in Boolean Algebra only have one of two possible values, a logic “0”
and a logic “1”

A brief description of the various Laws of Boolean are given below with Arepresenting a
variable input.

Postulates and Theorems of Boolean Algebra

BOOLEAN FUNCTIONS:

□ A binary variable can take the value of 0 and 1.

□ A Boolean function is an expression formed with.
1. Binary variables (x, y)
2. Binary operator (AND, OR) and
3. Unary operator (NOT).

□ The example for Boolean function;

F1=xyz1

□ The example for Boolean function;

F2=x+y1z
 □ The example for Boolean function;
F3=xy’+x’y

Simplification of Boolean Functions:

A Boolean function can be minimized by algebraic manipulations.
i).Simplify the Boolean expression
xy +xy’
= x(y+y’) (Complement law y+y’=1)
= x(1)
=x

ii) Simplyfy (A+B)’(A’+B’)’

(A+B)’(A’+B’)’
=(A’.B’)((AB)’)’ ( deMorgans Law)
=(A’.B’)(A.B)(Since A.A’=0)
=0

iii) Simplify a’bc+abc’+abc+a’bc’

a’bc+abc’+abc+a’bc’
= a’bc+a’bc’+abc’+abc (Cummutative law)
=a’b(c+c’)+ab(c+c’)
=a’b+ab (Since c+c’=1)
=b(a+a’)
=b (Since c+c’=1)

CONANICAL AND STANDARD FORM

MINTERM:
● A binary variable appear in normal form(x) in its compliment form (x’).
● It may appear in either form ,there are four possibilities.
● x’y’, x’y, xy’, xy
● Each of these four AND terms represent one of the distinct areas is called minterm or a
standard product.

MAX TERM:
● Four possible combination of OR binary values x’+y’, x’+y, x+y’, x+y.
● These four term of distinct area is called maximum term.
● The procedures for obtaining product of max term directly form the truth table.
● From a max term for each combination of the variable which produces a 0 in the function
AND of all those max term.
● Boolean function expressed as a some of min term of product max term as set to be a
canonical form.

x y Min terms Max terms

0 0 m0=x’y’ M0=x + y

0 1 m1=x’y M1=x + y’

1 0 m2=xy’ M2=x’ + y

1 1 m3=xy M3=x’ + y’

Sum of Minterms
i) Express the Boolean function F=A+B’C in a sum of minterms.
Sol:
● This function has three variables: x, y, and z.
● All terms must have these three variables.
1st term
A=A(B+B’)
=AB+AB’
=AB(C+C’)=AB’(C+C’)
=ABC+ABC’+AB’C+AB’C’
2 term
nd

B’C= B’C(A+A’)
=AB’C+A’B’C
A+B’C = ABC+ABC’+AB’C+AB’C’+AB’C+A’B’C
 =m1+M4+m5+m6+m7
F(A,B,C)=£(1,4,5,6,7)
2. Express the Boolean function F = x + y z as a sum of minterms
Sol:
● This function has three variables: x, y, and z.
● All terms must have these three variables.
● Thus, we need to expand the first term by ANDing it with (y + y')(z + z'), and we expand
the second term with (x + x') to get
F=x+yz
= x (y + y') (z + z') + (x + x') y z
= x y z + x y z' + x y' z + x y' z' + x y z + x' y z
= x' y z + x y' z' + x y' z + x y z' + x y z
= m3 + m4 + m5 + m6 + m7
= Σ(3, 4, 5, 6, 7)
Solve the following boolean function to sum of min terms

i) F(x,y,z)= (xy+z)
ii) F(x,y,z)=x(y’+z)+yz

Product of Max terms

The Boolean function F=xy+X’z

=xy+x’z ( (x+yz = (x+y)(x+z) xy=A,x’=Y,z=Z )
=(xy+x’)(xy+z)
=(x+x’)(y+x’)(x+z)(y+z)
= (y+x’)(x+z)(y+z)
(x’+y)= (x’+y+z) (x’+y+z’)
(x+z)= (x+y+z) (x+y’+z)
(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+y+z) (x+y’+z)
=M0.M2.M4.M5
F(x,y,z)=π(0,2,4,5)
 Difference between SOP and POS

S.No. SOP POS

A way of representing boolean A way of representing boolean

1. expressions as sum of product terms. expressions as product of sum terms.

SOP uses minterms. Minterm is product POS uses maxterms. Maxterm is sum
of boolean variables either in normal of boolean variables either in normal
2. form or complemented form. form or complemented form.

It is sum of minterms. Minterms are It is product of maxterms. Maxterms

3. represented as ‘m’ are represented as ‘M’

SOP is formed by considering all the POS is formed by considering all the
4. minterms, whose output is HIGH(1) maxterms, whose output is LOW(0)

While writing minterms for SOP, input While writing maxterms for POS, input
with value 1 is considered as the with value 1 is considered as the
variable itself and input with value 0 is complement and input with value 0 is
5. considered as complement of the input. considered as the variable itself.