Qualification - BTEC Higher National Diploma in Computing

Unit Name - Discrete Mathematics

Unit Number - Unit 18

Unit Level - Level 5

Assignment Title - Discrete mathematics in software engineering concepts

Learning Outcome 1: Examine set theory and functions applicable to software engineering

Learning Outcome 2: Analyse mathematical structures of objects using graph theory

Learning Outcome 3: Investigate solutions to problem situations using the application of Boolean algebra

Learning Outcome 4: Explore applicable concepts within abstract algebra.

Boost Your Grade With The Best Unit 18 Discrete Mathematics - BTEC Higher National Diploma in Computing Assignment Help!!

Activity 1 -

Part 1 -

1. Let A and B be two non-empty finite sets. If cardinalities of the sets A, B, and A ∩ B are 72, 28 and 13 respectively, find the cardinality of the set A ∪ B.

2. If n(A - B) = 45, n(A ∪ B) = 110 and n(A ∩ B) = 15, then find n(B).

3. If n(A) = 33, n(B) = 36 and n(C) = 28, find n(A ∪ B ∩ C).

Solution:

1. n(AUB) = n(A) + n(B) - n(A∩B) = 72+28-13 = 87
2. n(B) = n(AUB) - n(A∩B)- n(A-B) = 110-45-15 = 50
3. n(AUBUC) = n(A)+n(B)+n(C)-n(A∩B)-n(B∩C)-n(A∩C)+n(A∩B∩C)
= 33+26+28-(a+5)-(b+5)-(c+5)+5
= 33+26+28+5-15-(a+b+c)

n(A) = 33 = 10+5+a+b. So, a+b = 18
n(B) = 36 = 15+5+a+c. So, a+c = 16
n(C) = 28 = 13+5+b+c. So, b+c = 10

2(a+b+c) = 44. Therefore, a+b+c = 22
n(AUBUC) = 33+26+28+5-15-22 = 55

Part 2 -

1. Write the multi-sets of prime factors of given numbers.

I. 160

II. 120

III. 250

2. Write the multiplicities of each element of multisets in part 2(1-I,ii,iii) separately.

3. Find the cardinalities of each multiset in part 2-1.

Solution:

1)
a) A = {2,2,2,2,2,5}
b) A = {2,2,2,3,5}
c) A = {2,5,5,5}

2) a) Multiplicity of 2 = 5, Multiplicity of 5 = 1
b) Multiplicity of 2 = 3, Multiplicity of 3 and 5 = 1
c) Multiplicity of 2 = 1, Multiplicity of 5 = 3

3) Cardinalities = 6,5 and 4

Part 3 -

1. Determine whether the following functions are invertible or not. If it is invertible, then find the rule of the inverse (f-1(x))

2. Function f(x) = 5/9 (x-32) converts Fahrenheit temperatures into Celsius. What is the function for opposite conversion?

Solution:

1.

i) not invertible. Because the function is not one-one. f(5) = f(-5) = 25
ii) invertible.

Let y = f(x). Then, y = 1/x
∴ x = 1/y
∴ f-1(y) = 1/y

iii) invertible.

Let y = f(x). Then, y = x2
∴ x = y1/2
∴ f-1(y) = y1/2

iv) invertible.

Let y = f(x). Then, y = sin x
∴ x = sin-1 y
∴ f-1(y) = sin-1 y

v) invertible.

Let y = f(x). Then y = 2 cos x
∴ cos x = y/2
∴ x = cos-1(y/2)
∴ f-1(y) = cos-1 (y/2)

2. y =5/9 (x-32)
9y = 5(x-32)
9y = 5x - 160
5x = 9y+160
x = (9y+160)/5

The inverse function is g(x) = (9x+160)/5 = (9/5)x + 32

Part 4 -

1. Formulate corresponding proof principles to prove the following properties about defined sets.

i.

A = B <=> A ⊆ B and B ⊆ A

ii. De Morgan's Law by mathematical induction.

iii. Distributive Laws for three non-empty finite sets A, B, and C.

Solution:

1.

i)

Part (a) : If A = B, then A ⊆ B and B ⊆ A

Let x ∈ A. Since A=B, x ∈ B. So, x ∈ B whenever x ∈ A. ∴ A ⊆ B
Let x ∈ B. Since A=B, x ∈ A. So, x ∈ A whenever x ∈ B. ∴ B ⊆ A
From the two above, A ⊆ B and B ⊆ A

Part (b) : If A ⊆ B and B ⊆ A, then A = B

Proof by contradiction :- Assume A ≠ B. Then, it is either the case that there is at least one element in A which is not in B, or there is at least one element in B which is not in A. The first is not possible because A ⊆ B, while the second case is ruled out because B ⊆ A. Hence, A ≠ B cannot hold.

ii)

To prove: (A1 ∩ A2 ∩ A3 ... ∩ An)' = A1' U A2' U ... U An'

Proof by induction on the number of sets n:

Base case: n = 2.
(A1 ∩ A2)' = A1' U A2'

(a) Let x ∈ (A1 ∩ A2)'. Then, x ∉ (A1 ∩ A2).
∴ x ∉ A1 or x ∉ A2
∴ x ∈ A1' or x ∈ A2'
∴ x ∈ A1' U A2'
∴ (A1 ∩ A2)' ⊆ A1' U A2'

(b) Let x ∈ A1' U A2'
Then, x ∈ A1' or x ∈ A2'
∴ x ∉ A1 or x ∉ A2
∴ x ∉ (A1 ∩ A2)
∴ x ∈ (A1 ∩ A2)'
∴ A1' U A2' ⊆ (A1 ∩ A2)'

From (a) and (b), A1' U A2' = (A1 ∩ A2)'. Proof of base case complete.

Induction hypothesis: Assume (A1 ∩ A2 ∩ A3 ... ∩ Ak)' = A1' U A2' U ... U Ak' holds for some k ∈ N

Induction step: To prove : (A1 ∩ A2 ∩ A3 ... ∩ Ak ∩ Ak+1)' = A1' U A2' U ... U Ak' U Ak+1'

LHS = (A1 ∩ A2 ∩ A3 ... ∩ Ak ∩ Ak+1)' = (B ∩ Ak+1)' where B = A1 ∩ A2 ∩ A3 ... ∩ Ak
From base case, LHS = (B ∩ Ak+1)' = B' U Ak+1'
From the definition of B, LHS = ( A1 ∩ A2 ∩ A3 ... ∩ Ak)' U Ak+1'
From induction hypothesis, LHS = (A1' U A2' U ... U Ak') U Ak+1' = A1' U A2' U ... U Ak' U Ak+1'
Hence proved.

iii)

To prove: AU(B∩C) = (AUB)∩(AUC)
(a) To prove: AU(B∩C) ⊆ (AUB)∩(AUC)
Let x ∈ AU(B∩C). Then, x ∈ A or x ∈ B∩C.
x ∈ A or (x ∈ B and x ∈ C)
Case 1: - x ∈ A. Then, x ∈ AUB and x ∈ AUC. So, x ∈ (AUB)∩(AUC)
Case 2: (x ∈ B and x ∈ C), then x ∈ (AUB) because x ∈ B. Also, x ∈ (AUC) because x ∈ C. Therefore, x ∈ (AUB)∩(AUC)

In either case, x ∈ (AUB)∩(AUC) whenever x ∈ AU(B∩C). So, AU(B∩C) ⊆ (AUB)∩(AUC)
(b) To prove: (AUB)∩(AUC) ⊆ AU(B∩C)
Let x ∈ (AUB)∩(AUC). So, x ∈ (AUB) and x ∈ (AUC).

Case 1: x ∈ A. Then, x ∈ AU(B∩C).
Case 2: x ∉ A. Since x ∈ (AUB) and x ∉ A, x ∈ B. Also, since x ∈ (AUC) and x ∉ A, x ∈ C. Therefore, x ∈ B and x ∈ C. So, x ∈ B∩C. Then, x ∈ AU(B∩C).

In either case, x ∈ AU(B∩C) whenever x ∈ (AUB)∩(AUC). So, (AUB)∩(AUC) ⊆ AU(B∩C)
From (a) and (b) above, AU(B∩C) = (AUB)∩(AUC)

Activity 2 -

Part 1 -

1. Discuss using two examples on binary trees both quantitatively and qualitatively.

Solution:

(a) A binary tree can be used to store data in a fashion that makes searching quite fast. Searching can be done in logarithmic time in the average case if data is stored in a binary search tree. For every node in the binary tree, all nodes in its left subtree will store values less than the value of the node, while all nodes in its right subtree will store values greater than the value of the node.

Quantitatively, the time required to search for an element will be defined by the recurrence T(n) = T(n/2) + 0(1)

(b) Another example of a binary tree is to store an arithmetic expression. The operator appears as a node, and its operators are children. For instance, 5X3 will be represented as a node marked X for the operand as the parent, 5 and 3 as the left and right children respectively. Evaluation is then bottom to top, and the value at the root is the value of the expression.

Part 2 -

1. State the Dijkstra's algorithm for a directed weighted graph with all non-negative edge weights.

2. Find the shortest path spanning tree for the weighted directed graph with vertices A, B, C, D, and E given using Dijkstra's algorithm.

Solution:
1. Dijkstra algorithm :-

def RELAX(u, v, w) :
if d[v] > d[u] + w(u, v)
d[v] ← d[u] + w(u, v)
Π[v] ← u // Π[v] = parent of v

def DIJKSTRA(G, w, s) :
for each vertex v ∈ V[G]
d[v] = ∞
Π[v] ← NIL
d[s] = 0

S ← Ø
Q ← V[G]
while Q ≠ Ø
u ← EXTRACT-MIN(Q)
S ← S U {u}
for each vertex v ∈ Adjacency_list [u]
RELAX(u, v, w)
Dijkstra's algorithm, run on a weighted, directed graph G = (V, E) with non-negative weight function w and source s, terminates with d[u] = δ(s, u) for all vertices u ∈ V, where δ(s, u) denotes the shortest distance from s to u. Also, Π[v] = u iff v is the parent of u in the shortest path tree.

2. Starting with E as the source vertex, the shortest distances are d(A) = 5, d(D) = 3, d(B)=8, d(C) =9 and d(E) = 0. Shortest path spanning tree is (E,A),(E,D),(A,C),(A,B)

Part 4 -

1. Construct a proof for the five color theorem for every planar graph.

2. Discuss how efficiently Graph Theory can be used in a route planning project for a vacation trip from Colombo to Trincomalee by considering most of the practical situations (such as millage of the vehicle, etc.) as much as you can. Essentially consider the two fold,

- Routes with shortest distance(Quick route travelling by own vehicle)

- Route with the lowest cost

3. Determine the minimum number of separate racks needed to store the chemicals given in the table (1st column) by considering their incompatibility using graph coloring technique. Clearly state you steps and graphs used.

Solution:

1. Proof by contradiction.

Let G be the smallest planar graph that cannot be colored with five colors.
Let v be a vertex in G that has the maximum degree. Then, deg(v) < 6

Case 1: deg(v) ≤ 4. G-v can be colored with five colors. Since v has degree at most 4, there are at most 4 colors that have been used on the neighbors of v. We can then use the remaining 5th color to color v. So G can be colored with five colors, which is a contradiction.

Case 2: deg(v) = 5. G-v can be colored with 5 colors.
If at least two of the 5 neighbors of v are colored with the same color, then there is at least one color available for v, and the proof is done. So, let us assume that the neighbors of v are colored with 5 different colors - 1,2,3,4,5. Without loss of generality, let us also assume that these are the colors of vertices in the clockwise order.

Consider the vertices in G with colors 1 and 3. If this subgraph of G is disconnected and v1 and v3 are in two different components, then we can easily swap the colors 1 and 3 in the component with v1. This will still be a valid 5-coloring of G-v. Both v1 and v3 will be colored with color 3 now. Now, coloring v with color 1 gives a 5-coloring for G - a contradiction. Therefore both v1 and v3 must lie in the same component in that subgraph, i.e. there exists a path from v1 to v3 such that every vertex on this path is colored with either color 1 or color 3.

Now, consider colors 2 and 4. Take all vertices of G that have color 2 or 4. If v2 and v4 are not on the same connected component then we can swap the colors in the chain starting at v2 and use the remaining color to color v. If v2 and v4 are in the same connected component then there is a path from v2 to v4 in G such that every vertex on it has color 2 or color 4.

Therefore, there must be two edges that cross each other because the colors 1,2,3,4,5 are in clockwise order. This contradicts the assumption - planarity of the graph G. Proof complete.

2. For each pair of cities (u,v) connected by road, let w(u,v) = αd(u,v) + (1-α)c(u,v) where d(u,v) is the actual geographical distance between u and v, c(u,v) is the cost incurred - in dollars - in taking that route, and α is a scalar between 0 and 1. Then, apply the minimum spanning tree algorithm to get the MST of the graph.

3. Create a graph with one node for each chemical. If a chemical is incompatible with another one, add an edge between those nodes. Then, color the graph with the fewest colors possible. Put all chemicals with the same color in the same shelf.

Avail Unmatched Computer Science Assignment Help Service To Stay Ahead Of The Race!!

Activity 3 -

Part 1 -

1. Discuss two real world binary problems in two different fields using applications of Boolean algebra.

Solution:
1. The problem of traffic light signals can be modelled using boolean algebra. Every light is either on or off. Also, lights have to follow certain constraints like they cannot be on at the same time, at least one of them must be on etc. which can be modelled as equations in boolean algebra.

2. An elevator's functioning can be modelled as a problem in boolean algebra. For instance, an elevator should not be both moving and have its door open. It should not be at multiple floors simultaneously. These can be modelled using equations in boolean algebra.

Part 2 -

1. Develop truth tables and its corresponding Boolean equation for the following scenarios.

i. ''If the driver is present AND the driver has NOT buckled up AND the ignition switch is on, then the warning light should turn ON.''

ii. If it rains and you don't open your umbrella then you will get wet.

2. Produce truth tables for given Boolean expressions.

Solution:

(i) Let us define the following boolean variables :

X : driver is present
Y : driver is buckled up
Z : ignition switch is on
A : warning light is on

Truth table is shown below. The corresponding boolean equation is A = XY'Z

X          Y          Z          A

---------------------------------

0          0          0          0

0          0          1          0

0          1          0          0

0          1          1          0

1          0          0          0

1          0          1          1

1          1          0          0

1          1          1          0

ii) Let us define the following boolean variables:

X: it rains, Y: you open your umbrella, Z: you get wet.

Then, the truth table is shown below. The boolean equation is Z = XY'

X          Y          Z

-------------------------

0          0          0

0          1          0

1          0          1

1          1          0

2.

A          B          C          (i)         (ii)

----------------------------------------------

0          0          0          0          0

0          0          1          1          1

0          1          0          1          0

0          1          1          0          1

1          0          0          1          1

1          0          1          0          0

1          1          0          0          1

1          1          1          1          1

Part 3 -

2. Find the simplest form of given Boolean expressions using algebraic methods.

Solution:

(i) A(A+B) + B(B+C) + C(C+A)
= AA+AB+BB+BC+CC+CA
= A+AB+B+BC+C+AC
= A(1+B)+B(1+C)+C(1+A)
= A1+B1+C1 = A+B+C

(ii) (A+B')(B+C) + (A+B)(C+A')
= AB+AC+B'B+B'C+AC+AA'+BC+BA'
= AB+AC+0+B'C+AC+0+BC+A'B
= AB+AC+B'C+BC+A'B
= (AB+A'B) + AC + (B'C+BC)
= B(A+A') + AC + C(B'+B)
= B1 + AC + C1
= B + AC + C
= B+ C(A+1)
= B+ C1
= B + C

(iii) (A+B)(AC+AC')+AB+B
= (A+B)(A(C+C'))+B(A+1)
= (A+B)(A1)+B1
= (A+B)A + B
= AA + BA + B
= A + B + BA
= A + B(1+A)
= A + B1
= A+ B

(iv) A'(A+B) + (B+A)(A+B')
= A'A + A'B + BA + BB' + AA +AB'
= 0 + A'B + BA + 0 + A + AB'
= A'B + AB + A(1+B')
= A'B + AB + A1
= A'B + AB + A
= A'B + A(B+1)
= A'B + A1
= A'B + A

Activity 4 -

Part 1 -

1. Describe the characteristics of different binary operations that are performed on the same set.

2. Justify whether the given operations on relevant sets are binary operations or not.

i. Multiplication and Division on se of Natural numbers

ii. Subtraction and Addition on Set of Natural numbers

iii. Exponential operation: (x, y) → xy on Set of Natural numbers and set of Integers.

Solution:

1. A binary operation on a set A is a function f defined on AXA such that f((a,b)) ∈ A. The binary operation is said to be commutative if f((a,b)) = f((b,a)) for all a,b ∈ A. It is said to be associative if f(f(a,b),c) = f((a,f(b,c))). An element e is said to be the identity of A w.r.t f if f((a,e)) = a = f((e,a)) for all a ∈ A. An element b is said to be the inverse of a if f((a,b)) = e = f((b,a))

2.

(i) Multiplication is a binary operation since the product of any two natural numbers is also a natural number. Division is not a binary operation since the natural numbers are not closed under division.

(ii) The sum of two natural numbers is also a natural number, so + is a binary operation on N. The difference of two natural numbers need not be a natural number, for instance 2-3 = -1 is not in N. Therefore, subtraction is not a binary operation on N.

(iii) Exponentiation is a binary operation on the naturals because mn is a natural number for all m,n in N. It is not a binary operation on the integers because xy need not be an integer if x and y are both integers, for instance 2-3 is not an integer.

Part 2 -

1. Build up the operation tables for group G with orders 1, 2, 3 and 4 using the elements a, b, c, and e as the identity element in an appropriate way.

2. i. State the Lagrange's theorem of group theory.

ii. For a subgroup H of a group G, prove the Lagrange's theorem.

iii. Discuss whether a group H with order 6 can be a subgroup of a group with order 13 or not. Clearly state the reasons.

Solution:

1.

 Order 1 a b c e a e e e e b e e e e c e e e e e e e e e
 Order 2 a b c e a e e e e b e e e e c e e e e e e e e e

2.
For any finite group G, the order (number of elements) of every subgroup H of G divides the order of G.

Proof :

(i) If H is a finite subgroup of a group G and H contains n elements then any right coset of H contains n elements.
Proof: For any element x of G, Hx = {h • x | h is in H} defines a right coset of H. By the cancellation law in the group, each h in H will give a different product when multiplied on the right by x. So, |Hx| = |H|.

(ii) Two right cosets of a subgroup H of a group G are either identical or entirely disjoint.
Proof: Suppose Hx and Hy have an element z in common. Then for some elements h1 and b of H
h1 • x = z = h2 • y
This implies that x = h1-1 z = h1-1 • (h2 • y) = (h1-1 • h2)• y. Lett h3 = h1-1 • h2 . Then, x = h3 • y. This means that every element of Hx can be written as an element of Hy by the correspondence
h • x = (h • h3) • y
for every h in H. ie, if Hx and Hy have a single element in common then every element of Hx is also in Hy. Similarly, we can show that every element of Hy is also in Hx.
Since every element g of G is in some coset, the elements of G can be distributed among H and its right cosets without duplication. So, if k is the number of right cosets and n is the number of elements in each coset, |G| = kn. So, n - the size of the coset, divides |G| - the size of the group.

No, since 6 does not divide 13.

Part 3 -

1. Check whether the set S = R - {-1} is a group under the binary operation '*'defined as a * b = a + b + ab for any two elements a, b ∈ S.

2. i. State the relation between the order of a group and the number of binary operations that can be defined on that set.

ii. How many binary operations can be defined on a set with 4 elements?

3. Discuss the group theory concept behind the Rubik's cube.

Solution:

1. Associativity

a*(b*c) = a*(b+c+bc) = a + (b+c+bc) + a(b+c+bc) = a+b+c+bc+ab+ac+abc
(a*b)*c = (a+b+ab)*c= a+b+ab+c+(a+b+ab)c = a+b+c+ab+ac+bc+abc

0 is the identity element since a*0 = a+0+a.0 = a = 0*a = 0 + a + 0.a

Now, we check whether each element has an inverse. Let a+b+ab=0
a+b(1+a) = 0
b = -a/(1+a)

b exists in the set since a cannot be -1. Now, we will verify that a*b = 0
a*(-a/(1+a)) = a + -a/(1+a) + a.(-a/(1+a)) = (a(1+a) - a - a2)/(1+a) = 0
Similarly, b*a = 0

Therefore, this is a group.
2. (i) If a group G has order m, the cartesian cross product GXG has m2 elements. For each of the m2 ordered pairs, we can choose one of the m elements in G. Therefore, we can have mm*m binary operations.
(ii) 416
3. The central piece on every face is the identity element, it does not change whatever the operation performed on the cube.

Part 4 -

1. Prepare a presentation for ten minutes that explains an application of group theory in computer sciences.

Solution:

Group theory has applications in cryptography. Many cryptosystems are based on group theory. The RSA cryptosystems is one such.

RELATED COURSES & ASSIGNMENT SERVICE!!

 Pearson BTEC Level 7 Certificate in Strategic Management and Leadership (RQF) Digital Electronic Circuits Assignment Help Business Administration BTEC Diploma - Level 1 Assignment Help Software Development Assignment Help Alternative Methods of Construction Assignment Help Level 4 Diploma in Business Administration Assignment Help HND Diploma in Business Enterprise Assignment Help Database Design and Development Assignment Help Strategic Human Resource Management Assignment Help Discuss the importance and dynamics of working within a team Teaching Assistant - Child and Young Individual Development Assignment Help Delivery of Engineering Processes Safely as a Team Assignment Help  #### Are You Looking for Discrete Mathematics Assignment Help?

Looking For High-Quality Unit 18 Discrete Mathematics - Higher National Diploma in Computing Assignment Help Services? Miracleskills.Com Is The Place Where You Need To Be!

 Grading Criteria LO1 : Examine set theory and functions applicable to software engineering P1Perform algebraic set operations in a formulated mathematical problem. P2 Determine the cardinality of a given bag(multiset). M1Determine the inverse of a function using appropriate mathematical technique. D1Formulate corresponding proof principles to prove properties about defined sets. LO2 Analyse mathematical structures of objects using graph theory. P3Model contextualized problems using trees, both quantitatively and qualitatively. P4Use Dijkstra's algorithm to find a shortest path spanning tree in a graph. M2Assess whether an Eularian and Hamiltonian circuit exists in an undirected graph. D2Construct a proof of the Five colour theorem. LO3Investigate solutions to problem situations using the application of Boolean algebra. P5Diagram a binary problem in the application of Boolean Algebra. P6Produce a truth table and its corresponding Boolean equation from an applicable scenario. M3Simplify a Boolean equation using algebraic methods. D3 Design a complex system using logic gates. LO4 Explore applicable concepts within abstract algebra. P7Describe the distinguishing characteristics of different binary operations that are performed on the same set. P8 Determine the order of a group and the order of a subgroup in given examples. M4 Validate whether a given set with a binary operation is indeed a group. D4 Prepare a presentation that explains an application of group theory relevant to your course of study.

Access Our Services for for below mentioned courses like:

• Unit 33 Applied Analytical Models Assignment Help
• Unit 20 Applied Programming and Design Principles Assignment Help
• Unit 26 Big Data Analytics and Visualisation Assignment Help
• Unit 30 Applied Cryptography in the Cloud Assignment Help
• Unit 22 Application Development Assignment Help
• Unit 29 Network Security Assignment Help
• Unit 24 Advanced Programming for Data Analysis Assignment Help
• Unit 32 Information Security Management Assignment Help
• Unit 25 Machine Learning Assignment Help
• Unit 31 Forensics Assignment Help
• Unit 27 Transport Network Design Assignment Help
• Unit 23 Risk Analysis & Systems Testing Assignment Help