Analysis of GCD, Set Theory, and Lexicographic Order in Mathematics

Verified

Added on 2024/07/22

AI Summary

This mathematics assignment delves into several core concepts, starting with the computation of the Greatest Common Divisor (GCD) and its properties for co-prime numbers. It then explores set theory, simplifying expressions using De Morgan's Laws and Venn diagrams, and includes defining set operations. The assignment further examines functions between sets, their connections to power sets, and determining the number of possible functions and relations. Finally, it investigates lexicographic order, listing elements in lexicographic order and defining relations based on string membership in a language, with detailed solutions and justifications provided for each problem, demonstrating a comprehensive understanding of these mathematical principles. Desklib offers more solved assignments and study tools for students.

Contents
List of figure.............................................................................................................................. 1
Introduction............................................................................................................................. 2
1...............................................................................................................................................3
2...............................................................................................................................................4
3...............................................................................................................................................5
4...............................................................................................................................................8
Conclusion................................................................................................................................ 9
References.............................................................................................................................. 10
List of figure
Figure 1 Possible connections.................................................................................................. 6
1

Paraphrase This Document

Need a fresh take? Get an instant paraphrase of this document with our AI Paraphraser

Introduction
This report is prepared on mathematics concepts in which various laws are used related to set
theory. The first part determines the concept of GCD (Greatest Common Divisor) which
provides a highest common factor of values or pair of values. The second part determines the
concept of set theory and some De Morgan Laws which help to simplify the conditions. The
third part explains the concept of Venn diagram and some function concepts. The last part
examines the concept of lexicographic order which determines the relation among the
strings.
2

1. (a) Compute gcd(132, 84).
Solution:
Factors of 132 = 2 * 2 * 3 * 11
Factors of 84 = 2 * 2 * 3 * 7
Common factors = 2 * 2 * 3 = 12
132 = 12 * 11
84 = 12 * 7
Hence, gcd(132, 84) is 12.
(b) Suppose a, b ∈ N are co-prime. What is gcd(a, a + b)?
Solution:
If a and b are natural co-prime numbers then gcd(a, a+b) always becomes 1.
Because the set of co-prime number always has 1 same factor which is 1.
For example, a = 10 = 2 * 5
B = 21 = 3 * 7
In this example, both values doesn’t have any same factor which determines gcd is 1.
Gcd(a, a+b) = gcd(10, 10 + 21) = gcd(10,31) = 1 because 2 natural numbers are co-prime then
their product never contain any common prime number.
Hence, gcd(a,a+b) = 1 (Niven, Zuckerman & Montgomery, 2013).
3

2. For sets A and B, define A * B to be (AUB)c (the complement of AUB).
(a) Simplify (A * B) * (A * B). Justify your answer (e.g. using a Venn diagram or some other
technique).
Solution:
(A * B) * (A * B) = ((AUB)C)*((AUB)C) taking complement of individual sets and * change into
union.
= ((AUB)C U (AUB)C)C taking the complement of the whole by De-Morgan law
= ((AUB)C)C ∩ ((AUB)C)C changing the whole set in the intersection by De-Morgan law
= (AUB) ∩ (AUB) change by set theory and Boolean algebra
=A U B is the answer (Ali, Feng, Liu, Min & Shabir, 2009).
(b) Express Ac using A and *. Justify your answer.
Solution:
Ac = (A U ϕ)C according to set theory,
Which gives A * ϕ.
Its justification proved this as A * ϕ = (A U ϕ)C which implies Ac.
Hence, Ac gives A * ϕ (Kunen, 2014).
(c) Express A \ B using A, B, and *. Justify your answer.
Solution:
(A ∩ B) = (AC U BC)C these are the 2 complements when you see on Venn diagram.
= (A * A) * (B * B) is the answer.
Justification:
AC = A*A
BC = B * B
4

Paraphrase This Document

Need a fresh take? Get an instant paraphrase of this document with our AI Paraphraser

3. (a) List all functions f: {a, b, c} → {0,1 }.
Solution:
There are 8 possible functions as:
 f(Z) = 0 -> f(a) = f(b) = f(c) = 0
 f(Z) = 1 -> f(a) = f(b) = f(c) = 1
 f(a) = f(b) = 0, f(c) = 1
 f(a) = f(c) = 0, f(b) = 1
 f(a) = 0, f(b) = f(c) = 1
 f(a) = f(b) = 1, f(c) = 0
 f(a) = 1, f(b) = f(c) = 0
 f(a) = f(c) = 1, f(b) = 0
(b) Describe a connection between your answer for (a) and Pow({a, b, c}).
Solution:
On the basis of (A) part, values are 0 and 1. Pow(a, b, c) can relate to (a) part in terms of 2n
which is 23 = 8
Hence, pow(a, b, c)= ({a, b, c}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, , {}) (Wilkinson, 2012).
5

Figure 1 Possible connections
(c) In general, if card(A) = m and card(B) = n, how many:
(i) Functions are there from A to B?
Solution:
In this question, there are 2 given sets which are A and B.
It implies: (A) = m and (B) = n.
In this part, need to find functions which are from A to B.
6

Suppose A = {A1, A2, A3 …., An}
Similar to B = {B1, B2, B3, ….., Bn}
Take a function (f) which is assigned to A as ax in which B as by = then f(ax) of B.
According to the rule of n * n till n-times which gives nx possible terms.
Hence, the possibilities of A element are n terms.
Moreover, a function from A to B is nx.
(ii) Relations are there between A and B?
Solution:
According to above part, we supposed Suppose A = {A1, A2, A3 …., An}
Similar to B = {B1, B2, B3, ….., Bn}.
It shows that total relation between A and B are 2(x * y)
In which x is for A elements and y for B elements.
Hence, 2|A * B| are 2(x) * (y) which gives 2xy.
Moreover, the relation between a and b are 2xy.
7

Paraphrase This Document

Need a fresh take? Get an instant paraphrase of this document with our AI Paraphraser

4. Let _ = fa; bg and L = fw 2 __ : 3jlength(w)g.
(a) List the elements of L_3 in lexicographic order.
De_ne R _ __ _ __ as follows: (w;w0) 2 R if there is a v 2 __ such
that: either wv 2 L and w0v =2 L, or wv =2 L and w0v 2 L. For example
(a, bbb) 2 R because for v = _, av = a =2 L and bbbv = bbb 2 L. On the
other hand, (a; b) =2 R because for any v 2 __, length(av) = length(bv);
so whenever av 2 L, bv 2 L and vice-versa.
(b) Which of the following are elements of R:
(i) (abab; baba)?
(ii) (ab; abab)?
(iii) (_; b)?
(iv) (_; bb)?
(v) (_; bbb)?
Solution:
a. The elements of L<=3 up to 3 or 3 which are in lexicographic order. In this λ doesn’t
contain any value in the string because of empty string which makes its length = 0.
So it is divisible by 3. The list contains 8 strings and one empty string which are as
follows:
1. λ
2. aaa
3. bbb
4. aab
5. bba
6. abb
7. baa
8. aba
9. bab
b.
Solution:
1. Elements of R in (abab, baba) is 0 because of (a, b) are not element (∉) of R relation. It is
possible because of the same size of strings which implies len(ab) = len(ba).
However, ab is elements of lexicographic order and ba also as well. In this, aba and bab are
the part of the lexicographic list (Mateva & Topalova, 2009).
2. (ab, abab) are the elements (∈) of R relation because of aba are the elements in
lexicographic list and ababa are not the part of the list.
3. (λ, b) is the element of R relation because of aa belongs to lexicographic list which gives
λaa to aa aren’t an element of list and baa are the part of the list.
4. (λ, bb) isn’t an element of R relation because of a ∉ R and bba are the elements of the list.
5. (λ, bbb) aren’t an element of R relation because of b ∉ R and bbb are the elements of the
lexicographic list.
8

Conclusion
This report concludes that the concepts of mathematics are used in terms of set theory,
functions, Venn diagram, and lexicographic order. The set theory concepts help to solve or
simplify the functions by using some laws like De Morgan Law. The functions and Venn
diagram are determined in the third part which help to find the possible values or
connections. The lexicographic order determines the relation on comparing with the list of
strings.
9

References
 Mateva, Z.T. and Topalova, S.T., 2009. Line spreads of PG (5, 2). Journal of
Combinatorial Designs, 17(1), pp.90-102.
 Ali, M.I., Feng, F., Liu, X., Min, W.K. and Shabir, M., 2009. On some new operations in
soft set theory. Computers & Mathematics with Applications, 57(9), pp.1547-1553.
 Kunen, K., 2014. Set theory an introduction to independence proofs (Vol. 102).
Elsevier.
 Wilkinson, L., 2012. Exact and approximate area-proportional circular Venn and Euler
diagrams. IEEE transactions on visualization and computer graphics, 18(2), pp.321-
331.
 Niven, I., Zuckerman, H.S. and Montgomery, H.L., 2013. An introduction to the theory
of numbers. John Wiley & Sons.
10

1 out of 10

Analysis of GCD, Set Theory, and Lexicographic Order in Mathematics

Paraphrase This Document

Paraphrase This Document

Paraphrase This Document

Related Documents

Foundations of Mathematics: Week 1 Homework Assignment - Fall 2019

+13062052269

info@desklib.com

Analysis of GCD, Set Theory, and Lexicographic Order in Mathematics

Paraphrase This Document

⊘ This is a preview!⊘

Paraphrase This Document

⊘ This is a preview!⊘

Paraphrase This Document

⊘ This is a preview!⊘

Related Documents

Foundations of Mathematics: Week 1 Homework Assignment - Fall 2019

+13062052269

info@desklib.com