∀ Mathe 1 PrepDiskrete Mathematik · Folien 1–3

Mengenbeweise & Boolesche Algebra

ca. 15 min0 / 4 Übungen

Viele Aufgaben sagen „Zeigen Sie …“. Hier lernst du die zwei Standardwerkzeuge für Mengen: den Elementbeweis mit zwei Inklusionen und das Rechnen mit Gesetzen (Boolesche Algebra).

Werkzeug 1: Elementbeweis

Die Schablone

A ⊆ B zeigen: „Sei x ∈ A beliebig.“ → Definition von A auspacken (was weiß ich über x?) → umformen → Definition von B einpacken → „Also x ∈ B.“

A = B zeigen: beide Richtungen, A ⊆ B und B ⊆ A (Bsp. 1.14, Folien 1 S. 22–23).

Das Wort beliebig ist wichtig: Du darfst über x nichts annehmen außer x ∈ A. Ein Beispiel (x = 3) beweist nichts.

Beispiel · A \ (A \ B) = A ∩ B
Zeige für beliebige Mengen A, B: A \ (A \ B) ⊆ A ∩ B.
    0 / 5

    Alternative: Wahrheitstafel für Mengen

    Statt zwei Inklusionen kann man auch jedes Gebiet im Venn-Diagramm einzeln prüfen. Die Gebiete sind genau die Zeilen einer Wahrheitstafel über „x ∈ A“, „x ∈ B“ (Satz 1.13, Folien 1 S. 19–21).

    Am Beispiel De Morgan: Komplement von A ∪ B gegen Ā ∩ B̄. Eigene Animation der KI.
    ✏️ Übung · Beweis zusammenbauenmittel
    Zu zeigen: Für Mengen A, B, C mit A ⊆ B gilt A ∩ C ⊆ B ∩ C.
    Bausteine (anklicken zum Anhängen)
    Dein Beweis (anklicken entfernt)

      Werkzeug 2: Gesetze der Booleschen Algebra

      Definition · Boolesche AlgebraDef. 1.21, Folien 2 S. 10–11
      Für ⊓ (z. B. ∩, ∧), ⊔ (z. B. ∪, ∨), ¬ (Komplement), 0 (∅) und 1 (Grundmenge M) gelten:
      • (A1) Assoziativ, (A2) Kommutativ
      • (A3) Distributiv: a ⊓ (b ⊔ c) = (a ⊓ b) ⊔ (a ⊓ c) und a ⊔ (b ⊓ c) = (a ⊔ b) ⊓ (a ⊔ c)
      • (A4) a ⊓ 1 = a, a ⊔ 0 = a    (A5) a ⊓ ¬a = 0, a ⊔ ¬a = 1
      Daraus folgen u. a. a ⊓ a = a (Satz 1.23), a ⊓ 0 = 0, a ⊔ 1 = 1 (Satz 1.25), De Morgan ¬(a ⊓ b) = ¬a ⊔ ¬b (Satz 1.26).
      Wie finde ich den nächsten Schritt?
      1. Steht ein Strich über einem zusammengesetzten Ausdruck? → De Morgan, damit die Striche nur noch auf einzelnen Buchstaben sitzen.
      2. Kommt derselbe Teil in zwei Klammern vor? → ausklammern (Distributivgesetz rückwärts).
      3. Steht X neben X? → Komplementierung: X ∪ X = M, X ∩ X = ∅.
      4. Steht M oder ∅ dabei? → Beschränktheit: X ∩ M = X, X ∪ ∅ = X, X ∪ M = M, X ∩ ∅ = ∅.
      ✏️ Übung · Vereinfachen, Schritt für Schrittmittel
      (A ∩ B) ∪ (A ∩ B)
      Welcher Schritt bringt dich weiter?
      ✏️ Übung · Mit De Morganknifflig
      A ∪ B ∪ (A ∪ B)
      Welcher Schritt bringt dich weiter?
      ✏️ Übung · Gesetze erkennenmittel
      Womit vereinfacht sich A ∩ (A ∪ B) am schnellsten?