6.2.10 Aussagenlogische Formeln vereinfachen

Aussagenlogische Formeln vereinfachen

Aufgabe

Nutze logische Identitäten, um die folgende aussagenlogische Formel auf möglichst einfache Gestalt zu bringen:

$((X\rightarrow Y)\rightarrow (Y\rightarrow Z))\rightarrow Z$

Ein möglicher 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.

${\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}}$

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.