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.
Identity function, i
Maps each element onto itself ∀x ∈ A i(x) = x. 1x = x = x1 i ◦ f = f = f ◦ i The identity function on a set X is the function iX : X → X
Inverse function
The inverse of an injective function f : X → Y is the function f^-1 : Y → X
5 proofs from an injection f : A → B, with its inverse f^-1 : B → A
- f^−1 is injective, and (f^−1)^−1 = f.
- f ◦ f^−1 is the identity function on the range of f.
- f^−1 ◦ f is the identity function on the domain of definition of f.
- f is well-defined (has a value for each element in its domain) if and only if f^−1 is surjective.
- f is surjective if and only if f^ −1 is well-defined.
Binary relations
Relations between pairs of elements.
e.g. ‘brother’ and ‘sister’.
John and Mary have three children, Anne, Barbara, and Charles.
, belong to ‘brother’ relation, while ,, , belong to ‘sister’ relation.
General definition of a relation
If A and B are any sets, a relation between A and B is
any subset of the Cartesian product A × B.
Composite relations
BrotherInLaw = (Brother ◦ Husband) ∪ (Brother ◦ Wife) ∪ (Husband ◦ Sister)
The composition of two relations R and S is the relation:
R ◦ S = {hx, yi | ∃z(xRz ∧ zSy)}
Types of relation
The relation R ⊆ A × B is
• one-to-one (injective) if for each A there is at most one B and for each y ∈ B there is at most one x ∈ A
• one-to-many if for each B there is at most one A, but
for at least one A there are two or more y ∈ B
• many-to-one if for each A there is at most one B, but
for at least one B there are two or more A
• many-to-many if for at least one A there are two or more B, and for at least one B there are two or more A
Transitivity
A relation R ∈ A2
is transitive if and only if, whenever xRy and yRz, then also xRz:
∀x, y, z ∈ A (xRy ∧ yRz → xRz)
> is transitive. 9>5 and 5>3 so 9>3.
Intransitive
Not transitive for at least one set of elements
Antitransitive
Not transitive for any set of elements
Symmetry
A relation R ⊆ A2
is symmetric if whevever xRy then also yRx:
∀x, y ∈ A (xRy → yRx)
Asymmetric
Not symmetric for any elements.
‘brother’ is not symetric, as Jordan’s brother is Jack, but Jordan could be Jack’s sister. However it is not asymmetric as Jordan could actually be Jack’s brother
A relation R ⊆ A^2 is asymmetric if whevever xRy then it is not the case that yRx:
∀x, y ∈ A (xRy → ¬yRx).
Antisymmetric
A relation is antisymmetric if the only case in which xRy and yRx is when x = y.
e,g, factor - If x is a factor of y and y is a factor of x then
x and y must be the same number.
A relation R ⊆ A2
is antisymmetric if whenever both xRy and yRx then x = y:
∀x, y ∈ A (xRy ∧ yRx → x = y).
Reflexivity
A reflexive relation is one in which each element is related to itself:
A relation R ⊆ A^2 is reflexive if:
∀x ∈ A (xRx)
Factor is reflexive since every number is a factor of itself
Irreflexive
An irreflexive relation is one in which no element is related to itself:
A relation R ⊆ A^2 is irreflexive if:
∀x ∈ A (¬xRx).
> is irreflexive, if x > y then definitely not y > x.
Equivalence Relations
An equivalence relation is a relation that is reflexive, symmetric, and
transitive, e.g.
1. xRx
2. If xRy then yRx
3. If xRy and yRz then xRz
On any set of sets, the relation ‘has the same cardinality as’ is an equivalence relation.
If R ⊆ A^2 is an equivalence relation, and a ∈ A, we write
[[a]]R = {x ∈ A | aRx}.
Equivalence
class
The set [[a]]R
The R is subscript
What does x ≺ y mean
‘x comes before y’
Order Relations - a strict total/linear order
This is the kind of order defined by a relation which is transitive, irreflexive, and linear
- If x ≺ y and y ≺ z then x ≺ z.
- It is not the case that x ≺ x for any element x.
- For any elements x, y, one of x ≺ y, y ≺ x, and x = y must hold.
Order Relations - a strict partial order
Any transitive, asymmetric relation on a set S, including total relations.
Given a set S with a relation ≺ on S • (S, ≺) is a strict partial order if... • (S, ≺) is a weak partial order if.. • (S, ≺) is a strict total order if... • (S, ≺) is a weak total order if...
• (S, ≺) is ≺ is transitive and irreflexive (and therefore also
asymmetric);
• (S, ≺) is a weak partial order if ≺ is transitive, reflexive, and antisymmetric;
• (S, ≺) is a strict total order if ≺ is transitive, irreflexive, and linear, i.e.,
∀x, y ∈ S (x ≺ y ∨ y ≺ x ∨ x = y);
• (S, ≺) is a weak total order if ≺ is transitive, reflexive, antisymmetric, and linear.
Conjunction (Logic)
Conjunction means 'and'. Denoted by '∧'. A ∧ B mean A and B. This is only true if A is true and B is true. Is assaciative: (A ∧ B) ∧ C = A ∧ (B ∧ C):
’~=’ symbol (the wiggle is above the lines)
This symbol means 2 formula are logically equivalent.
A ∧ B ~= B ∧ A (commutative)
(A ∧ B) ∧ C ~= A ∧ (B ∧ C)
A ∧ A ~= A (associative)
Disjunction
Disjunction means ‘or’.
Denoted by ‘∨’.
A ∨ B mean A or B. This is true if A is true or if B is true, or both.
A ∨ A ~= A
1) A ∧ (B ∨ C) ~=
2) A ∨ (B ∧ C) ~=
1) A ∧ (B ∨ C) ~= (A ∧ B) ∨ (A ∧ C)
2) A ∨ (B ∧ C) ~= (A ∨ B) ∧ (A ∨ C)
Negation
Negation means ‘not’.
Denoted by ‘¬’.
¬A is true iff A is false.
De Morgans Law
Break the line + change the sign
In this case there is no line, but separate brackets with not symbol and flip the V sign.
Tautologies
And the Law of the Excluded middle
A tautology is a logical formula which is true in all circumstances, i.e., a logically true formula.
e.g. A ∨ ¬A
This is the Law of the Excluded middle
Contradictions
A contradiction is a logical formula which can never
be true, i.e., a logically false formula.
e.g. A ∧ ¬A
Condtionals
Conditional means ‘if…then…’
Only false if A is true and B is false - If it’s snowing then it’s cold.
Logical notation: A → B
A → B is false iff A is true and B is false
In A → B, A is the antecedent and B is the consequent.
A → B ~= ¬A ∨ B
Prove using proof by contradiction - assume the opposite is true then disprove.
Biconditionals
Biconditional means ‘if and only if (iff)’
Logical notation: A ↔ B
A ↔ B is true iff A and B have the same truth value
Basically opposite of XOR gate.
A ↔ B ~= (A → B) ∧ (B → A)
To prove this, we must prove both “If A then B” and “If
B then A”.
Inference and Validity
An inference (or argument) consists of a set of statements called premises together with a statement called the conclusion. If the premises guarantee the conclusion AND the premises are true, then the inference is valid, otherwise it is invalid.
Can prove validity with truth tables.
If it is sunny we shall go to the seaside.
If we go to the seaside we shall swim.
Therefore, if it is sunny we shall swim.
Valid or invalid?
This is a valid inference
If you annoy that wasp, it will sting you.
If you keep quite still, you will not annoy that
wasp.
Therefore, if you keep quite still, that wasp
will not sting you.
Valid or invalid?
This is an invalid inference
∀ symbol
This symbol is for universal statements. It means ‘for every’.
All cows eat grass
For every x, if x is a cow then x eats grass.
∀x(C(x) → G(x))
Can be disproved with a single counterexample
∃ symbol
This symbol means ‘for some’
or ‘there exists’.
Some mammals fly
For some x, x is a mammal and x flies.
∃x(M(x) ∧ F(x))
Can be proved with a single example
What is 1,1,2,3,5,8,13,21,34,59,….
The Fibonacci sequence - it appears in many natural contexts e.g. populations and spirals
The golden ratio
The ratio of successive terms of a sequence gives a new sequence, e.g.
f2/f1, f3/f2, f4/f3, …
Do this for the Fibonacci sequence and eventually the sequence converges to
(1 + √5)/2 - the golden ratio
Ackermann Numbers - Power Towers
A power tower extends the idea of a power
m↑n = m^n = mmm…*m (n times)
m↑↑n = m↑m↑m…↑m (n times)
m↑↑↑n = m↑↑m↑↑m…↑↑m (n times)
These numbers give a sequence - 1↑1, 2↑↑2, 3↑↑↑3, …
Approximation Sequences
By Taylor’s theorem, near x = 0, a function can be approximated by polynomials of the form:
fn(x) = nΣk=0 Tk(x)
T0 = F(0), T1 = F’(0)x, T2 = (F’‘(0)x^2)/2
(Just binomial expansion formula really)
F^k = (d^kF)/(dx^k)
(Think double differentiation)
This is an exponential function
Arithmetic sequence
A sequence with a common difference between each term.
1,4,7,10,13,…
d = 3 (any term subtract the term before)
Arithmetic series
An arithmetic series, is the sum of an arithmetic progression.
Geometric sequence
A sequence with a common ratio between each term.
1,2,4,8,16,32,…
r = 2 (any term divided by the term before)
Geometric series
A geometric series is the sum of a geometric progression.
Sum of a geometric series
Sn = (a(1-r^n)) / 1-r S∞ = a / 1-r for |r| < 1
Sum of an arithmetic series
Sn = 1/2 n(a + l)
= 1/2 n[2a + (n – 1)d]
Experiment in probability
I An experiment is a process where one (and only one) of a number of possible outcomes (elementary events) happens.
e.g. cut a pack of cards and note what the suit is, or measure the height of a randomly-selected student
We must be able to specify precisely what outcomes can occur.
Sample space of an experiment
The sample space of an experiment is the collection of all possible outcomes.
e.g. for cards suit noting - {♦, ♥, ♠, ♣}
What is an event
An event is a collection of the possible outcomes in the sample space. An event occurs if and only if one of the outcomes which make up the event occurs.
e.g. for cards and suit noting - the suit is red (outcomes ‘heart’ or ‘diamond’)
Experiments and set theory
Outcome is like element of a set
Sample space is like universal set (S) of elements relating to experiment
Event is like subset of S
Empty/null set (∅) is like no outcomes happening
i.e. the ‘impossible event’.
∪ and ∩ can be used
The complement A’ of an event, A, is the event that…
The complement, A’ of an event, A, is the event ‘that A
does not occur’
Complementary events
Events that partition the sample space.
Compound experiments
Experiments performed in a number of
stages in sequence (e.g. throwing a die three times)
Multiplication principle
The multiplication principle states that in an r stage
compound experiment, the total number of outcomes is
n1 × n2 × . . . × nr
e.g. the number of outcomes in throwing a die 3 times is 6^3.
The number of ways in which the birthdays of n people could occur is 365^n
Sampling
Selecting one set of objects from another.
Sampling with replacement - when an object is selected it is then replaced before the next object is selected;
Sampling without replacement - when an object is selected it is not replaced before the next object is selected
A permutation of r objects from n
- All possible ways of doing something.
- a selection of r objects from n without replacement
- the sequence of selection is important.
- i.e.: an ordered subset of r of the n objects.
- Note: An ordered selection of all n objects is called a
permutation of n objects.
A combination of r objects from n
- a selection of r objects from n without replacement,
- the sequence of selection is unimportant.
- i.e. an ’unordered subset’ of r of the n objects.
- Note: {a, b} and {b, a} are different permutations of the
three letters {a, b, c}, but are the same combination.
Number of arrangements of {a,b,c,d}
multiplication principle = 4x3x2x1 = 4! = 24
Number of arrangements of 2 of the letters from {a,b,c,d}
multiplication principle =
(4x3x2x1)/(2x1) = 4!/2! = 4x3 = 12
For any combination of r objects from n there are how many permutations of r objects from n
For any combination of r objects from n there are r! permutations of r objects from n.
This is because there are r! permutations of the r objects in the combination
The number of different ways of choosing 6 from 49 (national lottery) is…
(49C6)
= 49/1 x 48/2 x 47/3 x 46/4 x 45/5 x 44/6
=13, 983, 816
Number of ways of getting exactly 3 lottery numbers
(6C3) x (43C3) = 246,820
So odds = 13,983,816/246,820
= 1:56.7
Axiomic approach to probability - 3 Axioms
- Axiom 1: P(A) ≥ 0 for all events A ∈ S
- Axiom 2: P(S) = 1
- Axiom 3: P(A ∪ B) = P(A) + P(B) if A and B are
mutually exclusive. Similarly, if A1, A2, A3, . . . are mutually
exclusive (pairwise disjoint) then P(A1 ∪ A2 ∪ A3 ∪ . . .) = P(A1) + P(A2) + P(A3) + . . .
Definition of a graph
A graph is a non-empty set V of nodes, and a set E of edges that connect pairs of nodes
Simple, undirected graph
Never 2+ edges between each pair of nodes and no edges from a node to itself
Directed graph (Digraph) (With loops)
Same as simple undirected graph but each edge has a direction (arrow), and loops (node to itself or 2 nodes 2 connections) are allowed.
If simple then no loops/double edges.
Degree of a vertex/node
The number of edges attached to the node
deg(v)
Neighbourhood (neighbour set) of a vertex/node
Set of nodes attached to it by edges
Tree
An undirected graph with no cycles
Rooted tree
A tree where all nodes orient away from a single root node
m-ary tree
full m-ary tree if every internal node has exactly m children
m=2 is binary tree
Planar graph
Can be drawn on a plane without any 2 edges crossing
Polyhedral graph
Can be drawn as a polyhedron
Face
A face of a connected simple graph is where all paths close upon themselves is a region enclosed by edges. The outside region in a planar graph is considered as one face.
Euler’s Formula
V-E+F=2
Maximum number of edges in a planar graph with V vertices
E = 3V-6
F = 2E/3 -> V-E+2E/3 = 2
-> 3V-3E+2E = 6
->3V = 6+E -> E = 3V-6
