Aussagenlogische Formeln vereinfachen
Aufgabe
Nutze logische Identitäten, um die folgende aussagenlogische Formel auf möglichst einfache Gestalt zu bringen:
Ein großes Problem bei der Anwendung logischer Identitäten ist oftmals das Verständnis dafür, dass ein 
, 
oder 
aus der Aufgabenstellung nicht identisch ist mit einem , oder aus den logische Identitäten.
Um dieses Problem zu verdeutlichen und gleichzeitig dass Verständnis dafür zu erhöhen, nehmen wir hier eine Umbenennung der aussagenlogischen Variablen aus der Aufgabenstellung vor:
Sei 
, sei 
und sei 
.
Damit ergibt sich folgende (leicht veränderte) Aufgabenstellung:
Aufgabe
Nutze logische Identitäten, um die folgende aussagenlogische Formel auf möglichst einfache Gestalt zu bringen:
Ein möglicher Lösungsweg
Das folgende Video erläutert einen möglichen Lösungsweg:
Die folgende Aneinanderreihung der Anwendung der Gesetze stellt einen möglichen Lösungsweg dar. Es gibt darüber hinaus jedoch noch viele alternative Lösungswege, welche am Ende alle zum gleichen Ziel führen.
![{\displaystyle {\begin{alignedat}{2}&((X\rightarrow Y)\rightarrow (Y\rightarrow Z))\rightarrow Z&\qquad [{\text{Implikation umformen}}]\\[.3cm]\equiv \quad &\neg ((X\rightarrow Y)\rightarrow (Y\rightarrow Z)\ )\lor Z&\qquad [{\text{Implikation umformen}}]\\[.3cm]\equiv \quad &\neg (\neg (X\rightarrow Y)\lor (Y\rightarrow Z)\ )\lor Z&\qquad [{\text{Implikation umformen}}]\\[.3cm]\equiv \quad &\neg (\neg (\neg X\lor Y)\lor (Y\rightarrow Z)\ )\lor Z&\qquad [{\text{Implikation umformen}}]\\[.3cm]\equiv \quad &\neg (\ \neg (\neg X\lor Y)\lor (\neg Y\lor Z)\ )\lor Z&\qquad [{\text{De Morgansches Gesetz}}]\\[.3cm]\equiv \quad &\neg (\ (\neg \neg X\land \neg Y)\lor (\neg Y\lor Z)\ )\lor Z&\qquad [{\text{Doppelnegationsgesetz}}]\\[.3cm]\equiv \quad &\neg (\ (X\land \neg Y)\lor (\neg Y\lor Z)\ )\lor Z&\qquad [{\text{De Morgansches Gesetz}}]\\[.3cm]\equiv \quad &\neg (\ X\land \neg Y)\land \neg (\neg Y\lor Z)\lor Z&\qquad [{\text{De Morgansches Gesetz}}]\\[.3cm]\equiv \quad &(\ \neg X\lor Y)\land (\neg \neg Y\land \neg Z)\lor Z&\qquad [{\text{Doppelnegationsgesetz}}]\\[.3cm]\equiv \quad &(\ \neg X\lor Y)\land (Y\land \neg Z)\lor Z&\qquad [{\text{Klammern auflösen}}]\\[.3cm]\equiv \quad &(\ \neg X\lor Y)\land Y\land \neg Z\lor Z&\qquad [{\text{Bindungsstärke beachten!}}]\\[.3cm]\equiv \quad &(\ (\ \neg X\lor Y)\land Y\land \neg Z)\lor Z&\qquad [{\text{Kommutativgesetz}}]\\[.3cm]\equiv \quad &(\ (\ Y\lor \neg X)\land Y\land \neg Z)\lor Z&\qquad [{\text{Kommutativgesetz}}]\\[.3cm]\equiv \quad &(\ Y\land (\ Y\lor \neg X)\land \neg Z)\lor Z&\qquad [{\text{Absorptionsgesetz}}]\\[.3cm]\equiv \quad &(\ Y\land \neg Z)\lor Z&\qquad [{\text{Distributivgesetz}}]\\[.3cm]\equiv \quad &(\ Y\lor Z)\land (\neg Z\lor Z)&\qquad [{\text{Komplementärgesetz}}]\\[.3cm]\equiv \quad &(\ Y\lor Z)\land 1&\qquad [{\text{Neutralitätsgesetz}}]\\[.3cm]\equiv \quad &Y\lor Z&\qquad [{\text{Fertig}}]\\[.3cm]\end{alignedat}}}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/f7682fe36e772d4b047f8af116762b90211ee548)
Hinweis
Der hier gezeigt Lösungsweg ist ein sehr ausführlich dargestellter Weg. Wer das Prinzip verstanden und entsprechende Erfahrungen mit der Anwendung logischer Identitäten aufgebaut hat, wird in der Lage sein, mehrere Schritte auf einmal durchzuführen.
Aber Vorsicht!
Mehrere Schritte auf einmal durchzuführen bedeutet immer ein erhöhtes Riskio in Bezug auf Fehler. Gerade zu Beginn sollte man deshalb lieber ausführlicher arbeiten. Je mehr Erfahrung man hat, desto mehr Schritte können auch (fehlerfrei) auf einmal erfolgen.
Die Sache mit der Bindungsstärke
In dem gezeigten Lösungsweg wird einmal auf die Bindungsstärke hingewiesen.
Die Bindungsstärke der Junktoren ist vergleichbar mit der Bedeutung des allgemein bekannten mathematischen Grundsatzes: Punkt- vor Strichrechnung.
Wichtig
Punkt- vor Strichrechnung
Du erinnerst dich in Bezug auf Addition und Multiplikation an:
Man kann hier sagen: Die Bindungsstärke der Multiplikation (*) ist größer als die Bindungsstärke der Addition (+). Aus diesem Grund muss die Multiplikation vor den beiden Additionen ausgeführt werden.
Die Klammern bei 
können gesetzt werden, sie müssen aber nicht gesetzt werden.
Falls die Addition vor der Multiplikation ausgeführt werden soll, müssen entsprechend andere Klammern gesetzt werden:
Allerdings ist das Ergebnis dann auch ein Anderes.
Die Klammern bei 
sowie bei 
müssen in diesem Fall gesetzt sein, sie dürfen nicht entfallen.
Frage
Wie lautet das Ergebnis dieser Rechnung:
Bindungsstärke der Junktoren in der Aussagenlogik
Die Bindungsstärke der Junktoren in der Aussagenlogik ist nun wie folgt definiert:
bindet am stärksten, dahinter folgen 
und 
.
Analog zu Punkt- vor Strichrechnung lässt sich hier also festhalten:
- Die Negation () bindet stärker als das logische UND (
).
- Das logische UND () bindet stärker als das logischen ODER (
).
- Das logische ODER () bindet stärker als die Implikation (
).
- Die Implikation () bindet stärker als die Äquivalenz ().
Hier noch einmal der Auszug aus dem obigen Lösungsweg, in dem auf die Beachtung der Bindungsstärke hingewiesen wird:
![{\displaystyle {\begin{alignedat}{2}&(\ \neg X\lor Y)\land Y\land \neg Z\lor Z&\qquad [{\text{Bindungsstärke beachten!}}]\\[.3cm]\equiv \quad &(\ (\ \neg X\lor Y)\land Y\land \neg Z)\lor Z&\\[.3cm]\end{alignedat}}}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/2200e38d055695fdd069ae0e5a96de329af684f0)
Hinweis
In der unteren Zeile ist ein Klammerpaar hinzugekommen. Dieses Klammerpaar kann gesetzt werden, es muss aber nicht gesetzt werden.
Dieses folgt direkt aus dem Grundsatz:
Das logische UND () bindet stärker als das logischen ODER ().
Das Klammerpaar ist in dem aufgezeigten Lösungsweg freiwillig gesetzt worden, um deutlich zu machen, dass eine Vereinfachung von 
zu 
an dieser Stelle nicht erlaubt ist.
