Mathematical foundations

Logic is the fundamental idea in both hardware and software.

A proposition is a statement which is true or false. 'Paris is the capital of France' is a true proposition. '2+2=5' is a false proposition. 'Be quiet' is not a proposition at all (it is an imperative - an instruction).

A proposition has a truth value, which is either true or false. This data type, with just two values, true or false, is usually called a boolean, after George Boole, who developed many of these ideas.

There are three basic logical operators, 'not, 'and' and 'or'.

'not' inverts a truth value. So if p is true, not p is false. If p is false, not p is true. We can set this out in a truth table:

p |
not p |

false |
true |

true |
false |

In many programming languages, not is written !. So for example

if x!=5.. do something

means if x is not equal to 5, do something.

'and' works on two truth values. It means 'both':

p |
q |
p and q |

false |
false |
false |

false |
true |
false |

true |
false |
false |

true |
true |
true |

'and' is often written &&. So

if x==3 && y==4.. do something

means if x is 3 and y is 4, do something

'or' means either or both:

p |
q |
p or q |

false |
false |
false |

false |
true |
true |

true |
false |
true |

true |
true |
true |

'or' is often written as ||

These logical operators correspond exactly to logic gates in digital electronics

A mathematical set is simply a collection of things. For example {Paris, New York, Moscow} is a set of three cities. {8, 4} is a set of two integers.

Sets are the basis mathematical object. All other types of object - number, function, vectors, groups, fields, rings - are defined in terms of sets.

Sets are not ordered, so {3,2,1} is the same set as {1,3,2}

Sets have no duplicates. {2,2,2,3,3,4} is the same set as {2,3,4}.

The things in a set are called its elements. x ∈ S means 'x is an element of S'

We can combine sets in two ways - union and intersection, corresponding to the logical or and and.

The union of two sets is the things in either, or both, sets. So the union of {1,2,3} and {2,3,4} is {1,2,3,4}. This is written as ∪, so te union of sets A and B is A ∪ B.

The intersection is the elements in one and the other. So the union of {1,2,3} and {2,3,4} is {2,3}. This is written A ∩ B

A subset of a set is some (maybe all) the elements. So a subset of {1,2,3,4} is {1,3}.

A set relates in some ways to data structures in software.

There are several different kinds of numbers

The natural numbers are 1,2,3,4.. Some people count 0 as a natural number. It is possibly to define the natural numbers in set terms (and the other kinds of numbers in terms of the natural numbers). Natural numbers are usually used for counting things. The set of natural numbers is usually written ℕ.

The integers are signed : .. -3, -2, -1, 0, +1, +2, +3.. The set of integers is ℤ (from the German Zahlen - numbers)

The rational numbers are fractions - like 1/4 and 3/4. There are also rationals greater than 1, like 4/3 and 27/6, and negative rationals like -2/3 and -14/3. On paper we can also write rationals as decimal expansions, such as 0.25 or 5.6713. Rational numbers can always be expressed as a/b where a and b are integers. The rational are ℚ, for quotient.

The irrational numbers cannot be written as a/b. An example is pi, which is about 3.14159265359.., and the square root of 2, which is around 1.41421356237.

The real numbers are all of these : integers, rationals and irrationals. They are called 'real' because there are also imaginary numbers, like the square root of -1. Measurements of quantities in science and engineering are usually real numbers. The reals are ℝ.

Ordinal numbers are used to label things, based on their position in some way. They are in contrast with cardinal numbers, used for counting how many. For example, a bus might carry the number 17. This does not mean there are 17 buses. It is a label, to show it is the bus on route number 17.

A function pairs up elements of one set with elements of another set.

For example one set might be {London, Paris, New York} and another set {red, green, blue}. One way to pair these is London - red, Paris - green, New York - blue. This is a mapping. Given one (say Paris), that maps to another (green).

This makes no 'sense'. We could have a different mapping - say London - red, Paris - green, New York - blue. That makes no sense either. Check London and New York both map to blue - no problem.

The only rule is that one element cannot map to two different ones. We cannot have London - red, London - green, New York - blue. This is simply how functions are defined - not 'one-to-many'.

We can also pair up elements of a set to elements of the same set. For example with the set {1,2,3}, we can have pairs (1,3), (2,2) and (3,1)

We often first meet functions like y(x) = 2x+1. This is a function from ℝ to ℝ. It pairs up 2 with 5, because 2 X 2+1=5. 3 pairs with 7, 4 with 9, and so on. This function has a formula : 2x+1. But a function does not have to have a formula. It is simply a set of pairs.

In software, a function might be called a map. A map is a set of key-value pairs. We can ask the map to fetch a value which has been paired with some key.

An example polynomial is the function ℝ→ℝ

y(x) =4x3+5x2+2x+4 (this is a cubic - power of 3 )

Another is

y(x) =2x2+3 (this is a quadratic - power of 2)

and

y(x) =4x-1 (this is linear)

So a polynomial is the sum of some terms, each of which is a power of x, times a constant (called the coefficient).

A logarithm is another type of function. It is often abbreviated to 'log'.

Some examples:

log10 100 = 2

log10 1000 = 3

log10 1000 = 4

log10 10= 1

log10 1/10 = -1

So the log of a number is what power we need to raise 10 to to get the number.

In symbols 10 log x = x

This function is the log to base 10.

In computer science we more often use the log to base 2:

log2 4 = 2

log2 8 = 3

log2 16 = 4

We can think of the log to base 2 as the number of times we can divide by 2 (before getting down to 1). For example log2 16 = 4 because starting at 16 and dividing by 2 we get 8, 4, 2, and 1.

This is often used in Computer Science because many algorithms work by splitting a data set into two parts. The number of times we can do this is the log to base 2.

The word vector is used in mathematics, physics and computing, with related but slightly different meanings.

In this diagram, we have vectors labelled a, b, c, d and e. They are all arrows, starting at the origin 0, and going sideways and up and down.

Vector a goes 2 sideways and 1 up. We write this as (2,1).

Vector b goes 3 sideways and 3 up, so b is (2,3).

Vector c goes 'backwards', to the left of the origin, so it is (-2,2).

d is (-3,-2). e is (1,-2).

In general these vectors are (x,y), where x and y are real numbers. We say these are vectors in ℝ2, meaning they are pairs of real numbers.

Two special vectors are marked, labelled i and j, which is what they are usually called. These vectors are 1 unit long, and are along the x and y axes. So i is (1,0), and j is (0,1).

A scalar is a simple value, not a vector. We can multiply a vector by a scalar to change its length. In this example f is (2,1). We have multiplied this by 2 to get g, which is (4,2).

In symbols,

2(2,1) = (4,2)

In general the scalar product of (a,b) multiplied by f is

f(a,b) = (fa, fb).

We can add two vectors, like this

f is (2,1), and g is (1,2). We can add the sideways and vertical components separately, and get (3,3) for the sum, as shown.

In general we have

(a,b)+(c,d) = (a+c, b+d)

and we can combine addition with scalar addition, so if we have two vectors u and v, we can form a new one as

a.u + b.v

where a and b are scalars.

One way to multiply two vectors is called the dot or scalar product. We multiply the components, and add. For example, the dot product of (2,3) and (4,5) is

( 2X4, 3X5) = (8,15)

In symbols,

(a,b).(c,d) = (ac, bd)

We can have vectors in 3d, using i j and k as unit vectors:

An example 3d vector would be (6,3,-2) with components 6 on the x axis, 3 on the y axis and -2 on the z axis.

We would call this a vector in ℝ3.

We can also have vectors in ℝ4, like (4,2,-6,3) (but they are hard to draw).

Many quantities have magnitude and direction - such as velocity, acceleration, electric field, gravitational field, magnetic field. These all need vectors to represent them, usually in ℝ3.

For example the velocity of a particle might be (3,2,7), meaning 3 m/s in the x direction, 2 m/s in the y direction, and 7 m/s on z.

We can also see a vector as a map, from component index to component. For example the 3d vector (3,7,4) might be seen as a function, mapping 0 to 3, 1 to 7 and 2 to 4.