CHAPTER ONE

INTRODUCTION
1.1 COMPUTER MEMORY OVERVIEW
The computer memory is one of the most important elements in a computer system. It stores data
and instructions required during the processing of data and output results. Storage may be required
for a limited period of time, instantly or for an extended period of time.

Computer memory refers to the electronic holding place for instructions and data where the
processor can read quickly.
Memory Hierarchy
The memory is characterized on the basis of two key factors; capacity and access time. The lesser
the access time, the faster is the speed of memory.
The computer uses a hierarchy of memory that is organized in a manner to enable the fastest speed
and largest capacity of memory as shown in figure.

Types of Memory:
In general, the memory is classified into two categories.
(i) Primary memory or Main memory.
(ii) Secondary memory or Auxiliary memory.
Parameters of Memory:
The following terms are most commonly used for identifying comparative behaviour of various
memory devices and technologies.
(i) Storage Capacity It is representative of the size of the memory. The capacity of internal
memory and main memory can be expressed in terms of number of words or bytes.
(ii) Access Modes A memory is comprised of various memory locations the information from
these memory locations can be accessed randomly. sequentially and directly.
(iii) Access Time The access time is the time required between the desired modes for a read or
write operation till the data is made available or written at the desired location.
(iv) Physical Characteristics In this respect. the devices can be categorized into four main
categories electronic, magnetic, mechanical and optical.
Permanence of Storage Its permanence is high for future use in magnetic materials.

1.2 DECIMAL NUMBER SYSTEM

The decimal number system is also known as base 10. The values of the positions are
calculated by taking 10 to some power.
Why is the base 10 for decimal numbers?
Because we use 10 digits, the digits 0 through 9. Ie 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
The decimal number system is a positional number system with a base 10.

5000 600 20 3

5 x 103 6 x102 2 x 101 3 x 100

Example: 5623
5623000 + 600 + 20 + 3 = 5 x 103 + 6 x102 + 2 x 101 + 3 x 100
1.3 BITS, BYTES, AND WORDS
• A bit is a single binary digit (a 1 or 0).
• A byte is 8 bits
• A word is 32 bits or 4 bytes Long word = 8 bytes = 64 bits
• Quad word = 16 bytes = 128 bits
Programming languages use these standard number of bits when organizing data storage and
access.
1.4 MEMORY MEASUREMENT
When you use a RAM, ROM. Floppy disk or hard disk. the data is measured using some unit. In
computer terminology. They are called nibble. Bit, Byte, Kilobyte, Megabyte, Gigabyte, etc.
Bit It stands for a Binary Digit. Which is either 0 or 1.
Byte (B) A byte is approximately one character (letter ’a’. number ‘1’. Symbol’?’. etc…). Also.
a group of 8 bits is called a byte.
Nibble 4 bits make one nibble.
Kilobyte (KB) In memory. a group of 1024 bytes is called a Kilobyte.
Megabyte (MB) In memory. a group of 1024 Kilobytes is called a Megabyte. It is sometimes
used. less precisely, to mean 1 million bytes or 1000 KB.
Gigabyte (GB) In memory, a group of 1024 megabytes is called a Gigabyte. It is sometimes
used, less precisely, to mean 1 billion bytes or 1000 MB. Now, a number of companies
manufacture memory chips in terms of Megabyte such as 64 MB, 128 MB, 256 MB, 1.2 GB etc.
Terabyte (TB) A terabyte, exactly 2 bytes (2 GB).is approximately a trillion (10) bytes.
Petabyte (PB) one petabyte of information equal to 1000 terabytes or 10 bytes.
Exabyte (EB) One Exabyte of information equal to 1000 petabytes or 10 bytes.
Zettabyte (ZB) One zettabyte of information equal to 1000 exabytes or 10 bytes.
Units of computer memory measurements.
1Bit = Binary Digit
8 Bits = 1 Byte = 2 Nibble
1024 Bytes = 1 KB (Kilobyte)
1024 KB = 1 MB (Megabyte)
1024 MB = 1 GB (Giga Byte)
1024 GB = 1 TB (Terabyte)
1024 TB = 1 PB (Petabyte)
1024 PB = 1 EB (Exabyte)
1024 EB = 1 ZB (Zettabyte)
1024 ZB = 1 YB (Yottabyte)
1024 YB = 1 ( Brontobyte)
1024 Brontobyte = 1 (Geop Byte) , Bit is the smallest memory measurement unit.
Geop Byte is the highest memory measurement unit.
 CHAPTER TWO
BINARY, OCTAL AND HEXADECIMAL NUMBERS
2.1 THE BINARY NUMBERS SYSTEM
The binary number system is also known as base 2. The values of the positions are
calculated by taking 2 to some power.
Why is the base 2 for binary numbers?
Because we use 2 digits, the digits 0 and 1.
Thus, the binary system of numbers has a radix of 2 and uses
only the digits 0 and 1.
Decimal vs Binary

Here are some equivalent values:

Decimal: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Binary: 0 1 10 11 100 101 110 111 1000 1001 1010 1011 1100 1101 1110 1111

2.1.1 Conversion of binary to decimal number system

The decimal number 234.5 is equal to 2x102 + 3x101 + 4x100 + 5x10−1 ie the sum of terms
comprising (a digit) multiplied by the base raised to some power
The base are important terms to consider when converting number system such binary, octal
and hexadecimal
In the binary system of numbers, the base is 2, so 1101.1
is equivalent to:1x23 + 1x22 + 0x21 + 1x22 + 1x2−1
1
Thus, the decimal number equivalent to the binary number 1101.1 is 8 + 4 + 0 + 2 + 2 that is
13.5 i.e. 𝟏𝟏𝟎𝟏. 𝟏𝟐 = 𝟏𝟑. 𝟓𝟏𝟎 , the suffixes 2 and 10 denoting binary and decimal systems of
numbers respectively.

Note
When converting binary into decimal we start counting from right to left ( 0,1,2 … and if the
binary has decimal number we start counting just after decimal places from left to the right but
with negative ie -1, -2,….)
Problem 1. Convert 110112 to a decimal number.
Solution
From above 110112 = 1x24 + 1x23 + 0x22 + 1x21 + 1x20

Then, 110112 = 16 + 8 + 0 + 2 + 1
Thus 110112 = 𝟐𝟕𝟏𝟎 ,

Problem 2. Convert 0.10112 to a decimal fraction.

Solution
0.10112 = 1x2−1 + 0x2−2 + 1x2−3 + 1x2−4
1 1 1 1
= 1x + 0x + 1x + 1x
21 22 23 24
1 1 1 1
= 1x + 0x + 1x + 1x
2 4 8 16
1 1 1
= +0+ +
2 8 16
1+8+2 11
= 16 = 16 = 0.6875
Thus , 0.10112 = 0.687510

Problem 3. Convert 101.0101 2 to a decimal number.

Solution
101.01012 = 1x22 + 0x21 + 1x20 + 0x2−1 + 1x2−2 + 0x2−3 + 1x2−4
1 1 1 1
= 4 + 0 + 1 + 0x 1 + 1x 2 + 0x 3 + 1x 4
2 2 2 2
1 1 1 1
= 4 + 0 + 1 + 0x 2 + 1x 4 + 0x 8 + 1x 16
1 1
= 4+0+1+0+ +0+
4 16
4+1 5
= 5 + 16 = 16 = 5.3125
Thus , 101.10112 = 5.312510

Practice Exercise 1 Conversion of binary to decimal numbers

In Problems 1 to 5, convert the binary numbers given to decimal numbers.

1. (a) 110 (b) 1011 (c) 1110 (d) 1001

2. (a) 10101 (b) 11001 (c) 101101 (d) 110011

3. (a) 101010 (b) 111000 (c) 1000001 (d) 10111000

4. (a) 0.1101 (b) 0.11001 (c) 0.00111 (d) 0.01011

5. (a) 11010.11 (b) 10111.011 (c) 110101.0111 (d) 11010101.10111

2.1.2 Conversion of decimal number to binary system
An integer decimal number can be converted to a corresponding binary number by repeatedly
dividing by 2 and noting the remainder at each stage
Example: Convert 𝟑𝟗𝟏𝟎 to binary number.

Remainder
2 39
2 19 1
2 9 1
2 4 1
2 2 0
2 1 0
0 1

The result is obtained by writing the top digit of the remainder as the least significant bit (a bit is
a binary digit and the least significant bit is the one on the right). The bottom bit of the
remainder is the most significant bit, i.e. the bit on the left. Thus 3910 = 𝟏𝟎𝟎𝟏𝟏𝟏2

The fractional part of a decimal number can be converted to a binary number by repeatedly
multiplying by 2, as

Problem 2 Convert 0.4062510 into binary number

Solution
Given 0.4062510
Then Answer Carry
0.40625x2 = 0.8125 0
0.8125x2 = 1.6250 1
0.6250x2 = 1.2500 1
0.2500x2 = 0.5000 0
0.5000x2 = 1.0000 1

Then from top to bottom It will be 0.4062510 = 0.011012

Problem 3 Convert 58.3125 10 to a binary number.

Solution
58.3125 10 given then converting binary number.

Here we have two cases

 Case 1 58 10

Remainder
2 58
2 29 0
2 14 1
2 7 0
2 3 1
2 1 1
0 1

Thu, 58 10 = 1110102
Case 2
Then for 0.312510 Given
Then converting into binary
0.3125𝑥2 = 0.625 0
0.625𝑥2 = 1.25 1
0.25𝑥2 = 0.5 0
0.5𝑥2 = 1.0 1
Thus 0.312510 = 0.01012

Then the binary of 58.3125 10 = 111010.01012

Practice Exercise 3 Conversion of decimal to binary numbers

In Problems 1 to 5, convert the decimal numbers given to binary numbers.

1. (a) 5 (b) 15 (c) 19 (d) 29

2. (a) 31 (b) 42 (c) 57 (d) 63

3. (a) 47 (b) 60 (c) 73 (d) 84

4. (a) 0.25 (b) 0.21875 (c) 0.28125 (d) 0.59375

5. (a) 47.40625 (b) 30.8125 (c) 53.90625(d) 61.65625

OPERATION OF BINARY NAUMBER SYSTEM

(a) Addition of Binary number

Binary addition of two/ three bits is achieved according to the following rules

(i) Binary addition of two bits

Sum carry
0+0=0 0
0+1=1 0
1+0=1 0
1+1=0 1
(ii) Binary addition of three bits
Sum carry
0+0+0= 0 0
0+0+1= 1 0
0+1+0= 1 0
1+0+0= 1 0
0+1+1= 0 1
1+0+1= 0 1
1+1+0= 0 1
1+1+1= 1 1

Problem 1 perform the following binary operation

𝟏𝟏𝟏𝟏𝟏
+ 𝟏𝟎𝟏𝟎𝟏
(a) 11111 + 10101 = 𝐒𝐮𝐦 𝟏𝟏𝟎𝟏𝟎𝟎
𝐂𝐚𝐫𝐫𝐲 𝟏𝟏𝟏𝟏𝟏

1101001
+ 1110101
(b) 1101001 + 1110101 = 𝐒𝐮𝐦 𝟏1011110
𝐂𝐚𝐫𝐫𝐲 11 1

𝟏𝟎𝟏𝟏𝟏𝟎𝟏
𝟏𝟏𝟎𝟎𝟎𝟎𝟏
+𝟏𝟏𝟎𝟏𝟎𝟏
(c) 1011101 + 1100001 + 110101 = 𝐒𝐮𝐦 𝟏𝟏𝟏𝟏𝟎𝟎𝟏𝟏
𝐂𝐚𝐫𝐫𝐲 𝟏𝟏𝟏𝟏𝟏 𝟏
 (b) Subtractions of Binary number

Binary subtraction is also similar to that of decimal subtraction with the difference that when 1
is subtracted from 0, it is necessary to borrow 1 from the next higher order bit and that bit is
reduced by 1 (or 1 is added to the next bit of subtrahend) and the remainder is 1.

(i) Binary subtraction of two bits

Sum carry
0−0=0 0
0−1=1 0
1−0=1 0
1−1=0 0
(ii) Binary subtraction of three bits
Sum carry
0−0−0= 0 0
0−0−1= 1 0
0−1−0= 1 0
1−0−0= 1 0
0−1−1= 0 0
1−0−1= 0 0
1−1−0= 0 0
1−1−1= 1 0
 Problem 1

Perform the following binary number

11
(a) 11 − 10 = −10 =1
01

110
−10
(b) 110 − 10 = = 100
100

1111
−110
(c) 1111 − 110 = = 1001
1001

100
−10
(d) 100 − 10 = = 10
010

1000
−11
(e) 1000 − 11 = = 101
0101

1000
−111
(f) 1000 − 111 = =1
0 001

1000
− 1
(g) 1000 − 1 = = 111
0 111

Note

When you borrow 1 bit it will be equivalent to 2 bits so that when you have

100 − 1 = 011 = 11 and 100 − 11 = 001 = 1

Practice Exercise 3 Binary addition and subtraction

Perform the following binary additions:

1. 10 + 11 2. 101 + 110 3. 1101 + 111
4. 1111 + 11101 5. 110111 + 10001 6. 10000101 + 10000101
7. 11101100 + 111001011 8. 110011010+ 11100011 9. 10110 + 1011 + 11011 10. 111 +
10101 + 11011
11. 1101 + 1001 + 11101 12. 100011 + 11101 + 101110

Perform the following binary additions

1.1111 − 110 2. 1000 − 11 3. 1111 − 111 4. 110101 − 1010 5. 11011 − 111

(c) Multiplication of Binary number

For binary multiplication, we follow the same process as multiplying two decimal numbers where
we multiply each digit of the second number by the first whole number, then we just need to add
them, switching each resulting multiplication one digit to the left.

1x1 = 1 and 1x0 = 0 also 0x0 = 0

Problem

Find the value of each of the following binary multiplication

1011
x101
(a) 1011x 101 = 1011
0000
+1011
110111

11101
x1111
(b) 1111 x 11101 = 11101
11101
11101
+11101
110110011

Thus 1111 x 11101 = 110110011

Practice Exercise 4 Binary multiplication

Perform the following binary multiplication:
1. 10 x 11 2. 101 x 110 3. 1101 x 111 4. 1111 x 11101 5. 110111 x 10001
1) switch on calc (hehe) 2) at the left of the ON button theres a botton called MODE/CLR press it 2 times

3) when u press mode 2 times u will see options like 1sd 2reg 3base 4) at this menu press 3base

5) when u select base calc will show the main screen of 0 if u select the base opttion u will see a 'd'

written at the rightof 0 6) so when its done u can start ---- so ##enter the no which u want to convert int

binary eg 4. ##press '=' ## then look for the button log (ie logarithm) which is also for binary BIN press

it ## thats all u will see the bin no (eg if u tried for 4 u will see ans as - 100) and u can also convert no

from bin to decimal # press log (bin) see the 'b' right of 0 # then type ur binary no press = # then press

x^2

(d) Division of binary number

Step 1: First, look at the first two numbers in the dividend and compare with the divisor. Add
the number 1 in the quotient place. Then subtract the value, you get 1 as remainder.
Step 3: Repeat the process until the remainder becomes zero by comparing the dividend and the
divisor value.
Problem 1
Perform the following binary division
1101
(a) 100111 ÷ 11 = 11 100111
−011
11
− 11
11
−11

11.11
(b) 1111 ÷ 100 = 100 1111
−111
111
− 100
110
−100
100
−100

Practice exercise 4 division of binary

(a) 1000 ÷ 111
(b) 1010 ÷ 11
(c) 11101 ÷ 110
2.2 Octal Number system
For decimal integers containing several digits, repeatedly dividing by 2 can be a lengthy process.
In this case, it is usually easier to convert a decimal number to a binary number via the octal
system of numbers. This system has a radix of 8, using the digits 0, 1, 2, 3, 4, 5, 6 and 7.

Example: convert 43178 to a decimal number

Such that 43178 = 4x83 + 3x82 + 1x81 + 1x80

= 4x512 + 3x64 + 1x8 + 1
= 2048 + 192 + 8 + 1
= 224910
Thus 43178 = 224910

An integer decimal number can be converted to a corresponding octal number by repeatedly

dividing by 8 and noting the remainder at each stage, as shown below;

Problem 1
Convert 49310 into octal number
Solution

493 10

Remainder
8 493
8 61 5
8 7 5
0 7

Then the octal number of 493 10 = 7558

The fractional part of a decimal number can be converted to an octal number by repeatedly
multiplying by 8, as
shown below for the fraction

Problem 1 convert 0.437510 to octal number

Solution

Then for 0.437510 Given

Then converting into binary
0.4375𝑥8 = 3.5 3
0.5𝑥8 = 4.0 4
 Thus 0.437510 = 0.348
Then the octal number of 0.437510 = 0.348

For fractions, the most significant bit is the top integer obtained by multiplication of the decimal
fraction by 8, thus, 0.437510 = 0.348

The natural binary code for digits 0 to 7 is shown in Table 1 below, and an octal number can be
converted to a binary number by writing down the three bits corresponding to the octal digit.

Table 1 include the numbers from 10 through 16.

binary Octal decimal

000 0 0
001 1 1
010 2 2
011 3 3
100 4 4
101 5 5
110 6 6
111 7 7
1000 10 8
1001 11 9
1010 12 10
1011 13 11
1100 14 12
1101 15 13
1110 16 14
1111 17 15
10000 20 16

Conversion of decimal number into binary via octal number

Problem 1 convert 5613.9062510 into binary via octal number

Solution
5613.9062510 given then converting into octal
Here we have two cases
Case 1
 Remainder
8 5613
8 701 5
8 87 5
8 10 7
8 1 2
0 1

Thu, 561310 = 127558

Case 2 Then for 0.9062510 Given

Then converting into octal
0.90625𝑥8 = 7.2500 7
0.2500𝑥8 = 2.0000 2
0.9062510 = 0.728
Thus 5613.9062510 = 12755.728

Then the binary of be 5613.9062510 = 12755.728 = 1010111101.111012

Problem 2 Convert 126510 to binary number, via octal

Solution
126510 to binary number, via octal

Here we have two cases

Case 1
Remainder
8 1265
8 158 1
8 19 6
8 2 3
0 2

126510 = 23618

Case 2 converting 23618 into binary

23618 = 0100111100012
 Problem 2 Convert 5613.9062510 into binary via octal
Solution
5613.9062510 given then converting into oct
Here we have two cases
Case 1

Remainder
8 5613
8 701 5
8 87 5
8 10 7
8 1 2
0 1
Thu, 561310 = 127558
Case 2
Then for 0.9062510 Given
Then converting into octal
0.90625𝑥8 = 7.2500 7
0.2500𝑥8 = 2.0000 2
0.9062510 = 0.728

Thus 5613.9062510 = 12755.728

Then the binary of be 5613.9062510 = 12755.728 = 1010111101.111012

Converting binary number to Decimal number via octal number

When converting binary to octal, Group the binary number in three’s from the binary point and
write down their corresponding binary number using Table 1

Problem 1 Convert 11110011.100012 to decimal number via octal

Solution
Grouping the binary number into three bits
011 110 011 . 100 010 2 = 363.42
= 363.428 octal number
363.428 = 3 × 82 + 6 × 81 + 3 × 80 + 4 × 8−1 + 2 × 8−2
1 1
= 3 × 64 + 6 × 8 + 3 × 1 + 4 × 8 + 2 × 64
4 2
= 192 + 48 + 3 + 8 + 64
 2+32
= 192 + 48 + 3 +
64
34
= 243 + 64

Thus, 11110011.100012 = 243.5312510

Problem 2 Convert 111.01112 to decimal number via octal

Solution
111
⏟ . 011
⏟ 100
⏟ = 7.348
7 3 4 2
= 7.348 = 7x8 + 3x8−1 + 4x8−2
1 1
= 56 + 3x + 4x
8 64
= 56.437510
Thus , 111.01112 = 56.437510
Note that if the grouping of bits does not fit the three, we add zeros before and binary fraction
add the zeros after fraction binary

Problem 3 Convert 11 110 011.100 01 2 to a decimal number via octal.

Solution
Grouping the into 3 bits from the right to the left 011
⏟ 110
⏟ 011
⏟ . 100
⏟⏟ 010 2 = 363.428
3 6 3 4 2
Then convert 363.428 into decimal ie
363.428 = 3x82 + 6x81 + 3x80 + 4x8−1 + 2x8−2
1 1
= 3x64 + 6x8 + 3x1 + 4x + 2x
8 64
= 192 + 48 + 3 + 0.5 + 0.03125
= 243.5312510

Practice Exercise 6 Conversion between decimal and binary numbers via octal
In Problems 1 to 3, convert the decimal numbers given to binary numbers, via octal.
1. (a) 343 (b) 572 (c) 1265
2. (a) 0.46875 (b) 0.6875 (c) 0.71875
3. (a) 247.09375 (b) 514.4375 (c) 1716.78125
4. Convert the binary numbers given to decimal numbers via octal.
(a) 111.011 1 (b) 101 001.01 (c) 1 110 011 011 010.001 1
10.4 Hexadecimal numbers
2.1.3 Hexadecimal system
The hexadecimal system is particularly important in computer programming, since four bits (each
consisting of a one or zero) can be succinctly expressed using a single hexadecimal digit. Two
hexadecimal digits represent numbers from 0 to 255, a common range used, for example, to specify
colours. Thus, in the HTML language of the web, colours are specified using three pairs of
hexadecimal digits RRGGBB, where RR is the amount of red, GG the amount of green, and BB
the amount of blue.
A hexadecimal numbering system has a radix of 16 and uses the following 16 distinct digits: 0,
1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E and F ‘A’ corresponds to 10 in the decimal system, B to 11,
C to 12, and so on.

The table 2 Shows hexadecimal numbers.

binary octal decimal hexadecimal
000 0 0 0
001 1 1 1
010 2 2 2
011 3 3 3
100 4 4 4
101 5 5 5
110 6 6 6
111 7 7 7
1000 10 8 8
1001 11 9 9
1010 12 10 A
1011 13 11 B
1100 14 12 C
1101 15 13 D
1110 16 14 E
1111 17 15 F
10000 20 16 10
10001 21 17 11
10010 22 18 12
10011 23 19 13
10100 24 20 14
10101 25 21 15
 10110 26 22 16
10111 27 23 17
11000 30 24 18
11001 31 25 19
11010 32 26 1A
11011 33 27 1B
11100 34 28 1C
11101 35 29 1D
11110 36 30 1E
11111 37 31 1F
100000 40 32 20

(a) Converting from hexadecimal to decimal

Problem 1
Convert the following hexadecimal numbers into their decimal equivalents:
(i) 1A16
Solution
1A16 = 1x161 + A × 160
= 1x16 + 10 × 1
= 16 + 10
Thus, 1A16 = 2610
(ii) 1E16
Solution
1E16 = 1x161 + E × 160
= 1x16 + 14 × 1
= 16 + 14
Thus, 1E16 = 3010
(iii)7A16
Solution
1A16 = 7x161 + A × 160
= 7x16 + 10 × 1
= 112 + 10
Thus, 7A16 = 12210
(iv) 3F16
Solution
1F16 = 1x161 + F × 160
= 1x16 + 15 × 1
= 16 + 15
Thus, 1F16 = 3110
 (v) 1𝐴4𝐸16
Solution
1𝐴4𝐸16 = 1x163 + Ax162 + 4x161 + Ex160
= 1x163 + 10x162 + 4x161 + 14x160
= 4096 + 2560 + 64 + 14 = 6734

Thus 1A4E16 = 673410

(vi) C916
Solution
C916 = Cx161 + 9 × 160
= 12x16 + 9 × 1
= 192 + 9
Thus, C916 = 20110

(vii) BD16
Solution
BD16 = Bx161 + D × 160
= 11x16 + 13 × 1
= 176 + 13
Thus, BD16 = 18910
(b) Converting from decimal to hexadecimal

This is achieved by repeatedly dividing by 16 and noting the remainder at each stage, WHILE

Considering A = 10, B = 11, C = 12, D = 13, E = 14, F = 15

Problem 1 Convert the following decimal numbers into their hexadecimal equivalents:

(a) 2610

2610 to hexadecimal
Here we have
Remainder
16 26
16 1 10 =A
0 1
2610 = 1A16

(b) 44710
 44710 to Hexadecimal
Here we have

Remainder
16 447
16 27 15 =F
16 1 11 = B
0 1

44710 = 1BF16

Thus 44710 = 1BF16

(c) 10810

10810 to Hexadecimal
Here we have

Remainder
16 108
16 6 12 =C
0 6

10810 = 6C16

Thus 10810 = 6C16

Practice Exercise 7 Hexadecimal numbers

In Problems 1 to 4, convert the given hexadecimal numbers into their decimal equivalents.

1. E716 2. 2C16

3. 9816 4. 2F116

In Problems 5 to 10, convert the given decimal numbers into their hexadecimal equivalents.

5. 5410 6. 20010 7. 9110 8. 23810 9. 16210 10. 23910

(c) Converting from binary to hexadecimal

The binary bits are arranged in groups of four, starting from right to left, and a hexadecimal
symbol is assigned to each group.
Problem 1 Convert the following binary numbers into their hexadecimal equivalents:
(a) 110101102 (b) 11001112 (c) 11100111101010012 (d) 110011112 (b) 1100111102
Solution
Grouping into 4 bits and assign the hexadecimal from table 4
(a) 110101102 = 1101 ⏟ ⏟
0110 = D616 From table 2 above
D 6

(b) 11001112 = 0110

⏟ ⏟
0111 = 6716
6 7
(c) 11100111101010012 = 1110
⏟ ⏟
0111 ⏟
1010 ⏟
1001 = E7A916
E 7 A 9
(d) 110011112 = 1100
⏟ ⏟
1111 = CF16
𝐶 𝐹

(d) Converting from hexadecimal to binary

The above procedure is reversed;

Problem Convert the following hexadecimal numbers into their binary equivalents:
(i) 3F16 = 0011 11112

(ii) A616 = 1010 01102

(iii) 6CF316 = 𝟎𝟏𝟏𝟎 𝟏𝟏𝟎𝟎 𝟏𝟏𝟏𝟏 𝟎𝟎𝟏𝟏𝟐

Practice Exercise 7 Hexadecimal numbers

In Problems 1 to 4, convert the given binary numbers into their hexadecimal equivalents.

1. 110101112 2. 111010102 3. 100010112 4. 101001012

In Problems 5 to 8, convert the given hexadecimal numbers into their binary equivalents.

5. 3716 6. ED16 7. 9F16 8. A2116

OPERATION OF HEXADECIMAL

How to do hexadecimal addition and subtraction?

Here we will discuss about solving hexadecimal addition and subtraction.

(a) Addition and subtraction of hexadecimal

(i) Hexadecimal Addition:
 The table for hexadecimal addition is as follows:

Addition of hexadecimal numbers can be easily carried with the help of the above table.

Following example illustrates the use of the table.

Problem evaluate: (B A 3)16 + (5 D E)16

Solution:

We note from the table that

3 + E = 11 1 1 carry

A + D = 17 BA3
17 + 1 (carry) = 18 5DE
B + 5 = 10
1181
10 + 1 (carry) = 11

Hence the required sum is 1181 in hexadecimal.

(ii) Hexadecimal Subtraction:

Subtraction of hexadecimal numbers can be accomplished by using complement method. Although

it is not a very simple method computers use it very efficiently. These above explanations will help
you to understand the concept about hexadecimal addition and subtraction.
 CHAPTER THREE

SETS AND PROBABILITY

3.1 SETS

3.1.1 Definition
is a group/ collection of things such as a herd of cattle, a pile of books, a collection of trees, a
shampoos bee and a fleck of sheep
OR A set is an unordered collection of different elements. A set can be written explicitly by
listing its elements using set bracket. If the order of the elements is changed or any element of a
set is repeated, it does not make any changes in the set
Some Example of Sets

• A set of all positive integers

• A set of all the planets in the solar system
• A set of all the students taking DIT at CBE
• A set of all the lowercase letters of the alphabet
• A set of all cities in Tanzania
3.1.2 Description of sets
-A set is described/denoted by Carl brackets { } and named by Capital letters

Examples

If A is a set of books in the library then A is written as

A= {All books in the library} and read as A is a set of all books written in the library
-The things/objects in the set are called Elements or members of the set

Example
1. If John is a student of class B, then John is a member of class B and shortly denoted as
∈B.
2. If A= {1,2,3} then 1 ∈ A, 2 ∈ A and 3 ∈ A 1}
The number of elements in a set is denoted by n(A)
Example
If A= {a, e, i, o, u} then n (A) =5
Example
1. If A is a set of even, describe this set by
a) Words
b) Listing
c) Formula

Solution:
1. (a) By words;
A = {even numbers}
(b) By Listing
A = {2, 4, 6, 8…}
(c) By Formular
A = {x: x= 2n} where n = {1, 2, 3…} and is read as A is a set of all element x such that x
is an even number.
2. Describe the following sets by Listing; A= {whole numbers between 1 and 8}
Solution:
A= {2, 3, 4, 5, 6, 7}
3. Write the following sets in words; A= {an integer < 10}
Solution:
A= {integers less than ten} or A is a set of integers less than ten
3.1.3 TYPES OF SETS
Finite set; Is a set where all elements can be counted exhaustively.
Infinite set: An Infinite set is a set that all of its elements cannot be exhaustively counted
Example
B= {2, 4, 6, 8…}
An Empty set; Is a set with no elements. An Empty set is denoted by { } or Ø
Example
If A is an Empty set then can be denoted as A= { } or A= Ø

Exercise 3.1
1. List the elements of the named sets
(i) A = {x: x is an odd number < 10}
(ii) B = {days of the week which began with letter S}
(iii)C = {Prime numbers less than 13}
2. Write the named sets in words
(i) B = {x: x is an odd number < 12}
B is a set of x such that x is an odd number less than twelve
(ii) E = {x: x is a student in your class}
E is a set of x such that x is a student in your class
3. Write the named sets using the formula methods
(i) A= {all men in Tanzania}
A= {x: x is all men in Tanzania}
(ii) B= {all teachers in your school}
B= {x: x is all teachers in your school}
(iii)C= {all regional capital in Tanzania}
C= {x: x is all regional capital in Tanzania}
(iv) D= {b, c, d, f, g…}
D= {x: x is a consonant}
3.1.4 COMPARISON OF SETS
Set may be equivalent, equal or one to be a subset of other.
Equivalent sets are setting whose members (numbers) match exactly.
Example 1
A= {2, 4, 6, 8} and B= {a, b, c, d} then show that A and B are equivalent
The two sets can be matched as

Generally, if n(A) = n(B) then A and B are equivalent sets

Example 2
If A= {1, 2, 3, 4} and B= {1, 2, 3, 4} since n(A) = n(B) and the elements are alike then set A is
equal to set B
3.1.5 SUBSET:
Given two sets A and B, B is said to be a subset of A. If all elements of B belong to A
Example
If A= {a, b, c, d, e} and B = {a, b, c, e}, Set B is a subset of A since all elements of set B belongs
to set A. But set B has less elements than set A. Then set B is a proper subset of set A

and A is a super set of B. Symbollically B ⊂ A . If A= B then either A is an improper subset of

B or B is an improper subset of A. Symbolically written as A⊆B or B⊆A
Note: an empty set is a subset of any set
The number of subsets in a set is found by the formula 2n where n = number of elements of a
set
Example
1. List all subset of A= {a, b}
Solution:

2n , n = number of elements in a set.

So, 22 = 4
The number of subsets = 4
The subset of A are { }, {a}, {b}, {a, b}

2. How many subsets are there in A= {1, 2, 3, 4}

Solution:
The number of subsets= 24= 16

3.1.6 UNIVERSAL SET (∪ or ξ)

 Is a single set which contains all elements sets under consideration for example the set of integers
contains all the elements of sets such as odd numbers, even numbers, counting numbers, and whole
numbers. In this case the set of integers is the Universal set.
Exercise 3.2
1. Which of the following sets are
(a) Finite set
(b) Infinite set
(c) Empty set
A= {Nairobi, Dar es Salaam}
B= {2, 4, 6…36}
E= {All mango trees in the world}
F= {x: x is all students aged 100 years in your school}
H= {1, 3, 5, 7}
D= {all lions in your school}
I= Ø

Solution:
(a) Finite set are
A= {Nairobi, Dar es Salaam}
B= {2, 4, 6…36}
H= {1, 3, 5, 7}

(b) Infinite set

E= {All mango trees in the world}
F= {x: x is all students aged 100 years in your school}
(c) Empty sets are
D= {all lions in your school}
I= Ø
2. In each of the following pairs of sets show by matching whether the pairs are equivalent or
not Equivalent are:
(a) A= {a, b, c, d} and B= {b, c, d, e}
(b) B= {Rufiji, Ruaha, Malagarasi} and C= {lion, leopard}

3. Which of the following sets are equal?

A= {a, b, c, d}, B= {d, a, b, c}, C= {a, e, I, o, u}, D= {a, b, c, d}, E= {d, c, b, a}, F= {a, e, b, c,
d}
4. List all subsets of each of the following sets
 (a) A= {1}
(b) B= Ø
(c) C = {Tito, Juma}
5. Name the subsets of each pair by using the symbol ⊂
(a) A= {a, b, c, d, e, f, g, h} and B= {d, e, f}
(b) A= {2, 4} and D= {2, 4, 5}
(c) A= {1, 2, 3, 4 …} and B= {2, 4, 6, 8…}
6. Given G = {cities, towns and regions of Tanzania} which of the following sets are the
subsets of G?

A= {Nairobi, Dar es Salaam}

B= {Dodoma, Mombasa, Mwanza}
C= { }
D= {Arusha, Iringa, Bagamoyo}
E= {Mbeya, Tunduru, Ruvuma}

7. Which of the following sets are the subsets of K given that K= {p, q, r, s, t, u, v, w}
A= {p, s, t, x} B= {q, r, d, t} C= { } D= {p, q, r, s, t, u, v, w} E= {a, b, c, d}
F= {s, v, q}
8. What is n(A) if A= { }
9. Write in words the universal set of the following sets
(a) A= {a, b, c, d}
(b) B= {1, 2, 3, 4} Answer; The universal set of set B is the set of natural numbers

3.1.7 OPERATION WITH SETS

UNION

The union of two sets A and B is the one which is formed when the members of two sets are
putted together without a repetition. Thus, the union is ∪, this union of A and B can be denoted
as A∪B is defined as x; X∈A or X∈B

Example

1. If A= {2, 4, 6} and B= {2, 3, 5} then A∪B= {2, 4, 6} ∪ {2, 3, 5} = {2, 3, 4,5, 6}

2. Find A∪B when A= {a, b, c, d, e, f} and B= {a, e, i, o, u}
Solution: A∪B= {a, b, c, d, e, f, i, o, u}

INTERSECTION

The Intersection of two sets A and B is a new set formed by taking common elements. The
symbol for intersection is “∩”

Example

1. A= {1, 2, 3, 4, 5}, B= {1, 3, 5} then A∩B= {1,3,5}

2. Find A∩B if A= {a, e, i, o, u}, B= {a, b, c, d, e, f} then A∩B= {a, e}

3.1.8 COMPLEMENT OF A SET

If A is a subset of a universal set, then the members of the universal set which are not in A, form
compliment of A denoted by A΄ or Ac

Example

If ∪ = {a, b, c … z} and A= {a, b} then A΄= {c, d, e, … z}

Given that U= {15, 45, 135, 275} and A= {15} find A΄
Solution: 𝐴′ = {45, 135, 275}

3.1.9 JOINT AND DISJOINT SETS

JOINT SETS; Are sets with common elements

E.g. A= {1, 2, 3, 5}, D= {1, 2} then A and D are joint sets since {1, 2} are common elements

DIS JOINT SETS; Are sets with no elements in common

For example, A= {a, b, c} and B= {1, 2, 3, 4} then A and B are disjoint sets since they do not
have a common element

EXERCISE 3.3

1. Find
(a) Union
(b) Intersection of the named sets
(i) A= {5, 10, 15}, B= {15, 20}
(a) A∪B = {5, 10, 15, 20}
(b) A∩B = {15}
 (ii) A= { }, B= {14, 16}
(a) A∪B= { , 14, 16}
(b) A∩B= { }

(iii)A= {First five letters of the English alphabet}, B= {a, b, c, d, e}

(iv) A= {counting numbers}, B= {prime numbers}

(v) A = {o, }, B= { }

3.1.10 VENN DIAGRAM

A Venn diagram is a drawing in which geometric figures such as circles and rectangles are used
to represent sets. One use of Venn diagrams is to illustrate the effects of set operations.

Are the diagrams (ovals) devised by John Venn for representation of sets

Example1 If A= {a, b, c} can be represented as

µ is the universal set, in this case is the set of all English alphabets. If the set have any elements in
common, the ovals overlap for example, If A= {a, b, c} and B= {a, b, c, d} then it can be
represented as
Disjoint sets also can be represented on a Venn diagram

Example 2: If A= {a, b}, B= {1, 2} the relation A and B is as follows

Examples 3: If A is a subset of B, represent the two sets on a Venn diagram

Example 4: Represent A= {2, 3, 5}, B= {2, 5, 7} C= {2, 3, 7} in a Venn diagram

Solution:

Example5: Represent AUB in a Venn diagram given that A= {1, 2}, B= {1, 3, 5}

Solution:

Example6: If set A and B have same elements in common, represent the following in a Venn
diagram

(a) A∪B
(b) A∩B
Solution:
Example 7

In a certain primary school 50 pupils were selected to form three schools’ teams of football,
volleyball and basketball as follows

30 pupils formed a football team

20 pupils formed a volleyball team

25 pupils formed a basketball team

14 play both volleyball and basketball

18 pupils play football and basketball

8 pupils play all of the three games

7 pupils play football only

Represent this information in a Venn diagram

Solution:

Example 8 A and B are sets such that n(A∩B)=4 and n(A∪B)=6 if A has 4 elements
(a) How many elements are there in B?
(b) Which set is the subset of the other
 Solution:

(a) 6 elements are in B

(b) A⊂B

3.1.11 Basic Venn diagrams can illustrate the interaction of two or three sets.

Example 9
Create Venn diagrams to illustrate A ⋃ B, A ⋂ B, and Ac ⋂ B

A ⋃ B contains all elements in either set.

A B

A ⋂ B contains only those elements in both sets – A⋃B in

the overlap of the circles.
 A B

A⋂B

A B
Ac will contain all elements not in the set A. Ac ⋂ B
will contain the elements in set B that are not in set
A.

Ac ⋂ B

Example 10
Use a Venn diagram to illustrate (H ⋂ F)c ⋂ W

We’ll start by identifying everything in the set H ⋂ F

 H F

Now, (H ⋂ F)c ⋂ W will contain everything not in the set identified above that is also in set W.

H F

Example 11
Create an expression to represent the outlined part of the Venn diagram shown.

H F
The elements in the outlined set are in sets H and F,
but are not in set W. So we could represent this set as
H ⋂ F ⋂ Wc

Try it Now 3
Create an expression to represent the outlined portion of the Venn diagram shown

A B

Example 14
A survey asks 200 people “What beverage do you drink in the morning”, and offers choices:
• Tea only
• Coffee only
• Both coffee and tea

Suppose 20 report tea only, 80 report coffee only, 40 report both. How many people drink tea in
the morning? How many people drink neither tea or coffee?

This question can most easily be answered by

creating a Venn diagram. We can see that we can
find the people who drink tea by adding those who
drink only tea to those who drink both: 60 people. 80 40 20

We can also see that those who drink neither are

those not contained in the any of the three other
groupings, so we can count those by subtracting Coffee Tea
from the cardinality of the universal set, 200.
200 – 20 – 80 – 40 = 60 people who drink neither.

3.1.12 Cardinality
Often times we are interested in the number of items in a set or subset. This is called the cardinality of
the set.
 Cardinality
The number of elements in a set is the cardinality of that set.

The cardinality of the set A is often notated as |A| or n(A)

Example 12
Let A = {1, 2, 3, 4, 5, 6} and B = {2, 4, 6, 8}.
What is the cardinality of B? A ⋃ B, A ⋂ B?

The cardinality of B is 4, since there are 4 elements in the set.

The cardinality of A ⋃ B is 7, since A ⋃ B = {1, 2, 3, 4, 5, 6, 8}, which contains 7 elements.
The cardinality of A ⋂ B is 3, since A ⋂ B = {2, 4, 6}, which contains 3 elements.

Example 13
What is the cardinality of P = the set of English names for the months of the year?

The cardinality of this set is 12, since there are 12 months in the year.

Sometimes we may be interested in the cardinality of the union or intersection of sets, but not know the
actual elements of each set. This is common in surveying.

Example 15
A survey asks: Which online services have you used in the last month:
• Twitter
• Facebook
• Have used both
The results show 40% of those surveyed have used Twitter, 70% have used Facebook, and 20%
have used both. How many people have used neither Twitter or Facebook?

Let T be the set of all people who have used Twitter, and F be the set of all people who have
used Facebook. Notice that while the cardinality of F is 70% and the cardinality of T is 40%, the
cardinality of F ⋃ T is not simply 70% + 40%, since that would count those who use both
services twice. To find the cardinality of F ⋃ T, we can add the cardinality of F and the
cardinality of T, then subtract those in intersection that we’ve counted twice. In symbols,
n(F ⋃ T) = n(F) + n(T) – n(F ⋂ T)
n(F ⋃ T) = 70% + 40% – 20% = 90%

Now, to find how many people have not used either service, we’re looking for the cardinality of
(F ⋃ T)c . Since the universal set contains 100% of people and the cardinality of F ⋃ T = 90%,
the cardinality of (F ⋃ T)c must be the other 10%.

In general, the number of elements in two sets is connected by the formula

n(A∪B) = n(A) + n(B) – n(A∩B)

CARDINALITY OF SET

Cardinality properties
n(A ⋃ B) = n(A) + n(B) – n(A ⋂ B)

n(Ac) = n(U) – n(A)

n(Bc) = n(U) – n(B)
Notice that the first property can also be written in an equivalent form by solving for the
cardinality of the intersection:
n (A ⋂ B) = n(A) + n(B) – n(A ⋃ B)
it is sometimes denoted as |𝐴⋃ 𝐵| = |𝐴 | + | 𝐵| − |𝐴 ⋂ 𝐵|
such that
|𝐴⋃ 𝐵| = n (𝐴⋃ 𝐵)
|𝐴 | = n(𝐴)
| 𝐵| = n(𝐵)
|𝐴 ⋂ 𝐵| = n(𝐴 ⋂ 𝐵)
Example 16
Fifty students were surveyed, and asked if they were taking a social science (SS), humanities
(HM) or a natural science (NS) course the next quarter.
21 were taking a SS course 26 were taking a HM course
 19 were taking a NS course 9 were taking SS and HM
7 were taking SS and NS 10 were taking HM and NS
3 were taking all three 7 were taking none

How many students are only taking a SS course?

It might help to look at a Venn diagram. SS

From the given data, we know that there are HM
3 students in region e and a c
b
7 students in region h.
e
Since 7 students were taking a SS and NS course, we d f
know that n(d) + n(e) = 7. Since we know there are 3
students in region 3, there must be g
7 – 3 = 4 students in region d. h
NS
Similarly, since there are 10 students taking HM and
NS, which includes regions e and f, there must be
10 – 3 = 7 students in region f.

Since 9 students were taking SS and HM, there must be 9 – 3 = 6 students in region b.

Now, we know that 21 students were taking a SS course. This includes students from regions a,
b, d, and e. Since we know the number of students in all but region a, we can determine that 21
– 6 – 4 – 3 = 8 students are in region a.

Example 17
If n(G) = 20, n(H) = 30, n(G ⋂ H) = 5, find n(G ⋃ H)
Solution
n(G ⋃ H) = n(G) + n(H) − n(G ⋂ H)
= 20 + 30 − 5
= 45
n(G ⋃ H) = 45

Example 18
If n(G) = 5, n(H) = 8, n (G ⋂ H) = 4, find n(G ⋃ H)
Solution
 n(G ⋃ H) = n(G) + n(H) − n(G ⋂ H)
=5+8−4
=9
n(G ⋃ H) = 9
EXERCISE:
1. Represent the following in Venn diagrams
(a) A={a, b, c, d}

(b) A⊂B

(c) A= {a, b, c} and B= {a, b, c}

(d) A= {1, 2, 3} and B= {4, 6, 8}

2. Write in words the relationship between the two sets shown in the figure below
 Their relationship is A⊂B

3. Describe in set notation the meaning of the shaded regions in the following Venn diagrams

(a) A∩B

(b) A∩B∩C

3. In a boys school of 200 students, 90 play football, 70 play basketball, and 30 play Tennis. 26
play basketball and football, 20 play basketball and Tennis, 16 play football and Tennis, while
10 play all three games. How many students in school play none of the three games

4+10+34+6+10+16+58+N= 200
138+N= 200
N=200-138
N=62
62 students play none of the games

3.1.13 COMPLEMENT OF A SET

If A is a subset of a universal set, then the compliment of set A may be represented in a Venn
diagram

Example 21

1. Show in a Venn diagram that (AUB)′

Solution:

(A∪B)΄

(AUB)′ = members of outside A∪B

2. A∩ 𝐵 ′

3. Represent AÎ,∩, µ in a Venn diagram and shade the required region

 A is a subset of Universal set

WORD PROBLEMS

Examples

1. In a certain school of 120 students, 40 learn English, 60 learn Kiswahili and 30 learn both
Kiswahili and English. How many students learn
(a) English only
(b) Neither English nor Kiswahili

Solution:

Let µ = {students in a school}

A= {Students learning English}
B= {Students learning Kiswahili}
(a) n(A) – n(A∩B) = number of students learning English only
40 – 30 = 10
Therefore, the number of students learning English only is 10
(b) =n(µ)-[n(A)+ n(B)- n(A∩B)]
= 120-[40+60-30]
=120-70
=50
50 students learn neither English nor Kiswahili

Alternatively
 (a) By Venn diagram

(b) 10 students learn English only

2. In a certain school 50 students eat meat, 60 eat fish and 25 eat both meat and fish. Assuming
that every student eats meat or fish, find the total members of students in a school
Solution:
Let µ= {total number of students}
A= {students eating fish}
B= {students eating meat}
n(A∪B) = n(A)+ n(B)- n(A∩B)
n(A∪B) =50+60-25
n(A∪B) = 85 students
There are 85 students in a school

Alternatively

(a) By Venn diagram

(b) 85 students were in school

3. There are 24 men at a meeting, 12 are farmers, 18 are soldiers, 8 are both farmers and soldiers
(a) How many are farmers or soldiers

(b) How many are neither farmers nor soldiers

Solution:

NB; both/and means “intersection”

By Venn diagrams

(a) 22 men are soldiers or farmers

(b) 2 are neither farmers nor soldiers
4. In an examination, 120 candidates offered math, 94 English and 48 offered both math and
English. How many candidates offered English but not math assuming that every candidate
offered one of the subjects or both math and English

Solution:

(a) By Venn diagram

(b) 46 students offered English but not math

EXERCISE

1. A class shows that 15 of the students play basketball, 11 play netball and 6 play both
basketball and netball. How many students are there in a class? If every student plays at least
one game

Solution:

n(A∪B)= n(A)+ n(B)- n(A∩B)

n(A∪B)=15+11-6

n(A∪B)=20

There are 20 students in the class

2. In a class of 20 pupils, 12 pupils study English but not History, 4 study History but not
English and 1 who study neither English nor History. How many study History

Solution:

Let A= {pupils who study English}

B= {pupils who study History}

12 + x + 4 = 20

X=3

History = x + 4 =7

7 pupils study History

2. At a certain meeting 30 people drank Pepsi, 60 drank Coca-Cola, and 25 drank both Pepsi
and Coca-Cola. How many people were at the meeting assuming that each person took Pepsi
or Coca-Cola
Solution:
Let A= {drank Pepsi}
B= {drank Coca-Cola}
n(A∪B) = n(A)+n(B)-n(A∩B)
=30+60-25
=65
65 people were at the meeting

3. Represent (A∩B) ∩ (B∩C) on a Venn diagram

4. Represent (A∪B) ∩ C

5. If set A and B have the same common elements represent

 (a) A∪B

(b) A∩B in a Venn diagram

6. In a school of 160 pupils, 50 have bread for breakfast and 80 have sweet potatoes. How many
pupils have neither Bread nor potatoes assuming that none take bread and sweet potatoes

30 pupils have neither Bread nor Potatoes

7. Every Man in a certain club owns a Land Rover or a car. 23 men own Land Rover, 14 own
cars and 5 owns both Land Rovers and cars. How many men are in a club?

32 men were in the club

8. In a certain street of 200 houses. 170 have electricity and 145 have glass doors. How many
houses have both electricity and glass doors, assuming that each house has either a glass door
or electricity or both?

170-x + x + 145-x = 200

170+145+x-x-x = 200
315-x = 200
X=315-200
X=115
115 houses have both electricity and glass doors

REVISION EXERCISE

1. How many subset are there in A= {a, b, c, d, e, f, g}

Solution:
Since n(A) = 7 then From 2n=27=128
Set A has 128 subsets

2. List all the subsets of A= {2, 4, 6}

Solution:
n(A)= 3
2n=23= 8
The subsets are { }, {2}, {4}, {6}, {2, 4}, {2, 6}, {4, 6}, {2, 4, 6}

3. If µ= {a, b, c, d, e}, B= {e, d}, A= {a, b, c} list the elements of B′

(a) B′ = {a, b, c}
(b) Find A΄∩B΄
Solution:
A΄= {d, e}
B΄= {a, b, c}
A΄∩B΄ = { }
(b) A∪(B΄∩A΄) = {a, b, c}
4. Draw a Venn diagram and shade the required region of the following

(a) A΄∪B

(b) B΄∩A΄

(c) A∩B

5. In a group of 29 tourists from different countries, 17 went to Manyara national park, 13 to

Mikumi national park and 8 went neither Mikumi nor Manyara national park. How many
tourists went to both places

To find x 17-x + x + 13-x + 8 = 29

38-x = 29
x =9
:. 9 tourists went both places
 6. From the figure

(a) List the members of set A

A= {1, 2, 5, b}
(b) List the members of set C
C= {1, 4, a, b}

3.1.13 CARTESIAN PRODUCT OF TWO ORDERED PAIR

The Cartesian product of two sets A and B (also called the product set, set direct product, or
cross product) is defined to be the set of all ordered pairs (a,b) where aA and bB.

It is denoted AB. A  B = (a, b) | a  A, b  B

Some relations map some points in a set A to one or several points in a set B. These relations can
be saw as a subset of AB and are called correspondences.
Example:
A={1,2,3} B={a, b,c,d}

AB.={(1,a),(1,b),(1,c),(1,d),(2,a),(2,b),(2,c),(2,d),(3,a),(3,b),(3,c),(3,d)}
a correspondence {(2,d),(3,c)}

If A and B are two non-empty sets, then their Cartesian product A × B is the set of all ordered
pair of elements from A and B.

A × B = {(x, y) : x ∈ A, y ∈ B}

Suppose, if A and B are two non-empty sets, then the Cartesian product of two sets, A and set B
is the set of all ordered pairs (a, b) such that a ∈A and b∈B which is denoted as A × B.
For Example;

1. If A = {7, 8} and B = {2, 4, 6}, find A × B.

Solution:

A × B = {(7, 2); (7, 4); (7, 6); (8, 2); (8, 4); (8, 6)}

The 6 ordered pairs thus formed can represent the position of points in a plane, if a and B are
subsets of a set of real numbers.

2. If A × B = {(p, x); (p, y); (q, x); (q, y)}, find A and B.
Solution:

A is a set of all first entries in ordered pairs in A × B.

B is a set of all second entries in ordered pairs in A × B.

Thus A = {p, q} and B = {x, y}

3. If A and B are two sets, and A × B consists of 6 elements: If three elements of A × B are (2, 5)
(3, 7) (4, 7) find A × B.

Solution:

Since, (2, 5) (3, 7) and (4, 7) are elements of A × B.

So, we can say that 2, 3, 4 are the elements of A and 5, 7 are the elements of B.

So, A = {2, 3, 4} and B = {5, 7}

Now, A × B = {(2, 5); (2, 7); (3, 5); (3, 7); (4, 5); (4, 7)}

Thus, A × B contain six ordered pairs.

4. If A = { 1, 3, 5} and B = {2, 3}, then

Find: (i) A × B (ii) B × A (iii) A × A (iv) (B × B)

Solution:

A ×B={1, 3, 5} × {2,3} = [{1, 2},{1, 3},{3, 2},{3, 3},{5, 2},{5, 3}]

B × A = {2, 3} × {1, 3, 5} = [{2, 1},{2, 3},{2, 5},{3, 1},{3, 3},{3, 5}]

A × A = {1, 3, 5} × {1, 3, 5}= [{1, 1},{1, 3},{1, 5},{3, 1},{3, 3},{3, 5},{5, 1},{5, 3},{5, 5}]
B × B = {2, 3} × {2, 3} = [{2, 2},{2, 3},{3, 2},{3, 3}]

Note:

If either A or B are null sets, then A ×B will also be an empty set, i.e., if A = ∅ or

B = ∅, then A × B = ∅

3.2 PROBABILITY
3.2.1 Fundamental principles of counting
The fundamental counting principle is a rule used to count the total number of possible
outcomes in a situation. It states that if there are n ways of doing something, and m ways
of doing another thing after that, then there are n×m times ways to perform both of these
actions. In other words, when choosing an option for n and an option for m, there are
n×m different ways to do both actions.

Example
Lily is trying to decide what to wear. She has shirts in the following colours: red, purple,
and blue and she put in the following colours: black and white. How many different outfits
can Lily choose from (assuming she selects one shirt and one pair of pants)?

Solution

We know from the definition of the rule of product that if there are n options for doing one

thing (like choosing a shirt), and m options for doing another thing (like choosing a pair of

pants), then there are n times n×m total combinations we can choose from. In this case, there

are 33 options for choosing a shirt, and there are 22 options for choosing pants. Thus, there

are 3 times and 2 time = 3×2=6 total options.

Here is a table where each row represents a possible outfit.

 Shirt Pants

Red Black

Blue Black

Purple Black

Red White

Blue White

Purple White

As expected, there are 6 possible combinations.

Example 2
Supposed that at the dinner there are 6 varieties of soda and 28 choices of sauce. How many
such combinations are there that consist of 1 variety of soda and 1 kind of sauce
Solution
There are 6 ways followed by 28 ways thus there are 6x28 = 168 ways
Example 3
To make a yogurt parfait, you choose one flavor of yogurt, one fruit topping, and one nut
topping. How many parfait choices are there?

Yogurt Parfait
(choose 1 of each)
Flavor Fruit Nuts
Plain Peaches Almonds
Vanilla Strawberries Peanuts
Bananas Walnuts
Raspberries
Blueberries
 Solution
number of flavor x number of fruit x number of nuts
2x5x3 = 30 ways

Example 4
A password is 4 letters followed by 1 digit. Uppercase letters (A) and lowercase letters (a)
may be used and are considered different. How many passwords are possible?
Solutions
Since both upper- and lower-case letters can be used, there are 52 possible letter choices.
letter letter letter letter number
52  52  52  52  10 = 73,116,160 ways
There are 73,116,160 possible passwords.

Example 5
In how many ways can the word ASSASSINATION be arranged

3.2.2 PERMUTATIONS AND COMBINATIONS

Deal with arrangements of objects

Factorial notation
Consider the following pattern
2x1=2
3x2x1=6
4 x 3 x 2 x 1 = 24
5 x 4 x 3 x 2 x 1 = 120
6 x 5 x 4 x 3 x 2 x 1 = 720
Generally
If you have and different objects, you can get
n x (n – 1) x (n – 2) x (n – 3) x…... 3 x 2 x 1 different arrangements
n x (n – 1) x (n – 2) x (n – 3) x…… x 3 x 2 x 1 is called n – factorial denoted by n!
Examples
2! = 2 x 1= 2
3! = 3 x 2 x 1 = 6
 4! = 4 x 3 x 2 x 1 = 24
5! = 5 x 4 x 3 x 2 x 1 = 120
6! = 6 x 4 x 3 x 2 x 1 = 720
0! = 1

Exercise

1. Evaluate each of the following

8! 3! 5!
a) 6 b) c) (7 – 2)! d) 0! e)
3! (5 – 2)! 2!

2. Simplify
n!
(a) (n+1)!
(n+1)!
(b) (n−1)!
(2n)!
(c) (2n+2)!

3. Write the following in factorial form

(a) 4 x 3 x 2 x 1
(b) 6 x 5 x 4
(7x6)(3𝑥2𝑥1)
(c) 2

Solution

1. a. 6! = 6 x 4 x 3 x 2 x 1 = 720

8! 8x7x6x5x4x3x2x1 40320
b. 3! = = = 6720
3x2x1 6

c. (7 – 2)! this implies that 5! = 5 x 4 x 3 x 2 x 1 = 120

3! 3x2x1
d. 0! = =6
1

5! 5x4x3! 20
e. = = = 10
(5 – 2)! 2! 3!2! 2

n! n! 1
2. (a) = (n+1)n! = n+1
(n+1)!

(n+1)! (n+1)n(n−1)!
(b) = = n(n + 1) = n2 + n
(n−1)! (n−1)!
 3.2.3 WAYS OF ARRANGING UNLIKE OBJECTS
Examples
1. How many different three numbers can be formed using the digits 9, 6 and 3
Solution
Digits 9, 6, 3
Ways of science 3 3 3
The total number of ways is 3 x 3 x 3 = 27
2. How many 3 letters groups can be formed using the letters 0, N and W provide each letter
is used once?
Solution
Letters O N W
Ways of selective 3 2 1
Total number of ways = 3x2x1
= 6
3.2.4 PERMUTATIONS
-Is arrangement of objects in a particular order.
n!
-It is defined as np = p (n, r) = (n−r)!
r
Example
1. How many ways three letters A B C can be arranged taking three at a time?
Solution
ABC, BCA, BAC, CAB, CBA, ACB
There are 6 ways ie 3p3 = 6
Note:
i) The upper 3 indicates the total number of objects
ii) The lower 3 indicates the number of items used in making arrangements
ii How many three letters A, B, C can be arranged taking two at a time?
Solution.
AB, BA, CA, AC, BC, CB
There are 6 ways
i.e. 3p2 = 6
Note
The order of arrangement matters
 i.e. AB is different permutation from BA

Generally
n
To find pr i.e. the number of permutations of n different objects taking r at a time can be
arranged as follows.
- The 1st place can be filled in n different ways
- The 2nd place can be filled in (n – 1) different ways
- ‘’ 3rd place ‘’ ‘’ ‘’ ‘’ (n – 2) ‘’ ‘’
- rth ‘’ ‘’ ‘ ‘ (n – r + 1) ‘’ ‘’
Pr = n (n – 1) (n – 1) …… (n – r + 1) ……..i
n

eqn (i) can be multiplied and divided by (n – r) (n – r – 1) …….x 3 x 2 x 1

eqn i) becomes
n(n − 1)(n − 2)(n − 3) … … . (n − r + 1)x(n − r − 1) … .3x2x1
npr =
(n − r)x(n − r − 1) … … x3x2x1
n!
npr =
(n − r)!
1. How many two letters patterns can be formed from the letter six?

Solution
n = 6, r = 2
6! 6𝑥5𝑥4!
6p2 = (6−2)! = = 30 ways
4!
2. How many arrangements can be made from the word mathematics?
solution
m = 2, a = 2, t = 2 n=11

n!
arrangement = m!t!a!

11! 39,916,800
= 2!2!2! = = 4, 989,600
8

The word Mathematics can be arranged in 4, 989,600 ways

3.2.5 COMBINATIONS
- Is the selection of objects where order is not important
Example (1)
Three letters ABC may be arranged taking three at a time as follows
ABC, BCA, BAC, CAB, CBA, ACB
- These are different permutations but the same combination
- Denoted by, 3C3 = 1
 Examples (2)
We may take the same letters; find the numbers of selections of the letters ABC, taking
two at a time
AB, AC, BC, BA, CA, CB
AB, AC, BC
3
C2
Examples (3)
In how many ways can r objects be chosen from n unlike objects?
The number of combinations of n objects taking at time can be arranged in r!
The number of combinations of n objects taking r at a time can be arranged in r
The numbers of permutations
= r! x nCr
npr = r! x nCr
npr
nC r = r!
But
n!
npr = (n−r)!

n!
nC r =
(n − r)! r!

Note:
n
i) nCr may be written as ( ) or C(n, r )
r

ii) nCo = 1, n
Cn = 1, n
C1 = n

Examples (4)
A mixed hockey team containing 5 men and 6 women is to be chosen from 7 men and 9 women
in how many ways can this be done?
Solution
5 men can be selected from 7 men in, 7C5 ways
6 women can be selected from 9 men in, 9C5 ways
The combination will be,
7
C5 x 9C6
7! 9!
= (7−5)!5! x (9−6)!6!
5040 362,880
= x
240 4320
 = 21 x 84
= 1,764 ways

Examples (5)
Tabulate the different selections of two letters that can be made from the letters TAKEN, deduce
the value of 5C2
Solution
TAKEN
TA, TK, TE, TN, AK, AE, AN, KE, KN, EN
5! 120
5 C2 = = = 10
(5 − 2)! 2! 12

Examples 6

In how many ways can a cricket team be selected from 13 players? Hint a cricket team has 2
players.

Solution

13! 6,227,020,800
13C2 = (13−2)!2! = = 78
79,833,600

Examples 7
In ow many ways can a football team of 11 players can be chosen from a class of 15? In how
many ways can be the 4 spectators be chosen
from the class of 15?

Solution

15!
(a) 15C11 = (15−11)!11! = 1365
15!
(b) 15C4 = (15−4)!4! = 1365

Note: nCr = nCn-r

Exercise

1. From a list of 30 books, how many different groups of 22 books can be selected?

Solution

30!
n = 30 , r = 22 then 30C22 = (30−22)!22! = 5,852,925

2. How many different netball teams of 7 members can be formed from 18 players?

Solution

n
Cr = 18C7

18!
18C7 = = 31,824
(18 − 7)! 7!

3. A circle has 10 marked points, how many different & three – sided figures which can
be formed by joining any three of these points

Solution

10!
10C3 = (10−3)!3! = 120

4. How many different committees comprising of 20 people can be formed from 25

people?

Solution

25!
25C20 = = 53,130
(25 − 20)! 20!

5. If a plane paper has 9 points in which no three points appear on the same straight line,
how many distinct triangles can be formed by joining any three points?

Solution

9!
9C3 = (9−3)!3! = 84
 3.2.6 PROBABILITY OF AN EVENT.
In any experiment, depending on the number of trials.
Sample space, S
Is the set of all possible outcomes.
Example;
Tossing of dice once;
S = {1, 2, 3, 4, 5, 6}.
Tossing of coin once.
S = {H, T}.
Event, E
- Is the specified outcomes.
Example;
Tossing of a dice once the specified outcome is odd number.
Sample space, S = {1, 2, 3, 4, 5, 6}
Event, E = {1, 3, 5}

Possibility
- Is the occurrence of any expected event.
Note:
Sample space and event are usually denoted by capital letters like A, B and E.

Definition.
Possibility of an event is the ratio of number of events to the number of sample space.
Number of event n(E)
P(E) = =
Number of sample space n(S)

Example;
A coin is tossed twice, what is the probability of getting two tails?

Solution
By using probability table.

Sample space, S = {HH, HT, TH,TT}

Event, E = {TT}
Thus,
n(S) = 4, n(E) = 1
Number of event 1
P(E) = = = 0.25
Number of sample space 4

Exercise
1. Write the possibility set for each of the following experiments;
a) Expectation of the football match between two teams
b) A die is flipped and a face showing up is recorded.

2. A student is taken at random from a class of 15 boys and 10 girls. What is the probability that
the student taken at random is not a girl?

3. A number between 19 and 31 inclusive is chosen at random. What is the that;

a) The number chosen is odd?
b) The number chosen is prime?

4. Taking the sample space for the total number of all possible outcomes when a pair of dice is
flipped, find on a single flip of a pair of dice, the probability of obtaining;
a) A sum of ten.
b) A odd sum.
c) A sum less than fire.

3.2.7 COMBINED EVENTS.

Combined events are those events that can be represented by two or more simple
events.
The events/outcome can easily be obtained by using a tree diagram or a table.

Example;
Use a tree diagram to list the sample space showing the possible arrangements of
boys and girls in a family of exactly three children. What is the probability that,
a) All children are girls.
b) Two children are girls and one is a boy.
c) At least one of the children is a boy.
d) None of the children are girls.
(c)
Solution
The tree diagram.

The outcome can be summarized as;

S = {BBB, BBG, BGB, BGG, GBB, GBG, GGB, GGG}.

(a) E1 = {GGG}; n(S) = 8
n(E1) = 1
Number of event n(E1 )
P(E1 ) = Number of sample space = n(S)

Number of event n(E1 )

P(E1 ) = Number of sample space = n(S)

n(E1 ) 1
P(E1 ) = =8
n(S)

(b) E2 = {BGG, GBG, GGB)

n(E2) = 3
Number of event n(E1 )
P(E2 ) = Number of sample space = n(S)

n(E1 ) 3
P(E1 ) = =8
n(S)

(c) E3 = {BBB, BBG, GBB, BGB, BGG, GBG, GGB}

n(E3) = 7
Number of event n(E3 )
P(E3 ) = Number of sample space = n(S)
 n(E3 ) 7
P(E3 ) = =8
n(S)
(d) E4 = {BBB}
n(E4 ) = 1
Number of event n(E4 )
P(E4 ) = Number of sample space = n(S)

n(E4 ) 1
P(E4 ) = =8
n(S)

Example 2:
In a single toss of a pair of dice, find the probability of obtaining a sum of
(i) 9
(ii) 12
(iii) 9 or 12

Solution.

n(S) = 6 x 6 = 36

Let E1 be the event of a sum of 9

E2 be the event of a sum of 12

(a) Then, E1 = {(3,6), (4,5), (5,4), (6,3)}

Number of event n(E1 )
P(E1 ) = Number of sample space = n(S)
 n(E1 ) 4 1
P(E1 ) = = 36 = 9
n(S)

(b) Also, E2 = {(6,6)}

Number of event n(E2 )
P(E2 ) = Number of sample space = n(S)
n(E2 ) 1
P(E2 ) = = 36
n(S)
(c) The sum is 9 or 12.

P(E1 + E2) = P(E1 ) + P(E2)

n(E1 ) n(E2 )
P(E1 + E2 ) = +
n(S) n(S)
1 1
= + 36
9
5
= 36
Example 3
A bag contains 3 black marbles and 2 white marbles. A marble is taken at random from the bag
and then replaced, a second marble is chosen what is the probability that;
(i) They are both black, and
(ii) One is black and the other is white
Solution
B W T
3 2 5
3 2
p(B) = 5 and p(W) = 5 Then using tree diagram

Second Draw
First Draw P(B1, B2)
3
B2
5

3 B1
5
2 P(B1, W2)
W2
5

3 P(W1, B2)
5 B2

2
5 W1

𝟐 P(W1, W2)
W2
𝟓
 (i) If the drawing is made with replacement the probability that both are black ball
3 3 9
will be p(B1 ∩ B2 )=5 x 5 = 25 = 0.36
(ii) Probability that one is black and the other is white when drawing is made with
2 3 3 2 12
replacement will be p(w1 ∩ B2 ) + p(B1 ∩ w2 ) = 5 x 5 + 5 x 5 = 25 = 0.48

Exercise
1. A fraction is written by selecting the numerator from the digit 1,2 and 4 and the denominator
from the digits 5, 6 and 7. Find the probability that the fraction written will be;
a) Less than two-third
b) Less or equal to a half

2. Two coins and a die are simultaneously tossed. What is the probability that the number less
than three, a head and a tail will show up.

3. Two dice are flipped. Find the probability of getting

a) At least one 5.
b) A total score of 6.
c) A total score not divisible by 3.

4. Three coins are tossed simultaneously. Find the probability that

a) Three tails appear.
b) At least two tails appear.
c) Two heads and one tail appear.

Note:
Probabilities are expressed as fractions or percentages and obey the following rules.

i) Rule of range.
Let E be an event, then 0 ≤ P(E) ≤ 1
i.e Probability of an event lies between 0 and 1.
If P(E) = 0, then E can not occur.
If P(E) = 1, then E is certain to occur.

ii) Rule of complement.

If E is an event, then
P(E) + P(E)' = 1
Where, P(E)' = 1 - P(E), Where P(E)' is the probability of an event not occurring.
 3.2.8 MUTUALLY AND NON-MUTUALLY EXCLUSIVE EVENTS

MUTUALLY EXCLUSIVE EVENTS.

- These are events that cannot occur concurrently.
- Occurrence of one event precludes the occurrence of the other event.
For mutually exclusive events, P(AnB) = 0
P(A ∪ B) = P(A) + P(B)

NON-MUTUALLY EXCLUSIVE EVENTS.

- These are events that can occur concurrently.

- The occurrence of one will not hinder the occurrence of the other. They may both occur
simultaneously.
For Non-mutually exclusive events,
P(A ∪ B) = P(A) + P(B) − P(A ∩ B)

Example 1;
A boy contains 3 red balls, 4 blue balls, 5 white balls and 6 green balls. Which are identical. A
ball is drawn at random, Find the probability that it is either;
(i) red or blue.
(ii) red or white.
(iii) blue or white or green.
(iv) red or blue or green or white.
Solution.
R B W G T
3 4 5 6 18

3 4 5 6
p(R) = 18, p(B) = 18 p(W) = 18 , p(G) = 18
3 4 7
(i) p(R ∪ B) = p(R) + p(B) = 18 + 18 = 18 = 0.38888888
3 5 8
(ii) p(R ∪ W) = p(R) + p(W) = 18 + 18 = 18 = 0.4444444
4 5 6 15
(iii) p(B ∪ W ∪ G) = p(B) + p(W) + p(𝐺) = + + = = 0.8333
18 18 18 18
3 4 5 6 18
(iv) p(R ∪ B ∪ W ∪ G) = p(R) + p(B) + p(W) + p(G) = 18 + 18 + 18 + 18 = 18 = 1

Example 2;
A card is chosen at random from a standard deck of 52 playing cards. What is the probability of
getting a king or a club?
Solution
The two events are non-mutually exclusive events.

P(King or Club) = P(King) + P(Club) - P(King and Clubs)

4 13 1
P(King or Club) = 52 + 52 − 52
16 4
[Link] 52 = 13

Exercise.
1. If P(A) = 0.1, P(B) = 0.9 and P(AnB) = 0.2. Find P(AuB) given that A and B are
non-mutually exclusive events

2. If P(A) = 0.2 and P(B) = 0.5, Find P(AuB) given that A and B are independent
events.

1 1
3. If P(A) = 3 and P(B) = , Find P(AuB) given that A and B are mutually exclusive
2
events.

4. Find the probability of drawing an Ace or a King in a single draw from a deck of
52 playing cards.

5. A fair die is tossed once. Find the probability of getting a number greater than three
or an even number.

[Link] INDEPENDENCE AND DEPENDENT EVENTS.

INDEPENDENT EVENTS.
- Are those events in which the occurrence of one event has nothing to do with the
occurrence or non-occurrence of the other event.
Two events A and B are said to be independent if P(AnB) = P(A) x P(B). This is
called multiplicative rule for independent events.
Example.
An electronic device has two independent components with reliability of 0.82 each.
The device work only if both components are functional, What is the probability that
the device will not work?
Solution

Let A be the event of first component

B be the event of second component
P(AnB) = P(A) x P(B)
= 0.82 x 0.82
P(AnB) = 0.6724
Therefore,
The probability that the device will not work.
P(AnB)′ = 1 - P(AnB)
= 1 - 0.6724
P(AnB)′ = 0.3276

Exercise
A bag contains 3black marbles and 2 white marbles.
a) A marble is taken at random from the bag and then replaced. A second marble is
chosen. What is the probability that;
i) They are both black?
ii) One is black and the other is white?

b) Find the probability if the two marbles are chosen without any replacement.

DEPENDENT EVENTS.
- Are those events in which the occurrence of one event affects the occurrence of the
other event.

- Two events A and B are said to be dependent if,

𝐴
P(AnB) = P( 𝐵) x P(B) or
𝐵
P(AnB) = P( 𝐴) x P(A) Where
 𝐴 𝐵
P( ) or P( ) is conditional probability.
𝐵 𝐴

- It read as probability of A is given that B has occurred/ is certain to occur.

Example 1
2 1 𝐴
If A and B are dependent events such that P(B) = 3 and P(AnB) = 4. Find P( 𝐵)

Solution

A
P(A ∩ B) = P (B) x P(B)
A P(A∩B)
𝑃 (B) = P(B)
1
4 1 3
= 2 = 4x2
3

3
=8

Example 2
𝐵 3 1
If A and B are dependent events such that P( 𝐴) = 4 and P(A) = 2, Find P(AnB).

Solution.
B
P(A ∩ B) = P ( ) x P(A)
A
3 1
= x
4 2
3
=8
Exercise
1. A coin is tossed and a spinner numbered 1 to 7 is made to spine. Find the probability of
obtaining a tail on the coin and an odd number on the spinner.

2. The names of 5 boys and 3 girls were put in a box. One name is picked at random from the
box, without replacing the first name, second name is picked at random. Find the probability that
both are names of boys.

3. On an interview, four out of ten interviewees got an A grade. If there interviewees are chosen
at random without replacement, find the probability that all three got an A on the interview.
Conditional probability
A
: event A given the condition that event B has occurred.
B

{2}| E1 : point 2 occurs given that the point is known to be even.

A
𝑃 (B)the conditional probability of A given B (as the event B has occurred, the chance of
the event A then occurs!!)

Formula of the conditional probability:

A P( A  B)
P( ) =
B P( B)
and

B P( A  B)
P( ) =
A P( A) .
1
P( E1  {2}) P({2}) 6 1
Example P({2} | E1 ) = = = =
P( E1 ) P( E1 ) 1 3
2

Ac A
Note:
P( ) + P( ) = 1
B B
A B
Note:
P( A  B) = P( B) P( ) = P( A) P( )
B A
Independent Events:
A
P( ) = P( A)
B
or  A and B are independent events.
B
P( ) = P( B) .
A
 A
Dependent Events:
P( )  P( A)
B
or  A and B are dependent events.

B
P( )  P( B) .
A
Intuitively, if events A and B are independent, then the chance of event A occurring is the same no
matter whether event B has occurred. That is, event A occurring is “independent” of event B
occurring. On the other hand, if events A and B are dependent, then the chance of event A occurring
given that event B has occurred will be different from the one with event B not occurring.
Example
A: the event of a police officer getting promotion.
M: the event of a police officer being man.
W: the event of a police officer being woman.

A A

P( A) = 0.27, P( ) = 0.3, P( ) = 0.15
M W
The above result implies the chance of a promotion knowing the candidate being male is twice
higher than the one knowing the one being female. In addition, the chance of a promotion knowing
the candidate being female (0.15) is much lower than the overall promotion rate (0.27). That is,
the promotion event A is “dependent” on the gender event M or W.
 A promotion is related to the gender.

Note: P( A  B) = P( A) P( B) as events A and B are independent.

Example
The following are the data on the gender and marital status of 200 customers of a company.

Male Female
Single 20 30
Married 100 50
(i) What is the probability of finding a single female customer?
(ii) What is the probability of finding a married male customer?
(iii) If a customer is female, what is the probability that she is single?
(iv) What percentage of customers is male?
(v) If a customer is male, what is the probability that he is married?
(vi) Are gender and martial status mutually exclusive? Explain.
(vii) Is martial status independent of gender? Explain.

A1: the customers are single

A2: the customers are married
B1: the customers are male.
B2: the customers are female.
Male Female Total
Single 20 30 50
Married 100 50 150
Total 120 80 200

𝟑𝟎
(i) 𝐩(𝐀 𝟏 ∩ 𝐁𝟐 ) = 𝟐𝟎𝟎 = 𝟎. 𝟏𝟓
𝟏𝟎𝟎
(ii) 𝐩(𝐀 𝟐 ∩ 𝐁𝟏 ) = 𝟐𝟎𝟎 = 𝟎. 𝟓
𝐀 𝐩(𝐀𝟏 ∩𝐁𝟐 )
(iii) 𝐩 (𝐁 𝟏 ) = .
𝟐 𝐩(𝐁𝟐 )

P(B2 ) = P( A1  B2 ) + P( A2  B2 ) =
30 50 80
+ =
200 200 200
30
 A  P( A1  B2 ) 200 30
P 1  = = = = 0.375 .
 B2  P(B2 ) 80 80
200

(iv) P(B1 ) = P( A1  B1 ) + P( A2  B1 ) =
20 100 120
+ = = 0.6
200 200 200
100
 A2  P( A2  B1 ) 200 100 5
(v) P  = = = = .
 B1  P(B1 ) 120 120 6
200
(vi) Gender and marital status are not mutually exclusive since

P( A1  B1 )  0
 (vii) Gender and marital status are not independent since

 A  30 50
P 1  =  = P( A1 ) .
 B2  80 200
Example
A football team has to play two matches to qualify for the second round. There 0.7 chance that it
will win the first match and 0.8 chance of winning the second Match. Find the probability that it
will win;

(i) Only one match, and

(ii) At least one match
Solution

consider a tree diagram

Second
First Match
Match
0.8
W2
P(W1, W2) =

0.7 W1
0.2 P(W1, L2) =
L2

0.8 P(L2, W2) =

W2

L1

0.2 P(L1, L2) = 0.3 x0.2=0.6

L2
(2Marks)

(a) The probability that it will qualify Only one match

p(W1 ∩ L2 ) + p(L1 ∩ W2 ) = 0.24 + 0.14 = 0.38

(b) The probability that it will qualify At least one match

 p(W1 ∩ L2 ) + p(L1 ∩ W2 ) + p(W1 ∩ W2 ) = 0.24 + 0.14 + 0.56 = 0.94

Example
The following table shows Classification of CBE staffs by Gender and Education;
Graduate (G) Postgraduate (P) Total
Male (M) 7 20 27
Female (F) 4 9 13
Total 11 29 40

If one of these staff member is selected at random for membership on research committee,
what is the probability that this staff is
(i) A Female and Graduate, and
(ii) A Male and Graduate.

Given

Graduate (G) Postgraduate (P) Total

Male (M) 7 20 27
Female (F) 4 9 13
Total 11 29 40
27 13 11 29 G 7 G 4
P(M) = 40 , p(F) = 40 , p(G) = 40 , p(P) = 40 , P (M) = 11, , P ( F ) = 11,
P 20 p 9
P (M) = 29 and , P (F) = 29

Asked to find
G 4 13 42
(i) p(F ∩ G) =, P (F ) x p(F) = 11 x 40 = 440
G 7 27 189
(ii) p(M ∩ G) =, P (M) x p(M) = 11 x 40 = 440

APPLICATION OF PROBABILITY
The applications of probability includes;

i) Budget estimates. ii) Assessing the amount of harvest in agriculture.

iii) Lottery games. iv) Human reproductions to plan a baby boy or girl. v) Risk control in
many aspects in our day to day life.
 CHAPTER FOUR

BOOLEAN LOGIC CONCEPTS

4.1 DEFINITION OF LOGIC
Logic concerns with the study of analysis of methods of reasoning which lead to certain
conclusion or statement.
Propositional Logic is concerned with statements to which the truth values, “true” and “false”,
can be assigned. The purpose is to analyze these statements either individually or in a composite
manner
Prepositional Logic – Definition
A proposition is a collection of declarative statements that has either a truth value "true” or a truth
value "false". A propositional consists of propositional variables and connectives. We denote the
propositional variables by capital letters (A, B, etc.). The connectives connect the propositional
variables.
Some examples of Propositions are given below −

• "Man is Mortal", it returns truth value “TRUE”

• "12 + 9 = 3 – 2", it returns truth value “FALSE”
The following is not a Proposition −
• "A is less than 2". It is because unless we give a specific value of A, we cannot say whether
the statement is true or false.
CONNECTIVES
In propositional logic generally we use five connectives which are −
• Disjunction -OR (∨)
• Conjunction -AND (∧)
• Negation/ NOT (¬)
• Implication / if-then (→)
• If and only if (⇔).
1. DISJUNCTION OR (∨)
The OR operation of two propositions A and B (written as A∨B) is true if at least any of the
propositional variable A or B is true.
The truth table is as follows −

A B A∨B

T T T

T F T

F T T

F F F

2. CONJUCTION AND (∧)

The AND operation of two propositions A and B (written as A∧B) is true if both the
propositional variable A and B is true.
The truth table is as follows −

A B A∧B

T T T

T F F

F T F

F F F
3. Negation (¬)
The negation of a proposition A (written as ¬A) is false when A is true and is true when A is
false.
The truth table is as follows −

A ¬A

T F

F T

4. CONDITIONAL /Implication

Implication / if-then (→) − An implication A→B is the proposition “if A, then B”. It is false
if A is true and B is false. The rest cases are true.
The truth table is as follows −

A B A→B

T T T

T F F

F T T

F F T
Example

Write down the truth table for (P → Q) ∧ (Q → P)

(A) (B)

P Q P→Q Q→P A∧B

T T T T T

T F F T F

F T T F F

F F T T T

The statement (P → Q) ∧ (Q → P) is known as bi-conditional statement and is abbreviated as

P⇔ Q

5. BI-CONDITIONAL
If and only if (⇔) − A⇔B is bi-conditional logical connective which is true when A and B
are same, i.e. both are false or both are true.
The truth table is as follows −

A B A⇔B

T T T

T F F

F T F

F F T
Example write down the Truth table for P ⇔ Q
P Q P⇔ Q

T T T

T F F

F T F

F F T

Example. The truth value of 43 > 3 if and only if 5< 3 (F)

43 < 3 if and only if 3 < 5 (F)

43< 3 if and only if 5 < 3 (T)

43> 3 if and only if 5 > 3 (T)

TAUTOLOGIES
A Tautology is a formula which is always true for every value of its propositional variables.
Example − Prove [(A→B) ∧A] →B is a tautology
The truth table is as follows −

A B A→B (A → B) ∧ A [(A → B) ∧ A] → B

T T T T T

T F F F T

F T T F T

F F T F T

As we can see every value of [(A→B) ∧A] →B is "True", it is a tautology.

CONTRADICTIONS
A Contradiction is a formula which is always false for every value of its propositional variables.
Example − Prove (A∨B) ∧[(¬A) ∧(¬B)] is a contradiction
The truth table is as follows −

A B A∨B ¬A ¬B (¬ A) ∧ (¬ B) (A ∨ B) ∧ [(¬ A) ∧ (¬ B)]

T T T F F F F

T F T F T F F

F T T T F F F

F F F T T T F

As we can see every value of (A∨B) ∧[(¬A) ∧(¬B)] is “False”, it is a contradiction.

CONTINGENCY
A Contingency is a formula which has both some true and some false values for every value of
its propositional variables.
Example − Prove (A∨B) ∧(¬A) a contingency
The truth table is as follows −

A B A∨B ¬A (A ∨ B) ∧ (¬ A)

T T T F F

T F T F F

F T T T T

F F F T F
As we can see every value of (A∨B) ∧(¬A) has both “True” and “False”, it is a contingency.

4.2.2 INVERSE, CONVERSE, AND CONTRA-POSITIVE

Implication / if-then (→) is also called a conditional statement. It has two parts −

• Hypothesis, p
• Conclusion, q
As mentioned earlier, it is denoted as p→q
Example of Conditional Statement − “If you do your homework, you will not be punished.”
Here, "you do your homework" is the hypothesis, p, and "you will not be punished" is the
conclusion, q.
Inverse − An inverse of the conditional statement is the negation of both the hypothesis and the
conclusion. If the statement is “If p, then q”, the inverse will be “If not p, then not q”.
Thus, the inverse of p→q is ¬p→¬q.
Example − The inverse of “If you do your homework, you will not be punished” is “If you do
not do your homework, you will be punished.”
Converse − The converse of the conditional statement is computed by interchanging the
hypothesis and the conclusion. If the statement is “If p, then q”, the converse will be “If q, then
p”.

The converse of p→q is p→q.

Example − The converse of "If you do your homework, you will not be punished" is "If you will
not be punished, you do your homework”.
Contra-positive − The contra-positive of the conditional is computed by interchanging the
hypothesis and the conclusion of the inverse statement. If the statement is “If p, then q”, the
contra-positive will be “If not q, then not p”.
The contra-positive of p→q is ¬q→¬p.
Example − The Contra-positive of " If you do your homework, you will not be punished” is "If
you are punished, you did not do your homework”.

EQUIVALENT STATEMENTS/ PROPOSITIONAL EQUIVALENCES

Two statements X and Y are logically equivalent if any of the following two conditions hold −
• The truth tables of each statement have the same truth values.
• The bi-conditional statement X⇔Y is a tautology.
Example − Prove ¬(A∨B) and [(¬A) ∧(¬B)] are equivalent

Testing by 1st method (Matching truth table)

A B A∨B ¬ (A ∨ B) ¬A ¬B [(¬ A) ∧ (¬ B)]

T T T F F F F

T F T F F T F

F T T F T F F

F F F T T T T

Here, we can see the truth values of ¬(A∨B) and[(¬A) ∧(¬B)] are same, hence the statements are
equivalent.

Testing by 2nd method (Bi-conditionality)

A B ¬ (A ∨ B) [(¬ A) ∧ (¬ B)] [¬ (A ∨ B)] ⇔ [(¬ A) ∧ (¬ B)]

T T F F T

T F F F T

F T F F T

F F T T T

As [¬(A∨B)] ⇔[(¬A) ∧(¬B)] is a tautology, the statements are equivalent.

Two propositions are logically equivalent if they have exactly the same truth values
Example P V Q and Q V P are logically equivalent

Solution: Draw truth for P V Q and Q V P

1 2 3 4

P Q PVQ QVP

T T T T

T F T T
F T T T

F F F F

Since column 3 has exactly the same truth values as column 4 then P V Q≡ Q V P

Questions

Show whether or not the following propositions are logically equivalent

(i) P → Q, ~ P V Q

Q P→Q ~P ~PVQ
T T T F T
T F F F F
F T T T T
F F T T T

Since column 3 and 5 have exactly the same truth value therefore P → Q≡ ~ P V Q

(ii) P → (P V Q); P → Q

P Q PVQ 1→3 p →Q

T T T T T

T F T T F

F T T T T
F F F T T

Since column 4 does not have exactly same truth value as column 5 then p → (P V Q)≠ P → Q
 (iii) P → Q: ~ P → Q

P Q P→Q ~P ~P→Q
T T T F T
T F F F T
F T T T T
F F T T F
Since column 3 does not have exactly same truth values as column 5 therefore P → Q ≠ ~ P → Q

(iv) P → Q; Q → P

P Q P→Q Q→P
T T T T
T F F T
F T T F
F F T T

Since column 3 does not have exactly same truth values as column 4 therefore P → Q≠ Q → P

(v) ~(P→Q);PV~Q
(5) (6)

P Q ~Q P→Q ~ (P → Q) P V ~Q
T T F T F T
T F T F T T
F T F T F F
F F T T F T
Since column 5 does not have exactly same truth value as column 6 therefore

~ (P → Q) P V ~Q

(vi) ~ (P V Q); ~P ∧ ~Q

P Q ~P ~Q PVQ ~ (P V Q) ~P ∧ ~Q
T T F F T F F
T F F T T F F
F T T F T F F
F F T T F T T

Since column 6 has exact same truth values as column 7 therefore ~ (P V Q) → (~P ∧ ~Q)
4.2.4 LAWS OF ALGEBRA OF PROPOSITIONS

1. Idempotent laws

a) P V P≡ P b) P Λ P≡ P

2. Commutative

a) P V Q≡ Q V P b) P⋀ Q≡ Q Λ P

3. Associative laws

a) (P V Q) V R≡ P V (Q V R) b) (P Λ Q) Λ R ≡P Λ (Q Λ R)

4. Distributive laws

a) P V (Q Λ R) ≡ (P V Q) Λ (P V R b) P Λ (Q V R) ≡ (P Λ Q) V (P Λ R)

5. Identity laws

a) P V F≡ P b) P Λ T ≡P c) P V T ≡T d) P Λ F ≡T

6. Complementary laws

a) P V ~ P ≡T b) P Λ ~ P ≡T c) ~ ~P ≡P d) ~ T ≡F or T~≡F e) ~ F ≡T or T~≡T

7. De-Morgan’s law

a) ~ (P V Q) ≡ ~ P Λ ~ Q b) ~ (P Λ Q) ≡ ~ P V ~ Q

Examples

1. Using the laws of algebra of proposition simplify (P V Q) ∧ ~ P

Solution

(P V Q) Λ ~ P≡ (~ P Λ P) V (~ P Λ Q) ……distributive law

≡F V (~ P Λ Q) ………compliment law

≡ (~ P Λ Q) ………...identity
 2. Use the laws of algebra of propositions to simplify the statement given
below; q ∨ (p ∧∼ q) ∨ (r ∨ q)

Solution
q ∨ (p ∧∼ q) ∨ (r ∨ q) Given
[(q ∨ p) ∧ (q ∨∼ q)] ∨ (r ∨ q) Distributive Law
[(q ∨ p) ∧ T] ∨ (r ∨ q) Complementary Law
(q ∨ p) ∨ (r ∨ q) Identity Law
q ∨ (r ∨ p) Associative law

Questions

1. Simplify the following propositions using the laws of algebra of propositions

i) ~ (P V Q) V (~P Λ Q)

ii) (P Λ Q) V [~ R Λ (Q Λ P)]

2. Show using the laws of algebra of propositions (P Λ Q) V [P Λ (~Q V R)] ≡ P

3. Construct a truth table for [(p → ~q) ∧ (r → p) ∧ r] → ~p

ARGUMENTS

An argument in logic is a declaration that a given set of proposition p1, p2, p3….pn called
premises yields to another proposition Q called a conclusion such as argument is denoted by p1,

p2….pn Q

Example of an argument
If I like mathematics, then I will study, either I study or I fail. But I failed therefore I do not like
mathematics.
VALIDITY OF AN ARGUMENT
Validity of an argument is determined as follows
→An argument P1, P2, P3… Pn⊢ Q is valid if Q is true whenever all the premises P1, P2, P3… Pn
are true
→Validity of an argument is also determined if and only if the proposition
(P1 ∧ P2 ∧ P3 ∧ …... Pn) → Q is a tautology
 Example

Prove whether the following argument is valid or not P, P → Q⊢ Q

Solution:

Draw a truth table for [P ∧ P → Q] → Q

P Q P→Q P ∧ (p → Q) P ∧ (p → Q) → Q

T T T T T

T F F F T

F T T F T

F F T F T

1. Since in row 1 the conclusion is true and all the premises are true then the argument is valid

2. Since column 5 is a tautology then the argument is valid

QUESTION

Use the truth table to show whether the given argument is valid or not P → Q, Q → R⊢ P → R

Example

Symbolize the given argument and then test its validity

*If I like mathematics, then I will study, either I study or I fail. But I failed, therefore I do not like
mathematics.
Solution.

The given argument is symbolized as follows

Let p ≡ I like mathematics

q ≡ I will study

r ≡ I fail

Then given argument is as follows

P → q, q v r, r, ⊢~p

Testing the validity [(p → q) ∧ (q ∧ r) ∧ r] → ~p

P Q R P→q qvr 3∧4∧5 ~p 6→7

T T T T T T F F

T T F T T F F T

T F T F T F F T

T F F F F F F T
F T T T T T T T

F T F T T F T T

F F T T T T T T

F F F T F F T T

Since column 8 is not a tautology the given argument is not valid

QUESTIONS

1. Translate the following arguments in symbolic form and then test its validity

i) If London is not in Denmark, then Paris is not in France. But Paris is in France, therefore
London is in Denmark

ii) If I work, I cannot study. Either I work or I pass mathematics. I passed mathematics
therefore I studied.

iii) If I buy books, I lose money. I bought books, therefore I lost money

2. Determine the validity of

i) p → q, ~q⊢ ~p

ii)~p → q, p⊢ ~q

iii) [p → ~ q], r → q, r⊢ ~p

ELECTRICAL NETWORK

Electrical network is an arrangement of worse and switches that will accomplish a particular task
e.g. lighting a lamp, turning a motor.

The figure below shows an electrical network

When the switch p is closed the current flows between T1 and T2

The above network simplifies to the following network

Relationship between statement in logic and network

A SERIES AND PARALLEL CONNECTION OF SWITCHES

(i) A series connection of switches

The following switches are connected in series

The current flow between T1 and T2 when both switches are closed current flows when
p ∧ Q is true

(ii) A parallel connection of switches

The current will flow when either one of the switches is closed.

Currents flow when P V Q is true

 Example

Consider the electrical network below

(i) Construct a compound statement presenting the network above

(ii) Find possible switch setting that will allow the current to flow between T1 and T2

Solution
Note i) current flows between T1 and T2 when switch p is closed i.e. p is true OR
ii) The current flows between T1 and T2 when switch switches q and r are closed i.e.
Q ∧ R is true. The required compound statement is p v (Q ∧ R)
iii) To find possible switch setting, draw a truth table P v (Q ∧ R)
P Q R Q∧R P V (Q ∧ R) Current flows yes or
No
T T T T T Yes

T T F F T Yes

T F T F T Yes

T F F F T Yes

F T T T T Yes

F T F F F No

F F T F F No

F F F F F No
 Possible switch setting

P Q r

Closed Closed Closed

Closed Closed Closed

Closed Closed Closed

Closed Closed Closed

Closed Closed Closed

Questions

1. Construct compound statement that correspond to the networks

Solution

The current will flow when all three switches p, q, and r are closed i.e. p ∧ q ∧ r

The required compound statement is P ∧ Q ∧ R

The required component statement is (P ∨ q)

The required compound statement is (p ∧ q) V (r∧ s)

The required compound statement is P V Q V R

The required compound statement is p ∧ (q V (r ∧ s))

The required compound statement is (P ∨ Q ∨ R) ∧ S

2. In electrical network of (ii) find possible switch setting that will allow the current to flow
between T1 and T2

ii) (P ∨ Q) ∧ R

P Q R PVQ (P V Q) ∧ R

T T T T T

T T F T F

T F T T T

T F F T F

F T T T T

F T F T F

F F T F F

F F F F F

Possible switch settings

P Q R

Closed Closed Closed

Closed Open closed

From statements to network

Example Draw a network for the statement (p v Q) ∧ (R ∧ S)

Solutions

Corresponding network is shown below

Questions
Draw network for the following statements

1. [P ∨Q ∧ (R ∧ S)] 2. [(P ∧ Q) ∧ (R V S)]

3. [P V (Q ∧ S) V (R ∧ T)] 4. (Q V (R V S) V P) 5. [P V (Q ∧ (R ∧ S)]
 CHAPTER FIVE

BOOLEAN ALGEBRA AND GRAPH THEORY CONCEPTS IN DESIGNING AND

ANALYZING COMPUTER NETWORKS

5.1 Algebra Operations and Logic Gates (AND, NAND, NOT, OR, NOR, Exclusive OR,
Exclusive NOR Diagrams

A Boolean expression always produces a Boolean value.

A Boolean expression is composed of a combination of the Boolean constants (True or False),
Boolean variables and logical connectives.
Each Boolean expression represents a Boolean function.
Example Z= AB′C is a Boolean expression
Boolean algebra is the branch of algebra in which the values of the variables are the truth
values true and false, usually denoted 1 and 0 respectively
Basic operations
The basic operations of Boolean algebra are as follows:

(i) AND (conjunction), denoted x∧y (sometimes x AND y or xy), satisfies x∧y = 1 if x = y = 1,
and x∧y = 0 otherwise.
(ii) OR (disjunction), denoted x∨y (sometimes x OR y or xy), satisfies x∨y = 0 if x = y = 0, and
x∨y = 1 otherwise.
(iii) NOT (negation), denoted ¬x (sometimes NOT x, x or !x), satisfies ¬x = 0 if x = 1 and ¬x = 1
if x = 0
(iv) EXCLUSIVE OR gate
(v) Exclusive NOR gate
(vi) NAND gate

(i) AND gate

Is said to be 1 if both are 1
Examples A AND B
See table below
Truth Table:
A B X
0 0 0
0 1 0
1 0 0
1 1 1
If both input values are 1, AND returns a 1; otherwise AND returns a 0.
Its diagram
A and B are the input signals and X is the output signal.
Boolean expression: A  B (A AND B)

Logic Diagram:
A
X
B

(ii) NOT (negation) gate

1 if the value is 0 and 0 if the value is 1
Example if A is the statement then negation is NOT A that is ~A
-its truth table is
Truth Table:
A X
0 1
1 0
NOT takes a binary input value and inverts it
Its logical diagram
A is the input signal and X is the output signal.
Boolean expression: X = A'
Logic Diagram:
A X

(iii) OR gate
Is 1 if any of the logical value is 1 otherwise is 0
Truth Table
A B X
0 0 0
0 1 1
1 0 1
1 1 1
If both input values are 0, OR returns 0; otherwise OR returns a 1.

Its logical diagram

A and B are the input signals and X is the output signal.
Boolean expression: A + B (A OR B)
Logic Diagram:
A
X
B

(iv) Exclusive OR gate

Is 0 if both of logical value are 0’s or 1’s otherwise is 1
Truth Table
A B X
0 0 0
0 1 1
1 0 1
1 1 0
If both inputs are the same value, XOR returns a 0; otherwise XOR returns a 1

Logical diagram
A and B are the input signals and X is the output signal.
Boolean expression: A  B (A XOR B)
Logic Diagram:
A
X
B

(v) NAND gate

Is said to be 0 if both of the logical value are 1 otherwise is 1

Its truth tables

Truth Table
A B X
0 0 1
0 1 1
1 0 1
1 1 0
If the inputs are different or both 0, NAND returns a 1; if both are 1, it returns a 0

Its logical diagram

A and B are the input signals and X is the output signal.
Boolean expression: (A  B)’ (NOT (A AND B))
Logic Diagram:
A
X
B
(vi) EXCLUSIVE NOR gate
Is the negation of XOR gate
Truth Table
A B X
0 0 1
0 1 1
1 0 1
1 1 0
If the inputs are both 0, NOR returns a 1; otherwise NOR returns a 0.

Its logical Diagram

A and B are the input signals and X is the output signal.
Boolean expression: (A + B)’ (NOT (A AND B))
Logic Diagram:
A
X
B

QUESTIONS AND ANSWERS

(1) Compare and contrast the AND gate and the NOR gate.
An AND gate produces a 1 as output only if both inputs are 1, whereas a NAND gate
produces a 1 as output in all cases /except/ when both inputs are 1. That is, the AND
and NAND gates produce opposite results. The values produced by one of these gates
can be replicated by inverting the results produced by the other.

(2) Draw and label the symbol for a three input AND gate, then show its
behavior with a truth table.
A B C X
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 0
1 0 0 0
1 0 1 0
1 1 0 0
1 1 1 1
X=A B C

(3) Draw and label the symbol for a three-input OR gate, then show its
behavior with a truth table.
 A
X
B
C

A B C X
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 1
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 1
X=A+B+C

BOOLEAN ARITHMETICS, IDENTITIES AND ALGEBRAIC EXPRESSION

Laws and rules of Boolean algebra expression
S/N Name of the law Rule or Law
1 Commutative laws A+B=B+A
A. B=B.A
2 Associative law (A+B) +C = A+(B+C)
(A.B).C = A. (B.C)

3 Distributive laws A.(B+C) =A. B+A.C

A+ (B.C) =(A+B). (A+C)
4 Sum rules A+0=A
A+1=1
A+A=A
A+A̅=0

5 Product rule A.0=0

A.1=A
A. A=A
̅=0
A. A
6 Absorption rule A+A.B=A
A.(A+B) =A
A+A̅. B= A+B

We have seen how Boolean expressions can be used to express a logic operation mathematically.
We can also use these expressions combined with Boolean theorems to simplify a logic circuit.
The Boolean theorems are grouped into two categories below.
Table 1 lists the single-variable theorems.
Table 2 lists the theorems relating expressions with multiple variables.
Table 3 lists two special multivariable theorems which express how to change an AND
expression to an OR expression and vice versa. De-Morgan’s theorems in Table 3
Note that
AB and A  B are equivalent representations for the AND function. The dot notation is used
below to avoid confusion when combining numbers and variables, ie, to differentiate the
expression x  0 from the variable x0.

1. x 5. x + 0 = x x
0
x
0
0

2. x 1 = x x 6. x + 1 = 1 x
x 1
1 1

3. x  x = x x 7. x + x = x x
x x

4. x  x = 0 x 8. x + x = 1 x
0 1

Table 1: Single-variable Theorems

 9. x + y = y + x 13a. x( y + z ) = xy + xz

10. x  y = y  x 13b. (w + x)( y + z) = wy + xy + wz + xz

11. x + ( y + z) = ( x + y) + z = x + y + z 14. x + xy = x

12. x( yz) = ( xy) z = xyz 15a. x + xy = x + y

15b. x + xy = x + y

Table 2: Multivariable Theorems

16. ( x + y ) = x  y 17. ( x  y ) = x + y

Table 3: De-Morgan’s Theorems

These theorems can be used to simplify expressions as shown in the examples below. In all of
the following examples, we refer to the theorems above by number for simplicity.
Example 1

Simplify the expression z = ABD + ABD to a sum of products (SOP) form.

z = ABD + ABD
z = AB ( D + D) by theorem 13

z = AB (1) by theorem 8

z = AB by theorem 2

 z = AB
Example 2

Simplify the expression z = ( A + B )( A + B ) to a sum of products form.

z = ( A + B )( A + B )

z = AA + AB + BA + BB by theorem 13
 z = 0 + AB + BA + B by theorems 3 and 4

z = B( A + A + 1) by theorem 13

z = B(1) by theorem 6

z=B by theorem 2
z=B
Example 3

Simplify the expression z = ( A + C )  ( B + D ) to a sum of products form.

z = ( A + C )  ( B + D)

z = ( A + C ) + ( B + D ) by theorem 17

z = ( AC ) + ( B D) by theorem 16

z = ( AC ) + ( BD)

 z = AC + BD
Example 4
Determine the output expression of the circuit in Figure 1 and simplify to a sum of products.

A
B
z = A B  C by analysis
C
z
z = A+ B +C by theorem 17

z = A+ B +C
Figure 1: Logic Circuit

 z = A+ B +C
Example 5
Construct a logic circuit for the truth table shown in table1

A B OUTPUT(X)
0 0 0
0 1 1
1 0 1
1 1 0
Table1. Truth table.
Solution
Then the Boolean expression from the above truth table will be taken only when the output (F) is
logic HIGH (1) that is to say, The corresponding Boolean function
F=̅ X. Y+X. ̅
Y
Its logic diagrams

Example 6
Design a logic circuit that has three inputs, A, B, and C, and whose output will be HIGH only
when a two or three of the inputs are HIGH
Solution
Then the truth table will be
A B C Output (X)
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
Then the Boolean Expression will be X = A ̅. B. C + A. B
̅. C + A. B. C̅ + A. B. C
 Then on simplification will have

=A̅ . B. C + A. B
̅. C + A. B. C̅ + A. B. C Given
̅ + A) + A. C. (B
= B. C. (A ̅ + B) + 𝐴. 𝐵(C̅ + C) Distribution
= B. C. (1) + A. C. (1) + 𝐴. 𝐵(1) Sum law
X = B. C + A. C + 𝐴. 𝐵

Thus, the logic circuit

Example 7
Construct truth table of the following logic function ̅+A
Y = AB ̅B .
Solution
The truth table will be
B 𝐴̅ 𝐵̅ 𝐴. 𝐵̅ 𝐴̅. 𝐵 𝐴. 𝐵̅ + 𝐴̅. 𝐵
A
0 1 1 0 0 0
0
1 1 0 0 1 1
0
0 0 1 1 0 1
1
1 0 0 0 0 0
1
Example 8
Draw the truth table and logic circuit of each of the following;
(a) 2 -input AND gate, and
(b) 2 -input OR-gate
Solution
(a) 2-input AND -gate
B A.B = Q
A
0 0
0
1 0
0
0 0
1
1 1
1

(b) 2 input OR gate

B A+B = Z
A
0 0
0
1 1
0
0 1
1
1 1
1