Diskrete Mathematik mit Grundlagen Sebastian Iwanowski • Rainer Lang Diskrete Mathematik mit Grundlagen Lehrbuch für Studierende von MINT-Fächern Sebastian Iwanowski Rainer Lang Fachhochschule Wedel Wedel, Deutschland ISBN 978-3-658-07130-1 ISBN 978-3-658-07131-8 (eBook) DOI 10.1007/978-3-658-07131-8 Die Deutsche Nationalbibliothek verzeichnet diese Publikation in der Deutschen Natio- nalbibliografi e; detaillierte bibliografi sche Daten sind im Internet über http://dnb.d-nb.de abrufb ar. Springer Vieweg © Springer Fachmedien Wiesbaden 2014 Das Werk einschließlich aller seiner Teile ist urheberrechtlich geschützt. Jede Verwertung, die nicht ausdrücklich vom Urheberrechtsgesetz zugelassen ist, bedarf der vorherigen Zu- stimmung des Verlags. Das gilt insbesondere für Vervielfältigungen, Bearbeitungen, Über- setzungen, Mikroverfi lmungen und die Einspeicherung und Verarbeitung in elektronischen Systemen. Die Wiedergabe von Gebrauchsnamen, Handelsnamen, Warenbezeichnungen usw. in die- sem Werk berechtigt auch ohne besondere Kennzeichnung nicht zu der Annahme, dass solche Namen im Sinne der Warenzeichen- und Markenschutz-Gesetzgebung als frei zu be- trachten wären und daher von jedermann benutzt werden dürft en. Gedruckt auf säurefreiem und chlorfrei gebleichtem Papier Springer Vieweg ist eine Marke von Springer DE. Springer DE ist Teil der Fachverlagsgruppe Springer Science+Business Media. www.springer-vieweg.de Vorwort DiesesLehrbuchgibteineEinführungindieMathematikimAllgemeinenunddie DiskreteMathematikimBesonderenundrichtetsichinersterLinieanStudierende eines Fachs an einer Fachhochschule oder Universität, für das die Beherrschung einer analytischen Denkweise eine wichtige Voraussetzung ist. Der wesentliche Inhalt dieses Buchs wird an der FH Wedel seit Jahren in ei- ner Erstsemesterveranstaltung für alle Studiengänge mit Informatikanteilen ein- gesetzt. Für derartige Studiengänge ist die Kenntnis der meisten Inhalte dieses Buchs an jeder Hochschule obligatorisch. In den anderen Studiengängen und in derSchulewerden diehiervorgestellten Inhaltedagegen kaumgelehrt,undesist eine Intention derAutoren,dafür eine größere Aufgeschlossenheit zu erreichen. Das Buch enthält neben den Disziplinen der Diskreten Mathematik auch eine ausführliche Einführung in die allgemeine Mathematik mit den Kapiteln Logik, Mengenlehre und Beweisführung. Es setzt nicht die Lektüre eines anderen Lehr- buchsvoraus.DahereignetsichdiesesBuchalsersterEinstiegindieMathematik derHochschulefürjedesStudienfachmitdemZiel,systematischesundabstraktes Denken zu erlernen. AlsVorkenntniswirddieMathematikbiszur9.SchulklassedesGymnasiumsvor- ausgesetzt,vorallemderUmgangmitZahlenundihrenelementarenBeziehungen. Mathematik der gymnasialen Oberstufe wird hier nicht benötigt. Dahereignet sich diesesBuchauchfürSchüleran Gymnasien,dieihrenHorizont erweitern wollen und einen umfassenderen Einblick in die Welt der Mathema- tik gewinnen wollen, als ihn die Lehrpläne an den Schulen zulassen. Wir haben durch die Zulassung von Schülern an unseren Klausuren nachgewiesen, dass der Schulstoff der 9. Klasse vollkommen ausreicht, um den Inhalt dieses Buches zu verstehen.UnserejüngsteKlausurteilnehmeringingindie8.Klasseundlöstealle bearbeiteten Aufgaben vollkommen richtig. Im Folgenden gehen wir auf diese beiden Leserkreise näher ein und schließen mit didaktischen Erläuterungen für Dozenten und Lehrer. Anmerkungen für Studierende Dieses Buch hat denAnspruch,den gesamten auch von Hauptfach-Informatikern benötigten Bedarf an Diskreter Mathematik abzudecken. Für das Bachelorstudi- um gilt das ohne Einschränkung. Lediglich im Masterstudium könnte punktuell eine weitergehende Vertiefung erforderlich sein, wenn Sie eine sehr mathematik- orientierteVeranstaltungbelegen.AberauchfürdasMasterstudiumwirdderhier VI behandelteInhaltgrößtenteilsausreichen.InsbesondereeignetessichalsWieder- holung fürs Selbststudium. An manchen Hochschulen wird die Mathematik nicht nach Gebieten getrennt, sondern gemischt in den Vorlesungen Höhere Mathematik I, II, ... gelehrt. Wenn Sie also einen Inhalt Ihrer Vorlesung in diesem Buch vermissen, dann gehört er vermutlich zu einem der anderen Gebiete der Mathematik. Die inhaltliche Ab- grenzungder Diskreten Mathematik zu denanderen mathematischen Disziplinen wird am Anfang von Kapitel 1 vorgenommen. Mathematik kommtüberall im Lebenvor.DiewörtlicheÜbersetzungdesWortes „Mathematik“ ausdemGriechischenheißtauchschlicht„Wissenschaft“.Umdiesen AnspruchzubedienenundgleichzeitigeinenBezugzudenvielfältigenAnwendun- gen aufzuzeigen, legen wir großen Wert auf Beispiele. Diese Beispiele sollen aber keineSpezialkenntnisseausderPraxisvoraussetzen.Daherhaltenwirsieelemen- tarundbeziehenunsinvielenFällen aufdieMathematikkenntnissevonSchülern der Mittelstufe. Unsere beispielorientierte Ausrichtung soll nicht dazu verleiten anzunehmen, der vermittelteStoffseiumbesondersschwierigeAnteilereduziertwordenodersonst- wie vereinfachtworden.Wirsetzen zwarwenigVorkenntnissevoraus,habenaber den Anspruch, den Leser auf ein mathematisches Niveau zu bringen, das dem akademischen Niveau der Informatik an jeder Hochschulein Deutschland gerecht wird,sowohlanFachhochschulenalsauchanUniversitäten.DadieInformatikder Mathematikamnächstensteht,bedienenwirdamitauchdieAnforderungenaller anderenStudiengänge–natürlichnurbezogenaufdasVerständnisderMathema- tikimAllgemeinensowieausschließlichderDiskretenMathematikimBesonderen, nicht aber der anderen Spezialgebiete wie z.B. der Analysis. Dieses Buch richtet sich aber nicht an Studierende der Mathematik selbst. Denn geradedieschwierigenBeweisewerdenhierweggelassen,unddieeinfachenBewei- se werden für deren Niveau zu ausführlich beschrieben. Außerdem fehlen einige Inhalte in speziellen Disziplinen der Diskreten Mathematik, die wir für den IT- Anwendungsbezugfür entbehrlichhalten. AlsOrientierungshilfe undAppetitma- cher vor Beginn eines Mathematikstudiums mag aber auch dieses Buch hilfreich sein, insbesondere fürLehramtsstudenten. In erster Linie soll dieses Buch ein hilfreicher Studienbegleiter sein. Wir wollen Sie nicht im Ungefähren verweilen lassen. Daher legen wir Wert auf Genauigkeit undGründlichkeitinderArgumentation,ohneSiemitFormalismusunnötigüber- frachten zu wollen. Wir halten uns hier an Albert Einstein: Beschreibe die Welt so einfach wie möglich, aber nicht einfacher. Für ein passives Verständnis aller Lehrinhalte ist das Buch selbsterklärend. Für ein aktives Verständnis dienen zahlreiche Übungsaufgaben, welche den Stoff sys- VII tematisch wiederholen und die Anwendungsbezüge verdeutlichen. Letztendlich kann ein vollständiges Verständnis aber nur durch das selbständige Lösen die- ser Übungsaufgaben mit anschließender Korrektur und Diskussion durch einen Lehrer (Professor, Assistent oder studentischer Tutor) erzielt werden. Das ist in derMathematik genausowieinderMusik oderimSport:NurdurchDurcharbei- teneinesBuchswerdenSieniemalseinMeister diesesFachswerden.Dazugehört auch kontinuierlicheÜbungund eine professionelle AnleitungzurVerbesserung. Anmerkungen für Schüler SiegehennochzurSchuleundinteressierensichfürMathematik?OderSiehaben zumindest festgestellt, dass Sie zwar in Mathematik nicht unbegabt sind, aber vom Fach bisher zu wenig fasziniert wurden? DannkönntediesesBuchIhnenhelfen,mehrBegeisterungzuentwickelnundsich in Richtungeines interessanten und zukunftssicheren Berufs zu orientieren. Wir setzen lediglich die Schulmathematik bis zur 9. Klasse voraus. Sie werden durch das Studium dieses Buchs merken, dass die Schulmathematik nur einen sehr kleinen Ausschnitt aus der Welt der Mathematik und ihren Anwendungen abdeckt. Sie werden ferner merken, dass das Gebiet der Diskreten Mathematik nicht schwieriger zu verstehen ist als andere in der Schule gelehrte Inhalte. Noch dazu ist es sehr praxisrelevant, vor allem, wenn Sie sich für IT-Anwendungen interessieren. Vielleicht gewinnen Sie ja genügend Interesse an diesem Gebiet und entscheiden sich für ein Studiumder Mathematik selbst oder der Informatik oder einesande- ren Fachs, in dem die Diskrete Mathematik nützlich ist. Es ist unsere Hoffnung, aufdieseWeiselangfristig denimmergrößer werdendenBedarfderWirtschaftan kompetenten Mitarbeitern durch eine ausreichende Absolventenzahl zu befriedi- gen. Bereits seit Jahren steht in den Berufen der angewandten Mathematik, im Besonderen in der Informationstechnologie, ein viel zu großes Angebot an Ar- beitsplätzen einer viel zu kleinen Zahl von Bewerbern gegenüber, und das unab- hängig von der aktuellen Konjunktur. Anmerkungen für Lehrende AnderFHWedelwirddieVorlesungDiskreteMathematikmit4SWSVorlesung und2SWSangeleiteter Übungdurchgeführt.FürdenArbeitsaufwand,insbeson- dereinwöchentlichaufgegebenenÜbungsaufgaben,vergebenwir5ECTS-Punkte. DieVorlesungumfasstbisaufwenigevertiefendeAbschnittedengesamtenInhalt diesesBuches.DieKapitel1und2richtensichanalleStudierendenderHochschu- VIII le, auch der Ingenieurwissenschaften und Betriebswirtschaft. Aus diesem Grund istdieLogikhiernursoknappbehandelt,wiedasfüreinVerständnisderweiteren mathematischenInhalteerforderlichist.FürIT-StudiengängegibtesVertiefungen der Logik in der VorlesungGrundlagen der Theoretischen Informatik. VieleThemen, diehier behandelt werden,berührenzumindestThemen,dieauch im Schulunterricht behandelt werden. Daher nutzen wir die Möglichkeit, etwas mehr vom Wesen der Mathematik auch für die Inhalte der Schulmathematik zu vermitteln. Einzelne Themen, z.B. die Konstruktion endlicher Körper, können in derSchuleauch in separaten Neigungsgruppen erarbeitet werden, sei es in einem größeren Schulprojekt oder auch in einem Vertiefungsfach, wie das in manchen Bundesländern in derMittelstufe angeboten wird. IndenKapiteln1bis3werdenallgemeinemathematischeGrundlagenbehandelt, da wir darin keine Vorkenntnissevoraussetzen. Wir streuen aber auch hier schon viele Themen der Diskreten Mathematik ein. Die folgenden Kapitel behandeln dann ausschließlich Inhalte der Diskreten Mathematik. Die ersten beiden Kapitel müssten eigentlich gleichzeitig eingeführt werden, da Logik und Mengenlehre gegenseitig aufeinander Bezug nehmen. Wir lösen die- ses Dilemma, in dem wir im Kapitel 1 (Logik) auf informelle Weise Konzepte der Mengenlehre benutzen, wie sie teilweise schon in der Grundschule verwendet werden. Im Kapitel 2 (Mengenlehre) wird das dann formalisiert. Ferner werden in die- semKapitelauchRelationenundFunktionensystematischeingeführt.Zumindest Funktionen sind bereits aus dem Schulunterricht bekannt sowie einer möglicher- weise parallel laufenden Analysisveranstaltung, sodass wir hier auf einen Wie- dererkennungseffekt setzen. Das wesentliche Ziel ist es, hier ein Verständnis für funktionaleZusammenhängeinvielenAnwendungenzuwecken,dasnichtaufdie technischen Fertigkeiten einer Kurvendiskussionreduziert wird. Kapitel 2 schließt mit Booleschen Algebren ab, welche von der Systematik her eher in das spätere Kapitel 5 der Algebraischen Strukturen gehören. Da Boole- schen Algebren aber gerade durch die Logik und Mengenlehre motiviert werden, erscheint unsder Zeitpunktihrer Einführung an dieser Stelle angebracht. Außer- demerhaltenwirdamiteinanspruchsvollesBeispielfürDefinitionen,Axiomeund Sätze, welche im dritten Kapitel behandelt werden. DasdritteKapitelvermitteltdieTechnikfürdasBeweisenmathematischerAussa- gen undSätze.VonderSystematikhermüsstedieses Themaeigentlich imersten Kapitelmitbehandelt werden.WirhieltendieVermittlungderelementaren Men- genlehre jedoch für dringlicher und anschaulicher und können im dritten Kapitel bereits mehr Basiswissen für die Beispiele voraussetzen, z.B. die oben zitierten Booleschen Algebren. IX Im vierten Kapitel werden die natürlichen und die ganzen Zahlen behandelt und ihre wichtigsten Eigenschaften diskutiert. Außerdem wird eine Einführung in die modulare Arithmetik gegeben, einer für die Informatik besonders wichtigen Dis- ziplin der Zahlentheorie. Im fünften Kapitel werden die Beispiele der modularen Arithmetik abstrahiert zu der Definition von Gruppe und Körper. Dieses Kapitel arbeitet hauptsächlich mitBeispielen anstattmitformalexaktenBeweisen,umesauchfürErstsemester verständlich zu machen. Den Abschluss des fünften Kapitels bildet eine Konstruktionsanleitung zur Bil- dungallerendlichenKörper.DieseKonstruktionsanleitunggehörtsicherlichnicht zumStandardeinerErstsemestervorlesungundkanninjedemStudiengangbeiBe- darfweggelassen werden,ohneeinewesentlicheLückezuhinterlassen. Wirhaben aberdieErfahrunggemacht,dassdieStudierendengeradehieranvielSpaßhaben. Sie werden von demverblüffendenVollständigkeitsanspruch des Galoisschen Sat- zesüberendlicheKörperfasziniert undkönnenanhandeigenhändigkonstruierter Körper besser begreifen, wie hier die Rechengesetze der ihnen bekannten reellen Zahlen auf endliche Mengen verallgemeinert werden. Einige unserer Studieren- den schrieben in höheren Semestern sogar aus eigenem Antrieb Software für das Rechnen in endlichen Körpern. Hinzu kommt die Relevanz für kryptographische Verfahren, was dieMotivation der Studierendenebenfalls steigert. ImsechstenKapitelgehtesumKombinatorikalsGrundlagederinvielenFächern benötigten Statistik und Wahrscheinlichkeitstheorie. Die letztgenannten Gebiete werden hier aber nicht mehr thematisiert, weil sie nur zu Teilen zur Diskreten Mathematik gehören. Dafürgibt es an derFH WedelSpezialvorlesungen, dieauf die jeweiligen Studiengänge ausgerichtet sind. Den Schwerpunkt legen wir in der Kombinatorik auf dieBehandlungvon Permutationen. Auchhier stellen wir wie- der einen Bezug zur Gruppentheorie her. Bis auf diesen letzten Absatz setzt das Kapitel der Kombinatorik aber keine InhaltederKapitel 4 und 5 voraus. ImsiebtenKapitelwerdendieGrundlagenderGraphentheoriebehandelt.Einbe- sonderesAugenmerkwirdaufdieDiskussionalgorithmischerVerfahrengelegt,die in vielen Anwendungsgebieten eine Rolle spielen. Aber auch hier sollen keine be- sonderenIT-Kenntnissevorausgesetztwerden.DaherwirdderAlgorithmusbegriff sehr informell behandelt und kein Pseudocode gegeben. Manchederhieraufgeführten Aussagen undSätzewerden exaktbewiesen. Wenn Beweise geführt werden, wird das Ende eines Beweises mit „(cid:2)“ gekennzeichnet. Wenn ein formaler Beweis nicht geführt wird, dann erläutern wir das meistens durch informelle Argumenteoder am Beispiel. Zuweilen verweisen wir auf vertie- fende Literatur, wo die ausgelassenen Beweise nachgelesen werden können. X Wir wünschen nun allen Lesern viel Spaß und viel Erkenntnisgewinn beim Lesen dieses Buches. Verbesserungsvorschläge sind unsimmer willkommen. Wedel, im August 2014, Sebastian Iwanowski undRainer Lang Danksagung WirsprechenunserenbesonderenDankanHelgaKarafiataus,diealsAssistentin fürDiskreteMathematikanderFHWedelwertvolledidaktischeBeiträgegeliefert hat.SiehatunsereVorlagesehrsorgfältig Korrekturgelesen. Vorallemhatsiein ungezähltenStundenihreprofundenLATEX-Kenntnisseeingesetzt,umunserBuch in diese ansprechendeForm zu bringen. Wir danken ferner Maya Brandl, einer Mitstudentin von Sebastian Iwanowski aus dem Mathematikstudium an der FU Berlin, die das finale Manuskript sehr sorgfältig redigiert hat. AndieserStellesollauchBeateundPeterIwanowskigedanktwerden,denEltern deseinenAutors,diealsMathematikermitLeidenschaftanSchuleundHochschule gelehrthaben.SielegtendemAutordasInteresseanderMathematikindieWiege.