2. Disjunktive Normalform
Erste Erkundung
In einer großen IT-Firma mit hohen Sicherheitsanforderungen gibt es am Eingang ein Zugangssystem für die Mitarbeiter mit drei Möglichkeiten:
|
|
Der Zugang für die Mitarbeiter wird nur freigegeben, wenn C und P erfüllt sind oder wenn C und S erfüllt sind.
In allen anderen Fällen bleibt der Zugang gesperrt.
Wie sieht die dazu passende Wertbelegungstabelle aus?
| C | P | S | Zugang |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
Die nächste Überlegung:
- In welchen Zeilen ist der Ausgang Zugang gleich 1?
| C | P | S | Zugang |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
Die nächsten Überlegungen:
- Wie lassen sich diese Bedingungen als logische Ausdrücke mit UND formulieren?
- Wie können diese Ausdrücke zusammengefasst werden, sodass der Zugang genau dann freigegeben wird?
C∧¬P∧S
C∧P∧¬S
C∧P∧S
Diese Terme lassen sich zu einem logischen Ausdruck zusammenfassen:
(C∧¬P∧S) ∨ (C∧P∧¬S) ∨ (C∧P∧S)
Im vorherigen Beispiel wurde analysiert, unter welchen Bedingungen ein Mitarbeiter Zugang zur Firma bekommt. Die Ausgangswerte wurden in einer Tabelle dargestellt, die einzelnen Zeilen als logische Bedingungen formuliert und schließlich alle Bedingungen zu einem einzigen logischen Ausdruck zusammengefasst.
Solche Ausdrücke, die aus ODER-Verknüpfungen von UND-Termen bestehen – wobei jeder UND-Term eine Kombination von Variablen oder deren Negationen darstellt – nennen wir disjunktive Normalform. Sie ist ein standardisiertes Format, um jede beliebige logische Funktion systematisch darzustellen.
Das Beispiel mit dem Zugangssystem zeigt: Mit der disjunktiven Normalform lassen sich auch komplexe Bedingungen übersichtlich in eine Formel übersetzen, die genau angibt, wann der Ausgang 1 ist.
Eine logische Formel steht in disjunktiver Normalform, wenn sie als ODER-Verknüpfung von UND-Termen geschrieben ist.
- Jeder Term in Klammern ist eine Konjunktion (UND-Verknüpfung)
- Die Gesamtheit aller Terme ist eine Disjunktion (ODER-Verknüpfung)
- Jede Zeile der Wahrheitstabelle, in der der Ausgang 1 ist, liefert einen UND-Term
- Jede boolesche Funktion kann in disjunktiver Normalform dargestellt werden
Hier nochmal das Vorgehen beim Herleiten einer DNF zusammengefasst:
- Wahrheitswerttafel aufstellen, falls nicht gegeben.
- Zeilen der Wahrheitstabelle mit Ausgang = 1 markieren
- Jede Zeile in eine UND-Bedingung umwandeln (1 → Variable, 0 → ¬Variable)
- Alle UND-Bedingungen mit ODER verknüpfen
- Optional: Vereinfachung der DNF zeigen
Aufgabe 1: Smarthome Lichtsteuerung
Grinda möchte ihr zu Hause smart gestalten und beginnt mit der Lichtsteuerung. Um diese zu realisieren hat sie drei Anhaltspunkte:
- B: Bewegung im Raum
- T: Tageslicht vorhanden
- M: Schalter manuell gedrückt
| B | T | M | Licht |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 |
- Markiere alle Zeilen, in denen Licht = 1.
- Wann ist das Licht im Raum an? Formuliere in Worten.
- Formuliere für jede markierte Zeile den UND-Term.
- Fasse alle UND-Terme zu einer disjunktiven Normalform (DNF) zusammen.
Lösung
- Wenn Bewegung im Raum ist und kein Tageslicht ist vorhanden ODER wenn der Schalter manuell betätigt wurde.
- (B∧¬T∧¬M)∨(¬B∧¬T∧M)∨(B∧¬T∧M)∨(¬B∧T∧M)∨(B∧T∧M)
Aufgabe 2: Getränkeautomat
Alfred steht vorm Getränkeautomaten und möchte sich eine Limo holen. Der Automat spuckt nur das gewünsche Getränk aus, wenn eine passende Münze eingeworfen wurde (M) und das Getränk vorrätig ist (V). Manchmal kann es aber auch sein, dass eine Sonderaktion läuft (S). Dann hat man Glück und bekommt sein Getränk (falls vorrätig) einfach so.
- Erstelle eine Wahrheitstabelle für M, V und S. Trage in jeder Zeile ein, ob der Automat das Getränk ausgibt (Ausgang = 1) oder nicht (Ausgang = 0).
- Formuliere den logischen Ausdruck als disjunktive Normalform.
Lösung
M V S Ausgabe 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 0 1 1 0 1 1 1 1 1 - (¬M∧V∧S) ∨ (M∧V∧¬S) ∨ (M∧V∧S)
Manchmal ergeben sich aus der Wahrheitstabelle viele UND-Terme, die man in der DNF zusammenfügt. Für komplexe Funktionen kann die DNF sehr lang werden.
Mit logischen Gesetzen lassen sich manche Formeln vereinfachen, sodass sie kürzer und übersichtlicher werden, ohne dass sich die Logik ändert.
Beispiel – Getränkeautomat:
Aus der Tabelle ergibt sich die DNF:
(¬M∧V∧S) ∨ (M∧V∧¬S) ∨ (M∧V∧S)
Alle Terme haben V gemeinsam – das bedeutet, dass das Getränk nur ausgegeben wird, wenn es vorrätig ist.
Man kann also V einmal vorne schreiben und die anderen Teile zusammenfassen:
V ∧ ((¬M∧S) ∨ (M∧¬S) ∨ (M∧S))
Schaut man sich die Klammern an, fällt auf: egal, ob M oder S zutrifft, das Getränk wird ausgegeben, solange V = 1.
Damit kann man die DNF einfacher schreiben:
V∧(M∨S)
Grundidee
Wenn mehrere UND-Terme sich nur in einer Variablen unterscheiden, beschreiben sie oft denselben Sachverhalt und können kürzer geschrieben werden.
Es wird also nach UND-Termen gesucht, die sich nur in einer Variablen unterscheiden.
Wenn ein Ergebnis unabhängig davon eintritt, ob eine Variable wahr oder falsch ist, muss diese Variable nicht mehr einzeln aufgeführt werden. Mann kann also die Terme zu einem zusammenfassen und die eine verschiedene Variable weglassen.
Beispiel:
(T ∧ D ∧ B) ∨
(T ∧ D ∧ ¬B) ∨
(T ∧ ¬D ∧ B)
(T ∧ D ∧ B) ∨ (T ∧ D ∧ ¬B) → T ∧ D
Der dritte Term bleibt unverändert:(T ∧ D) ∨ (T ∧ ¬D ∧ B)
Wenn mehrere UND-Terme sich nur in einer Variable unterscheiden, ist diese Variable für den Ausgang nicht entscheidend und kann beim Zusammenfassen weggelassen werden.