CAB203 | 2024 S1
Discrete Structures
Table of Contents
Week 2: Data Representations
Week 3: Propositional Logic
Week 4: Sets
Week 5: Predicate Logic
Week 6: Relations, Functions
Week 7: Graphs
Week 8: Trees
Week 9: Case studies
Week 10: Finite State Automata
Week 11: Linear Algebra
Week 12: Probability and Bayesian reasoning
Week 13: Program Correctness
CAB203 Discrete Structures
Describe what is CAB203 is about
Week 1: What is Mathematics
Solving a problem
Suppose we have this problem here:
You have some apples
You have some friends
You want to know if you have enough apples to give one to each friend.
Extraneous properties
There are many properties in this situation, some are not relevant:
Size and shape of each apple
Size and shape of each friend, their name, hair colour
and what we want to do:
which apple goes to each person?
We can use abstraction to simplify the problem by ignoring the irrelevant information and focusing on information that is relevant to the problem.
Abstractions
Abstractions aims to capture the relevant properties of the situation:
x = number of apples
y = number of people
and the relationships between those properties
?
is number of apples equal to, or more than number of people.
Mathematical approach to problem solving:
Analyse the problem, and sort for relevant properties.
Create abstraction of the situation.
Solve the problem in the abstraction.
Translate the solution back into the real situation.
Natural numbers
The usual abstraction for problem involves counting natural numbers, i.e. 0, 1, 2, 3 .....
Create an abstraction:
assign a number to each apple, start from 1, x is the last number used.
assign a number to each person, start from 1, y is the last number used.
Solve the problem in the abstraction, we compare x and y to see which one comes first in the number order.
Translate the solution back: if then we can give an apple to each friend
Natural numbers are completely abstract. When you think about it, we say there are 1 apple or 2 oranges on the table, we are using natural numbers to describe the situation but the number themselves are not part of the reality. They are just symbol that we assign to object therefore there is no such thing as 1, 2 in the real world / natural number don't exist in physical form. Pretty interesting.
How abstractions can go wrong
Abstraction might not have enough information, for example if the counting system only goes up to three then we can't answer questions that are above that number like four.
Abstraction might have too much information, for example instead of having extract quantities of the number of apples we have a 2D image of apples and we have to count the number of apples by looking at the image, it will be hard to get information that we care about.
Abstraction might have the wrong information, for example if our abstraction only tells us the color of the apples, we can't answer questions about the quantities of apples.
That's why it's important to have the correct abstraction for the problem that is being solved.
Abstractions on their own
We often study abstractions without references to any particular problems or real situations. In this scenario abstraction is called mathematical theory. These usually consist of / look like
A collection of mathematical objects, like numbers, operations (addition, subtraction)
Axioms, statements about how objects are related to each other, for example a + b = b + a
We can derive new relationships by applying logic to the axioms.
Natural numbers look like this:
Objects: 0, 1, 2, 3, ......
Some of the Axioms that is commonly used
If x, y and z are natural numbers:
0 is a natural number
x = x
if x = y then y = x
if x = y and y = z then x = z
if x = w then w is a natural number
S(x) is natural number
if S(x) = S(y) then x = y
S(x) = 0 is always false
NOTE: S(X) is a shorthand way of saying X + 1
Adding 1 to a number is called the successor function and we write it as S(x) where x is any counting number. I’ll use an example to make it easier to understand: let’s say the counting number is 5. If we apply S(x) to that counting number, it would look something like this:
S(5) = 5 + 1
Here's another example, but instead it's S(S(x), this is a short way of saying x + 2:
S(S(4) = 4 + 2
S(S(4) = (4 + 1) + 1
We can combine axioms together by using logic to create new true statements about natural numbers.
For example: if we apply S(X) twice to 6, we will find that S(S(6)) is a natural number. This statement means that we add 1 to 6 twice, and the result is still a natural number. It would look something like this:
S(S(6)) = 6 + 2
S(S(6)) = (6 + 1) + 1
S(S(6)) = 8
These are three examples of the same thing
Mathematical objects
Mathematical objects are like labels or names for different things. They don't have any meaning by themselves, they only tell us how they are different from other things.
For example, 2 is a name for something that comes after something that comes after 0.
0 is just a name for something that doesn't change when you add it to something else.
These names help us to compare and calculate things, but they don't tell us what those things are in reality. They are abstract, which means they are not tied to any specific thing. They could be used to describe many different things, like apples, eyes, stars, etc.
The only way we can know more about these objects is by using rules or axioms that tell us how they behave and relate to each other. These rules are like the grammar of mathematics, they help us to make sense of the symbols and expressions we use.
Relationships between objects
What do relationships between objects look like?
Sometimes, we want to talk about how different things are related to each other.
For example, we can say that a cat is smaller than a dog, or that a triangle has three sides.
To talk about these relationships, we use sentences that can be either true or false.
For example, the sentence "a cat is smaller than a dog" is true, but the sentence "a triangle has four sides" is false.
These sentences are called propositions. They are the basic building blocks of logic and mathematics.
When we want to create a new branch of mathematics, we start by choosing some propositions that we assume to be true. These are called axioms. They tell us what kind of things we are studying and what rules they follow.
For example, one of the axioms of geometry is that two points determine a line. This means that if we have two points, we can draw a line that passes through them. This is something we take for granted when we study geometry.
Applying theories to real situations
A real situation is something that happens in the real world, like counting apples, measuring distances, or making money. To apply a mathematical theory to a real situation, we need to do two things:
First, we need to match up every object in the theory to something in the real situation. For example, if we want to use arithmetic to count apples, we need to match up every number to a group of apples with that numbers to represent how many apples we have.
Second, we need to make sure that all of the rules in the theory are true in the real situation. For example, if we want to use arithmetic to count apples, we need to make sure that adding two groups of apples always gives us the same number of apples as adding the numbers that represent them. This way, we can use arithmetic to calculate how many apples we have.
If these two conditions a meant, then we can use the mathematical theory to learn more about the real situation. For example, if we know that we have 3 apples, and we get 2 more apples, we can use arithmetic to figure out that we have 5 apples. We don't have to count them again because it's true. Mathematicians would say that the real situation is a model for the theory, which means that it follows the rules of the theory. A model can help us understand and predict what happens in the real situation.
When theories don't apply to real situations
If a situation does not obey all axioms in a mathematical theory, then the theory does not apply. Consider:
Each number corresponds to the number of members in a committee.
Addition corresponds to combining all members of two committees into one committee.
But this does obey the axioms of the natural numbers
Alice, and Dave form the committee for revising extensions request policies. This corresponds to the number 2. We add these committees together to create a new committee of Alice, Bob, Charlie and Dave. This corresponds to numbers 4.
So, 3 + 2 = 4!
This is not a model for the natural numbers. The committee's situation is not a model of the theory natural numbers, because it does not obey all the axioms of the natural numbers. One of the axioms of the natural numbers is that addition is commutative, which means that a + b = b + a for any natural numbers a and b. But in this example, the order of adding the committees matters, because Alice is in both committees, so 3 + 2 is not the same as 2 + 3. Therefore, the theory of natural numbers does not apply to this situation, and you cannot use the properties of the natural numbers to reason about it.
Another way to think about it is that the theory of natural numbers is about counting discrete objects, such as apples, pencils, etc. But the situation with the committees is not about counting discrete objects, but about combining sets of people, which may have overlaps or duplicates. Therefore, the theory of natural numbers is not the right tool to use for this situation. You need a different theory that can handles sets and their operations, such as the theory of set algebra.
An analogy for this: supposes two people are playing a board game.
The rules of the game (say, chess) are like a mathematical theory.
This particular game is a like model for chess.
If they instead play according to some other rules, then this is not a game of chess.
Truth in mathematics
Statements in mathematics are always relative to a particular mathematical theory.
A statement may be true in one theory and not in another, for example:
ab = ba for real numbers, but not for matrices
A true statement in a theory says nothing about a real situation if it is not a model for the theory.
Within a theory and its models, truth is absolute:
The rules of logic guarantee that true statements in a theory are true in every model of the theory.
It's possible for a mathematical theory to be inconsistent in which case every statement in the theory is true, but also every statement in the theory is false!
What do mathematicians do?
Mathematicians usually do some of these things:
Create new abstractions (often abstractions of other abstractions!)
Develop techniques for solving problems in particular abstractions.
Determine properties of objects in particular abstractions (proving theorems)
Apply abstractions to model and solves (applied mathematics)
Terminology for models
A model is a way describing something using math. There are two ways to use models:
One way is to start with a real system, like a car or a planet, and then find a math theory that can describe how it works. This is called a system model. For example, you can use physics to model how a car moves or how gravity affects a planet.
Another way is to start with a math theory, like geometry or algebra, and then find a real system that can be described by it. This is called a mathematical model. For example, you can use geometry to model the shape of a snowflake or algebra to model the patterns of numbers.
These two ways are kind of opposite, but they are both useful. Usually, when people talk about models, they mean the second way, the mathematical model.
Computers are also a way of describing things using math. Computers use bits, which are symbols that can be either 0 or 1, to represent any kind of information. To use computers, we need to do three things:
First, we need to convert the information we want it use into bits. This is called data representation. For example, we can use bits to represent numbers, letters, images, sounds, etc.
Second, we need to tell the computer what to do with the bits. This is called programming. We use rules and instructions written in a special language, to tell the computer how to manipulate the bits and get the results we want.
Third, we need to convert, the bits back into the information we want to see. This is called output. For example, we can use bits to display images on a screen, play sounds on a speaker, print text on a paper, etc.
All of these steps are basically math, because bits are math objects and programming is math logic. Computers can help use model things using math, because they can do math very fast and accurately. Good programmers can use math theories that have been developed for a long time to make their programs better and easier.
Modular Arithmetic
Modular arithmetic is a way of doing math with whole numbers, where you only care about the remainder after dividing by a fixed number. This fixed number is called the modulus, and it can be any positive number bigger than one. For example, if the modulus is 12, then 15 and -9 are the same, because they both have a remainder of 3 when divided by 12. We write this:
15 ≡ - 9 (mod 12)
You can think of modular arithmetic as using a clock to keep track of numbers. A clock has a modulus of 12 because it resets to 0 after reaching 12. So, if it is 10 o'clock now, and you add 5 hours, you get 3 o'clock, not 15 o clock. This is because:
10 + 5 ≡ 3 (mod 12)
Modular arithmetic is very useful in computer science, because computers use binary numbers, which are made of only 0s and 1s. To represent negative numbers, computers use a method called 2's complement, which depends on modular arithmetic. For example, to represent -5 in 8-bit binary, we take the modulus of 5 by 256 (which is:
) and get 251. Then we write 251 in binary, which is 11111011. This is how computers store -5 in memory.
Modular arithmetic is also good for modeling many things, such as the days of the week, the seasons, the colors of a Rubik's cube, and the indices of a ring buffer. A ring buffer is a data structure that stores a fixed number of elements in a circular order. For example, if the ring buffer has a size of 10, and the first element is at index 0, then the next element is at index 1, and so on, until the last element is at index 9. Then, the next element is at index 0 again, and the cycle repeats. To find the index of any element , we can use modular arithmetic. For example, if we want to find the index of the 15th element, we can take the modulus of 15 by 10, and get 5. So, the 15th element is at index 5.
Modular arithmetic is also the foundation of many special topics, such as cryptography, which is the science of making and breaking secret codes. Many encryption algorithms use modular arithmetic to transform message into codes that are hard to crack. For example, one of the most popular encryption methods is called RSA, which uses very large prime numbers and modular arithmetic to create public and private keys. A public key is used to encrypt a message, and a private key is used to decrypt it. The security of RSA relies on the fact that it is very hard to find the modulus and the private key from the public key, even with powerful computers.
Mathematical definitions
Mathematical definitions are like labels that we use to name different ideas or objects in math. For example, we can use the word "circle" to name a shape that has a fixed distance from a center point. Definitions help us to communicate more clearly and quickly, but they do not change the nature of things they name.
They are similar to how we use functions or variables in programming to make our code shorter and easier to understand. However, we have to be careful when we use words that have a different meaning in math than in everyday language. For example, the word "even" in math means a number that can be divided by 2, but in English it can also mean fair or balanced. We should always use the math meaning when we talk about math.
Example definition: Divides
Definition: Let a, b be integers. If there exists another integer c such that ac = b, we say that a divides b and write a | b. Equivalently, we say b is divisible by a.
In definitions, we use italics to emphasise the words that are being defined. The definition will always refer to previously defined terms or basic objects (in this case, multiplication and equality).
Divides
The previous definition says that these all have the exactly the same meaning:
a | b
a divides b
b is divisible by a
There exists some integer c such that ac = b
We can use them interchangeably. The first three are defined in the definition. They are shortcut names for the last one.
Parity
Integers have one of two different parities:
x is even means 2 | x
x is odd means 2 | (x - 1)
Some properties:
even ± even = even
even ± odd = odd
odd ± odd = even
So two numbers have the same parity if their difference is even.
Clock arithmetic
If it's 10 o'clock. What time is it in 5 hours?, 3 o'clock
Time wraps around at 12. Adding any multiple of 12 hours does not change the o'clock, for example: is 27 hours after midnight the same o'clock as 39 hours after midnight?
Yes: 39 is a multiple of 12 away from 27.
So a and b are the same o'clock if 12 divides a - b.
Modular arithmetic is an abstraction
Modular arithmetic is an abstraction of parity and clock arithmetic.
Parity is arithmetic modulo 2
Clock use arithmetic modulo 12
More generally, we can have arithmetic modulo n for any positive integer n.
Modular arithmetic is a kind of extension to the integers by adding a new relation (modular equivalence.)
Modular arithmetic creates cyclic groups. Groups are a cornerstone of mathematics.
Modular equivalence
Modular arithmetic works by replacing equality with modular equivalence also called modular congruence.
Definition
If n | (a - b) we say a and b are equivalent modulo n and write
a ≡ b (mod n)
Properties of modular arithmetic
Modular equivalence plays nicely with addition, subtraction and multiplication. Suppose that a ≡ b (mod n) and c ≡ d (mod n).
Then:
a + c ≡ b + d (mod n)
a - c ≡ b - d (mod n)
ac ≡ bd (mod n)
This means we can use many tools from normal arithmetic with modular arithmetic.
If a ≡ b (mod n) and b ≡ c (mod n) then. a ≡ c (mod n). This means that we can free replace one number with an equivalent one.
Mod operator
For computing, we might want to store only small numbers. We have a special notation for this:
Definition:
a mod n is the smallest non-negative b such that a ≡ b (mod n)
Equivalently, a mod n is the remainder you get when you divide a by n.
Example: 17 mod 4 = 1 because 17 = 4(4) + 1
In Python and many other programming languages, this is the % operator.
Also in some languages, a % n is negative if a is negative.
Divide revisited
Let's practice using definitions to get a useful property of the mod operator.
Lemma
Let a and b be integers. If a mod b = 0 then b | a.
The symbol | is used to mean "divides" or "is a divisor of" in math. For example, 2 | 6 means that 2 divides 6, or 2 is divisor of 6. This means that 6 can be written as 2 times some other integer, like 6 = 2 x 3. Another way to say this is that 6 is a multiple of 2, or 6 mod 2 = 0. The mod operator gives the remainder when one number is divided by another. For example, 7 mod 2 = 1 because 7 divided by 2 gives a quotient of 3 and a remainder of 1.
A lemma is a small statement that helps us prove bigger statements in math. A lemma is usually derived from the basic rules or axioms of math, and it can be used to support other lemmas or theorems. A theorem is a major result that has been proven using lemmas and axioms. To prove a lemma or a theorem, we have to show a logical sequence of steps that starts from the axioms and ends with the statement we want to prove. This is called a proof.
Proof of lemma
Proof.
Let integers a and b be given such that a mod b = 0. Then from the definition of the mod operator we have:
a ≡ 0 (mod b).
From the definition of modular equivalence we have:
b | (a - 0).
From a well-known lemma we see that a - 0 = a for any integer, so b | a.
Exponents and logarithms
Exponents
Notation: means a * a * a
means multiple a together n times
a is called the base
n is called the exponent
Exponents can be defined where n is not integer. Real and even complex values of n can be used.
Laws of exponents
Important exponents in Computer Science
In computer science you'll see a lot of powers of 2. For example, we have prefixes.
kilo- means multiple by
mega- means multiple by =
giga- means multiple by =
tera- means multiple by =
peta- means multiple by =
exa- means multiple by =
For example, one kilobit is 1024 = bits.
We will always use these multipliers when talking about bits / bytes.
Logarithms
logarithms are the inverse of exponents.
if n = then
So tells what exponent is needed to make x from a:
Laws of logarithms
Base transformation law
Calculators usually have only base 10 and base e
Use base transformation to calculate etc.
Example: address lines (1)
Address lines are used to identify the location of a memory unit, such as a byte, in a computer system. Each address line can carry one bit of information, which means it can be either 0 or 1. The more address lines you have, the more memory units you can access.
To find out how many address lines you need for a certain number of memory units, you can use the formula:
number of address lines = number of memory units
This formula is based on the fact that each address line can have two possible values (0 or 1), so if you have n address lines, you can have two possible values (0 or 1), so if you have n address lines, you can create different combinations of bits, which correspond to different memory locations.
For example, if you have 3 address lines, you can create 8 different combinations of bits, such as 000, 001, 010, 011, 100, 101, 110, and 111. These combinations can be used to access 8 different memory units.
Using this formula, you can answer the questions in your example:
How many address lines required for 65536 addresses?
number of address lines = = 16
You need 16 address lines to access 65536 memory units.
How many address lines required for 4096 kilobytes (one address per byte)?
First, you need to convert kilobytes to bytes. One kilobyte is equal to 1024 bytes, so 4096 kilobytes is equal to 4096 x 1024 = 4194304 bytes. Then, you can use the formula:
number of address = = 22
You need 22 address lines to access 4194304 bytes.
How many address lines required for 5000 bytes (one address per byte)?
number of address lines = = 12.287771
You need 12.287771 address lines to access 5000 bytes. However, since you cannot have a fractional number of address lines, you need to round up to the next integer, which is 13. This means you will have some extra memory units that are not used.
Ceiling and floor
12.28771.. address line doesn't make sense
Introduce the ceiling and floor
Ceiling: round up. [a] is the next integer above a
Floor: round down. [a] is the next integer below a
We need [ ] = 13 address lines
Week 2: Data Representations
Week 3: Propositional Logic
Week 4: Sets
Week 5: Predicate Logic
Week 6: Relations, Functions
Week 7: Graphs
Week 8: Trees
Week 9: Case studies
Week 10: Finite State Automata
Week 11: Linear Algebra
Week 12: Probability and Bayesian reasoning
Week 13: Program Correctness
Last updated
