T04-Boolesche-Algebra-und-Beweise

Boolesche Algebra & Beweise

Zusammenfassung

Die Boolesche Algebra ist eine algebraische Struktur mit fünf Axiomen (Kommutativität, Assoziativität, Absorption, Distributivität, Komplement), aus denen sich weitere Regeln wie De Morgan, Konsenssatz, Idempotenz und das Dualitätsprinzip herleiten lassen. Jede Aussage, die ausschließlich aus den Axiomen bewiesen wird, gilt in allen Booleschen Algebren — also in ebenso wie in oder . Die zentrale Klausuraufgabe (A3a, 7 Punkte) verlangt einen Widerspruchsbeweis per Induktion über Primimplikanten.

Exam-Relevanz

Aufgabe 3a (7 Punkte) — Beweis durch Widerspruch per Induktion.

Behauptung (falsch): Die Anzahl an Primimplikanten ändert sich nicht, wenn ein Eintrag zu der ON-Menge hinzugefügt wird.

Der Beweis soll in zwei Schritten geführt werden:

  1. Induktion: Unter der Annahme der Behauptung gilt: Alle ON-Mengen haben genau so viele Primimplikanten wie die leere ON-Menge und auch so viele wie die ON-Menge mit allen Belegungen (d.h. ).
  2. Widerspruch: Die leere ON-Menge hat 0 Primimplikanten, die volle ON-Menge hat genau 1 Primimplikanten (nämlich die Konstante 1). Dies ist ein Widerspruch Behauptung ist falsch.

Diese Aufgabe kombiniert vollständige Induktion mit Widerspruchsbeweis — zwei der drei in der Vorlesung eingeführten Beweistechniken.

Axiome der Booleschen Algebra

Es sei eine Menge mit zwei binären Operationen und und einer unären Operation . Das Tupel heißt Boolesche Algebra, falls nichtleer ist und für alle die folgenden Axiome gelten:

Kommutativität

Assoziativität

Absorption

Distributivität

Achtung: In der Booleschen Algebra gilt Distributivität in beide Richtungen — anders als z.B. in , wo nur distributiv ist, nicht aber .

Komplement

Konventionen

  • statt , statt
  • , , oder für Negation
  • bindet stärker als , bindet stärker als

Wichtige Sätze

Alle folgenden Regeln sind aus den Axiomen ableitbar und gelten somit in jeder Booleschen Algebra.

Existenz und Eindeutigkeit neutraler Elemente

Die Elemente und sind eindeutig. Außerdem:

Doppeltes Komplement

Eindeutigkeit des Komplements

Idempotenz

Beweisskizze: (Absorption mit ).

De-Morgan-Regel

Beweisskizze (für die erste Gleichung): Zeige und mittels Distributivität und Komplement, dann folgt aus der Eindeutigkeit des Komplements .

Konsenssatz (Consensus)

Beweisskizze: Der Term wird durch Absorption "geschluckt": und analog für die andere Seite. Der Konsens-Term ist also redundant.

Resolution (duale Form des Konsenssatzes)

Dualitätsprinzip

Gilt eine aus den Axiomen abgeleitete Gleichung , so gilt auch die zu duale Gleichung, die aus durch gleichzeitiges Vertauschen von und sowie und hervorgeht.

Begründung (für den Fall ohne und ): Die Axiome sind paarweise dual zueinander. Jede Ableitung, die aus den Axiomen gewinnt, liefert bei Vertauschung von und die duale Gleichung, da jeder Schritt auf einem dualen Axiom beruht. Enthält auch oder , so beachte man, dass diese durch die Komplement-Axiome (, , etc.) eingeführt werden, die ebenfalls dual sind.

Beispiel:

Beweistechniken in BA

1. Direkter Beweis (Sukzessive Folgerungen)

Aus folgt , aus folgt , aus folgt , also gilt .

Beispiel: Zeige in jeder Booleschen Algebra.

2. Beweis durch Widerspruch (Indirekter Beweis)

Man nimmt das Gegenteil an und leitet einen Widerspruch her.

Vorgehen:

  1. Annahme: gilt.
  2. Schrittweise Folgerungen aus (und den Axiomen).
  3. Widerspruch (oder Widerspruch zu已知Tatsachen).
  4. ist falsch gilt.

Beispiel: Zeige: Es gibt kein mit und .

Annahme: Es gibt ein mit . Dann ist (da aus den Axiomen folgt). Widerspruch zu .

3. Vollständige Induktion

Induktionsanfang (IA): Beweise Aussage für (oder ).
Induktionsvoraussetzung (IV): Annahme: Aussage gilt für ein .
Induktionsschritt (IS): Beweise Aussage für unter Verwendung der IV.

Beispiel: Zeige .

  • IA (): ✓
  • IV:
  • IS:

Typische Klausuraufgabe

A3a — Widerspruchsbeweis per Induktion (7 Punkte)

Gegeben: Die Behauptung "Die Anzahl an Primimplikanten ändert sich nicht, wenn ein Eintrag zu der ON-Menge hinzugefügt wird."

Zu zeigen: Diese Behauptung ist falsch, durch Widerspruchsbeweis per Induktion.

Vollständiger Lösungsansatz

Schritt 1: Induktion über die Größe der ON-Menge

Sei die Aussage: "Jede ON-Menge der Größe hat genau so viele Primimplikanten wie die leere ON-Menge."

  • IA (): gilt trivial (leere Menge hat so viele Primimplikanten wie sich selbst).
  • IV: gelte für ein .
  • IS (): Sei eine ON-Menge der Größe . Dann existiert ein , sodass eine ON-Menge der Größe ist. Nach IV hat genau so viele Primimplikanten wie die leere ON-Menge. Nach der angenommenen Behauptung ändert sich die Anzahl der Primimplikanten nicht beim Hinzufügen von . Also hat auch genau so viele Primimplikanten wie die leere ON-Menge. gilt.

Damit gilt für alle , insbesondere auch für (die volle ON-Menge ).

Schritt 2: Widerspruch

  • Die leere ON-Menge () hat 0 Primimplikanten (die Funktion ist konstant 0, es gibt keinen Implikanten).
  • Die volle ON-Menge () hat genau 1 Primimplikanten, nämlich die Konstante 1 (das leere Monom), da jede Belegung die Funktion erfüllt.
  • Nach Schritt 1 müssten beide die gleiche Anzahl an Primimplikanten haben. Aber .

Widerspruch! Die Behauptung ist falsch.

Wichtige Hinweise

  • Die Induktion geht über die Größe der ON-Menge, nicht über die Anzahl der Variablen.
  • Der Schlüssel ist, dass die annahmebedingte Induktion die Behauptung auf alle ON-Mengen verallgemeinert — auch die Extremfälle (leer und voll), die offensichtlich unterschiedlich viele Primimplikanten haben.
  • In der Klausur müssen IA, IV, IS und der Widerspruch explizit und nachvollziehbar aufgeschrieben werden.

Übungsblätter

Blatt Aufgabe Thema Punkte
Blatt01 2a Dualitätsprinzip begründen 1
Blatt01 2b BA auf : Absorption & Komplement per Fallunterscheidung 3
Blatt01 3 O-Notation (Beweistechniken) 6
Blatt01 4a Induktion: Binärbaum Knoten 3
Blatt05 4a Widerspruchsbeweis: azyklischer Graph hat Wurzel —
Blatt05 4c Induktion: Eindeutigkeit der Belegung —
Blatt06 3a Boolescher Ring : 7 Ring-Axiome beweisen 13
Blatt06 6a Widerspruchsbeweis: Primimplikanten monotoner Funktionen enthalten nur positive Literale 3 (Bonus)

Quellen

Priorität

CRITICAL. A3a ist mit 7 Punkten der schwerste Einzelteil der Klausur und kombiniert zwei Beweistechniken. Die Axiome der BA sind die Grundlage für alle weiteren Themen (Schaltkreise, PLA, Minimalpolynome). Beherrsche:

  1. Die 5 Axiome auswendig (inkl. dualer Form).
  2. De Morgan, Konsenssatz, Dualitätsprinzip.
  3. Widerspruchsbeweis per Induktion (das A3a-Pattern).