Aussagenlogik

Vereinfachung von aussagenlogischen Ausdrücken

Mit den bisher vorgestellten Rechenregeln und logischen Äquivalenzen können wir aussagenlogische Ausdrücke vereinfachen, indem wir darin enthaltene Variablen konsistent, d.h. durch identische Ausdrücke, ersetzen. Dies ist ein bewährtes Hilfsmittel, um komplexe Formeln einfacher verständlich darzustellen, ohne dabei ihren Wahrheitsgehalt zu verändern. Man nennt dies das Ersetzungsprinzip oder Substitutionsprinzip.

Es ist zu beachten, dass wir im Folgenden für eine bessere Übersicht in den komplexen Beispielen auf die abkürzenden Schreibweisen für die Konjunktion und die Negation zurückgreifen werden. Damit Sie sich an beide Arten der Notation gewöhnen, werden wir die etwas einfacheren Beispiele weiterhin in ausführlicher Schreibweise notieren.

Beispiele: Vereinfachung von Ausdrücken mit dem Substitutionsprinzip

1. Sei \(P\) ein aussagenlogischer Ausdruck. Dann lässt sich die Formel \((P \lor 0) \land (P \lor \neg P)\) wie folgt vereinfachen:
   
   Wegen der Neutralität von \(\lor\) ist \(P \lor 0 \equiv P\). Somit können wir \(P \lor 0\) in der obigen Formel durch \(P\) ersetzen, ohne dabei den Wahrheitsgehalt der Formel zu verändern.
   Weiterhin ist \(P \lor \neg P\) eine Tautologie, d.h. es ist \(P \lor \neg P \equiv 1\). Somit können wir \((P \lor \neg P)\) in der obigen Formel durch \(1\) ersetzen.
   Damit ergibt sich \((P \lor 0) \land (P \lor \neg P) \equiv P \land 1\).
   Wegen der Identität von \(\land\) gilt weiter \(P \land 1 \equiv P\) und wir können somit weiter \(P \land 1\) durch \(P\) ersetzen.
   Damit lässt sich die Formel insgesamt wie folgt vereinfachen: \[(P \lor 0) \land (P \lor \neg P) \equiv P \land (P \lor \neg P)\] \[\equiv P \land 1\] \[\equiv P\]
2. Seien \(P\) und \(Q\) aussagenlogische Ausdrücke. Dann lässt sich die Formel \(P \land (P \lor Q) \lor \neg P\) wie folgt vereinfachen:
   
   Weil die Konjunktion eine höhere Bindungsstärke hat als die Disjunktion, können wir die Absorptionsregel bezüglich der Konjunktion auf \(P \land (P \lor Q)\) anwenden und erhalten \(P \land (P \lor Q) \equiv P\). Somit können wir \(P \land (P \lor Q)\) durch \(P\) ersetzen und erhalten damit \(P \lor \neg P\).
   Weil \(P \lor \neg P\) eine Tautologie ist, gilt weiter \(P \lor \neg P \equiv 1\).
   Damit können wir die Formel insgesamt wie folgt vereinfachen: \[P \land (P \lor Q) \lor \neg P \equiv P \lor \neg P\] \[\equiv 1\]
3. Seien \(P\) und \(Q\) aussagenlogische Ausdrücke. Dann lässt sich die Formel \((P \lor (P \land Q)) \land (\neg P \lor Q)\) wie folgt vereinfachen:
   
   Mit der Regel zur Absorption bezüglich der Disjunktion ist \(P \lor (P \land Q) \equiv P\). Damit können wir die Formel in einem ersten Schritt vereinfachen zu \((P \lor (P \land Q)) \land (\neg P \lor Q) \equiv P \land (\neg P \lor Q)\).
   Mit der Regel zur Absorption bezüglich der Konjunktion mit Negation ist \(P \land (\neg P \lor Q) \equiv P \land Q\).
   Insgesamt können wir die Formel damit folgendermaßen vereinfachen: \[(P \lor (P \land Q)) \land (\neg P \lor Q) \equiv P \land (\neg P \lor Q)\] \[\equiv P \land Q\]
4. Seien \(P, Q, R\) und \(S\) aussagenlogische Ausdrücke. Dann lässt sich die Formel \((P\overline{Q}R\overline{S}) \lor (P\overline{Q}RS) \lor (PQRS)\) wie folgt vereinfachen:
   
   Weil das Kommutativgesetz und das Assoziativgesetz für die Konjunktion gelten, können wir die Reihenfolge der Operanden innerhalb einer Klammer jeweils beliebig tauschen und klammern. Dadurch können wir die Formel umformen zu \(((PR)(\overline{QS})) \lor ((PR)(\overline{Q}S)) \lor ((PR)(QS))\).
   Durch Anwendung des Distributivgesetzes können wir \((PR)\) jeweils aus den einzelnen Termen herausziehen und erhalten \((PR)((\overline{QS}) \lor (\overline{Q}S) \lor (QS))\).
   Wir können ein weiteres Mal das Distributivgesetz anwenden und den rechten Teilausdruck \((\overline{QS}) \lor (\overline{Q}S) \lor (QS)\) umformen zu \(\overline{Q}(\overline{S} \lor S) \lor (QS)\).
   Weil \(\overline{S} \lor S\) eine Tautologie ist, gilt \(\overline{S} \lor S \equiv 1\). Somit vereinfacht sich \(\overline{Q}(\overline{S} \lor S) \lor (QS)\) weiter zu \(\overline{Q} \land 1 \lor (QS)\).
   Mit der Identität der Konjunktion gilt \(\overline{Q} \land 1 \equiv \overline{Q}\) und damit können wir die Formel \(\overline{Q} \land 1 \lor (QS)\) weiter vereinfachen zu \(\overline{Q} \lor (QS)\).
   Indem wir die Regeln zur Absorption bezüglich der Disjunktion mit Negation leicht abwandeln, vereinfacht sich \(\overline{Q} \lor (QS)\) weiter zu \(\overline{Q} \lor S\).
   Wir setzen diesen vereinfachten Teilausdruck in die ursprüngliche Formel ein und erhalten \((PR)(\overline{Q} \lor S)\).
   Indem wir erneut das Distributivgesetz anwenden, lässt sich die Formel schließlich umformen zu \((PR\overline{Q}) \lor (PRS)\).
   Insgesamt lässt sich die Formel somit wie folgt vereinfachen: \[(P\overline{Q}R\overline{S}) \lor (P\overline{Q}RS) \lor (PQRS) \equiv ((PR)(\overline{QS})) \lor ((PR)(\overline{Q}S)) \lor ((PR)(QS))\] \[\equiv (PR)((\overline{QS}) \lor (\overline{Q}S) \lor (QS))\] \[\equiv (PR)(\overline{Q}(\overline{S} \lor S) \lor (QS))\] \[\equiv (PR)(\overline{Q} \land 1 \lor (QS))\] \[\equiv (PR)(\overline{Q} \lor (QS))\] \[\equiv (PR)(\overline{Q} \lor S)\] \[\equiv (PR\overline{Q}) \lor (PRS)\]