lOMoARcPSD|21122727

CFS10BT-Number Systems- Notes-PDF

Information Technology (Tshwane University of Technology)

Studocu is not sponsored or endorsed by any college or university

Downloaded by Frank Cruz ([email protected])
 lOMoARcPSD|21122727

TSHWANE UNIVERSITY OF TECHNOLOGY

FACULTY INFORMATION AND COMMUNICATION TECHNOLOGY

SEMESTER 1
2019
NUMBER SYSTEMS and BINARY LOGIC
COURSE NAME: NATIONAL DIPLOMA:
FOUNDATION IT
INFORMATION TECHNOLOGY
B TECH FINANCIAL INFORMATION SYSTEMS

SUBJECT NAME: COMPUTING FUNDAMENTALS 1B

FOUNDATION INFORMATION SYSTEMS BF
INFORMATION SYSTEMS BT
FINANCIAL INFORMATION SYSTEMS BT

SUBJECT CODE: CFS 10 BT / FIS 11 BT

REVISED by: T.P. MSIMANGA

© Copyright Reserved
All rights reserved. Apart from any fair dealing for the purpose of research criticism or review as permitted under
Copyright Act, no part of this document may be reproduced or transmitted in any other form or by any means,
electronic or mechanical, including photocopy and recording, without permission in writing from the publisher.

Acknowledgements Thank you to STUDY OPPORTUNITIES for allowing us to use

their publications to compile these notes.

CSF 10 BT / FIS 11 BT #.1

Downloaded by Frank Cruz ([email protected])

 lOMoARcPSD|21122727

Chapter 1 Data Representation

When you have completed this chapter, you should be able to:
 understand the decimal, binary, octal and hexadecimal number systems and be able
to convert form integer;
 write integers in sign-and-size code.

1. Introduction
A computer is based on the most basic beginnings of 2 electronic states. The electronic circuits
of a computer can only be in one of two states: ‘on’ or ‘off’. A bit (binary digit) represents these
two states. There are therefore two values which a bit or binary digit can be, namely 0 and 1.
One could say that strings of ones and zeros are the mother tongue of the computer!

2. Grouping of bits
Computer manufacturers use a grouping of bits to represent letters, figures and special
characters such as ? or +. A group of eight bits is called a byte.

A computer word is the number of bits that can be handled as a unit. The word length of
computers differs. In modern computers it is normally 32 or 64 bits.

3. Number systems
There are different number systems. The number system that is familiar to us is called the
decimal number system.

The decimal number system uses ten symbols (0, 1, 2, 3, 4, 5, 6, 7, 8, and 9) to represent
numbers. The decimal number system therefore has a base of 10.

The following table shows the properties of different number systems.

Number Base Number of Symbols used to represent Example of the
system symbols numbers number 12
Decimal 10 10 0123456789 12
Binary 2 2 01 1100
Octal 8 8 01234567 14
Hexadecimal 16 16 0123456789ABCDEF C

3.1 Place value

Consider the decimal number 612. The value of the 6 in 612 is 600. For the value 68, 6’s place
value is 60

The place of the figure determines its value. This concept is the same for all number systems.
The place values of the decimal number system are shown in the following table.
Power 103 102 101 100 10-1 10-2 10-3
Place value 1000 100 10 1 0,1 0,01 0,001
Example of number 5 3 4 7 , 2 3 1
3.2 Expanded notation
By multiplying numbers with their place values, you can write numbers in expanded notation.

CSF 10 BT / FIS 11 BT #.2

Downloaded by Frank Cruz ([email protected])

 lOMoARcPSD|21122727

Examples:
5347,23110 = 5x103 + 3x102 + 4x101 + 7x100 + 2x10-1 + 3x10-2 + 1x10-3
702,0710 = 7x102 + 0x101 + 2x100 + 0x10-1 + 7x10-2

Take note: Since we are working with different number systems you must include the
base to ensure that everybody knows in which number system you are
working. If you do not include the base, marks will be deducted in this module.

4. Binary number system

We have already seen that the binary number system consists of the numbers 0 and 1.
The place values of the binary number system are shown in the following table.
Power 23 22 21 20 2-1 2-2 2-3
Place value 8 4 2 1 0,5 0,25 0,125
Example of number 1 1 0 1 , 1 0 1

4.1 Expanded notation

Example:
1101,1012 = 1 x 23 + 1 x 22 + 0 x 21 + 1 x 20 + 1 x 2-1 + 0 x 2-2 + 1 x 2-3

Take note: The methods used in this module and these notes, will be the only methods
that will be marked. Indicate all steps to get full marks!

4.2 Converting from binary to decimal

If a binary number is written in expanded notation, it is easy to calculate the decimal number.
Do the following to obtain the decimal value of a binary number.

• Write the number in expanded notation

• Multiply each number with its place value
• Add these values together to obtain the decimal value.

Example 1: Convert 10112 to a decimal number.

10112 = 1x23 + 0x22 + 1x21 + 1x20 Write the number in expanded notation.
= 1x8 + 0x4 + 1x2 + 1x1 Multiply each number with its place value.
= 8+0+2+1 Add these values together to obtain the
= 1110 decimal value.

Example 2: Convert 11011012 to a decimal number.

11011012 = 1x26 + 1x25 + 0x24 +1x23 + 1x22 + 0x21 + 1x20
= 1x64 + 1x32 + 0x16 + 1x8 + 1x4 + 0x2 + 1x1
= 64 + 32 + 0 + 8 + 4 + 0 + 1
= 10910

CSF 10 BT / FIS 11 BT #.3

Downloaded by Frank Cruz ([email protected])

 lOMoARcPSD|21122727

Example 3: Convert 100111,012 to a decimal number.

The conversions can also be done by writing the place values above each binary number and
then adding the place values, which are not zero together.
You must add decimal
numbers, else your
answer will be wrong!

100111,012 = 1x25 + 0x24 +0x23 + 1x22 + 1x21 + 1x20 + 1x2-1 + 1x2-2

= 1x32 + 0x16 + 0x8 + 1x4 + 1x2 + 1x1 + 1x0,5 + 1x0,25
= 32 + 0 + 0 + 4 + 2 + 1+ 0,5 + 0,25
= 39,7510

Example 4: Convert 101,1012 to a decimal number.

101,1012 = 1x22 + 0x21 + 1x20 + 1x2-1 + 0x2-2 + 1x2-2
= 1x4 + 0x2 + 1x1 + 1x0,5 + 0x0,25 + 0x0,125
= 4 + 0 + 1+ 0,5 + 0 + 0,125
= 5,62510

You can test your answer by using the place value. Therefore, for Example 4 you can test
your answer as follows:

Step 1: Write down the place values of the binary number system. It is only necessary to
write down the place values smaller or equal to 510 and bigger or equal to
0,62510

Place values 4 2 1 0,5 0,25 0,125

Step 2: Start at the left-hand side of the decimal comma, and determine from left to right
what combination of place values make up the number 510

Place values 4 2 1
Number 1 0 1

1 + 4 = 510

Step 3: Start at the decimal comma and determine from right to left what combination of
place values make up the fraction 0,62510

Place values 4 2 1 0,5 0,25 0,125

Number 1 0 1 , 1 0 1

4 + 1+ 0,5 + 0,125 = 5,62510

Therefore 5,62510 = 101,1012

CSF 10 BT / FIS 11 BT #.4

Downloaded by Frank Cruz ([email protected])

 lOMoARcPSD|21122727

Exercise
1. Convert the following binary numbers to decimal numbers.

a) 10102 b) 111112 c) 1010012

d) 110011002 e) 100000112 f) 111011112
g) 101,1012 h) 1100,0112 i) 10111,1012

4.3 Converting from decimal to binary

The integer and fractional parts of each number are done separately.

4.3.1 The integer part

With integer conversion, division by two takes place successively until the quotient becomes 0.
In each step the remainder (0 or 1) will be the binary digit in that column. The binary integer is
written from bottom to top.

Example 1: Convert 9010 to a binary number.

Step 1: Divide by 2 until the answer is 0. Write the remainder of each division on the right-
hand side

2 90
2 45 r 0
2 22 r 1
2 11 r 0
2 5 r 1
2 2 r 1
2 1 r 0
0 r 1

Step 2: Write the remainders down from bottom to top.

Therefore 9010 = 10110102

Example 2: Convert 13710 to a binary number.

2 137
2 68 r 1
2 34 r 0
2 17 r 0
2 8 r 1
2 4 r 0
2 2 r 0
2 1 r 0
0 r 1

Therefore 13710 = 100010012

CSF 10 BT / FIS 11 BT #.5

Downloaded by Frank Cruz ([email protected])

 lOMoARcPSD|21122727

4.3.2 Fractional part

Multiply the fraction by two, until it becomes 0. The digit (0 or 1) in the left most column will be
the decimal fraction. The binary fraction is written from top to bottom.

Example 3: Convert 0,2510 to a binary number.

Step 1: Multiply by 2 until the answer is 0.

25 You must write down a carry over of 0

X2 on the left most column, else your
0 50 answer will be wrong!
X2
1 00

Step 2: Write the left most column down from top to bottom.

Therefore 0,2510 = 0,012

Example 4: Convert 0,87510 to a binary number.

875
X2
1 750
X2
1 500
X2
1 000
Therefore 0,87510 = 0,1112

4.3.3 To convert a decimal number with a fraction

Example 5: Convert 17,2510 to a binary number.
Step 1: Determine the integer part

2 17
2 8 r 1
2 4 r 0
2 2 r 0
2 1 r 0
0 r 1
Therefore 1710 = 100012

Step 2: Determine the fractional part

25
X2
0 50
X2
1 00
Therefore 0,2510 = 0,012

CSF 10 BT / FIS 11 BT #.6

Downloaded by Frank Cruz ([email protected])

 lOMoARcPSD|21122727

Step 3: Combine the answers for the two separate parts

Therefore 17,2510 = 10001,012

You can test your answer by using the place value. For the above example (i.e. Example 5)
you can test your answer as follows:

Step 1: Write down the place values of the binary number system. It is only necessary to
write down the place values smaller or equal to 1710 and bigger or equal to
0,12510

Place values 16 8 4 2 1 0,5 0,125

Step 2: Start at the left-hand side of the decimal comma, and determine from left to right
what combination of place values make up the number 1710

Place values 16 8 4 2 1
Number 1 0 0 0 1

1 + 16 = 1710

Step 3: Start at the decimal comma and determine from right to left what combination of
place values make up the fraction 0,12510

Place values 16 8 4 2 1 0,5 0,125

Number 1 0 0 0 1 , 0 1

16 + 1+ 0,125 = 17,2510

Therefore 17,2510 = 1011012

Exercise
1. Convert the following decimal numbers to binary numbers.

a) 2710 b) 8510 c) 11210 d) 12510 e) 10010

f) 93,12510 g) 145,510 h) 179,62510 i) 251,87510 j) 300,2510

5. Hexadecimal number system

The base of the hexadecimal number system is 16. Therefore the hexadecimal number system
consists of 16 different elements. The first 10 elements in the hexadecimal number system are 0
to 9.

Because the elements of a number system must all be single symbols, the hexadecimal number
system uses the letters A, B, C, D, E and F as elements to represent the values 10 to 15. This is
shown in the table:

CSF 10 BT / FIS 11 BT #.7

Downloaded by Frank Cruz ([email protected])

 lOMoARcPSD|21122727

Decimal Hexadecimal
10 A
11 B
12 C
13 D
14 E
15 F

The table of place values of the hexadecimal number system is as follows:

Power 162 161 160 16-1

Place value 256 16 1 0,06255
Example of number 1 A 7 , 2

The hexadecimal number 1A7,216 can be written in expanded notation as follows:

1A7,216 = 1x162 + Ax161 + 7x160 + 2x16-1

= 1x256 + 10x16 + 7x1 + 2x0,0625
= 256 + 160 + 7 + 0,125
= 423,12510

5.1 Converting from hexadecimal to decimal

If a hexadecimal number is written in expanded notation, it is easy to calculate the decimal
value. The same method used for conversion of binary to decimal is followed:

• Write the number in expanded notation.

• Multiply each number with its place value.
• Add these numbers together to obtain the decimal value.

Example: Convert AF316 to a decimal number.

AF316 = A x 162 + F x 161 + 3 x 160 Write the number in expanded notation.
= A x 256 + F x 16 + 3 x 1 Multiply each number with its place value.
= 10 x 256 + 15 x 16 + 3 x 1
= 2560 + 240 + 3 Add these numbers together to obtain the
= 280310 decimal value.

You can test your answer by using the place value.

Place values 256 16 1

Number A F 3

2560 + 240 + 3 = 280310

CSF 10 BT / FIS 11 BT #.8

Downloaded by Frank Cruz ([email protected])

 lOMoARcPSD|21122727

5.2 Converting from decimal to hexadecimal

Example 1: Convert 28510 to a hexadecimal number.

Step 1: Divide by 16 until the answer is 0. Write the remainder of each division on the right-
hand side

16 285 The remainder was 13, but 13 is

16 17 rD represented by a D in hexadecimal and
16 1 r1 therefore you must write the D and not the
0 r1 13.

Step 2: Write the remainders down from bottom to top.

Therefore 28510 = 11D16

You can test your answer by using the place value.

Place values 256 16 1

Number 1 1 D

256 + 16 + 13 = 28510

Exercise
1. Convert the following hexadecimal numbers to decimal.
a) 2416 b) A216 c) 11016
d) B0316 e) AB1216 f) 1BCD16

2. Convert the following decimal numbers to hexadecimal.

a) 2010 b) 3710 c) 12010
d) 29010 e) 145610 f) 120010

6. Converting from binary to hexadecimal

Hexadecimal values are a shorter notation of the binary equivalent. The contents of files of data
are sometimes given in hexadecimal code. The conversion between the binary number system
and the decimal number system is very easy. Sometimes the hexadecimal code is used for a
shorter notation than binary code.

Following the relationship between the place values of binary numbers and the hexadecimal
numbers, the conversion between this number system is very simple and quick. Each group of
four bits is replaced with a hexadecimal number.

Example 1: Convert 101110012 to a hexadecimal number.

Step 1: Start at the binary comma and divide the binary number into groups of four. (You can
add extra zeros in front to form groups of four – see next example).

1011 1001
CSF 10 BT / FIS 11 BT #.9

Downloaded by Frank Cruz ([email protected])

 lOMoARcPSD|21122727

Step 2: Replace each group with a hexadecimal number.

1011 1001
B 9

1011 10012 = B916

Example 2: Convert 11011111012 to a hexadecimal number.

0011 0111 1101

3 7 D

11 0111 11012 = 37D16

7. Converting from hexadecimal to binary

Example 1: Convert A316 to a binary number.

To convert a hexadecimal number to a binary number, each hexadecimal number must be
written as a binary number of four bits.

A 3
1010 0011

A316 = 1010 00112

Example 2: Convert 2C716 to a binary number.

2 C 7
0010 1100 0111
Zero’s in front of a number has no
meaning; therefore you do not need
2C716 = 10 1100 01112
to write it down. It is not wrong to
leave it, i.e. 0010 1100 01112

CSF 10 BT / FIS 11 BT #.10

Downloaded by Frank Cruz ([email protected])

 lOMoARcPSD|21122727

Exercise
1. Convert the following binary numbers to hexadecimal.

a) 100111002 b) 1011012 c) 1112

d) 10111111112 e) 1000000100002 f) 1010011002

2. Convert the following hexadecimal numbers to binary.

a) A716 b) D1516 c) 100016
d) AAB16 e) 34E16 f) 5E816

3. Complete the letters a - j of the following table.

Base 2 Base 10 Base 16
a b AF
c 75 d
101111 e f
g h 12A
i 125 j

4. Write the number 13 as a

a) hexadecimal number
b) binary number

5. Determine the value of X in each of the following cases.

a) X2 = 1610 b) X10 = 21016 c) 10012 = X10
d) 10016 = X2 e) A3516 = X10 f) 23110 = X16
g) 12110 = X2 h) 101111102 = X16 i) X8 = 11210

6. Give the answer for each of the following:

a) The decimal value of 10016.
b) The hexadecimal value of 17810.
c) The binary value of 10110.
d) The hexadecimal value of 10010002.
e) The decimal value of 1100112.
f) The binary value of BC216.

CSF 10 BT / FIS 11 BT #.11

Downloaded by Frank Cruz ([email protected])

 lOMoARcPSD|21122727

Chapter 2 Binary addition, internal representation and two’s

complement arithmetic
When you have completed this chapter, you should be able to
 add binary numbers;
 write integers in sign-and-size code;
 convert integer numbers to two’s complement and visa versa.
 do two’s complement arithmetic

1. Introduction
All data is represented in a computer in one of two conditions, zeros and one’s. To be able to
understand better how a computer works, it is useful to know how numbers are represented in a
computer.

Fewer mistakes are made when the correct data types are used in Turbo Pascal. When
programming in Pascal, it is important to know how the different types of data such as REAL,
INTEGER and LONGINT are represented in the computer.

In other programs such as a database, it is important to know that we get different data types,
for example, integers and real and that the internal representation differs.

2. Addition of binary numbers

The addition of binary numbers works according to the same principles as those of the decimal
number system. Let us see what happens when two decimal numbers are added:

Transfer 111
768
+475
1243

It is always done from right to left.

The following combinations exist when two single digit binary numbers are added:

0 0 1 1
+0 +1 +0 +1
0 1 1 10 (transfer of 1)

Example 1: Calculate the following: 101012 + 102

Transfer (none)
10101
+ 10
1 0 1 1 12

CSF 10 BT / FIS 11 BT #.12

Downloaded by Frank Cruz ([email protected])

 lOMoARcPSD|21122727

Example 2: Calculate the following: 101112 + 1102

Transfer 11
10111
+ 110
1 1 1 0 12

Remember: 12 + 12 + 12 = 112

Example 3: Calculate the following: 111012 + 1112 + 10112

Transfer 1 1 1 1
11101
When three or more numbers must be
+ 111
added, the chances of making a mistake
100100
becomes much smaller if the first two
+ 1011
numbers are added and then the third one
1 0 1 1 1 12

To check whether the addition was correctly done, the numbers may be changed to decimals.

111012 = 1x24 +1x23 + 1x22 + 0x21 + 1x20

= 1x16 + 1x8 + 1x4 + 0x2 + 1x1
= 16 + 8 + 4 + 0 + 1
= 2910

1112 = 1x22 + 1x21 + 1x20

= 1x4 + 1x2 + 1x1
= 4+2+1
= 710

You can do the same with the other numbers:

111012 + 1112 + 10112 = 1011112

2910 + 710 + 1110 = 4710

The addition was therefore correctly done.

Exercise
1. Calculate the following:

a) 10012 + 1102 b) 11102 + 1012

c) 1011112 + 11112 d) 11112 + 1112
e) 10112 + 11112 + 1012 f) 1100002 + 10112 + 11112

CSF 10 BT / FIS 11 BT #.13

Downloaded by Frank Cruz ([email protected])

 lOMoARcPSD|21122727

3. Internal representation of integers

Digital systems like computers must be able to represent positive and negative numbers. There
are three methods of representing positive and negative integers namely the
• sign-and-size code
• one’s complement
• two’s complement

3.1 The sign-and-size code

This code uses the ordinary binary equivalent of a number and places an extra bit in the front in
order to represent the sign. In the case of a positive number, the extra bit will be a 0, and in
the case of a negative number, the extra bit will be a 1.

Example 1: Use 1 byte to represent the numbers, -12 and 12, in the sign-and-size-code.

2 12
2 6 r 0
2 3 r 0
2 1 r 1
0 r 1
Therefore 1210 = 11002

Take note: One byte (7 bits + sign bit = 8 bits) is used throughout for the representa-
tions.

One byte (7 bits + the sign bit = 8 bits) is used throughout for the representations.
Sign-and-size-code:

12 0 0 0 0 1 1 0 0

-12 1 0 0 0 1 1 0 0

Example 2: Convert the number -120 to the sign-and-size-code and represent it in 1 byte.
2 120
2 60 r 0
2 30 r 0
2 15 r 0
2 7 r 1
2 3 r 1
2 1 r 1
0 r 1
Therefore 12010 = 11110002
Sign-and-size-code:
For readability and to
-12010 1 1 1 1 1 0 0 0
use a standard format
throughout, you must
We will write it as: -12010 = 1 1111 0002 write the sign bit, leave
a space followed by four
digits, a space, and the
CSF 10 BT / FIS 11 BT remaining three digits. #.14

Downloaded by Frank Cruz ([email protected])

 lOMoARcPSD|21122727

The sign-and-size method is not generally used in computers. This type of representation results
in problems when adding is done, as the sign bit must be handled separately from the rest of
the number.

Example 3: Add -12 to 12. (We have used the conversion in Example 1 to just add the two
numbers)

1 0001 100
+0 0001 100
1 0 0 1 1 0 0 02

Convert the answer to a decimal number:

110002 = 1x24 + 1x23 + 0x22 + 0x21 + 0x20

= 1x16 + 1x8 + 0x4 + 0x2 + 0x1
= 16 + 8 + 0 + 0 + 0
= 2410

Therefore 1 0011 0002 = -2410

The answer is -2410, which is wrong. We know the answer is 0. The two’s complement
representation solves this problem.
Exercise

1. Represent the following decimal numbers in the sign-and-size code. Use 1 byte for the
representation.
a) 6710 b) -3510 c) 9710
d) -12410 e) -12710 f) -11110

2. The following binary numbers are written in sign-and-size code. Write down the decimal
equivalent.
a) 0 0001 1012 b) 1 0111 0002 c) 0 0011 1012
d) 1 1101 1112 e) 1 0101 0102 f) 1 1111 1012

3.2 Two’s complement representation

Two’s complement is used in computers to do manipulations with positive and negative
numbers. Two’s complement is the most generally used representation of integers. Programmers
of computers writing in low-level languages like Assembler, use two’s complement to represent
numbers.

3.2.1 Conversion of positive decimal numbers to two’s complement

The two’s complement representation of a positive number is the binary value of the number
with a 0 in front to indicate that it is a positive number. Two’s complement representation of a
positive number is thus the same as that in sign-and-size code.

CSF 10 BT / FIS 11 BT #.15

Downloaded by Frank Cruz ([email protected])

 lOMoARcPSD|21122727

Take note: You should know now how to convert numbers. We will only give the
answers in the examples that follow.

Example 1: Give the two’s complement representation of the number 1510.

1510 = 0 0001 1112

Example 2: Give the two’s complement representation of the number 8710.

8710 = 0 1010 1112

Example 3: Give the two’s complement representation of the number 12310.

12310 = 0 1111 0112

3.2.2 Conversion of negative decimal numbers to two’s complement

The followings steps are followed to write a negative number in two’s complement:

1. Change the positive number to a binary number and add zeros in front so that the number is
made up of 8 bits.
2. Change all one’s to zero’s and zero’s to one’s.
3. Add 1.

Example 1: Give the two’s complement representation of the number -7110.

Step 1: Convert 7110 to a binary number. Use one byte for the representation.

7110 = 0 1000 1112 (You know how to get this answer)

Step 2: Change all one’s to zero’s and zero’s to one’s.

1 0111 0002

Step 3: Add 1.

1 0111 000
+ 1
1 0 1 1 1 0 0 12

Example 2: Give the two’s complement representation of the number -2010.

2010 = 0 0010 1002 Convert 2010 to a binary number

1 1101 0112 Change the numbers

1 1101 011 Add 1

+ 1
1 1 1 0 1 1 0 02

CSF 10 BT / FIS 11 BT #.16

Downloaded by Frank Cruz ([email protected])

 lOMoARcPSD|21122727

3.2.3 Conversion from two’s complement to decimal

Example 1: Determine the decimal value of the two’s complement value of 001001102.
This representation is for a positive number because the left hand bit is 0. To obtain the decimal
value, the binary number must be converted back to decimals.

Therefore 0 0100 1102 = 3810

Example 2: Determine the decimal value of the two’s complement representation

1 0110 1112.

The conversion of a negative two’s complement number to decimal is done as follows:

1. Change all one’s to zero’s and all zero’s to one’s.
2. Add 1.
3. Give the decimal value of the binary representation. Remember that the sign is negative!

Step 1: Change all one’s to zero’s and all zero’s to one’s of the number 1 0110 1112.

0 1001 0002

Step 2: Add 1.

0 1001 0012

Step 3: Give the decimal value of the binary representation.

Therefore 1 0110 1112 = -7310

Exercise
1. Represent the following decimal numbers in the sign-and-size code. Use one byte for the
representation.
a) 3710 b) -5610 c) 8110
d) -11110 e) 10810 f) -12710

2. The following numbers are represented in the sign-and-size code. Give the decimal value
of each representation.
a) 0 0110 1012 b) 0 1110 1112 c) 1 0000 1002
d) 1 1101 1112 e) 0 0001 1012 f) 1 1001 1102

3. Change the following decimal numbers to two’s complement. Use one byte for the
representation.
a) 2510 b) 8110 c) -10210
d) 12610 e) -9910 f) -12310

4. The following binary numbers are represented in two’s complement. Give the decimal
value of each.
a) 0 0101 0102 b) 0 1110 0012 c) 1 0110 1112
d) 1 1111 1102 e) 0 1101 0012 f) 1 0011 1102

CSF 10 BT / FIS 11 BT #.17

Downloaded by Frank Cruz ([email protected])

 lOMoARcPSD|21122727

4. Two’s complement arithmetic

Of all the functions that a computer can perform, addition is the most basic, essential,
arithmetical process. Addition forms the foundation of all the other arithmetical processing
because:

Addition is the complement of subtraction. For example:

65 - 13 = 52
65 + (-13) = 52

Multiplication is repeated addition

5 x 65 = 65 + 65 + 65 + 65 + 65

Division is accomplished using subtraction repeatedly. The number of times the divisor is
subtracted from the dividend is the answer. Division is therefore the repeated addition of the
complement until the result is equal to zero or smaller than the divisor.

260
- 65 1
195
- 65 2
130
- 65 3
65
- 65 4
0
260, 65 = 4

The following steps are used when doing complement arithmetic:

1. Give the binary representation of the numbers in one byte. Add zeros in front so that each
representation consists of 8 bits.
2. Rewrite the subtraction as the “addition of the complement”.
3. Do the necessary binary addition.
4. If there are more than eight bits, ignore the extra bits (left hand side).
5. Write the answer again as decimal numbers if it is requested.

Example 1: Calculate the following by making use of complement arithmetic:

5410 - 1310. Convert the answer back to decimals.

Step 1: Give the binary representation of the numbers in one byte.

5410 – 1310 = 0 0110 1102 - 0 0001 1012

Step 2: Rewrite the subtraction as ‘an addition of the complement’. (K2 means the two’s
complement of the value in brackets.)
= 0 0110 110 + K2(0 0001 101)

CSF 10 BT / FIS 11 BT #.18

Downloaded by Frank Cruz ([email protected])

 lOMoARcPSD|21122727

Step 3: Do the necessary binary addition.

= 00110110
+11110011
100101001

Step 4: If there are more than eight bits, ignore the extra bits on the left hand side.

= 0 0101 0012

Step 5: Write the answer again as a decimal number. 0 0101 0012 is a positive number. The
conversion is therefore easy. 0 0101 0012 = 4110. (You know how to do this)

= 4110

Example 2: Calculate the following by making use of complement arithmetic:

9010 - 12010. Convert the answer back to decimals.

Step 1: Give the binary representation of the numbers in one byte.

9010 – 12010 = 0 1011 0102 - 0 1111 0002

Step 2: Rewrite the subtraction as ‘an addition of the complement’. (K2 means the two’s
complement of the value in brackets.)

= 0 1011 010 + K2(0 1111 000)

Step 3: Do the necessary binary addition.

= 01011010
+10001000
11100010

Step 4: If there are more than eight bits, ignore the extra bits on the left hand side.

= 1 1100 0102

Step 5: The answer is negative. The two’s complement number must be transformed into a
decimal number. (- K2(1 1100 010) = - 0 0011 1102 = - 3010)

= -3010

CSF 10 BT / FIS 11 BT #.19

Downloaded by Frank Cruz ([email protected])

 lOMoARcPSD|21122727

Example 3: Calculate -3410 – 3510 by using complement arithmetic and give the answer in
decimal.

-3410 – 3510 = - 0 0100 0102 – 0 0100 0112

= K2(0 0100 010) + K2(0 0100 011)
= 1 1011 110 + 1 1011 101

11011110
+ 11011101
110111011

= - K2(1 0111 011)

= - 0 1000 1012
= - 6910

Exercise
1. Represent the following numbers in two’s complement: 127 and 4. Use 1 byte for the
representation.

2. Calculate the following by making use of two’s complement arithmetic. Check the answers
by changing the two’s complement answers to decimal numbers.

a) 6410 - 2110 b) 3210 - 7110 c) -2710 - 3210

d) -8810 - 1210 e) 2110 - 3410 - 1110 f) 23 + 2116 - 348 – 112
g) + 48 - 2A16 – 11010 2 - 1110

CSF 10 BT / FIS 11 BT #.20

Downloaded by Frank Cruz ([email protected])

 lOMoARcPSD|21122727

Chapter 3 Binary logic

When you have completed this chapter you should be able to
 write down a definition of a Boolean variable
 give all the possible outputs of each of the Boolean operators AND, OR and NOT
 evaluate Boolean functions for all given variables
 express Boolean functions in terms of truth tables and minterms
 simplify a Boolean function by means of a Karnaugh diagram
 represent Boolean functions by means of circuit diagrams

1. Introduction
A computer works on the basic principle of one of two electronic conditions. The two conditions
are represented in the circuits of the computer as either a low or a high voltage (either 0 or 5
Volts for example). The two conditions are also represented by ‘on' or ‘off', ‘1' or ‘0', TRUE or
FALSE. Operations within the computer are done with the two conditions as basis. It is
convenient to use 0 and 1 to represent these two conditions because people are used to work
with numbers.

A unique algebra is designed for the binary number system (0 and 1). George Boole (1815 -
1864), an English mathematician, developed this algebra known as Boolean algebra. Boolean
algebra is a branch of mathematics and involves TRUE or FALSE logic. It was only in 1938 that
C. E. Shannon demonstrated that this algebra could be used in electronic circuitry. Knowledge of
Boolean algebra is useful in the design of the modern computer.

Where is Boolean algebra used?

 A computer uses it in the CPU for operations.

 It is also used in the support systems of the computer, for example in the screen card,
keyboard, and the control card of the disk drive.
 Boolean algebra is also used in the design of electronic circuits. An example of this can be
found in an air conditioner:

A circuit for temperature control in an air conditioner can be designed by using Boolean algebra
to do the following:

o At temperatures above 210 C, switch the air conditioner on.

o At temperatures below 190 C, switch the air conditioner off.

The temperature is regulated to be approximately 200 C. For the circuit the temperature
being the input variable and the switch of the air conditioner being the output.

2. Basic concepts of Boolean algebra

Binary logic consists of theorems, which can be only true or false, and the manipulation thereof.
Like algebra, Boolean algebra also has rules about variables, operators and order of precedence,
etc.

CSF 10 BT / FIS 11 BT #.21

Downloaded by Frank Cruz ([email protected])

 lOMoARcPSD|21122727

2.1 Variables
A Boolean variable can only have one of two values, namely TRUE or FALSE.
In algebra it can be represented by a 1 or a 0, and in a physical circuit by a switch, which can be
CLOSED or OPEN.

A single letter of the alphabet represents a Boolean variable. A capital letter or a small letter can
be used, for instance A, B, x, y.

Value of variable Value in algebra Physical representation by switches

TRUE 1
Current flow

FALSE 0
Current does not flow

2.2 Operators
Like arithmetic, where +, -, x, and ÷ are operators, Boolean algebra also has operators. The
basic operators of Boolean algebra are AND (.), OR (+) and NOT (’). Remember that Boolean
operators are used throughout this chapter. The value of a Boolean variable can only be 0 or 1!

2.2.1 AND-operator
Notation: C = A.B (Read as “C equals A AND B”.)
C = AB
The AND-operator can be illustrated using a circuit diagram with two switches, A and B,
connected in series.

A B
+ S The light bulb L will be on only if
L switch A and switch B are closed.

In other words all the variables have to be 1 in order for the outcome to be 1.

2.2.2 OR-operator
Notation: C=A+B (Read “C equals A OR B”.)

The OR operator can be illustrated using a circuit diagram with two switches, A and B, connected
in parallel.
A

The light bulb L will be on if

B
switch A or switch B or both
+ S are closed.
L

In other words if at least one of the variables equals one, the outcome will be 1.
CSF 10 BT / FIS 11 BT #.22

Downloaded by Frank Cruz ([email protected])

 lOMoARcPSD|21122727

2.2.3 NOT-operator
Notation: B = A' (Read “B equals NOT A” or “B equals A complement”.)

Take note: We are suppose to write NOT A as A. However, the character size of most
of the letter types differs. In most cases, this causes the NOT-sign not to
be properly above the correct variable (letter). It makes readability quite
difficult. Therefore, for this module we will use the ' (apostrophe) (as
seen above) to indicate the NOT.

The NOT operator always changes the value:

 if the value of the variable is 1, the NOT operator will change 1 to 0.
 if the value of the variable is 0, the NOT operator will change 0 to 1.

2.3 Order of precedence

A Boolean expression results when one combines Boolean variables with Boolean operators, for
example A.B + A'.B. This expression contains Boolean variables, A and B, and the following
operators; AND(.), OR(+) and NOT(').

The Boolean expression can also be expressed in function notation (F-notation):

F(A,B) = A.B + A'.B

In ordinary algebra, we have a certain order of precedence of the operators. In Boolean algebra
we also have a certain order of precedence namely:

1. Brackets
2. NOT
3. AND
4. OR

3. Truth tables
Consider the following examples where functions are evaluated for all possible combinations of
values of the variables used in the function.

Example 1: Evaluate the Boolean function F(A,B) = A.B for all possible combinations of
values that the variables can have.

There are two Boolean variables namely A and B. The two variables can have 22=4 different
combinations.

A B A.B
0 0 0
0 1 0
1 0 0
1 1 1

CSF 10 BT / FIS 11 BT #.23

Downloaded by Frank Cruz ([email protected])

 lOMoARcPSD|21122727

Example 2: Evaluate the Boolean function F(A,B) = A + B for all possible combinations of
values that the variables can have.

There are two Boolean variables namely A and B. The two variables can have 22=4 different
combinations.

A B A+B Remember that the variables

0 0 0 must always be in alphabetical
0 1 1 order!
1 0 1
1 1 1

Example 3: Evaluate the Boolean function F(x,y) = xy + x'+ y for all possible combinations
of values that the variables can have.

x y x' xy xy + x'+ y
0 0 1 0 1
0 1 1 0 1
1 0 0 0 0
1 1 0 1 1

Take note: Do the calculation in a series of steps, column by column. First determine all
NOT’s then combinations of variables. Therefore, reduce the expression to its
most simple form. For example, do a' in a separate column and thereafter a'c
(see Example 4).

Example 4: Evaluate the Boolean function F(a,b,c) = ab + a'c + b for all possible
combinations of values that the variables can have.

With three variables there are 23=8 different combinations.

a b c a' ab a'c ab + a'c + b

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

We can also use truth tables to determine whether two functions are equal to one another.

CSF 10 BT / FIS 11 BT #.24

Downloaded by Frank Cruz ([email protected])

 lOMoARcPSD|21122727

Example 5: Determine whether F=G by using a truth table. F(x,y,z)=x+y and

G(x,y,z)=x'y+xy'+xy.
Instead of
writing down
x y z x' y' x'y xy' xy x+y x'y+xy'+xy
the functions
0 0 0 1 1 0 0 0 0 0
you can just
0 0 1 1 1 0 0 0 0 0
write F and G
0 1 0 1 0 1 0 0 1 1
in the last two
0 1 1 1 0 1 0 0 1 1
columns.
1 0 0 0 1 0 1 0 1 1
1 0 1 0 1 0 1 0 1 1
1 1 0 0 0 0 0 1 1 1
1 1 1 0 0 0 0 1 1 1
Thus F(x,y,z) = G(x,y,z)
You must give an answer. If F and G were not
equal to one another you must write:
Thus F(x,y,z) = G(x,y,z).

Example 6: Determine whether F=G by using a truth table. F(a,b,c)=ab+c and

G(a,b,c)=ac+b'c.
a b c b' ab ac b'c F G
0 0 0 1 0 0 0 0 0
0 0 1 1 0 0 1 1 1
0 1 0 0 0 0 0 0 0
0 1 1 0 0 0 0 1 0
1 0 0 1 0 0 0 0 0
1 0 1 1 0 1 1 1 1
1 1 0 0 1 0 0 1 0
1 1 1 0 1 1 0 1 1
Thus F(x,y,z) = G(x,y,z)

Exercise
1. Represent each of the following Boolean functions by using a truth table.
a) F(a,b) = a'b + a
b) F(x,y) = (x + y)' + x'y'
c) F(A,B,C) = A'B + B + C'
d) G(a,b,c) = a'b' + c' + (ab)'
e) G(w,x,y,z) = w'xy + (yz' + w)'

2. Determine whether F and G are equivalent (equal) by using a truth table.

a) F(x,y,z) = x+y.z and G(x,y,z) = (x + y)(x + z)
b) F(x,y,z) = (x + y + z)' and G(x,y,z) = x' + y' + z'
c) F(A,B,C) = AB+A'C+BC and G(A,B,C) = AB+A'C
d) F(a,b,c) = a'b'c + a'bc and G(a,b,c) = (a + b)'c + ab'c

3. Prove the following identities.

a) a + a'b = a + b
b) (xyz)' = x' + y' + z'
CSF 10 BT / FIS 11 BT #.25

Downloaded by Frank Cruz ([email protected])

 lOMoARcPSD|21122727

4. Laws of Boolean algebra

In Example 5 in the previous topic, the following was shown using a truth table:
F(x,y,z)=G(x,y,z) where F(x,y,z)=x+y and G(x,y,z)=x'y+xy'+xy.
x’y + xy’ + xy is thus the same as the less complex x + y. It is more efficient to build a circuit for
the function F(x,y,z) than for G(x,y,z). Boolean functions are simplified in order to find a less
complex function with the same output.

Consider the following Laws of Boolean algebra, which can be used to simplify Boolean
expressions.
Identity elements x+0=x x.1 = x
x+1=1 x.0 = 0
Commutative law x+y=y+x
x.y = y.x
Associative law x + (y + z) = (x + y) + z
x.(y.z) = (x.y).z
Distributive law x + (y.z) = (x + y).(x + z)
x.(y + z)= (x.y) + (x.z)
Complementary law x + x' = 1
x.x' = 0
De Morgan’s laws These theorems are related to compliments
(x + y)' = x'y'
(xy)' = x' + y'
Theorems for simplifications x + x = x
x.x = x
x + xy = x
x(x + y) = x
x + x'y = x + y
x(x' + y) = xy
xy + x'z + yz = xy + x'z
Take note: In this module we will not simplify Boolean functions using algebra, but by
means of Karnaugh diagrams (see later). It is however easier to
understand if you know the Laws of Boolean algebra.

5. Representation of Boolean functions in terms of minterms

5.1 What is a minterm?

We know that the operator + separates terms in a Boolean function. The function, F(x,y,z)=x’y
+ xyz + x(y’+z’), thus contains the terms x’y, xyz and x(y’+z’). In this example, only the term
xyz is a minterm.

A term is called a minterm if

 all the variables occur as plain variables or as complements in the term;

 and all the variables are separated with AND operators.

Every Boolean function can be expressed as the sum of minterms. You can therefore rewrite a
Boolean function so that all the terms are minterms.

CSF 10 BT / FIS 11 BT #.26

Downloaded by Frank Cruz ([email protected])

 lOMoARcPSD|21122727

Example 1: Rewrite F(x,y,z) = xyz' + x'yz' + x'y' so that all the terms are minterms.
F(x,y,z) = xyz' + x'yz' + x'y'
= xyz' + x'yz' + x'y'.1 because x'y'.1=x'y'
= xyz' + x'yz' + x'y'(z + z') because z+z'=1 (complementary law)
= xyz' + x'yz' + x'y'z + x'y'z' distributive law

In the above example x'y' is not a minterm (it does not contain all the variables – z is missing).
To make it a minterm you must use the AND-operator and add the variable(s) that is missing.
Apply the distributive law to make those terms minterms.

Example 2: Rewrite F(x,y,z) = x'y + y'z so that all the terms are minterms.
F(x,y,z) = x'y.1 + y'z.1
= x'y(z + z') + y'z(x + x')
= x'yz + x'yz' + xy'z + x'y'z

Example 3: Rewrite F(x,y,z) = y +xyz so that all the terms are minterms.
F(x,y,z) = y + xyz
= y.1 + xyz
= y(x + x') + xyz
= xy + x'y + xyz Because xyz+xyz=xyz
= xy.1 + x'y.1 + xyz you must draw a line
= xy(z + z') + x'y(z + z') + xyz through the repeated
= xyz + xyz' + x'yz + x'yz' + xyz minterms. You can
= xyz + xyz' + x'yz + x'yz' re-write the function.

Example 4: Rewrite F(w,x,y,z) = wx + w’x’y so that all the terms are minterms.
F(w,x,y,z) = wx.1 + w'x'y.1
= wx(y + y') + w'x'y(z + z')
= wxy.1 + wxy'.1 + w'x'yz + w'x'yz'
= wxy(z + z') + wxy'(z + z') + w'x'yz + w'x'yz'
= wxyz + wxyz' + wxy'z + wxy'z' + w'x'yz + w'x'yz'

5.2 Minterms
To write a function in the m-notation, all the terms of the function must be minterms.

5.2.1 Minterms for one variable

If one variable occurs, 21 possible minterms exists, namely X and X'.
X Term Notation
0 X' m0
1 X m1

CSF 10 BT / FIS 11 BT #.27

Downloaded by Frank Cruz ([email protected])

 lOMoARcPSD|21122727

5.2.2 Minterms for two variables

If there are two variables, there are 22 = 4 possible minterms.
X Y Term Notation
0 0 X'Y' m0
0 1 X'Y m1
1 0 XY' m2
1 1 XY m3

5.2.3 Minterms for three variables

If there are three variables, there are 23 = 8 possible minterms.
X Y Z Term Notation
0 0 0 X'Y'Z' m0
0 0 1 X'Y'Z m1
0 1 0 X'YZ' m2
0 1 1 X'YZ m3
1 0 0 XY'Z' m4
1 0 1 XY'Z m5
1 1 0 XYZ' m6
1 1 1 XYZ m7

5.2.4 Minterms for four variables

If there are four variables, there are 24 = 16 possible minterms.
W X Y Z Term Notation
0 0 0 0 W'X'Y'Z' m0
0 0 0 1 W'X'Y'Z m1
0 0 1 0 W'X'YZ' m2
0 0 1 1 W'X'YZ m3
0 1 0 0 W'XY'Z' m4
0 1 0 1 W'XY'Z m5
0 1 1 0 W'XYZ' m6
0 1 1 1 W'XYZ m7
1 0 0 0 WX'Y'Z' m8
1 0 0 1 WX'Y'Z m9
1 0 1 0 WX'YZ' m10
1 0 1 1 WX'YZ m11
1 1 0 0 WXY'Z' m12
1 1 0 1 WXY'Z m13
1 1 1 0 WXYZ' m14
1 1 1 1 WXYZ m15

CSF 10 BT / FIS 11 BT #.28

Downloaded by Frank Cruz ([email protected])

 lOMoARcPSD|21122727

5.3 M-notation
Functions can be written in m-notation.

Example 1: Write the function F(x,y) = x'y + xy as the sum of minterms in the m-notation.
F(x,y) = x'y + xy
= m1 + m3

Take note: To write a term quickly in it’s related m-notation do the following:

 Write 1 above a variable in un-complemented form and 0 above a

variable complemented form
1 1 0
x y z'
 Calculate the decimal value of the ‘binary number’. 1102 = 610
 Thus xyz' = m6

Example 2: Write the function F(x,y,z) = xyz' + xy'z' + x'y'z' as the sum of minterms in the
m-notation.
F(x,y,z) = xyz' + xy'z' + x'y'z'
= m6 + m4 + m0 You must always write or re-write
= mo + m4 + m6 the m-notation in numerical order.

Example 3: Write the function F(w,x,y,z) = w'xyz' + w'xz as the sum of minterms in the m-
notation.
F(w,x,y,z) = w'xyz' + w'xz
= w'xyz' +w'xz.1
= w'xyz' + w'xz(y + y')
= w'xyz' + w'xyz + w'xy'z
= m6 + m7 + m5
= m5 + m6 + m7

5.4 S-notation
To write a Boolean function in the S-notation, all the terms of the function must be minterms. S-
notation is the same as m-notation, just another manner of writing.

Function: F(x,y,z) = x'y'z' + x'yz + xy'z You must always write or re-
m-notation: F(x,y,z) = m0 + m3 + m5 write the s-notation in
S-notation: F(x,y,z) = S(0,3,5) numerical order.

CSF 10 BT / FIS 11 BT #.29

Downloaded by Frank Cruz ([email protected])

 lOMoARcPSD|21122727

Exercise

1. Write the following functions as the sum of minterms.

a) F(a,b) = a + b
b) F(x,y,z) = xy' + xz'
c) G(w,x,y,z) = wx'yz' + wx + y'z
d) F(a,b,c) = a + bc
e) G(A,B,C,D) = ABC + D

2. Write the following functions as the sum of minterms in the m-notation.

a) F(X,Y) = XY' + X'Y'

b) G(a,b,c) = a'b'c' + abc + b'c
c) F(w,x,y,z) = wxy'z' + w'x'y'z + wxyz + w'y'z + wxz'

3. Write the following functions as the sum of minterms in the S-notation.

a) G(x,y,z) = xy'z' + xy + yz
b) F(W,X,Y,Z) = Y
c) c) G(A,B,C) = A'B'C + AB'C + A'B d) G(a,b,c) = a'b + ab + a'b'c'

4. If F(x,y,z) = x'y'z + xy'z + x'yz' write F’(x,y,z) as the sum of minterms.

5. If G(a,b,c,d) = abcd + a'b'c write G’(a,b,c,d) as the sum of minterms in the m-notation.

6. If F(x,y,z) = S(0,1,3,5,6,7) write F’(x,y,z) as the sum of minterms.

7. If G(A,B,C,D) = m0 + m2 + m5 + m7 + m9 + m10 write G’(A,B,C,D) as the sum of

minterms in the S-notation.

CSF 10 BT / FIS 11 BT #.30

Downloaded by Frank Cruz ([email protected])

 lOMoARcPSD|21122727

6. Simplification by means of Karnaugh diagrams

We have already seen that the Boolean functions can be simplified. Some of the functions are
difficult to simplify algebraically. Karnaugh diagrams are a more systematic way of simplifying
the Boolean functions.

Let us look at the Karnaugh diagrams for different number of variables.

Karnaugh diagram for two variables

Y
0 1
X
m0 m1
0
X'Y' X'Y
m2 m3
1
XY' XY

Karnaugh diagram for three variables

YZ
00 01 11 10
X
m0 m1 m3 m2
0
X'Y'Z' X'Y'Z X'YZ X'YZ'
m4 m5 m7 m6
1
XY'Z' XY'Z XYZ XYZ'

Karnaugh diagram for four variables

YZ
00 01 11 10
WX
m0 m1 m3 m2
00
W'X'Y'Z' W'X'Y'Z W'X'YZ W'X'YZ'
m4 m5 m7 m6
01
W'XY'Z' W'XY'Z W'XYZ W'XYZ'
m12 m13 m15 m14
11
WXY'Z' WXY'Z WXYZ WXYZ'
m8 m9 m11 m10
10
WX'Y'Z' WX'Y'Z WX'YZ WX'YZ'

To simplify the Boolean functions by means of a Karnaugh diagram, the following steps must be
followed:

Step 1: Write the Boolean function in terms of minterms.

Step 2: Place the minterms on the Karnaugh diagram. Draw the Karnaugh diagram for the
number of variables namely two, three or four – see below. In the position of the
minterm, a 1 is placed. Refer to the previous discussions for the tables of minterms.

CSF 10 BT / FIS 11 BT #.31

Downloaded by Frank Cruz ([email protected])

 lOMoARcPSD|21122727

Step 3: Group the adjacent terms. An adjacent term is one that differs in respect of only
variable. The next two terms are adjacent: XYZ’ and XYZ. These terms differ only with
respect to Z. The algebraic simplification of XYZ’ and XYZ is as follows:
XYZ' + XYZ = XY(Z + Z')
= XY
If two adjacent terms are grouped together, they can be simplified to one term. Only
1, 2, 4, 8 and/or 16 number of terms may be grouped together. When grouping
minterms, we must try to group the maximum number of terms together, because the
more minterms that are grouped together, the fewer variables there are in the terms.

YZ
WX 00 01 11 10
Grouping B
00 1 1
1 1
01 Grouping A
1
11 1 1
Grouping C
10 1

Step 4: Make deductions from groupings in terms of variables. Therefore simplify, if possible,
each group and express it in terms of variables.

Grouping A
 The variables X and Z do not change in value in the grouping.
 The variables W and Y changes in value and may be omitted.
 The term for the grouping is thus XZ.

Grouping B
 The variables W’, X’ and Y’ do not change in value in the grouping.
 The variable Z changes in value and may be omitted.
 The term for the grouping is thus W'X'Y'

Grouping C
 The variables W, Y and Z’ do not change in value in the grouping.
 The variable X changes in value and may be omitted.
 The term for the grouping is thus WYZ'

Thus the simplified function is: F(X,Y,Z) = W'X'Y' + WYZ' + XZ

CSF 10 BT / FIS 11 BT #.32

Downloaded by Frank Cruz ([email protected])

 lOMoARcPSD|21122727

Example 1: Use a Karnaugh diagram to simplify F(a,b,c) = ac + ab’c’ + a’bc’ + ab.

Step 1: Write the Boolean function in terms of minterms.

F(a,b,c) = ac + ab'c' + a'bc' + ab Write each minterm in terms

= ac(b + b') + ab'c' + a'bc' + ab(c + c') of one’s (un-complement)
= abc + ab'c + ab'c' + a'bc' + abc + abc' and zeroes (complement) to
= abc + ab'c + ab'c' + a'bc' + abc' make it easier to place the
= 1.1.1 + 1.0.1 + 1.0.0 + 0.1.0 + 1.1.0 minterms on the Karnaugh
diagram.
Step 2: Place the minterms on the Karnaugh diagram.

bc
00 01 11 10
a
0 1

1 1 1 1 1

Step 3: Group the adjacent terms.

bc
00 01 11 10
a
1
0

1 1 1 1 1

Step 4: Make deductions from groupings in terms of variables. Simplify the function.

bc
00 01 11 10
a
1
0

1 1 1 1 1

F(a,b,c) = a + bc'

CSF 10 BT / FIS 11 BT #.33

Downloaded by Frank Cruz ([email protected])

 lOMoARcPSD|21122727

Example 2: Simplify the following function using a Karnaugh map and then divert the
simplest function:

F(W,X,Y,Z) = m0 + m1 + m3 + m7 + m8 + m9 + m14 + m15

YZ
WX 00 01 11 10 Remember you must group the
maximum number of terms
00 1 1 1 together. If you have group the
two terms in the first row, first
01 1 two columns and last row, first
two columns it would have seemed
11 1 1 right, but it is not the maximum
number of terms together. Also
10 1 1 remember we have said earlier
that it is more efficient to build the
circuit for the simplest function.
F(W,X,Y,Z) = X'Y' + W'YZ + WXY

Consider the following Karnaugh diagram and grouping.

Grouping 1

bc
a 00 01 11 10
1
0 1 1

1 1 1 1

Grouping 2

bc
a 00 01 11 10
0 1 1 1

1 1 1 1

A different grouping can also be made that will not be wrong. The simplified function will have
the same number of terms and the same number of variables in the relevant term.

CSF 10 BT / FIS 11 BT #.34

Downloaded by Frank Cruz ([email protected])

 lOMoARcPSD|21122727

Exercise
Use Karnaugh diagrams to represent the following Boolean functions. Deduce for each a function
with the fewest terms and the fewest variables in each term.

1. F(a,b) = a'b' + a'b

2. F(x,y) = S(0,1,2)
3. F(x,y,z) = x'y' + xz
4. F(a,b,c) = a'b'c + ab'c + abc' + ab
5. G(X,Y,Z) = S(0,1,4,5)
6. F(x,y,z) = m0 + m1 + m2 + m4 + m6
7. G(a,b,c,d) = S(1,2,3,6,8,10,11,12,14)
8. F(a,b,c,d) = a'bcd' + (ac + bc)d
9. F(W,X,Y,Z) = WXY'Z' + WY'Z' + WY'(X + X')
10. F(w,x,y,z) = m0 + m2 + m3 + m5 + m9 + m11 + m13 + m15

7. Circuits
In 1938 CE Shannon showed that Boolean algebra could be used to represent electronics
circuits. The symbolic representation of the AND, OR, NOT, NAND and NOR gates are given:

AND
X

Y

OR
X
+
Y

NOT

X X'

NAND
X

Y

NOR
X
+
Y

Take note: These are the only symbols accepted in this module. You must include the
sign inside the symbol, else the symbol is wrong.

CSF 10 BT / FIS 11 BT #.35

Downloaded by Frank Cruz ([email protected])

 lOMoARcPSD|21122727

Example 1: Draw the circuit for the function F(A,B) = A'B' + AB.
A

B

Take note: The Boolean variables A and B can have the value of 0 and 1. Different
voltage levels represent a 0 or a 1. A high voltage level represents a logical
1-state end a low voltage level a logical 0-state. The Boolean operators also
known as logic gates, is an electronic apparatus that has one or more
inputs and one output.

Example 2: Draw the circuit for the function f(x,y) = x + x'y + y.

y  +

Example 3: Draw the circuit for the function G(x,y,z) = (x + y + z)' + x'z'.

y +

z
+

Exercise
1. Draw circuits of the following Boolean functions:
a) F(a,b) = a + b + ab
b) G(x,y) = (x + y')' + y
c) F(x,y,z) = (x + y + z)' + (x'y')'
d) F(A,B,C) = AB + (A + C')' + BC
e) G(w,x,y,z) = w'x + xy + wz
f) G(X,Y,Z) = ((XYZ + X'Z' + Y'Z)( XY + X'Z'))'

CSF 10 BT / FIS 11 BT #.36

Downloaded by Frank Cruz ([email protected])

 lOMoARcPSD|21122727

REVISION QUESTIONS FOR STUDENTS:

PLACE VALUES:
Decimal
Power
,
Place
Value ,
,
X10 ,
Binary
Power
,
Place
Value ,
,
X2 ,
Octal Hexadecimal
Power
,
Place
Value ,
,
X8 , X16
Binary
Power
,
Place
Value ,
,
X2 ,
,

CSF 10 BT / FIS 11 BT #.37

Downloaded by Frank Cruz ([email protected])

 lOMoARcPSD|21122727

Number Systems
Binary and Binary Conversion
bit:

NUMBER SYSTEMS
Number Base Number of Symbols used to represent numbers
Symbols
System

Convert from Binary to Decimal

101112=

Must
include the
1101112= base

100111,012 = Must use

this
method

1100,0112 =
TEST
YOUR
ANSWER
10111,1012 =

Convert from Decimal to Binary

9010 17110

0,2510 0,62510

CSF 10 BT / FIS 11 BT #.38

Downloaded by Frank Cruz ([email protected])

 lOMoARcPSD|21122727

20,50 191,875
2010 19110

0,5010 0,87510

Hexadecimal and Hexadecimal Conversions

Decimal Hexadecimal 163 162 161 160 16-1

Convert from Hexadecimal to Decimal

2A816 =

1FF16 =

29816 =

28510 48910

CSF 10 BT / FIS 11 BT #.39

Downloaded by Frank Cruz ([email protected])

 lOMoARcPSD|21122727

Convert from Binary to Hexadecimal and Hexadecimal to Binary

Decimal Binary Hexadecimal

11100010102 =
Zero’s in
front of
number
101011002 =
has no
meaning
but is not
2BF16 =
wrong

A8216 =

Sign-and-Size-Code
Positive Number: Extra bit
Negative Number: Extra bit
35 =

-162 =

84 =

11101111 =

00011101 =

00001101 =

Two’s Compliment
BINARY ADDITIONS
0 0 1 1
+ 0 + 1 + 1 1
+ 1

CSF 10 BT / FIS 11 BT #.40

Downloaded by Frank Cruz ([email protected])

 lOMoARcPSD|21122727

CONVERT FROM DECIMAL TO TWO’S COMPLIMENT

+ :

Give the Two’s Compliment Representations of the following:

1510 =

8710 =

12310 =

- Follow the following 3 steps:




Give the Two’s Compliment Representation of the following:
- 7110 =

- 2010 =

- 5210 =

CONVERT FROM TWO’S COMPLIMENT TO DECIMAL

Determine the decimal value of the following two’s compliment representation:
+

0 0100 1102

0 1001 1112

- Follow the following 3 steps:




1 0110 1112

1 1111 1102

0 1101 0012

CSF 10 BT / FIS 11 BT #.41

Downloaded by Frank Cruz ([email protected])

 lOMoARcPSD|21122727

TWO’S COMPLIMENT ARITHMETIC

5410 - 1310

3410 - 3516

-2410 - 418

308 - 4116 - 1210

-210 + 358 - 6116

Truth Tables:
Truth Tables
Value In Algebra Physical representation

Operators:
Operator Notation Meaning Physical representation

Order of precedence:

1. _______________________________________

2. _______________________________________

3. _______________________________________

4. _______________________________________

Evaluate Boolean Function F(A,B) = A.B for all possible combinations of values that the variables can have.
A and B can have 22 = 4 different combinations:

Evaluate Boolean Function F(A,B) = A + B for all possible combinations of values that the variables can have.
A and B can have 22 = 4 different combinations:

CSF 10 BT / FIS 11 BT #.42

Downloaded by Frank Cruz ([email protected])

 lOMoARcPSD|21122727

Evaluate Boolean Function F(A,B) = A ‘ B for all possible combinations of values that the variables can have.
A and B can have 22 = 4 different combinations:

Evaluate Boolean Function F(x, y)) = xy + x’ + y for all possible combinations of values that the variables can have.

Evaluate Boolean Function F( x , y ) = x + x’y’ + xy for all possible combinations of values that
the variables can have.

Evaluate Boolean Function F( x , y , z ) = x’y + yz’ + x + z for all possible combinations of values
that the variables can have.

Evaluate Boolean Function F( a , b , c ) = (a’c + bc)abc + a’b’ for all possible combinations of
values that the variables can have.

Evaluate: F ( x , y , z ) = G ( x , y , z ) where
F ( x , y , z ) = x’y’z + xyz’ and G ( x , y , z ) = ( x + y )’z + xy’

Evaluate: F ( a , b , c ) = G ( a , b , c ) where
F ( x , y , z ) = (ab + b’c) + a’c’ and G ( x , y , z ) = ( a + b )’c + ab’

CSF 10 BT / FIS 11 BT #.43

Downloaded by Frank Cruz ([email protected])

 lOMoARcPSD|21122727

Evaluate: F ( x , y , z ) = G ( x , y , z ) where
F ( x , y , z ) = x’y’z + xyz’ and G ( x , y , z ) = ( xz’ + y )z’ + xy’z

Revision

Adding Binary

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

Sign-and-Size
Questions usually say to convert a number to sign-and-size and represent it in 1 byte (8 bits)

Question
Convert the following decimal numbers to Sign and Size and represent your answer in 1Byte:
6310

Two’s Compliment (Decimal to Two’s Compliment)

Positive: Sign-and-Size of number
Question
Give the Two’s compliment representation of 10010

Negative: Follow the 3 steps

Question
Give the Two’s compliment representation of -8210
 Change positive to binary

 Change all 1’s to 0’s and 0’s to 1’s

 Add 1

Two’s Compliment (Two’s Compliment to Decimal)

CSF 10 BT / FIS 11 BT #.44

Downloaded by Frank Cruz ([email protected])

 lOMoARcPSD|21122727

Positive: Sign-and-Size of number

Question
Work out the decimal of the following Two’s compliment representation:
K2(0 0111 011)

Negative: Follow the 3 steps

Question
Work out the decimal of the following Two’s compliment representation:
K2(1 1001 001)
 Change 1’s to 0’s and 0’s to 1’s

 Add 1

 Work out the decimal

Two’s Compliment Arithmetic

Addition is the compliment of subtraction

1. Give binary representation of the positive numbers

2. Rewrite subtraction as “addition of compliment”
3. Do addition
4. Ignore more than 8 bits
5. Write answer as decimal

6010 - 3010

-2810 - 5210

1210 – 3010 – 6A16

CSF 10 BT / FIS 11 BT #.45

Downloaded by Frank Cruz ([email protected])