Discrete Mathematics Assignment: Number Systems and Logic

This document presents a comprehensive solution to a Discrete Mathematics assignment. The solution begins with number system conversions, including decimal to base 5 and decimal to base 8, and then performs arithmetic operations in hexadecimal and octal. It proceeds to explore logical statements, determining tautologies, contradictions, and equivalencies using truth tables. The assignment delves into set theory, Venn diagrams, and set identities. Furthermore, it covers sorting algorithms (insertion, quicksort, bubble, selection, and merge sort), detailing the steps and comparisons for each. The solution also addresses relations, domains, ranges, and properties like reflexivity, anti-symmetry, and transitivity. Finally, it concludes with graph theory, including adjacency matrices, graph walks, and the construction of a minimum spanning tree using Prim's method, along with the calculation of the tree's cost. Desklib provides this assignment solution, along with other past papers and solved assignments for students.

Running head: DISCRETE MATHEMATICS
DISCRETE MATHEMATICS
Name of the Student
Name of the University
Author Note

1DISCRETE MATHEMATICS
Question 1:
a) (175773)10 to ()5
This can be obtained by dividing the number by 5 and then taking out the remainders in
descending order.
Diviso
r
Dividend Remainder
5 175773 3
5 35154 4
5 7030 0
5 1406 1
5 281 1
5 11 1
5 2 2
0
(175773)10 = (21111043)5
b) (22.5602)10 can be converted to base 8 by dividing the number by 8 and then taking the
remainders.
Diviso
r
Dividend Remainder
8 22 6
2

2DISCRETE MATHEMATICS
product remainder whole
number
0.5602*
8
4.4816 0.4816 4
0.4816*
8
3.8528 0.8528 3
0.8528*
8
6.8224 0.8224 6
0.8528*
8
6.5792 0.5792 6
0.5792*
8
4.6336 0.6336 4
(22.5602)10 = (26.43664)8
ii) (FBCF9)16 + (3AFD7)16
a)
In the hexadecimal addition if the sum is more than F then carry is added to the previous
addition bit.
FBCF9
3AFD7
= 136CD0
b) (5432)8 – (574)8 = (4636)8

3DISCRETE MATHEMATICS
Octal subtraction is like the subtraction in any other number system. Only difference is in the
borrow part, in decimal number system a group of 1010 is borrowed and in octal number
system a group of 810 is borrowed.
c) (110010101)2 X (1100)2
Binary multiplication rules are
0X0 = 0, 1X0 = 0, 0X1 = 0 and 1X1 = 1.
This follows the same multiplication structure of decimal multiplication where each digit of
one number is multiplied with every digit of other number in corresponding one bit shifted
lines and finally all those lines are added.
Hence, (110010101)2 X (1100)2 = (1001011111100)2
Question 2:
i. A compound statement is a tautology if the statement is true irrespective of the truth of
individual statements. Compound statement is a contradiction if the statement is always false
irrespective of the values of individual statements. A compound statement is satisfiable if at
least one truth statement for one or more truth values of the individuals.
In the statement (~𝑎∨~𝑏) ˅ (𝑎∧𝑏) the individual statements are a, b, (~𝑎∨~𝑏) and (𝑎∧𝑏).
In the truth table 1 is considered truth and 0 is considered false.
a b (~𝑎∨~𝑏) (𝑎∧𝑏) (~𝑎∨~𝑏) ˅
(𝑎∧𝑏)
0 0 1 0 1
0 1 1 0 1
1 0 1 0 1

4DISCRETE MATHEMATICS
1 1 0 1 1
Hence, the compound statement is always truth irrespective of the truth of individual
statement and hence the compound statement is a tautology.
ii. (𝑝∨~𝑞)∧(𝑝∧𝑞)≡(𝑝∧𝑞)
Truth table:
p q (𝑝∨~𝑞) (𝑝∧𝑞) (𝑝∨~𝑞)∧(𝑝∧
𝑞)
0 0 1 0 0
0 1 0 0 0
1 0 1 0 0
1 1 1 1 1
Hence, as the two truth tables of (𝑝∧𝑞) and (𝑝∨~𝑞)∧(𝑝∧𝑞) are same so, both expressions
are equivalent.
iii. truth table of statements are given below.
p q r s 𝐩→(𝐪 ^
𝐫)
𝐫→𝐬 𝐬→𝐪 ~𝐩 ∴𝐬
F F F F T T T F
F F F T T T F T
F F T F T F T F
F F T T T T T T

5DISCRETE MATHEMATICS
As in the first row all the premises are true and the conclusion is false hence the argument is
invalid.
iv. Let,
x1 : The weather is not nice today
x2 : its cold outside
x3 : we will go fishing
x4: Then we will go to the Snowy mountains
x5: We will ski there
Question 3:
i.
Total number of subjects = 50.
41 reported relief from at least one of the drugs.
Hence, the number of people relived from none of the drugs = 50 – 41 = 9.
b. number of people relived from three drugs = relived from at least one drug – (relived from
drug A and B + relived from drug A and C + relived from drug B and C) = 41 – (9+14+15) =
41 – 38 = 3 subjects.
c.
Venn diagram:
BA
C
A and B
and C = 3
A and B
= 9
B and C=
15

6DISCRETE MATHEMATICS
d. Number of subjects that only got relief from A = 14 + 9- 21 = 2 subjects.
ii. (Q-P) ∩(R-P) = (𝑸 ∩𝑹)−𝑷
Venn diagram:
Q
Hence, from the above Venn diagram it can be seen that the two areas are the same. Hence,
the two set identities are equal.
Question 4:
The list in the entry order from left to right is the following.
9,3,7,5,2,1.
i. Insertion sort:
Steps comparisons
0 9 3 7 5 2 1 0
1 3 9 7 5 2 1 1
2 3 7 9 5 2 1 2
A and C=
9
P
R
(𝑸 ∩𝑹)−𝑷
(Q-P) ∩(R-P)

7DISCRETE MATHEMATICS
3 3 5 7 9 2 1 3
4 2 3 5 7 9 1 4
5 1 2 3 5 7 9 5
Hence, the total number of comparisons = 0 + 1 + 2 + 3 + 4+ 5 = 15.
ii. quicksort algorithm:
for each (unsorted) partition
set first element as pivot
storeIndex = pivotIndex + 1
for i = pivotIndex + 1 to rightmostIndex
if element[i] < element[pivot]
swap(i, storeIndex); storeIndex++
swap(pivot, storeIndex - 1)
Steps comparisons
0 9 3 7 5 2 1 0

8DISCRETE MATHEMATICS
1 3 7 5 2 1 9 5
2 2 1 3 7 5 9 4
3 1 2 3 5 7 9 4
Hence, total number of comparisons = 5+4+4 = 13.
iii. Bubble sort
do
swapped = false
for i = 1 to indexOfLastUnsortedElement-1
if leftElement > rightElement
swap(leftElement, rightElement)
swapped = true
while swapped
Pass comparisons
0 9 3 7 5 2 1 0
1 3 7 5 2 1 9 5
2 3 5 2 1 7 9 5
3 3 2 1 5 7 9 5
4 2 1 3 5 7 9 5
5 1 2 3 5 7 9 5
Total number of comparisons = 5 + 5 + 5 + 5 +5 =25.
The sorted sequence is 1,2,3,5,7,9.

9DISCRETE MATHEMATICS
iv. Selection sort:
repeat (numOfElements - 1) times
set the first unsorted element as the minimum
for each of the unsorted elements
if element < currentMinimum
set element as new minimum
swap minimum with first unsorted position
Steps comparisons
0 9 3 7 5 2 1 0
1 1 3 7 5 2 9 5
2 1 2 7 5 3 9 4
3 1 2 3 5 7 9 3
Total number of comparisons = 5 + 4 + 3 = 12.
The sorted sequence is 1,2,3,5,7,9.
v. Merge sort:
split each element into partitions of size 1
recursively merge adjacent partitions
for i = leftPartIdx to rightPartIdx
if leftPartHeadValue <= rightPartHeadValue
copy leftPartHeadValue

10DISCRETE MATHEMATICS
else: copy rightPartHeadValue
copy elements back to original array
Merge
sort
Comparison
s Step Parts
0 0
9,3,7,5,2,
1
0 1 9,3,7 5,2,1
0 2 9,3 7 5,2 1
0 3 9 3 7 5 2 1
3 4 3,9 5,7 1,2
3 5 3,5,7,9 1,2
8 6
1,2,3,5,7,
9
Hence, total number of comparisons = 3+3+8 = 14.
In increasing order after merge sorting the sequence will be 1,2,3,5,7,9.
The sorted sequence is 1,2,3,5,7,9.
Question 5:
A = {1, 2, 3, 4, 5,6,7}
Ordered pairs of R = {(1,1),(2,2),(2,5),(3,2),(3,3),(3,4),(3,5),(3,6),(4,4),(4,5),(6,6),(7,1),(7,7)}

11DISCRETE MATHEMATICS
The range of relation R as evident from graph is 1 to 7.
The domain of relation R is 1 to 7.
The relation is reflexive as every point in A is a point in R.
The relation is anti-symmetric as when (x,y) and (y,x) belongs to R then x = y.
The relation R is not transitive as for every (x,y) and (y,x) belongs to R not always x=y. As
an example (3,4) and (4,5) are in R but 3 ≠5.
Hence, as one condition is not satisfied, although two conditions are satisfied, hence R is not
a partial order.
As for every x there are more y values, hence the relation R is not a function.
Question 6:
i.
Required to be proved
f ( a ) =3 a3 – 2a – 6 is O ( a3 )
= ||3a^3|| + ||2a^3|| + ||6a^3||
= 11 a3
Hence, by taking c = 11 and m=1
|3 a3 – 2a – 6|≤11 a3
|3 – 2 – 6| <= 11 a3 – 5≤11a3
Hence, f(a) is O ( a3 )
ii. Required to be proved