A First Meeting with Discrete Mathematics

References

[EG]   sections 1.1 - 1.2, 1.3 (minus subsection 1.3.7), 1.4, 1.5 - 1.8;

Online revision texts for pre-university mathematics

and the text below.

Keywords

What is discrete mathematics? An overview of central topics covered on this course. How to read a mathematics book. Hints as to how to solve mathematical problems. Revision of high school arithmetic with numbers, fractions and square roots. Revision of how to manipulate and reduce algebraic expressions from high school. Revision of how to solve linear equations.

Introduction

We shall begin by reading chapter 1 of [EG] which gives an introduction to central topics in discrete mathematics - the subject of this course. As this course is probably your first mathematics course at university level and you are going to study the course as a distance course without the support of lectures, we shall also give some general hints on how to read a mathematics book and how to reach a solution to mathematics problems that at a first glance may seem almost impossible to ever be able to solve. We shall also give a short introduction on how to present a solution to a problem so that others will be able to understand it - this is important in exams and reports where you have to present some of your work.

As many of you studied your 'gymnasium'-mathematics course(s) quite a while ago, we shall also use some of this block and block 2 on revising and deepening your understanding of some important topics which you already have learnt. These include arithmetic with integers and fractions, reduction of algebraic expressions and the solution of linear equations. We shall also revise basic work with functions. Finally it is very useful to be able to solve quadratic equations, so we shall revise the formula for obtaining such solutions. If your mathematical skills are a bit old and rusty, you might need to spend more than the average 20 hours of studying for the first two blocks as you will need time to get the hang of things again. The best way of doing this is to solve a lot of exercises from the second coursebook ([D]). If you feel you also have difficulty with the exercises in [D], use the revision resources for pre-university mathematics, you can find a link to these on the course website.

1. What is Discrete Mathematics?

Start by reading the introductory paragraphs and section 1.1 in [EG]. Here the meaning of the main concept covered by the book - discrete mathematics - is being explained. Discrete mathematics is the cornerstone of this course, so it is important to understand what it entails. You may skip the exercises of section 1.1, but I recommend that you read through them.

2. Mathematical Models

Section 1.2 in [EG] explains the meaning of the other main concept covered by the book - mathematical models. You will already have encountered many such models. Take for example a roadmap of Sweden, it is a mathematical model of the physical roads and towns. A lot of details are not included in such a map, e.g. whether there are houses or trees on the side of the roads or open fields, and you may also find that minor sideroads have been excluded, but in spite of these abstractions the maps are still useful for finding the way from one town to another. You may also have seen maps of Sweden for hikers, these will emphasize other details than the roadmaps and are thus a different model of the same thing - namely Sweden. You may skip the exercises of section 1.2 also, but I recommend that you read through them.

At the top of page 4, Eriksson mentions the integers (Swedish: heltalen). The set of integers is the set of all whole numbers, positive as well as negative and also zero:

... -3, -2, -1, 0, 1, 2, 3, 4, 5, ...

Exercise B1.1
Give some examples of numbers which are not integers.   

The set of integers is a very important set. Almost everything we shall do on this course will concern integers in one way or the other.

3. Topics in Discrete Mathematics

Now read section 1.3 in [EG] in which five of the most important topics of this course are being introduced. You should skip subsection 1.3.7 which is beyond the scope of this course, and you may also skip all the exercises that are not specifically mentioned in this study guide.

Do not worry if you do not understand everything in this section. The section is basically an outline of the whole book, and everything mentioned here will be explained in detail later, so it is only natural that you will not fully grasp everything - just ignore the passages you do not understand. You may want from time to time to return to this section during the study of the course to reassure yourself that you have understood something which you could not understand at the beginning of the course!

Modular Arithmetic

Now read subsection 1.3.1 in [EG] and do övning 1.6 (An answer can be found at the back of the book). Modular arithmetic is used extensively in many computing subjects, and it is thus important for you to have basic knowledge about this. We shall study it in greater detail later.

Exercise B1.2
If 9 February 2006 was a Thursday, which day of the week was it

• on 16 February 2006?
• on 16 March 2006?

       

Sets

Next read subsection 1.3.2 in [EG] and do övning 1.7 (An answer can be found at the back of the book). The concept of a set is one of the most basic in mathematics. A set is merely a collection of objects. The objects could be numbers or letters for example, e.g. we talk about the collection of all integers as the set of integers. Because sets are so basic, we shall study them already in Block 3 right after the two introductory blocks.

Graphs and Relations

In subsection 1.3.3 in [EG] the concept of a graph is introduced. A graph consists of a set of dots which are called nodes or vertices (Swedish: noder eller hörn) together with a set of lines, called edges (Swedish: kanter) connecting (some of) the nodes. You can see an example of a graph at the top of page 6. Note that some pairs of nodes in this example are connected by an edge while other pairs of nodes have no edge between them.

Graphs can be used to described relations between the elements of a set by letting each element of the set correspond to a node and letting an edge between two nodes indicate that the two nodes are related. On the other hand, if no edge is present between a pair of nodes, this will mean that they are not related. Now do övning 1.8.

Logic

Towards the end of the course we shall study logic. This topic is introduced in subsection 1.3.4 in [EG]. This subject is highly abstract, so do not worry if you do not get much out of this subsection on this first reading, hopefully you will understand more at the end of the course. You may skip the exercise, but you should read through it.

Recursion

Subsection 1.3.5 in [EG] is about induction and recursion. We shall study recursion on this course because computer languages allow recursive functions, that is functions in which there is a function call to the function itself. This topic can be a bit tricky, so do not worry if you do not grasp it fully. Try solving övning 1.10 and övning 1.11.

Combinatorics

The final topic in discrete mathematics which is covered by this course is combinatorics. This is introduced in subsection 1.3.6 in [EG]. Basically combinatorics is an advanced form of counting - a counting technique which can be used to count the number of elements of large, abstract sets which are not easily listed. You may skip the exercises of this subsection, but as usual read through them to see what kind of problems can be solved by the techniques discussed here.

4. Arithmetical skills and Manipulation of Algebraic Expressions

It is very important for you to be able to do arithmetic with both numbers and letters. A computer is only as good as the programmer who programs it, so if you cannot in principle compute expressions by hand, you are not very likely to be able to write the program to get the computer to do it correctly either. It is therefore important to have understood all the principles of arithmetic that you learnt in your 'gymnasium'-mathematics course(s) and perhaps a few new ones also. You should read through Section 1.4 in [EG] and solve the exercises in övningar 1.16 - 1.18.

In Block 2 we are going to read parts of the other coursebook by Dunkels et al which trains the reader in the arithmetic and algebraic skills required for a university mathematics course at level A. If you did not find övningar 1.16 - 1.18 above relatively easy, you are now advised to study the online revision texts for pre-university mathematics to which you can find a link on the course website. There is a lot of material on this site, so read only those texts you want to brush up on. If you feel a need to study it all, read some of the texts this week and save some for next week and read them together with block 2. Save the sections about factorising quadratics and solving quadratic equations on a first reading, these will be covered specifically in Block 2 as some of you may not have learnt this in your 'gymnasium'-mathematics course(s).

The remaining four sections of chapter 1 in [EG] are mainly about study skills:

5. Presentation of Mathematical Work

Every examination (Swedish: tenta) in mathematics at Mid Sweden University has a note in the rubric along the following lines:

"Till alla uppgifter skall fullständiga lösningar lämnas. Resonemang, ekvationslösningar och uträkningar får inte vara så knapphändiga att de blir svåra att följa. Brister i framställningen kan ge poängavdrag även om slutresultatet är rätt!"

It is thus extremely important for you to learn how to present your work with the right amount of argumentation and working clearly shown. Section 1.5 in [EG] gives you a first introduction to this by forcing you to reflect over two different solutions to an exercise where one is inadequate while he other is very good.

You will gradually get better at presenting your work as time goes by. One of the purposes of the assignments on the course is precisely for you to get feedback from the lecturer on how you have presented your work. Try to compare how your solutions look with the model answers I will give you to your assignments and also compare the worked examples in the book with your solutions. Can you perhaps make your's better?

6. Problem Solving

Section 1.6 in [EG] gives some general guidelines as to how to attack mathematical problems. Read this carefully and try the methods on the exercises you cannot solve immediately.

7. Reading Mathematics

Section 1.7 in [EG] and the note How to read a maths book which can be accessed by clicking on the link or via the course homepage give some hints on how to read a mathematical text. This is not like reading a novel, you will need pencil and paper to be able to do so. This is because it is a good idea to make up your own little examples as you get on with the reading. Being able to construct examples is usually the key ingredient in being able to understand a concept.

8. Discrete Mathematics for Work and Play

Finally section 1.8 in [EG] introduces discrete mathematics as a subject which also has recreational applications. Many number-puzzles in newspapers and magazines have their roots in discrete mathematics. One of the latest puzzle-manias with its roots in discrete mathematics is Sudoku for example. In fact the construction of Sudoku-games with certain properties is a very interesting combinatorial problem.

Exercise B1.3
Try to solve a Sudoku-game if you have never tried one before.

Exercise B1.4
Solve the logic problem in section 1.8 in [EG]: What question should the princess ask?   

Week Exercise 1

1. Showing all your working, solve the following equations:

(a)  x + 5 = 2;
(b) 2x - 8 = 7x - 2

where x is a real number.

2. Without using a calculator, and showing all your working, solve

(a) exercise 1.5(b) in [D];
(b) exercise 1.10(b) in [D];
(c) exercise 1.11(a) in [D];
(d) exercise 1.15(f) in [D];
(e) exercise 1.15(j) in [D];
(f) exercise 1.16(b) in [D];
(g) exercise 1.25(c) in [D].