K1 Zur Sprache der Mathematik

Einen Ausdruck, der eindeutig wahr oder falsch ist.

Beispiel: “3 ist eine Primzahl.” (w)

“1+1=4” (f)

Gegenbeispiele:

“Nachts ist es kälter als draußen.” (?)

-> ist keine Aussage in diesem Sinne, da unklar ist, was es bedeuten soll

“Alle Personen in diesem Raum sind sympathisch.”

-> ist ebenfalls keine Aussage in diesem Sinne, weil verschiedene Beobachter ihr verschiedene Wertzuweisungen zuweisen würden

• Negationen

• Konjunktionen

• Disjunktionen

Seien A und B zwei Aussagen.

Die Aussage (¬A) ist die Aussage „Die Aussage A ist falsch.“ und heißt die Negation von A.

Seien A und B zwei Aussagen.

Die Aussage (A ∧ B) ist die Aussage „Die Aussage A ist wahr und die Aussage B ist wahr.“ und heißt die Konjunktion von A und B.

-> die Konjunktion ist also ein logisches „und“

Seien A und B zwei Aussagen.

Die Aussage (A ∨ B) ist die Aussage „Mindestens eine der beiden Aussagen A und B ist wahr.“ Sie heißt die (nicht-exklusive) Disjunktion von A und B.

-> die Disjunktion ist ein logisches (nichtexklusives) „oder“

-> statt „A impliziert B“ sagt man auch „wenn A, dann B“, „B folgt aus A“, „A ist hinreichend für B“ oder „B ist notwendig für A“

-> ist die Aussage A falsch, so ist die Implikation A ⇒ B stets wahr; man kann also aus einer falschen Aussage folgern, was immer man möchte

-> statt „A ist äquivalent zu B“ sagt man auch „A gilt genau dann, wenn B gilt“

-> die Aussage A ⇐⇒ B hat dieselbe Wahrheitstafel wie die Aussage C in, d.h. zwei Aussagen sind genau dann äquivalent wenn sie denselben Wahrheitswert besitzen

1. Tertium non datur

2. Transitivität

3. Assoziativität

4. Kommutativität

5. Distributivität

6. Monotonie

7. de Morgansche Regeln

8. doppelte Negation

Für beliebige Aussagen A,B,C ist die folgende Aussage stets wahr:

Für beliebige Aussagen A,B,C ist die folgende Aussage stets wahr:

Für beliebige Aussagen A, B, C ist die folgende Aussage stets wahr:

Für beliebige Aussagen A, B, C ist die folgende Aussage stets wahr:

Für beliebige Aussagen A, B, C ist die folgende Aussage stets wahr:

Für beliebige Aussagen A, B, C ist die folgende Aussage stets wahr:

Für beliebige Aussagen A, B, C ist die folgende Aussage stets wahr:

Für beliebige Aussagen A, B, C ist die folgende Aussage stets wahr:

• durch Wahrheitstafeln

• durch logische Umformungen

um bei komplizierteren Ausdrücken den Überblick zu behalten, wollen wir Klammern wenn möglich weglassen!

• Außenklammern können stets gefahrlos weggelassen werden, also schreiben wir A ∧ (B ∨ C) statt (A ∧ (B ∨ C))

• aufgrund der Assoziativität können wir auch bei mehreren aufeinanderfolgenden Konjunktionen bzw. mehreren aufeinanderfolgenden Disjunktionen Klammern weglassen

• um weitere Klammern zu sparen, vereinbaren wir, dass Negation stärker bindet als Konjunktion und Disjunktion, und dass alle drei Verknüpfungen stärker binden als Implikation und Äquivalenz

  -> Wir schreiben also A ∧B ∧ ¬C =⇒ A ∧ ¬C

  statt (((A ∧B)∧(¬C)) =⇒ (A ∧(¬C))).

Für beliebige Aussagen A und B gilt:

Beweis:

Kontraposition ist häufig eine nützliche Beweismethode:

• angenommen, es ist die Wahrheit der Implikation A ⇒ B zu zeigen

• man nimmt zunächst an, B sei falsch

  -> mit etwas Glück kann man vielleicht daraus folgern, dass dann auch A falsch sein muss

• in diesem Fall hat man dann die Implikation (¬B) ⇒ (¬A), und daher wegen des Kontrapositionsprinzip auch die Implikation

  A ⇒ B gezeigt

• hilfreich ist diese Beweistechnik dann, wenn die Annahme der Falschheit von B eine Denkrichtung vorgibt, die man unter der Annahme der Wahrheit von A vielleicht nicht einschlagen würde.

• bei komplizierteren Beweisen reichen ausschließlich Äquivalenzumformungen oft nicht, deshalb werden wir oft so nicht vorgehen können!

• in den meisten Fällen wird man, um die Äquivalenz zweier Aussage A und B zu zeigen, zunächst die Implikation A ⇒ B und anschließend die Implikation B⇒ A zeigen müssen

• dies wird im Beweis oft dadurch kenntlich gemacht, dass man den Äquivalenzpfeil in zwei Implikationspfeile zerlegt und eben einmal „⇒“ zeigt, das ist die Implikation von links nach rechts, und dann auch noch „⇐“, die andere Implikation

um die Implikation A ⇒ B zu zeigen, können wir also wie folgt vorgehen:

• wir nehmen an, dass A und die Negation von B gelten

• können wir daraus eine falsche Aussage (einen sogenannten Widerspruch) herleiten, so gilt ¬(A ∧ ¬B), und daher haben wir die gewünschte Implikation bewiesen

• eine Menge M ist eine Zusammenfassung von „Objekten“ so dass für jedes „denkbare Objekt“ x eindeutig geklärt ist, ob x zu M gehört oder nicht

• „x ∈ M“ - x ist ein Element von M

• bei endlichen Mengen werden alle enthaltene Elemente zusammengefasst wie folgt:

• unendliche Mengen werden wie folgt beschrieben:

• Mengen können auch in beschreibender/impliziter Form beschrieben werden:

• Achtung: eine Menge muss nicht Elemente halten!

• die Aussage „4 ist eine natürliche Zahl“ können wir in Mengensprache formulieren als „4 ∈ N“

  -> fast alle Aussagen, die uns interessieren, können in Mengensprache formuliert werden, z.B. gilt:

  (b ist ein blaues Auto) ⇐⇒ (b ∈ {x | x ist ein blaues Auto})

• logische Umformungen können ebenfalls auf die Mengen übertragen werden

  
  

M ∩ N := {x | (x ∈ M)∧(x ∈ N)} heißt der Schnitt von M und N.

-> entspricht in der Aussagenlogik der Konjunktion

M ∪ N := {x | (x ∈ M)∨(x ∈ N)} heißt die Vereinigung von M und N.

-> entspricht in der Aussagenlogik der Disjunktion

M \ N := {x | (x ∈ M)∧(x 6∈ N)} heißt das Komplement von N in M.

-> entspricht nicht der Negation!

Eine Menge M heißt Teilmenge einer Menge N, geschrieben M ⊆ N, falls gilt ((x ∈ M) ⇒ (x ∈ N)). Wir schreiben dann M ⊆ N.

-> Der Strich in „⊆“ deutet an, dass M und N auch gleich sein dürfen. Wenn wir sagen wollen, dass M eine Teilmenge von N, aber nicht gleich ist, so schreiben wir:

• um zu zeigen, dass zwei Mengen gleich sind, kann man also zeigen, dass sie jeweils ineinander enthalten sind

  ->genauso, wie man eine Äquivalenz beweist, indem man zwei Implikationen zeigt

• das ist oftmals eine wichtige Beweismethode!

• Elemente von Mengen dürfen wieder Mengen sein!

• beim Umgang mit Mengen von Mengen muss man sehr genau zwischen den Symbolen „ ⊆ “ und „ ∈ “ unterscheiden:

  • ist M := {1,{2}}, so gilt {1} ⊆ M und {2} ∈ M

    -> aber die Aussagen {1} ∈ M und {2} ⊆ M sind falsch

• die Menge aller Teilmengen einer gegebenen Grundmenge

• Beispiel:

• ist in der Mathematik eine Menge, deren Elemente allesamt Teilmengen einer gemeinsamen Grundmenge sind

• Beispiel: M := {2,4}, P(M)={Ø, {2},{4},{2,4}}, Ms = {{2,4}}

• man unterscheidet (gewisse Zusammenfassungen von Objekten im Sinne von Cantor) zwischen Klassen und Mengen

  -> Mengen sind genau diejenigen Klassen, die selbst Element einer Klasse sind

• Schnitte, Vereinigungen, Komplemente, Teilmengen und Potenzmengen von Mengen sind wieder Mengen und es gelten die bekannten Identitäten

• da Teilmengen von Mengen wieder Mengen sind, ist jede Klasse, die R enthält keine Menge

  -> insbesondere ist die Klasse M := {M | M ist eine Menge} aller Mengen keine Menge

• die Ausdrücke „Das Auto ist blau.“ und „x 2 = 4“ sind keine Aussagen, weil ihr Wahrheitswert davon abhängt, welches Auto gemeint ist bzw. welche Zahl man in die Variable x einsetzt

• setzt man für jede freie Variable einen passenden Begriff ein erhält man eine Aussage