Discrete Maths Flashcards
Natural numbers
Counting numbers
e.g. 0,1,2,3,4,5,…
Denoted by ‘N’
Prime numbers
A natural number is prime if it has exactly two distinct factors. Itself, and 1
Integers
Whole numbers. All natural numbers as well as negatives.
e.g. …,-3,-2,-1,0,1,2,3,…
Denoted by ‘Z’
Rational numbers
Numbers which can be expressed as a decimal fraction.
e.g. 1/2, 3/4, 1/4… - Not pi, 2^0.5
Denoted by ‘Q’ (quotient)
Irrational numbers
Opposite of rational, can’t be expresseed as decimal fraction.
e.g. pi, 2^0.5 (root 2)…
Real numbers
Numbers which are not imaginary (All numbers we would use to quantify)
Denoted by ‘R’
Set, members and elements
A set is defined in terms of its members. It is the result of considering certain elements together (e.g. set of natural numbers). An element can be any entity of any kind
The set of odd numbers less than 10
1,3,5,7,9
What does ‘x ∈ A’ mean?
The element x is a member of the set A
∈ with a diagonal line through it means ‘is not a member of’
Equality of sets
When 2 sets have the exact same elements.
P: The set of odd numbers between 2 and 8
Q: The set of prime factors of 105
For both, the elements are 3,5,7, hence P=Q.
The exact definition is:
‘X = Y ’ means that, for every x, x ∈ X if and only if x ∈ Y
In other words, two sets are equal so long as every element is either a member of both of them
or a member of neither of them
The null set
A set with no members,
e.g. P = The set of unicorns in the London zoo.
Q = The set of prime numbers between 114 and 126.
P=Q so there is only one set with no members, the null set.
Denoted by ‘∅’
Subsets
The set of prime numbers between 10 and 100 is part of the set of odd numbers between 10 and 100. A part of a set in this sence is called a ‘subset’.
‘X ⊆ Y ’ means that X is a subset of Y
The exact definition is:
‘X ⊆ Y ’ means that for any element x, if x ∈ X then x ∈ Y .
Proper subsets
The subsets of a set include the set itself (X ⊆ X), but if we have a subset not equal to the set itself, it is a proper subset, e.g. X ⊂ Y
‘X ⊂ Y ’ means that X ⊆ Y and X != Y
This means that ‘X ⊆ Y ’ is equivalent to ‘X ⊂ Y or X = Y ’.
Defining sets
We use the template {x | . . . } to denote the set of all elements x such that . . .
For example, the set of odd numbers between 10 and 20 would be represented as
{x | x is odd and 10 < x < 20}
Alternatively you could just write {11,13,15,17,19}
{x | x ∈ S and x has φ} = {x ∈ S | x has φ}.
Intersection
X ∩ Y = {x | x ∈ X and x ∈ Y }
Elements which are members of both listed sets are in the intersection (∩) of the 2.
{2, 4, 6, 8, 10} ∩ {2, 3, 4, 5, 6} = {2, 4, 6}.
Rules from intersection definition
- X ∩ Y ⊆ …
- X ⊆ Y if and only if X ∩ Y = …
- X ∩ ∅ = …
- X ∩ X = …
- X ∩ Y = Y ∩ … (i.e., ∩ is a commutative operation)
- X ∩ (Y ∩ Z) = (X ∩ Y ) ∩ … (i.e., ∩ is an associative operation)
- X ∩ Y ⊆ X
- X ⊆ Y if and only if X ∩ Y = X.
- X ∩ ∅ = ∅.
- X ∩ X = X
- X ∩ Y = Y ∩ X (i.e., ∩ is a commutative operation)
- X ∩ (Y ∩ Z) = (X ∩ Y ) ∩ Z (i.e., ∩ is an associative operation)
Union
Any element of either set.
X ∪ Y = {x | x ∈ X or x ∈ Y }
{2, 4, 6, 8, 10} ∪ {2, 3, 4, 5, 6} = {2, 3, 4, 5, 6, 8, 10}
More the 2 sets - format
B = A1 ∩ A2 ∩ A3 ∩ A4 ∩ A5
or B = ^5 ∩ i = 1 Ai
Disjoint sets
Disjoint sets have no intersection (mutually exclusive)
X and Y are disjoint if and only if X ∩ Y = ∅.
Pairwise disjoint
Any 2 of 3+ sets are disjoint
X ∩ Y = X ∩ Z = Y ∩ Z = ∅
If 2 of the sets are not disjoint, the sets are not pairwise disjoint
Union and intersection can be used together. Answer card has example
‘So long as the next card drawn is either a king or an ace, and also either a club or a diamond,
then I shall win.’ In other words, I shall win if the next card is in the set
(K ∪ A) ∩ (C ∪ D)
Distributive laws
Like multiplying out brackets
X ∩ (Y ∪ Z) = (X ∩ Y ) ∪ (X ∩ Z)
X ∪ (Y ∩ Z) = (X ∪ Y ) ∩ (X ∪ Z)
Set difference
D = {x | x drives a car}
L = {x | x has a valid licence}
To find law breakers we want members of set D who are not members off set L, and this is denoted D \ L
X \ Y = {x | x ∈ X and x /∈ Y }
{2, 4, 6, 8, 10} \ {2, 3, 4, 5, 6} = {8, 10}
Proofs from definition of difference
- X \ Y ⊆ X
- (X \ Y ) ∩ Y = ∅
- X \ Y = ∅ if and only if X ⊆ Y
- X \ (Y ∩ Z) = (X \ Y ) ∪ (X \ Z)
- X \ (Y ∪ Z) = (X \ Y ) ∩ (X \ Z)
Power set
All the subsets of a set
e.g. The power set of {1, 2, 3} is the set
{∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}
Definition : ℘(X) = {Y | Y ⊆ X}
‘Y ∈ ℘(X)’ = ‘Y ⊆ X’.
Cardinality of a set
The cardinality of a set is the number of elements it contains.
|{1, 3, 5, 6, 8, 12, 15, 18}| = 8
Singleton Set
A set with a cardinality of 1
Finite and infinite sets - difference
For any finite set X, if Y ⊂ X, then |Y | < |X|,
‘the whole is greater than any of its parts’
Not true for infinite sets
Power of infinite sets
|℘(X)| > |X|
Strings
Given a set X, a string over X is a finite sequence of elements each of which is a member of X.
Alph = {a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z},
Empty string
Unique string of length 0, denoted by ‘Λ’
|Λ| = 0
String-set
The set of all strings over X is called the string-set of X, and is denoted ‘X’. So long as X contains at least one member, X will be infinite
{a}* = {Λ, a, aa, aaa, aaaa, aaaaa, aaaaaa, aaaaaaa, . . .}
a^0 = Λ, a^1 = a,
{a}* = {a^n | n ∈ N}.
{0, 1}* =
{0, 1}∗ = {Λ, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, 101, 110, 111, 0000, . . .}
X^+ =
X^+ = X* \ {Λ}.
(Alph^+)
The set without the Λ
X∗ = X+ ∪ {Λ}
What is a function
Mapping from one set to another.
1 |→ 1
3 |→ 9
6.3 |→ 39.69
Function - Domain
Inputs!
(set of possible inputs)
f : D → C
Function - Codomain
Outputs!
(set of possible outputs)
f : D → C
Square function acting on natural number inputs to produce natural number outputs
square : R → R
Notation for functions that take 2 inputs such as ‘add’
add : R × R → R
Combine the two inputs into a single input.
The set of ordered pairs of elements from the set S is the
Cartesian product S × S. Thus for addition on the real numbers the domain is the
Cartesian product R × R
Functions can have wider, non arithmetical application, e.g
capital : Countries → Cities
France |→ Paris
Italy |→ Rome
…
f : X → Y vs f : x |→ y
f : X → Y means that f is a function mapping elements of X (the domain) to elements of Y (the codomain). f : x |→ y means that the function f maps the element x to the element y. In this case we can write y = f(x). and y is called the image of x under the function f. We also say that f(x) is the value of f for the argument x.
Linear function f : R → R
- form
f(x) = ax + b
Quadratic functions - form
f(x) = ax2 + bx + c
Polynomial functions - form
f(x) = a0 + a1x + a2x^2 + a3x^3 + · · · + anx^n
Exponential functions - form
f(x) = ab^x
Logarithmic functions - form
f(x) = logb x if and only if x = b^f(x)
Injection
One to one function. Only one A per B
The function f : A → B is an injection if and only if, for all x, y ∈ A, if f(x) = f(y) then x = y:
∀x ∈ A ∀y ∈ A (f(x) = f(y) → x = y)
Surjection
Onto function.
Range = Codomain
No B left out (every output possible).
A function f : A → B is a surjection if and only if every element of B is the image
under the function of some element of A, i.e., for every y ∈ B there exists an element
x ∈ A such that y = f(x):
∀y ∈ B ∃x ∈ A (y = f(x))
Bijection
A bijective function is both surjective (onto), and injective (one-to-one).
One A per B and no B left out
Both sets A and B must have the same cardinality
Functional composition
Given functions g : A → B and f : C → D, where B ⊆ C, the composition of f and g is the function f ◦ g : A → D defined by the rule:
(f ◦ g)(x) = f(g(x))
for every x ∈ A.
If f and g are both injections then so is f ◦ g.
