Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Foundation of Maths (1) > Final Exam > Flashcards

Final Exam Flashcards

1
Q

What is the disjoint union ⊔?

A

Is the union of A and B when A ∩ B = ∅. i.e. A and B are disjoint.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What is the output of the Euclidean Algorithm?

A

the gcd

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is the gcd?

A

If m and n are non-zero integers, then the largest integer which is a common divisor of both m and n is called the greatest common divisor of m and n.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Define integer division.

A

The integer d is said to divide the integer a if
a = d . t for some integer t.
d is a divisor of a
a is a multiple of d

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Define common divisor.

A

d is said to be the common divisor of integer m and n if d | m and d | n

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Informal defenition of sets.

A

A set is a collection of objects. The objects of a set are called the elements of the set.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Define the extensionality principal.

A

Two sets are equal iff they have the same elements.
i.e. S = T iff x ∈ S implies x ∈ T and x ∈ T implies x ∈ S

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Define subset.

A

A set T is a subset of a set S if every element of T is also an element of S.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Define proper subset. Give the symbol.

A

T is a proper subset of S if T is a subset of S and T is not equal to S.
⊊

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What does it mean to say two sets A and B are disjoint?

A

A ∩ B = ∅

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is the notation for the set theoretic difference?

A

A \ B

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What is a set?

A

A set is determined completely by its elements.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is the null set?

A

A set with no elements

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Give the 5 logical laws of sets.

A

x ∈ A ∪ B iff x ∈ A or x ∈ B.
x ∈ A ∩ B iff x ∈ A and x ∈ B.
x ∈ A \ B iff x ∈ A and x ∉ B.
A ⊂ B iff x ∈ A implies x ∈ B.
A = B iff x ∈ A implies x ∈ B and x ∈ B implies x ∈ A

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What is the notation for restricted comprehension?

A

{x ∈ S | c(x)} ⊆ S

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What is unrestricted comprehension, why is this a problem?

A

This is when we drop the requirement that x ∈ S. This leads to problems as Ω := {x | x is a set not containing itself} tells us that Ω ∈ Ω and Ω ∉ Ω which is a contradiction. The element Ω cannot be both in the set and out of it.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What rule prevents unrestricted comprehension?

A

Axiomatic Rules for Set Theory. A set cannot be an element of itself. x ∉ x always.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

What is U?

A

The ambient set containing all possibilities. So for every A ⊂ U, we can define A^c = U \ A.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

What is a proposition?

A

Is a declarative sentence that is either true or false.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

What is the symbol for XOR?

A

⊕

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Define logical equivalence.

A

Two compound propositions are logically equivalent if their equivalence is a tautology under all possible assignments of truth values to their prime propositions.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

What are the two absorption laws?

A

(P ^ Q) v Q = Q
(P v Q) ^ Q = Q

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

What is the role for the part P and the part Q in P implies Q.

A

P is the hypothesis
Q is the conclusion

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

What is the equivalence law?

A

P <-> Q = (P -> Q) ^ (Q -> P)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

What is the converse of P -> Q?

A

Q -> P

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

What is a Mersenne Prime?

A

A prime of the form (2^n) - 1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

What is iff? Split it in two and give the names of each part.

A

If and only if is an equivalence relation.
Hence P <-> Q is the same as
P -> Q ^ Q->P
P -> Q is the ONLY IF part and means it is NECESSARY that Q is true for P to be true.
Q -> P is the IF part and means it is SUFFICIENT that Q is true for P.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

Create a predicate to represent the fact that the square of any real number is non-negative.

A

∀x ∈ R : x^2 >= 0

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

Create a predicate to represent the fact that 16 is a square integer.

A

∃n ∈ Z : n^2 = 16

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

What is the truth set of P (on S)?

A

{x ∈ S | P(x) }
All the elements of S that satisfy the predicate P.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

Translate the following predicates into truth sets.
P(x) ^ Q(x)
P(x) v Q(x)
¬P(x)
P(x) ^ ¬Q(x)
P(x) ⊕ Q(x) (Give another name for this one)

A

A ∩ B
A ∪ B
A^c = U \ A
A ∩ B^c = A \ B
(A ∪ B) \ (A ∩ B) = (A \ B) ∪ (B \ A) (Symmetric Sum)

where A = {x ∈ U | P(x)}
B = {x ∈ U | Q(x)}

32
Q

Constant Rule for summation.

A

n sum k = m (c . ak) = c (n sum k = m (ak) )

33
Q

Sum Rule for summation.

A

n sum k = m (ak + bk) is equivalent to
(n sum k = m (ak) ) +
(n sum k = m (bk) )

34
Q

Sum of a constant rule.

A

n sum k = m (c) is equivalent to
(n - m + 1)c

35
Q

Sum of numbers between 1 and n.

A

n (n + 1) / 2

36
Q

Sum of numbers between 1^2 and n^2. (n sum k=1 (k^2) )

A

n(n + 1)(2n + 1) / 6

37
Q

Rule for shifting delimiters.
Apply this rule to 30 sum k=15 (2k + 3)

A

l + s sum n = k + s (A(n-s))
is equivalent to
l sum n=k (An)

Also should add a new variable i = n + s

E.g. = 16 sum i=1 (2i + 31) where i is equal to k - 14.

38
Q

Rule for geometric sum.
(n sum k=0 (a^k))

A

a^(n+1) - 1 / (a - 1)

39
Q

Is a sum i=1 b sum j=1 (2i + 3j)
the same as b sum j=1 a sum i=1 (2i + 3j)?

A

Yes

40
Q

Rule for nested sums with products.

A

n sum i=1 (Ai) * m sum j=1 (Bj)

n sum i=1 m sum j=1 (Ai)(Bj)

41
Q

Explain the three principles of positivity.

A

Trichotomy: for every real x, exactly one of the following is true x > 0, x = 0, -x > 0.
Closedness: the sum and the product of positive numbers is positive.
Archimedean Axiom: For every real number x, there exists an integer n such that n - x is positive.

42
Q

What is the strictly less than sign?

A

<

43
Q

Define binary relation?

A

A binary relation on a set S is a predicate P(x, y) with x, y free variables ranging over S.

44
Q

Define total order.

A

A total order <= on a set is a binary relation such that all the following holds.
Reflexivity: For all s elements of S, s <= s
Anti-Symmetry: For all s and t elements of S, [s <= t ^ t <= s ] -> s = t
Transitivity: For all s, t and u elements of S, [s <= t ^ t <= u] -> (s <= u)
Strong Connectedness: For all s and t elements of S, (s <= t) v (t <= s).

45
Q

What bracket is used for (a) less than and equal to range and (b) less than range

A

[ is inclusive
( is exclusive

46
Q

|2x + 3| <= 5. Expand the inequality.

A

-5 <= 2x + 3 <= 5

46
Q

Should infinity be included for infinite intervals. How should the range of an infinite set be described?

A

No.
(-∞, ∞) := R

47
Q

Define a function.

A

Let A and B be two sets, A function f from A to B assigns to every element a ∈ A a unique element f(a) ∈ B.

48
Q

Define extensionality for functions.

A

Two functions f: A -> B and g: X -> Y are considered to be equal iff,
A = X (same domains)
B = Y (same codomains)
For all a ∈ A f(a) = g(a) (Same results)

49
Q

Define the image of a function f: A -> B.

A

Is the set im(f) ;= {b ∈ B | ∃a ∈ A : f(a) = b} = {f(a) ∈ B | a ∈ A} ⊂ B

50
Q

Condition for surjectivity.

A

im(g) = codom(g)

51
Q

Define a real function.

A

A -> B is a real function if A ⊂ R and B ⊂ R

52
Q

Define the natural domain.

A

The natural domain D(f) of an algebraic formula f(x) is the set of real numbers x for which f(x) evaluates to a unique real number.

53
Q

What are the four essential laws for finding the solutions to inequalities?

A

ab = 0 <-> a = 0 v b = 0
a/b = 0 <-> a = 0 ^ b != 0
ab > 0 <-> (a > 0 ^ b > 0) v (a < 0 ^ b < 0) <-> a/b > 0
ab < 0 <-> (a > 0 ^ b < 0) v (a < 0 ^ b > 0) <-> a/b < 0

54
Q

What does A subset B imply?

A

(x ∈ A) -> (x ∈ B)

55
Q

What is |a| < b?

A

-b < a ^ a < b

56
Q

What is |a| > b?

A

a > b v -a>b

57
Q

Define injective. Give another name.
Explain it.

A

A function is said to be injective if for all a1 and a2 elements of the domain. f(a1) = f(a2) implies a1 = a2.

Also called ‘one to one’

Two different inputs yield different outputs.

58
Q

Define surjective. Give another name. Explain it.

A

A function is said to be surjective if for all b elements of codomain, some a exists where f(a) = b.

Also called ‘onto’.

Im(f) = codom(f)

59
Q

What is the co-restriction to an arbitrary function f:A -> B?

A

f~ : A –> im(f)

Makes the arbitrary function always surjective.

60
Q

Define bijective. Explain it.

A

A function is bijective if it is both surjective and injective.

All inputs map to exactly one output. All outputs are mapped to by exactly one input. One to one correspondence.

61
Q

Under what condition can two function f and g be made into composites?

A

codom(f) = dom(g)

62
Q

Define composities.

A

For functions f and g where codom(f) = dom(g). g ∘ f is the composite or g(f(x))

63
Q

Define the identity function.

A

For any set S, the identity function on S is just the function. ids : S –> S

64
Q

Define inverse function.

A

f: A –> B and g: B –> A
For all a elements of A : g(f(a)) = a
For all b elements of B : f(g(b)) = b

65
Q

Describe the graph of 2^x.
Describe the differences in the graphs of 3^x and (1/2)^x

A

Intercepts the y-axis at y=1, slopes downward to the left.

3^x has a steeper slope down to the left, is smaller at values below 0 and greater above.

(1/2)^x is the reflection of 2^x through the y-axis and slopes down to the right.

66
Q

Describe the graph of log2(x). Describe the differences between the graph of log5(x).

A

log2(x) intercepts the x axis at x=1. It slopes from high values of y to low values of y without crossing the y-axis.

log5(x) intercepts the same but is steeper as it slopes from high y-values to low y-values.

67
Q

Expand (a1 * a2)^x

A

a1^x * a2^x

68
Q

State the change of bases rule in logarithms.

A

loga(y) = logb(y) / logb(a)

69
Q

What is the floor of x?

A

The largest integer less or equal to x.

70
Q

What is the ceiling of x?

A

The smallest integer greater or equal to x

71
Q

How many decimal digits does a positive integer have?

A

floor(log10(n)) + 1

72
Q

What is the highest power of p dividing N!?

A

floor(N/p) + floor(N/p^2)+ floor(N/p^3) + ….

73
Q

How many multiples of m are there among 1 to N integers.

A

floor(N/m)

74
Q

What does the lower limit need to be to sum a geometric sum a^k?

A

n=0

Foundation of Maths (1) (1 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions