Discrete Mathematics

Assignment - 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.

Assignment Brief:

Activity 01

Part 1

Question 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^-1 (x) using appropriate mathematical technique.

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.

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.

Part 4

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

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.

Part 3
1. Simplify the following Boolean expressions using algebraic methods.

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.

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 = R -{-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)