Mathematik für Informatiker / eXamen.press (PDF)

1 Logik und Mengen (S. 1)

1.1 Elementare Logik

Die Logik ist ein wichtiges Hilfsmittel in der Informatik. Sie wird beim Entwurf von Programmen gebraucht oder um die Korrektheit von Algorithmen zu veri.zieren. Sie hilft bei der Beantwortung von Fragen wie "Hat die Switch-Anweisung wohl nichts übersehen?" oder "Arbeitet der Algorithmus wohl in allen Spezialfällen so, wie ich es möchte?". Die Logik ist notwendig, um Anforderungen eindeutig und widerspruchsfrei zu formulieren. Was ist zum Beispiel die Verneinung von "Jeder Benutzer hat ein Passwort"? Es gibt in der Umgangssprache verschiedene Möglichkeiten, die nach den Regeln der Logik richtige Verneinung ist aber eindeutig:" Es gibt mindestens einen Benutzer, der kein Passwort hat". (Nicht nur) für Informatiker ist logisch-analytisches Denkvermögen eine wichtige Anforderung, und daher steht die Logik auch am Anfang unseres Weges.

Definition 1.1 Eine Aussage (engl. proposition) ist ein Satz, von dem man eindeutig entscheiden kann, ob er wahr oder falsch ist.

Der Wahrheitswert "wahr" wird dabei mit "w" oder "1" abgekürzt, der Wahrheitswert "falsch" mit "f" oder "0".

Unsere Definition ist etwas optimistisch. Bei einer axiomatischen Behandlung der Mathematik stellt sich leider heraus, dass nicht jede Aussage entscheidbar ist. Genau das sagt nämlich der berühmte Unvollständigkeitssatz des österreich-ungarischen Mathematikers Kurt Gödel (1906–1978): In jeder formalen Theorie, die mindestens so mächtig wie die Theorie der natürlichen Zahlen (Peano-Arithmetik) ist, bleiben wahre (und falsche) arithmetische Formeln übrig, die nicht innerhalb der Theorie beweisbar (widerlegbar) sind. Wir werden aber zum Glück auf keine dieser Aussagen stoßen.

Beispiel 1.2 Aussagen
Handelt es sich um eine Aussage?

a) Wien ist die Hauptstadt von Österreich.
b) 1 + 5 = 6.
c) 5 ist kleiner als 3.
d) Guten Abend!
e) x + 3 = 5.
f) Heute ist Montag.

Lösung zu 1.2
a)

Aus den Rezensionen zur 2. Auflages:

"In diesem korrigierten Nachdruck des 1. Bandes … eines 2-bändigen Werkes zur Mathematik für Informatiker berücksichtigen die Autoren einige Verbesserungsvorschläge und Ergänzungen. Konkret heißt das, dass innerhalb der diskreten Mathematik im Kapitel zur Zahlentheorie ein weiteres Anwendungsbeispiel aufgenommen wurde. Außerdem wurde ein neues Kapitel zum Thema Polynomringe und endliche Körper eingefügt. Ein weiterer ergänzender Abschnitt findet sich in der Grafentheorie. … Zu der bereits sehr guten Ausstattung zur Lernhilfe und -kontrolle … tritt jetzt noch eine ergänzende Website hinzu …" (Isigkeit, ekz-Informationsdienst Einkaufszentrale für öffentliche Bibliotheken, 2008, Issue 1-2)