Why should I learn discrete math

Erich Prisner
Summer semester 2000

This is the internet script for the lecture. The medium "Internet" has the main advantages of flexibility (it can be changed later) and simple distribution (no paperwork). In addition, hypertext prevents the illusion that there is a natural linear order in the text. There are also disadvantages when it comes to displaying certain mathematical formulas.

Like most scripts, this is not intended to replace books. Books are more carefully written and usually more detailed. In particular, I would warn you against the impression that you could learn the content of the lecture while sitting at the computer: To understand it correctly, you have to work yourself, so at least have pen and paper ready! Over time you should get away from the screen and later also from the paper: You have understood a chapter when you can explain the content to a fellow student on a walk.

Symbols in Unix / Linux / Macintosh / Windows

If you do not see (almost) identical symbols in the following two lines, your operating system does not have the symbol fonts. In that case, please read on.

ØÚÙů $ Î "® £ ³ÍÏÈÇ» ƹ


(Version 5.7.)
--- the packed script for Windows (currently contains about 98% of the final volume).

Table of Contents


Discrete mathematics deals with discrete mathematical structures such as Boolean algebras, relations, (order relations, equivalence relations, graphs, directed graphs (digraphs), functions) designs, finite geometries, hypergraphs, Latin squares, finite bodies, codes, or even finite ones Subsets of plane, space, or the set of natural numbers. More precisely, discrete mathematics deals with problems on such structures and their solutions. In addition, areas from set theory and logic are dealt with in this lecture that are not actually included in the field of discrete mathematics. Since we are marking out a "broad field", there is a risk that the event will wither into a huge collection of definitions (see index). I can only counter this danger by adding as much content-related mathematics as possible to the necessarily formal description and manipulation of the structures: It should be clear that mathematics does not arise (even before!) By a mathematician looking at mathematical structures and using formal methods Derives sentences. Mathematical sentences arise from clear, natural questions (often motivated by application areas) that curious people brooded over until they not only had the answer but were even able to pass it on. In order to pass on the answer as well as to critically examine it, this formal way of speaking is now indispensable.

Although discrete mathematics clearly differs from continuous mathematics, it has many connections to analysis, (linear) algebra, probability theory, ... and in both directions. Terms and methods of discrete mathematics are used there, but conversely, methods of analysis and linear algebra are also extremely useful for certain discrete problems. Unfortunately, due to lack of time, we cannot deal with many of these deeper connections.

Sham criteria

50% of the achievable points in the exercises and a successful exam are necessary to obtain a certificate. The exam is written in the 12th week of the semester, the repeat exam in the 14th (last) week of the semester.

Collaboration on the script

You are cordially invited to help build and maintain the script. Please point out all typing errors, ambiguities, content errors, ... This way the script can get better and better during the semester. For those of you who have already mastered Java --- some Java applets would certainly add to the fun one can have with these pages.

So far, useful tips have been received from Annett Wenzel, Kerstin Buchholz and Michael Kühn. Many Thanks.

Lecture schedule

Erich Prisner
created in March 2000, last changed on July 13th. 2000.