LERNZIELE:
Am Ende dieser Lektion wird der/die Studierende in der Lage sein:

1. den FND/FNC-Algorithmus auf konkrete Ausdrücke anzuwenden, um deren konjunktive und disjunktive Normalformen zu finden.
2. den Einsatz einfacher und zusammengesetzter Schalter in der Aussagenlogik zu verstehen.
3. die Struktur zusammengesetzter Schalter und schwarzer Kästen zu identifizieren.
4. die Wahrheitstabelle zu verwenden, um Informationen über ein Gerät zusammenzufassen.
5. die DNF und KNF eines Geräts aus seiner Wahrheitstabelle zu extrahieren.
6. einen zusammengesetzten Schalter zu entwerfen, der dasselbe Verhalten wie ein gegebenes Gerät aufweist.

INHALTSVERZEICHNIS
DER FND/FNC-ALGORITHMUS
ALGORITHMUS ZUR BESTIMMUNG DER NORMALFORM AUS WAHRHEITSTABELLEN: SCHWARZE KÄSTEN UND ZUSAMMENGESETZTE SCHALTER
BEISPIELÜBUNGEN

Obwohl wir gezeigt haben, dass alle Ausdrücke der Aussagenlogik äquivalent zu einer Normalform sind, haben wir bisher nichts darüber gesagt, wie man solche Normalformen findet. Um dies zu erreichen, betrachten wir einen Algorithmus, dessen Ziel es ist, Ausdrücke in Normalform zu erzeugen, und schließlich untersuchen wir die Anwendungen, die sich aus diesen Themen ergeben.

Der FND/FNC-Algorithmus

Der FND/FNC-Algorithmus ist eine Abfolge von Schritten, mit denen du aus jedem Ausdruck der Aussagenlogik den äquivalenten Ausdruck in DNF oder KNF (je nach Bedarf) finden kannst. Er wird wie folgt durchgeführt:

• SCHRITT 1: Ersetze alle Teil-Ausdrücke der Form (F\rightarrow G) durch (\neg F\vee G), ebenso wie (F\leftrightarrow G). Wiederhole diesen Schritt, bis alle Implikationen und Äquivalenzen eliminiert sind.
• SCHRITT 2: Eliminiere doppelte Negationen und wende die de-Morgan-Gesetze an, wo möglich. Folgende Ersetzungen sind durchzuführen:
  • \neg\neg G \longmapsto G
  • \neg(G\wedge H) \longmapsto (\neg G \vee \neg H)
  • \neg(G\vee H) \longmapsto (\neg G \wedge \neg H)

  Wenn keine Teil-Ausdrücke der Form \neg\neg G, \neg(G \wedge H) oder \neg(G \vee H) mehr vorhanden sind, fahre mit Schritt 3 fort.

• SCHRITT 3: Dieser Schritt unterteilt sich je nachdem, ob man zu einer DNF oder KNF gelangen möchte:
  • Wenn eine KNF gewünscht ist:

    Verwende die \vee-Distribution, wo immer möglich. Folgende Ersetzungen sind anzuwenden:

    \left.\begin{matrix}G\vee(H\wedge K) \\ \\ (H\wedge K)\vee G \end{matrix} \right\} \longmapsto (G\vee H)\wedge (G\vee K)

    Wenn keine Ausdrücke der Form G\vee(H\wedge K) oder (H\wedge K)\vee G mehr vorhanden sind, wurde die KNF erreicht.

  • Wenn eine DNF gewünscht ist:

    Verwende die \wedge-Distribution, wo immer möglich. Folgende Ersetzungen sind anzuwenden:

    \left.\begin{matrix}G\wedge(H\vee K) \\ \\ (H\vee K)\wedge G \end{matrix} \right\} \longmapsto (G\wedge H)\vee (G\vee K)

    Wenn keine Ausdrücke der Form G\wedge(H\vee K) oder (H\vee K)\wedge G mehr vorhanden sind, wurde die DNF erreicht.

Beispiele

Wende den FND/FNC-Algorithmus auf die folgenden Ausdrücke an, um ihre konjunktive und disjunktive Normalform zu finden.

1. (A\rightarrow (B\rightarrow A)) [LÖSUNG]
2. ((A\vee B)\rightarrow(\neg B \wedge A)) [LÖSUNG]

Algorithmus zur Bestimmung der Normalform aus Wahrheitstabellen: Schwarze Kästen und Zusammengesetzte Schalter

Der FND/FNC-Algorithmus erlaubt es uns, für jeden Ausdruck der Aussagenlogik seinen äquivalenten Ausdruck in Normalform zu finden. Es gibt jedoch Situationen, in denen kein Anfangsausdruck vorhanden ist, mit dem man arbeiten könnte. Das ist etwa der Fall, wenn wir nur das Ergebnis einer Wahrheitstabelle eines Ausdrucks F haben, dessen propositionaler Aufbau unbekannt ist. Dies in Worten zu erklären ist ein langwieriger Prozess; die Methode lässt sich jedoch viel besser durch Beispiele verdeutlichen. Deshalb folgen einige Beispiele, die ich im Video entwickle. Zuvor sollten jedoch die folgenden Konzepte betrachtet werden:

• Kabel: Medium, durch das ein Signal fließt.
• Knoten: Punkt, an dem sich drei oder mehr Kabel treffen.
• Einfacher Schalter: Gerät, das die Zustände Ein (1) und Aus (0) annehmen kann, wobei es sich immer in genau einem dieser Zustände befindet. Der Zustand „Ein“ lässt ein Signal durch, der Zustand „Aus“ blockiert es.
• Zusammengesetzter Schalter: Gerät, das aus einfachen Schaltern und Kabeln besteht.
• Black Box (Schwarze Kiste): Ein beliebiges Gerät, dessen innere Struktur nicht beobachtet werden kann.

Einfache Schalter werden modelliert durch aussagenlogische Variablen, zusammengesetzte durch Ausdrücke der Aussagenlogik. Die einfachsten Fälle ergeben sich durch die Disjunktions- und Konjunktionsverknüpfungen, wie sie im Folgenden dargestellt sind.

Schematische Darstellung der Konjunktion

Schematische Darstellung der Disjunktion

Beispielübungen

1. Gegeben ist ein Gerät, das aus einer Black Box und 4 geordneten Schaltern besteht. Die Aktivierung des Geräts erfolgt unter folgenden Bedingungen:
   • Bedingung 1: Es wird aktiviert, wenn zwei aufeinanderfolgende Schalter eingeschaltet sind. Diese Bedingung ist jedoch nicht mehr gültig, wenn drei aufeinanderfolgende Schalter eingeschaltet sind.
   • Bedingung 2: Es wird aktiviert, wenn alle Schalter ausgeschaltet sind.
   • Ausnahme: Wenn keine der obigen Bedingungen erfüllt ist, wird das Gerät ausgeschaltet.

   a) Fasse diese Informationen in einer Wahrheitstabelle zusammen. [LÖSUNG]

   b) Leite aus der Wahrheitstabelle die DNF und KNF ab, die das Verhalten der Maschine reproduzieren. [LÖSUNG]

   c) Verwende die im vorherigen Schritt erhaltene KNF oder DNF (die einfachere von beiden), um einen zusammengesetzten Schalter zu entwerfen, der das gleiche Verhalten wie das Gerät aufweist. [LÖSUNG]

2. Dasselbe wie in der vorherigen Aufgabe, nur dass das Gerät jetzt 5 Schalter besitzt. [HERAUSFORDERUNG FÜR DIE LESERIN / DEN LESER]