Discrete Mathematics Hasitha

Higher Nationals
Internal verification of assessment decisions – BTEC (RQF)

INTERNAL VERIFICATION – ASSESSMENT DECISIONS
Programme title BTEC Higher National Diploma in Computing
Ms. Nuwani Ranasinghe

Assessor Internal Verifier
Unit 18 : Discrete Mathematics
Unit(s)
Discrete mathematics in software engineering concepts
Assignment title
J.V.H.S.Jayasekara
Student’s name
List which assessment Pass Merit Distinction
criteria the Assessor has
awarded.
INTERNAL VERIFIER CHECKLIST
Do the assessment criteria awarded match

those shown in the assignment brief? Y/N
Is the Pass/Merit/Distinction grade awarded

justified by the assessor’s comments on the Y/N
student work?
Has the work been assessed
Y/N
accurately?
Is the feedback to the student:
Give details:
• Constructive?
Y/N
• Linked to relevant assessment
criteria? Y/N
• Identifying opportunities for

improved performance? Y/N
• Agreeing actions? Y/N
Does the assessment decision need

Y/N
amending?
Assessor signature Date
Internal Verifier signature Date

Programme Leader signature(if
Date
required)
Unit 18 :Discrete Mathematics J.V.H.S.Jayasekara COL/E-010204

1
Confirm action completed
Remedial action taken
Give details:
Assessor signature Date
Internal Verifier
Date
signature
Programme Leader
Date
signature (if required)
2
Higher Nationals - Summative Assignment Feedback Form
Student Name/ID J.V.H.S.Jayasekara COL/E-010204
Unit Title Unit 18 : Discrete Mathematics
Assignment Number 1 Assessor Ms. Nuwani Ranasinghe

21/03/2022 Date Received 1st
Submission Date
submission
Date Received 2nd
Re-submission Date
submission
Assessor Feedback:
LO1 Examine set theory and functions applicable to software engineering.
Pass, Merit & Distinction P1 P2 M1 D1

Descripts
LO2 Analyse mathematical structures of objects using graph theory.

Descripts
LO3 Investigate solutions to problem situations using the application of Boolean algebra.
Descripts
LO4 Explore applicable concepts within abstract algebra.

Descripts
Grade: Assessor Signature: Date:
Resubmission Feedback:
Grade: Assessor Signature: Date:
Internal Verifier’s Comments:
Signature & Date:

* Please note that grade decisions are provisional. They are only confirmed once internal and external moderation has taken place and grades decisions have
been agreed at the assessment board.
3
Pearson
Higher Nationals in
Computing
Unit 18 : Discrete Mathematics
4
General Guidelines
1. A Cover page or title page – You should always attach a title page to your assignment. Use previous page as
your cover sheet and make sure all the details are accurately filled.
2. Attach this brief as the first section of your assignment.
3. All the assignments should be prepared using a word processing software.
4. All the assignments should be printed on A4 sized papers. Use single side printing.
5. Allow 1” for top, bottom , right margins and 1.25” for the left margin of each page.
Word Processing Rules
1. The font size should be 12 point, and should be in the style of Time New Roman.
2. Use 1.5 line spacing. Left justify all paragraphs.
3. Ensure that all the headings are consistent in terms of the font size and font style.
4. Use footer function in the word processor to insert Your Name, Subject, Assignment No, and Page Number
on each page. This is useful if individual sheets become detached for any reason.
5. Use word processing application spell check and grammar check function to help editing your assignment.
Important Points:
1. It is strictly prohibited to use textboxes to add texts in the assignments, except for the compulsory information.
eg: Figures, tables of comparison etc. Adding text boxes in the body except for the before mentioned
compulsory information will result in rejection of your work.
2. Carefully check the hand in date and the instructions given in the assignment. Late submissions will not be
accepted.
3. Ensure that you give yourself enough time to complete the assignment by the due date.
4. Excuses of any nature will not be accepted for failure to hand in the work on time.
5. You must take responsibility for managing your own time effectively.
6. If you are unable to hand in your assignment on time and have valid reasons such as illness, you may apply (in
writing) for an extension.
7. Failure to achieve at least PASS criteria will result in a REFERRAL grade .
8. Non-submission of work without valid reasons will lead to an automatic RE FERRAL. You will then be asked to
complete an alternative assignment.
9. If you use other people’s work or ideas in your assignment, reference them properly using HARVARD
referencing system to avoid plagiarism. You have to provide both in-text citation and a reference list.
10. If you are proven to be guilty of plagiarism or any academic misconduct, your grade could be reduced to A
REFERRAL or at worst you could be expelled from the course
5
Student Declaration
I hereby, declare that I know what plagiarism entails, namely to use another’s work and to present it as my own
without attributing the sources in the correct way. I further understand what it means to copy another’s work.
1. I know that plagiarism is a punishable offence because it constitutes theft.

2. I understand the plagiarism and copying policy of the Edexcel UK.
3. I know what the consequences will be if I plagiaries or copy another’s work in any of the assignments for this
program.
4. I declare therefore that all work presented by me for every aspects of my program, will be my own, and where
I have made use of another’s work, I will attribute the source in the correct way.
5. I acknowledge that the attachment of this document signed or not, constitutes a binding agreement between
myself and Pearson, UK.
6. I understand that my assignment will not be considered as submitted if this document is not attached to the
attached.
Student’s Signature: Date:

[email protected] 21/03/2022
6
Feedback Form
Formative feedback: Assessor to Student
Action Plan
Summative feedback
Feedback: Student to Assessor
Assessor’s
Date
Signature
Student’s
Date
Signature
7
Assignment Brief
Student Name /ID Number J.V.H.S.Jayasekara COL/E-010204
Unit Number and Title Unit 18: Discrete Mathematics
Academic Year 2021/22
Unit Tutor Unit 18 :Discrete Mathematics
Assignment Title Discrete mathematics in Computing
Issue Date
Submission Date
IV Name & Date
Submission Format:
This assignment should be submitted at the end of your lesson, on the week stated at the front of this
brief. The assignment can either be word-processed or completed in legible handwriting.
If the tasks are completed over multiple pages, ensure that your name and student number are present
on each sheet of paper.
Unit Learning Outcomes:
LO1 Examine set theory and functions applicable to software engineering.
LO2 Analyse mathematical structures of objects using graph theory.
LO3 Investigate solutions to problem situations using the application of Boolean algebra.
LO4 Explore applicable concepts within abstract algebra.
8
Assignment Brief and Guidance:
9
Activity 01
Part 1
1. Perform algebraic set operations in the following formulated mathematical problems.
i. 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 .
ii. If n( A  B )=45, n( A  B )=110 and n( A B )=15, then find n(B).
iii.If n(A)=33, n(B)=36 and n(C)=28, find n( A  B  C ).
Part 2
1. Write the multisets (bags) of prime factors of given numbers.
i. 160
ii. 120
iii. 250
2. Write the multiplicities of each element of multisets (bags) in Part 2-1(i,ii,iii) separately.
3. Determine the cardinalities of each multiset (bag) in Part 2-1(i,ii,iii).
Part 3
1. Determine whether the following functions are invertible or not and if a function is invertible,
 
then find the rule of the inverse f  x  using appropriate mathematical technique.
1
i. f :     ii. f :     
f ( x)  x 2 f ( x)  1
x
iii. f :  
 
iv.  2 2

f :   ,    1, 1
f ( x)  x 2 f ( x)  sin x
v. f : 0 ,     2, 2
f ( x)  2 cos x
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.
10
Activity 02
Part 1
1. Model two contextualized problems using binary trees both quantitatively and qualitatively.
Part 2
1. State the Dijkstra’s algorithm for a directed weighted graph with all non-negative edge
weights.
2. Use Dijkstra’s algorithm to find the shortest path spanning tree for the following weighted
directed graph with vertices A, B, C, D, and E given. Consider the starting vertex as E.
Part 3
1. Assess whether the following undirected graphs have an Eulerian and/or a Hamiltonian cycle.
i.
11
ii.
iii.
Part 4
1. Construct a proof of the five color theorem for every planar graph.
12
Activity 03
Part 1
1. Diagram two real world binary problems in two different fields using applications of Boolean
Algebra.
Part 2
1. Produce 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.
i. 𝐴̄𝐵̄ 𝐶 + 𝐴𝐵̄ 𝐶̄ + 𝐴𝐵𝐶 + 𝐴̄𝐵𝐶̄
ii. (𝐴 + 𝐵̄ + 𝐶)(𝐴 + 𝐵 + 𝐶)(𝐴̄ + 𝐵 + 𝐶̄ )
Part 3
1. Simplify the following Boolean expressions using algebraic methods.
i. 𝐴(𝐴 + 𝐵) + 𝐵(𝐵 + 𝐶) + 𝐶(𝐶 + 𝐴)
ii. (𝐴 + 𝐵̄ )(𝐵 + 𝐶) + (𝐴 + 𝐵)(𝐶 + 𝐴̄)
iii. (𝐴 + 𝐵)(𝐴𝐶 + 𝐴𝐶̄ ) + 𝐴𝐵 + 𝐵
iv. 𝐴̄(𝐴 + 𝐵) + (𝐵 + 𝐴)(𝐴 + 𝐵̄ )
Part 4
1. Consider the K-Maps given below. For each K- Map
i. Write the appropriate standard form (SOP/POS) of Boolean expression.
ii. Design the circuit using AND, NOT and OR gates.
iii. Design the circuit only by using
 NAND gates if the standard form obtained in part (i) is SOP.
 NOR gates if the standard form obtained in pat (i) is POS.
(a)
AB/C 0 1
00 0 0
01 0 1
11 0 1
10 1 0
13
(b)
AB/CD 00 01 11 10
00 1 0 0 1
01 0 1 0 1
11 1 1 1 0
10 1 1 1 1
(c)
AB/C 0 1
00 1 0
01 1 1
11 1 0
10 0 1
14
Activity 04
Part 1
1. Describe the distinguishing characteristics of different binary operations that are performed on the
same set.
Part 2
1. Determine 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 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.
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.
Part 3
1. Validate whether the set S    {1} is a group under the binary operation ‘*’defined as
a * b  a  b  ab for any two elements a, b  S .
Part 4
1. Prepare a presentation for ten minutes to explore an application of group theory relevant to
your course of study. (i.e. in Computer Sciences)
15
Grading Rubric
Grading Criteria Achieved Feedback
LO1 : Examine set theory and functions applicable to software

engineering.
P1 Perform algebraic set operations in a formulated mathematical

problem.
P2 Determine the cardinality of a given bag (multiset).
M1 Determine the inverse of a function using appropriate

mathematical technique.
D1 Formulate corresponding proof principles to prove properties

about defined sets.
LO2 : Analyse mathematical structures of objects using graph
theory.
P3 Model contextualized problems using trees, both quantitatively

and qualitatively.
P4 Use Dijkstra’s algorithm to find a shortest path spanning tree in a
graph.
M2 Assess whether an Eulerian and Hamiltonian circuit exists in an

undirected graph.
D2 Construct a proof of the Five colour theorem.

16
LO3 : Investigate solutions to problem situations using the
application of Boolean algebra.
P5 Diagram a binary problem in the application of Boolean Algebra.
P6 Produce a truth table and its corresponding Boolean equation

from an applicable scenario.
M3 Simplify a Boolean equation using algebraic methods.
D3 Design a complex system using logic gates.
LO4 : Explore applicable concepts within abstract algebra.
P7 Describe 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 Explore with the aide of a prepared presentation the application

of group theory relevant to your course of study
17
Acknowledgement
All praise and blessing are due to the creator of mankind and all that exists, for His
blessings, and guidance at every stage of my life. For the successful completion of this
assignment, I needed the help and guidelines of some respected person, who deserves my
greatest gratitude. The completion of this assignment gives me much pleasure. I wish to
thank the officials and other staff members who rendered their help during the period of
my study.
Thank you.
Yours’s sincerely,
Hasitha
18
1. Activity 01
1.1 Part 1
1.1.1 Question1
Perform algebraic set operations in the following formulated mathematical problems.
i. 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
ii. If n (A-B) = 45, n(A U B) =110 and n(A ∩ B) =15, then find n(B)
19
iii. If n(A)=33, n(B)=36 and n(C)=28, find n( A B C ).
20
1.2. Part 2
1.2.1. Question1
Write the multisets (bags) of prime factors of given numbers.
Multiset of 160 of prime factors = [2,2,2,2,2,5]

Multiset of 120 of prime factors = [2, 2, 2, 3, 5]
Multiset of 250 of prime factors=2,5,5,5]
1.2.2. Question2
Write the multiplicities of each element of multisets (bags) in Part 2-1(i,ii,iii) separately.
1. 160 = [2, 2, 2, 2, 2, 5]
Multiplicity of 2 = 5
2. 120 = [2, 2, 2, 3, 5]
3. 250 = [2, 5, 5, 5]
21
1.2.3. Question3
Determine the cardinalities of each multiset (bag) in Part 2-1(i, ii, iii).
i.) A = {2, 2, 2, 2, 2, 5}, n(A) = 6

ii.) A = {2, 2, 2, 3, 5}, n(A) = 5
iii.) A = {2, 5, 5, 5}, n(A) = 4
1.3. Part 3
1.3.1. Question1
Determine whether the following functions are invertible or not and if a function is
invertible, then find the rule of the inverse  f x  using appropriate mathematical
1
technique.
i. f :    ii. f :   
f ( x)  x 2 f ( x)  1
x
iii. f :    iv.  2 2

f :   ,    1, 1
f ( x)  x 2 f ( x)  sin x
v. f : 0 ,     2, 2
f ( x)  2 cos x
i.
22
ii.
This function is not surjective and injective. Therefore the function has an
inverse function.
iii.
23
iv.
This function is not subjective and this function is invertible.

Therefore, this function has an inverse function.
y = sin x
x = sin -1
f -1 (x) = sin -1 (x)
24
v.
This function is not subjective and this function is invertible.

Therefore, this function has an inverse function.
y = 2 cos x
cos x = y/2
f -1 (x) = cos-1 (x/2)
25
1.4. Part 4
1.4.1. Question1
Formulate corresponding proof principles to prove the following properties about defined
sets.
i. A  B  A  B and B  A
Suppose we want to show A = B. If we show A ⊆ B, then every element of A is also in
B, but there's still a chance that B has some elements that aren't in A, so we can't infer
A = B. But if we additionally nor B ⊆ A, then B cannot contain anything that is not in
A, so A = B.
ii. De Morgan’s Law by mathematical induction.

Complement of the Intersection Equals the Union of the Complements
Let P = (A ∩ B)' and Q = A' U B'
Let x be an arbitrary element of P then x ∈ P ⇒ x ∈ (A ∩ B)'
⇒ x ∉ (A ∩ B)
⇒ x ∉ A or x ∉ B
⇒ x ∈ A' or x ∈ B'
⇒ x ∈ A' U B'
⇒x∈Q
Therefore, P ⊂ Q …………….. (i)
Again, let y be an arbitrary element of Q then y ∈ Q ⇒ y ∈ A' ∩ B'
⇒ y ∈ A' and y ∈ B'
⇒ y ∉ A and y ∉ B
⇒ y ∉ (A U B)
⇒ y ∈ (A U B)'
⇒y∈P
26
Therefore, Q ⊂ P …………….. (ii)
Now combine (i) and (ii) we get;
P=Q
(A U B)' = A' ∩ B'
iii. Distributive Laws for three non-empty finite sets A, B, and C.
Using the Indirect Method

Let A, B, C be sets. If A ⊆ B and B ∩ C = ∅, then A ∩ C = ∅
If we assume the conclusion is false and we obtain a contradiction --- then the theorem
must be true.
Assume A ⊆ B and B ∩ C = ∅ , and A ∩ C ≠ ∅ . To prove that this cannot occur, let

x∈A∩C.
x ∈ A ∩ C ⇒ x ∈ A and x ∈ C ⇒ x ∈ B and x ∈ C ⇒ x ∈ B ∩ C
But this contradicts the second premise. Hence, the theorem is proven.
27
2. Activity 02
2.1. Part 1
2.1.1 Question1
Model two contextualized problems using binary trees both quantitatively and qualitatively.
A binary tree is a tree-like structure that is rooted and in which each vertex has at most two
children and each child of a vertex is designated as its left or right child.
Binary tree example in quantitative
Blumensath and Davies (2009) and Baraniuk et al. (2010), the wave coefficients showing
the structure of the radial tree can be retrieved from the signals using a specially adapted
compression sensor algorithm from n = O (k) measurements. K is the signal change.
Motivated by these results, we present a simplified proportional dimensional asymptotic
framework. This allows quantitative evaluation of recovery guarantees for compact tree-
based sensing. In the case of Gaussian matrices, this framework is applied to the current
worst-case analysis of iterative tree projection (ITP) using tree based restricted isometry
property (RIP). Within the same framework, obtain quantitative results based on a new
analysis method that takes into account the fixed points of the algorithm. By taking
advantage of the factual mean condition that the measurements are statistically signal-
independent, significant quantitative improvements can be obtained compared to the tree-
based RIP analysis. And the result is a brief update description that clearly identifies the
number of measurements required as a scatter multiplier. For example, the accurate
recovery of the binary tree-based signal by Gaussian measurement shows that virtually no
noise is virtually guaranteed with the steady-state ITP provided with the n≥50k. All the
results extend to the most realistic situation where the measurements are corrupted by noise.
(Point, 2020).
28
Binary tree example in qualitative
When two alternative therapies (A and B) are available, some patients' subgroups may show
better outcomes for a compared to A, but the opposite for other subgroups. In this case,
there is qualitative communication with the subset (for example imbalance). Such an
interaction would mean that certain subgroups of patients should be treated differently and
therefore related to personal care. For randomized clinical trial data that include the
characteristics of many patients who interact with treatment in a complex way, an
appropriate statistical method is still not available to detect treatment qualitative
interactions between subgroups.
As an exit, this paper proposes a new method called the Qualitative Interaction tree
(QUINT) for this purpose. QUINT produces a binary tree that divides the patient into
surrounding nodes based on patient characteristics. These nodes are assigned to one of three
categories: the first is better than the A, the second is better than the B, and the third option
has no difference in treatment type. The simulated data QUINT results showed satisfactory
performance in terms of improvement and recovery. The results applied to the real data
show that QUINT provided a clearer picture of the qualitative interactions in the data
compared to the other methods. (Point, 2020).
29
2.2. Part 2
2.2.1 Question1
State the Dijkstra’s algorithm for a directed weighted graph with all non-negative edge
weights.
Dijkstra's algorithm takes care of the shortest-path problem for any weighted, coordinated
diagram with non-negative loads. It can handle graphs made up of cycles, but negative
loads will cause this calculation to give incorrect results. Hence, here we accept w(e) ≥ 0
for all E. The pseudocode in the algorithm below shows Dijkstra's algorithm. The algorithm
maintains a priority queue minQ which is used to store the raw vertices with their shortest
path estimates est(v) as key values. It then repeatedly extracts from minQ the vertex u that
has the minimum est(u) and relaxes all edges falling from u to any vertex in minQ. After a
vertex is extracted from minQ and all relaxations through it are complete, the algorithm
treats that vertex as processed and does not touch it again. Dijkstra's algorithm either stops
when minQ is empty or when each node has been examined exactly once.
2.2.2 Question2
Use Dijkstra’s algorithm to find the shortest path spanning tree for the following weighted
directed graph with vertices A, B, C, D, and E given. Consider the starting vertex as E.
30
Shortest path to D : E to D =3
Shortest path to A : E to A =5
Shortest path to B : E to D to B =7
Shortest path to C : E to A to C =9 or E to D to C=9
31
2.3. Part 3
2.3.1 Question1
Assess whether the following undirected graphs have an Eulerian and/or a Hamiltonian
cycle.
EULER PATH is a path that uses every edge in a graph with no repeats. Being a path, it
does not have to return to the starting vertex.
EULER CIRCUIT is a circuit that uses every edge in a graph with no repeats. Being a
circuit, it must start and end at the same vertex.
EULER’S PATH AND CIRCUIT THEOREMS

A graph will contain an Euler path if it contains at most two vertices of odd degree. A
graph will contain an Euler circuit if all vertices have even degree.
1.
vertices A and C have degree 4, B is degree 2, D is degree 3, and E is degree 1. This graph
contains two vertices with odd degree (D and E) and three vertices with even degree (A, B,
and C),
Then Euler’s theorems tell us this graph has an Euler path, but not an Euler circuit
32
Figure 1-Solution for Question1 of part 2.3
We can see that once we travel to vertex E there is no way to leave without returning to C,
so there is no Hamiltonian circuit. If we start at vertex E we can find several
Hamiltonian paths, such as ECDAB and ECABD.
2.
Regarding this graph vertices A, C, D and E have degree 3, B is degree 2. This graph
contains four vertices with odd degree (A, C, D and E) and one vertices with even degree
(B),
Then Euler’s theorems tell us this graph has no Euler path or Euler circuit
In the graph, there is a Hamiltonian circuit. If we start at vertex B we can go through the
{B, C, D, E, A, B} with no repeat. We can find a Hamiltonian cycle.
33
3.
Regarding this graph vertices A, C and D have degree 2, B and E is degree 3. This graph
contains two vertices with odd degree (A and E) and three vertices with even degree (A, C,
D) Then Euler’s theorems tell us this graph has an Euler path, but not an Euler circuit
so there is no Hamiltonian circuit. If we start at vertex A we can find several

Hamiltonian paths, such as ABCED and AECBD. If we start at vertex C we can find
another several Hamiltonian paths, such as CBAED, CEABD, CBDEA, CEDBA.
34
2.4. Part 4
2.4.1 Question1
Construct a proof of the five color theorem for every planar graph.
Theorem: Every planar graph with n vertices can be colored with at most 5 colors.
Proof by induction, we induce over n the number of vertices in a planar graph G.
Base case, P(n≤5): Since there are ≤5 nodes in G, the graph can be colored with 5 colors.
Inductive step, P(n+1): Suppose P(n)
P(n) is true, i.e. for every planar graph with n vertices we have to show P(n).
P(n) is true.
We know that every planar graph has a vertex with deg(v)≤5. We call this knot in our v
Graph G. Remove v and for the remaining subgraph G′ we can assume P(n).
If deg(v)≤4, we can color all vertices adjacent to v with 4 colors and use color 5 for coloring
v itself to achieve valid coloring.
If deg(v)=5, we assume that all vertices adjacent to v are colored differently.
So proven.
35
3. Activity 03
3.1. Part 1
3.1.1 Question1
Diagram two real world binary problems in two different fields using applications of
Boolean Algebra.
Example 1
Payment method whether to pay using cash or card option.
B C X B → Pay with Bills

C→ Pay with cash
0 0 0
Output X→ Payment done
0 1 1
X=!BC+B!C+BC
1 0 1
1 1 1
Example 2
Coffee Machine Decanter with choices for Hot coffee and Ice coffee.
H I X
H → Pay with Bills
0 0 0 I→ Pay with cash
Output X→ Served chosen
0 1 1
X=H!I+!HI
1 0 1
1 1 0
36
3.2. Part 2
3.2.1 Question1
Produce 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.
A B C F A – Driver is Present
0 0 0 0 B – Buckled Up
C – Ignition Switch ON
0 0 1 0 F – Warning Light
0 1 0 0
F= A and !B and C
0 1 1 0
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 0
ii. If it rains and you don't open your umbrella, then you will get wet.
A B F A-Raining
B-Open umbrella
F-Getting wet
0 0 0 F=A and !B
0 1 0
1 0 1
1 1 0
37
3.2.2 Question2
Produce truth tables for given Boolean expressions.

i. 𝐴̄𝐵̄ 𝐶 + 𝐴𝐵̄ 𝐶̄ + 𝐴𝐵𝐶 + 𝐴̄𝐵𝐶̄ =F
A B C 𝐴̄ 𝐵̄ 𝐶̄ 𝐴̄𝐵̄ 𝐶 𝐴𝐵̄ 𝐶̄ 𝐴𝐵𝐶 𝐴̄𝐵𝐶̄ F
0 0 0 1 1 1 0 0 0 0 0
0 0 1 1 1 0 1 0 0 0 1
0 1 0 1 0 1 0 0 0 1 1
0 1 1 1 0 0 0 0 0 0 0
1 0 0 0 1 1 0 1 0 0 1
1 0 1 0 1 0 0 0 0 0 0
1 1 0 0 0 1 0 0 0 0 0
1 1 1 0 0 0 0 0 1 0 1
ii. (𝐴 + 𝐵̄ + 𝐶)(𝐴 + 𝐵 + 𝐶)(𝐴̄ + 𝐵 + 𝐶̄ ) =F
A B C 𝑨̄ 𝑩̄ 𝑪̄ (𝑨 + 𝑩̄ + 𝑪) (𝑨 + 𝑩 + 𝑪) (𝑨̄ + 𝑩 + 𝑪̄) F
0 0 0 1 1 1 1 0 1 0
0 0 1 1 1 0 1 1 1 1
0 1 0 1 0 1 0 1 1 0
0 1 1 1 0 0 1 1 1 1
1 0 0 0 1 1 1 1 1 1
1 0 1 0 1 0 1 1 0 0
1 1 0 0 0 1 1 1 1 1
1 1 1 0 0 0 1 1 1 1
38
03.3. Part 3
3.3.1 Question1
Simplify the following Boolean expressions using algebraic methods.
i. 𝐴(𝐴 + 𝐵) + 𝐵(𝐵 + 𝐶) + 𝐶(𝐶 + 𝐴)
ii. (𝐴 + 𝐵̄ )(𝐵 + 𝐶) + (𝐴 + 𝐵)(𝐶 + 𝐴̄)
39
iii. (𝐴 + 𝐵)(𝐴𝐶 + 𝐴𝐶̄ ) + 𝐴𝐵 + 𝐵
iv. 𝐴̄(𝐴 + 𝐵) + (𝐵 + 𝐴)(𝐴 + 𝐵̄ )
40
3.4. Part 4
3.4.1 Question1
Consider the K-Maps given below. For each K- Map
i. Write the appropriate standard form (SOP/POS) of Boolean expression.

ii. Design the circuit using AND, NOT and OR gates.
iii. Design the circuit only by using
 NAND gates if the standard form obtained in part (i) is SOP.
 NOR gates if the standard form obtained in pat (i) is POS.
a)
i.
41
ii.
SOP
POS
42
iii.
43
44
b)
45
46
47
48
c)
49
50
For NOR gate POS
51
4. Activity 04
4.1. Part 1
4.1.1 Question1
Describe the distinguishing characteristics of different binary operations that are performed
on the same set.
Basically, binary operations on a set are calculations that combine two elements of the set
(called operands) to produce another element of the same set.
The binary operation, (say *) on a non-empty set A are functions from A × A to A.
*: A × A → A∗:A×A→A
It is an operation of two elements of the set whose domains and co-domain are in the
same set. Closure property: An operation * on a non-empty set A has closure property, if,
a ∈ A, b ∈ A ⇒ a * b ∈ A
Properties of Binary operation on a set A are as follows:
Closure Property:
A binary operation * on a non-empty set P has closure property, if a ∈ P, b ∈ P ⇒ a * b

∈ P. For example, addition is a binary operation that is closed on natural numbers,
integers, and rational numbers.
Associative Property:
The associative property of binary operations holds if, for a non-empty set S, we
can write (a * b) *c = a*(b * c), where {a, b, c} ∈ S. Suppose Z be the set of integers and
multiplication be the binary operation. Let, a = -3, b = 5, and c = -16. We can write (a ×
b) × c = 240 = a × (b × c).
Commutative Property:
A binary operation * on a non-empty set S is commutative, if a * b = b * a, for all
(a, b) ∈ S. Suppose addition be the binary operation and N be the set of natural numbers.
Let, a = 4 and b = 5, a + b = 9 = b + a.
Identity:
A non-empty set P with a binary operation * is said to have an identity e ∈ P, if e*a
= a*e= a, ∀ a ∈ P. Here, e is the identity element.
52
Inverse:
A non-empty set P with a binary operation * is said to have an inverse element, if a * b =

b * a = e, ∀ {a, b, e}∈P. Here, a is the inverse of b, b is the inverse of a and e is the
identity element.
Distributive:
Let * and # be two binary operations defined on a non-empty set S. The binary operations
are distributive if, a* (b # c) = (a * b) # (a * c), for all {a, b, c} ∈ S. Suppose * is the
multiplication operation and # is the subtraction operation defined on Z (set of integers).
Let, a = 3, b = 4, and c = 7. Then, a*(b # c) = a × (b − c) = 3 × (4 − 7) = -9. And, (a * b) #
(a * c) = (a × b) − (a × c) = (3 × 4) − (3 × 7) = 12 − 21 = -9. Therefore, a* (b # c) = (a * b)
# (a * c), for all {a, b, c} ∈ Z.
Cancellation:
Consider a non-empty set A, and a binary operation * on A. Then the operation * has the
cancellation property, if for every a, b, c ∈A, we have
a*b=a*c⇒b=c [left cancellation]
b*a=c*a⇒b=c [Right cancellation]
Important Notes on Binary Operation
 Not all binary operations hold associative and commutative properties.

 A binary operation can be understood as a function f (x, y) that applies to two
elements of the same set S, such that the result will also be an element of the set S.
53
4.2. Part 2
4.2.1 Question1
Determine 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.
We denote by * an operation of the group G. We point out that the group cannot have any
elements of order 3. We note that the general number of possible definitions of the
operation * on the group G is less than 9. As an example: * can be defined as follows:
* e a b c
e e a b c
a a e c b
b b c a e
c c b e a
The latter table is for the group of order 4. Note that if we only consider the first row and
the first column we get a table for the group of order 1, and if we consider the first two
rows and columns keeping this, we get a table of order 2. It is not possible to get a table
for a group of order 3 from the table for a group of order 4. Therefore, we present a table
for a group of order 3 separately:
* e a b
e e a b
a a b e
b b e a
54
4.2.2 Question2
i. State the relation between the order of a group and the number of binary operations
that can be defined on that set.
There are n elements in the set and binary operation i. The 2 operations can be applied to
each of them in relationships, hence the total number of combinations will be.
𝑛(𝑛−1)
𝑛 𝑛−1 2 1+2+⋯.𝑛
2 .2 …2 .2 = 2 = 2 2
ii. How many binary operations can be defined on a set with 4 elements?
= 24(4-1)/2 = 26 = 64
4.2.2 Question3
i. State the Lagrange’s theorem of group theory.
Lagrange theorem is one of the central theorems of abstract algebra. It states that
in group theory, for any finite group say G, the order of subgroup H of group G
divides the order of G. The order of the group represents the number of elements.
Lagrange Theorem Statement

As per the statement, the order of the subgroup H divides the order of the group G. This
can be represented as;
|G| = |H|
Before proving the Lagrange theorem, let us discuss the important terminologies and
three lemmas that help to prove this theorem.
55
ii. For a subgroup H of a group G, prove the Lagrange’s theorem.
Lagrange Theorem Proof
Let H be any subgroup of the order n of a finite group G of order m. Let us consider the
cost breakdown of G related to H.
Now let us consider each coset of aH comprises n different elements.
Let H = {h1,h2,…,hn}, then ah1,ah2,…,ahn are the n distinct members of aH.
Suppose, ahi=ahj⇒hi=hj be the cancellation law of G.
Since G is a finite group, the number of discrete left cosets will also be finite, say p. So,
the total number of elements of all cosets is np which is equal to the total number of
elements of G. Hence, m=np
p = m/n
This shows that n, the order of H, is a divisor of m, the order of the finite group G. We
also see that the index p is also a divisor of the order of the group.
Hence, proved, |G| = |H|

(byjus)
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.
According to the theory, that subgroup order divides group order. But 6 does not
divide 13, so a group of order 13 cannot have a subgroup of order 6. Subgroups can
only have order 1 or 13 as 13 is a prime.
56
4.3. Part 3
4.3.1 Question1
Validate whether the set S    {1} is a group under the binary operation ‘*’defined as
a * b  a  b  ab for any two elements a, b  S .
a b = a + b +ab a b = a + b + ab (from definition of binary operation) b a = b + a + b a =

a + b + ab b a = b + a + ba = a + b + ab(since addition and multiplication of nos is
commutative) therefore a b = b a a b = b a (operation is commutative) a (b c) = (a b) ca
(b c) = (a b) c a (b c)=a+b+c+bc+ab+ac+abca (b c)=a+b+c+bc+ab+ac+abcand (a b)
c=a+b+c+ab+bc+ac+ abc(a b) c=a+b+c+ab+bc+ac+abc (since addition and
multiplication of nos is commutative) therefore a (b c) = (a b) ca (b c)=(a b) c
(associative property satisfied) Such that a x = a a x = a and x a = a x a = a now on
solving a x = a a x = a (a + x + ax = aa + x + ax = a on solving above equation we get
x(a+1)=0x(a+1)=0 a+1a+1 can’t we 0 because aa belongs to Q−{−1}Q-{-1} if (a+1) is 0
then aa is -1 which is not possible. therefore, xx is 0. Similarly, from x a = a x a = a xx
is 0.i.e identity element is o.(zero).
57

Discrete Mathematics Hasitha

Uploaded by

Copyright:

Available Formats

Discrete Mathematics Hasitha

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Discrete Mathematics Hasitha

Uploaded by

Copyright:

Available Formats

Higher Nationals

Internal verification of assessment decisions – BTEC (RQF)

Ms. Nuwani Ranasinghe

Do the assessment criteria awarded match

Is the Pass/Merit/Distinction grade awarded

• Identifying opportunities for

• Agreeing actions? Y/N

Does the assessment decision need

Internal Verifier signature Date

Unit 18 :Discrete Mathematics J.V.H.S.Jayasekara COL/E-010204

Assessor signature Date

Unit 18 :Discrete Mathematics J.V.H.S.Jayasekara COL/E-010204

Assignment Number 1 Assessor Ms. Nuwani Ranasinghe

LO1 Examine set theory and functions applicable to software engineering.

Pass, Merit & Distinction P1 P2 M1 D1

LO2 Analyse mathematical structures of objects using graph theory.

Pass, Merit & Distinction P3 P4 M2 D2

LO4 Explore applicable concepts within abstract algebra.

Grade: Assessor Signature: Date:

Grade: Assessor Signature: Date:

Internal Verifier’s Comments:

Signature & Date:

Unit 18 :Discrete Mathematics J.V.H.S.Jayasekara COL/E-010204

Unit 18 :Discrete Mathematics J.V.H.S.Jayasekara COL/E-010204

Word Processing Rules

Unit 18 :Discrete Mathematics J.V.H.S.Jayasekara COL/E-010204

1. I know that plagiarism is a punishable offence because it constitutes theft.

Student’s Signature: Date:

Unit 18 :Discrete Mathematics J.V.H.S.Jayasekara COL/E-010204

Formative feedback: Assessor to Student

Feedback: Student to Assessor

Unit 18 :Discrete Mathematics J.V.H.S.Jayasekara COL/E-010204

Student Name /ID Number J.V.H.S.Jayasekara COL/E-010204

Unit Number and Title Unit 18: Discrete Mathematics

Academic Year 2021/22

Unit Tutor Unit 18 :Discrete Mathematics

Assignment Title Discrete mathematics in Computing

IV Name & Date

Unit Learning Outcomes:

LO1 Examine set theory and functions applicable to software engineering.

LO2 Analyse mathematical structures of objects using graph theory.

LO4 Explore applicable concepts within abstract algebra.

Unit 18 :Discrete Mathematics J.V.H.S.Jayasekara COL/E-010204

Unit 18 :Discrete Mathematics J.V.H.S.Jayasekara COL/E-010204

Unit 18 :Discrete Mathematics J.V.H.S.Jayasekara COL/E-010204

Unit 18 :Discrete Mathematics J.V.H.S.Jayasekara COL/E-010204

Unit 18 :Discrete Mathematics J.V.H.S.Jayasekara COL/E-010204

Unit 18 :Discrete Mathematics J.V.H.S.Jayasekara COL/E-010204

Unit 18 :Discrete Mathematics J.V.H.S.Jayasekara COL/E-010204

Unit 18 :Discrete Mathematics J.V.H.S.Jayasekara COL/E-010204

Grading Criteria Achieved Feedback

LO1 : Examine set theory and functions applicable to software

P1 Perform algebraic set operations in a formulated mathematical

P2 Determine the cardinality of a given bag (multiset).

M1 Determine the inverse of a function using appropriate

D1 Formulate corresponding proof principles to prove properties

P3 Model contextualized problems using trees, both quantitatively

M2 Assess whether an Eulerian and Hamiltonian circuit exists in an

D2 Construct a proof of the Five colour theorem.

P5 Diagram a binary problem in the application of Boolean Algebra.

ab=ac⇒b=c [left cancellation]

ba=ca⇒b=c [Right cancellation]