Aussagenlogik und Beweisprinzipien – Mathe Studium 1. Semester Lernzettel zum Herunterladen als PDF

Aussagen und Verknüpfungen

Gesetze der Aussagenlogik

Quantoren

Beweisprinzipien

Wahrheitstafeln systematisch aufstellen

Eine Wahrheitstafel ist das wichtigste Werkzeug, um zu entscheiden, ob zwei zusammengesetzte Aussagen äquivalent sind oder ob eine Aussage eine Tautologie ist. Bei \(n\) Teilaussagen hat die Tafel genau \(2^n\) Zeilen, denn jede Teilaussage kann wahr oder falsch sein. Für drei Aussagen \(A,B,C\) sind es also acht Zeilen. Damit keine Zeile vergessen wird, schreibt man die Belegungen immer in derselben Reihenfolge auf: in der ersten Spalte vier Mal w und vier Mal f, in der zweiten Spalte abwechselnd zwei Mal w und zwei Mal f, in der dritten Spalte abwechselnd w und f.

Notwendig, hinreichend und die Sprache der Sätze

Mathematische Sätze haben fast immer die Form „Wenn \(A\), dann \(B\)“. Die Umgangssprache kennt viele Varianten, die alle dieselbe Implikation \(A\Rightarrow B\) meinen: „aus \(A\) folgt \(B\)“, „\(A\) ist hinreichend für \(B\)“, „\(B\) ist notwendig für \(A\)“, „\(A\) gilt nur dann, wenn \(B\) gilt“, „\(B\) gilt, falls \(A\) gilt“. Die Verwechslung von „notwendig“ und „hinreichend“ gehört zu den häufigsten Fehlern im ersten Semester. Ein Beispiel aus der Analysis: Differenzierbarkeit ist hinreichend für Stetigkeit, aber nicht notwendig; Stetigkeit ist notwendig für Differenzierbarkeit, aber nicht hinreichend, wie die Betragsfunktion in \(0\) zeigt. Ein Beispiel aus dem Studienalltag: Die Teilnahme an der Klausur ist notwendig für das Bestehen, aber nicht hinreichend.

Weitere Beweistechniken

Fallunterscheidung. Lässt sich die Menge aller zu betrachtenden Objekte in endlich viele Fälle zerlegen, die alle Möglichkeiten abdecken, genügt es, jeden Fall einzeln zu beweisen. Typisch ist die Zerlegung der ganzen Zahlen nach den Resten bei Division durch eine feste Zahl: Jede ganze Zahl hat die Form \(2k\) oder \(2k+1\), bei Division durch 3 die Form \(3k\), \(3k+1\) oder \(3k+2\). Eindeutigkeitsbeweis. Um zu zeigen, dass es höchstens ein Objekt mit einer Eigenschaft gibt, nimmt man zwei Objekte \(x,y\) mit dieser Eigenschaft an und beweist \(x=y\). So wird zum Beispiel gezeigt, dass das neutrale Element einer Gruppe eindeutig ist. Existenzbeweis. Eine Aussage „\(\exists x:\,P(x)\)“ beweist man durch Angabe eines Beispiels (konstruktiv) oder indirekt durch einen Widerspruch zur Annahme „\(\forall x:\,\neg P(x)\)“. Ein Gegenbeispiel dient dagegen nur zum Widerlegen von Allaussagen.

Wie schreibt man einen Beweis auf?

Ein Beweis ist ein Text für Leserinnen und Leser, keine Rechnung auf einem Schmierzettel. Er beginnt mit der Voraussetzung („Seien \(m,n\) ungerade ganze Zahlen“) und einer Ankündigung der Beweisart („Wir zeigen die Kontraposition“). Jeder Schritt wird begründet („nach Definition“, „nach der binomischen Formel“, „nach Induktionsvoraussetzung“). Am Ende steht die Behauptung, markiert mit \(\square\) oder „q. e. d.“. Hilfreich sind feste Formulierungen: „Es existiert ein \(k\in\mathbb Z\) mit …“, „Sei \(x\) beliebig, aber fest“, „Ohne Einschränkung sei …“. Rechnen Sie nie rückwärts von der Behauptung aus und schließen dann „also stimmt es“, wenn die Schritte nicht umkehrbar sind: Aus \(1=2\) folgt durch Multiplikation mit \(0\) die wahre Aussage \(0=0\), aber das beweist natürlich nichts.

Quantorenaussagen lesen und schreiben lernen

Quantorenaussagen sind lange Sätze in kompakter Zeichensprache. Lesen Sie sie von links nach rechts als Spiel zwischen zwei Personen: Wer „für alle“ sagt, überlässt dem Gegner die Wahl, wer „es gibt“ sagt, darf selbst wählen. Bei \(\forall\varepsilon>0\ \exists\delta>0\) wählt der Gegner zuerst ein beliebig kleines \(\varepsilon\), Sie müssen darauf mit einem passenden \(\delta\) antworten. Deshalb darf \(\delta\) von \(\varepsilon\) abhängen, nicht aber umgekehrt. Vertauschen Sie die Quantoren, ändert sich der Sinn: „Zu jeder Person gibt es einen Lieblingsfilm“ ist harmlos, „es gibt einen Film, der für alle der Lieblingsfilm ist“ dagegen eine starke Behauptung.

Beweise in der Klausur: ein Fahrplan

In Klausuren des ersten Semesters kommen immer wieder dieselben Aufgabentypen vor: eine Aussage negieren, eine Wahrheitstafel aufstellen, eine Behauptung durch Gegenbeispiel widerlegen und einen kurzen Beweis führen. Für den Beweis lohnt sich ein fester Ablauf. Erstens: Voraussetzung und Behauptung getrennt notieren. Zweitens: Alle Definitionen der vorkommenden Begriffe hinschreiben, denn die meisten Beweise im ersten Semester sind nichts anderes als das Einsetzen von Definitionen. Drittens: Bei Teilbarkeit und Parität mit \(2k\) und \(2k+1\) rechnen. Viertens: Bei Aussagen mit „es gibt kein“ oder „ist irrational“ den Widerspruch versuchen. Fünftens: Zum Schluss ausdrücklich festhalten, dass die Behauptung bewiesen ist. Wer diese Schritte einübt, gewinnt Sicherheit und verliert keine Punkte durch Lücken in der Begründung.